Method of reformulating static circuit optimization problems for reduced size, degeneracy and redundancy

Abstract

A method of pruning an initial timing graph for static optimization of a digital circuit includes examining a first group of nodes, which in turn include at least a first one of the nodes in the initial timing graph, to determine whether every node in the first group is prunable. The method further includes pruning the first group by pruning every node therein, if every node therein is prunable, and if the pruning would be beneficial. Furthermore, the method includes repeating the examining and pruning steps for a substantial number of additional groups of nodes, so as to create a pruned timing graph having enhanced numerical qualities and/or compactness compared to an initial timing graph. The pruning can be conducted on groups of more than one node at a time, or on only individual nodes at one time. Reduced size, and the benefits thereof, can be determined by a comparison of the number of nodes and number of directed edges before pruning, with the number of nodes and the number of directed edges after pruning, by summing the quantities before pruning and comparing the sum to the summed quantities after pruning, with or without weighting. Preferably, multistep pruning can be employed to first perform all pruning operations with a gain of a certain value, and to continue for gains of lower values. In an alternative method, an explicit representation of the problem as a timing graph is not employed, but the circuit optimization problem is restated in an analogous manner by pruning arrival times and manipulating constraints.