HPC Project 4: Combining Patterns to Solve a Simple Problem

Overview

In this exercise, we want to use parallelism to accelerate the computation of the sum of the squares of the values stored in an input file. The basic idea is to parallelize this summation by distributing it across P different PEs. To make the problem interesting, we'll be using the same large files you used in this week's lab.

Getting Started

The file sumSquares.c contains a sequential program to read N double values from a file into an array, sum the squares of the values in the array, and report the resulting value. The file Makefile lets you build sumSquares using the make utility.

Use the text files in the directory /home/cs/374/exercises/04 to test this program.

If you do not want to use these clunky, long, absolute file-names, you can create a symbolic link to each one. For example, if you enter the following command in your project folder:

   ln -s /home/cs/374/exercises/04/1m-doubles.txt

Add the necessary calls to sumSquares.c to separately time:

1. the time required to open the file, allocate the array, and read the file's values into the array,
2. the time required to compute the sum of the squares of the values in the array, and
3. the total time (i.e., from just after MPI_Init() to just before MPI_Finalize()).

Then build the program, and when it builds without errors or warnings, execute it using each of the .txt files in /home/cs/374/exercises/04. In a spreadsheet, record the sums and times you get for each file.

The Project

The end-goal of this project is to create a program mpiSumSquares that uses MPI to perform this computation faster. Use everything you learned in this week's lab exercise to complete this task.

As in sumSquares.c, your mpiSumSquares program should use MPI_Wtime() calls to calculate the read time, the sum-the-squares time, and the total time, to indicate how much of the overall time the read and sum-the-squares steps are consuming.

Use a similar procedure to what we did in the lab, running your program over 3 trials for each file-size. For each trial, record the sum, the read-time, sum-the-squares time, and the total time in a spreadsheet, and use those entries to calculate the minimum value for each time. You should get approximately the same sum-values as sumSquares.c produced.

Your sum-values may not be exactly the same because when adding and multiplying many real numbers, round-off errors may occur, and the particular round-off errors depend on the order in which the adds and multiplies occur. Since the exact order in which the adds and multiplies occur within a parallel computation is non-deterministic, you may not get exactly the same results in different executions of a parallel computation that uses real numbers.

When your program works correctly, use your spreadsheet to record the sums, the trial-times, and the minima you get for each file, using P = 1, 2, 4, 6, and 8 processes.

For P = 2, 4, 6, and 8, use your spreadsheet to compute the parallel speedup, and the parallel efficiency.

Visualizing the Results

Using the data in your spreadsheet, create the following charts:

• Time as P and N Vary: A 3D column-chart with your program's Total Time as the vertical dimension, and P and N as the other (horizontal) dimensions. Orient this 3D chart so that its shortest columns are nearest the viewer, so that as much detail can be seen as possible.
• Time as P Varies with Fixed N=1B: A 2D stacked column-chart for N = 1B, with Time on the vertical axis and P = 1, 2, 4, 6, 8 on the horizontal axis. In each column, the minimum read time should be at the bottom of the stacked bar, with the minimum sum-the-squares time on top of it; the height of the column should equal the total time.
• Speedup as P and N Vary: A 2D line-chart with P = 2, 4, 6, 8 on the horizontal axis, Speedup on the vertical axis, and separate lines/series for each N = 1M, 10M, 100M, and 1B file sizes.
• Efficiency as P and N Vary: A 2D line-chart with P = 2, 4, 6, 8 on the horizontal axis, Efficiency on the vertical axis, and separate lines/series for each N = 1M, 10M, 100M, and 1B file sizes.

These four charts should allow you to explore how well your program scales as P and N change. Be sure to use descriptive titles and labels for your charts and their axes, and use chart-columns or lines that can be easily distinguished from one another when the chart is printed on a gray-scale printer.

Hand In

Hard copies of:

1. A 2-3 page analysis of your results. Things to discuss:
   • The decisions you made in designing your program, and what aspects of the lab exercise influenced your decisions.
   • The changes of your program's execution time as P and N change. What do your timing measurements reveal about where your program is losing or gaining time? Speculate as to what might be causing that.
   • The changes of your program's Speedup as P and N change. For a given file size N, is there an optimal value of P with respect to Speedup?
   • For each file size N, is there a P value for which your program's efficiency is below our 60% threshold of acceptability?
   • After reviewing Amdahl's and Gustafson's Laws, where can the effects of these laws be seen in your charts? Be specific.
   As always, make your analysis as quantitative as possible--each claim you make should be supported by citing specific data points from your spreadsheet data.
2. Your charts and spreadsheet data. Make each chart a full page in size to maximize the ability to see its details.
3. The source code for your program and your Makefile.
4. If you used AI for this project, an additional 2-3 page report, as described on the 374 course policies page.

Please staple these pages together and make certain that your name is on each page.

CS > 374 > Exercises > 04 > Homework Project