A scalable mark-sweep garbage collector on large-scale shared-memory machines

ABSTRACT

This work describes implementation of a mark-sweep garbage collector (GC) for shared-memory machines and reports its performance. It is a simple ''parallel'' collector in which all processors cooperatively traverse objects in the global shared heap. The collector stops the application program during a collection and assumes a uniform access cost to all locations in the shared heap. Implementation is based on the Boehm-Demers-Weiser conservative GC (Boehm GC). Experiments have been done on Ultra Enterprise 10000 (Ultra Sparc processor 250 MHz, 64 processors). We wrote two applications, BH (an N-body problem solver) and CKY (a context free grammar parser) in a parallel extension to C++.Through the experiments, We observe that load balancing is the key to achieving scalability. A naive collector without load redistribution hardly exhibits speed-up (at most fourfold speed-up on 64 processors). Performance can be improved by dynamic load balancing, which exchanges objects to be scanned between processors, but we still observe that straightforward implementation severely limits performance. First, large objects become a source of significant load imbalance, because the unit of load redistribution is a single object. Performance is improved by splitting a large object into small pieces before pushing it onto the mark stack. Next, processors spend a significant amount of time uselessly because of serializing method for termination detection using a shared counter. This problem suddenly appeared on more than 32 processors. By implementing non-serializing method for termination detection, the idle time is eliminated and performance is improved. With all these careful implementation, we achieved average speed-up of 28.0 in BH and 28.6 in CKY on 64 processors.

REFERENCES

• 1: Josh Barnes and Piet Hut. A hirarchical O(N log N) force-calculation algorithm. Nature, 324:446-449, 1986.
• 2: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 4: Andrew A. Chien , Uday S. Reddy , John Plevyak , Julian Dolby, ICC++-AC++ Dialect for High Performance Parallel Computing, Proceedings of the Second JSSST International Symposium on Object Technologies for Advanced Software, p.76-95, March 11-15, 1996
• 5: David L. Detlefs. Concurrent garbage collection for C++. In Topics in Advanced Language Implementation, chapter 5, pages 101-134. The MIT Press, 1991.
• 6: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 7: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 8: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 9: M. P. Herlihy , J. E. B. Moss, Lock-Free Garbage Collection for Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.304-311, May 1992 [doi>10.1109/71.139204]
• 10: Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.73-82, May 19-22, 1993, San Diego, California, United States
• 11: Nobuyuki Ichiyoshi and Masao Morita. A shared-memory parallel extension of KLIC and its garbage collection. In Proceedings of FGCS '94 Workshop on Parallel Logic Programming, pages 113-126, 1994.
• 12: A. Imai , E. Tick, Evaluation of Parallel Copying Garbage Collection on a Shared-Memory Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1030-1040, September 1993 [doi>10.1109/71.243529]
• 13: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 14: Yoshikazu Kamoshida. HOCS: A C++ extension with parallel objects and multi-threading. February 1997. (senior thesis), The University of Tokyo.
• 15: J. S. Miller , B. S. Epstein, Garbage collection in MultiScheme, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.138-160, June 1990, Sendai, Japan
• 16: James O'Toole , Scott Nettles, Concurrent replicating garbage collection, Proceedings of the 1994 ACM conference on LISP and functional programming, p.34-42, June 27-29, 1994, Orlando, Florida, United States
• 17: Joseph P. Skudlarek, Remarks on A methodology for implementing highly concurrent data, ACM SIGPLAN Notices, v.29 n.12, p.87-93, Dec. 1994 [doi>10.1145/193209.193230]
• 18: Joseph P. Skudlarek, Notes on “A methodology for implementing highly concurrent data objects”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.45-46, Jan. 1995 [doi>10.1145/200994.200999]
• 19: Kenjiro Taura, Satoshi Matsuoka, and Akinori Yonezawa. ABCL/f: A future-based polymorphic typed concurrent object-oriented language - its design and implementation -. In number 18 in Dimacs Series in Discrete Mathematics and Theoretical Computer Science, pages 275-292. the DIMACS work shop on Specification of Algorithms, 1994.
• 20: Kenjiro Taura , Akinori Yonezawa, An effective garbage collection strategy for parallel programming languages on large scale distributed-memory machines, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.264-275, June 18-21, 1997, Las Vegas, Nevada, United States
• 21: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992

INDEX TERMS

Keywords:
dynamic load balancing, garbage collection, parallel algorithm, scalability, shared-memory machine