Parallel garbage collection implemented in hardware

摘要

Embodiments of the invention provide a method and system for dynamic memory management implemented in hardware. In an embodiment, the method comprises storing objects in a plurality of heaps, and operating a hardware garbage collector to free heap space. The hardware garbage collector traverses the heaps and marks selected objects, uses the marks to identify a plurality of the objects, and frees the identified objects. In an embodiment, the method comprises storing objects in a heap, each of at least some of the objects including a multitude of pointers; and operating a hardware garbage collector to free heap space. The hardware garbage collector traverses the heap, using the pointers of some of the objects to identify others of the objects; processes the objects to mark selected objects; and uses the marks to identify a group of the objects, and frees the identified objects.

主权项

1. A method for dynamic memory management implemented in hardware, the method comprising:
storing objects in a plurality of heaps; and operating a hardware garbage collector to free heap space occupied by specified ones of the objects, including: traversing the plurality of the heaps and marking selected ones of the objects of the heaps based on given criteria; and using said marks to identify a plurality of the objects, and freeing the identified plurality of objects; wherein: at least some of the objects include pointers that reference others of the objects; the pointers of objects in each of the heaps include local pointers and foreign pointers; the local pointers of each of the heaps point to objects stored in the each heap; the foreign pointers of each of the heaps point to objects stored in others of the heaps; each of the single heap mark engines includes a foreign barrier queue for storing the foreign pointers of the one of the heaps that is traversed by the each mark engine, and the each of the mark engines puts the foreign pointers in and removes the foreign pointers from the foreign barrier queue of the each mark engine for processing by others of the mark engines; using the hardware garbage collector further includes implementing a termination protocol to terminate a mark phase of the garbage collector; and the implementing a termination protocol includes: the mark engine of each of the heaps, under defined conditions, asserting a ready to terminate signal to a termination engine; the termination engine, upon receiving the ready to terminate signals from all the mark engines, broadcasting a start termination signal to all the mark engines; each of the mark engines, upon receiving the start termination signal, recording an occupancy of the foreign barrier queue of the each mark engine into a termination counter; in each of the mark engines, decrementing the termination counter of the each mark engine whenever a pointer is removed from the foreign barrier queue of the each mark engine; each of the mark engines asserting a foreign barrier complete signal to the termination engine when the termination counter of the each mark engine reaches zero; the termination engine initializing a countdown timer to a predetermined value upon receiving the foreign barrier complete signals from all the mark engines; aborting the termination protocol if any of the mark engines encounters an unmarked object during the termination protocol; and declaring the termination protocol complete if the countdown timer reaches 0.