Due to continual progress in the large-scale integration of semiconductor circuits, parallel computing principles can already be met in low-cost sys tems: numerous examples exist in image processing, for which special hard ware is implementable with quite modest resources even by nonprofessional designers. Principles of content addressing, if thoroughly understood, can thereby be applied effectively using standard components. On the other hand, mass storage based on associative principles still exists only in the long term plans of computer technologists. This situation is somewhat confused by the fact that certain expectations are held for the development of new storage media such as optical memories and "spin glasses" (metal alloys with low-density magnetic impurities). Their technologies, however, may not ripen until after "fifth generation" computers have been built. It seems that software methods for content addressing, especially those based on hash coding principles, are still holding their position firmly, and a few innovations have been developed recently. As they need no special hardware, one might expect that they will spread to a wide circle of users. This monograph is based on an extensive literature survey, most of which was published in the First Edition. I have added Chap. ?, which contains a review of more recent work. This updated book now has references to over 1200 original publications. In the editing of the new material, I received valuable help from Anneli HeimbUrger, M. Sc. , and Mrs. Leila Koivisto.
Reihe
Auflage
Sprache
Verlagsort
Verlagsgruppe
Illustrationen
2
2 s/w Abbildungen
XIII, 388 p. 2 illus.
ISBN-13
978-3-642-83056-3 (9783642830563)
DOI
10.1007/978-3-642-83056-3
Schweitzer Klassifikation
1 Associative Memory, Content Addressing, and Associative Recall.- 1.1 Introduction.- 1.2 The Two Basic Implementations of Content Addressing.- 1.3 Associations.- 1.4 Associative Recall: Extensions of Concepts.- 2 Content Addressing by Software.- 2.1 Hash Coding and Formatted Data Structures.- 2.2 Hashing Functions.- 2.3 Handling of Collisions.- 2.4 Organizational Features and Formats of Hash Tables.- 2.5 Evaluation of Different Schemes in Hash Coding.- 2.6 Multi-Key Search.- 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.4 The Word-Parallel, Bit-Serial CAM.- 3.5 The Word-Serial, Bit-Parallel CAM.- 3.6 Byte-Serial Content-Addressable Search.- 3.7 Functional Memories.- 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.3 Circuits for Bit-Serial and Word-Serial CAMs.- 4.4 Optical Content-Addressable Memories.- 5 The CAM as a System Part.- 5.1 The CAM in Virtual Memory Systems.- 5.2 Utilization of the CAM in Dynamic Memory Allocation.- 5.3 Content-Addressable Buffer.- 5.4 Programmable Logic.- 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.6 Bit-Slice Content-Addressable Processors.- 6.7 An Overview ofParallel Processors.- 7 Review of Research Since 1979.- 7.1 Research on Hash Coding.- 7.2 CAM Hardware.- 7.3 CAM Applications.- 7.4 Content-Addressable Parallel Processors.- 7.5 Optical Associative Memories.- References.
