Comparison-based sort in an array processor

Patent metadata

Field	Value
Publication number	US-2016124755-A1
Application number	US-201414530027-A
Country	US
Kind code	A1
Filing date	Oct 31, 2014
Priority date	Oct 31, 2014
Publication date	May 5, 2016
Grant date	—

Abstract

An array processor includes a managing element having a load streaming unit coupled to multiple processing elements. The load streaming unit provides input data portions to each of a first subset of processing elements and receives output data from each of a second subset of the processing elements based on a comparatively sorted combination of the input data portions. Each processing element is configurable by the managing element to compare input data portions received from the load streaming unit or two or more of the other processing elements. Each processing unit can further select an input data portion to be output data based on the comparison, and in response to selecting the input data portion, remove a queue entry corresponding to the selected input data portion. Each processing element can provide the selected output data portion to the managing element or as an input to one of the processing elements.

First claim

1 . An array processor comprising:
a managing element having a load streaming unit coupled to a plurality of processing elements, the load streaming unit,
providing input data portions to each of a first subset of the plurality of processing elements; and
receiving output data from each of a second subset of the plurality of processing elements based, at least in part, on a comparatively sorted combination of the input data portions provided to the first subset of the processing elements;
wherein each of the plurality of processing elements is configurable by the managing element to,
compare the input data portions received from either the load streaming unit or two or more of the other processing elements, wherein the input data portions are stored for processing in respective input queues;
select an input data portion to be the output data from the processing element based on the comparison;
in response to selecting the input data portion, remove a queue entry corresponding to the selected input data portion; and
provide the output data to either the managing element or as an input to one of the plurality of processing elements.

2 . The array processor of claim 1 , wherein for at least one of the second subset of the processing elements, the managing element provides a control signal to the processing element in response to receiving the output data generated by the processing element, wherein the control signal directs the processing element to provide next output data.

3 . The array processor of claim 1 , wherein for at least one of the first subset of the processing elements, the managing element receives a control signal from the processing element including a request for a next input data portion.

4 . The array processor of claim 3 , wherein the control signal indicates an input data stream from which to provide the next input data portion.

5 . The array processor of claim 1 , wherein the managing element:
determines whether an end-of-stream indicator associated with an input data stream is detected, wherein the input data stream comprises a next input data portion; provides the end-of-stream indicator to the processing element in response to determining that the end-of-stream indicator is detected; and provides the next input data portion of the input data stream in response to determining that the end-of-stream indicator was not detected.

6 . The array processor of claim 1 , wherein the managing element:
determines that an end-of-stream indicator associated with each of a plurality of input data streams are detected, wherein the managing element and the plurality of processing elements are configured to merge and sort the plurality of input data streams; and generates a notification indicating that the plurality of input data streams are merged and sorted.

7 . The array processor of claim 1 , wherein each of the plurality of processing elements comprises logic units programmed to:
in response to selecting a comparison result from one of the input queues, remove the selected input data portion from a head position of the input queue where the selected input data portion is stored; route the selected input data portion to an output of the processing element; and request a next input data portion from the managing element or from one of the plurality of processing elements to store in the input queue from which the selected input data portion was removed.

8 . The array processor of claim 7 , wherein each of the plurality of processing elements further comprises logic units programmed to:
during said compare of the input data portions, determine whether the head position of either of the input queues includes an end-of-stream indicator; in response to determining that the head position of one but not the other input queue includes an end-of-stream indicator, select and remove the input data portion from the head position of the other input queue, until an end-of-stream indicator is detected in the head position of both input queues; and in response to determining that the head position of both input queues include an end-of-stream indicator, remove both end-of-stream indicators and sending one end-of-stream indicator from the processing element to either a store streaming unit in the managing element or to an input of one of the plurality of processing elements.

9 . The array processor of claim 1 , wherein at least one of the second subset of the processing elements:
receives a first control signal from the managing element in response to providing the output data generated by the processing element to the managing element; and transmits a second signal to a processing element of a third subset of the plurality of processing elements to request output data generated by the processing element of the third subset of the processing elements.

10 . The array processor of claim 1 , wherein at least one of the first subset of the processing elements:
receives a first control signal from a processing element of a third subset of the plurality of processing elements requesting next output data generated by the processing element of the first subset of the processing elements; and provides a second control signal to the managing element to request a next input data portion.

11 . The array processor of claim 1 , wherein each of the plurality of processing elements:
compares a first input data portion with a second input data portion received at the processing element; and selects the first input data portion or the second input data portion as the output data associated with the processing element.

12 . The array processor of claim 1 , wherein the plurality of processing elements are configured to select one of the input data portions based, at least in part, on a sorting truth table associated for performing a merge sort algorithm.

13 . The array processor of claim 1 , wherein at least one of the first subset of the processing elements:
receives a first portion of a first input data stream and a second portion of a second input data stream from the managing element; and selects the first portion or the second portion as the output data associated with the processing element.

14 . The array processor of claim 13 , wherein at least one of the first subset of the processing elements stores the first portion of the first input data stream in a first input queue of the processing element and the second portion of the second input data stream in a second input queue of the processing element.

15 . The array processor of claim 1 , wherein at least one of the first subset of the processing elements:
receives a first portion of a first input data stream and a second portion of the first input data stream from the managing element; and selects the first portion or the second portion of the first input data stream as the output data associated with the processing element.

16 . The array processor of claim 1 , wherein at least one of the second subset of the processing elements:
receives, as an input at the processing element, first output data from a first processing element of a remainder subset of the plurality of processing elements, and second output data from a second processing element of the remainder subset of the processing elements, wherein the remainder subset of the processing elements does not include the second subset of the processing elements; and selects between the first output data and the second output data as the output data associated with the processing element of the second subset of the processing elements.

Assignees

• IBM

Inventors

• Balakrishnan Ganesh
• Blaner Bartholomew
• Reilly John J
• Stuecheli Jeffrey A

Classifications

• G06F9/30021 Primary

  Compare instructions, e.g. Greater-Than, Equal-To, MINMAX · CPC title

• G06F9/4436 Primary

  Physics · mapped topic

• G06F15/8015

  One dimensional arrays, e.g. rings, linear arrays, buses · CPC title

• G06F15/82

  data or demand driven · CPC title

• G06F15/7885

  Runtime interface, e.g. data exchange, runtime control · CPC title