ASSOCIATIVE LIST SELECTOR.
Abstract
The design and operation of an Associative List Selector (ALS) and a Switching Unit (SUN) is described. The ALS, used in conjunction with a controlling computer (either the CDC 1604B or the Univac M1218), provides a unique approach to rapid list intersection. The approach utilized is a form of content addressing, and specifically is termed hash addressing or address calculation. The memory within the ALS is a conventional read/modify/write memory with a cycle time of one microsecond. It has the capacity to store 4096 words of 72 bits each. The ALS has the ability to handle lists with a nominal length of 2000 items. Basic operation consists of storing a reference or master list in the ALS memory. Subsequent search lists are then transferred to the ALS. Effectively, the complete master list is searched for a match with each item of each search list. Matches are marked in a tag field of memory; one tag column is required for marking the intersection of the master list with a search list. A single tag column may also be used to mark the intersection of the master list with the union of two or more search lists. A total of twenty-four tag columns are provided. Data items in the stored master list can be retrieved on the basis of programmer-specified tag field configuration. Addressing for the storage and search operation are accomplished by mapping or transforming each 36-bit data item into an 11-bit address. Using this method of addressing, an item known to be present can be found with 1.5 memory probes on the average if the lists are completely random. Since the memory cycle time is one microsecond, one memory probe can be accomplished in one microsecond.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1966
- Accession Number
- AD0802993
Entities
People
- Dale E. Brotherton
- Russell G. Gall
Organizations
- Goodyear Aerospace