GC/VLSI

A hardware storage reclamation process derived using the DDD transformation system. The design specification is taken from Clinger's Scheme311 implementation

purpose: research
dates: 1989
students: C. David Boyer, Bhaskar Bose
engineering: Robert W. Wehrmeister
faculty: Steve Johnson
information: [Boyer-Johnson-89]

This photomicrograph shows a VLSI realization of the stop-and-copy garbage collector first prototyped in PLD technology. This chip was fabricated around 1989. The implementation was derived using the DDD transformation system, starting with a high-level description of the algorithm. The target technology is programmed logic arrays (PLAs), synthesized from boolean sum-of-products expressions using the Octtools tool set from the University of California at Berkeley.

The device is not a full garbage collector. It contains 8 "tag" bits and 8 "data" bits of a data for a word in the memory. Three of these chips are used in combination to collect a heap of 32-bit words (8 tag-bits ane 24 data-bits). The chip failed in testing, due to a "design execution" error, not a design error. Specifically, a number of p-wells were missing or misaligned, due to a problem in the CAD tool set, (a problem that was known at Berkeley but not well documented at the time).