Department of Computer Science

ITCS 3145 Parallel Programming (Cluster Computing)
Fall 2005

Dr. Barry Wilkinson


Lecture materials Assignments Papers Tests

Lecture Materials

The following slides are provided as Powerpoint slides or pdf files.  You may wish to print these sides out as 1 x 2 or 2 x 3 thumbnails.

Lecture slides (pdf format)
pdf slides
Powerpoint slides
Outline (Powerpoint) Course outline, prerequisites, course text,  course contents, assessment, instructor details.  
1. Parallel Computers (Powerpoint) Demand for computational speed, types of parallel computers, cluster computing. Chapter 1
2. Message-passing Computing (Powerpoint) Basics of message-passing programming, software tools, MPI, evaluating parallel programs, compiling MPI programs. Chapter 2
3. Embarrassingly Parallel Computations (Powerpoint) Embarrassingly Parallel examples, Mandelbrot Set, Monte Carlo methods. Chapter 3
4. Partitioning and Divide and Conquer Strategies (Powerpoint) Partitioning and divide and conquer examples, bucket sort, numerical integration, N-body problem. Chapter 4
5. Pipelined Computations (Powerpoint) Pipeline technique and types, examples, adding numbers, sorting, prime number generation, solving system of linear equations. Chapter 5
6. Synchronous Computations (Powerpoint) Synchronization, barrier implementation, synchronous computation examples, data parallel, synchronous iteration, solving system of linear equations by iteration, heat distributed problem, cellular automata, partially synchronous methods. Chapter 6
7. Load Balancing and Termination Detection (Powerpoint) Dynamic load balancing, distributed termination detection algorithms, program example (shortest path problem) Chapter 7
8. Programming with Shared Memory (Powerpoint) Shared memory multiprocessors, constructs for specifying parallelism, processes, threads, language constructs, dependency analysis, OpenMP, performance issues, program examples Chapter 8
9. Distributed Shared Memory Systems and Programming (Powerpoint) Potential speedup of sorting in parallel, compare and exchange, bubble sort, odd-even transposition sort, mergesort, quicksort, odd-even mergesort, bitonic mergesort, sorting on meshes and hypercube, rank sort, counting sort, radix sort, sample sort, sorting on clusters. Chapter 9
(Chapter 10 in 2nd edition)
10. Sorting Algorithms (Powerpoint)   Chapter 10
11. Numerical Algorithms (Powerpoint)   Chapter 11
12. Image Processing (Powerpoint)   Chapter 12

Click here for a "Figures-Only" PDF version

Other sources of materials:

Textbook home page giving instructions on using MPI etc:


Assignment Topic
Assignment 1 Ping-pong program
Assignment 2 Monte Carlo program (pi by integration)
Assignment 3
Parallelizing Mandlebrot program or any program of your choice which uses graphics.
Code for bitmap.
Assignment 4 Write/test program for test 2, Part II.

Sample Assignments:

Assignment 1 Familiarization Assignment
Assignment 2 Mandelbrot Assignment
Assignment 3 Astronomical N-body Problem
Assignment 4 Open Ended Pthreads Assignment




M. Allen, B. Wilkinson, and J. Alley, "Parallel Programming for the Millennium: Integration Throughout the Undergraduate Curriculum," 2nd Forum on Parallel Computing Curricula, June 22nd, 1997.


Paper2 B. Wilkinson and M. Allen, "A State-Wide Senior Parallel Programming Course," IEEE Transactions on Education, Vol. 42, no. 3 (August), 1999, pp. 167-173.




Class tests:

Class test 1 Date:

Topics for test 1: Material up and including pipelining (Chapter 1 to Chapter 5).

Sample tests:
Sample test
Test 1 Fall 2003    Solution for part II
Test 1 Spring 2002 to add
Test 1 Spring 2000
Test 1 Fall 1998

Note: Posted tests may have some questions not from current class notes. Your test will only have material from class notes.

Class test 2 Date:

Topics for test 2: Chapter 6, 7, and 8

Sample test 2
Another sample test 2


Class test 3 Date:

Topic for test 2: Chapter 9 (Sorting)


Final Exam: Date:


Sample final exams:
Final Fall 2003 to add
Final Spring 2002 to add
Final Fall 2000
Final Spring 2000
Final Fall 1998
Final Spring 1998

Note: Posted final tests may have some questions not from current class notes. Your  test will only have material from class notes. Also there may be duplicated questions. (Final tests were not previously posted). Do not expect the same questions.