DYNAMIC ASSOCIATIVE DATA PROCESSING SYSTEM

• US 3,611,314 A
• Filed: 09/09/1969
• Issued: 10/05/1971
• Est. Priority Date: 09/09/1969
• Status: Expired due to Term

• Current Assignee: Herschell F. Murry, John P. Pritchard Jr
• Original Assignee: Herschell F. Murry, John P. Pritchard Jr
• Inventors: Pritchard, John P. Jr., Murry, Herschell F.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US04/856,267
• Time in Patent Office: 756 Days
• Field of Search: 340/172.5
• US Class Current: 711/112
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

An associatively organized data processing system is disclosed. The bits of each data word are recorded radially on a magnetic disk by means of a separate read-write head for each bit track. Logic circuitry is provided for each read-write head to perform associative processing. Thus, all words in memory can be associatively processed after one revolution of the disk. The match and occupancy status of each work is determined by corresponding bits on an occupancy-status track and a matchstatus track. The status tracks are updated as each word is logically processed by means of spaced read and write heads and shift registers to delay the bits of status data before they are updated and recorded back on the disk in accordance with the associative processing of the words.

Claims

1. In a method for processing data, the steps of organizing a memory unit into a plurality of word positions, each word position having at least a minimum number of corresponding bit positions, each word position including at least one status bit representing the occupancy status of the word, cycling the words to means for writing in the words, and writing new data in each word identified as vacant by the respective status bit.

2. In a method for processing data, the steps of organizing a memory unit into a plurality of word positions, each word position having at least a minimum number of corresponding bit positions, each word position including an occupancy status bit indicating the occupancy status of the word position, scanning the word positions while reading the occupancy status bit and writing new data words in the word positions identified as vacant by the respective occupancy status bits.

3. The method for processing data stored as a plurality of content addressable words each word position having a plurality of bits with at least one bit of each word representing the status of the word which comprises repetitively cycling all of the words to processing logic, processing each word only while at the processing logic, and updating the status bit of each word while the word is still at the processing logic to record the results of said processing.

4. The method of claim 3 including the steps of:

a. designating one of said status Bits an occupancy-status bit for representing the occupancy status of its respective word; and

b. designating another of said status bits a matched-status bit for representing the respective word satisfying an associative search criteria.

5. The method for processing data comprised of organizing the data into a plurality of words each word having a corresponding number of bit positions and identifiable only by content, continuously and sequentially cycling all of the words past a processing window, processing selected words as the respective words are cycled past the processing window and updating the words in at least one bit position as required to maintain a record of the status of the word in relation to the processing.

6. The method for processing data comprised of organizing the data into a plurality of words each comprised of a corresponding number of bit positions and having at least one status bit, repetitively sequencing the words to a processing window, and updating the respective status bits in accordance with the processing of the respective words before the respective words leave the processing window.

7. The method for processing data comprising organizing the data into a plurality of words each word comprised of a corresponding set of bit positions, one of the bit positions of each word defining the occupancy status of the word and another bit position of each word defining the match status of the word, repetitively sequencing the words to a processing window while processing the respective words only during the period the words are within the processing window, the processing including updating of the status bits to maintain a record of the results of the processing for subsequent processing.

8. The system for associatively processing data which comprises:

logic means for comparing a data word having a plurality of bits to an associative argument and producing a logic signal representative of the comparison, memory means organized to store a plurality of the words and cyclically present the words stored therein to the logic means, and means for updating at least one bit of each word in response to the logic signal from the logic means to store the results of the comparison of the word and the associative argument of said memory means for subsequent processing.

9. The system of claim 8 wherein the memory means is mounted on a rotating member.

10. The system of claim 8 wherein the memory means is a rotating magnetic recording means.

11. The system of claim 8 wherein the memory means comprises a plurality of parallel shift registers having corresponding numbers of bits.

12. The system of claim 8 wherein the logic means includes:

a head buffer for sequentially receiving the words from the memory means, an argument buffer for storing an associative argument, and logic gate means for comparing the word in the head buffer to the word in the argument buffer.

13. The system of claim 12 wherein the logic gate means includes means for producing an '"'"''"'"''"'"''"'"'equal to'"'"''"'"''"'"''"'"' logic signal when the word in the head buffer is equal to the word in the argument buffer.

14. The system of claim 12 wherein the logic gate means includes means for producing a '"'"''"'"''"'"''"'"'greater than'"'"''"'"''"'"''"'"' logic signal when the word in the head buffer is greater than the word in the argument buffer.

15. The system of claim 14 further characterized by means of shifting the word in the head buffer to the argument buffer when a '"'"''"'"''"'"''"'"'greater than'"'"''"'"''"'"''"'"' logic signal is produced by the logic gate means.

16. The system of claim 14 further characterized by means of shifting the word in the head buffer to the argument buffer when a '"'"''"'"''"'"''"'"'less than'"'"''"'"''"'"''"'"' logic signal is produced by the logic gate means.

17. The system of claim 12 wherein the logic gate means includes means for producing a '"'"''"'"''"'"''"'"'less than'"'"''"'"''"'"''"'"' logic signal when the word in the head buffer is less than the word in the argument buffer.

18. The system of claim 8 wherein the means for updAting said at least one bit of each word comprises means for writing in said at least one bit after the word has passed the logic means.

19. The system of claim 8 further characterized by:

write means for writing in the words of the memory means as the words are cyclically presented to the write means, and means for reading said at least one bit prior to the presentation of the respective word to the write means and enabling the write means as the respective word is presented to the write means when said at least one bit contains a predetermined logic condition.

20. The system defined in claim 8 further characterized by:

read means for reading the words in memory as the words are cyclically presented to the read means, and means for reading said at least one bit prior to the presentation of the data word to the read means and producing a logic signal enabling the read means to read the respective word as it is presented to the read means.

21. In a system for processing data, the combination of:

rotating storage means defining a plurality of data words each having a plurality of bits, each word including at least one corresponding status bit, means for simultaneously reading said plurality of bits of each word in succession and comparing the bits with an associative argument and producing a logic signal representative of the comparison, and means for writing in the corresponding status bit in response to the logic signal to record the results of the comparison.

22. In a system for processing data, the combination of:

rotating storage means defining a plurality of data words each having a plurality of bits, each word including a corresponding occupancy-status bit, write means for writing in the bits of each word as the storage means rotates the respective words past the read means, means for reading the occupancy-status bit of each word prior to the positioning of the word at the write means and producing a logic signal enabling the write means as the corresponding word is positioned at the write means when the occupancy-status bit indicates that the word is vacant, and means for updating the occupancy-status bit for each word when a new word is written therein to indicate that the word is occupied.

23. In a system for processing data the combination of:

rotating storage means defining a plurality of data words each having a plurality of corresponding bits, each word including a corresponding match-status bit, read means for reading the bits of each word as the storage means rotates past the read means, and means for reading the match-status bit of each word prior to the positioning of the corresponding word at the read means and producing a logic signal enabling the read means as the corresponding word is positioned at the read means when the match-status bit indicates that the word is matched.

24. In a system for processing data, the combination of:

rotating storage means having a plurality of data tracks and at least one status track, read means for simultaneously writing bits of data on the respective data tracks and write means for simultaneously reading bits of data from the respective data tracks to define a series of words each having a corresponding number of bits, status track read means for reading bits from the status track, status track write means for writing on the status track after the read means, shift register means having a number of bits equal to the number of bit positions on the status track between the status track read means and the status track write means for transferring data bits from the status track read means to the status track write means, first logic means responsive to the data in a bit of the shift register means for selectively enabling the read means as the corresponding word is positioned at the read means, and second logic means responsive to the performance of a read or write function in a word for updating the correspoNding bit in the shift register means for writing back on the status track.

25. In a system for processing data, the combination of:

associative processing means, and storage means for cycling a plurality of associatively organized data words to the associative processing means, and for cycling a status bit of information corresponding to each data word with the corresponding data words including means for reading the status bit prior to arrival of the corresponding data word at the associative processing means and means for updating the status bit after the corresponding data word has been situated at the processing means for processing.

26. A method for processing data comprising the steps of:

a. organizing a memory unit into a plurality of word positions, each word position having at least a minimum number of corresponding bit positions including at least one status bit position;

b. repetitively cycling the words stored in said memory unit to data processing logic; and

c. performing data processing operations on the words with said processing logic, the data processing operations including;

d. updating the at least one status bit of the respective words as required to represent the results of the data processing to said words.

27. The method of claim 26 including the steps of:

a. recording words on a rotating storage means of said memory unit; and

b. cycling said rotating storage means past a read-write station of said memory unit.

28. The method of claim 26 including the step of shifting words through a fixed storage means of said memory unit to a read-write station of said memory unit.

29. A method for processing data comprising the steps of:

a. organizing a memory unit into a plurality of word positions, each word position having at least a minimum number of corresponding bit positions including at least two status bits;

b. designating one of said status bits an occupancy status bit for representing the occupancy status of its respective word;

c. designating another of said status bits a match-status bit for representing the respective word satisfying an associative search criteria;

d. repetitively cycling the words stored in said memory unit to data processing logic; and

e. performing data processing operations on the words stored in said memory unit with said data processing logic, said data processing operations including;

f. updating the status bits of respective words as required to represent the results of the data processing to said words.

30. The method of claim 29 including the steps of:

a. comparing the words indicated as occupied by said occupancy bits to an associated argument at preselected bits; and

b. updating said match-status bits of the respective words to reflect the results of the comparison.

31. The method of claim 30 wherein said match-status bits are updated to a matched status for each word that is identical to the argument at selected bits.

32. The method of claim 30 wherein the match-status bit is updated to a matched status for each word that is greater than the argument at selected bits.

33. The method of claim 30 wherein the match-status bit is updated to a matched status for each word that is less than the argument at selected bits.

34. The method of claim 30 wherein the match-status bit is updated to a matched status for each word that is greater than or equal to the argument at selected bits.

35. The method of claim 30 wherein the match-status bit is updated to a matched status for each word that is less than or equal to the argument at selected bits.

36. The method of claim 29 including the step of reading the words in which the matched status bits indicate that a previous associative search criteria was satisfied during subsequent cycles of the word.