Browse Prior Art Database

A MULTEPATH HYBRID NETWORK

IP.com Disclosure Number: IPCOM000128010D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 10 page(s) / 34K

Publishing Venue

Software Patent Institute

Related People

S. C. Kothari: AUTHOR [+5]

Abstract

A fault-tolerant multistage interconnection network, called the Hybrid network, and a fault-tolerant control algorithm for this network are introduced. The novel feature of this network is the hybrid design that not only has connections between switching ele-ments of successive stages, but also between switching elements of the same stage. The control algorithm is a simple modification of the destination tag algorithm, but it provides for fault-tolerance and is dynamic in nature. It is shown that the hybrid design technique is effective in reducing hardware, improving fault-tolerance and giving better performance than some other fault-tolerant networks.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A MULTEPATH HYBRID NETWORK

S. C. Kothari G. M. Prabhu Robert Roberts

Technical Report # 85-22 August 1985 Department of Computer Science Iowa State University Ames, IA 50010 MIS Program Division of Management University of Oklahoma Norman, OK 73019

A MULTIPATH HYBRm NETWORK S. C. Kothari ++ G. M. Prabhu ++ Robert Roberts * Department of Computer Science Iowa State University Ames. IA 54010 MIS Program Division of Management University of Oklahoma Norman, OK 73019

Abstract

A fault-tolerant multistage interconnection network, called the Hybrid network, and a fault- tolerant control algorithm for this network are introduced. The novel feature of this network is the hybrid design that not only has connections between switching ele-ments of successive stages, but also between switching elements of the same stage. The control algorithm is a simple modification of the destination tag algorithm, but it provides for fault-tolerance and is dynamic in nature. It is shown that the hybrid design technique is effective in reducing hardware, improving fault-tolerance and giving better performance than some other fault-tolerant networks.

Keywords: Fault-tolerance, hybrid design, multistage interconnection network. 2

1. Introduction

In multiprocessor systems, interconnection networks are used to provide connections from processors to processors or from processors to memory modules [1, 2). Multistage interconnection networks (MINs) have been introduced as a cost-effective way to provide high bandwidth interconnection networks in multiprocessor systems (7, 8). An intercon-nection network is a crucial component of a multiprocessor system, affecting both its relia-bility and throughput. MINs are normally designed for N = 2 inputs and outputs: the parameter N is called the size of the network. A MIN consists of several stages of switching elements with interconnections between two successive stages. With the advancement of VLSI, several MINs such as the Omega network [3). the Baseline network [6), etc., have been proposed for special purpose applications. These MIN's are generally referred to as Delta networks and have a destination tag based routing algorithm (DTA) (S). The DTA is distributed in nature, i.e., the routing is implemented at the switch level by using "smart" switches. The DTA employs a simple control scheme to achieve high speed switching, thus contributing to the overall speed of the system. Another important feature of these MINs is that they have the unique path property (UPP), i.e., the existence of a unique path between any input-output pair. However,. the unique path property .may not be desirable for two rea-sons. First, since there is a chance that two desired connections require a common link for routing, one or more connections may be blocked. In such a case, a conflict is said to occur. The high probability of occurrence of a conflict lowers the performance of th...