Programming with transactional coherence and consistency (TCC)

ABSTRACT

Transactional Coherence and Consistency (TCC) offers a way to simplify parallel programming by executing all code within transactions. In TCC systems, transactions serve as the fundamental unit of parallel work, communication and coherence. As each transaction completes, it writes all of its newly produced state to shared memory atomically, while restarting other processors that have speculatively read stale data. With this mechanism, a TCC-based system automatically handles data synchronization correctly, without programmer intervention. To gain the benefits of TCC, programs must be decomposed into transactions. We describe two basic programming language constructs for decomposing programs into transactions, a loop conversion syntax and a general transaction-forking mechanism. With these constructs, writing correct parallel programs requires only small, incremental changes to correct sequential programs. The performance of these programs may then easily be optimized, based on feedback from real program execution, using a few simple techniques.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 2: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 3: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 4: 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
• 5: Broadcom Corp., "The Broadcom BCM-1250 Multiprocessor," Presentation at 2002 Embedded Processor Forum, April 2002.
• 6: Byte Magazine, jBYTEmark Benchmark, http://www.byte.com, CMP Media LLC, 1999.
• 7: Michael K. Chen , Kunle Olukotun, The Jrpm system for dynamically parallelizing Java programs, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 8: Michel Dubois , Jin Chin Wang , Luiz A. Barroso , Kangwoo Lee , Yung-Syau Chen, Delayed consistency and its effects on the miss rate of parallel programs, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.197-206, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125941]
• 9: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 10: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
• 11: Lance Hammond , Benedict A. Hubbert , Michael Siu , Manohar K. Prabhu , Michael Chen , Kunle Olukotun, The Stanford Hydra CMP, IEEE Micro, v.20 n.2, p.71-84, March 2000 [doi>10.1109/40.848474]
• 12: 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
• 13: 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
• 14: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 15: 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
• 16: IBM Corporation, Encina Transactional-C Programmer's Guide and Reference for AIX, SC23-2465-02, 1994.
• 17: Java Grande Forum, Java Grande Benchmark Suite, http://www.epcc.ed.ac.uk/javagrande/, 2000.
• 18: R. Kalla, B. Sinharoy, and J. Tendler, "Simultaneous Multi-threading Implementation in POWER5," Conference Record of Hot Chips 15 Symposium, Palo Alto, CA, August 2003.
• 19: P. Keleher, A. L. Cox, and W. Zwaenepoel, "Lazy Release Consistency for Software Distributed Shared Memory," Proceedings of the Fifth International Symposium on High-Performance Computer Architecture, pp. 279--283, Orlando, FL, 1999.
• 20: Tom Knight, An architecture for mostly functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.105-112, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319854]
• 21: Leonidas I. Kontothanassis , Michael L. Scott , Ricardo Bianchini, Lazy release consistency for hardware-coherent multiprocessors, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.61-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224398]
• 22: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 23: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 24: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 25: Bil Lewis , Daniel J. Berg, Multithreaded programming with Pthreads, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 26: José F. Martínez , Josep Torrellas, Speculative synchronization: applying thread-level speculation to explicitly parallel applications, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 27: Kunle Olukotun , Lance Hammond , Mark Willey, Improving the performance of speculatively parallel applications on the Hydra CMP, Proceedings of the 13th international conference on Supercomputing, p.21-30, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305155]
• 28: Jeffrey Oplinger , Monica S. Lam, Enhancing software reliability with speculative threads, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 29: Manohar K. Prabhu , Kunle Olukotun, Using thread-level speculation to simplify manual parallelization, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 30: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 31: R. Raman, "UltraSparc Gemini: Dual CPU Processor," Conference Record of Hot Chips 15 Symposium, Palo Alto, CA, August 2003.
• 32: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 33: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 34: Standard Performance Evaluation Corporation, SPECjbb2000 v1.01, http://www.spec.org/jbb2000/, Warrenton, VA, 2000.
• 35: Standard Performance Evaluation Corporation, SPEC*, http://www.specbench.org/, Warrenton, VA, 1995-2000.
• 36: J. Steffan , T Mowry, The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.2, January 31-February 04, 1998
• 37: T. N. Vijaykumar , Gurindar S. Sohi, Task selection for a multiscalar processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.81-92, November 1998, Dallas, Texas, United States
• 38: T. Wilkinson, Kaffe Virtual Machine, http://kaffe.org, 1997-2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.0 General

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

Keywords:
feedback optimization, multiprocessor architecture, transactions