Assignments

Assignment #2 Due: Friday 5 May 06, in class Project proposal

Assignment #1 Due: Friday 14 Apr 06, 9am (no class)

You should do this assignment alone. Feel free to use any sources of information you can find--the goal is to learn as much as you can about parallel computing.

You may work with others, but the algorithms and programming should be your work.

The purpose of this assignment is to give you an opportunity to experience writing simple programs using shared memory.

This experience will provide a foundation for writing and/or running much more complex programs.

You should first find out the CPU/memory information of a multi-processor shared-memory computer m3r.tcs.auckland.ac.nz through secure shell (ssh).

You must use this machine only for 703 homework assignments or, with instructor's permission, for your course project. In any case, you should never interfere with the research work on this research machine. You have many choices in doing this assignment. You may use any language and any tools available on this computer.

Assignment 1 (5% of grade)

Write a shared-memory program that reads from a file a list of double-precision floating point numbers and rearranges them. It then writes to the standard output(the screen, most probably) the largest, smallest, and median values. Your program should operate in parallel with P processors specified on the command line. You may want to test your program with smaller files, but the benchmark data consists of 50 million double-precision floating point numbers stored in binary format in the file /afs/.ec.auckland.ac.nz/course/compsci/compsci.703.c.s1.06/A1/bf_sort.dat.
Do not try to copy the file--it is 400 MBytes! In addition to printing the three values, you should also print out (a) the wall-clock time from when the file is opened until it is assembled in main memory as a single array, and (b) the wall-clock time from when the array is filled until the three values have been determined (but not yet printed). You may want to run the experiments several times, because times may very based on other demand on the system. You should report only the best time.

The assignment is to determine from the data the three values of minimum, maximum, and median. There is a linear-time algorithm for determining median, and you are permitted (but not encouraged) to use this algorithm instead of sorting. You need not do a complete sort if you can determine these three numbers from the data by some other means.

What to Hand In

Please turn this homework in on paper in class at the beginning of lecture on the due date. No late assignments will be accepted.

Describe the algorithm you used, how you parallelized the program and why you believe this is the best method. Provide printouts of your program using 1, 2, 4, 8 and M processors Printout should include times, number of processors, and the answers. (M is the maximum number of processors/hardware threads you are able to use, ideally 16). Report some other result you have obtained developing and testing the program, e.g., the time for sorting a range of file sizes, or the results of sorting a partially sorted file. Explain why the result is interesting.

As an appendix, you should attach source code for all experiments you reported.

Hints

1. Use the following for finding more about CPU/Memory info of m3r server:

cat /var/log/dmesg | grep CPU

cat /var/log/dmesg | grep mem

2. M3R has eight processors, each with two threads. Two threads running on a single processor never run twice as fast as a single thread. You should explore the difference, for example, between two threads running on the same processor and two threads running on different processors.

If you have any questions, please feel free to contact the tutor:

Cong Wang
E-mail: <wcon006@ec.auckland.ac.nz>
Office: 303-Level Five