CSS 534/490: Parallel Programming in Grid and Cloud

CSS 534/490: Parallel Programming in Grid and Cloud
Summer 2012
MW 545-750pm at UW1-221
Prof. Munehiro Fukuda

Professor:

Munehiro Fukuda <mfukuda@u.washington.edu>, room UW1-331, phone 352-3459, office hours: MW 500-540pm

Course Description:

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) task-parallel programming with MapReduce, and (4) data-parallel programming with MASS.

Prerequisites:

Graduate students: CSS543 or professor's consent
Undergraduate students: None (but it would be easier if you have taken CSS430, 432, "or" 434)

Work Load and Grading:

Course Work % CSS534 % CSS490 Achievements Approximately Corresponding Numeric Grade

Programming 1 15% 20% 90s 3.5 - 4.0

Programming 2 15% 20% 80s 2.5 - 3.4

Programming 3 15% 20% 70s 1.7 - 2.4

Programming 4 20% 20% 60s or below 0.0 - 1.6

Literature Survey 15% N/A

Midterm Exam 10% 10%

Final Exam 10% 10%

Textbooks/References:

The class mainly focuses on the original lecture notes. Therefore, the course has no specific textbook although there are many useful references (marked with recommended) and manuals to assist your programming and literature-survey work. Note that some of the following references start with an abbreviation that is used to indicate chapters referred in our course schedule.

Parallel Programming
- Pattern: Patterns for Parallel Programming, Timothy G. Mattson, Beverly A. Sanders, and Berna L. Massingill, Addison-Wesley, 2005
- CDK5: Distributed Systems, Concepts and Design, George Coulouris, Jean Dollimore, and Tim Kindberg, Addison-Wesley, 2011
Grid and Cloud
- Grid-D: Grid Computing for Developers, Vladimir Silva, Charles River Media, Inc., 2006
- Grid-2: The Grid 2, 2nd Ed, Ian Foster and Carl Kesselman, Morgan Kaufmann, 2003
- Cloud: Cloud Application Architectures, George Reese, O'Reilly, 2009
OpenMP
- OpenMP: Using OpenMP, Barbara Chapman et.al., The MIT Press, 2007 (recommended)
- The OpenMP API Specification for Parallel Programming (http://openmp.org/wp/)
MPI
- MPI: Parallel Programming with MPI, Peter S. Pacheco, Morgan kaufmann, 1997 (recommended)
- The Message Passing Interface (MPI) Standard (http://www.mcs.anl.gov/research/projects/mpi/)
- mpiJava Home Page (http://www.hpjava.org/mpiJava.html)
MapReduce
- MapReduce: Data-Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer, Morgan and Claypool, 2010
- Hadoop: Hadoop: The Definitive Guide, MapReduce for the Cloud, Tom White, O'Reilly, 2009 (recommended)
- Apache Hadoop (http://hadoop.apache.org/)

Policies:

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.

Course Goals:

The overall goal of CSS 534/490, "Parallel Programming in Grid and Cloud" includes:

Examine theoretical programming models and patterns for parallel computing.
Examine practical middleware design for parallel programming in grid and cloud systems.
Use contemporary programming tools as well as job and resource management middleware.
Evaluate different programming models, patterns, and middleware mathematically with general metrics, empirically with benchmarks, practically with case studies, and
Develop advanced programming skills to effectively design and build parallel software, using grid and cloud computing tools.

Programming Assignments:

Four programming assignments are given. Please read assignment.html to understand the environment you use for assignments and the submission/grading procedures.

Laboratory Work:

For the first five weeks, we are planning to have post-lecture laboratory sessions that allow you to get familiar with tools such as OpenMP, MPI, MapReduce, and MASS so as to start each programming assignment smoothly. For each laboratory session, we will move from the classroom to the UW1-320 Linux laboratory where you will make a team of two students and work together on each programming exercise. Each group or student must turn in the source code and execution results in the laboratory or together with the following programming assignment work.

Group Discussions:

The first five weeks will also have post-lecture group discussions where you will form a team of 3 or 4 students, discuss about given topics, and present the discussions in the classroom.

Literature Surveys and Presentations

The three five weeks focus on case studies of grid and cloud systems. There each graduate student will choose one system, study about it through literature survey, and give a presentation of what s/he studied. Please refer to surveywork.html for more details.

Topics covered and tentative 534/490 schedule:

Note that this is an approximate ordering of topics. Chapters will take about the allotted time and not all sections in all chapters are covered.

Week Date Topics Sessions Readings Assignment

1 June 18 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 Program 1 (css534)
Program 1 (css490)

June 20 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

2 June 25 Shared Memory Programming 2
Memory model, DSM, and performance issues Discussion 1
(Static/dynamic load balancing) Patterns Ch 2: Background and Jargon of Parallel Programming
OpenMP Ch 5: How to Get Good Performance

June 27 Message Passing Programming 1
MPI: Message Passing Interface Laboratory 2
(MPI) Patterns Appx B: Intro to MPI
MPI Ch 3: Greeting
MPI Ch 4: Numerical Integration
MPI Ch 5: Collective Communicateion

3 July 2 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 Program 1 due
Program 2 (css534)
Program 2 (css490)

July 4 Holiday - No School

4 July 9 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

July 11 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

5 July 16 Midterm Exam in class

July 18 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 (css534)
Program 3 (css490)

6 July 23 Laboratory 4
(MASS)

July 25 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

7 July 30 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

Aug 1 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
Program 4 (css534/490)

8 Aug 6 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

Aug 8 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/

9 Aug 13 Final Exam in class

Aug 15 Student Final Project Student Presentation Program 4 due

Course Work	% CSS534	% CSS490	Achievements	Approximately Corresponding Numeric Grade
Programming 1	15%	20%	90s	3.5 - 4.0
Programming 2	15%	20%	80s	2.5 - 3.4
Programming 3	15%	20%	70s	1.7 - 2.4
Programming 4	20%	20%	60s or below	0.0 - 1.6
Literature Survey	15%	N/A
Midterm Exam	10%	10%
Final Exam	10%	10%

Week	Date	Topics	Sessions	Readings	Assignment
1	June 18	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	Program 1 (css534) Program 1 (css490)
	June 20	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
2	June 25	Shared Memory Programming 2 Memory model, DSM, and performance issues	Discussion 1 (Static/dynamic load balancing)	Patterns Ch 2: Background and Jargon of Parallel Programming OpenMP Ch 5: How to Get Good Performance
	June 27	Message Passing Programming 1 MPI: Message Passing Interface	Laboratory 2 (MPI)	Patterns Appx B: Intro to MPI MPI Ch 3: Greeting MPI Ch 4: Numerical Integration MPI Ch 5: Collective Communicateion
3	July 2	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	Program 1 due Program 2 (css534) Program 2 (css490)
	July 4	Holiday - No School
4	July 9	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
	July 11	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
5	July 16	Midterm Exam in class
	July 18	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 (css534) Program 3 (css490)
6	July 23		Laboratory 4 (MASS)
	July 25	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
7	July 30	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
	Aug 1	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 Program 4 (css534/490)
8	Aug 6	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
	Aug 8	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/
9	Aug 13	Final Exam in class
	Aug 15	Student Final Project	Student Presentation		Program 4 due