On bounding time and space for multiprocessor garbage collection

ABSTRACT

This paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. The algorithm is a real-time shared-memory copying collector. We prove that the algorithm requires at most 2(R(l + 2/k) + N + 5PD) memory locations, where P is the number of processors, R is the maximum reachable space during a computation (number of locations accessible from the root set), N is the maximum number of reachable objects, D is the maximum depth of any data object, and k is a parameter specifying how many locations are copied each time a location is allocated. Furthermore we show that client threads are never stopped for more than time proportional to k non-blocking machine instructions. The bounds are guaranteed even with arbitrary length arrays. The collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.

REFERENCES

• 1: S. Abraham and J. Patel. Parallel garbage collection on a virtual memory system. In E. Chiricozzi and A. D'Amato, editors, International Conference on Parallel Processing and Applications, pages 243-246, L'Aquila, Italy, Sept. 1987. Elsevier- North Holland.
• 2: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, ACM SIGPLAN Notices, v.23 n.7, p.11-20, July 1988
• 3: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 4: Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.213-225, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 5: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 6: Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.162-173, June 17-19, 1998, Montreal, Quebec, Canada
• 7: Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988 [doi>10.1145/48529.48536]
• 8: J. Crammond, A garbage collection algorithm for shared memory parallel processors, International Journal of Parallel Programming, v.17 n.6, p.497-522, Dec. 1989 [doi>10.1007/BF01407816]
• 9: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , Carel S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Language Hierarchies and Interfaces, International Summer School, p.43-56, July 23-August 02, 1975
• 10: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 11: Toshio Endo , Kenjiro Taura , Akinori Yonezawa, A scalable mark-sweep garbage collector on large-scale shared-memory machines, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509641]
• 12: Ian Foster, A multicomputer garbage collector for a single-assignment language, International Journal of Parallel Programming, v.18 n.3, p.181-203, Jun. 1990 [doi>10.1007/BF01407898]
• 13: A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir. The NYU Ultracomputer--designing a MIMD, sharedmemory parallel machine. IEEE Transactions on uompu{er8, t O-l~U,
• 14: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 15: 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]
• 16: 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]
• 17: 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
• 18: C. R. Inc. Cray T3D: Technical summary, Sept. 1993.
• 19: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 20: D. J. Kuck, E. S. Davidson, D. H. Lawrie, and A.H. samesh. Parallel supercomputing today and the Cedar approach. Science, pages 967-974, Feb. 1986.
• 21: L. Lamport uigiu iboiu ibgoui ivbgiooiuoi puter that correctly executes multiprocess programs. IEEE Transactions on Computers, C- 28(9):690-691, Sept. 1979.
• 22: R. D. Lins. A shared memory architecture for parallel cyclic reference counting. Microprocessing and Microprogmmming, 34:31-35, Sept. 1991.
• 23: Steven S. Lumetta , Alan M. Mainwaring , David E. Culler, Multi-protocol active messages on a cluster of SMP's, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-22, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509596]
• 24: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 25: Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
• 26: 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
• 27: G. F. Pfister, W. C. Brantley, D. A. George, S. L. Harvey opl{;k{p p;j{po oihoi uijkgui iugiu iugiu Melton vfyuf hgcytd fxrdx fxrdukyfiuhg iguiob Melton, V. A. Norton, and J. Weiss. The IBM Research parallel processorprototype (RP3). Introduction and architecture. In Proceedings International Conference on Parallel Processing, pages 764-771, Aug. 1985.
• 28: A. G. Ranade. How to emulate shared memory. In Proceedings Symposium on Foundations of Computer Science, pages 185-194, 1987.
• 29: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 30: 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
• 31: Thinking Machines Corporation. Model CM-2 technical summary. Technical Report HA87-4, Thinking Machines Corporation, Cambridge, Massachusetts, Apr. 1987.
• 32: M. Wallace and C. Runeiman. An incremental garbage collector for embedded real-time systems. in Proceedings of the Chaimers Winter Meeting, pages 273-288, Tanum Strand, Sweden, 1993. 1" UUII~II~U i/~ I- I*U{I-~UIZUUl{ L~1~bUUUUIU~ ~jrLuu. lJ~ Chalmers University of Technology, Technical Report 73:
• 33: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Algorithms, Design, Performance, Reliability, Theory, Verification