A systolic associative lisp computer architecture with incremental parallel storage management
John T. O’Donnell · 1981
This thesis presents an associative computer architecture for LISP which is suitable for VLSI implementation. The system supports compact list representation and parallel storage management through an incremental reference count algorithm. The architecture contains an Interpreter and a Manager running in separate processors, and an associative Memory Sytem which can shift stored information and which supports list structure operations. Each storage cell in the Memory System is an active functional unit with communication paths to its neighboring cells and to a tree network connecting all the cells to the Controller. The processors issue instructions to the Memory System. Instruction execution occurs in two phases. In the first phase the Controller routes the instruction issued by one of the processors into the Memory System tree network, which broadcasts the instruction to the storage cells and performs some instruction processing. In the second phase the cells execute the instruction and the tree network returns a response to the Controller, which routes it to the processor that issued the instruction. During each system cycle one of the processors is in the first phase of an instruction execution and the other processor is in the second phase. On the next cycle the processors switch phases. The Memory System always executes one instruction phase for each processor during each cycle. The tree network provides communications among the Memory System cells, allowing associative searching in blocks of cells. This facility provides fast implementation of an association list for LAMBDA bindings and property list searching. Simulation of the architecture shows that its Manager, executing an incremental algorithm in parallel with the Interpreter, reclaims garbage as fast as the Interpreter abandons it. Consequently the system could be used in real time applications. The system performance does not degrade until only a few available cells are left. The associative architecture implements the deep binding association lists of LISP 1.5 with fast constant time access.