Department of Computer Science

ITCS 3145 Parallel Programming (Cluster Computing)

Fall 2005

Dr. Barry Wilkinson

**Contents**:

Lecture materials | Assignments | Papers | Tests |

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.

pdf slides |
Powerpoint slides |
Topics |
Textbook |

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: http://www.cs.uncc.edu/par_prog

Assignment |
Topic |

Assignment 1 | Ping-pong program |

Assignment 2 | Monte Carlo program (pi by integration) |

Assignment 3
bitmap.c bmptest.c readme |
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 |

**Class tests:**

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.

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

Sample test 2

Another sample test 2

Topic for test 2: Chapter 9 (Sorting)

Topics:

*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.