|
Instructor: |
Cristiana Amza |
|
Location: |
GB 220 |
|
Class time: |
Tuesday 3:00-5:00 PM |
|
Project List: |
|
|
Office Hours: |
Thursday (Sept 15) BA 4142 10:30 a.m. - 3:30 p.m. |
This course is an intermediate graduate course in the area of parallel
programming. In the first part of the course we will briefly introduce the
architecture of parallel systems and the concept of data dependencies/races.
The three most commonly used parallel programming paradigms (shared memory,
distributed memory and data parallel) will then
be examined in detail. An overview of automatic parallelization of programs and
the use of parallel processing in related domains such as parallel and
distributed database transaction processing will also be given.
In the second part of the course selected research topics will be examined.
This part of the course consists of student-lead discussions of relevant
research papers. A research-intensive group project in an area related to
program parallelization is a fundamental part of the course. The projects
can be done individually or in small teams of two or three people. The project
outcome will be presented in a class session at the end of the semester. A list
of suggested research projects has been posted (project_suggestions.txt).
Students are also encouraged to propose their own projects and discuss them
with me. Please also read:
Class Goals and
Advice from Instructor
There is no required textbook for the class. You should be fine with the lectures and papers posted on this site. However, here are some suggestions for additional reading:
Parallel Programming in C with MPI and OpenMP
by Michael
J. Quinn
Threads Primer: A Guide to Multithreaded Programming
by Bil Lewis, Daniel
J. Berg
Concurrency Control and Recovery in Database Systems
by Philip
A. Bernstein, Vassos
Hadzilacos, Nathan
Goodman (free on-line edition you can download from
http://research.microsoft.com/pubs/ccontrol/ in .pdf)
It would be good for you if you had basic understanding of operating system
principles, basic architecture and some knowledge of network programming. These
are not strict pre-requisites though, most of the
necessary material will be covered in class.
Sample project report: Link
to Sample Project Report.
Pthread program examples have been posted here: Code Examples. Please also consult this pthread How to use guide and this pthread reference manual
The first programming assignment is out: Assignment 1. Pthread program examples have been posted here: Code Examples. Please also consult this pthread How to use guide and this pthread reference manual
MPI program examples have been posted here: Code Examples. Please also consult this MPI How to use guide|
Date |
Topic |
|
Assignment |
Handouts |
|
|
Sep 13 |
Intro and project suggestion Slides-part1 Slides-part2 |
|
|
|
|
|
Sep 20 |
Parallel Programming and Optimizations Pthreads OpenMP Slides |
|
|
|
|
|
Sept 27 |
Parallel Programming and Optimizations Project ideas: TM/Games |
Ahmed Abdelkhalek and Angelos Bilas. Parallelization and performance of interactive multiplayer game servers. In Proc. of the 18th International Parallel and Distributed Processing Symposium (IPDPS 2004), April 2004 quake-parallel-ipdps04.pdf Colin Chung
|
Paper summaries |
|
|
|
Oct 4
|
Lock Synchronization and Optimization, Distributed Applications and Environments |
John M. Mellor-Crummey and
Michael L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors.
ACM Transactions on Computer Systems, 9 (1):21-65, February 1991. tocs91.pdf Michel Nacouzi and Thomas Lin Donnybrook: Enabling Large-Scale, High-Speed, Peer-to-peer Games. Ashwin Bharambe, John R. Douceur, Jacob R. Lorch, Thomas Moscibroda, Jeffrey Pang, Srinivasan Seshan, and Xinyu Zhuang, SIGCOMM, 2008. donnybrook.pdf Valentin Berbenetz DNA Polony Sequencing http://www.currentprotocols.com/protocol/mb0708 Francesco Iorio |
Paper summaries |
|
|
|
Oct 11 |
Software Distributed Shared Memory |
Informal oral project proposals. Kai Li, Paul Hudak Memory Coherence in Shared Virtual Memory Systems, 1991 ivy91.pdf Valmiki Rampersad John Carter, John Bennett, and Willy Zwaenepoel
Implementation and Performance of Munin munin91.pdf
Nozar Kianian-Fard A performance study of general-purpose applications on graphics processors using CUDA, Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W. Sheaffer, Kevin Skadron, JPDC, Volume 68, Issue 10, General-Purpose Processing sing Graphics Processing Units, October 2008. http://dx.doi.org/10.1016/j.jpdc.2008.05.014 and CUDA vs OpenCL Reza Mokhtari and Vlad Makalski |
Proposal & Paper summaries |
|
|
|
Oct 18 |
Software Distributed Shared Memory |
Informal oral project proposals (contd). TreadMarks: Distributed Shared Memory on
Standard Workstations and Operating Systems, P. Keleher,
A.L. Cox, S. Dwarkadas and OpenMP for Networks of SMPs,
Y.C. Hu, H. Lu, A.L. Cox, and W. Zwaenepoel, Journal of Parallel and Distributed
Computing, vol. 60 (12), pp. 1512-1530, December 2000 Fundamentals of Grid Computing, IBM http://www.redbooks.ibm.com/redpapers/pdfs/redp3613.pdf Allan Menezes Short Introduction to Event-Driven Servers by Instructor |
Proposal & Paper summaries |
|
|
|
Oct 25 |
Multithreading vs Event-Driven model for Server Code |
Flash: An Efficient and Portable Web Server, Vivek S. Pai, Peter Druschel, Willy Zwaenepoel, USENIX Annual Technical Conference, 1999. flash.pdf Sintugan Panchalingam and Yang Xinrui SEDA: An Architecture for Well-Conditioned,
Scalable Internet Services. Presented at the Eighteenth Symposium on
Operating Systems Principles (SOSP'01), Lazy Asynchronous I/O for Event Driven Servers. Khaled Elmeleegy, Anupam Chanda, Alan L. Cox and Willy Zwaenepoel, in Proceedings of the USENIX 2004 Annual Technical Conference. laio04.pdf John Matienzo |
Papers summaries |
|
|
|
Nov 1 |
Advanced Synchronization Mechanisms in Multiprocessor and Distributed Systems
|
Adaptive Overload Control for Busy Internet Servers, Matt Welsh and David Culler. In Proceedings of the 4th USENIX Conference on Internet Technologies and Systems (USITS'03), March 2003. seda-usits03.pdf Mani Golafra Code Transformations to Improve Memory Parallelism Vijay
S. Pai and Sarita Adve pai_micro99.pdf Cache-Conscious Concurrency Control of
Main-Memory Indexes on Shared-Memory Multiprocessor Systems |
Paper summaries |
|
|
|
Nov 8 |
Nonblocking Synchronization and TM vs Event-Driven model for Server Code |
Read Copy Update: Using Execution History to Solve Concurrency Problems. Mc Kenney P. and Slingwine J. rcu.pdf Maciej Makowski and Patrick Judd Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III: Software transactional memory for dynamic-sized data structures. PODC 2003 podc-moir.pdf Wilson To 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. PPoPP 2006 mcrt.pdf Ilian Tili |
Paper summaries |
|
|
|
Nov 15 |
Transactional Memory
|
Kaloian Manassiev, Madalin Mihailescu and Cristiana Amza.Exploiting Distributed Version Consistency in a Transactional Memory Cluster. PPoPP 2006 dtm.pdf Kuei (Jack) Sun STEPS Towards Cache-Resident Transaction Processing, Stavros
Harizopoulos and Anastassia
Ailamaki. Proceedings of the 30th International
Conference on Very Large Data Bases, |
Paper summaries |
|
|
|
Nov 22 |
Transactional Memory
|
Maged M. Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Transactions on Parallel and Distributed Systems 2004 hazard_pointers.pdf Steven Gurfinkel A Case for Staged Database Systems. Stavros Harizopoulos and Anastassia Ailamaki stages.pdf Richard Abrich |
Paper summaries |
|
|
|
Nov 29
|
Project class presentation
|
|
|
|
|
|
Dec 22 |
Final project report due |
||||