A VSI Pipeline Sorting Algorithm Design and Implementation

Hardware based sorting techniques date back to the late 1800s when Herman Hollerith, an employee of the census Bureau developed the first tabulating and sorting machine. [Knuth] The machine was developed to meet the needs census statistics gathering. At that time up to 49 cards a minute could be sorted, as it was based on the performance of the human operator. Since, that time faster general purpose computers have been developed. Now most sorting is done on these computers under software control. But, sorting still remains to be a problem in that it can take up to 1/4th of a computer\u27s processing time. Computers have become more specialized to handle such high performance task as real-time simulation and artificial intelligence. To achieve higher performance dedicated hardware is being design to meet the challenge. Algorithms once reserved for software are now being migrated to hardware. Sorting is no exception. In this research, a new pipeline sorting algorithm, called the Pipeline Orderer Algorithm, is presented. This algorithm is well suited for VLSI implementation. A gate array chip using this algorithm has been implemented and is currently being employed in a high performance image generation system