EECS technical reports

Oskicat catalog record
Conditions of Use

Archive Home Page

RESST: A VLSI Implementation of a Record-Sorting Stack

Carey, Michael J.
Hansen, Paul M.
Thompson, Clark D.
Technical Report Identifier: CSD-82-102
April 21, 1982

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.

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.