| Abstract |
|---|
| The use of PC clusters interconnected by high performance localnetworks is one of the major current trends in parallel/distributed computing.These clusters can yield effective parallel systems for a fraction of the priceof machines using special purpose hardware. Although significanteffort has been undertaken on system-level and programmingenvironment issues for such clusters, much less attention has been paidto some of the algorithmic issues. In this paper we show that theoretical(BSP-like) coarse-grained models are well adapted to solve important classes ofproblems on PC clusters. We give coarse-grained parallel algorithmsto solve many problems arising in the context of interval graphs,namely connected components, maximum weighted clique, BFS and DFStrees, minimum interval covering, maximum independent set and minimumdominating set. All of the described $p$-processor parallelalgorithms require only constantor O(log p) number of communication rounds and are efficient inpractice as demonstrated by our experimental results obtained on aFast Ethernet based cluster. In an interesting interplay betweentheory and practice we note that super-linear speedupsoccurred for large data because of swapping factors. |
| Contact |
| Isabelle Guerin Lassous LIAFA - Universite Paris 7,Case 7014,2, place Jussieu,F-75251 PARIS Cedex 05,FRANCE, guerin@liafa.jussieu.fr |