Comprehensive testing of multistage interconnection networks
Antoine N. Mourad, Banu Özden, Miroslaw Malek · IEEE Transactions on Computers · 1991
The authors present efficient methods for testing packet-switched multistage interconnection networks. In addition to testing the data paths and routing capabilities, tests for detecting faults in the control circuitry including the conflict resolution capabilities are provided. Using a general model of the switch, testing sequences are constructed for the internal functions of the f*f switch requiring only O(f/sup 2/2/sup f/) tests in the case of round-robin priority and O(f2/sup f-1/) in the case of fixed priority (f is usually a constant that is less than or equal to eight). Algorithms are then presented to test the entire network using at most twice the number of tests needed to test a switch, independently of the network size, which results in O(log N) testing time for an N-processor network. It is shown that the method achieves higher coverage and several-orders-of-magnitude reduction in the testing time of complex multiprocessor systems compared to previous methods.>