Implementation

I decided to write this program in Objective-C based on the Cocoa frameworks. This is the suggested language for Mac OS X development and since I will be using Apple’s XGrid on Mac OS X machines, it was the logical choice. Objective-C allows the use of C and C++ code throughout the code as well as the Objective-C objects from the Cocoa classes.

Coding the executable to be run on the agents turned out to be a relatively simple task. It included two major classes, Vertex and Graph, and a main.m file to handle flow control. The purpose of the executable is to run on a single step of the problem as determined by the calling XGrid plug-in.

XGrid allows for the development of a custom plug-in that will run a command-line executable on a set of files. This turned out to be the ideal method of generating the colorings of the subgraphs but did not work as well for recombination. XGrid, as of the current preview release, does not have any support for recursively dependent tasks. This left me looking for a workaround to submitting a new job manually for each level of the recombination tree.

The solution was to write a shell script that would complete each job, delete the old files, and submit the next job. The script turned out to be very successful and allowed the entire problem to be solved in three steps. First, I broke the graph in serial on one computer. Then I submitted the coloring job with the list of broken subgraphs. Finally I was able to run the shell script with a single command to submit the sequential jobs for recombination.

 

Results

Experimental Setup

To test my methods, I was given access to a lab of 24, 500 MHz, PowerMac G4s. Each computer was running Mac OS 10.3.3 with XGrid Technology Preview 2. I did tests on two, manually generated, planar graphs. The first graph, “large_planar_manual.txt”, had 85 vertices. The second graph was simply a larger planar graph, this one containing 157 vertices.

First Run

The first run of this program turned out largely to be a failure. There were two primary reasons for this: memory leaks were so large that some computers began to crash, and I did not go in with an effective plan to automate recombination. Because the memory leaks existed in both the coloring algorithm and the recombination algorithm, there was no way to compensate by adjusting the number of subgraphs. I was also forced to manually submit each recombination step as a separate job.

Second Run

In this run I made use of the shell script that would automate the recombination steps so that only one command must be given for all recombination.

The coloring operation did not take long to compete once the graphs were broken. The complete coloring of the subgraphs was finished within 45 seconds. Most of this time was caused by job overhead and network communication, demonstrating the inefficiency of running jobs that are two small.

The recombination step took significantly longer. Overall, recombination took about 28 minutes to complete and return a fully reconstructed graph. This time was, unfortunately, still on the order O(3n/p). The small size of the graph that dictated the size of k was mostly responsible for the lack of better results.

 

Conclusions

The results show that my value of k could have been much smaller. However, since I set k=p, any smaller would have caused some computers to be largely inactive. The value of the function S(j) is the real variable in the runtime; it controls the time spent at each step. Since I have no estimate as to the shape or average value of this function, it was difficult to find an appropriate value for k.

This method for three-coloring graphs proved to have some potential. However, the actual test runs that I did were not as effective as I would have hoped. The value of k was fixed due to the relatively small size of my test graphs, which limited the real flexibility of this method. I believe that with extensive testing, an appropriate value of k could be found such that the time would shrink to near O(3n/p).

 

 

See the Code

Home