Title: Polynomial-time techniques for approximate timing analysis of asynchronous systems
Abstract: As designers face the limitations of synchronous circuits, there has been a renewed interest in asynchronous design techniques that use timing assumptions to obtain fast and low-overhead circuits. Since statistical variations in manufacturing conditions, operating conditions, etc. result in uncertainties in component delays in a chip, it is important to analyze asynchronous systems with uncertain delays to check for timing constraint violations, and to determine sufficient conditions for their correct operation. Unfortunately, exact timing analysis with uncertain component delays is computationally intractable in general. This thesis presents polynomial-time techniques for approximate timing analysis of asynchronous systems. Although the algorithms are conservative in the worst case, experiments indicate that they are fairly accurate in practice.
Three important problems in asynchronous timing analysis are addressed. First, a polynomial-time algorithm for computing bounds on signal propagation delays from each primary input to each gate in a combinational circuit is described. This has applications in determining input timing constraints for correct operation of asynchronous circuits. To improve the accuracy of simulation, a polynomial-time reconvergent fanout analysis technique is also proposed. As an application, a timing analysis tool for a class of asynchronous circuits is presented. Experiments indicate that the proposed algorithm is efficient and fairly accurate in practice.
Next, the problem of computing bounds on time separation of events is addressed. This has important applications in timing verification, analysis and optimization of asynchronous systems. A polynomial-time algorithm for analyzing choice-free systems with min and max timing constraints, but without repeated occurrences of events is first proposed. The algorithm is based on computing a convex over-approximation of the feasible region of a system of constraints. Experiments indicate that the algorithm is highly efficient and accurate in practice.
Finally, the time separations problem for choice-free systems with repeated events and min and max timing constraints is addressed. Tightly-coupled systems, a class of practical asynchronous systems, are characterized, and a polynomial-time algorithm for computing time separation bounds in tightly-coupled systems is proposed. To demonstrate the practicality of the approach, a complete asynchronous differential equation solver chip has been analyzed using the proposed algorithm.
Publication Year: 1998
Publication Date: 1998-01-01
Language: en
Type: book
Access and Citation
Cited By Count: 12
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot