Parallel real-time garbage collection of multiple heaps in reconfigurable hardware

Abstract

Despite rapid increases in memory capacity, reconfigurable hardware is still programmed in a very low-level manner, generally without any dynamic allocation at all. This limits productivity especially as the larger chips encourage more and more complex designs to be attempted. Prior work has shown that it is possible to implement a realtime collector in hardware and achieve stall-free operation - but at the price of severe restrictions on object layouts. We present the first hardware garbage collector capable of collecting multiple inter-connected heaps, thereby allowing a rich set of object types. We show that for a modest additional cost in logic and memory, we can support multiple heaps at a clock frequency competitive with monolithic, fixed-layout heaps. We evaluate the hardware design by synthesizing it for a Xilinx FPGA and using co-simulation to measure the run-time behavior over a set of four benchmarks. Even at high allocation and mutation rates the collector is able to sustain stall-free (100% minimum mutator utilization) operation with up to 4 inter-connected heaps, while only requiring between 1.1 and 1.7 times the maximum live memory of the application.