HPC MPI Homework Project 6: Measuring Speedup

Overview

To find all prime numbers up to some limit value N, this algorithm works as follows:

1. Create the sieve -- an array indexed from 2 to N. (This can be an array of bools or ints or anything else that supports random access and provides entries that are easy to "mark".)
2. Set k to 2.
3. Loop:
   1. In the sieve, mark all entries whose indices are multiples of k between k² and N, inclusive.
   2. Find the smallest index greater than k that is unmarked, and set k to this value.
   Until k² > N.
4. The indices of the unmarked sieve entries are prime numbers.

Today we wll study a parallel version of this algorithm that distributes "the sieve" across M different PEs, to see what kind of speedup and efficiency it offers.

Exercise

Chapter 5 of your text provides a parallel version of Eratosthenes Sieve called sieve1.c (see Figure 5.6) and explains how it was designed. Unfortunately, that program has a bug that makes it only work correctly with more than one process. Download this corrected version and this Makefile. Make and run it to verify that it is working correctly.

Then rerun it, using a large limit value (e.g., 100,000,000 or more) on 1 PE, and record the execution time in a spreadsheet. The Makefile provides a way to do this conveniently.

Then run it again using 2 PEs (hopefully different from those of your classmates) and record its execution time in your spreadsheet. Using these values, compute the speedup S₂, and the efficiency E₂ as discussed in class.

Then run it again using 4 PEs (again, hopefully different from those of your classmates) and record its execution time in your spreadsheet. Using these values, compute the speedup S₄, and the efficiency E₄.

If all is well (i.e., your classmates are not interfering with you), you should see measurable speedup when using 2 and 4 PEs. Which has higher speedup? Which has higher efficiency?

There are at least three ways in which the program can be improved. Implementing these improvements is this week's assignment.

Homework

Your task is to write three "improved versions" of sieve1.c, as described in your text:

• sieve2.c, in which you modify sieve1.c to exclude all even integers from consideration. (See section 5.9.1 in your text.)
• sieve3.c, in which you modify sieve2.c to eliminate the broadcast step. (See section 5.9.2 in your text.)
• sieve4.c, in which you modify sieve3.c by reorganizing its loops to increase the cache hit rate. (See section 5.9.3 in your text.)

Hand In

• Your source code for the four programs.
• Four spreadsheet charts -- one for each program -- showing the execution times on Ohm using 1, 2, 4, 8, and 16 PEs.
• Four spreadsheet charts -- one for each program -- showing the speedups on Ohm using 2, 4, 8, and 16 PEs.
• Four spreadsheet charts -- one for each program -- showing the efficiencies on Ohm using 2, 4, 8, and 16 PEs.
• A 1 page analysis of your results: How do the execution times of these programs compare? Do the execution times match those predicted in the textbook? How do their speedups compare? How do their efficiencies compare? What is the optimal number of PEs for maximizing speedup? What is the optimal number of PEs for maximizing efficiency? Are these optimal numbers the same or different for your four programs?

Up to the HPC Homework Page

Up to the Calvin HPC Course Page