Introduction to Parallel Computing
Exercise 1 (Deadline: May 3)

Wolfgang Schreiner
RISC-Linz

April 9, 1999

Write on the Convex SPP a parallel (Fortran or C) program solving the "All Pairs Shortest Path" problem. Use the sequential program on the course page as the starting point and apply the parallelization features of the Convex compiler.

1. Compile the sequential program with -O2. Measure the execution times of function path for matrix sizes 256 and 384 and take these times as the base times of all your comparisons with the parallel program.
2. Compile the program with -O3 without changes; analyze the messages generated by the compiler and explain them in detail, i.e., describe how the compiler transformed the program.

   Measure the execution times for both input sizes and 1, 2, 4, 8, 12 processors. Use the CXpa performance profiler to analyze the performance of your program (for appropriate input and processor number). Determine which fraction of execution time was spent in which part of the program.

3. Try to improve the performance of the program by restructuring it and/or using pragmas and/or parallelization constructs and/or compilation flags. Proceed in the analysis as for the previous case.
4. Write a report documenting your results including
   • the changed parts of your source code,
   • analysis of the compiler reports,
   • execution times (numerical tables and graphical diagrams),
   • speedups (numerical tables and graphical diagrams),
   • efficiencies (numerical tables and graphical diagrams),
   • analysis of program behavior and performance,
   • any other findings, problems, comments, etc.