Overview

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.

Hardware

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.

Results

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