Content-Addressable Memory: Applications, Algorithms, and Simulation

摘要

An number of algorithms supporting artificial intelligence (AI), database management, and pattern recognition have been developed at the Air Force Institute of Technology (AFIT). These algorithms exploit an innovative peripheral-memory architecture, also developed at AFIT, which uses content-addressable memory (CAM). Algorithms for LISP garbage collection, database searching, and pattern recognition have been developed. This thesis analyzes the algorithms and the supporting CAM hardware using both computer simulation (N.2 and VHDL) as well as mathematical models of algorithmic complexity. Included in this study are CAM algorithms for performing: (1) real-time LISP garbage collection in a virtual memory environment and (2) associatively searching through a database whose records are many times longer than the CAM's basic word size. In contrast to classical garbage-collection algorithms, the algorithm described in this thesis reclaims storage in real time. Program interruptions are limited to 1/100th of a second for memory utilizations beyond 99% in a 100 Megaword address space. The simple expedience of a free-page table extends this utilization limit to 100%. Unlike previous CAM-based schemes, the new algorithm operates in a virtual memory environment and requires much less total CAM. For databases searches, it is shown that, by avoiding indices, the higher cost of CAM is offset by decreased memory needs. The AFIT CAM is shown to be more flexible than previous CAMs in adapting to different database records widths.