CPSC 425: Parallel Computing

Course Description

This course provides an introduction to parallel computing, covering topics including parallel architectures, programming techniques and libraries, the study of existing parallel computing systems, and performance analysis. Students will use a variety of hardware to explore current libraries and methods used for parallel programming.

Course Goals & Objectives

• To understand parallel hardware and software systems.
• To gain experience developing parallel algorithms.
• To write programs in multiple parallel programming environments.
• To be able to evaluate the performance of parallel programs.

Student Learning Outcomes

• identify and explain the use of parallel computing in the age of multi-core computers.
• explain the difference between thread-level and process-level parallelism.
• explain the role of caches in a modern computing system and understand the role of caching in writing performant code.
• explain non-determinism in the context of parallel computing and be able to account for it in parallel programs.
• recognize race conditions and be able to protect critical sections with locks.
• compare and contrast mutexes, semaphores, read-write locks, and conditions as tools for protecting critical sections.
• use a message-passing system to communicate data between processes.
• use higher-level message passing operations such as broadcast and reduce.
• write parallel programs using thread-level and process-level parallelism to solve non-trivial problems.
• calculate speedup and efficiency for parallel programs.
• apply Amdahl’s Law to estimate the expected speedup parallelism would bring to a program.
• identify and explain common parallel algorithmic techniques.

Grading Policy

• Programming Projects, 50%
• Labs, 20%
• Three exams, 10% each

• [94, ∞): A
• [90, 94): A-
• [87, 90): B+
• [84, 87): B
• [80, 84): B-
• [77, 80): C+
• [72, 77): C
• [70, 72): C-
• [66, 70): D+
• [60, 66): D
• [0, 60): F

Late assignments will have a 10% reduction in grade for each day late. Lab assignments will be due at the end of the day of the class period after they are assigned. For example, labs given on Wednesday will be due at the end of the day Friday. There will be no make up for missed tests. If you cannot attend a test period, please contact me ahead of time to arrange another time to take it. Final grades will not be rounded up, and no extra credit opportunities will be given on an individual basis.

The University provides the opportunity to provide grading feedback midway through the semester. This will take into account your score on the mid-term exam and the programming projects submitted up to that point. Any student receiving less than a 65% on either of these will receive a "U" for their mid-semester grade. If this happens to you, please don't hesitate to talk with me about how we can improve your performance in this class.

Student Conduct

• You are expected to attend each class meeting. If you miss a class, you are responsible for the material covered.
• This class will be interactive. Expect to answer questions in class and always feel free to ask any questions yourself.
• If you miss an exam, you are required to provide legitimate documentation of an emergency for your absence to have a make up exam.
• If you can't make an exam for a non-emergency reason, you must schedule an alternate time to take it ahead of time.

Honor Policy

Students are expected to conduct themselves in a manner consistent with the letter and spirit of the UMW Honor Constitution, as well as the CPSC department honor policy. For this class in particular:

For labs, collaboration is OK. The goal of the labs is to ensure you understand the concepts we are going over.

For projects, you may discuss the ideas with other students, but all of your work must be your own. You must yourself write and understand everything in each assignment you submit. It is an honor code violation to copy directly from another student either by copy and paste or by transcription, or to copy from the web.

For exams, you can not talk to anyone during the exam, or use any kind of notes.

If you have any questions or need clarification, please don't hesitate to contact me!

Disability Statement

Title IX Statement

The University of Mary Washington faculty are committed to supporting students and upholding the University's Policy on Sexual and Gender Based Harassment and Other Forms of Interpersonal Violence. Under Title IX and this Policy, discrimination based upon sex or gender is prohibited. If you experience an incident of sex or gender based discrimination, we encourage you to report it. While you may talk to me, understand that as a "Responsible Employee" of the University, I must report to UMW's Title IX Coordinator what you share. If you wish to speak to someone confidentially, please contact the below confidential resources. They can connect you with support services and help you explore your options. You may also seek assistance from UMW's Title IX Coordinator. Please visit http://diversity.umw.edu/title-ix/ to view UMW's Policy on Sexual and Gender Based Harassment and Other Forms of Interpersonal Violence and to find further information on support and resources.

Recording Statement

Classroom activities in this course may be recorded by student's enrolled in the course for the personal, educational use of that student or for all students presently enrolled in the class only, and may not be further copied, distributed, published or otherwise used for any other purpose without the express written consent of the course instructor. All students are advised that classroom activities may be taped by students for this purpose. Distribution or sale of class recordings is prohibited without the written permission of the instructor and other students who are recorded. Distribution without permission is a violation of copyright law. This policy is consistent with UMW's Policy on Recording Class and Distribution of Course Materials.

Tentative Schedule

Date	Class Topic	Assignment Due
August 22	Course Introduction
August 24	Parallel Hardware
August 26	Parallel Software
August 29	Introduction to Pthreads
August 31	Pthreads Continued
September 2	No class
September 5	Labor Day
September 7	Lab 1: Pthreads
September 9	Critical Sections & Mutexes
September 12	Semaphores
September 14	Lab 2: Thread Timing
September 16	Read-Write Locks
September 19	Lab 3: Deadlock
September 21	Barriers & Conditions
September 23	Travelling Salesman Problem
September 26	No class
September 28	Review & Catchup	Knapsack Solver
September 30	Exam 1
October 3	Cache Systems
October 5	No class
October 7	Lab 4: False Sharing
October 10	Fall Break
October 12	Introduction to OpenMP
October 14	Reductions & Parallel For
October 17	Lab 5: OpenMP
October 19	Loop Scheduling
October 21	OpenMP Synchronization
October 24	Parallel Searching
October 26	Parallel Sorting
October 28	Exam 2
October 31	Introduction to MPI
November 2	MPI Continued	Horizontal Image Blur
November 4	Lab 6: MPI
November 7	Collective Communication
November 9	Lab 7: Collective Communication
November 11	MPI Odds & Ends
November 14	Lab 8: MPI Deadlock
November 16	Distributed Sorting
November 18	Threads vs. Processes and Hybrid	Forest Fire Simulation
November 21	The Julia Set
November 23	Thanksgiving Break
November 25	Thanksgiving Break
November 28	Introduction to CUDA
November 30	CUDA Continued
December 2	GPU Architecture	Bin Packing
December 9	Final Exam, 8:30 - 11:00 AM