Implementation of Parallel Graph Algorithms on a Massively Parallel SIMD Computer with Virtual Processing

We describe our implementation of several PRAM graph algorithms on the massively parallel computer MasPar MP-1 with 16,384 processors. Our implementation incorporated virtual processing and we present extensive test data. In a previous project [13], we reported the implementation of a set of parallel graph algorithms with the constraint that the maximum input size was restricted to be no more than the physical number of processors on the MasPar. The MasPar language MPL that we used for our code does not support virtual processing. In this paper, we describe a method of simulating virtual processors on the MasPar. We recoded and fine-tuned our earlier parallel graph algorithms to incorporate the usage of virtual processors. Under the current implementation scheme, there is no limit on the number of virtual processors that one can use in the program as long as there is enough main memory to store all the data required during the computation. We also give two general optimization techniques to speed up our computation. We tested our code with virtual processing on test graphs with various edge densities. We also compared the performance data for our parallel code with the performance data of sequential code for these problems. We found that the extra overhead for simulating virtual processors is moderate and the performance of our code tracks theoretical predictions quite well, although real-time speed-ups are quite small since the MasPar processors are rather slow. In addition, our parallel code using virtual processing runs on much larger size inputs than our sequential code