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

A method of restating an initial statement of a circuit optimization problem for static optimization of a digital circuit, the problem statement having a plurality of arrival times of signals in the digital circuit and a plurality of constraints, said method comprising the steps of:

• (a) examining all those of the constraints in which at least a first group of the arrival times occur to determine if said constraints in which said first group of arrival times occur can be algebraically manipulated in a manner corresponding to pruning of said first group of arrival times;
• (b) manipulating said constraints in which said first group of arrival times occur if said constraints in which said first group of arrival times occur can be so manipulated as to prune said first group of arrival times, and if said manipulation would be beneficial;
• and
• (c) repeating steps (a) and (b) for a substantial number of additional arrival time groups so as to create a pruned restatement of the optimization problem having enhanced qualities with respect to the initial statement of the optimization problem, said enhanced qualities comprising at least one of numerical qualities and compactness.

A method for static optimization of a digital circuit, said method comprising the steps of:

• (a) creating a description of the digital circuit;
• (b) creating an initial timing graph based on the circuit description of the digital circuit, the initial timing graph having a plurality of nodes corresponding to arrival times of signals in the digital circuit and a plurality of directed edges corresponding to propagate segments in the digital circuit, those of the edges directed into a given node being referred to as fan-ins for that node and being connected to associated fan-in nodes, those of the edges directed out of the given node being referred to as fan-outs for that node and being connected to associated fan-out nodes;
• (c) pruning said initial timing graph, said pruning in turn comprising the steps of:
• (c-1) examining a first group of the nodes including at least a first one of the nodes in the initial timing graph to determine if every node of said first group is pruneable;
• (c-2) pruning said first group by pruning every node of said first group if every node of said first group is pruneable, and if said pruning would be beneficial;
• and
• (c-3) repeating steps (c-1) and (c-2) for a substantial number of additional groups including at least additional ones of the nodes to create a pruned timing graph having enhanced qualities with respect to the initial timing graph, said enhanced qualities comprising at least one of numerical qualities and compactness;
• (d) listing timing constraints corresponding to the pruned graph;
• (e) adding additional constraints and objective functions as necessary;
• and
• (f) optimizing the circuit based on the timing constraints corresponding to said pruned graph.

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for pruning an initial timing graph for static optimization of a digital circuit, the initial timing graph having, a plurality of nodes corresponding to arrival times of signals in the digital circuit and a plurality of directed edges corresponding to propagate segments in the digital circuit, those of the edges directed into a given node being referred to as fan-ins for that node and being connected to associated fan-in nodes, those of the edges directed out of the given node being referred to as fan-outs for that node and being connected to associated fan-out nodes, said method steps comprising:

• (a) examining a first group of the nodes including at least a first one of the nodes in the initial timing graph to determine if every node of said first group is pruneable;
• (b) pruning said first group by pruning every node of said first group if every node of said first group is pruneable, and if said pruning would be beneficial;
• and
• (c) repeating steps (a) and (b) for a substantial number of additional groups including at least additional ones of the nodes to create a pruned timing graph having enhanced qualities with respect to the initial timing graph, said enhanced qualities comprising at least one of numerical qualities and compactness.

A method for static optimization of a digital circuit, said method comprising the steps of:

• (a) creating a description of the digital circuit;
• (b) creating an initial problem statement having a plurality of arrival times of signals in the digital circuit and a plurality of constraints, said initial problem statement being based on said description of the digital circuit;
• (c) restating said initial problem statement, said restating of said initial problem statement in turn comprising the steps of:
• (c-1) examining all those of the constraints in which at least a first group of the arrival times occur to determine if said constraints in which said first group of arrival times occur can be algebraically manipulated in a manner corresponding to pruning of said first group of arrival times;
• (c-2) manipulating said constraints in which said first group of arrival times occur if said constraints in which said first group of arrival times occur can be so manipulated as to prune said first group of arrival times, and if said manipulation would be beneficial;
• and
• (c-3) repeating steps (c-1) and (c-2) for a substantial number of additional arrival time groups so as to create a pruned restatement of the optimization problem having enhanced qualities with respect to the initial statement of the optimization problem, said enhanced qualities comprising at least one of numerical qualities and compactness;
• (d) adding additional constraints and objective functions as necessary;
• and
• (e) optimizing the digital circuit based on said timing constraints corresponding to said restated problem statement.

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for restating an initial statement of a circuit optimization problem for static optimization of a digital circuit, the problem statement having a plurality of arrival times of signals in the digital circuit and a plurality of constraints, said method steps comprising:

• (a) examining all those of the constraints in which at least a first group of the arrival times occur to determine if said constraints in which said first group of arrival times occur can be algebraically manipulated in a manner corresponding to pruning of said first group of arrival times;
• (b) manipulating said constraints in which said first group of arrival times occur if said constraints in which said first group of arrival times occur can be so manipulated as to prune said first group of arrival times, and if said manipulation would be beneficial;
• and
• (c) repeating steps (a) and (b) for a substantial number of additional arrival time groups so as to create a pruned restatement of the optimization problem having enhanced qualities with respect to the initial statement of the optimization problem, said enhanced qualities comprising at least one of numerical qualities and compactness.