The design of integrated circuits is costly, time consuming, and complex. Automated synthesis techniques, verification that a design meets its specification, and testing that the final product is free of fabrication errors are three indispensable stages in the design process. The ultimate goal of our research is the design and implementation of efficient algorithms for VLSI synthesis, verification, and testing. A fundamental understanding of the underlying computational models is essential to achieve this goal. Therefore, an important part of our work is the development of the mathematical models for the design, evaluation, and application of these algorithms. We have chosen two application areas: asynchronous networks and testing.
Design and verification of asynchronous networks---networks that operate without a clock---is a research area of growing importance for several reasons. First, it is becoming increasingly more difficult to achieve proper synchronization among all the parts of clocked systems, as they become larger and more distributed. Unclocked systems do not suffer from such timing problems and, moreover, can be designed in a highly modular fashion. Second, unclocked systems can offer significant energy savings over clocked systems; this has become extremely important in a world of portable electronics. We develop methods and CAD tools for the design and analysis of asynchronous networks.
In deterministic testing --- where a test is pre-computed so as to detect a given set of faults --- we develop mathematical models of testing and diagnosis, realistic fault models, lower bounds on test lengths, and near-optimal tests. Random or pseudo-random tests are easier to generate than deterministic tests. Our work here provides mathematical models of random testing. The classical fault models assume the presence of at most one fault. In modern digital circuits, multiple faults are highly likely. We develop a methodology for modelling multiple faults and for generating and verifying tests for such faults. Our models and algorithms are directed towards the testing of embedded multi-port RAMs and CAMs.
Return to Maveric Research Group.