ON THE MULTIPLE BRIDGE FAULT-DIAGNOSIS OF BASE-LINE MULTISTAGE INTERCONNECTION NETWORKS

This paper proposes new algorithms for diagnosing (detection, identifi cation and location) baseline multistage interconnection networks (MIN ) as one of the basic units in a massively parallel system. This is ac complished in the presence of single and multiple faults under a new f ault model. This model referred to as the geometric fault model, consi ders defective crossing connections which are located between adjacent stages, internally to the MIN (therefore, a Fault corresponds to a ph ysical bridge fault between two connections). It is shown that this ty pe of fault affects the correct geometry of the network, thus requirin g a different testing approach than previous methods. Initially, an al gorithm which detects the presence of bridge faults (both in the singl e and multiple Fault cases), is presented. For a single bridge Fault, the proposed algorithm locates the fault except in an unique pathologi cal case under which it is logically impossible to differentiate betwe en two equivalent locations of the fault (however, the switching eleme nt affected by this fault is uniquely located). The proposed algorithm requires log(2) N lest vectors to diagnose the MIN as fault free (whe re N is the number of input lines to the MIN). For fully diagnosing a single bridge fault, this algorithm requires at most 2 x log(2) N test s and terminates when multiple bridge Faults are detected. Subsequentl y, an algorithm which locates all bridge faults is given. The number o f required lest vectors is O(N). Fault location of each bridge fault i s accomplished in terms of the two lines in the bridge and the numbers of the stages between which it occurs. Illustrative examples are give n.