Abstract

We present an approach for fault detection in layered interconnection networks (LINs). An LIN is a generalized multistage interconnection network commonly used in reconfigurable systems; the nets (links) are arranged in sets (referred to as layers) of different size. Switching elements (made of simple switches such as transmission-gate-like devices) are arranged in a cascade to connect pairs of layers. The switching elements of an LIN have the same number of switches, but the switching patterns may not be uniform. A comprehensive fault model for the nets and switches is assumed at physical and behavioral levels. Testing requires configuring the LIN multiple times. Using a graph approach, it is proven that the minimal set of configurations corresponds to the node disjoint path sets. The proposed approach is based on two novel results in the execution of the network flow algorithm to find node disjoint path sets, while retaining optimality in the number of configurations. These objectives are accomplished by finding a feasible flow such that the maximal degree can be iteratively decreased, while guaranteeing the existence of an appropriate circulation. Net adjacencies are also tested for possible bridge faults (shorts). To account for 100 percent fault coverage of bridge faults a postprocessing algorithm may be required; bounds on its complexity are provided. The execution complexity of the proposed approach (inclusive of test vector generation and post-processing) is O(N4WL), where N is the total number of nets, W is the number of switches per switching element, and L is the number of layers. Extensive simulation results are provided.

Department(s)

Electrical and Computer Engineering

Sponsor(s)

ITC Endowment

Comments

This research supported in part by the ITC endowment.

Keywords and Phrases

Fault Tolerance; Fault Detection; Reconfigurable System; Layered Interconnection Networks; Network Flow; Switch; Algorithms; Computational Complexity; Computer Simulation; Failure Analysis; Graph Theory; Integrated Circuit Testing; Multistage Interconnection Networks; Network Flow Algorithm; Switching Elements; Interconnection Networks

International Standard Serial Number (ISSN)

0018-9340

Document Type

Article - Journal

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 2004 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jun 2004

Download

Full Text Link

Share

 
COinS