CSS 534: Parallel Programming in Grid and Cloud
Spring 2014
MW 545-750pm at UW2-105
Prof. Munehiro Fukuda
This course closely examines programming methodology and middleware used for parallel computing in grid and cloud systems, and develops your programming skills high enough to design and build application-specific parallel software with up-to-date grid and cloud programming environments.
Topics covered include parallel-computing platforms, parallel-programming models (such as supported with OpenMP, MPI, and other paradigm-oriented language tools such as MapReduce), programming patterns (such as task and data parallelism), middleware for job and resource management, and fault tolerance.
For each of the topics, we will cover the background and motivation, programming and design theory, and current technology implementation in grid and cloud. In addition, the first five weeks will advance your parallel-programming knowledge and skills through in-class discussions and laboratory hands-on programming exercises, while the last five weeks will strengthen your ability of system analysis through literature surveys and presentations on grid/cloud systems.
Four programming assignments are given: (1) shared-memory-based programming with a tool such as OpenMP, (2) message-passing-based programming with a tool such as MPI, (3) paradigm-oriented programming with MapReduce, and (4) data-parallel/agent-based programming with MASS.
| Course Work | Percentage | Achievements | Approximately Corresponding Numeric Grade |
| Programming 1 | 15% | 90s | 3.5 - 4.0 |
| Programming 2 | 15% | 80s | 2.5 - 3.4 |
| Programming 3 | 15% | 70s | 1.7 - 2.4 |
| Programming 4 | 20% | 60s or below | 0.0 - 1.6 |
| Literature Survey | 15% | ||
| Midterm Exam | 10% | ||
| Final Exam | 10% |
Although post-lecture laboratory work can be done in collaboration, all programming assignments 1 through to 4 are to be done independently. Any collaboration of work will result in severe penalty. You may discuss the problem statement and any clarification with each other, but any actual work to be turned in must be done without collaboration.
Any homework is due at the beginning of class on the due date. The submission may be postponed only in emergencies such as accidents, sickness, sudden business trips, and family emergencies, in which case you may turn in your homework late with a written proof. No make-up exams will be given except under exceptional circumstances. Barring emergencies, I must be informed before the exam.
To request academic accommodations due to a disability, please contact Disability Resources for Services (DRS) in UW1-175, (email: drs@uwb.edu, TDD: 425-352-5303, and FAX: 425-352-5381). If you have a documented disability on file with the DSS office, please have your DRS counselor contact me and we can discuss accommodations.
| Week | Date | Topics | Sessions | Readings | Assignment |
|---|---|---|---|---|---|
| 1 | Mar 31 | System Models SMP, clusters, hybrid systems, grid, and cloud |
Patterns Ch 2: Background and Jargon of Parallel Computing CDK4 Ch 2: System Models MPI Ch 1: Introduction |
||
| Apr 2 | Share Memory Programming 1 Loop parallelism, multi-processes, multi-threads, and OpenMP |
Laboratory 1 (OpenMP) |
Patterns Appx A: Intro to OpenMP OpenMP Ch 1: Introduction OpenMP Ch 3: Writing a First OpenMP Program OpenMP Ch 4: OpenMP Languge Features |
Program 1 assigned | |
| 2 | Apr 7 | Shared Memory Programming 2 Memory model, DSM, and performance issues |
(Static/dynamic load balancing) | Patterns Ch 2: Background and Jargon of Parallel Programming OpenMP Ch 5: How to Get Good Performance |
|
| Apr 9 | Discussion 1 (Static/dynamic load balancing) |
||||
| 3 | Apr 14 | Message Passing Programming 1 MPI: Message Passing Interface |
Patterns Appx B: Intro to MPI MPI Ch 3: Greeting MPI Ch 4: Numerical Integration MPI Ch 5: Collective Communicateion |
||
| Apr 16 | Laboratory 2 (MPI) |
Program 1 due extended to Friday Program 2 assigned |
|||
| 4 | Apr 21 | Message Passing Programming 2 MPI Performance Hybrid OpenMP and MPI |
Discussion 2 (OpenMP vs MPI and Hybrid pros/cons) |
MPI Ch 11: Performance MPI Ch 12: More on Performance |
|
| Apr 23 | Paradigm-Oriented Programming 1 Task parallelism and MapReduce |
Laboratory 3 (MapReduce) |
Patterns Ch3.2: Task Decomposition Patterns Ch4.4: Task Parallelism MapReduce Ch 2: MapReduce Basics MapReduce Ch 3: MapReduce Algorithm Design |
||
| 5 | Apr 28 | Paradigm-Oriented Programming 2 MapReduce applications |
Discussion 3 (MapReduce pros/cons and MapReduce-suitable applications) |
MapReduce Ch 4: Inverted Indexing for Text Retrieval MapReduce Ch 5: Graph Algorithms |
|
| Apr 30 | Paradigm-Oriented Programming 3 Data parallelism, GlobalArrays, MASS, and thread migration |
Discussion 4 (Paradim programming vs DMS, and their computation granurality) |
Patterns Ch3.3: Data Decomposition Patterns Ch4.6: Geometric Decomposition http://www.emsl.pnl.gov/docs/global/ |
Program 2 due Program 3 assigned |
|
| 6 | May 5 | Midterm Exam in class | |||
| May 7 | Laboratory 4 (MASS) |
||||
| 7 | May 12 | Parallel Programming Patterns Task, Data, and Mixed parallelism |
Discussion 5 (Application design with task, data, and mixed parallelism) |
Patterns Ch4:The Algorithm Structure Design Space Patterns Ch5:The Supporting Structures Design Space Patterns Ch6:The Implementation Mechanisms Desgin Space |
|
| May 14 | Job Management Rsh, intra/inter-cluster and centralized/decentralized scheduling, autonomic computing, and cluster virtualization |
Grid-D Ch 5: Schedulers Grid-2 Ch 18: Resource and Service Management |
|||
| 8 | May 19 | OpenPBS, Condor, Legion, NetSolve, Ninf, Globus, XenoServer, COD, Amazon EC2 | Survey Work Presentation 1 | http://www.globus.org/ http://www.cs.wisc.edu/condor/ http://legion.virginia.edu/ http://icl.cs.utk.edu/netsolve/ http://www.cl.cam.ac.uk/research/srg/netos/xeno/ http://www.cs.duke.edu/nicl/cod |
Program 3 due (extended to May 21) Program 4 assigned |
| May 21 | File Management Network, distributed, and parallel file systems |
CDK4 Ch 8: DFS Grid-D Ch 9: Data Management Grid-2 Ch 22: Data Access, Integration, and Management Hadoop Ch 3: Hadoop DFS Cloud Ch 2:Amazon Cloud Computing |
|||
| 9 | May 26 | Holiday (No School) | |||
| May 28 | NFS, AFS, PVFS, MPI/IO, Hadoop, and Amazon-S3 | Survey Work Presentation 2 | http://www.openafs.org/ http://www.pvfs.org/ http://www.nersc.gov/nusers/resources/software/libs/io/mpiio.php http://hadoop.apache.org/ http://aws.amazon.com/s3/ |
||
| 10 | June 2 | Fault Tolerance Two-phase commitment, replication, and check-pointing |
CDK4 Ch 14: Distributed Transaction CDK4 Ch 15: Replication Cloud Ch 4: Ready for the Cloud Cloud Ch 6: Disaster Recovery |
||
| June 4 | Globus-DUROC, MS Cloud DB, Coda/AFS, Condor-MW, MapREduce/Hadoop, Legion-FTMPI | Survey Work Presentation 3 | http://www.globus.org/toolkit/docs/2.4/duroc/
http://www.microsoft.com/windowsazure/ http://www.cs.wisc.edu/condor/mw/ http://hadoop.apache.org/ http://legion.virginia.edu/ |
||
| 11 | June 9 | Student Final Project | Student Presentation | Program 4 due | |
| June 11 | Final Exam in class |