Packed loop memory with data manipulation capabilities
First Claim
1. In a multi-record circulating loop memory system, apparatus for sorting the data records contained therein comprisinga 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
Specification