Adaptive message routing in a class of fault-tolerant multistage interconnection networks

	Adaptive message routing in a class of fault-tolerant multistage interconnection networks
	Zhou, YQ; Min, YH
	1997-07-01
发表期刊	COMPUTERS & ELECTRICAL ENGINEERING
ISSN	0045-7906
卷号	23 期号:4 页码:239-247
摘要	Multistage interconnection networks (MINs) are often used to provide interconnections in multiprocessor systems. A unique path MIN usually has lower hardware complexity and simple control algorithm, but it lacks fault-tolerance. This paper proposes a class of multipath MINs,which are obtained by adding auxiliary links at the final stage in quad tree networks so that they can provide more paths between each source-destination pair, and presents their routing algorithm which is both destination tag based and adaptive. Starting with the routing: tag for the minimum path between a given source-destination pair, the routing algorithm uses a set of rules to select switches and modify routing tag. In addition to trying the auxiliary link when both of the output links are unavailable, the second output link is tried before the auxiliary link when the first output link is unavailable. This feature distinguishes the proposed routing algorithm from the one for quad tree networks and makes better use of all the possible paths between the given source-destination pair. At the end of this paper, an index of performance called capacity is introduced to compare different kinds of MINs. Comparison shows that the proposed MINs have better capacity than quad tree networks. (C) 1997 Elsevier Science Ltd.
关键词	communication fault-tolerance multistage interconnection networks parallel and distributed processing
收录类别	SCI
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Interdisciplinary Applications ; Engineering, Electrical & Electronic
WOS记录号	WOS:A1997XY28000004
出版者	PERGAMON-ELSEVIER SCIENCE LTD
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13262
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhou, YQ
作者单位	CHINESE ACAD SCI, INST COMP TECHNOL, BEIJING 100080, PEOPLES R CHINA
推荐引用方式 GB/T 7714	Zhou, YQ,Min, YH. Adaptive message routing in a class of fault-tolerant multistage interconnection networks[J]. COMPUTERS & ELECTRICAL ENGINEERING,1997,23(4):239-247.
APA	Zhou, YQ,&Min, YH.(1997).Adaptive message routing in a class of fault-tolerant multistage interconnection networks.COMPUTERS & ELECTRICAL ENGINEERING,23(4),239-247.
MLA	Zhou, YQ,et al."Adaptive message routing in a class of fault-tolerant multistage interconnection networks".COMPUTERS & ELECTRICAL ENGINEERING 23.4(1997):239-247.