McRT-Malloc: a scalable transactional memory allocator

ABSTRACT

Emerging multi-core processors promise to provide an exponentially increasing number of hardware threads with every generation. Applications will need to be highly concurrent to fullyuse the power of these processors. To enable maximum concurrency, libraries (such as malloc-free packages) would therefore need to use non-blocking algorithms. But lock-free algorithms are notoriously difficult to reason about and inappropriate for average programmers. Transactional memory promises to significantly ease concurrent programming for the average programmer. This paper describes a highly efficient non-blocking malloc/free algorithm that supports memory allocation and deallocation inside transactional code blocks. Thus this paper describes a memory allocator that is suitable for emerging multi-core applications, while supporting modern concurrency constructs.This paper makes several novel contributions. It is the first to integrate a software transactional memory system with a malloc/free based memory allocator. We present the first algorithm which ensures that space allocated in an aborted transaction is properly freed and does not lead to a space blowup. Unlike previous lock-free malloc packages, our algorithm avoids atomic operations on typical code paths, making our algorithm substantially more efficient.

REFERENCES

• 1: Allan, E., Chase, D., Luchango, V., Maessen, J., Ryu, S., Steele Jr., G., Tobin-Hochstadt, S. The Fortress language specification, version 0.618. Sun Microsystems Technical Report, April 2005.
• 2: Emery D. Berger , Kathryn S. McKinley , Robert D. Blumofe , Paul R. Wilson, Hoard: a scalable memory allocator for multithreaded applications, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.117-128, November 2000, Cambridge, Massachusetts, United States
• 3: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 4: Cray Inc. The Chapel language specification, version 0.4. Technical Report, Cray Inc. Feb 2005.
• 5: Ennals, R. Cache sensitive software transactional memory. Technical Report.
• 6: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 7: Michael Greenwald, Non-blocking Synchronization and System Design, Stanford University, Stanford, CA, 1999
• 8: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 9: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 10: Maurice Herlihy , Victor Luchangco , Mark Moir, The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures, Proceedings of the 16th International Conference on Distributed Computing, p.339-353, October 28-30, 2002
• 11: Maged M. Michael, Scalable lock-free dynamic memory allocation, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 12: Mark S. Johnstone , Paul R. Wilson, The memory fragmentation problem: solved?, Proceedings of the 1st international symposium on Memory management, p.26-36, October 17-19, 1998, Vancouver, British Columbia, Canada
• 13: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 14: Justin Rattner, Multi-Core to the Masses, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.3, September 17-21, 2005 [doi>10.1109/PACT.2005.31]
• 15: Virendra J. Marathe , William N. Scherer , Michael L. Scott, Design tradeoffs in modern software transactional memory systems, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-7, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066660]
• 16: Maged M. Michael, Safe memory reclamation for dynamic lock-free objects using atomic reads and writes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571829]
• 17: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123001]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Languages, Performance

Keywords:
memory management, runtimes, synchronization, transactional memory