A boolean content addressable memory and its applications (tagged architecture, graph traversal, garbage collection)
Heonshik Shin · 1985
This dissertation presents a Boolean content addressable memory and its applications to graph traversals and garbage collection in list processing systems. An associative tag is a tag which consists of a small number of content-addressable tag bits. It can identify an address based on its content in addition to read and write operations. This tag can be used as an efficient working space for memory management. The Boolean content addressable memory (BCAM) is a one-bit wide CAM with which address encoding logic is incorporated on a chip. Since it is I/O compatible with the bit RAM, BCAMs can be effectively implemented as a tag in the primary memory to embody the associative tag. First, a memory with associative tag is applied to graph traversal problems. In a pseudo-random search, a visit is made to any one of the vertices which are queued for a future visit. Also, a breadth-first search can be formulated using such a tagged memory. These search algorithms require no extra space for a queue or stack without degrading the performance. Next, an algorithm for concurrent garbage collection is developed using the memory with associative tag which is used to indicate whether the corresponding element is free for allocation, marked as an active node, or queued for marking. The correctness of the algorithm is proved. Important performance improvements include no need for the free list for memory allocation and fast marking without a stack or the critical section. Last, the associative tag is applied to parallel garbage collection systems where each processor with a garbage collection process assigned has exclusive access to a block of memory. Performance analysis shows that the parallel memory with associative tag provides the parallel garbage collection with substantial advantage over other types of memories.