Patent ID: 6836753
Filing Date: 2004-12-28
Classification: G06F

Abstract:
A method of slack allocation within a timing graph, comprising the steps of:setting an initial edge time for each edge in the timing graph; setting a weight value for each edge in the timing graph; and iteratively performing the following steps: computing an amount of the available slack to be budgeted to each edge of the graph; for each edge having a weight greater than zero, if the computed slack is greater than a predetermined epsilon, then restore the edge time to that in an immediately preceding iteration, and if the computed slack is less than or equal to the predetermined epsilon, then saving a current edge time and setting a weight of the edge to zero; stopping the iterative steps if an amount of slack to allocate is less than the predetermined epsilon; determining a new budget for each edge; and incrementing the edge time for each edge by the corresponding new budget; until the iterative steps are stopped or a maximum number of iterations is performed.