We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 20 Issue 6
November  2005
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Ji-Peng Zhou. Fault-Tolerant Wormhole Routing with 2 Virtual Channels in Meshes[J]. Journal of Computer Science and Technology, 2005, 20(6): 822-830.
Citation: Ji-Peng Zhou. Fault-Tolerant Wormhole Routing with 2 Virtual Channels in Meshes[J]. Journal of Computer Science and Technology, 2005, 20(6): 822-830.
shu

Fault-Tolerant Wormhole Routing with 2 Virtual Channels in Meshes

  • Department of Computer Science, Jinan University, Guangzhou 510632, P.R. China

More Information
  • Received Date: October 31, 2004
  • Revised Date: May 27, 2005
  • Published Date: November 14, 2005
    Abstract
  • In wormhole meshes, a reliable routing is supposed to be deadlock-free and fault-tolerant. Many routingalgorithms are able to tolerate a large number of faults enclosed by rectangular blocks or special convex, none of them, however, is capable of handling two convex fault regions with distance two by using only two virtual networks. In this paper, a fault-tolerant wormhole routing algorithm is presented to tolerate the disjointed convex faulty regions with distance two or no less, which do not contain any nonfaulty nodes and do not prohibit any routing as long as nodes outside faulty regions are connected in the mesh network. The processors' overlapping along the boundaries of different fault regions is allowed. The proposed algorithm, which routes the messages by X - Y routing algorithm in fault-free region, can tolerate convex fault-connected regions with only two virtual channels per physical channel, and is deadlock- and livelock-free. The proposed algorithm can be easily extended to adaptive routing.
    • FullText(HTML)
    • References (16)
  • [1]
    Allen F et al. A Version for Protein Science Using Petaflop Supercomputer. IBM Systems J., 2001, 40: 310--327.
    [2]
    Mukherjee S S, Bannon R, Lang S, Spink A. The Alpha 21364 network architecture. IEEE Micro., 2002, 17(1): 26--35.
    [3]
    Scott S L. Synchronization and communication in the T3E multiprocessor. In Proc. ASPLOS 7, Oct. 1996, pp.26--36.
    [4]
    Laudon J, Lenoski D. The SGI Origin: A CCNUMA highly scalable server. In Proc. Int. Symp. Computer Architecture, 1997, pp.241--351.
    [5]
    Boppana R V, Chalasani S. Fault-tolerant wormhole routing algorithms for mesh networks. IEEE Trans. Computers, 1995, 44(7): 848--864.
    [6]
    Chalasani S, Boppana R V. Communication in multicomputers with nonconvex faults. IEEE Trans. Computers, 1997, 46(5): 616--622.
    [7]
    Kim S P, Han T. Fault-tolerant wormhole routing in mesh with overlapped solid fault regions. Parallel Computing, 1997, 23: 1937--1962.
    [8]
    Sui P H, Wang S D. An improved algorithm for fault-tolerant wormhole routing in meshes. IEEE Trans. Computers, 1997, 46(9): 1040--1042.
    [9]
    Boppana R V, Chalasani S. Fault-tolerant communication with partitioned dimension-order routers. IEEE Trans. Parallel and Distributes Systems , 1999, 10(10): 1026--1039.
    [10]
    Zhou J P, Lau F C M. Adaptive fault-tolerant wormhole routing in 2D meshes. In Proc. 15th Annual International Parallel & Distributed Processing Symposium, Hyatt Regency, San Francisco Airport, April 23--27, 2001, pp.56--63.
    [11]
    Zhou J P, Lau F C M. Fault-tolerant wormhole routing in 2D meshes. In Proc. 2000 International Symposium on Parallel Architectures, Algorithms and Networks, Dallas/Richandson, Texas, USA, Dec. 7--9, 2000, pp.94--101.
    [12]
    Tsai M J. Fault-tolerant routing in wormhole meshes. Journal of Interconnection Networks, 2003, 4(4): 463--495.
    [13]
    Ho C T, Stockmeyer L. A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers. IEEE Trans. Computers, 2004, 53(4): 427--438.
    [14]
    Wu J. A fault-tolerant and deadlock-free routing in 2D meshes based on odd-even turn model. IEEE Trans. Computers, 2003, 52(9): 1154--1169.
    [15]
    Zhou J P, Lau F C M. Fault-tolerant wormhole routing algorithm in 2D meshes without virtual channels. In Parallel and Distributed Processing and Applications, Lecture Notes in Computer Science 3358, Cao J N, Yang L T, Lau F (eds.), Springer-Verlag, 2004, pp.688--297.
    [16]
    Wang D. A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in meshes. IEEE Trans. Computers, 2003, 52(3): 310--320.
    • Relative Articles

  • Related Articles

    [1]LIU Songyan, MAO Zhigang, YE Yizheng. Implementation of Java Card Virtual Machine[J]. Journal of Computer Science and Technology, 2000, 15(6): 591-596.
    [2]XU Xiaofei, YE Dan, LI Quanlong, ZHAN Dechen. Dynamic Organization and Methodology for Agile Virtual Enterprises[J]. Journal of Computer Science and Technology, 2000, 15(4): 368-375.
    [3]GAO Shuming, WAN Huagen, PENG Qunsheng. Constraint-Based Virtual Solid Modeling[J]. Journal of Computer Science and Technology, 2000, 15(1): 56-63.
    [4]HE Taosong. Volumetric Virtual Environments[J]. Journal of Computer Science and Technology, 2000, 15(1): 37-46.
    [5]Cai Yong, Heng Phengann, Wu Enhua, Liu Xuehui, Li Hongju, Sun Qingjie. An Image-Based Virtual Reality Prototype System[J]. Journal of Computer Science and Technology, 1998, 13(5): 475-480.
    [6]Zhang Qiong, Shi Jiaoring. Acoustic Simulation with Dynamic Mechanisms in Virtual Reality[J]. Journal of Computer Science and Technology, 1998, 13(3): 285-288.
    [7]Chang No Yoon, Myung Hwan Chi, Heedong Ko, Jongsei Park. Applying Virtual Reality to Molecular Graphics System[J]. Journal of Computer Science and Technology, 1996, 11(5): 507-511.
    [8]Min Youli, Min Yinghua. A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes[J]. Journal of Computer Science and Technology, 1995, 10(6): 536-544.
    [9]Wang Xiaoming, Yang Qiaolin. Using Virtual ATE Model to Migrate Test Programs[J]. Journal of Computer Science and Technology, 1995, 10(4): 289-297.
    [10]Deng Yaping, Chen Tinghuai. A Reliable and Fault-Tolerant Interconnection Network[J]. Journal of Computer Science and Technology, 1990, 5(2): 117-126.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (17) PDF downloads (1326) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return