Hardware sorter and its application to data base machine

Abstract

The main contribution of this paper is the design of a hardware sorter. This sorter is configured as a balanced, fixed binary tree of node units; the configuration of the sorter is independent of the length of data to be sorted. Each node unit can be realized on a single LSI chip. The logic of the hardware sorter design is heavily influenced by a specific, compressed, representation of sorted data. Using this hardware sorter and a few auxiliary functions based on the sorted property, we demonstrate the design of a relational data base machine.