Node-to-Set Disjoint-Path Routing in Hierarchical Cubic Networks

被引：20

作者：

Bossard, Antoine ^{[1
]}

Kaneko, Keiichi ^{[1
]}

机构：

[1] Tokyo Univ Agr & Technol, Grad Sch Engn, Tokyo, Japan

来源：

COMPUTER JOURNAL | 2012年 / 55卷 / 12期

基金：

日本学术振兴会;

关键词：

interconnection network; algorithm; parallel processing; hypercube; HCN; HYPERCUBES;

D O I：

10.1093/comjnl/bxr137

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Hypercubes are a simple topology frequently used as interconnection network of parallel systems. However, hypercubes connecting a significant number of nodes also have an impractically high number of edges. To address this issue, Ghose and Desai introduced a new topology, hierarchical cubic networks, containing almost half many edges than a hypercube of the same size. In this paper, we describe a node-to-set disjoint-path routing algorithm in a hierarchical cubic network HCN(n) finding node-disjoint paths between one source node and k (k < n+1) destination nodes in O(knlog k) time complexity. Generated paths have lengths of at most 3n+k+3.

引用

页码：1440 / 1446

页数：7

共 14 条

[1]

Bland A.S., 2009, P CRAY US GROUP C CO

[2]

Bossard A, 2011, PROCEEDINGS OF THE FOURTH INTERNATIONAL C* CONFERENCE ON COMPUTER SCIENCE AND SOFTWARE ENGINEERING 2011 (C3S2E '11), P51

[3] Node-to-set disjoint-path routing in perfect hierarchical hypercubes [J].

Bossard, Antoine ;

Kaneko, Keiichi ;

Peng, Shietung .

PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE (ICCS), 2011, 4 :442-451

[4] Topological properties of hierarchical cubic networks [J].

Chiang, WK ;

Chen, RJ .

JOURNAL OF SYSTEMS ARCHITECTURE, 1996, 42 (04) :289-307

[5] PROPERTIES AND PERFORMANCE OF FOLDED HYPERCUBES [J].

ELAMAWY, A ;

LATIFI, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1991, 2 (01) :31-42

[6] THE TWISTED N-CUBE WITH APPLICATION TO MULTIPROCESSING [J].

ESFAHANIAN, AH ;

NI, LM ;

SAGAN, BE .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (01) :88-93

[7]

Ford L.R., 1956, Canadian journal of Mathematics, V8, P399, DOI 10.4153/CJM-1956-045-5

[8] Node-disjoint paths and related problems on hierarchical cubic networks [J].

Fu, JS ;

Chen, GH ;

Duh, DR .

NETWORKS, 2002, 40 (03) :142-154

[9] HIERARCHICAL CUBIC NETWORKS [J].

GHOSE, K ;

DESAI, KR .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1995, 6 (04) :427-435

[10]

Gu QP, 1997, IEICE T INF SYST, VE80D, P425

← 1 2 →