A fast circuit topology for finding the maximum of n k-bit numbers

Yuce B., Ugurdag H. F., Gören S., DÜNDAR G.

21st Symposium on Computer Arithmetic, ARITH 2013, Austin, TX, Amerika Birleşik Devletleri, 7 - 10 Nisan 2013, ss.59-66, (Tam Metin Bildiri) identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/arith.2013.35
  • Basıldığı Şehir: Austin, TX
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.59-66
  • Anahtar Kelimeler: Area-timing product, Computer arithmetic, Logic synthesis, Maximum finder, Minimum finder, Timing optimization
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

Finding the value and/or address (position) of the maximum element of a set of binary numbers is a fundamental arithmetic operation. Numerous systems, which are used in different application areas, require fast (low-latency) circuits to carry out this operation. We propose a fast circuit topology called Array-Based maximum finder (AB) to determine both value and address of the maximum element within an n-element set of k-bit binary numbers. AB is based on carrying out all of the required comparisons in parallel and then simultaneously computing the address as well as the value of the maximum element. This approach ends up with only one comparator on the critical path, followed by some selection logic. The time complexity of the proposed architecture is O(log 2n + log2k) whereas the area complexity is O(n 2k). We developed RTL code generators for AB as well as its competitors. These generators are scalable to any value of n and k. We applied a standard-cell based iterative synthesis flow that finds the optimum time constraint through binary search. The synthesis results showed that AB is 1.2-2.1 times (1.6 times on the average) faster than the state-of-the-art. © 2013 IEEE.