Back to Search

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

Title	A fast circuit topology for finding the maximum of n k-bit numbers
Author	Yuce, B., Uğurdağ, Hasan Fatih, Gören, S., Dundar, G.
Publication Date:	2013
Publication Place	- IEEE
Subject	Computational complexity, Digital arithmetic, Iterative methods, Network topology, Program compilers
Type	Document
Language	English
Digital	Yes
Manuscript	No
Library:	Özyeğin University
Library Asset ID	1063-6889
Record ID	b10452a0-c703-4a3c-a021-e51101176179
Library Location	Electrical & Electronics Engineering
Date	2013
Notes	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Sample Text	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(log2n + log2k) whereas the area complexity is O(n2k). 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.
DOI	10.1109/ARITH.2013.35

View in source Özyeğin University Özyeğin University - Historical works, archives, and periodicals search engine

Özyeğin University

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

Author Yuce, B., Uğurdağ, Hasan Fatih, Gören, S., Dundar, G.

Publication Date 2013

Publication Place - IEEE

Subject Computational complexity, Digital arithmetic, Iterative methods, Network topology, Program compilers

Type Document

Language English

Digital Yes

Manuscript No

Library Özyeğin University

Library Asset ID 1063-6889

Record ID b10452a0-c703-4a3c-a021-e51101176179

Library Location Electrical & Electronics Engineering

Date 2013

Notes Due to copyright restrictions, the access to the full text of this article is only available via subscription.

Sample Text 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(log2n + log2k) whereas the area complexity is O(n2k). 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.

DOI 10.1109/ARITH.2013.35