Systolic sorting in a sequential input/output environment (Q1068554)

A new parallel sorting architecture called the 2-way sorter is presented which is especially well-suited for use in an environment with sequential input and output. A 2-way sorter having an area of \(n(k+1)a/2\) can sort m sequences of n k-bit numbers in time \(((\lceil m/2\rceil +1)n+k)t\), where a and t are the area and the time of its bit-level building block, the 2- way cell. Using the same hardware mn k-bit numbers can be sorted in time O(mn log\({}^ 2m)\) without needing more memory than for storing the mn numbers. The 2-way sorter qualifies to be a perfect systolic architecture: It is built from simple cells having a constant number of inputs and outputs and constant area and time. Except for a one-bit control information all communication is local. All its cells are active at the same time. In a sequential input/output environment the 2-way sorter has optimal area, period and time.