AD-A255 013 ' •,,.,(

Our 1989-1991 research on Testing and Fault-Tolerant Design Techniques culminated in numerous results reflected in over 37 publications, a large number of presentations at national and international meetings and followup implementations in computer industry. Here is a brief overview of the most important projects. 1. Topological Testing. We have continued working on our new concept, topological testing, and demonstrated several applications in the area of multiprocessor testing. Topological testing uses graph theoretic optimization methods, such as the Traveling Salesman Problem, the Chinese Postman Problem, coloring, path covering and partitioning to minimize the test time. The topological testing techniques can be applied to test a system's behavior and its organization at each level of the system's hierarchy; namely, circuit, logic, register transfer, instruction and processor-memory-switch levels. Specifically, the topological testing approach was demonstrated by developing tests for the multistage interconnection network and the hypercube network. We have also developed optimal test sets for mesh networks and further increased a test coverage by including solutions for priority circuits