A new approach to parallelising tracing algorithms

ABSTRACT

Tracing algorithms visit reachable nodes in a graph and are central to activities such as garbage collection, marshaling etc. Traditional sequential algorithms use a worklist, replacing a nodes with their unvisited children. Previous work on parallel tracing is processor-oriented in associating one worklist per processor: worklist insertion and removal requires no locking, and load balancing requires only occasional locking. However, since multiple queues may contain the same node, significant locking is necessary to avoid concurrent visits by competing processors.

This paper presents a memory-oriented solution: memory is partitioned into segments and each segment has its own worklist containing only nodes in that segment. At a given time at most one processor owns a given worklist. By arranging separate single-reader-single-writer forwarding queues to pass nodes from processor i to processor j we can process objects in an order that gives lock-free mainline code and improved locality of reference. This refactoring is analogous to the way in which a compiler changes an iteration space to eliminate data dependencies.

While it is clear that our solution can be more effective on NUMA systems and even necessary when processor-local memory may not be addressed from other processors, slightly surprisingly, it often gives significantly better speed-up on modern multi-cores architectures too. Using caches to hide memory latency loses much of its effectiveness when there is significant cross-processor memory contention or when locking is necessary.

REFERENCES

• 1: Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277678]
• 2: C. Attanasio, D. Bacon, A. Cocchi, and S. Smith. A Comparative Evaluation of Parallel Garbage Collectors. In LCPC, Springer Verlag, pages 177--192, 2001.
• 3: Giuseppe Attardi , Tito Flagella, A customisable memory management framework, Proceedings of the 6th conference on USENIX Sixth C++ Technical Conference, p.8-8, April 11-14, 1994, Cambridge, MA
• 4: H. G. Baker, ACTOR SYSTEMS FOR REAL-TIME COMPUTATION, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 5: Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005 [doi>10.1145/1108970.1108972]
• 6: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 7: Hans-J. Boehm, Reducing garbage collector cache misses, Proceedings of the 2nd international symposium on Memory management, p.59-64, October 15-16, 2000, Minneapolis, Minnesota, United States
• 8: 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]
• 9: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 10: Yannis Chicha and Stephen Watt. A Localised Tracing Scheme applied to Garbage Collection. In APLAS, LNCS 4279, 2006.
• 11: Alan Demers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 12: 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]
• 13: 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]
• 14: Christine H. Flood , David Detlefs , Nir Shavit , Xiaolan Zhang, Parallel garbage collection for shared memory multiprocessors, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.21-21, April 23-24, 2001, Monterey, California
• 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: Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 17: Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, ACM SIGPLAN Notices, v.28 n.7, p.73-82, July 1993
• 18: 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]
• 19: Intel. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3A: System Programming Guide. In http://www.intel.com/products/processor/manuals/index.htm, 2008.
• 20: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 21: Simon Marlow , Tim Harris , Roshan P. James , Simon Peyton Jones, Parallel generational-copying garbage collection with a block-structured heap, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375637]
• 22: Maged M. Michael , Martin T. Vechev , Vijay A. Saraswat, Idempotent work stealing, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
• 23: D. Plainfosse , M. Shapiro, Survey of Distributed Garbage Collection Techniques, University of Bologna, 1994
• 24: Yefim Shuf , Manish Gupta , Hubertus Franke , Andrew Appel , Jaswinder Pal Singh, Creating and preserving locality of java applications at allocation and garbage collection times, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 25: David Siegwart , Martin Hirzel, Improving locality with parallel hierarchical copying GC, Proceedings of the 5th international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada [doi>10.1145/1133956.1133964]
• 26: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
memory-centric tracing algorithm, parallel