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

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-82-102
April 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.

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},
    Institution = {EECS Department, University of California, Berkeley},
    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