Using the algorithm presented in Ja Ja, I wrote code to color a cyclic directed graph on SMP parallel machines.
The code was written for Dr. David Bader while I was at UNM.
Tools and Libraries
I used Dr. Bader's SIMPLE library, which is designed to effienciently use clusters of SMP machines. It handles both SMP and MPI-type communications with a portable set of primitives.
We used a DEC AlphaServer 8400, with eight 433MHz 21142A CPUs and 4GB of memory. Kudos to Sandia National Labs for donating time to the project.
This graph pretty much tells it all: If you make the input large enough, the parallel version is faster. Also note that the algorithm scales reasonably well.
Final report, MS Word 95 format
Final report, PostScript format
Final report, plain text
Data used in the report and graph
Be aware that you'll need to have SIMPLE working for this to compile; I used version 3.2C.
Code, syntax highlighted and converted to HTML for viewing
Plain code for download
Tarfile of the above
Back to code page
Back to home page