Optimized testing of meshes

Efficient testing techniques for two-dimensional mesh interconnection networks are presented. The tests cover faults in the data paths and the control circuitry, including faults in the arbitration logic of the switches. Testing for the resolution of the conflicts is important for ensuring the correct functioning of the interconnection network, since a fault in the arbitration logic may cause the loss of packets. Modeling conflict resolution as a graph coloring the approach optimizes the testing time by parallelizing the tests for different nodes. The testing time is constant, independent of the size of the parallel network, except for the routing tests. The proposed methods are not implementation specific and can be applied to any design with a mesh topology. However, for some specific designs only a subset of tests might be needed, depending on the type of communication or control scheme. The novel approach to the minimization of the conflict tests is twofold: it can be used to test the conflicts; it also gives a method for controlling each input of a switch and observing each output of the switch such that any test at each level can be applied to as many nodes as possible simultaneously