A Minimum-Area Circuit for l-Selection

Pavol Duris and Ondrej Sykora and Clark D. Thompson and Imrich Vrto

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-85-244

, 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 - logl)}). When l >= 2^k, A = Omega(2^k (logl - 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},
    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