CS475 Fall 2008 - Homework 2
Parallel Program for Sieve of Eratosthenes
Objectives
The objective of this homework is to start with a straightforward
parallel implementation and progressively tune it and measure the
performance gains as you go along. You will consider three specific
optimizations, viz., (i) avoiding communication (almost) completely by
duplicating the work of determining of the primes up to sqrt(n) on each
processor; (ii) then improving the sequential part through tiling; and
(iii) allocating memory for only the odd numbers. These programs are
cumulative, each version building on the other. This is a long homework,
so please get started early.
Problem Statement
For this homework, you will need to write analyze and report on three
programs (all derived from a single, common starting point that is
provided here). This program uses the memory
allocation/data distribution strategy discussed in class (and also
allocates two extra chars of memory to make the indexing logic simpler
(the index into the array IS the integer that the location
represents: marked[i] represents the status of i.
- Your first program should be (nearly) communication-free. Each
processor should independently first compute all the primes up to
sqrt(n), and then use these primes to mark off their share of the
array of n integers. It will need to allocate a local auxiliary
array to store these primes.
- Your second program should include the previous optimization and also
reorder the loops on each processor for improved locality. You should
experiment with the block size, b, and report how/why you chose the
one you did.
- Your third program should further optimize this by allocating memory
for only odd numbers. Hypothesize about the improvement you can get from
the modification, and your experimental data should study if/how the
hypothesis is validated.
You may use LAM MPI on the linux machines for the initial design,
development and debugging of the programs. Your performance measurements
for the comparisons should be done on bassi at NERSC.
Your code should conform to the following:
- You should implement each of the three improvements as stand-alone
MPI programs.
- Your programs should take n as a command line argument.
(Recall: your program is going to find and count all primes less than or
equal to n.)
Your programs should run with only one input given.
Feel free to add optional arguments if you would like,
but no other input should be required.
- Your programs should have two modes of compilation:
- DEBUG mode -- in which it should print some outputs (as explained
below)
- PERF mode -- in which it will not print any outputs.
The motivation for these two compilation modes is that when you measure
the performance of your code, you should not include the time for
input/output. Note that you should use a compilation flag (a.k.a. compile
time macro) and not a C-style if statement, because such an
if statement will affect the performance measurements. Here is
an example code fragment that can be used to mark-off sections that needs
to included only in a DEBUG mode:
#ifdef DEBUG printf("%d primes are less than or equal to %d\n", count, n); #endif
The above printf statement will be included in your compilation only when
you define DEBUG in your compilation command. That is, only
when you give mpicc -DDEBUG -o myprog myprog.c
In the absence
of this flag ( -DDEBUG ) your compiler will not include the
printf statement in the final executable.
Here is an introduction to C preprocessor directives. Check Section
7.3.7 for conditional compilation.
- You should provide a Makefile that can compile the three different
programs (three improvements from the provided code) that you are
going to turn in. Your Makefile should create executables for the DEBUG
versions of the programs, with the executables named sieve1, sieve2, sieve3
(first, second, and third implementation respectively).
- All implementations should report the running time in the same format
as the provided program.
- Please provide README and job scripts you used as announced earlier.
What/When/How to Submit:
- 11:59 PM Tue, Sept 30. MPI Programs to be submitted via checkin.
A detailed description of MPI program output will be
posted here. Please read carefully
and make sure that your programs match the description.
- 5:00 pm, Fri, Oct 5. Lab report (soft copy) to be submitted via
checkin. If your program has been modified between submission of program
and lab report, please turn in the new version also by checkin, and
describe clearly in your lab report, what has changed.
Good luck and have fun!