CSE 260 Homework Assignment #3: Iterative solver for Poisson's Equation

Due: Tuesday 10/21/08 at 5pm

Changelog

In this laboratory you'll parallelize and experiment with an existing serial implementation of Jacobi's Method in 3 dimensions, which is available as the compressed archive file j3d_serial.tgz. (Look over README.txt for information about code porting, etc.)

A new version was posted, fixing a bug with array bounds: j3d_serial_10-17.tgz.

A small error was repaired in the printout of the convergence check, removing the ! (negative sense) from the test of computeErr. The code has been wrapped up in a new tarball: j3d_serial_10-20.tgz.

The program provides various command line options which are parsed in the source file cmdLine.C, including options you’ll need after you’ve parallelized the code:

 -N      <integer>       domain size, the bounds of the computational mesh
 -i      <integer>        # iterations
 -err                          report error (Residual in the L_inf norm)
 -px     <integer>       number of processors on x axis
 -py     <integer>       number of processors on y axis
 -pz     <integer>       number of processors on z axis   

Thus, the command line

   Jacobi3D -N 128 -i 5 -px 1 -py 2 -pz 4

will run Jacobi3D on 8 processors (threads) over a 128³ mesh for 5 iterations The processors will be configured in a 1 x 2 x 4 geometry.

Threaded implementation

Parallelize the code using pthreads. Your code should support 1, 2, and 3-dimensional geometries, and should support the case when N³ is not divisible by the processor geometry. Verify that your code is correct by comparing the final error (residual) with single processor runs: print out the value of the residual to 6 decimal places. To what degree are the results independent of the number of threads and the processor geometry? Be sure to provide an explanation.

The solver handles cubical meshes of size N × N × N. Choose a value of N such that you can run 100 iterations in under 10 seconds on 1 processor.

If the number of processors P_kdoes not divide N evenly along some axis k, you must make sure that all processors are as evenly loaded as possible. Thus, no processors will be without a work assignment, and the assigned workloads will never differ by more than one along any of the 3 axes.

Teams of 2

The technique we'll use is to coarsen the solution and iterate several times to obtain an approximate solution, which serves as a good initial guess. We then refine this solution and iterate until convergence.  This strategy contains the essential machinery for implementing multigrid, which is an algorithm for accelerating convergence.

Modify your code so that, once the RHS and initial guess have been generated, a new coarsened version of the initial guess and RHS are produced, and subsequently smoothed by a Jacobi solver. This coarsened solution is then projected (via interpolation) back onto the original mesh and is used as an improved initial guess.

Note that Jacobi3D has an option to print out the error (L_inf residual) every iteration. You'll need to use this option in order to demonstrate the improved running time of your two level solver when delivering a given level of accuracy.

Be sure and iterate many times at the coarse level so that you see a significant improvement in the time needed to reach convergence. To coarsen a mesh, use multigrid restriction, that is, simple averaging of the nearest neighbors. Thus, if C is the coarsening factor each coarsened mesh point (I,J,K) will be obtained from points ((I*C)+i, (J*C)+j), (K*C)+k ), where i, j, k range from 0 to C-1.  A coarsening factor of 2 should be sufficient, but larger values may help improve convergence. To update the fine mesh with the coarsened guess, use the multigrid prolongation operation (interpolation) to re-refine the mesh. The details of are described in Jim Demmel's notes.

Structure your code so that you use a single function to solve both the coarsened and refined problems.

Matlab code for the acceleration scheme is available as jac_matlab.tgz

Things you should turn in

If you are working in a team, include a self-evaluation discussing the division of labor and other aspects of how you worked together as a team team. A copy of the form is available here.

Your turnin will consist of two parts. Submit a hard copy of your report in class. Also transmit an electronic copy by emailing a single archive file, e.g. .zip, .tgz, containing your writeup and source code-- and the self-evaluation, if applicable.

Be sure and delete all .o files and executables before creating the tar file. Email the archive file as an attachment to the following address, and put the string cse260:A3 in the Subject: line:

baden

+260_a3

@

ucsd.

edu

The name of your archive file should start with your login ID, e.g. baden.tgz. When your archive file is extracted, a new directory should be created with the name of your login ID. The directory should contain two subdirectories

src:	All source code including your makefile, so we can build the software.
report	Your report including any image files, screen shots, or other output you wish us to see.

Maintained by

baden

@

ucsd.

edu

[Tue Oct 28 19:52:07 PDT 2008]