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.

plot of results

  • Final report, MS Word 95 format
  • Final report, PostScript format
  • Final report, plain text
  • Data used in the report and graph
  • Code

    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

  • graph_color.c
  • graph_color.h
  • Plain code for download

  • graph_color.c
  • graph_color.h
  • Makefile
  • Tarfile of the above
  • Navigation

  • Back to code page
  • Back to home page