Optimal information dissemination in star and pancake networks

Author

Berthomé, Pascal ; Ferreira, Afonso ; Perennes, Stéphane

Author_Institution

Lab. de l´´Inf. du Parallelisme, Ecole Normale Superieure de Lyon, France

Volume

7

Issue

12

fYear

1996

fDate

12/1/1996 12:00:00 AM

Firstpage

1292

Lastpage

1300

Abstract

This paper presents a new decomposition technique for hierarchical Cayley graphs. This technique yields a very easy implementation of the divide and conquer paradigm for some problems on very complex architectures as the star graph or the pancake. As applications, we introduce algorithms for broadcasting and prefix-like operations that improve the best known bounds for these problems. We also give the first nontrivial optimal gossiping algorithms for these networks. In star-graphs and pancakes with N=n! processors, our algorithms take less than [log N]+1.5n steps

Keywords

computational complexity; divide and conquer methods; graph theory; multiprocessor interconnection networks; parallel architectures; decomposition technique; divide and conquer paradigm; hierarchical Cayley graphs; nontrivial optimal gossiping algorithms; optimal information dissemination; pancake networks; prefix-like operations; star networks; very complex architectures; Algorithm design and analysis; Broadcasting; Computer networks; Concurrent computing; Helium; Hypercubes; Intelligent networks; Multiprocessor interconnection networks; Network topology; Parallel programming;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.553290

Filename

553290