CS525: Parallel Computing

Assignments and Solutions:

Assignment 1: Parallel Computing Platforms

Deadline: Mar 3, 2005 (in class). No late solutions will be accepted.
Problems: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.24, 1.27, (from your handout on architectures).

Performance Metrics.

Problems: 3.1, 3.5, 3.9, 3.14 (from your handout on analytical modeling).

Assignment 2: Group Communications / Basic Parallel Programming

Deadline: Mar 22, 2005 (in class). No late solutions will be accepted.

Problems: 3.5, 3.8, 3.19, 3.20 (from your handout on group communications).

Programming Problems:

Problem 1. Write an MPI program to estimate t_s and t_w on the platform you are using.

Problem 2. Write a pthreads program to estimate the time to create and join a thread, the time for a successful lock. The time for a successful trylock and an unsuccessful trylock.

Assignment 3: Programming/Sorting/Graphs.

Deadline: Apr 26, 2005 (in class).

Problem 1. Write a POSIX threads program for quicksort. Use the partitioned list algorithm discussed in the class. Make sure you use tree-based prefix algorithms and minimize mutual exclusion. Use condition waits where possible. Implement it on the 8 processor SMP and show speedup curves as you increase the size of the list.

Problem 2. Write an MPI program for solving the all-pairs shortest path problem using Floyds algorithm and 2-D checkerboard mapping of the adjacency matrix. To test the algorithm, generate adjacency matrices of varying sizes (from 1000 x 1000 onwards) and show speedups on 1 - 8 processors.