Objectives

The objective of this lab is to write your first MPI programs, to debug and test them, and to experimentally determine the gains you get in running them in parallel on up to 16 processors (two nodes on carver). For the Pi program, you will have two versions of your code: one using a cyclic distribution and one using a block distribution. The timings for both versions should be compared and discussed in your report. For the sieve program you may want to use the most efficent method from HW2 (sieve5 blocked for locality). You may use Program1 the (unblocked) version that uses half the memory and marks off only odd multiples of each prime.

Exercise 4.11 in the text describes how the value of Pi can be computed by evaluating a definite integral. Your main assignment is to solve Problem 4.11. That is, turn in a correct working program that computes Pi using the rectangle rule. You should also address 4.11 (b) relating to the performance of your parallel program on a varying number of processors and report that in your lab report.

Use MPI to parallelize the sieve program. Use the most efficent method from HW2 that you successfully completed (sieve5 - blocked for locality). As always, you should report speedup relative to the fastet sequential program that you have.

Your code should conform to the following:

• Create 3 programs:
  pi_cyc.c - Pi computed with cyclic distribution.
  pi_block.c - Pi computed with block distribution.
  sieve_mpi.c - Your MPI sieve code.
• Your pi code should be parameterized with the number of strips to evaluate, i.e., it should run for any value from 1,000,000 to 10,000,000,000. Your program should take this value (the number of strips) as a command line argument.
• Each process, after completing its share of computations should print, to the stdout, its processor id, followed by its partial sum (that it is going to return to the master process). Just print the "raw" partial result, do not multiply it by 4. Use the following format:

      printf("%d %lf\n", rank, partial_result); 

  where, rank is the rank of the process, and partial_result is the result it has computed and is going to return to the master process.
• The master process (after adding up the partial results) should print the final Pi Value. Use the following format:

   printf("FINAL PI VALUE
      IS %lf\n", final_result); 

  where, final_result is the final value of Pi computed by the master process.
• The sieve code should take n and tile size as command line arguments. Tile size should be optional and should default to the best block size you found for carver with a n of 2E9 and 4E9 (if you used a blocked version, of course). It should create the same output as it did for HW2.
• For all programs please test the processor number up to 16, use at most 2 nodes on carver.
• Please use this makefile. Makefile
• You should submit the source code in a file named HW4.tgz by midnight on Tuesday, Nov. 1.
• You should submit the lab report by midnight on Thursday, Nov. 3.

How to Submit:

• You must submit the file from one of the Linux machines, such as crestone or dmx.
• All assignments are submitted electronically via the ~cs475/bin/checkin program.
• You must submit a single tar file containg all of your source code and your Makefile.
• You must name the tar file as HW4.tgz
• You may resubmit the file as many times as you like. Subsequent submissions will not overwrite previous submissions.Please do not modify the filename when resubmitting.The system will take care of it.
• If you have more than one file for your program, then you should provide a makefile that will compile all executables. Your executables should contain names as described previoudly. Any assignment submitted that contains code that will not compile will receive a 0%.
• The checkin program should be used as follows:
  ~cs475/bin/checkin HW4 HW4.tgz
  

• Enter the directory that contains the files you want to submit.
• Use the command:

   tar czvf HW4.tgz [file1] [file2] [file3] ..  

Your tar file should contain only the program files you want to submit and the makefile.Here is an example tar file HW4.tgz. It should not contain any additional directories.
• Use the command:

   man tar

  for more information.

Good luck and have fun!