Finding isolated minterms in logic functions and developing an efficient simplification algorithm

Autor: Akar, Hakan
Přispěvatelé: Başçiftçi, Fatih, Enstitüler, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Ana Bilim Dalı
Jazyk: turečtina
Rok vydání: 2020
Předmět:
Popis: Bilişim sektörünün hemen hemen bütün alanlarında kullanılan entegre devrelerin daha küçük, daha sade ve daha hızlı olabilmesi için lojik fonksiyonların sadeleştirilmesi büyük önem taşımaktadır. Lojik fonksiyonların sadeleştirilmesi için çok farklı teknikler ve algoritmalar geliştirilmiştir. Bu tez çalışmasında bir çeşit doğrudan örtme tekniği sunulmuştur. Ayrıca lojik fonksiyon dosyalarının içindeki izole mintermler tespit edilerek sadeleştirme işleminde iyileştirme sağlanmıştır. Sunulan sadeleştirme tekniklerinin algoritmaları hazırlanmış, çok işlemcili bilgisayarlara uyumlu parallel versiyonu geliştirilmiş ve C# programında kodlanmıştır. Bu çalışmada; lojik fonksiyon dosyalarının ne kadar sadeleştirilebileceği, izole mintermlerin tespitinin lojik fonksiyonların sadeleştirilmesini ne kadar etkilediği, fonksiyon sadeleştirme ve izole minterm tespiti işleminin ne kadar paralel hale getirilebileceği araştırılmıştır. Araştırma sonuçlarına göre yakın sonuç kapsama algoritmasının (YSKA) sadeleştirme oranı %82,86 iken, kesin sonuç kapsama algoritmasında (KSKA) bu oran %0,34 artarak %83,20 olmuştur. YSKA ve KSKA 41 benchmarkta eşit sayıda Asal İmplikant (AI) sonucuna ulaşmış, 9 benchmarkta ise KSKA daha iyi sonuç bulmuştur. Fakat YSKA, KSKA'na göre 6,92 kat daha hızlı çalışmıştır. Araştırma sonucunda giriş değişkeni ve ON mintermi sayısının fazla olmadığı benchmarklarda YSKA ve KSKA aynı ya da çok yakın sadeleştirme yaptıkları tespit edilmiştir. Yüksek sayıda ON ve/veya OFF mintermi içeren benchmarklarda KSKA yüksek çalışma süresine rağmen daha sade sonuçlara ulaşmıştır. Bu tez çalışmasında, izole mintermlerin tespitinin hem YSKA hemde KSKA'nın sonuç kalitelerini arttırdığı ve genel ortalamada çalışma zamanlarını düşürdüğü tespit edilmiştir. İzole mintermlerin tespiti algoritması YSKA üzerinde %2,33 sonuç kalitesi artışı, %12,68 çalışma zamanı kazanımı sağlamıştır. İzole mintermlerin tespiti algoritması KSKA üzerinde %1,09 sonuç kalitesi artışı, %6,51 çalışma zamanı kazanımı sağlamıştır. İzole mintermleri tespit edip sıralamak için geliştirilen algoritma sıralama aşamasında işlem zamanı kullanırken, YSKA ve KSKA'nın işini kolaylaştırarak sadeleştirme aşamasında zaman kazandırmaktadır. Algoritmaların paralel programlamaya uyarlanması, izole mintermlerin tespiti ve YSKA'nda önemli iyileştirmeler (%49,37, %22,88) sunarken, KSKA'nda belirgin bir farklılık (%1,18, %0,65) oluşturmamıştır. Paralel programlamanın algoritmaların sonuç kalitesi, yani bulduğu AI sayısı üzerinde herhangi bir etkisi olmamıştır.
Minimization of logic functions is very important for the development of simpler, smaller and faster integrated circuits which are used in almost every area of IT sector. Many techniques and algorithms have been developed to simplify logic functions. In this study, a new version of direct cover technique is presented. In addition, minimization process is improved by finding isolated minterms in logic function files. Algorithms for presented minimization technique are prepared and parallel computing algorithms compatible with multicore computers are developed and all these algorithms are coded in Microsoft C# program. The following questions have been answered in this study; how much minimization is possible for logic function files, how the process of finding isolated minterms affect function minimization, what is the potential speedup in parallelization of function minimization and isolated minterm detection algorithms. Results revealed that minimization ratio of Close Results Covering Algorithm (Yakın Sonuç Kapsama Algoritması, YSKA) (82.86%) are increased by 0.34% in Exact Results Covering Algorithm (Kesin Sonuç Kapsama Algoritması, KSKA) algorithm (83.20%). Both YSKA and KSKA finds equal number of PIs in 41 benchmarks and KSKA finds better results in 9 benchmarks. However, YSKA computes PIs 6.92 times faster. It was also found that YSKA and KSKA perform the same or very close minimization results in benchmarks where input variable and ON minterms are not high. On benchmarks with a high number of ON and/or OFF minterms, KSKA achieved better results despite its high uptime. In this thesis, it has been found that the detection of isolated minterms improves the quality of the results of both YSKA and KSKA and decreases the average computing time. The detection algorithm of isolated minterms resulted in 2.33% quality increase and 12.68% faster computing time on YSKA. The detection algorithm of isolated minterms resulted in 1.09% quality increase and 6.51% faster computing time on KSKA. While the algorithm developed for detecting and sorting the isolated minterm uses processing time in the sorting phase, it saves time in minimization phase by facilitating the work of the YSKA and KSKA. While parallelization of algorithms has provided significant improvements in detection of isolated minterms and YSKA (49.37%, 22.88%), there was no significant improvement (1.18%, 0.65%) in KSKA algorithm. Parallel programming had no effect on the result quality of the algorithms like the number of prime implicants.
Databáze: OpenAIRE
Externí odkaz: