And then there were none: a stall-free real-time garbage collector for reconfigurable hardware
📜 Abstract
Researchers have developed a garbage collector synthesized directly to hardware, which is capable of collecting a heap of uniform objects completely concurrently. These uniform heaps are composed entirely of objects of a fixed shape where the size of the data fields and the location of pointers of each object are fixed. The stall-free collector can be used directly with programs hand-written in hardware description languages. It can also be part of a hardware 'runtime system' used by high-level language systems including dynamic memory allocation. Three collectors are compared in terms of memory usage, clock frequency, throughput, and application stalls, using an allocation-intensive application. The researchers also present analytic closed-form worst-case bounds for the minimum heap size required for 0-stall real-time behavior, which are empirically validated.
✨ Summary
The paper presents a complete garbage collector implemented directly in FPGA hardware rather than as a hardware-assisted software collector. Its concurrent snapshot-based design provides single-cycle heap access and eliminates collector-induced stalls for the mutator, yielding deterministic 100% mutator utilization for the supported uniform-object heap model. The implementation uses at most 1% of the logic resources of a high-end FPGA; experiments report real-time collection approximately 4%–17% slower than explicit malloc/free management with comparable energy consumption, while outperforming stop-the-world collection on the evaluated hardware workloads. The paper also derives and validates bounds on the minimum heap size required for stall-free operation. These results establish a hardware garbage-collection design point that trades generality of object layout for strong timing guarantees. The work was recognized as a SIGPLAN Research Highlight for presenting the first complete hardware garbage collector and for eliminating interference with the mutator. (research.google)
A direct follow-on publication by the same authors extended the approach from a single uniform heap to multiple interconnected heaps, relaxing the object-layout restrictions while retaining stall-free operation for up to four heaps in the reported evaluation. (eurekamag.com) Later work and surveys continue to cite the paper as an early reference point for hardware and near-memory garbage-collection designs; a patent on parallel hardware garbage collection explicitly describes its design as generalizing the paper’s fixed two-pointer-per-object system. (patents.justia.com)