Firmware sort processor system

Claim 2

In a data processing system, the combination comprising: a. a main memory for storing raw data to be processed; b. a sort processor cooperating with said main memory, said sort processor including a search memory for holding data to be processed and for performing the sorting functions, a register file holding data representing parameters selected for the data processing operation, and a micro-program storage unit for storing replaceable control routines for the sort processor and for its data exchange with external units; c. a central processor unit connected for cooperative communication and control of said main memory and said sort processor; wherein said sort processor functions completely independent of the central processor unit except for the use of a start signal and wherein all sort algorithms are stored in the sort processor thus rendering it independent of the central processor unit.

Claim 3

The data processing system as in claim 1 wherein said micro-program storage unit includes: a memory control section for control routines for handling data in said main memory, a search control section for controlling search operations in said search memory, and a main control store which contains all the required sort-merge algorithms and all of the overall sort processing system control micro-routines

Claim 4

The data processing system as in claim 1 wherein said search memory provides storage for selected key word data taken from data records in said main memory, and provides storage for address-data which references each key word data to the address location of data records held in said main memory.

Claim 5

The data processing system as in claim 1 wherein said sort processor includes at least two comparators and two registers working in cooperation with said search memory for comparing: a set of at least two key words from said search memOry, or the key word currently fetched from said main memory with a base key word, said comparing being capable of occurrence during the time that said sort processor is performing a sequential search through said memory, in order to select a base reference key word for compiling an address list in an output buffer of said main memory.

Claim 6

The data processing system as in claim 4 wherein said main memory includes: an input buffer work area for storage of data records to be processed, each of said data records having a main memory address associated therewith; an output buffer string list area for sequential storing of starting addresses of records processed by the sort processor; and an initial parameters table area for establishing parametrical data for controlling the scope of the data processing operations, the said initial parameters table, specified by the starting address, Ao, being used by the sort processor which sequentially reads the entire initial parameters table.

Claim 7

The data processing system as in claim 4 wherein said central processor unit initiates operations of the sort processor by use of a control word, said control word comprising: a function code for selecting the data processing function to be performed by the sort processor, and a main memory address referencing the starting location Ao in the said initial parameters table area.

Claim 8

The system as defined in claim 1 including an external data storage unit wherein said sort processor and central processor unit share the main memory and wherein the sort processor is given a lower priority of access to the main memory than the central processor unit.

Claim 9

The system as in claim 7 wherein the said sort processor and the said central processor unit share the said external storage unit, and wherein the sort processor controls the data transfer between the external storage unit and the main memory only during a sort-merge operation.

Claim 10

The system as in claim 1 wherein the main memory is constituted of two physically separate main memory sections and wherein the central processor unit has exclusive access to both sections of the main memory while the sort processor has an exclusive access to only one section of the main memory.

Claim 11

The system as in claim 9 wherein said sort processor and said central processor unit share a common external storage unit.

Claim 12

The combination as defined in claim 1 wherein said micro-program storage unit comprises a control store in the sort processor which is dynamically alterable and capable of being reloaded from the main memory or any other source of micro-programs thus permitting the implementation of sort-merge algorithms.

Claim 13

The data processing system of claim 1 in which the micro-program storage unit comprises a control store partitioned into three separate sections on a functional algorithmic basis so that the sort-merge algorithm is stored in a first control store, the search memory control algorithm is stored in a second control store, and the main memory control algorithm is stored in a third control store, such sectional structure providing for: the minimization of total control store capacity requirements, suitability of implementation with LSI components, more efficient debugging and maintainability capability.

Claim 14

A sort processor interconnected for cooperation with a central processor unit and a main memory, said sort processor comprising: a search memory, a register file, a micro-program storage unit, and at least two registers and two comparators cooperating with said search memory for sorting and merging new data records according to parameters stored in said register file, and to a sort-merge algorithm stored in said micro-program storage unit of the said sort processor as firmware.

Claim 15

A sort processor interconnected for cooperation with a central processor unit and a main memory, said sort processor comprising: a search memory, a register file, a micro-program storage unit, and at least two registers and two comparators cooperating with said search memory for sorting and merging new data records according to parameters stored in said register file, and to a sort-merge algorithm stored in said micro-program storage unit of the said sort processor as firmware.

Claim 16

In a data processing system including a main memory, a central processor unit and a sort processor, the method of processing data comprising the steps of: a-1. allocating portions of main memory for an input buffer, for an outPut buffer, and for an initial parameters table; a-2. storing raw data records into the input buffer, and storing parameter data into said initial parameters table; a-3. establishing (a-3.1) an address Ao for the first location of the parameter data in said initial parameters table; establishing (a-3.2) addresses Bo and Bn for the first and last data records in said input buffers; (a-3.3) establishing an address Go for a selected key word of the first record of said data records in said input buffer; and (a-3.4) establishing addresses Po and Pn for the first and last addresses in said output buffer; a-4. initiating the sort processor, by using a start signal generated by the central processing unit to inform the sort processor that a function code control word is now available on the main memory bus; a-5. transferring data from said initial parameters table in said main memory to a register file in said sort processor; a-6. transferring key words Ki starting with the first record in the input buffer area from a location designated Gi into a search memory in said sort processor; a-7. establishing a key word reference base Ko according to an instruction from the control word and the initial parameters table; a-8. computing the address Bi of the next key word corresponding to each key word Ki, and storing the computed Bi and Ki in the sequential locations of the search memory as one word; a-9. searching for the highest or lowest key word from the contents of said search memory; a-10. writing the corresponding address Bo of the base Ko into the first address Po location of the said output buffer; a-11. operating upon said base Ko according to an incrementing or decrementing function as required to establish sequential bases Kn; a-12. comparing each key word in said search memory sequentially with each subsequent base Kn to identify a selected relationship which when found causes transfer of the address Bn of said identified key word Kn into the Pn location of said output buffer; a-13. replacing the removed key word data in said search memory with new unprocessed key word data from said input buffer; a-14. processing said data until any one of the following conditions are met: (a-14.1) all the available key word data in the input buffer are processed, (a-14.2) the output buffer area is completely filled, (a-14.3) searches for the current string are exhausted; a-15. interrupting the central processor unit and making the sort processor wait for a new control word.

Claim 17

In a data processing system including a main memory, a central processor unit and a sort processor, the method of processing data comprising the steps of: a-1. allocating portions of main memory for an input buffer, for an outPut buffer, and for an initial parameters table; a-2. storing raw data records into the input buffer, and storing parameter data into said initial parameters table; a-3. establishing (a-3.1) an address Ao for the first location of the parameter data in said initial parameters table; establishing (a-3.2) addresses Bo and Bn for the first and last data records in said input buffers; (a-3.3) establishing an address Go for a selected key word of the first record of said data records in said input buffer; and (a-3.4) establishing addresses Po and Pn for the first and last addresses in said output buffer; a-4. initiating the sort processor, by using a start signal generated by the central processing unit to inform the sort processor that a function code control word is now available on the main memory bus; a-5. transferring data from said initial parameters table in said main memory to a register file in said sort processor; a-6. transferring key words Ki starting with the first record in the input buffer area from a location designated Gi into a search memory in said sort processor; a-7. establishing a key word reference base Ko according to an instruction from the control word and the initial parameters table; a-8. computing the address Bi of the next key word corresponding to each key word Ki, and storing the computed Bi and Ki in the sequential locations of the search memory as one word; a-9. searching for the highest or lowest key word from the contents of said search memory; a-10. writing the corresponding address Bo of the base Ko into the first address Po location of the said output buffer; a-11. operating upon said base Ko according to an incrementing or decrementing function as required to establish sequential bases Kn; a-12. comparing each key word in said search memory sequentially with each subsequent base Kn to identify a selected relationship which when found causes transfer of the address Bn of said identified key word Kn into the Pn location of said output buffer; a-13. replacing the removed key word data in said search memory with new unprocessed key word data from said input buffer; a-14. processing said data until any one of the following conditions are met: (a-14.1) all the available key word data in the input buffer are processed, (a-14.2) the output buffer area is completely filled, (a-14.3) searches for the current string are exhausted; a-15. interrupting the central processor unit and making the sort processor wait for a new control word.

Claim 18

The process of claim 14 including the steps of: (a-16) transferring the records from the input buffer area to an external storage area by the sequentially arranged list of addresses (Bn) of the output buffer area and further loading new raw records to be sorted into the input buffer area; and (a-17) restarting the sequence from step (a-1) of claim 14.

Claim 19

The process of claim 15 including the steps of: (a-18) accumulating a plurality of strings of sorted data records in an external storage resulting from the sequences of claims 14 and 15; and (a-19) merging said strings of data records from said external storage through said sort processor to accumulate a complete sorted list of data records.

Claim 20

The process of claim 16 including the step of: (a-20) reading out the sorted records of the completed sorted list from external storage in order to establish a read-out of the actual list of records sorted by the specified key word.