CSS 534: Parallel Programming in Grid and Cloud
Autumn 2021
MW 545-745pm at UWBB 205
Prof. Munehiro Fukuda

Professor:

Munehiro Fukuda <mfukuda@uw.edu>, room UW1-271T, phone 352-3459, office hours: MW 5:15-5:45pm (Outside of the classroom) and 7:45-8:15 (In the classroom) or by appointment (Zoom)

COVID19 Policy:

Regardless outside or inside of the building, you need to wear a mask on campus. If I see anyone without wearing a mask in the classroom, I can't start the class. Although the class takes place at UWBB 205 in person, all class activities are synchronized with and recorded by Zoom. Therefore, if you feel sick, stay home and attend the class through Zoom. If you get COVID, definitely stay home. As of September 24, 2021, there is no official rule if the class as a whole must be quarantined upon finding any COVID-positive classmates. Even in the worst case, the class can continue in a Zoom-based online format. Prof. Erika Parsons is my back-up instructor.

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:

  1. parallel-computing platforms,
  2. parallel-programming models: OpenMP, MPI, MapReduce, Spark and other paradigm-oriented language tools,
  3. programming patterns such as task and data parallelism,
  4. parallel-job submission, management, and recovery.

For each of the topics, we will cover the background and motivation, programming and design theory, and current technology implementation in grid and cloud. Each lecture will advance your parallel-programming knowledge and skills through in-class discussions and laboratory hands-on programming exercises.

Five 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-parallelized programming with MapReduce,
  4. data-parallelized programming with Spark
  5. the final project to parallelize an open problem with each of MPI, MapReduce, Spark, and the MASS (multi-agent spatial simulation) library.

Prerequisites:

MS in Computer Science and Software Engineering as well as Cyber-Security Engineering only

Work Load and Grading:

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 15% 60s or below 0.0 - 1.6
Programming 5 20%
Midterm Exam 10%
Final Exam 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.
  1. Parallel Programming
  2. OpenMP
  3. MPI
  4. MapReduce
  5. Spark

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 Students (DRS) in UW1-071, (email: rosal@uw.edu, Phone: 425-352-5307, and FAX: 425-352-5114). If you have a documented disability on file with the DRS office, please have your DRS counselor contact me and we can discuss accommodations. For more information, please read this DRS statement.

The class follows the religious accomodation policy. Please check the Syllabi Guidelines and Resources webpage.

Course Goals:

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

Programming Assignments:

Five programming assignments are given. Please read assignment.html to understand the environment you use for assignments and the submission/grading procedures. You will submit only a soft copy to Canvas.

Laboratory Work:

We are planning to have six post-lecture laboratory sessions that allow you to get familiar with tools such as OpenMP, MPI, MapReduce, Spark and MASS so as to start each programming assignment smoothly. Please bring your labtop computer to the classroom for each laboratory session. You may work together or independently on each programming exercise. However, each student must independently turn in the source code and execution results, (i.e. a snapshot and performance comparisons if requested) to Canvas. To access cssmpi1h.uwb.edu ~ cssmpi12h.uwb.edu, you need to use Terminal for Mac OS/X and Linux or Putty for Windows.

Group Discussions:

We 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. This discussions are intended to have you digest materials only but not to grade the correctness of your discussions.

Final Project Presentation:

Program 5, (i.e., the final project) is an open project. You will form a team of three students to choose and implement a challenging application (but reasonably done within two and half weeks), using each of mpiJava, MapReduce, Spark, and MASS. Two presentations are planned: (1) topic presentation where each team will explain about the application they have chosen and the audience will evaluate how challenging it will be and (2) final presentation where each team summarize their programming and performance comparison work. The audience will evaluate their work.

Topics covered and tentative 534 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
0 Sept 29 System Models
SMP, clusters, hybrid systems, grid, and cloud		 Discussion 1
(Grid vs Cloud, Why shared memory couldn't gain popularity) 		Patterns Ch 2: Background and Jargon of Parallel Computing
CDK4 Ch 2: System Models 		 
1 Oct 4 Programming Foundations
Intro to shared memory, messag passing, embarassingly parallel, divide and conquer, pipeline, and synhcronization		 Discussion 2
(Implementation of data parallelism, Fault tolerance, HW1 Parallelization in Genetic Algorithm) 		MPI Ch 2: Overview of Parallel Computing
Patterns Ch5 The Supporting Structures Design Space		 Program 1 assigned
  Oct 6 Share Memory Programming 1
Loop parallelism, multi-processes, multi-threads, and OpenMP		 Laboratory 1
(OpenMP)		 Patterns Appx A: Intro to OpenMP
OpenMP Ch 1.8: Wasy to Create Parallel Programs
OpenMP Ch 3: Writing a First OpenMP Program
OpenMP Ch 4: OpenMP Languge Features		  
2 Oct 11 Shared Memory Programming 2
Memory model and DSM		 Discussion 3
(OpenMP versus Spark) 		Patterns Ch 2: Background and Jargon of Parallel Programming  
  Oct 13 Shared Memory Programming 3
Performance considerations		 Discussion 4
(Static/dynamic load balancing)		 Patterns Ch 2: Background and Jargon of Parallel Programming
OpenMP Ch 2.6: Performance Considerations
OpenMP Ch 5.2: Performance Considerations for Sequential Programs
OpenMP Ch 5.3: Measuring OpenMP Performance
OpenMP Ch 5.4: Best Practices		  
3 Oct 18 Message Passing Programming 1
MPI: Message Passing Interface		 Laboratory 2
(MPI)		 Patterns Appx B: Intro to MPI
MPI Ch 2.2:Software IssueMPI Ch 3: Greeting
MPI Ch 4: Numerical Integration
MPI Ch 5: Collective Communicateion
MPI CH 6: Grouping Data for Communcation
MPI CH 7: Communications and Topologies		 Program 1 due
Program 2 assigned
  Oct 20 Message Passing Programming 2
MPI performance
Hybrid OpenMP and MPI		 Discussion 5
(OpenMP vs MPI and Hybrid pros/cons)		 MPI Ch 11: Performance
MPI Ch 12: More on Performance		  
4 Oct 25 Message Passing Programming 3
MPI IO, MPI in different languages
MPI-based Systems		 Discussion 6
(Applications of MPI/IO, pyMPI, CUDA-aware MPI, and MPI/FT)		 MPI/IO, (MPI2 report ch 9)
pyMPI
mpiJava
CUDA-aware MPI		  
  Oct 27 Task Parallelism 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 Nov 1 Task Parallelism 2
MapReduce applications		 Discussion 7
(MapReduce pros/cons and graph application performance)		 MapReduce Ch 1: Introduction
MapReduce Ch 4: Inverted Indexing for Text Retrieval
MapReduce Ch 4.1: Web Crawling
MapReduce Ch 4.2-4.4: Inverted Indexing: Baseline/Revised Impelmentations
MapReduce Ch 4.6: Waht about Retrieval?
MapReduce Ch 5: Graph Algorithms
MapReduce Ch 5.1: Graph Representations
MapReduce Ch 5.2: Parallel Breadth-First Search
MapReduce Ch 5.3: PageRank
Program 2 due
Program 3 assigned
  Nov 3 Task Parallelism 3
Hadoop Ecosystem		 Discussion 8
(Hadoop Eco vs MPI in file access, job submission, and data flow)		 https://hadoop.apache.org/  
6 Nov 8 Midterm Exam in class      
  Nov 10 Data Parallelism 1
Data Parallelism and Spark		 Laboratory 4A
(Spark - Single Node Execution)		 Patterns Ch4: Data Decomposition
Spark Ch3: RDD - Transformation/Action
Spark Ch6: Partition
Spark Ch2: pySpark
Java Spark 		 
7 Nov 15 Data Parallelism 2
Spark Applications		 Laboratory 4B
(Spark - Standalone Cluster Execution)		 Spark Ch7:Spark Cluster
Java Spark Applications: Spark-2.3.1-bin.hadoop2.7.tgz's examples/src/ 		Program 3 due
Program 4 assigned
  Nov 17 Data Parallelism 3
Other Data Parallel Systems		 Discussion 9
(Matrix multiplication and triangle counting with Spark)		 Patterns Ch4:Data Decomposition
Global Array
Spark mllib
Spark GraphX
Data Ch16:Triangles Counting		  
8 Nov 22 Migration of Computing 1
Recursive Data Patterns		 Discussion 10
(Brainstorm data-science applications suitable to MPI, MapReduce, Spark, and MASS)		 Patterns Ch4: Data Decomposition
MASS
Nomadic Thread
Olden
  Nov 24 Migration of Computing 2
Agent-Based Computing		 Laboratory 5
(MASS)		 MASS
CSS599 (Wi21) Talk		 Program 4 due extended to Nov. 29
Program 5 assigned
9 Nov 29 Student Presentation 1 Final Project Topic Presenstation   Program 4's new deadline
  Dec 1 Parallel Programming Patterns
Task, Data, and Mixed parallelism 		Discussion 11
(Applications that take advantage of switched/mixed parallelism)		 Patterns Ch4:The Algorithm Structure Design Space
Patterns Ch5:The Supporting Structures Design Space
Patterns Ch6:The Implementation Mechanisms Desgin Space		  
10 Dec 6 Course Summary PAAMS'21 Talk    
  8 Student Presentation 2 Final Project Summary Presentation and Demonstration   Audience feedback due on Dec 10
11 Dec 13       Program 5 due at 5:45pm
  Dec 15 Final Exam in class