|
Instructor: |
Cristiana Amza |
|
Location: |
BA 4164 |
|
Class time: |
Monday 4:00-6:00 PM |
|
Project List: |
|
|
Office Hours: |
Thursday, Friday (Sept 25,26) BA 5287 11:30a.m.-7p.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
|
Date |
Topic |
|
Assignment |
Handouts |
|
|
Sep 14 |
Intro and project suggestion Slides-part1 Slides-part2 |
|
|
|
|
|
Sep 21 |
Parallel Programming and Optimizations Pthreads OpenMP Slides |
|
|
|
|
|
Sept 28 |
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 Matthew Misler
|
Paper summaries |
|
|
|
Oct 5
|
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 Martin Rozee 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 Ahmed Farroukh Fundamentals of Grid Computing, IBM http://www.redbooks.ibm.com/redpapers/pdfs/redp3613.pdf Kam Pui Tang |
Paper summaries |
|
|
|
Oct 12 |
Thanksgiving |
No class |
|
|
|
|
Oct 19 |
Software Distributed Shared Memory |
Informal oral project proposals. Kai Li, Paul Hudak Memory Coherence in Shared Virtual Memory Systems, 1991 ivy91.pdf John Carter, John Bennett, and Willy Zwaenepoel
Implementation and Performance of Munin munin91.pdf
Maxim Siniavine 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 Amirhassan Asgari |
Paper summaries |
|
|
|
Oct 26 |
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 Short Introduction to Event-Driven Servers by Instructor |
Paper summaries |
|
|
|
Nov 2 |
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 Ivan So 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 Vince Mirian |
Papers summaries |
|
|
|
Nov 9 |
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 Angela Lam
Free Transactions with Rio Data Replication Strategies for Fault Tolerance and Availability on
Commodity Clusters C. Amza,
A. Cox, W. Zwaenepoel. |
Paper summaries |
|
|
|
Nov 16 |
Optimizing for Underlying Parallel/Distributed Architecture |
Code Transformations to Improve Memory Parallelism Vijay
S. Pai and Sarita Adve pai_micro99.pdf Young Yoon Distributed Versioning: Consistent
Replication for Scaling Back-end Databases of Dynamic Content Web Sites Cache-Conscious Concurrency Control of
Main-Memory Indexes on Shared-Memory Multiprocessor Systems |
Paper summaries |
|
|
|
Nov 23 |
Concurrent and Distributed Transaction Processing Systems |
A Case for Staged Database Systems. Stavros Harizopoulos and Anastassia Ailamaki stages.pdf Chen Chen STEPS Towards Cache-Resident Transaction Processing, Stavros
Harizopoulos and Anastassia
Ailamaki. Proceedings of the 30th International
Conference on Very Large Data Bases, Exploring Thread-Level Speculation in Software: The Effects of Memory |
Paper summaries |
|
|
|
Nov 30 |
Putting it All Together: Nonblocking Synchronization, Transactional Memory
|
Read Copy Update: Using Execution History to Solve Concurrency Problems. Mc Kenney P. and Slingwine J. rcu.pdf Diego Huang Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III: Software transactional memory for dynamic-sized data structures. PODC 2003 podc-moir.pdf Meric Aydonat 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 Taneem Ahmed |
Paper summaries |
|
|
|
TBA |
Transactional Memory
|
Kaloian Manassiev, Madalin Mihailescu and Cristiana Amza.Exploiting Distributed Version Consistency in a Transactional Memory Cluster. PPoPP 2006 dtm.pdf Sanjeev Kumar, Michael Chu, Christopher J. Hughes, Partha Kundu, Anthony Nguyen. Hybrid Transactional Memory. PPoPP 2006 hybridtm.pdf |
Paper summaries |
|
|
|
TBA
|
Project class presentation
|
|
|
|
|
|
Dec 22 |
Final project report due |
||||