Testing layered interconnection networks

This paper presents an approach for fault detection in layered interconnection networks (LINs). A 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. A comprehensive fault model for the nets and switches is assumed at physical and behavioral levels. Testing requires to configure the LIN multiple times. Using a graph approach, it is proved that the minimal set of configurations corresponds to the node disjoint path sets. The proposed approach is based on two novel results inn 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 art appropriate circulation. Net adjacencies are also tested for possible bridge faults (shorts). To account for 100 % fault coverage of bridge faults a post-processing 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(N⁴W L), 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.