A timed automaton-based method for accurate computation of circuit delay in the presence of cross-talk Conference Paper uri icon


  • Springer-Verlag Berlin Heidelberg 1998. We present a timed automaton-based method for accurate computation of the delays of combinational circuits. In our method, circuits are represented as networks of timed automata, one per circuit element. The state space of the network represents the evolution of the circuit over time and delay is computed by performing a symbolic traversal of this state space. Based on the topological structure of the circuit, a partitioning of the network and a corresponding conjunctively decomposed OBDD representation of the state space is derived. The delay computation algorithm operates on this decomposed representation and, on a class of circuits, obtains performance orders of magnitude better than a non-specialized traversal algorithm. We demonstrate the use of timed automata for accurate modeling of gate delay and cross-talk. We introduce a gate delay model which accurately represents transistor level delays. We also construct a timed automaton that models delay variations due to cross-talk for two capacitively coupled wires. On a benchmark circuit, our algorithm achieves accuracy very close to that of a transistor level circuit simulator. We show that our algorithm is a powerful and accurate timing analyzer, with a cost significantly lower than transistor level circuit simulators, and an accuracy much higher than that of traditional timing analysis methods.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Taran, S., Khatri, S. P., Yovine, S., Brayton, R. K., & Sangiovanni-Vincentelli, A.

complete list of authors

  • Taşıran, S||Khatri, SP||Yovine, S||Brayton, RK||Sangiovanni-Vincentelli, A

publication date

  • January 1998