Our initial proposal stated: Our goal is to learn a parallel programming language, PVM (Parallel Virtual Machine), and then to program and execute the given algorithms on a pool of five networked workstations using PVM. We will measure the results of our experiments and compare them with the given theoretical results. Previous results have used simulations to compare results . our work will actually measure the execution time of the algorithms.

We followed our original agenda in phase I and II for the project. In phase I we learned the parallel virtual machine programming language (PVM) and ran sample programs using PVM in order to familiarize ourselves in assigning a task to multiple processors. In doing this we were able to study the various timings that took place. In phase II we studied with Dian and two of her other current research students on an approximation algorithm that is currently in development. In working with them on this, we came to the conclusion that the random graph generator currently in use does not fulfill the constraints for the approximation algorithm. Therefore, we decided that it would be beneficial if we designed and implemented a random graph generator to meet the constraints. To test this approximation algorithm we needed a tool that was accurate and reliable in showing the results of assigning a task to multiple processors.

The approximation algorithm developed by the other researchers in our group dealt with the scheduling problem in distributed computing. Distributed computing is a type of computing where multiple workstations can be utilized to simultaneously execute tasks that would normally be done sequentially on one workstation. These tasks are assigned to different workstations where one task may need to finish before another can begin. In studying how to efficiently schedule tasks on a group of workstations that are networked together, the approximation algorithm developed needed a way to be tested. Our part of the research was to develop a tool for this, specifically a new random graph generator.

To begin with, we needed to follow the constraints of the approximation algorithms. The random graph generator needed to be acyclic, rooted, and directed. Previously, researchers at the University of Minnesota - Morris had implemented a random graph generator, but it produced very similar graphs. Therefore, the output was biased because there was not a wide variety of different graphs, both good and bad to efficiently test the approximation algorithm. In our random graph generator, we decided to model a precedence graph, since it follows the constraints of the approximation algorithm. We needed a way to begin with a random graph and produce a precedence graph. We decided to start with a complete graph . one with edges between every two nodes. We assigned random weights to the edges.

We decided to use Prim's minimum spanning tree algorithm on the complete graph to produce random spanning trees for each n-node complete graph. In using a minimum spanning tree, it does follow the constraints of the approximation algorithm. We then could take the complete random graph, where all nodes have edges going to every other node in the graph, and produce a minimum spanning tree. In order to keep track of insertions and deletions in the graph, we implemented a heap priority queue. All the vertices are stored in the priority queue based on the key field, where the key field is denoted by the edge weights. The algorithm would then terminate when the priority queue was empty, producing a minimum spanning tree. Once we had the minimum spanning tree, we then formed a precedence graph by randomly adding a few minimum weight edges.

By implementing this using Java, our random graphs can be used by our research group in testing the approximation algorithm. In comparing the results, we then have an idea of how well the approximation algorithm works. With our random graph generator, a testbed of random graphs can be generated with a random number of levels, nodes, and children for each node. In some cases these graphs may not be completely random since we discard edges that would produce cycles, when adding in the few edges at the end, in order to follow the constraints of the approximation algorithm. The resulting graphs may be useful to other scientists, not just our research group, in testing the performance of other approximation algorithms.

Publications:
We presented our work at the Midwest Instruction and Computing Symposium (MICS) Conference held at Duluth, MN in April. This is a refereed conference covering a five-state area and has been in existence for almost 40 years. Our paper was published in the proceedings of the conference. We also presented at the Undergraduate Research Symposium that was held at the University of Minnesota . Morris.

Features of our research project, including our paper and presentation can be viewed at: http://csci.mrs.umn.edu/twiki/view/Crew2002/WebHome