CSC 573:
Seminar on The Future of Parallelism

Technological advances have resulted in increasing levels of on-chip functionality. The emergence of multi-core architectures, along with the proliferation of simultaneous multithreaded and symmetric multiprocessors, is making the extraction of parallelism from mainstream applications imperative. Simultaneously, the abundance of compute devices and storage capacity, along with easy networked access, implies the ability to access large amounts of distributed information and compute capacity. There is a need to reexamine the fundamental ways in which future systems are designed and utilized in order to facilitate parallelism. This seminar will examine all aspects of parallel systems - architecture, application, run-time, and compiler issues. Potential topics include (but are not limited to): Hardware and software transactional memory; Chip multiprocessor architectures; Parallel/architecture-aware algorithm design; Grid computing; New computational paradigms such as Quantum and DNA computing.

Class time: 10 a.m.--- noon, Wednesdays.
Class location: CSB 632.

Instructor:

Sandhya Dwarkadas
e-mail: sandhya at cs
Office: CSB 717, 275-5647
Office hours by appointment, but don't be afraid to drop by. If you want to be sure I'm in my office, use e-mail to contact me.

Prerequisites:

CSC 2/458, CSC 254, and CSC 256, or equivalent and instructor's consent.

Assignments and Grading

The course will examine the latest papers in the chosen topics, and will consist of presentation and discussion of the papers. Grading will be based on class participation, class presentations, paper summaries, and a term project.

Paper Reading List

Chip Multiprocessors (25th January, 2006)

  • Piranha: A Scalable Architecture Based on Single-Chip Multiprocessing, L. A. Barroso, K. Gharachorloo, R. McNamara, A. Nowatzyk, S. Qadeer, B. Sano, S. Smith, R. Stets, and B. Verghese in Proceedings of the International Symposium on Computer Architecture (ISCA), pp. 282-293, June 2000.
  • The Stanford Hydra CMP, Lance Hammond, Ben Hubbert, Michael Siu, Manohar Prabhu, Mike Chen, and Kunle Olukotun, IEEE Micro, pp. 71-84, March-April 2000.
  • Niagara: A 32-Way Multithreaded SPARC Processor, Poonacha Kongetira, Kathirgamar Aingaran, and Kunle Olukotun, IEEE Micro, pp. 21-29, March-April 2005.

    Hardware Support for Transactional Memory (1st, 8th February)

  • Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution, R. Rajwar and J. R. Goodman, 34th International Symposium on Microarchitecture (MICRO), December 2001.
  • Transactional Memory Coherence and Consistency , L. Hammond, V. Wong, M. Chen, B. Hertzberg, B. Carlstrom, M. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun, Proceedings of the 31st Annual International Symposium on Computer Architecture, M√ľnchen, Germany, June 2004.
  • LogTM: Log-based Transactional Memory K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood, International Symposium on High Performance Computer Architecture (HPCA), February 2006.

    Software Transactional Memory (15th February)

  • A Qualitative Survey of Modern Software Transactional Memory Systems, V. J. Marathe and M. L. Scott. TR 839, Department of Computer Science, University of Rochester, June 2004.
  • Advanced contention management for dynamic software transactional memory, W. N. Scherer and M. L. Scott, ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, July 2005.
  • McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime, B. Saha, A-R. Adl-Tabatabai, R. L. Hudson, C. C. Minh, and B. Hertzberg, International Symposium on the Principles and Practice of Parallel Programming, March 2006.

    Hybrid Transactional Memory (22nd February)

  • Hybrid Transactional Memory, S. Kumar, M. Chu, C. Hughes, P. Kundu, and A. Nguyen, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), March 2006.
  • Hybrid Transactional Memory, M. Moir, Unpublished manuscript, July 2005.
  • Hardware Acceleration of Software Transactional Memory, A. Shriraman, V. Marathe, S. Dwarkadas, M.L. Scott, D. Eisenstat, C. Heriot, W. N. Scherer III, and M. F. Spear, TR 887, Department of Computer Science, University of Rochester, December 2005.

    Speculative and Dynamic Parallelization (1st March)

  • The Jrpm System for Dynamically Parallelizing Java Programs, M. Chen and K. Olukotun, in Proceedings of the 30th International Symposium on Computer Architecture (ISCA), San Diego, CA, June 2003.

    Memory Models (8th March)

  • The Java Memory Model, J. Manson, W. Pugh, and S. V. Adve, in Proceedings of the Symposium on Principles of Programming Languages (PoPL), January 2005.
  • Threads Cannot be Implemented as a Library , Hans-J. Boehm, in Proceedings of the Conference on Programming Language Design and Implementation (PLDI), June 2005.

    Spring Break (15th March)

    Parallel File Systems (22nd March)

  • GPFS: A Shared-Disk File System for Large Computing Clusters , F. Schmuck and R. Haskin, First USENIX Conference on File and Storage Technologies, January 2002.
  • The Google File System , S. Ghemawat, H. Gobioff, and S-T. Leung, in Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP), October 2003.

    Parallel I/O (29th March, 5th April)

  • On Implementing MPI-IO Portably and with High Performance , R. Thakur, W. Gropp, and E. Lusk, In Proc. of the 6th Workshop on I/O in Parallel and Distributed Systems, May 1999.
  • MPI-IO/GPFS, an Optimized Implementation of MPI-IO on top of GPFS, J.P. Prost, R. Treumann, R. Hedges, B. Jia, and A. Koniges, in Proceedings of SuperComputing'01, November 2001.
  • PVFS: A Parallel File System for Linux Clusters, P.H. Carns, W.B. Ligon III, R.B. Ross and R. Thakur, in Proceedings of the 4th Annual Linux Showcase and Conf., October 2000.
  • Providing Tunable Consistency for a Parallel File Store , M. Vilayannur, P. Nath, and A. Sivasubramaniam, In Proceedings of the 4th USENIX Conference on File and Storage Technologies, December 2005.

    DNA Computing (12th April)

  • Simulating Boolean Circuits on a DNA Computer, M. Ogihara and A. Ray, Algorithmica, pages 239-250, 1999.
  • Molecular Computation to Solutions to Combinatorial Problems, L. A. Adleman, Science, Vol. 266, pages 1021-1023, November 1994.
  • "DNA Solution of Hard Computational Problems", R. J. Lipton, Science, Vol. 268, , pages 542-545, April 1995.

    (More on) Memory Models (19th April, 2006)

  • Architectural Semantics for Practical Transactional Memory, A. McDonald, B. D. Carlstrom, J. Chung, C-C Minh, C. Kozyrakis, and K. Olukotun, in International Symposium on Computer Architecture (ISCA), June 2006.
  • Conditional Memory Ordering, C. Praun, T. Cain, J-d Choi, and K. Ryu, in International Symposium on Computer Architecture (ISCA), June 2006.

    Quantum Computing (3rd May, 2006)

  • A Practical Architecture for Reliable Quantum Computers, M. Oskin, F. T. Chong, and I. Chuang, IEEE Computer, January 2002.
  • Quantum Memory Hierarchies: Efficient Designs to Match Available Parallelism in Quantum Computing, D. D. Thaker, T. S. Metodi, A. Cross, I. L. Chuang and F. T. Chong, in International Symposium on Computer Architecture (ISCA-33), June 2006.