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