A FAMILY OF FAULT-TOLERANT ROUTING PROTOCOLS FOR DIRECT MULTIPROCESSOR NETWORKS

被引：97

作者：

GAUGHAN, PT ^{[1
]}

YALAMANCHILI, S ^{[1
]}

机构：

[1] GEORGIA INST TECHNOL,SCH ELECT & COMP ENGN,COMP SYST RES LAB,ATLANTA,GA 30332

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1995年 / 6卷 / 05期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1109/71.382317

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Our goal is to reconcile the conflicting demands of performance and fault-tolerance in interprocessor communication. To this end, we propose a pipelined communication mechanism-pipelined circuit-switching (PCS)-which is a variant of the well known wormhole routing (WR) mechanism. PCS relaxes some of the routing constraints imposed by WR and as a result enables routing behavior that cannot otherwise be realized. This paper presents a new class of adaptive routing algorithms-misrouting backtracking with m misroutes (MB-m). This class of routing algorithms is made possible by PCS. We provide an analysis of the performance and static fault-tolerant properties of MB-m. The results of an experimental evaluation of PCS and MB-3 are also presented. This methodology provides performance approaching that of WR, while realizing a level of resilience to static faults that is difficult to achieve with WR.

引用

页码：482 / 497

页数：16

共 26 条

[1]

Berman P., Gravano L., Sanz J., Pifarre G., Adaptive deadlock-and and livelock-free routing with all minimal paths in torus networks, Proc. 4th ACM Symp. Parallel Algorithms, (1992)

[2]

Borkar S., Cohn R., Cox G., Gross T., Kung H.T., Lam M., Levine M., Moore B., Moore W., Peterson C., Susman J., Sutton J., Urbanski J., Webb J., Supporting systolic and memory communication in iWarp, Proc. 17th Int. Symp. Comput. Architect., pp. 70-81, (1990)

[3]

Chen M.S., Shin K.G., Adaptive fault-tolerant routing in hypercube cube multicomputers, IEEE Trans. Comput., 39, (1990)

[4]

Depth-first search approach for fault-tolerant routing in hypercube cube multicomputers, IEEE Trans. Parallel and Distrib. Syst., 1, pp. 152-159, (1990)

[5]

Chien A.A., A cost and speed model for k-ary n-cube wormhole routers, Proc. Hot Interconn. Workshop, (1993)

[6]

Chien A.A., Im J.H.K., Planar-adaptive routing: Low-cost adaptive networks for multiprocessors, Proc. 19th int. Symp. Comput. Architect., 20, 2, pp. 268-277, (1992)

[7]

Chow E., Madan H.S., Peterson J.C., Grunwald D., Reed D., Hyperswitch network for the hypercube computer, Proc. 15th Annu. Symp. Comput. Architect., pp. 90-99, (1988)

[8]

Daily W.J., Virtual-channel flow control, IEEE Trans. Parallel, 3, pp. 194-205, (1992)

[9]

Daily W.J., Aoki H., Deadlock-free adaptive routing in multicomputer networks using virtual channels, IEEE Trans. Parallel, (1993)

[10]

Daily W.J., Seitz C.L., Deadlock-free message routing in multi-processor interconnection networks, IEEE Trans. Comput., C-36, pp. 547-553, (1987)

← 1 2 3 →