CIS4930/CDA5125 Introduction to Parallel and Distributed Systems

CIS4930/CDA5125 Introduction to Parallel and Distributed Systems, Fall 2011

This course is supported in part by the Nividia CUDA Teaching center program (See Nvidia press release in May 11, 2011) and the early adopter program of NSF/IEEE-TCPP Parallel and Distributed Computing Curriculum.

Lecture 1

Lecture 2

Lecture 3

Lecture 2 Review
Dependence, loop transformation, and optimizing single thread performance
Homework 1 (Due: Sept 14, 11:59pm): Optimizing the matrix multiply code (naive_mm.c) for lingprog. You can find a partner for all programming assignment. Mail your code to Surjyendu Ray. At the beginning of the program, write the names of group members in the comment line. You should also report the float point operating rate in MFLOPS of linprog with two benchmarks: naive_mm and your optimized routine with specific parameters.
Your code should meet the following requirement: (1) it should produce correct results for all matrix sizes (0 point otherwise; using -DCHECK to produce output for checking); (2) it should achieve a speedup of 4 for most reasonably large matrix sizes; and (3) for 1024x1024 matrix, the multiplication time should be less than 2.1 second. The program should be compiled with -O3 flag when testing performance.

Lecture 4

Lecture 3 Review
Streaming SIMD Extension
Intel C++ Intrinsics Reference. Here is a local copy. Thanks to Hang Zhang for finding this document.
Homework 2 (Due: Sept 21, 11:59pm): Further Optimize your improved matrix multiply code in homework 1 using SSE programming. Mail your code to Surjyendu Ray. At the beginning of the program, write the names of group members in the comment line. You should also report the float point operating rate in MFLOPS of linprog with your optimized routine with SSE using 1024 by 1024 matrices. Your SSE matrix multiply routine should be correct for all matrix sizes; for 1024x1024 matrices, the multiplication time should be around 1 second. The program should be compiled with -O3 flag when testing performance. You may need to use the following SSE2 intrinsics: _mm_loadl_pd(), _mm_loadh_pd(), _mm_storel_pd(), _mm_storeh_pd(),_mm_add_pd(),_mm_mul_pd().

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Lecture 10 Review
Programming SMP systems: OpenMP
Homework 3 (Due: Oct 5, 11:59pm): Matrix multiplication code with pthread AND OpenMP. At the beginning of each of the programs, write the names of group members in the comment line. You should also report the float point operating rate of linprog with your threaded and openMP routines using 2048x2048 matrices. Your threaded and OpenMP matrix multiply routine should be correct for all matrix sizes; for 1024x1024 matrices, the time should be less than 0.3 second on linprog.
Extra point (closing time Oct 12, 11:59pm): Matrix multiplication challenge. 20 extra points will be added to the midterm grade for the group with the fastest time among all programs in the class for multiplying two 8192x8192 matrices on a single linprog machine. The time needs to be faster than 135 seconds.

Midterm to be held on Oct 17. Everyting up to the Lecture 12. Close everything, but you are allowed to bring a 11"x8.5" cheat-sheet to the exam.

Lecture 10

Lecture 11

Lecture 12

Lecture 13

Lecture 14

Lecture 15

Contact info for Surjyendu Ray (TA): Office: 100D MCH, Office hour: 10:00am-12:00pm, Thursday, Email: surjray.ta@gmail.com.
Term project information
Lecture 14 Review
Network interface design issue and a case study

Lecture 16

Lecture 17

Lecture 16 Review
Programming distributed memory systems: Message Passing Interface (MPI)
Homework 4 (Due: Nov. 9, 11:59pm): Matrix multiplication code with MPI. At the beginning of each of the programs, write the names of group members in the comment line. Your MPI matrix multiply routine must be correct for any matrix size and number of processes; each MPI should use O(Total_size / nprocs) memory space (no process should store any whole matrix); the time for computing multiply of two 8192x8192 matrices should be less than 105 seconds (with any number of processes) on linprog. You should start from the mpi_mm_driver.c program, and do not modify anything given. You should also try to reuse your sequential implementation.

Lecture 18

Lecture 19

Lecture 20

Term project progress report due Wednesday
In mpi_mm_driver.c code, please change the memory allocation for W to 'W = malloc((localN+nprocs)*K*sizeof(double));'. Here are test case 1 and test case 2 for the mpi MM program.
Lecture 18 Review
CUDA programming 1
CUDA C Programming Guide, version 4.0

Lecture 21

Lecture 19 Review
CUDA programming 2
Homework 5 (Due: Nov. 28, 11:59pm): Matrix multiplication code with CUDA. At the beginning of each of the programs, write the names of group members in the comment line. Your CUDA matrix multiply routine must be correct for matrices of sizes 1024x1024, 2048x2048, and 8192x8192; the time for computing multiply of two 8192x8192 matrices (single precision) should be less than 6 seconds on one of the gpu machine.

Lecture 22

Lecture 23

Please sign-up for your term project presentation time. Here is the project presentation peer grading sheet.
Lecture 21 Review
PRAM

Lecture 24

Final exam at Dec. 15, 10:00-12:00. Exam covers everything in the course. You are allowed to bring a 11"x8.5" cheat-sheet to the exam.
Term project report due at Dec. 14 at 11:59am.
Lecture 22 Review
LogP and BSP

Dec. 5 presentations

Christopher Ogden and Troy Rosenberg, "Parallelization of the Inverser Matrix Problem"
Robert Griesmeyer and Steven Bronson, "GPU implementation of Password Cracker"
Sree Anjana Ravi and Shruti Naik, "Scheduling in MapReduce"
Divyatej, Govardhan, and Subir "Energy Aware High Performance Computing"

Dec. 7 presentations