Unbounded page-based transactional memory

ABSTRACT

Exploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are desirable, as they can increase the scope of transactions' use, and thereby further simplify a programmer's job. However, hardware support is essential to support efficient execution of unbounded transactions. In this paper, we introduce Page-based Transactional Memory to support unbounded transactions. We combine transaction bookkeeping with the virtual memory system to support fast transaction conflict detection, commit, abort, and to maintain transactions' speculative data.

REFERENCES

• 1: C. Scott Ananian , Krste Asanovic , Bradley C. Kuszmaul , Charles E. Leiserson , Sean Lie, Unbounded Transactional Memory, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.316-327, February 12-16, 2005 [doi>10.1109/HPCA.2005.41]
• 2: Albert Chang , Mark F. Mergen, 801 storage: architecture and programming, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.28-50, Feb. 1988 [doi>10.1145/35037.42270]
• 3: J. Chung, H. Chafi, C.C. Minh, A. McDonald, B.D. Carlstrom, C. Kozyrakis, and K. Olukotun. The common case transactional behavior of multithreaded programs. In HPCA '06: Proceedings of the 12th International Symposium on High-Performance Computer Architecture, Washington, DC, USA, 2006. IEEE Computer Society.
• 4: Czarek Dubnicki , Thomas J. LeBlanc, Adjustable block size coherent caches, Proceedings of the 19th annual international symposium on Computer architecture, p.170-180, May 19-21, 1992, Queensland, Australia
• 5: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 6: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Michael Chen , Christos Kozyrakis , Kunle Olukotun, Transactional Coherence and Consistency: Simplifying Parallel Hardware and Software, IEEE Micro, v.24 n.6, p.92-103, November 2004 [doi>10.1109/MM.2004.91]
• 7: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 8: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, ACM SIGOPS Operating Systems Review, v.32 n.5, p.58-69, Dec. 1998
• 9: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 10: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 11: 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
• 12: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 13: Austen McDonald , JaeWoong Chung , Hassan Chafi , Chi Cao Minh , Brian D. Carlstrom , Lance Hammond , Christos Kozyrakis , Kunle Olukotun, Characterization of TCC on Chip-Multiprocessors, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.63-74, September 17-21, 2005 [doi>10.1109/PACT.2005.11]
• 14: K.E. Moore, J. Bobba, M.J. Moravan, M.D. Hill, and D.A. Wood. Logtm: Log-based transactional memory. In HPCA '06: Proceedings of the 12th International Symposium on High-Performance Computer Architecture, Washington, DC, USA, 2006. IEEE Computer Society.
• 15: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, ACM SIGARCH Computer Architecture News, v.33 n.2, p.494-505, May 2005
• 16: J. Torrellas , H. S. Lam , J. L. Hennessy, False Sharing and Spatial Locality in Multiprocessor Caches, IEEE Transactions on Computers, v.43 n.6, p.651-663, June 1994 [doi>10.1109/12.286299]
• 17: 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
• 18: C. Zilles and L. Baugh. Extending hardware transactional memory to support non-busy waiting and nontransactional actions. In TRANSACT: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Languages, Performance

Keywords:
concurrency, parallel programming, transactional memory, transactions, virtual memory