Packed loop memory with data manipulation capabilities

• US 4,064,556 A
• Filed: 06/23/1975
• Issued: 12/20/1977
• Est. Priority Date: 06/23/1975
• Status: Expired due to Term

• Current Assignee: Sperry Rand Corporation
• Original Assignee: Sperry Rand Corporation
• Inventors: Edelberg, Murray, Bonn, Theodore H., Schissler, Lloyd R.
• Primary Examiner(s): Chapnick, Melvin B.
• Application Number:
  US05/589,321
• Time in Patent Office: 911 Days
• Field of Search: 340/172.5, 445/1
• US Class Current: 711/110
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: G11C 19/00 Digital stores in which the information is moved stepwise, e.g. shift registers

Abstract

A digital memory comprising a multiplicity of circulating storage loops, in each of which, a plurality of digital data records are stored, and apparatus for sorting the data records. More particularly, a plurality of distributed processing elements perform a parallel sorting operation of each column of data records, where each column of data records is comprised of one data record in each circulating storage loop and the data records comprising each column are disposed in the same record position within their respective circulating storage loops. Thereafter, the apparatus performs a "precession" of the data records whereby the data records in each circulating storage loop are shifted one record position, in a common direction, with respect to the data records stored in the next preceding circulating storage loop. The apparatus repeats the column sorting operation and the precessions alternately until the column sort has been performed a number of times equal to the number of data record positions in each circulating storage loop. At this point the memory contents are sorted into "buckets," that is, the data records in each circulating loop are sorted with respect to the data records in every remaining loop though not necessarily with respect to each other. Apparatus is also provided to perform a final sort of the data records within each circulating storage loop. Additionally, the processing elements may be arranged to perform a variety of functions such as searching, retrieval, updating, and dynamic reconfiguration of the memory.

Claims

1. In a multi-record circulating loop memory system, apparatus for sorting the data records contained therein comprising

a plurality of circulating loop means having k record positions therein for storing k data records, where k is a positive integer, and wherein columns of data records are formed comprising a data record from each circulating loop means and where said data records forming said columns are disposed in the same record position within their respective circulating loop means;

first data processing circuit means for performing data comparisons of a predetermined type suitable for sorting in accordance with predetermined criteria, said comparisons being performed in each of said columns between data records disposed in the same column and re-ordering said data records within their respective columns according to said comparisons;

second data processing circuit means for precessing the data records stored within said memory system such that the data records disposed in each circulating loop means are shifted a record position, in a common direction, with respect to the data records in the next preceding circulating loop means; and

means for coupling data manipulation control signals from said memory system to said first and second data processing circuit means including signals for operating said first and second data processing circuit means alternately wherein, subsequent to k operations of said first data processing circuit means and k-1 operations of said second data processing circuit means, the data records stored in each circulating loop means are sorted with respect to the data records disposed in every other circulating loop means.

2. The apparatus as described in claim 1 wherein said second data processing circuit means comprises

precession register means for storing and manipulating a precession state signal from said means for coupling data manipulation control signals and generating therefrom a precess signal for each of said circulating loop means with which the precession of each circulating loop means is determined;

and

precession control means coupled to said circulating loop means, said means for coupling data manipulation control signals, and said precession register means for precessing each said circulating loop means in response to said precess signal in conjunction with a precession enable signal from said means for coupling data manipulation control signals.

3. The apparatus as described in claim 2 wherein each circulating loop means includes

main loop means comprising a substantial portion of the length, with respect to units of storage capacity, of said circulating loop means,

auxiliary loop means comprising the remainder of the length of said circulating loop means wherein the length of said main loop means is an integer multiple of the length of said auxiliary loop means, and

switching means for coupling said auxiliary loop means to said main loop means and responsive to said precession control means, such that for the appropriate precess signal in conjunction with said precession enable signal said switching means isolates said auxiliary loop means from said main loop means prohibiting the data disposed therein from circulating through said circulating loop means with the data disposed in said main loop means,

whereby a circulation of the the data records in all circulating loop means through a length equal to the length of said main loop means multiplied by s, where s is an integer and s multiplied by the length of said auxiliary loop means equals the length of a data record, results in a precession of the data records in said circulating loop means wherein said switching means maintains coupling between said main and auxiliary loop means with respect to the data records stored in said circulating loop means in which said main and auxiliary loop means are isolated by said switching means;

and wherein, after said circulation, the ordering of said data records within, said circulating loop means isolated by said switching means is maintained subsequent to re-coupling between said main and auxiliary loop means.

4. The apparatus of claim 1 wherein said first data processing circuit means comprises a plurality of loop processing circuit means is serially coupled in each of two said circulating loop means, and each said circulating loop means being serially coupled through two said loop processing circuit means at different points of said loop means, respectively.

5. The apparatus as described in claim 4 wherein said loop processing circuit means comprises:

comparator means, responsive to signals from said means for coupling data manipulation control signals, for comparing each data record disposed in the first circulating loop means associated with said loop processing circuit means with the data record disposed in the same column of the second circulating loop means associated with said loop processing circuit means thereby means associated with said loop processing circuit means thereby making data comparisons, and generating in response to each said data comparison, an interchange signal where re-ordering is necessary as defined by said signal from said means for coupling data manipulation control signals, and

loop control means, responsive to said comparator means, for maintaining, in the absence of an interchange signal, the disposition of compared data records within their respective circulating loop means, and in the presence of said interchange signal, for interchanging the compared data records between the associated circulating loop means such that the compared data records, in either event, are maintained within said same column,

whereby a sorting operation, with respect to the data records in each column, is performed after a plurality of said data comparisons.

6. The apparatus as described in claim 1 wherein said memory system further includes at least one data port means, responsive to said means for coupling data manipulation control signals, and coupled to an extremity of said plurality of circulating loop means for loading and unloading data into and out of said memory system respectively.

7. The apparatus as described in claim 6 further including means, responsive to said means for coupling data manipulation control signals, and coupled between said data port means and said extremity of said plurality of circulating loop means for sorting the data records disposed in each circulating loop as said data records are unloaded from said memory system.

8. The apparatus as described in claim 5 wherein said loop processing circuit means perform a plurality of data manipulation functions in addition to sorting in response to signals from said means for coupling data manipulation control signals as said data records circulate through said loop processing circuit means.

9. The method, utilizing the circulating loop memory system of claim 1 including a memory, of sorting the contents of said memory which includes a plurality of circulating storage loops each containing k data records, where k is a positive integer and wherein k columns of data records are formed each of which is comprised of a data record from each circulating storage loop and wherein said data records comprising said columns are disposed in the same position within their respective circulating loops;

comprising in combination the steps of;

arranging in sorted order according to predetermined criteria the data records disposed in each column utilizing said first data processing circuit means;

precessing the data records in each circulating loop, utilizing said second data processing circuit means, such that the data records disposed in each circulating loop are shifted a record position, in a common direction, with respect to the data records disposed in the next adjacent circulating storage loop; and

repeating the above-mentioned steps alternately until the kth operation of arranging said columns in sorted order is performed, whhereupon the data records disposed in each circulating storage loop will be sorted with respect to the data records disposed in every other circulating storge loop.

10. The method as described in claim 9 wherein the step of arranging a column of data records in sorted order, comprises in combination the steps of

a. comparing each data record disposed in each circulating storage loop with the data record disposed in the preceding circulating loop with the same column except for the first circulating storage loop,

b. comparing each data record disposed in each circulating loop with the data record disposed in the succeeding circulating storage loop within the same column, except for the last circulating storage loops, and

repeating steps (a) and (b) alternately for at most m/2 times where m is equal to the number of circulating storage loops.

11. The method as described in claim 9 wherein the step of precessing comprises in combination the steps of:

combining said circulating storage loops into successive groups each comprised of k circulating loops and a final group containing the remaining circulating loops where the number of circulating storage loops is not an integer multiple of k, and

shifting the data records in each circulating loop within each group a total of n-1 record positions where n corresponds to the number of each loop within its group and n is a positive integer ≦

k.

12. The method as described in claim 9 further including the step of sorting the data records within each circulating storage loop thereby effecting a complete sort of the data records stored within the memory.