Multiple record group rebound sorter

• US 5,185,886 A
• Filed: 09/25/1991
• Issued: 02/09/1993
• Est. Priority Date: 06/30/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.), National Semiconductor Corporation (Texas Instruments, Inc.)
• Inventors: Helliwell, Richard P., Edem, Brian C.
• Primary Examiner(s): Clark, David L.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US07/765,464
• Time in Patent Office: 503 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/DIG. 1, 364/DIG. 2, 395/600, 395/800
• US Class Current: 707/611
• CPC Class Codes: G06F 7/36 Combined merging and sorting
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A control system and method for use with a sort accelerator having a rebound sorter as a merger in disclosed. The control system allows records to be efficiently and effectively transferred between processing elements and record storage elements of a rebound sorter. The control system allows consecutive groups of records to be sorted in the rebound sorter without mixing records from separate groups. The control system also pipelines records through the sorter by allowing different groups of records to input into the rebound sorter directly adjacent to each other.

Claims

1. A method for controlling a sorter in a pipeline control system, said pipeline control system having a sorter for receiving as input records from a plurality of groups of records, each of the plurality of groups of records having N records and for outputting a first group of the plurality of groups of records in sorted order during the inputting of an immediately following group of another one of the plurality of groups of N records and then outputting the immediately following group of N records in sorted order immediately following the first one of the groups of records now in sorted order without mixing records from each of the plurality of groups of records, and a pipeline control means, said sorter having a single input means for receiving records and a single output means for outputting records in sorter order, said sorting means further including a plurality of processing element means for comparing record data, each of said processing element means having input means for receiving record data, said input means having an upper left input and a lower right input and output means for outputting record data, said output means having an upper right output and a lower left output, and processing element control means for controlling said processing element means to operate in a first mode to effect transfers of record data from said upper left input to said lower left output and from said lower right input to said upper right output and to operate in a second mode to transfer record data from said upper left input to said upper right output and from said lower right input to said lower left output, said upper left input of the first one of said processing element means being coupled to said single input means, said upper left input of each of the remaining ones of said processing element means being coupled to said lower left output of a preceding processing element means, said lower left output of the last one of said processing element means being connected to said lower right input thereof, said upper right output of said first processing element means being coupled to said single output means, and said upper right output of each of said remaining processing element means being connected to said lower right input of preceding processing element means, operation of all of said processing element means in said first mode, causes record data to be transferred serially through said processing element means to said last processing element means and to be then transferred serially back through said processing element means to said single output means, the method comprising the steps of:

inputting to said single input means of said sorter, the first record of another group of N records directly after the Nth record of said one group during the output of said remaining N-1 records of said one group;

generating a first signal to indicate that said another group of N records is being input to said sorter;

inputting said first signal to said pipeline control means;

generating a first force vertical signal in response to said first signal;

sending said first force vertical signal to the first one of said processing element means to cause said first processing element means to force the first record of said another group of the next one of said processing element means;

inputting the remaining N-1 records of said another group to said sorter immediately after the first record of said another group and during the output of the remaining records of said one group;

sequentially generating additional force vertical signals, sending one of said additional force vertical signals to each of said processing element means synchronously with the receipt of said first record of said another group, said additional force vertical signals causing said processing element means to force the records of said another group to the next one of said processing element means and preventing the interchange of records of said another group with the records of said one group;

maintaining each of said force vertical signals until said first record of said another group is transferred from said last processing element means and then sequentially removing said force vertical signals from each of said processing element means in reverse order; and

outputting records of said another group to form a succeeding string of records in sorted order immediately following the first sorted string of records.

2. The method of controlling a sorter as claimed in claim 1, including the step of:

generating a third signal during the outputting of the first record of said succeeding string of records arranged in sorter order to indicate a new sorted group of records is emerging from said sorter.

3. The method of controlling a sorter as claimed in claim 2, including the step of:

generating a boundary signal to accompany the records as the records move from one processing element to the next processing element. PG,82

4. A pipeline control system for receiving as input records from a plurality of groups of records, each of the plurality of groups of records having N records and for outputting a first group of the plurality of groups of records in sorted order during the inputting of an immediately following group of another one of the plurality of groups of N records and then outputting the immediately following group of N records in sorted order immediately following the first one of the groups of records now in sorted order without mixing records from each of the plurality of groups of records, said pipeline control system comprising:

sorting means for arranging in sorted order the records of one of the plurality of groups of records, said sorting means having a single input means for receiving records and a single output means for outputting records in sorted order, said sorting means further including a plurality of processing element means for comparing record data, each of said processing element means having input means for receiving record data, said input means having an upper left input and a lower right input and output means for outputting record data, said output means having an upper right output and a lower left output, and processing element control means for controlling said processing element means to operate in a first mode to effect transfers of record data from said upper left input to said lower left output and from said lower right input to said upper right output and to operate in a second mode to transfer record data from said upper left input to said upper right output and from said lower right input to said lower left output said upper left input of the first one of said processing element means being coupled to said single input means, said upper left input of each of the remaining ones of said processing element means being coupled to said lower left output of a preceding processing element means, said lower left output of the last one of said processing element means being connected to said lower right input thereof, said upper right output of said first processing element means being coupled to said single output means, and said upper right output of each of said remaining processing element means being connected to said lower right input of preceding processing element means, operation of all of said processing element means in said first mode, causes record data to be transferred serially through said processing element means to said last processing element means and to be then transferred serially back through said processing element means to said single output means;

storage means for storing the record data compared by said processing element means, said storage means coupled to said lower left output and said lower right input of each of said plurality or processing element means; and

pipeline control means coupled to each of said processing element means for controlling the movement of the record data from said first processing element means to said last processing element means and for preventing mixing records from each of the plurality of groups of N records.

5. The pipeline control system as defined in claim 4, wherein said pipeline control means comprises force vertical means for generating a force vertical signal, said force vertical signal being applied to said first processing element means at the same time as the input of a first record of said another group of records is being applied to said first processing element and which is applied to each of said processing element means in tandem with serial transfers of record data from said first processing element means toward said last processing element means to cause said processing element means to operate in said first mode of operation until said first record of said another group of records is transferred by said last processing element means.

6. The pipeline control system as defined in claim 5, wherein said force vertical means includes a plurality of force vertical elements, each of said force vertical elements individually connected to one of said processing element means for applying said force vertical signal to one of said processing element means to prevent records of said one group of N records from being mixed with records of said another group of N records.

7. The pipeline control system as defined in claim 6, wherein said force vertical elements include input means for receiving input signals and output means for sending said force vertical signal to said processing element means and for sending status signals to adjacent ones of said force vertical elements.

8. The pipeline control system as defined in claim 7 wherein said pipeline control means includes a plurality of boundary marker element means, each of said boundary marker element means associated with one of said processing element means for maintaining a boundary value which moves in parallel with the records as the records move from one of said processing element means to another of said processing element means.

9. The pipeline control system as defined in claim 4, further comprising:

means for generating an input signal indicating that the record input to said first processing element means is a first record of said another group of records;

force vertical means for receiving said input signal and for sequentially generating a plurality of force vertical signals;

each of said force vertical signals being applied to one of said processing element means in synchronous with said processing element means receiving said first record of said another group of records;

each of said force vertical signals causing said processing element means to operate in said first mode of operation; and

a latch means for maintaining each of said force vertical signals until said first record of said another group of records is transferred from said last processing element means and then sequentially removing said force vertical signals from each of said processing element means in reverse order.