RESOURCE PLACEMENT WITH MULTIPLE ADJACENCY CONSTRAINTS IN K-ARY N-CUBES

被引:14
作者
RAMANATHAN, P
CHALASANI, S
机构
[1] UNIV WISCONSIN,DEPT COMP SCI,MADISON,WI 53706
[2] UNIV WISCONSIN,DEPT ELECT ENGN & COMP SCI,MADISON,WI 53706
基金
美国国家科学基金会;
关键词
RESOURCE ALLOCATION; MULTIPROCESSORS; HYPERCUBES; MESH CONNECTED COMPUTERS; INTERCONNECTION NETWORK; FAULT-TOLERANCE;
D O I
10.1109/71.382319
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The problem of placing resources in a k-ary n-cube (k > 2) is considered in this paper. For a given j greater than or equal to 1, resources are placed such that each nonresource node is adjacent to j resource nodes. We first prove that perfect j-adjacency placements are impossible in k-ary n-cubes if n < j < 2n. Then, we show that a perfect j-adjacency placement is possible in k-ary n-cubes when one of the following two conditions is satisfied: 1) if and only if j equals 2n and k is even, or 2) if 1 less than or equal to j less than or equal to n and there exist integers q and r such that q divides k and q(r) - 1 = 2n/j. In each case, we describe an algorithm to obtain perfect j-adjacency placements. We also show that these algorithms can be extended under certain conditions to place j distinct types of resources in a such way that each nonresource node is adjacent to a resource node of each type. For the cases when perfect j-adjacency placements are not possible, we consider approximate j-adjacency placements. We show that the number of copies of resources required in this case either approaches a theoretical lower bound on the number of copies required for any j-adjacency placement or is within a constant factor of the theoretical lower bound for large k.
引用
收藏
页码:511 / 519
页数:9
相关论文
共 50 条
  • [41] Fault-Free Hamiltonian Cycles Passing through Prescribed Edges in k-Ary n-Cubes with Faulty Edges
    Zhang, Shurong
    Zhang, Xianwen
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (02) : 434 - 443
  • [42] Hamiltonian Paths of k-ary n-cubes Avoiding Faulty Links and Passing Through Prescribed Linear Forests
    Yang, Yuxing
    Zhang, Lingling
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2022, 33 (07) : 1752 - 1760
  • [43] Optimally Embedding 3-Ary n-Cubes into Grids
    Fan, Wei-Bei
    Fan, Jian-Xi
    Lin, Cheng-Kuan
    Wang, Yan
    Han, Yue-Juan
    Wang, Ru-Chuan
    JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2019, 34 (02) : 372 - 387
  • [44] On the extraconnectivity of k-ary n-cube networks
    Gu, Mei-Mei
    Hao, Rong-Xia
    Liu, Jian-Bing
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2017, 94 (01) : 95 - 106
  • [45] Embedding long cycles in faulty k-ary 2-cubes
    Wang, Shiying
    Feng, Kai
    Zhang, Shurong
    Li, Jing
    APPLIED MATHEMATICS AND COMPUTATION, 2012, 218 (09) : 5409 - 5413
  • [46] CYCLE AND PATH EMBEDDING ON 5-ARY N-CUBES
    Lin, Tsong-Jie
    Hsieh, Sun-Yuan
    Huang, Hui-Ling
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2009, 43 (01): : 133 - 144
  • [47] Optimally Embedding 3-Ary n-Cubes into Grids
    Wei-Bei Fan
    Jian-Xi Fan
    Cheng-Kuan Lin
    Yan Wang
    Yue-Juan Han
    Ru-Chuan Wang
    Journal of Computer Science and Technology, 2019, 34 : 372 - 387
  • [48] Path embeddings in faulty 3-ary n-cubes
    Wang, Shiying
    Lin, Shangwei
    INFORMATION SCIENCES, 2010, 180 (01) : 191 - 197
  • [49] Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links
    Dong, Qiang
    Yang, Xiaofan
    Wang, Dajin
    INFORMATION SCIENCES, 2010, 180 (01) : 198 - 208
  • [50] Reliability of Augmented 3-Ary n-Cubes with Extra Faults
    Sun, Xueli
    Fan, Jianxi
    Cheng, Baolei
    Wang, Yan
    Zhou, Jingya
    JOURNAL OF INTERCONNECTION NETWORKS, 2023, 23 (02)