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

1. 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.
2. 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.
3. 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.

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!