Perry Cheng
Guy E. Blelloch
ABSTRACT
We describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. The collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. However, since our earlier algorithm was designed for simple analysis, it had some impractical features. This paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on a Sun Enterprise 10000, a 64-way UltraSparc-II multiprocessor. To the best of our knowledge, this is the first implementation of a parallel, real-time garbage collector.
The average collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. Maximum pause times range from 3 ms to 5 ms. In contrast, a non-incremental collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. Since the collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.
- 1.Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978. Also AI Laboratory Working Paper 139, 1977. Google Scholar
Digital Library
- 2.Guy E. Blelloch and Perry Cheng. On bounding time and space for multiprocessor garbage collection. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, ACM SIGPLAN Notices, pages 104-117, Atlanta, May 99. ACM Press. Google ScholarDigital Library
- 3.Guy E. Blelloch, Perry Cheng, and Phil Gibbons. Room synchronizations. In ACM Symposium on Parallel Algorithms and Architecture. ACM Press, July 2001. Google ScholarDigital Library
- 4.C. J. Cheney. A non-recursive list compacting algorithm. Communications of the ACM, 13(11):677-8, November 1970. Google ScholarDigital Library
- 5.Perry Cheng. Scalable Real-time Parallel Garbage Collection for Symmetric Multiprocessors. PhD thesis, Carnegie Mellon University, 2001. Google ScholarDigital Library
- 6.Perry Cheng, Robert Harper, and Peter Lee. Generational stack collection and profile-driven pretenuring. In Proc. ACM SIGPLAN Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Montreal, June 1998. ACM Press. Google ScholarDigital Library
- 7.Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. In Lecture Notes in Computer Science, No. 46. Springer-Verlag, New York, 1976. Google ScholarDigital Library
- 8.Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):965-975, November 1978. Google ScholarDigital Library
- 9.Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Proc. ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, January 1994. Google ScholarDigital Library
- 10.Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Proc. ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, pages 113-123. ACM Press, January 1993. Google ScholarDigital Library
- 11.Tamar Domani, Elliot Kolodner, and Erez Petrank. A generational on-the-fly garbage collector for Java. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, pages 274-284, May 2000. Google ScholarDigital Library
- 12.Toshio Endo. A scalable mark-sweep garbage collector on large-scale shared-memory machines. Master's thesis, University ofTokyo, February 1998.Google Scholar
- 13.Steven L. Engelstad and James E. Vandendorpe. Automatic storage management for systems with real time constraints. In Paul R. Wilson and Barry Hayes, editors, OOPSLA/ECOOP '91 Workshop on Garbage Collection in Object-Oriented Systems, Addendum to OOPSLA'91 Proceedings, October 1991. Google ScholarDigital Library
- 14.Robert R. Fenichel and Jerome C. Yochelson. A Lisp garbage collector for virtual memory computer systems. Communications of the ACM, 12(11):611-612, November 1969. Google ScholarDigital Library
- 15.Christine Flood, Dave Detlefs, Nir Shavit, and Catherine Zhang. Parallel garbage collection for shared memory multiprocessors. In Proc. USENIX JVM Conference, April 2001. Google ScholarDigital Library
- 16.Seth Goldstein. Lazy Threads: Compiler and Runtime Structures for Fine-Grained Parallel Programming. PhD thesis, University of California at Berkeley, Fall 1997. Google ScholarDigital Library
- 17.A. Gottlieb, B. D. Lubachevsky, and L. Rudolph. Basic techniques for the efficient coordination of very large numbers of cooperating sequqnetial processors. ACM Trans. on Programming Languages and Systems, 5(2):164-189, April 1983. Google ScholarDigital Library
- 18.Robert H. Halstead. Multilisp: A language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7(4):501-538, October 1985. Google ScholarDigital Library
- 19.Maurice Herlihy and J. Eliot B Moss. Lock-free garbage collection for multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 3(3), May 1992. Google ScholarDigital Library
- 20.Martin Larose and Marc Feeley. A compacting incremental collector and its performance in a production quality compiler. In Richard Jones, editor, Proc. International Symp. on Memory Management, volume 34(3) of ACM SIGPLAN Notices, pages 1-9, Vancouver, October 1998. ACM Press. Google ScholarDigital Library
- 21.John McCarthy. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3:184-195, 1960. Google ScholarDigital Library
- 22.Scott M. Nettles and James W. O'Toole. Real-time replication-based garbage collection. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, volume 28(6) of ACM SIGPLAN Notices. ACM Press. June 1993. Google ScholarDigital Library
- 23.Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975. Google ScholarDigital Library
- 24.Tarditi, Morrisett, Cheng, Stone, Harper, and Lee. TIL: A type-directed optimizing compiler for ML. In Proc. ACM SIGPLAN Conference onProgramming Languages Design and Implementation, pages 181-192, 1996. Google ScholarDigital Library
- 25.David M. Ungar and David A. Patterson. Berkeley Smalltalk: Who knows where the time goes? In Glenn Krasner, editor, Smalltalk-80: Bits of History, Words of Advice, pages 189-206. Addison-Wesley, 1983.Google Scholar
Index Terms
- A parallel, real-time garbage collector
Recommendations
A parallel, real-time garbage collector
We describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. The collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationAn on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Concurrent, parallel, real-time garbage-collection
ISMM '10With the current developments in CPU implementations, it becomes obvious that ever more parallel multicore systems will be used even in embedded controllers that require real-time guarantees. When garbage collection is used in these systems, parallel ...
Comments