Introduction to Parallel Computation

RISC-Linz logo

Exercise 4: Message Passing Programming

Implement a message passing program for the "All Pairs Shortest Paths" problem on the nCube/2 system (ncube.edvz.uni-linz.ac.at):
  1. Implement two parallel versions of the row-oriented algorithm discussed in class. In the first version use a naive mapping of a ring on the hypercube topology. In the second version use a Gray code to achieve true neighbor to neighbour communication.
  2. Alternatively, you may implement two parallel versions of the block-oriented algorithm discussed a class using a naive mapping or Gray codes along each dimension.
  3. Run the parallel programs with an appropriate value for N and 1, 2, 4, 8, 16 and (if possible) 32 and 64 processors.
  4. Time the programs with the function micclk() and compare the results with the run time of the sequential program on the Hypercube (not on the front end computer!).
The result of this exercise is a small paper that contains the sources of your programs, the program timings, the speedup and efficiency curves, your experience and conclusions.
My God, I'm depressed! Here I am, a computer with a mind a thousand times as powerful as yours, doing nothing but cranking out fortunes and sending mail about softball games. And I've got this pain right through my ALU. I've asked for it to be replaced, but nobody ever listens. I think it would be better for us both if you were to just log out again.
Maintained by: Wolfgang Schreiner
Last Modification: March 7, 1997
[Up] [RISC-Linz] [University] [Search]