Clark D. Thompson and Michael J. Carey and Paul M. Hansen

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-82-102

, 1982

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/CSD-82-102.pdf

This report discusses a VLSI implementation of a record-sorting stack. Records are represented on the stack as (key, record-pointer) pairs, and the operations supported are PUSH, POP, and CLEAR. When records are POPed, they are returned in smallest-first order. The implementation allows the sorting of n records in O(n) time, and the design is cascadable so that the capacity of a single VLSI chip does not limit the amount of data which may be sorted. <p> This report describes a paper design and evaluation, and thus serves two purposes: It describes one particular VLSI sorting circuit, and it also serves as a case study in VLSI design methodology. The algorithm is described, the overall chip organization and data flow are presented, and detailed circuits, layouts, and timing analyses are given.

---

BibTeX citation:

@techreport{Thompson:CSD-82-102,
    Author= {Thompson, Clark D. and Carey, Michael J. and Hansen, Paul M.},
    Title= {RESST: A VLSI Implementation of a Record-Sorting Stack},
    Year= {1982},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6202.html},
    Number= {UCB/CSD-82-102},
    Abstract= {This report discusses a VLSI implementation of a record-sorting stack. Records are represented on the stack as (key, record-pointer) pairs, and the operations supported are PUSH, POP, and CLEAR. When records are POPed, they are returned in smallest-first order. The implementation allows the sorting of n records in O(n) time, and the design is cascadable so that the capacity of a single VLSI chip does not limit the amount of data which may be sorted.  <p>  This report describes a paper design and evaluation, and thus serves two purposes:  It describes one particular VLSI sorting circuit, and it also serves as a case study in VLSI design methodology. The algorithm is described, the overall chip organization and data flow are presented, and detailed circuits, layouts, and timing analyses are given.},
}

EndNote citation:

%0 Report
%A Thompson, Clark D. 
%A Carey, Michael J. 
%A Hansen, Paul M. 
%T RESST: A VLSI Implementation of a Record-Sorting Stack
%I EECS Department, University of California, Berkeley
%D 1982
%@ UCB/CSD-82-102
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6202.html
%F Thompson:CSD-82-102