Pavol Duris, Ondrej Sykora, Clark D. Thompson and Imrich Vrto
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-85-244
June 1985
http://www2.eecs.berkeley.edu/Pubs/TechRpts/1985/CSD-85-244.pdf
We prove tight upper and lower bounds on the area of semielective, when-oblivious VLSI circuits for the problem of l-selection. The area required to select the l-th smallest of n k-bit numbers is found to be heavily dependent on the relative sizes of l, k, and n. When l < 2^ k, the minimal area is A = 0mega((min{ n , l( k - log l)}). When l >= 2^ k, A = Omega(2^ k (log l - k + 1)).
BibTeX citation:
@techreport{Duris:CSD-85-244, Author = {Duris, Pavol and Sykora, Ondrej and Thompson, Clark D. and Vrto, Imrich}, Title = {A Minimum-Area Circuit for l-Selection}, Institution = {EECS Department, University of California, Berkeley}, Year = {1985}, Month = {Jun}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1985/5513.html}, Number = {UCB/CSD-85-244}, Abstract = {We prove tight upper and lower bounds on the area of semielective, when-oblivious VLSI circuits for the problem of <i>l</i>-selection. The area required to select the <i>l</i>-th smallest of <i>n</i> <i>k</i>-bit numbers is found to be heavily dependent on the relative sizes of <i>l</i>, <i>k</i>, and <i>n</i>. When <i>l</i> < 2^<i>k</i>, the minimal area is <i>A</i> = 0mega((min{<i>n</i> , <i>l</i>(<i>k</i> - log<i>l</i>)}). When <i>l</i> >= 2^<i>k</i>, <i>A</i> = Omega(2^<i>k</i> (log<i>l</i> - <i>k</i> + 1)).} }
EndNote citation:
%0 Report %A Duris, Pavol %A Sykora, Ondrej %A Thompson, Clark D. %A Vrto, Imrich %T A Minimum-Area Circuit for l-Selection %I EECS Department, University of California, Berkeley %D 1985 %@ UCB/CSD-85-244 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1985/5513.html %F Duris:CSD-85-244