One-to-All Broadcasting in Petersen-Torus Networks for SLA and MLA Models

ETRI Journal

关键词: parallel processing;    interconnection network;    Petersen torus;    Broadcasting;   

Others  :  1185819
DOI  :  10.4218/etrij.09.0208.0418

【 摘 要 】

In a network, broadcasting is the dissemination of a message from a source node holding a message to all the remaining nodes through a call. This letter proposes a one-to-all broadcasting algorithm in the Petersen-torus network PT(n, n) for the single-link-available and multiple-link-available models. A PT(n, n) is a regular network whose degree is 4 and number of nodes is 10n², where the Petersen graph is set as a basic module, and the basic module is connected in the form of a torus. A broadcasting algorithm is developed using a divide-and-conquer technique, and the time complexity of the proposed algorithm approximates n+4, the diameter of PT(n, n), which is the lower bound of the time complexity of broadcasting.

   

【 参考文献 】

• [1]R. Elsasser and T. Sauerwald, "Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs," STACS, Lecture Notes in Computer Science, vol. 4393, 2007, pp. 163-174.
• [2]Z. Shen, "A Generalized Broadcasting Schema for the Mesh Structures," Applied Mathematics and Computation, vol. 186, 2007, pp. 1293-1310.
• [3]Y.J. Tsai and P.K. McKinley "A Broadcasting Algorithm for ALL-Port Wormhole-Routed Torus Networks," IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 8, 1996, pp. 876-885.
• [4]J.-Y.L. Park and H.-A. Choi, "Circuit-Switched Broadcasting in Torus and Mesh Networks," IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 2, 1996, pp. 184-190.
• [5]S.-K. Lee and J.-Y. Lee, "Optimal Broadcast in α-Port Wormhole-Routed Mesh Networks," Proc. Int’l Conf. Parallel and Distributed Systems, 1997, pp. 109-114.
• [6]S.Y. Wang and Y.C. Tseng "Algebraic Foundations and Broadcasting Algorithm for Wormhole-Routed All-Port Tori," IEEE Trans. Computer, vol. 49, no. 3, Mar. 2000, pp. 246-258.
• [7]J.H. Seo, H.O. Lee, and M.S. Jang, "Petersen-Torus Networks for Multicomputer Systems," Int’l Conf. of NCM, vol. 1, Sept. 2008, pp. 567-571.
• [8]J.H. Seo, H.O. Lee, and M.S. Jang, "Optimal Routing and Hamiltonian Cycle in Petersen-Torus Networks," ICCIT, vol. 2, Nov. 2008, pp. 303-308.