Fast circuit topologies for finding the maximum of n k-bit numbers

Abstract

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(log2 n + log2 k), whereas the timing complexity of the fastest topology in previous work is O(log2 n log2 k). 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 ow, which nds 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.