Designers and users of computer systems have long been aware of the fact that inclusion of some kind of content-addressable or "associative" functions in the storage and retrieval mechanisms would allow a more effective and straightforward organization of data than with the usual addressed memories, with the result that the computing power would be significantly increased. However, although the basic principles of content-addressing have been known for over twenty years, the hardware content-addressable memories (CAMs) have found their way only to special roles such as small buffer memories and con trol units. This situation now seems to be changing: Because of the develop ment of new technologies such as very-large-scale integration of semiconduc tor circuits, charge-coupled devices, magnetic-bubble memories, and certain devices based on quantum-mechanical effects, an increasing amount of active searching functions can be transferred to memory units. The prices of the more complex memory components which earlier were too high to allow the application of these principles to mass memories will be reduced to a fraction of the to tal system costs, and this will certainly have a significant impact on the new computer architectures. In order to advance the new memory principles and technologies, more in formation ought to be made accessible to a common user.
Reihe
Sprache
Verlagsort
Verlagsgruppe
Produkt-Hinweis
Fadenheftung
Gewebe-Einband
Gewicht
ISBN-13
978-3-540-09823-2 (9783540098232)
DOI
10.1007/978-3-642-96552-4
Schweitzer Klassifikation
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 Codi ng 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.- References.
