Fast circuit topologies for finding the maximum of n k-bit numbers
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
Bir sayı kümesinin maksimum (ya da minimum) elemanının değerini ve/veya adresini (pozisyonunu) bulmak en temel aritmetik işlemlerden biridir. Çeşitli uygulama alanlarındaki birçok sistem, bu işlemi yerine getiren hızlı devrelere ihtiyaç duyar. Bu tezde, n tane k-bit uzunluğunda sayının en büyüğünün (benzer biçimde en küçüğünün) hem değerini hem de adresini bulan devreler için detaylı bir literatür taraması ve üç tane yeni devre topolojosi sunuyoruz. Önerdiğimiz topolojileri şu şekilde adlandırıyoruz: Array-based Topology (AbT), Hybrid Binary tree Topology (HBT) ve Quad tree Topology (QT). Önerilen topolojilerden en hızlısı (AbT) işini O(logn + logk) sürede tamamlarken, literatürdeki en hızlı topolojinin işini tamamlaması için O(logn logk) süre gerekir. Hem literatürdeki topolojiler hem de önerilen topolojiler için HDL kod üreteçleri yazdık. Bu otomatik kod üreteçleri herhangi bir n ve k değeri için ilgili topolojinin HDL kodunu üretebilecek yetenektedirler. Daha sonra ise, en iyi zaman kısıtını ikilik arama algoritmasına benzer bir yaklaşım ile bulan, yinelemeli ve standard-devre tabanlı bir sentez süreci uyguladık. Böylece, hem önerilen topolojiler hem de literatürdeki topolojiler için alan, güç tüketimi ve zaman sonuçlarını elde ettik. Ayrıca, bu sonuçları kullanarak şu birleşik başarım kıstaslarını da hesapladık: alan-zaman çarpımı (AZÇ), alan-zaman-kare çarpımı (AZ2Ç), güç-zaman çarpımı (GZÇ) ve enerji-zaman çarpımı (EZÇ). Sentez sonuçları, literatürdeki en hızlı devrenin, ortalamada AbT'den 1.61 kat, QT'den 1.28 kat ve HBT'den 1.01 kat daha yavaş olduğunu gösterdi. Finding the value and/or address (position) of the maximum (or similarly minimum) element of a set of binary numbers is a fundamental arithmetic operation. Numerous systems, which are used in various application areas, require fast (low-latency) circuits to carry out this operation. In this thesis, we present a detailed literature survey of previous works and propose three circuit topologies that determine both value and address of the maximum (or similarly minimum) element within an n-element set of k-bit binary numbers. Our proposed topologies are Array-based Topology (AbT), Hybrid Binary tree Topology (HBT), and Quad tree Topology (QT). The timing complexity of the fastest proposed architecture (AbT) is O(logn + logk), whereas the timing complexity of the fastest topology in previous work is O(logn logk). We wrote RTL code generators for the proposed topologies as well as their competitors. These automated generators are scalable to any value of n and k. Then, we applied a standard-cell based iterative synthesis flow, which finds the optimum timing through binary search. We obtained area, power consumption, and timing results for the proposed topologies as well as their competitors. Using these results, we also compute some combined performance metrics such that area-timing product (ATP), area-timing-square product (AT2P), power-timing product (PTP), and energy-timing product (ETP). The synthesis results showed that on the average, AbT is 1.61 times, QT is 1.28 times, and HBT is 1.01 times faster than the fastest in the literature.
Collections