Bi-way sorter: a two-dimensional systolic array

A VLSI implementation of a new two-dimensional systolic array for sorting in a sequential input/output environment is described. The new ´bi-way´ sorter allows double the key length in the same chip area than the previously proposed two-way sorter. A 10 bit, 20 number prototype bi-way sorting chip in 3 mu m CMOS has been tested at 9 MHz. Fast new techniques are described for sorting keys or sequences which exceed in length the capacity of the sorting hardware. A rapid testing procedure is outlined. The two-dimensional systolic sorter described offers an attractive alternative to nonsystolic sorters, especially at future levels of integration.