Implementation of parallel graph algorithms on the MasPar
Tsan‐sheng Hsu, Vijaya Ramachandran, Nathaniel Dean · DIMACS series in discrete mathematics and theoretical computer science · 1994
. Graphs play an important role in modeling the underlying structure of many real world problems. Over the past couple of decades, efficient sequential algorithms have been developed for several graph problems and have been implemented on sequential machines. The NETPAD system at Bellcore is a general tool for graph manipulations and algorithm design that facilitates such implementations. More recently, several research results on efficient parallel algorithms have been developed, but not much implementation has been done. We have implemented some of the parallel algorithms for basic graph problems on the massively parallel machine MasPar, and we have interfaced these algorithms with NETPAD. In this paper, we give a description of our implementation together with some performance data. We also describe the interface that we have built between our library of parallel graph algorithms and the NETPAD system. 1. Introduction This paper summarizes a project we undertook at Be...