Embedding meshes/tori in faulty crossed cubes

被引：29
作者：
Yang, Xiaofan [1 ]
Dong, Qiang [1 ]
Tang, Yuan Yan [1 ,2 ]
机构：
[1] Chongqing Univ, Coll Comp Sci, Chongqing 400044, Peoples R China
[2] Hong Kong Baptist Univ, Dept Comp Sci, Kowloon, Hong Kong, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 14-15期
关键词：
Interconnection networks; Crossed cube; Graph embedding; Mesh; Torus; Fault-tolerance; CONDITIONAL LINK FAULTS; HAMILTONIAN CYCLES; PATH; FAMILY;
D O I：
10.1016/j.ipl.2010.04.007
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The crossed cube is an important variant of the hypercube which is the most popular interconnection network for parallel processing. This paper is concerned with the problem of embedding meshes/tori in faulty crossed cubes. We reduce this mesh/tori embedding problem to the problem of embedding paths/cycles in faulty crossed cubes. Then, by exploiting the fault-tolerant pancyclicity of crossed cubes of lower dimension, several schemes for embedding 2D or 3D meshes/tori in faulty crossed cubes are proposed. All of these embeddings have small dilations and small congestions. The obtained results show that the parallel algorithms with mesh/torus task graphs can be efficiently executed on faulty crossed cubes. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：559 / 564
页数：6
相关论文
共 21 条
  • [1] Conditional fault diameter of crossed cubes
    Chang, Chien-Ping
    Wu, Chia-Ching
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2009, 69 (01) : 91 - 99
  • [2] Edge congestion and topological properties of crossed cubes
    Chang, CP
    Sung, TY
    Hsu, LH
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2000, 11 (01) : 64 - 80
  • [3] Diestel R., 2005, GRAPH THEORY, VThird
  • [4] Embedding a family of disjoint multi-dimensional meshes into a crossed cube
    Dong, Qiang
    Yang, Xiaofan
    Zhao, Juan
    [J]. INFORMATION PROCESSING LETTERS, 2008, 108 (06) : 394 - 397
  • [5] Embedding a family of disjoint 3D meshes into a crossed cube
    Dong, Qiang
    Yang, Xiaofan
    Zhao, Juan
    Tang, Yuan Yan
    [J]. INFORMATION SCIENCES, 2008, 178 (11) : 2396 - 2405
  • [6] THE CROSSED CUBE ARCHITECTURE FOR PARALLEL COMPUTATION
    EFE, K
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (05) : 513 - 524
  • [7] Embedding meshes into crossed cubes
    Fan, Jianxi
    Jia, Xiaohua
    [J]. INFORMATION SCIENCES, 2007, 177 (15) : 3151 - 3160
  • [8] Complete path embeddings in crossed cubes
    Fan, Jianxi
    Jia, Xiaohua
    Lin, Xiaola
    [J]. INFORMATION SCIENCES, 2006, 176 (22) : 3332 - 3346
  • [9] Optimal path embedding in crossed cubes
    Fan, JX
    Lin, XL
    Jia, XH
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (12) : 1190 - 1200
  • [10] Embedding fault-free cycles in crossed cubes with conditional link faults
    Fu, Jung-Sheng
    Hung, Hao-Shun
    Chen, Gen-Huey
    [J]. JOURNAL OF SUPERCOMPUTING, 2009, 49 (02) : 219 - 233
123