Associative memory device

• US 3,906,455 A
• Filed: 03/15/1974
• Issued: 09/16/1975
• Est. Priority Date: 03/15/1974
• Status: Expired due to Term

• Current Assignee: George B. Houston, Roger H. Simonsen
• Original Assignee: George B. Houston, Roger H. Simonsen
• Inventors: Houston, George B., Simonsen, Roger H.
• Primary Examiner(s): Fears, Terrell W.
• Application Number:
  US05/451,634
• Time in Patent Office: 550 Days
• Field of Search: 340/172.5,173RC,173AM
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc

Abstract

Apparatus for storing and associatively manipulating a large (10 X 106 character) data base is disclosed. Said apparatus providing access control to devices constructed to operate in a block oriented random access manner and providing decision logic asynchronous to a digital computer connected to said apparatus to provide the location of stored data satisfying selected Boolean combinations of conditions and conjunctive operations over a designated portion of the total data base.

Claims

1. An associative memory device comprising:

a. a data storage device wherein;

1. data is stored and retrieved in predefined data blocks of equal numbers of bits;

2. the data in said data blocks is maintained in a constantly circulating state;

3. means are provided for reading said data blocks from said storage device and for writing said data blocks to said storage device;

4. said data in said data blocks is read from said storage device and written to said storage as the circulating data passes said means for reading and writing said data blocks;

5. said data blocks are comprised of data subblocks of equal numbers of bits;

6. said data sub-blocks are divided into data fields as defined by each individual request to the associative memory device. b. a data storage device acquisition logic segment wherein;

1. said data blocks are addressed by data block groups, each data block group containing at least one data block;

2. said data block groups are comprised of daTa block subgroups containing equal numbers of data blocks;

3. means for parallel data transfer are provided to transfer data from said data storage device in parallel in units of data block subgroups, and c. a data processing logic segment wherein;

1. a subgroup processing element is provided for each data block subgroup contained in a data block group, each subgroup processing element containing means for receiving and storing the data in one data block subgroup being transferred in parallel from said data storage device by said data storage device acquisition logic segment;

2. a search specification control logic segment is provided, said search specification control logic being accessible by the computer program accessing said associative memory device to preset the limits of data search, the definition of said data fields, and the search success criteria for the duration of each access where access is the time from a request for an associative search by a computer program to said associative memory device until said associative memory device returns the results of the search to the requesting computer program;

3. logic is provided to combine the data in said subgroup processing elements and said search specification control logic to arrive at a best value from each data block subgroup and then combine said best values from the data block subgroups to arrive at a best value for the data block group;

4. logic is provided to cause said data storage device acquisition logic to transfer additional data block groups within the limits specified by said search specification control logic and to combine the best values for data block groups into a device result.

2. a search specification control logic segment is provided, said search specification control logic being accessible by the computer program accessing said associative memory device to preset the limits of data search, the definition of said data fields, and the search success criteria for the duration of each access where access is the time from a request for an associative search by a computer program to said associative memory device until said associative memory device returns the results of the search to the requesting computer program;

3. means are provided for reading said data blocks from said storage device and for writing said data blocks to said storage device;

4. An associative memory device as claimed in claim 1 wherein, additionally:

a. logic is provided in said data storage device acquisition logic segment to allow searching over more than one of said data storage devices; and

b. logic is provided in said data processing logic segment to combine said device results for each of said data storage devices into one final search result.

5. said data blocks are comprised of data subblocks of equal numbers of bits;

6. An associative memory device as claimed in claim 1 wherein:

said best value is determined on the basis of said data fields of said data sub-blocks meeting individual and conjunctive Boolean criteria input to said associative memory device as said device is accessed, said best value being the data sub-block that best meets said Boolean criteria.

7. An associative memory device as claimed in claim 1 wherein:

said best value is determined on the basis of said data fields of said data sub-blocks meeting individual and conjunctive Boolean criteria input to said associative memory device as said device is accessed, said best value being the data sub-block that first meets said Boolean criteria.

8. An associative memory device as claimed in claim 1 wherein, additionally:

logic is provided to limit the search for said best Value to a portion of said data storage device as specified by criteria input to said associative memory device as said device is accessed.

9. An associative memory device as claimed in claim 7 wherein:

the location of said best value which first meets said Boolean criteria is returned along with said device result.

10. An associative memory device comprising:

a. a circulating data storage device, said storage device being characterized by maintaining data contained therein in records comprising a preselected fixed number of bits, said data contained therein being addressable by sectors comprising a preselected fixed number of records, said data being further grouped into tracks comprising a preselected fixed number of sectors, track subgroups comprising a preselected fixed number of tracks, and track groups comprising a preselected fixed number of track subgroups;

b. means connected to said circulating data storage device for transferring said data contained therein from said circulating data storage device in a parallel mode in said track groups;

c. means connected to said means for transferring said data contained therein from said circulating data storage device in parallel mode in said track groups for selecting which of said track groups is to be transferred from said circulating data storage device;

d. means connected to said means for selecting which of said track groups is to be transferred from said circulating data storage device for receiving and storing said transferred track groups of data;

e. means responsive to said means for receiving and storing said transferred track groups of data for processing in parallel in track subgroups the data in each of said transferred track groups of data, said means for processing in parallel in track subgroups the data in each of said transferred track groups of data producing a best result for each track subgroup in each of said transferred track groups;

f. means cooperating with said means for processing in parallel in track subgroups the data in each of said transferred track groups of data for accepting the search criteria from the requesting computer program and for using said search criteria for specifying the area of said circulating data storage device to be searched and the criteria for selecting a best result, said best result being said record having said bits which best meet the search criteria provided by the requesting computer program when only one answer will meet said search criteria and which first meets said search criteria when more than one record can meet said criteria;

g. means responsive to said best result for each track subgroup for comparing said best result for each track subgroup and for producing a best result for each of said track groups;

h. means responsive to said best result for each track group for comparing said best result for each track group and for producing a best result for said circulating data storage device, and i. means responsive to said best result for said circulating data storage device for returning said best result for said circulating data storage device and the location of the record containing said best result for said circulating data storage device to the requesting computer program as a final results.

11. An associative memory device as claimed in claim 10 wherein, additionally, a. more than one circulating data storage device is provided, and b. means are provided responsive to said best results for each of said circulating data storage devices for comparing said best results and producing a single best results for all circulating data storage devices.

12. An associative memory device as claimed in claim 10 wherein:

a. said bits comprising said records are grouped into fields as defined by each requesting computer program, and b. said search criteria provided by each requesting computer program specifies which of said fields of each of said records are to be inspected and which of saiD fields of each of said records are to be ignored during the search for said best value.

13. An associative memory device as claimed in claim 12 wherein, additionally:

said search criteria provided by each requesting computer program specifies conjunctive operations across a variety of said fields of said records.