Fast memory snapshot for concurrent programmingwithout synchronization

ABSTRACT

The industry-wide turn toward chip-multiprocessors (CMPs) provides an increasing amount of parallel resources for commodity systems. However, it is still difficult to harness the available parallelism in user applications and system software code.

We propose MShot, a hardware-assisted memory snapshot for concurrent programming without synchronization code. It supports atomic multi-word read operations on a large dataset. Since modern processors support atomic access only to a single word, programmers should add synchronization code to process a multiword dataset concurrently in multithreading environment. With snapshot, programmers read the dataset atomically and process the snapshot image without synchronization code. We implement MShot using hardware resources for transactional memory and reduce the storage overhead from 2.98% to 0.07%. To demonstrate the usefulness of fast snapshot, we use MShot to implement concurrent versions of garbage collection and call-path profiling. Without the need for synchronization code, MShot allows such system services to run in parallel with user applications on spare cores in CMP systems. As a result, the overhead of these services

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
• 2: James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93396]
• 3: Angelos Bilas , Jason Fritts , Jaswinder Pal Singh, Real-Time Parallel MPEG-2 Decoding in Software, Proceedings of the 11th International Symposium on Parallel Processing, p.197-203, April 01-05, 1997
• 4: Colin Blundell , Joe Devietti , E. Christopher Lewis , Milo M. K. Martin, Making the fast case common and the uncommon case simple in unbounded transactional memory, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
• 5: Nicholas S. Bowen , Dhiraj K. Pradhan, Processor and Memory-Based Checkpoint and Rollback Recovery, Computer, v.26 n.2, p.22-31, February 1993 [doi>10.1109/2.191981]
• 6: Richard P. Brent, Recent Progress and Prospects for Integer Factorisation Algorithms, Proceedings of the 6th Annual International Conference on Computing and Combinatorics, p.3-22, July 26-28, 2000
• 7: Chi Cao Minh , Martin Trautmann , JaeWoong Chung , Austen McDonald , Nathan Bronson , Jared Casper , Christos Kozyrakis , Kunle Olukotun, An effective hybrid transactional memory system with strong isolation guarantees, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 8: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 9: Weihaw Chuang , Satish Narayanasamy , Ganesh Venkatesh , Jack Sampson , Michael Van Biesbrouck , Gilles Pokam , Brad Calder , Osvaldo Colavin, Unbounded page-based transactional memory, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: J. Chung, H. Chafi, et al. The Common Case Transactional Behavior of Multithreaded Programs. In the Proc. of the 12th Intl. Conf. on High-Performance Computer Architecture, Feb. 2006.
• 11: Khuzaima Daudjee , Kenneth Salem, Lazy database replication with snapshot isolation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029879]
• 13: Nathan Froyd , John Mellor-Crummey , Rob Fowler, Low-overhead call path profiling of unmodified, optimized code, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088161]
• 14: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• 15: Rahul Garg , Vijay K. Garg , Yogish Sabharwal, Scalable algorithms for global snapshots in distributed systems, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183439]
• 16: http://www.gzip.org/.
• 17: L. Hammond, V. Wong, et al. Transactional Memory Coherence and Consistency. In the Proc. of the 31st Intl.
• 18: Henry C. Baker, Jr. , Carl Hewitt, The incremental garbage collection of processes, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.55-59, August 15-17, 1977
• 19: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 20: Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376810]
• 21: http://www-306.ibm.com/software/tivoli/products/storage-mgr/.
• 22: Prasad Jayanti, An optimal multi-writer snapshot algorithm, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060697]
• 23: Austen McDonald , JaeWoong Chung , Brian D. Carlstrom , Chi Cao Minh , Hassan Chafi , Christos Kozyrakis , Kunle Olukotun, Architectural Semantics for Practical Transactional Memory, Proceedings of the 33rd annual international symposium on Computer Architecture, p.53-65, June 17-21, 2006
• 24: K. E. Moore, J. Bobba, et al. LogTM: Log-Based Transactional Memory. In the Proc. of the 12th Intl. Conf. on High-Performance Computer Architecture, Feb. 2006.
• 25: Michelle J. Moravan , Jayaram Bobba , Kevin E. Moore , Luke Yen , Mark D. Hill , Ben Liblit , Michael M. Swift , David A. Wood, Supporting nested transactional memory in logTM, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 26: Tipp Moseley , Alex Shye , Vijay Janapa Reddi , Dirk Grunwald , Ramesh Peri, Shadow Profiling: Hiding Instrumentation Costs with Parallelism, Proceedings of the International Symposium on Code Generation and Optimization, p.198-208, March 11-14, 2007 [doi>10.1109/CGO.2007.35]
• 27: http://memprofiler.com/.
• 28: http://profiler.netbeans.org/.
• 29: http://nullwebmail.sourceforge.net/httpd/.
• 30: PowerPC Assembler Reference.
• 31: http://pypy.org/.
• 32: J. M. Smith and G. Q. Maguire, Jr. Effects of copy-on-write memory management on the response time of UNIX fork operations. Computing Systems, 1(3):255--278, 1988.
• 33: Livio B Soares , Orran Y Krieger , Dilma Da Silva, Meta-data snapshotting: a simple mechanism for file system consistency, Proceedings of the international workshop on Storage network architecture and parallel I/Os, p.41-52, September 28-28, 2003, New Orleans, Louisiana [doi>10.1145/1162618.1162624]
• 34: http://user-mode-linux.sourceforge.net/.
• 35: http://w3m.sourceforge.net/.
• 36: Carl A. Waldspurger, Memory resource management in VMware ESX server, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844146]
• 37: Steven Wallace , Kim Hazelwood, SuperPin: Parallelizing Dynamic Instrumentation for Real-Time Performance, Proceedings of the International Symposium on Code Generation and Optimization, p.209-220, March 11-14, 2007 [doi>10.1109/CGO.2007.37]
• 38: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 39: M. Wu and X.-F. Li. Task-pushing: a scalable parallel gc marking algorithm without synchronization operations. In IPDPS'07: Proc. of intl. Parallel and Distributed Processing Symposium, 2007.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.0 General

General Terms:
Design

Keywords:
snapshot, transactional memory