World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ON A UNIFIED NEIGHBOURHOOD BROADCASTING SCHEME FOR INTERCONNECTION NETWORKS

    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

    • S. B. Akers and B. Krishnamurthy, IEEE Transaction on Computers c 38(4), 555 (1989). Crossref, ISIGoogle 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
    • S. G. Akl, K. Qiu and I. Stojmenović, Networks 23, 215 (1993). Crossref, ISIGoogle 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
    • C.-C. Chen and J. Chen, IEEE Transactions on Parallel and Distributed Systems 8(12), 1196 (1997). Crossref, ISIGoogle Scholar
    • W.-K. Chiang and R.-J. Chen, Information Processing Letters 56, 259 (1995). ISIGoogle Scholar
    • D. S. Cohen and M. Blum, Discrete Applied Math. 61(2), 105 (1995). Crossref, ISIGoogle Scholar
    • T. H.   Gormen , C. E.   Leiserson and R. L.   Rivest , Introduction to Algorithms ( The MIT Press , Cambridge, Massachusetts , 1990 ) . Google Scholar
    • M. Cosnard and A. Ferreira, Parallel Processing Letters 1, 103 (1991). Link, ISIGoogle Scholar
    • K. Day and A. Tripathi, IEEE Transactions on Parallel and Distributed Systems 5(1), 31 (1994). Crossref, ISIGoogle 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 Scholar
    • G. Fertin and A. Raspaud, k-Neighbourhood broadcasting, 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'0l) (2001) pp. 133–146. Google Scholar
    • S. Fujita, S. Perennes and J. G. Peters, Parallel Processing Letters 8(2), 189 (1998). LinkGoogle 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
    • S. Fujita, Journal of Interconnection Networks 4(4), 419 (2003). Link, ISIGoogle Scholar
    • W. H. Gates and C. H. Papadimitriou, Discrete Math. 27, 47 (1979). Crossref, ISIGoogle Scholar
    • M. H. Heydari and I. H. Sudborough, J. Algorithms 25(1), 67 (1997). Crossref, ISIGoogle Scholar
    • S. Latifi and P. K. Srimani, Parallel Computing 24, 1263 (1998). Crossref, ISIGoogle 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
    • I. M. Mkwawa and D. D. Kouvatsos, Journal of Interconnection Networks 4(1), 103 (2003). Link, ISIGoogle 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
    • S. Omura, H. Zheng and K. Wada, 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
    • K. Qiu, H. Meijer and S. G. Akl, Information Processing Letters 39(3), 125 (1991). Crossref, ISIGoogle Scholar
    • K. Qiu, S. G. Akl and H. Meijer, Journal of Parallel and Distributed Computing 22, 16 (1994). ISIGoogle 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 Scholar
    • K. 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 Scholar
    • K. 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 Scholar
    • K. 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 Scholar
    • K. 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
    • J. P. Sheu, W. H. Liaw and T. S. Chen, Information Processing Letters 48, 237 (1993). Crossref, ISIGoogle Scholar