Systolic merge sorter
First Claim
1. A sorter system comprising:
- a clock continuously generating a series of clock signals;
a systolic array circuit including at least one processing module and K−
1 registers, where K is an integer value greater than two, each processing module having at least one of the registers, each register for storing one data item; and
control circuitry in communication with serial access memory storing data items of a sequence to be sorted and in communication with the systolic array circuit to supply thereto data items as input and to receive therefrom data items as output, the control circuitry serially presenting K data items for input to the systolic array circuit in synchronization with the clock signals,wherein, on the next clock cycle after the control circuitry presents to the systolic array circuit the last of the K data items, the data item of least value of the K data items is outputted.
1 Assignment
0 Petitions
Accused Products
Abstract
A sorter system includes a clock continuously generating a series of clock signals, a systolic array circuit, and control circuitry in communication with serial access memory that stores data items of a sequence to be sorted and with the systolic array circuit to supply thereto data items as input and to receive therefrom data items as output. The systolic array circuit includes at least one processing module and K−1 registers, where K is an integer value greater than two. Each processing module has at least one of the registers, each register for storing one data item. The control circuitry serially presents K data items for input to the systolic array circuit in synchronization with the clock signals. On the next clock cycle after the control circuitry presents to the systolic array circuit the last of the K data items, the data item of least value in the given subsequence is output.
-
Citations
36 Claims
-
1. A sorter system comprising:
-
a clock continuously generating a series of clock signals; a systolic array circuit including at least one processing module and K−
1 registers, where K is an integer value greater than two, each processing module having at least one of the registers, each register for storing one data item; andcontrol circuitry in communication with serial access memory storing data items of a sequence to be sorted and in communication with the systolic array circuit to supply thereto data items as input and to receive therefrom data items as output, the control circuitry serially presenting K data items for input to the systolic array circuit in synchronization with the clock signals, wherein, on the next clock cycle after the control circuitry presents to the systolic array circuit the last of the K data items, the data item of least value of the K data items is outputted. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A computer-executed method of merge sorting a sequence having a large number of data items, the method comprising:
-
continuously generating a series of clock signals; serially presenting K data items for input to a systolic array circuit in synchronization with the clock signals, the systolic array circuit including at least one processing module circuit and K−
1 registers, where K is an integer value greater than two;conditionally exchanging data items between registers of the systolic array circuit during each clock cycle in which the K data items are serially presented to the systolic array circuit; and outputting the data item of least value of the K data items on the next clock cycle after the last of the K data items is presented to the systolic array circuit. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. Systolic array circuitry, comprising:
-
K−
1 registers, where K is an integer value greater than two, each register for storing one data item; anda plurality of identical processing module circuits connected in a pipeline, each processing module circuit being electrically connected to at least one neighboring processing module circuit for exchanging data items therewith, each processing module circuit having at least one of the K−
1 registers, a first one of the processing module circuits being first in position in the pipeline and is serially presented K input data items in synchronization with a series of clock signals,wherein, on the next clock cycle after the first processing module circuit in the pipeline is presented the last of K data items, a register of the first processing module circuit holds a data item of least value of the data items held by the K−
1 registers in the systolic array circuitry. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35)
-
-
36. A merge sorter circuit, comprising:
-
K−
1 registers, where K is an integer value greater than two, each register for storing one data item; anda plurality of identical processing module circuits connected in a bidirectional pipeline, each processing module circuit being electrically connected to at least one neighboring processing module circuit for exchanging data items therewith, each processing module circuit having at least one of the K−
1 registers, a first one of the processing module circuits being first in position in the pipeline and is serially presented K input data items in synchronization with a series of clock signals,wherein, on each clock signal, the processing module circuits conditionally execute an exchange of data items such that data items of greater values move towards one end of the pipeline while data items of lesser values move towards an opposite end of the pipeline.
-
Specification