An Efficient Parallel Heap Compaction Algorithm
Meeting Rooms 1-3
Wednesday, 11:00, 30 minutes | 7 | · | 8 | · | 9 | · | 10 | · | 11 | · | 12 | · | 13 | · | 14 | · | 15 | · | 16 | · | 17 | · | 18 | · | 19 | · | 20 | · | 21 |
Diab Abuaiadh, IBM Haifa Research Lab
Yoav Ossia, IBM Haifa Research Lab
Erez Petrank, Technion, Israel Institute of Technology
Uri Silbershtein, IBM Haifa Research Lab
We propose a heap compaction algorithm appropriate for modern computing
environments. Our algorithm is targeted at SMP platforms. It demonstrates
high scalability when running in parallel but is also extremely efficient
when running single-threaded on a uniprocessor.
Instead of using the standard forwarding pointer mechanism for updating
pointers to moved objects, the algorithm saves information for a pack of
objects. It then does a small computation to process this information
and determine each object's new location.
In addition, using a smart parallel moving strategy, the algorithm achieves
(almost) perfect compaction in the lower addresses of the heap, whereas
previous algorithms achieved parallelism by compacting within several
predetermined segments.
Next, we investigate a method that trades compaction quality for a further
reduction in time and space overhead.
Finally, we propose a modern version of the two-finger compaction algorithm.
This algorithm fails, thus, re-validating traditional wisdom asserting that
retaining the order of live objects significantly improves the quality of
the compaction.
The parallel compaction algorithm was implemented on the IBM production
Java Virtual Machine. We provide measurements demonstrating high efficiency
and scalability. Subsequently, this algorithm has been incorporated into the
IBM production JVM.
|
