Distributed computing and the multicore revolution

ABSTRACT

Changes in technology can have far-reaching effects on theory. For example, while Turing's work on computability predated the first electronic computers, complexity theory flowered only after computers became a reality. After all, an algorithm's complexity may not matter much in a mathematics journal, but matters quite a bit in a FORTRAN program. We argue that something similar is going on with parallel and concurrent computation: after decades of being respected but not taken seriously, research on multiprocessor algorithms and data structures is going mainstream.

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: Marcos K. Aguilera , Svend Frolund , Vassos Hadzilacos , Stephanie L. Horn , Sam Toueg, Abortable and query-abortable objects and their efficient implementation, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281107]
• 3: Rajeev Alur , Gadi Taubenfeld, Contention-free complexity of shared memory algorithms, Information and Computation, v.126 n.1, p.62-73, April 10, 1996 [doi>10.1006/inco.1996.0034]
• 4: 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]
• 5: N. Arora, R. D. Blumofe, and C. Plaxton. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems, 34(2):115--144, 2001.
• 6: Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kouznetsov, Synchronizing without locks is inherently expensive, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146427]
• 7: L. Baugh and C. Zilles. An analysis of i/o and syscalls in critical sections and their implications for transactional memory. In Workshop on Transactional Computing (TRANSACT), 2007.
• 8: Ariel Cohen , John W. O'Leary , Amir Pnueli , Mark R. Tuttle , Lenore D. Zuck, Verifying Correctness of Transactional Memories, Proceedings of the Formal Methods in Computer Aided Design, p.37-44, November 11-14, 2007 [doi>10.1109/FMCAD.2007.39]
• 9: A. Cohen, A. Pnueli, and L. Zuck. Verification of transactional memories that support non-transactional memory accesses. In Workshop on Transactional Computing (TRANSACT), 2008.
• 10: R. Colvin, L. Groves, V. Luchangco, and M. Moir. Formal verification of a lazy concurrent list-based set. In Proceedings of Computer Aided Verification, 2006.
• 11: L. Crowl, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Integrating transactional memory into c++. In Workshop on Transactional Computing (TRANSACT), 2007.
• 12: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 13: Peter Damron , Alexandra Fedorova , Yossi Lev , Victor Luchangco , Mark Moir , Daniel Nussbaum, Hybrid 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
• 14: F. E. Fich, V. Luchangco, M. Moir, and N. Shavit. Obstruction-free step complexity: Lock-free DCAS as an example. In Proceedings of the 19th International Conference on Distributed Computing (DISC), pages 493--494, 2005.
• 15: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 16: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 17: Dan Grossman , Jeremy Manson , William Pugh, What do high-level memory models mean for transactions?, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California [doi>10.1145/1178597.1178609]
• 18: R. Guerraoui, M. Herlihy, M. Kapalka, and B. Pochon. Robust contention management in software transactional memory. In OOPSLA 2005 Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL), 2005.
• 19: R. Guerraoui, M. Herlihy, and B. Pochon. Toward a theory of transactional contention managers. In P. Fraigniaud, editor, Proceedings of the International Conference on Distributed Computing (DISC), volume 3724 of Lecture Notes in Computer Science. Springer, Sept. 2005.
• 20: R. Guerraoui, M. Kapalka, and J. Vitek. STMBench7: A benchmark for software transactional memory. Technical report, EPFL, 2006.
• 21: 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
• 22: Timothy L. Harris, A Pragmatic Implementation of Non-blocking Linked-Lists, Proceedings of the 15th International Conference on Distributed Computing, p.300-314, October 03-05, 2001
• 23: 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
• 24: 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]
• 25: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 26: Maurice Herlihy , Eric Koskinen, Transactional boosting: a methodology for highly-concurrent transactional objects, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345237]
• 27: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 28: 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]
• 29: 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
• 30: Amos Israeli , Lihu Rappoport, Disjoint-access-parallel implementations of strong shared memory primitives, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.151-160, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198079]
• 31: Y. Lev, M. Moir, and D. Nussbaum. PhTM: Phased transactional memory. In Workshop on Transactional Computing (TRANSACT), 2007.
• 32: Victor M. Luchangco , Nancy A. Lynch, Memory consistency models for high-performance distributed computing, Massachusetts Institute of Technology, 2001
• 33: V. Marathe, W. Scherer, and M. Scott. Adaptive software transactional memory. Technical Report TR 868, Computer Science Department, University of Rochester, May 2005.
• 34: Milo Martin , Colin Blundell , E. Lewis, Subtleties of Transactional Memory Atomicity Semantics, IEEE Computer Architecture Letters, v.5 n.2, p.17, July 2006 [doi>10.1109/L-CA.2006.18]
• 35: A. McDonald, J. Chung, B. Carlstrom, C. Minh, H. Chafi, C. Kozyrakis, and K. Olukotun. Architectural semantics for practical transactional memory, 2006.
• 36: Maged M. Michael , Michael L. Scott, Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors, Journal of Parallel and Distributed Computing, v.51 n.1, p.1-26, May 25, 1998 [doi>10.1006/jpdc.1998.1446]
• 37: Mark Moir, Practical implementations of non-blocking synchronization primitives, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.219-228, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259442]
• 38: Mark Moir , Daniel Nussbaum , Ori Shalev , Nir Shavit, Using elimination to implement scalable and lock-free FIFO queues, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074013]
• 39: K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based transactional memory. In Proc. 12th Annual International Symposium on High Performance Computer Architecture, 2006.
• 40: K. E. Moore, M. D. Hill, and D. A. Wood. Thread-level transactional memory. Technical Report CS-TR-2005-1524, Dept. of Computer Sciences, University of Wisconsin, Mar. 2005.
• 41: Katherine F. Moore , Dan Grossman, High-level small-step operational semantics for transactions, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 42: H. E. Ramadan, C. J. Rossbach, and E. Witchel. The Linux kernel: A challenging workload for transactional memory. In Workshop on Transactional Memory Workloads, June 2006.
• 43: 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]
• 44: M. L. Scott. Sequential specification of transactional memory semantics. In TRANSACT:First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006.
• 45: Ori Shalev , Nir Shavit, Split-ordered lists: Lock-free extensible hash tables, Journal of the ACM (JACM), v.53 n.3, p.379-405, May 2006 [doi>10.1145/1147954.1147958]
• 46: 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]
• 47: F. Tabba, C. Wang, J. R. Goodman, and M. Moir. NZTM: Nonblocking, zero-indirection transactional memory. In Workshop on Transactional Computing (TRANSACT), 2007.
• 48: Marc Tremblay, Transactional memory for a modern microprocessor, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, p.1-1, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281101]
• 49: M. Tremblay and S. Chaudhry. A third-generation 65nm 16-core 32-thread plus 32-scout-thread cmt sparc® processor. In Proceedings of the 2008 IEEE International Solid-State Circuits Conference, 2008.
• 50: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 51: E. Vallejo, T. Harris, A. Cristal, O. Unsal, and M. Valero. Hybrid transactional memory to accelerate safe lock-based transactions. In Workshop on Transactional Computing (TRANSACT), 2008.
• 52: H. Volos, N. Goyal, and M. Swift. Pathological interaction of locks with transactional memory. In Workshop on Transactional Computing (TRANSACT), 2008.
• 53: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 54: C. Zilles and L. Baugh. Extending hardware transactional memory to support non-busy waiting and non-transactional actions. In TRANSACT:First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Languages, Theory