Evaluation plan: Assignments 40%, Minor1 15%, Minor2 15%, Major 30%

Piazza link: col380

Text Books

• Peter S. Pacheco, An introduction to Parallel Programming, Pacheco
• Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, Introduction to Parallel Computing, GGKK
• Michael J. Quinn, Parallel programming in C with MPI and OpenMP, Quinn
• Hennessy Patterson, Computer Architecture: A Quantitative Approach>, Hennessy
• Tannenbaum and Steen, Distributed Systems: Principles and Paradigms, Tannenbaum

Course Content

NOTE: Topics below are tentative (until we are past that week). We will update it as we go through the lectures in each week.

Topic	Supplementary Notes	Book Chapters
Introduction	lec1.pdf	Pacheco, GGKK, Quinn Chapter 1
[Performance] The only reason for parallelism	Quanitifying performance improvements analytically lec2_1.pdf, lec2_2.pdf, lec3.pdf	Pacheco Chapter 2.6, GGKK Chapter 5, Quinn Chapter 7
[Opportunities for parallelism/concurrency] Architecture, compiler and OS support	i. Data level parallelism with SIMD, Vector processors lec5.pdf, ii. Instruction Level Parallelism with compiler support lec6.pdf, iii. Thread and process level parallelism with shared and distributed memory address space multi-processors lec7.pdf, iv. Interconnection networks lec11.pdf	Pacheco Chapter 2.2-2.3, GGKK Chapter 2, 4, Quinn Chapter 2
[Writing parallel programs] C/C++ programming with compiler and library support	i. OpenMP Shared memory parallel programming lec4.pdf, ii. MPI Message Passing parallel programing lec8.pdf, lec12.pdf	Pacheco Chapter 5, GGKK Chapter 7.10, Quinn Chapter 17, Pacheco Chapter 3, GGKK Chapter 6, Quinn Chapter 4
[Probelms faced in parallelism/concurrency] Ensuring program correctness, correctness-vs-performance trade-offs	i. Coherence: Cache coherence and false sharing lec9_lec10.pdf ii. Synchronization: Locks, barriers, transactional memory lec13.pdf, lec14.pdf, lec15.pdf iii. Concurrency bugs Examples of bugs in production code, where programmer's expectations on deadlocks, program order and program atomicity are violated lec17.pdf, paper.pdf iv. Consistency: Memory consistency models lec16.pdf, Java memory model and Python interpreter coarse lock GILlec18.pdf	Hennessy 3.1-3.2, 4.1-4.3, 5.1-5.4
[Parallel program design] Algorithms and data structures	i. PRAM computation model lec20.pdf, pram_1.mp4, pram_2.mp4, pram_3.mp4 ii. Foster's design methodology lec21.pdf, foster.mp4 iii. Brent's theorem for upper bound lec22.pdf, brent.mp4 iii. Pointer jumping technique lec23.pdf, pointer_jumping.mp4 iv. Parallel reduction applications lec23b.pdf, parallel_reduction.mp4 v. Euler tour technique lec24.pdf, euler_tour.mp4 vi. Tree contraction (rake, compress, shunt) lec25.pdf, tree_contraction.mp4	GGKK Chapter 3, Quinn Chapter 3, brent_wikipedia

Assignments

We will strictly check for plagiarism against code available online or within your own class. Offenders will get a fail grade.

• Matrix LU decomposition with Pthreads and OpenMP Assignment 1: Due on Jan 24. Start at openmp-helloworld.
• Matrix multiplication with MPI Assignment2 Part 1: Due on Feb 28
• Pagerank using mapreduce, mapreduce using MPI Assignment2 Part 2: Due on Apr 2