SORTCHIP: A VLSI implementation of a hardware algorithm for continuous data sorting

Abstract

We present a VLSI implementation of a hardware sorting algorithm for continuous data sorting. The device is able to continuously process an input data stream while producing a sorted output data stream. At each clock cycle, the device reads and processes a 48-bit word, 24 bits for the datum and 24 bits for the associated tag. The data stream is sorted according to the tags preserving the order of words with identical tags. Sequences up to 256 words are completely sorted and longer sequences are partially sorted. The maximum operation frequency is 50 Mwords/s. The architecture is based on a chain of identical elementary sorting units. A full custom design exploits the highly regular architecture to achieve high area and time performance. We describe the algorithm and give architectural details.