Method and apparatus for formula area and delay minimization
AssigneeLSI Logic Corporation
InventorsAlexander Andreev, Ranko Scepanovic, Anatoli Bolotov
Life of this patent
Estimating the term…
Abstract
The present invention is a method and apparatus for optimizing the design of a combinational circuit. The method includes constructing a circuit sheaf for the combinational circuit and then performing vector optimization with domination. In the preferred embodiment, a complete BDD B is determined and, from that, a list of F-sets is computed. If the combinational circuit includes cells other than NOT, AND and XOR cells, the circuit is first transformed such that it only has those types of cells.
Claims12
A method for optimizing the design of a combinational circuit, said method comprising the following steps:
- a. Constructing a circuit sheaf for a combinational circuit by:
- graphing the combinational circuit, replacing an edge in the graph with plural new inputs, each of said plural new inputs connecting to one of plural new circuits, and then connecting together inputs for the plural new circuits to form a modified combinational circuit;
- and
- b. performing vector optimization with domination, in which:
- subcircuits are identified that perform a function realized by an output pin of a cell within the modified combinational circuit, quality vectors are associated with each of said subcircuits, and subcircuits associated with inferior quality vectors are replaced with subcircuits associated with superior quality vectors.
A system for optimizing the design of a combinational circuit, said system comprising the following steps:
- a. means for constructing a circuit sheaf for a combinational circuit by:
- graphing the combinational circuit, replacing an edge in the graph with plural new inputs, each of said plural new inputs connecting to one of plural new circuits, and then connecting together inputs for the plural new circuits to form a modified combinational circuit;
- and
- b. means for performing vector optimization with domination, in which:
- subcircuits are identified that perform a function realized by an output pin of a cell within the modified combinational circuit, quality vectors are associated with each of said subcircuits, and subcircuits associated with inferior quality vectors are replaced with subcircuits associated with superior quality vectors.
A computer-readable medium storing computer-executable process steps for optimizing the design of a combinational circuit, said process steps comprising:
- a. Constructing a circuit sheaf for a combinational circuit by:
- graphing the combinational circuit, replacing an edge in the graph with plural new inputs, each of said plural new inputs connecting to one of plural new circuits, and then connecting together inputs for the plural new circuits to form a modified combinational circuit;
- and
- b. performing vector optimization with domination, in which:
- subcircuits are identified that perform a function realized by an output pin of a cell within the modified combinational circuit, quality vectors are associated with each of said subcircuits, and subcircuits associated with inferior quality vectors are replaced with subcircuits associated with superior quality vectors.
Dependencies are inferred from the claim text.