###
A. Ferreira,
I. Guerin Lassous,
K. Marcus, and
A. Rau-Chaplin,"Parallel Computation on
Interval Graphs
using PC Clusters: Algorithms and Experiments"

###
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.

Home* Publications