Parallel Computation on Interval Graphs using PC Clusters: Algorithms and Experiments.

A. Ferreira, I. Guerin Lassous, K. Marcus, and A. Rau-Chaplin

Abstract: The use of PC clusters interconnected by high performance local networks is one of the major current trends in parallel/distributed computing. These clusters can yield effective parallel systems for a fraction of the price of machines using special purpose hardware. Although significant effort has been undertaken on system-level and programming environment issues for such clusters, much less attention has been paid to some of the algorithmic issues. In this paper we show that theoretical (BSP-like) coarse-grained models are well adapted to solve important classes of problems on PC clusters. We give coarse-grained parallel algorithms to solve many problems arising in the context of interval graphs, namely connected components, maximum weighted clique, BFS and DFS trees, minimum interval covering, maximum independent set and minimum dominating set. All of the described $p$-processor parallel algorithms require only constant or $O(\log p)$ number of communication rounds and are efficient in practice as demonstrated by our experimental results obtained on a Fast Ethernet based cluster. In an interesting interplay between theory and practice we note that super-linear speedups occurred for large data because of swapping factors.

Download paper in .pdf format
Download paper in .ps format

Home * Publications