Digital memory with data manipulation capabilities

• US 4,037,205 A
• Filed: 05/19/1975
• Issued: 07/19/1977
• Est. Priority Date: 05/19/1975
• Status: Expired due to Term

• Current Assignee: Sperry Rand Corporation
• Original Assignee: Sperry Rand Corporation
• Inventors: Edelberg, Murray, Schissler, Lloyd R.
• Primary Examiner(s): Morrison, Malcolm A.
• Assistant Examiner(s): Krass, Errol A.
• Application Number:
  US05/578,685
• Time in Patent Office: 792 Days
• Field of Search: 340/172.5, 179/15 R
• US Class Current: 711/110
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• 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
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A digital memory comprising a plurality of contiguous circulating serial data storage loops and a plurality of processing elements. Each pair of adjacent loops are coupled to a processing element such that each loop is coupled through two processing elements displaced by one-half loop length. Each processing element includes a serial comparator and a loop control circuit for either isolating or exchanging the data on the two incident loops. Additional circuits are included in each processing element which in combination with the comparator and loop control provide the memory, as the loop data circulates through the processing elements, with the capability of performing an ascending or descending sort of its contents, an associative search of its contents with retrieval of located data, an updating of stored data records, a loading or unloading of a record file or data base and a dynamic reconfiguration of the memory structure.

Claims

1. Digital memory apparatus for storing and processing digital data comprising

a plurality of circulating storage loop means for storing and circulating said digital data therein,

a plurality of data processing circuit means,

each said data processing circuit means being serially coupled in each of two said circulating storage loop means,

each said circulating storage loop means being serially coupled through two said data processing circuit means at different points of said loop means respectively, and

means for coupling data manipulation control signals including a mode defining signal and key field defining signals to said plurality of data processing circuit means,

each said data processing circuit means including comparator means responsive to said data manipulation control signals and to said digital data circulating in at least one of said two storage loop means associated therewith for performing comparisons with respect to said digital data in accordance with said control signals and loop control means coupled to said comparator means and serially coupled in said two loop means associated therewith for selectively effecting isolating and data interchanging connections between said two loop means,

wherein said data processing circuit means performs a plurality of data manipulation operations with respect to said digital data in response to said data manipulation control signals as said digital data serially circulates through said data processing circuit means.

2. The apparatus of claim 1 in which each said data processing circuit means comprises

comparator means responsive to said mode defining signal specifying a sort mode, to said key field defining signals and to said digital data circulating in said two storage loop means associated therewith for performing data comparisons between the data in said two storage loop means in the key fields defined by said key field defining signals and to generate a binary valued interchange signal in accordance with said data comparisons, and

loop control means serially coupled in said two loop means associated therewith and responsive to said loop interchange signal for effecting an isolating or data interchanging connection between said two loop means selectively in accordance with the respective binary value of said loop interchange signal,

thereby performing a sort of said digital data circulating in said plurality of circulating storage loop means in response to said sort mode defining signal.

3. The apparatus of claim 2 in which said means for coupling further includes means for coupling a key defining signal to said plurality of data processing circuit means.

4. The apparatus of claim 3 in which said comparator means includes means responsive to said mode defining signal specifying a search mode, to said key field defining signals, to said key defining signal and to said digital data circulating in one of said two storage loop means associated therewith for performing data comparisons between key data provided by said key defining signal and the data in said one storage loop means in the key fields defined by said key field defining signals and to generate a binary valued successful search signal whose binary values are representative respectively of a successful or unsuccessful search in accordance with said data comparisons,

said comparator means generating said interchange signal to effect said isolating connection in said loop control means when said search mode defining signal is active,

thereby performing a search with respect to said key data of said digital data circulating in said plurality of circulating storage loop means in response to said search mode defining signal.

5. The apparatus of claim 4 in which

said comparator means includes means for generating a replacement field signal on a replacement field line, said replacement field signal defining a replacement field of said digital data circulating in said one storage loop means and a replacement data signal on a replacement data line, said replacement data signal defining data to be inserted into said replacement field, and

said loop control means includes means responsive to said replacement field line and said replacement data line for inserting said replacement data into said replacement field as said digital data circulates through said loop control means.

6. The apparatus of claim 5 in which said means for coupling further includes means for coupling a tag field defining signal to said plurality of data processing circuit means.

7. The apparatus of claim 6 in which said comparator means further includes means for gating said tag field defining signal to said replacement field line when said search mode defining signal is active and for gating said successful search signal to said replacement data line, thereby inserting said successful search signal into the tag field defined by said tag field defining signal of said digital data circulating in said one storage loop means.

8. The apparatus of claim 7 in which said memory apparatus includes at least one data port at an extremity of said plurality of circulating storage loop means and with said sort mode defining signal active and said key field defining signal specifying said tag field, said digital data with said successful search signal in said tag field representative of a successful search are driven to said data port for retrieval.

9. The apparatus of claim 8 in which said data port includes an input terminal and with said sort mode defining signal active, said key field defining signal spanning a non-zero data field and a data file to be loaded applied to said input terminal, said data file is loaded into said memory apparatus.

10. The apparatus of claim 9 in which said data port includes an output terminal and with said sort mode defining signal active, said key field defining signal spanning a non-zero data field and a constant applied to said input terminal, the contents of said memory apparatus are unloaded at said output terminal.

11. The apparatus of claim 7 in which said means for coupling further includes means for coupling an update field defining signal and an update data defining signal to said plurality of data processing circuit means.

12. The apparatus of claim 11 in which said comparator means includes means responsive to said mode defining signal specifying an update mode for gating said update field defining signal to said replacement field line and said update data defining signal to said replacement data line, thereby updating the data field defined by said update field defining signal of selected digital data circulating in said plurality of circulating storage loop means with the data defined by said update data defining signal in response to said update mode defining signal.

13. The apparatus of claim 5 in which

said plurality of data processing circuit means are arranged sequentially in said memory apparatus, each said data processing circuit means providing a successful search chain signal, and

said comparator means includes a response output, the response outputs from said plurality of data processing circuit means being commonly connected to form a response line for said memory apparatus.

14. The Apparatus of claim 13 in which each said data processing circuit means includes data retrieval control means responsive to said successful search signal from the comparator means associated therewith and to the successful search chain signal from the previous data processing circuit means in said sequential arrangement thereof for providing an enable response signal to said comparator means associated therewith and a successful search chain signal to the next following data processing circuit means,

said enable response signal being rendered active only at the first data processing circuit means in the said sequential arrangement thereof having the comparator means thereof providing a successful search signal representative of a successful search,

said successful search chain signal provided to the data processing circuit means following said first data processing circuit means rendering the respective enable response signals thereof inactive,

each said comparator means including means for directing said digital data circulating in said one storage loop means associated therewith to said response output in response to an active enable response signal,

thereby retrieving said digital data circulating in said one storage loop means associated with said first data processing circuit means.

15. The apparatus of claim 14 in which said means for coupling further includes means for coupling a next response signal to said plurality of data processing circuit means.

16. The apparatus of claim 15 in which

said data retrieval control means includes means responsive to said next response signal for providing a reset signal that is rendered active only at the first data processing circuit means in said sequential arrangement thereof having the comparator means thereof providing a successful search signal representative of a successful search, and

said comparator means includes means for resetting said successful search signal to the state representative of an unsuccessful search in response to an active reset signal,

thereby retrieving said digital data circulating in said one storage loop means associated with the data processing circuit means following said first data processing circuit means and having the successful search signal associated therewith representative of a successful search.

17. The apparatus of claim 14 in which said comparator means comprises

a sequential state machine responsive to said mode defining signal, to said key field defining signal, to said key defining signal and to said digital data circulating in at least one of said two storage loop means associated therewith for performing said data comparisons and providing state signals in accordance therewith, and

comparator output logic responsive to said mode defining signal, to said key field defining signal, to said key defining signal, to said digital data circulating in one of said two storage loops associated therewith, to said enable response signal and to said state signals for providing said loop interchange signal, said successful search signal, said replacement field signal, said replacement data signal and said response output in accordance therewith.

18. The apparatus of claim 2 in which each said data processing circuit means further includes activity control means responsive to said mode defining signal specifying a reconfigure mode and to an activity signal for rendering said data processing circuit means active or inactive in accordance with said activity signal, said activity signal being applied to said loop control means to unconditionally effect said data interchanging connection for an inactive data processing circuit means and to render said loop interchange signal effective in selecting either said data interchanging connection or said isolating connection for an active data processing circuit means, thereby performing a reconfiguration of said memory apparatus in response to said reconfigure mode defining signal.

19. The apparatus of claim 18 in which each said circulating storage loop means is serially coupled through two active data processing circuit means at respective points of said loop means separated by one-half loop length,

said two active data processing circuit means belonging to odd and even phases respectively,

said key field defining signals belonging to said odd and even phases respectively.

20. The apparatus of claim 19 in which said activity control means further includes phase control means responsive to said mode defining signal specifying said reconfigure mode and to said activity signal for rendering said odd or even phase key field defining signals effective in accordance with the respective phase of the associated data processing circuit means.

21. The apparatus of claim 1 in which each said data processing circuit means is serially coupled in each of two adjacent circulating storage loop means.

22. The apparatus of claim 1 in which each said circulating storage loop means is serially coupled through to said data processing circuit means at respective points of said loop means separated by one-half loop length.

23. The apparatus of claim 1 in which each said circulating storage loop means comprises re-entrant shift register means.