Content-Addressable Memories

1 Associative Memory, Content Addressing, and Associative Recall.- 1.1 Introduction.- 1.1.1 Various Motives for the Development of Content-Addressable Memories.- 1.1.2 Definitions and Explanations of Some Basic Concepts.- 1.2 The Two Basic Implementations of Content Addressing.- 1.2.1 Software Implementation: Hash Coding.- 1.2.2 Hardware Implementation: The CAM.- 1.3 Associations.- 1.3.1 Representation and Retrieval of Associated Items.- 1.3.2 Structures of Associations.- 1.4 Associative Recall: Extensions of Concepts.- 1.4.1 The Classical Laws of Association.- 1.4.2 Similarity Measures.- 1.4.3 The Problem of Infinite Memory.- 1.4.4 Distributed Memory and optimal Associative Mappings.- 1.4.5 Sequential Recollections.- 2 Content Addressing by Software.- 2.1 Hash Coding and Formatted Data Structures.- 2.2 Hashing Functions.- 2.3 Handling of Collisions.- 2.3.1 Some Basic Concepts.- 2.3.2 Open Addressing.- 2.3.3 Chaining (Coalesced).- 2.3.4 Chaining Through a Separate overflow Area.- 2.3.5 Rehashing.- 2.3.6 Shortcut Methods for Speedup of Searching.- 2.4 Organizational Features and Formats of Hash Tables.- 2.4.1 Direct and Indirect Addressing.- 2.4.2 Basic Formats of Hash Tables.- 2.4.3 An Example of Special Hash Table Organization.- 2.5 Evaluation of Different Schemes in Hash Coding.- 2.5.1 Average Length of Search with Different Collision Handling Methods.- 2.5.2 Effect of Hashing Function on the Length of Search.- 2.5.3 Special Considerations for the Case in Which the Search Is Unsuccessful.- 2.6 Multi-Key Search.- 2.6.1 Lists and List Structures.- 2.6.2 An Example of Implementation of Multi-Key Search by Hash Index Tables.- 2.6.3 The Use of Compound Keywords in Hashing.- 2.7 Implementation of Proximity Search by Hash Coding.- 2.8 The TRIE Memory.- 2.9 Survey of Literature on Hash Coding and Related Topics.- 3 Logic Principles of Content-Addressable Memories.- 3.1 Present-Day Needs for Hardware CAMs.- 3.2 The Logic of Comparison Operations.- 3.3 The All-Parallel CAM.- 3.3.1 Circuit Logic of a CAM Bit Cell.- 3.3.2 Handling of Responses from the CAM Array.- 3.3.3 The Complete CAM Organization.- 3.3.4 Magnitude Search with the All-Parallel CAM.- 3.4 The Word-Parallel, Bit-Serial CAM.- 3.4.1 Implementation of the CAM by the Linear-Select Memory Principle.- 3.4.2 Skew Addressing.- 3.4.3 Shift Register Implementation.- 3.4.4 The Results Storage.- 3.4.5 Searching on More Complex Specifications.- 3.5 The Word-Serial, Bit-Parallel CAM.- 3.6 Byte-Serial Content-Addressable Search.- 3.6.1 Coding by the Characters.- 3.6.2 Specifications Used in Document Retrieval.- 3.6.3 A Record-Parallel, Byte-Serial CAM for Document Retrieval.- 3.7 Functional Memories.- 3.7.1 The Logic of the Bit Cell in the FM.- 3.7.2 Functional Memory 1.- 3.7.3 Functional Memory 2.- 3.7.4 Read-only Functional Memory.- 3.8 A Formalism for the Description of Micro-Operations in the CAM.- 3.9 Survey of Literature on CAMs.- 4 CAM Hardware.- 4.1 The State-of-the-Art of the Electronic CAM Devices.- 4.2 Circuits for All-Parallel CAMs.- 4.2.1 Active Electronic Circuits for CAM Bit Cells.- 4.2.2 Cryotron-Element CAMs.- 4.2.3 Josephson Junctions and SQUIDs for Memories.- 4.3 Circuits for Bit-Serial and Word-Serial CAMs.- 4.3.1 Semiconductor RAM Modules for the CAM.- 4.3.2 Magnetic Memory Implementations of the CAM.- 4.3.3 Shift Registers for Content-Addressable Memory.- 4.3.4 The Charge-Coupled Device (CCD).- 4.3.5 The Magnetic-Bubble Memory (MBM).- 4.4 Optical Content-Addressable Memories.- 4.4.1 Magneto-Optical Memories.- 4.4.2 Holographic Content-Addressable Memories.- 5 The CAM as a System Part.- 5.1 The CAM in Virtual Memory Systems.- 5.1.1 The Memory Hierarchy.- 5.1.2 The Concept of Virtual Memory and the Cache.- 5.1.3 Memory Mappings for the Cache.- 5.1.4 Replacement Algorithms.- 5.1.5 Updating of Multilevel Memories.- 5.1.6 Automatic Control of the Cache Operations.- 5.1.7 Buffering in a Multiprocessor System.- 5.1.8 Additional Literature on Memory Organizations and Their Evaluation.- 5.2 Utilization of the CAM in Dynamic Memory Allocation.- 5.2.1 Memory Map and Address Conversion.- 5.2.2 Loading of a Program Segment.- 5.3 Content-Addressable Buffer.- 5.4 Programmable Logic.- 5.4.1 RAM Implementation.- 5.4.2 CAM Implementation.- 5.4.3 FM Implementation.- 5.4.4 Other Implementations of Programmable Logic.- 5.4.5 Applications of the CAM in Various Control Operations.- 6 Content-Addressable Processors.- 6.1. Some Trends in Content-Addressable Memory Functions.- 6.2 Distributed-Logic Memories (DLMs).- 6.3 The Augmented Content-Addressable Memory (ACAM).- 6.4 The Association-Storing Processor (ASP).- 6.5 Content-Addressable Processors with High-Level Processing Elements.- 6.5.1 The Basic Array Processor Architecture.- 6.5.2 The Associative Control Switch (ACS) Architecture.- 6.5.3 An Example of Control-Addressable Array Processors: RADCAP.- 6.5.4 An Example of Content-Addressable Ensemble Processors: PEPE.- 6.6 Bit-Slice Content-Addressable Processors.- 6.6.1 The STARAN Computer.- 6.6.2 Orthogonal Computers.- 6.7 An Overview of Parallel Processors.- 6.7.1 Categorizations of Computer Architectures.- 6.7.2 Survey of Additional Literature on Content-Addressable and Parallel Processing.- 7 Review of Research Since 1979.- 7.1 Research on Hash Coding.- 7.1.1 Review Articles.- 7.1.2 Hashing Functions.- 7.1.3 Handling of Collisions.- 7.1.4 Hash Table Organization.- 7.1.5 Linear Hashing.- 7.1.6 Dynamic, Extendible, and External Hashing.- 7.1.7 Multiple-Key and Partial-Match Hashing.- 7.1.8 Hash-Coding Applications.- 7.1.9 Hash-Coding Hardware.- 7.2 CAM Hardware.- 7.2.1 CAM Cells.- 7.2.2 CAM Arrays.- 7.2.3 Dynamic Memories.- 7.2.4 CAM Systems.- 7.3 CAM Applications.- 7.4 Content-Addressable Parallel Processors.- 7.4.1 Architectures for Content-Addressable Processors.- 7.4.2 Data Base Machines.- 7.4.3 Applications of Content-Addressable Processors.- 7.5 Optical Associative Memories.- 7.5.1 General.- 7.5.2 Holographic Content-Addressable Memories.- References.