SRAM tabanlı FPGA devrelerinde LUT seviyesinde fonksiyonlar arasındaki NPN ilişkilerin maksimize edilmesi
Maximizing NPN equivalent functions in a LUT-level circuit 
for SRAM-based FPGAs
Yazar: UĞUR CORUH
Danışman: YRD. DOÇ. DR. TUĞÇE BALLI ALTUĞLU ; DOÇ. DR. FATİH KOÇAN
İstanbul Kemerburgaz Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering
Dizin: FPGA = FPGA

Özet:
Bu tezde, yeni bir FPGA (Field Programmable Gate Array) sentez algoritması geliştirmek için araştırma yapılmıştır. Yeni algoritma LUT (Lookup Table) seviyesindeki devrelerde NPN (Input Negation, Input Permutation and Output Negation) denk fonksiyon sayısını artırmayı amaçlamaktadır. Hedefimiz, NPN denk fonksiyonlar arasında SRAM (Static Random Access Memory ) paylaşımı sağlayan, yeni ve verimli bir FPGA mimarisi geliştirmektir. Bu tez çalışmasında, hızlı bir şekilde NPN denklik kontrolü yapmak amacıyla, FPGA sentez aracı olan ABC (A System for Sequential Synthesis and Verification) aracı için eklenti olarak çalışan bir araç geliştirilmiştir. Geliştirmiş olduğumuz aracın çalışma prensibi şöyledir: Öncelikle, iki adet mantıksal fonksiyonu hiper çizge olarak formülize eder. Daha sonra, çizge izomorfizm kontrolü yapan Nauty izomorfizm karşılaştırma aracını çağırıp bu iki çizgenin denkliklerini kontrol eder. Kullanıcılar, referans fonksiyon kümesini ABC aracına girdi olarak verirler. ABC aracı geliştirdiğimiz eklentiyi kullanarak kullanıcılardan aldığı fonksiyon kümesindeki fonksiyonlara NPN denk, LUT fonksiyonları oluşturur. Kullanıcının girdi olarak verdiği fonksiyonlar şöyle seçilir: İlk önce, devre orijinal ABC aracı ile sentezlenir. Normal ABC aracı sentezleme sonucu oluşan devreler analiz edilip en çok tekrar eden fonksiyon sınıfları belirlenir. Sonrasında bu sınıflardan seçilen temsilci fonksiyonlar geliştirmiş olduğumuz eklenti ile ABC aracında sentezleme için seçilir. Bir defaya mahsus da geliştirdiğimiz eklenti aktifleştirilip ABC aracı kullanılarak sentezleme yapılır ve oluşturulan LUT'ların girdi olarak verilen fonksiyonlara NPN denk olması sağlanır. Geliştirmiş olduğumuz ABC aracı eklentisi, olabilecek en iyi şekilde kullanıcıların girdi olarak verdiği fonksiyonlara NPN denk LUT'lar oluşturmaya çalışır. Önerilen araştırmanın performansı, MCNC (Microelectronics Center of North Carolina)  referans devreleri ile yapılan bir dizi FPGA sentezleme ile ölçülmüştür. Bu tez çalışmasında, beş ve altı girişli fonksiyonlar araştırılmıştır. Beş ve altı girişli fonksiyonların seçilmesinin nedeni pratik olarak kullanılabilir olmalarıdır.

Abstract:
In this thesis, we investigate a novel FPGA (Field Programmable Gate Array) synthesis algorithm. The new algorithm aims at maximizing the number of NPN (Input Negation, Input Permutation and Output Negation) equivalent functions in a LUT (Lookup Table) level circuit. The goal is to efficiently utilize newly proposed FPGA architectures that enable SRAM (Static Random Access Memory) sharing among NPN-equivalent functions. Our algorithm utilizes a fast NPN-equivalence checker tool and incorporates it into an FPGA synthesis tool, called the ABC (A System for Sequential Synthesis and Verification) tool. The NPN-equivalence checker tool formulates two logic functions as hyper-graphs and calls a hyper-graph isomorphism checker tool, called Nauty graph isomorphism tool, to check the equivalency of two hyper-graphs. The user provides a set of functions as input to the extension of ABC tool that we developed and forces the ABC tool to generate LUT functions that are NPN-equivalent to the user inputted functions. The user specified functions are identified as follows. First, the circuit is synthesized with the original, unmodified ABC tool. The resulting circuit is analyzed and the most frequently occurring NPN equivalence classes are identified. Later, a representative function from each of these classes is selected as the input to the second synthesis process. After that, we synthesize the circuit one more time with the modified ABC tool to force the LUTs to be equivalent to the identified functions. The modified ABC tool does its best to generate LUTs that are NPN-equivalent to the user specified functions. The performance of the proposed algorithm is evaluated by performing the synthesis on a set of benchmark circuits, namely MCNC (Microelectronics Center of North Carolina) synthesis benchmarks. In our experiments, we have investigated five and six input functions, since these input function sizes were applicable in practice.