Description:
This is the first program on LAM that splits a sequence of unsorted numbers into N chunks & assigns them to N worker processes. The worker processes then use qsort() to sort their individual sequence & return the sorted sequence back to the main manager/master program which then merges the sorted list & prints them out. This program was later updated to include MPE logging capabilities that generates log files to help in the visualization of send/receive calls.
Main areas explored in this assignment:
This is the first program (technically, the second, see below) that explores the features LAM provides for writing parallel programs, getting a feel of how parallel programs are written & using the send/receive to establish interaction between the workers & the manager. This program is an example of static work allocation where the manager statically decides how many numbers to allocate to each workers statically based on the size of the input sequence & number of workers. This assignment also explores the basic logging capabilities of MPE without the use of specific MPE logging calls & then uses jumpshot to visualize the log file.
A future work is to make the program dynamic in terms of work allocation & load balancing.
Assignment Resources:
MPE Makefile
Note: If you want to compile my programs using the above Makefile in
UBC CS Deptt machines, replace this block in my Makefile
##### User configurable options #####
bla bla bla ...
### End User configurable options ###
with this block (simply copy &
paste it over my original makefile, erasing the previous block).
MPE
Visualization using Jumpshot
Description & Observations of the visualization:
In this sample output we see that the manager splits the
total array equally into all the different workers (10 in this case)
& distributes the work load equally. To process the remainder of
the array after division, it reutilizes the first worker process by
resending it the remainder chunk of the numbers. After the sorting
& merging process is over, the manager sends a "kill" message to
all the workers who upon receiving the message terminates the
execution. Here we have chosen to reuse the first worker. The manager
could have chosen any other worker & killed the rest of the others.
Also ideally, the remainder chunk of the work should be assigned to the
first worker who reports that it has completed its task. This extension
is left as a future exercise. The green area we see are actually the
time wasted by the processors in waiting for receive message. This wait
time has to be reduced in order to increase efficiency.
This is indeed the first program written in LAM, which is a specific case of the above implementation where only two worker processes & one manager processes are created & they do the same operations as the one described above. I initially wrote this program to get started with LAM & then generalized it for arbitrary number of processors to produce the generalized implementation as described above.
First posted: Jan 15th 2006. Last updated: Feb 7th 2006 Credits: 10
