Timing verification method for deterministic and stochastic networks and circuits
AssigneeUmm Al-Qura University
InventorFatih Kocan
Life of this patent
Estimating the term…
Abstract
The timing verification method for deterministic and stochastic networks and circuits is a computerized method that includes a non-enumerative path length analysis algorithm for deterministic and stochastic directed acyclic graphs (DAGs) with applications to timing verification of circuits, the algorithm computing statistical measures of path lengths without storing and/or manipulating the paths in such networks. The timing verification method is able to compute deterministic or probabilistic costs assigned to edges, vertices, or both.
Claims12
A computer-implemented timing verification method for deterministic and stochastic networks and circuits, comprising the steps of:
- forming a directed acyclic graph representing an electronic digital circuit, the graph having a first plurality of vertices connected by a second plurality of edges thereby creating paths which can be traversed along the directed acyclic graph;
- computing statistical length measures based on the paths to non-enumeratively determine a top K most critical paths of the electronic digital circuit;
- determining a first path delay timing cost for all of the electronic digital circuit based on the statistical measures computation of the top K most critical paths;
- and
- displaying a first display record verifying whether the first path delay timing cost is within a margin of a first specified timing performance requirement of the electronic digital circuit.
A computer software product, comprising a medium readable by a processor, wherein the medium is a non-transitory computer readable media, the medium having stored thereon a set of instructions for timing verification of deterministic and stochastic networks and circuits, the set of instructions including:
- (a) a first sequence of instructions which, when executed by the processor, causes said processor to form a directed acyclic graph representing an electronic digital circuit, said graph having a first plurality of vertices connected by a second plurality of edges thereby creating paths which can be traversed along said directed acyclic graph;
- (b) a second sequence of instructions which, when executed by the processor, causes said processor to compute statistical length measures based on said paths to non-enumeratively determine a top K most critical paths of said electronic digital circuit;
- (c) a third sequence of instructions which, when executed by the processor, causes said processor to determine a first path delay timing cost for all of said electronic digital circuit based on said statistical measures computation of said top K most critical paths;
- and
- (d) a fourth sequence of instructions which, when executed by the processor, causes said processor to display a first display record verifying whether said first path delay timing cost is within a margin of a first specified timing performance requirement of said electronic digital circuit.
Dependencies are inferred from the claim text.