Systolic Merge Sorter

• US 20100235674A1
• Filed: 03/13/2009
• Published: 09/16/2010
• Est. Priority Date: 03/13/2009
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Song, William S.
• Granted Patent: US 8,190,943 B2
• Time in Patent Office: Days
• US Class Current: 713/600
• CPC Class Codes: G06F 7/32 Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence merging methods in generalG06F7/36 takes precedence

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.

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; 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.

2. The sorter system of claim 1, wherein the sequence is divided into a plurality of unsorted subsequences each having K data items and wherein the K data items presented to the systolic array circuit belong to one of these unsorted subsequences.

3. The sorter system of claim 2, wherein each of the K data items presented to the systolic array circuit is flagged when the last of the K data items is presented, each flag signifying that the flagged data item belongs to a different unsorted subsequence from that of each input data item subsequently presented to the systolic array circuit.

4. The sorter system of claim 2, wherein each data item is associated with a binary flag before that data item is presented, the flags of the K data items of a given unsorted subsequence having the same binary value, the unsorted subsequences being sorted in serial order, the binary value of the flags of the K data items of the unsorted subsequences alternating every other unsorted subsequence in the serial order.

5. The sorter system of claim 1, wherein each of the K data items presented to the systolic array circuit is first in order within a sorted subsequence of the sequence, each of the sorted subsequences belonging to a group of K subsequences being merge-sorted.

6. The sorter system of claim 5, wherein the control circuitry selects a next data item for input to the systolic array circuit based on the particular sorted subsequence to which the outputted data item belongs.

7. The sorter system of claim 1, wherein the systolic array circuit includes K−

1 processing modules arranged in a pipeline, each processing module circuit having one of the K−

1 registers for holding one data item, a first one of the K−

1 processing module circuits being positioned first in the pipeline and in communication with the control circuitry, and a second of the K−

1 processing module circuits being positioned second in the pipeline.

8. The sorter system of claim 7, wherein, during alternating clock cycles, the first one of the K−

1 processing module circuits conditionally swaps data items with the control circuitry in one clock cycle and conditionally swaps data items with the second of the K−

1 processing module circuits in the next clock cycle.

9. The sorter system of claim 1, wherein the systolic array circuit receives an input data item and produces a sorted output data item in alternating clock cycles.

10. The sorter system of claim 1, wherein the systolic array circuit receives an input data item and produces a sorted output data item in a single clock cycle.

11. The sorter system of claim 1, wherein the systolic array circuit includes two or more processing modules arranged in a pipeline, each processing module having two of the K−

1 registers for holding two data items, one of the two registers holding the data item of lesser value of the two data items and the other of the two registers holding the data item of greater value of the two data items.

12. The sorter system of claim 11, wherein, during each clock cycle, one of the processing modules receives a data item from and presents a data item to each neighbor, and compares the data items in its two registers with each received data item to determine a ranking among the data items and whether to swap data items with each neighbor.

13. The sorter system of claim 11, wherein the systolic array circuit is an input systolic array circuit and further comprising an output systolic array circuit in communication with the input systolic array circuit, wherein, on the next clock cycle after the control circuitry presents to the input systolic array circuit the last of the K data items, the data items in the input systolic array circuit simultaneously transfer to the output systolic array circuit.

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.

15. The computer-executed method of claim 14, further comprising dividing the sequence into a plurality of unsorted subsequences each having K data items, and wherein the K data items presented to the systolic array circuit belong to one of these unsorted subsequences.

16. The computer-executed method of claim 15, further comprising flagging each of the K data items presented to the systolic array circuit when the last of the K data items is presented, each flag signifying that the flagged data item belongs to a different unsorted subsequence from that of each input data item subsequently presented to the systolic array circuit.

17. The computer-executed method of claim 15, further comprising:

associating a binary flag with each data item before that data item is presented, the flags of the K data items of a given unsorted subsequence having the same binary value;

sorting the unsorted subsequences in serial order; and

alternating the value of the binary flag upon every other unsorted subsequence in the serial order.

18. The computer-executed method of claim 14, wherein each of the K data items presented to the systolic array circuit is first in order within a sorted subsequence of the sequence, each of the sorted subsequences belonging to a group of K subsequences being merge-sorted.

19. The computer-executed method of claim 18, further comprising selecting a next data item for input to the systolic array circuit based on the particular sorted subsequence to which the outputted data item belongs.

20. The computer-executed method of claim 14, wherein the systolic array circuit includes K−

1 processing modules arranged in a pipeline, each processing module having one of the K−

1 registers for holding one data item, a first one of the K−

1 processing modules being positioned first in the pipeline, and a second of the K−

1 processing modules being positioned second in the pipeline.

21. The computer-executed method of claim 20, further comprising conditionally swapping, during alternating clock cycles, data items between the first one of the K−

1 processing module circuits and control circuitry in one clock cycle and data items between the first and second of the K−

1 processing module circuits in the next clock cycle.

22. The computer-executed method of claim 14, further comprising receiving an input data item and producing an output data item by the systolic array circuit in alternating clock cycles.

23. The computer-executed method of claim 14, further comprising receiving an input data item and producing an output data item by the systolic array circuit in a single clock cycle.

24. The computer-executed method of claim 14, wherein the systolic array circuit includes two or more processing module circuits arranged in a pipeline, each processing module circuit having two of the K−

1 registers for holding two data items, one of the two registers holding the data item of lesser value of the two data items and the other of the two registers holding the data item of greater value of the two data items.

25. The computer-executed method of claim 24, further comprising receiving, by each processing module circuit, a data item from each neighboring processor module circuit during each clock cycle, and comparing, by that processing module circuit, the data items in its two registers with each received data item to determine a ranking among the data items and whether to swap data items with each neighbor processor module circuit.

26. The computer-executed method of claim 14, wherein the systolic array circuit is an input systolic array circuit and further comprising an output systolic array circuit in communication with the input systolic array circuit, and further comprising simultaneously transferring the data items in the input systolic array circuit to the output systolic array circuit on the next clock cycle after the last of the K data items is presented to the input systolic array circuit.

27. Systolic array circuitry, comprising:

K−

1 registers, where K is an integer value greater than two, each register for storing one data item; and

a 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.

28. The systolic array circuitry of claim 27, wherein each of the K data items presented to the systolic array circuit is first in order within a sorted subsequence of the sequence, each of the sorted subsequences belonging to a group of K subsequences being merge-sorted.

29. The systolic array circuitry of claim 27, wherein the sequence is divided into a plurality of unsorted subsequences each having K data items and wherein the K data items presented to the systolic array circuit belong to one of these unsorted subsequences.

30. The systolic array circuitry of claim 27, wherein the systolic array circuit includes K−

1 processing module circuits arranged in a pipeline, each processing module circuit having one of the K−

1 registers for holding one data item.

31. The systolic array circuitry of claim 30, wherein, during alternating clock cycles, one of the K−

1 processing module circuits conditionally swaps data items with a first neighboring processing module circuit and conditionally swaps data items with a second neighboring processing module circuit in the next clock cycle.

32. The systolic array circuitry of claim 27, wherein the systolic array circuitry receives an input data item and produces a sorted output data item in alternating clock cycles.

33. The systolic array circuitry of claim 27, wherein the systolic array circuitry receives an input data item and produces a sorted output data item in a single clock cycle.

34. The systolic array circuitry of claim 27, wherein the systolic array circuit includes two or more processing module circuits arranged in a pipeline, each processing module circuit having two of the K−

1 registers for holding two data items, one of the two registers holding the data item of lesser value of the two data items and the other of the two registers holding the data item of greater value of the two data items.

35. The systolic array circuitry of claim 34, wherein, during each clock cycle, one of the processing module circuits receives a data item from each neighboring processing module circuit, and compares the data items in its two registers with each received data item to determine a ranking among the data items and whether to swap a data item.