Browse Prior Art Database

Testing and Fault Tolerance of Multistage Interconnection Networks

IP.com Disclosure Number: IPCOM000131490D
Original Publication Date: 1982-Apr-01
Included in the Prior Art Database: 2005-Nov-11
Document File: 13 page(s) / 47K

Publishing Venue

Software Patent Institute

Related People

Dharma P. Agrawal: AUTHOR [+3]

Abstract

Test length is independent of network size in this simple, straightforward methodology for testing MINs. It requires only four test sequences for single-fault diagnosis.

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1982 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

Testing and Fault Tolerance of Multistage Interconnection Networks

Dharma P. Agrawal,

Wayne State University

Test length is independent of network size in this simple, straightforward methodology for testing MINs. It requires only four test sequences for single-fault diagnosis.

Advances in LSI and VLSI technology are encouraging greater use of multiple-processor systems with processing elements to provide computational parallelism and memory modules to store the data required by the PEs. A simple connection between the PE and MM is usually sufficient in a uniprocessor system, but a system with a large number of PEs and MMs requires a more complex data path.

Multistage interconnection networks, or MlNs, are useful in providing programmable data paths between functional modules in multiprocessor systems. The M I Ns are usually segmented into several stages, and the linkages between various stages are assigned so that any input can access any one of the outputs, and vice versa Each stage connects inputs to appropriate links of the next stage so that the cumulative effect of all stages satisfies inputoutput connection requirements.

These networks are usually implemented with simple modular switches, and several MlNs employing two-input two-output switching elements have been described in the literature. 1- 5 Permutation capability and other issues related to MlNs have also been widely covered, but little attention has been paid to the reliability of these networks. Since correct functioning of a multiple-processor system is dependent on the proper functioning of its interconnections, an MIN fault could lead to a catastrophic situation. But this can be easily avoided by taking necessary measures whenever a fault is detected.

In this article, we consider fault-detection-and-location techniques and fault-tolerant design schemes for a? class of MlNs implemented with 2 x 2 switching elements connecting a set of N PEs to N MMs. For simplicity, it is usually assumed that N is a power of two (N -- 2n or n = log2N) . Figure I illustrates the basic form and the two allowed states of a 2 x 2 SE. The logical level at the control input line decides whether it is in its straight (T) connected mode or exchange (X) state.

(Image Omitted: Figure 1. A switching element (a) with the control set at zero for a straight, or T. connection (b) and at one for an exchange, or X, connection (c).)

(Image Omitted: Figure 2. Baseline network for N = 8 (n = 3).)

Each stage of the MIN is implemented with N/2= 2n- ~ SEs; a three-stage network for N...