ON A UNIFIED NEIGHBOURHOOD BROADCASTING SCHEME FOR INTERCONNECTION NETWORKS
Abstract
The neighbourhood broadcasting problem in an interconnection network is defined as sending a fixed sized message from the source node to all its neighbours in a single-port model. Previously, this problem has been studied for several interconnection networks including the hypercube and the star. The objective of such works has been to minimize the total number of steps required for the neighbourhood broadcasting algorithms. Here, we first use a general neighbourhood broadcasting scheme to develop a neighbourhood broadcasting algorithm for the star interconnection network that is asymptotically optimal, conceptually simple, and easy to implement since routing for all nodes involved is uniform. It uses the cycle structures of the star graph as well as the standard technique of recursive doubling. We then show that the scheme for the star network is general enough to be applied to a broader family of interconnection networks such as the pancake interconnection network for which no previous neighbourhood broadcasting algorithm is known, resulting in asymptotically optimal algorithms. Finally, we use this scheme to develop neighbourhood broadcasting algorithms for multiple messages for several interconnection networks.
Some preliminary results appeared in [29, 30, 31] previously.
References
- IEEE Transaction on Computers c 38(4), 555 (1989). Crossref, ISI, Google Scholar
S. B. Akers , D. Harel and B. Krishnamurthy , The star graph: an attractive alternative to the n-cube, Proc. International Conference on Parallel Processing (1987) pp. 393–400. Google Scholar- Networks 23, 215 (1993). Crossref, ISI, Google Scholar
-
S. G. Akl , Parallel Computation, Models and Methods ( Prentice Hall , New Jersey , 1997 ) . Google Scholar -
J. C. Bermond , A. Ferreira and J. G. Peters , Partial broadcasting in hypercubes , International Workshop on Interconnectional Networks ( 1991 ) . Google Scholar - J.C. Bermond, A. Ferreira, S. Pérennes, and J.G. Peters, Neighbourhood broadcasting in hypercubes, Technical Report, SFU-CMPT-TR 2004-12, School of Computing Science, Simon Fraser University, Canada . Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 8(12), 1196 (1997). Crossref, ISI, Google Scholar
- Information Processing Letters 56, 259 (1995). ISI, Google Scholar
- Discrete Applied Math. 61(2), 105 (1995). Crossref, ISI, Google Scholar
-
T. H. Gormen , C. E. Leiserson and R. L. Rivest , Introduction to Algorithms ( The MIT Press , Cambridge, Massachusetts , 1990 ) . Google Scholar - Parallel Processing Letters 1, 103 (1991). Link, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 5(1), 31 (1994). Crossref, ISI, Google Scholar
G. Fertin and A. Raspaud , Neighbourhood communications in networks, Proc. Euro-conference on Combinatorics, Graph Theory and Applications,Electronics Notes on Discrete Mathematics (2001) p. 10. Google ScholarG. Fertin and A. Raspaud , k-Neighbourhood broadcasting, 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'0l) (2001) pp. 133–146. Google Scholar- Parallel Processing Letters 8(2), 189 (1998). Link, Google Scholar
S. Fujita , Neighbourhood information dissemination in the star Graph, Proc. of the International Colloquium on Structural Information & Communication Complexity (SIROCCO'98) (2000) pp. 1366–1370. Google Scholar- Journal of Interconnection Networks 4(4), 419 (2003). Link, ISI, Google Scholar
- Discrete Math. 27, 47 (1979). Crossref, ISI, Google Scholar
- J. Algorithms 25(1), 67 (1997). Crossref, ISI, Google Scholar
- Parallel Computing 24, 1263 (1998). Crossref, ISI, Google Scholar
A. Menn and A. K. Somani , An efficient sorting algorithm for the star graph interconnection network, Proc. International Conference on Parallel Processing (1990) pp. 1–8. Google Scholar- Journal of Interconnection Networks 4(1), 103 (2003). Link, ISI, Google Scholar
- D. D. Kouvatsos and I. M. Mkwawa, Neighbourhood broadcasting schemes for Cayley graphs with background traffic, manuscript, on-line at http://www.cms.livjm.ac.uk/pgnet2003/submissions/Paper-52.pdf (2003) . Google Scholar
- IEICE Trans. Inf. & Syst. E 88D(1), 89 (2005). Google Scholar
K. Qiu , H. Meijer and S. G. Akl , Parallel routing and sorting on the pancake network, Proc. 3rd International Conference on Computing and Information,Lecture Notes in Computer Science, No. 497 (Springer-Verlag, Ottawa, 1991) pp. 360–371. Google Scholar- Information Processing Letters 39(3), 125 (1991). Crossref, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 22, 16 (1994). ISI, Google Scholar
K. Qiu , Broadcasting on the star and pancake interconnection networks, Proc. of the 9th IEEE International Parallel Processing Symposium (1995) pp. 660–665. Google ScholarK. Qiu and S. K. Das , A novel neighbourhood broadcasting algorithm on star graphs, IEEE 9th International Conference on Parallel and Distributed Systems (IC-PADS'02) (2002) pp. 37–41. Google ScholarK. Qiu and K. Das , A simple and unified neighbourhood broadcasting scheme for interconnection networks, Proc. of the 16th International Conference on Parallel and Distributed Computing and Systems (PDCS-2004) (2004) pp. 59–64. Google ScholarK. Qiu , A unified neighbourhood broadcasting scheme for multiple messages on interconnection networks, Proc. of the International Conference on Advances in Computer Science and Technology (ACST-2006) (2006) pp. 234–238. Google ScholarK. Qiu , Designing parallel algorithms on the star graph using orthogonal decomposition, Proc. 19th International Conference on Parallel and Distributed Computing Systems (2006) pp. 19–23. Google Scholar- Information Processing Letters 48, 237 (1993). Crossref, ISI, Google Scholar


