Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-04
2003-02-11
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C716S030000
Reexamination Certificate
active
06519609
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention pertains generally to digital circuit design and particularly to logic synthesis and more particularly to a technology mapper used to perform logic synthesis.
2. Background of the Invention
Modem logic circuits are so complex that circuit designers must use computer-based techniques to help them in their task. The designers first abstractly represent the circuit as multiple combinatorial blocks (e.g., single-output, multiple-input Boolean equations) separated by sequential states. The combinatorial blocks are described by Directed Acyclic Graphs (“DAGs”) also referred to as “Boolean Trees.” In general, the computer-based techniques transform the abstract representation of the circuit design into a technology-dependent netlist representing the same circuit design. Computer-based techniques including behavioral synthesis, floorplanning, and logic synthesis are used to perform this transformation.
Logic synthesis takes the abstract representation of the circuit design, performs some abstract optimizations on the combinatorial and sequential blocks, and maps the blocks to the target technology library. Logic synthesis uses a technique called “Technology Mapping” to map the combinatorial blocks of the Boolean tree into the target library by replacing the nodes with library cells.
The Technology Mapper, accordingly, should efficiently tile a DAG with library cells. Usually, the task of matching the Boolean equation of a sub-part of the DAG to a cell is passed off to another entity, called the “Boolean Matcher.” The Boolean Matcher accepts a father node, some child nodes, and a library cell, and determines if the cell can cover the group of nodes. That is, the Boolean Matcher determines whether the cell has the same equation as a sub-part of the DAG, or the inverted equation modulo the inversion of any input. If the cell has the same equation as a sub-part of the DAG, the Boolean Matcher produces the input correspondence, which associates each cell input to an input of a node and states the cell's input's polarity.
The difficulty in performing Boolean matching lies in the possible permutation of inputs. A Boolean Matcher must be able to find not only an equivalent cell, but also the input correspondence. Thus, the representation of the equations for the DAG and the cell must conveniently allow inputs of at least one equation to be swapped in order to test the equivalence for any given pin permutation.
To this end, many techniques have been developed for performing Boolean matching. Some techniques perform matching based on tree patterns. Before starting a mapping process, the library cells are parsed and patterns are stored which represent the function implemented by each cell. Then, the Matcher essentially matches the current sub-tree function with a pattern. To allow the mapper to find better solutions, the matcher tests the equivalence of the cell pattern and the sub-tree function modulo the inversion of the function inputs and modulo the inversion of the function.
One reference,. Kurt Keutzer, “DAGON: Technology Binding and Local Optimization by DAG Matching,” Proceedings of the 24
th
ACM/IEEE Design Automation Conference, 1987, introduces a formalism for technology mapping using DAGs. The matching is performed by matching technology patterns in the canonical NAND/NOT form, thereby allowing matching modulo the polarity of inputs. However, this technique requires the Boolean network to be prepared before matching by covering it with virtual NAND/NOT cells. In addition, one has to write the patterns of the library cells in NAND/NOT form in order to map onto a technology library.
Another technique, described in E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, A. Wang, “Technology Mapping in MIS,” Proceedings of the ICCAD, 1987, also uses Boolean matching. This technique creates all non-isomorphic and irredundant NAND/NOT-based graphs. For each graph, an automaton is generated that does a depth-first transversal of the graph. The Boolean network is transformed into NAND/NOT graphs, and the match is tested by the automaton trying to transverse the Boolean network graph. A problem with this technique is that it must try several matches on the same cell. For instance, on an AND4 cell, two automata are used, one for the balanced graph and one for the unbalanced graph.
In F. Mailhot, G. De Michelli, “Technology Mapping using Boolean Matching,” Proceedings of the European Conference on Design Automation, 1990, the authors focus on symmetry between inputs to rapidly eliminate non-matching cases. For instance, when matching an AND2 (s=a AND b) gate, the two inputs can be marked as symmetric. Thus, if a Boolean equation F(x, y) is matched with {x=a, y=b} with a certain polarity for x and y, F(x, y) is also matched with {x=b, y=a} with the same polarities. On the contrary, it is useless to test the matching with {x=b, y=a} if the matching {x=a, y=b} has already been checked and found not feasible. This technique greatly limits the search space for symmetric cells (and library cells are often symmetric). But for all possible permutation of inputs, the technique must re-do the Shannon decomposition following the input permutation ordering.
Accordingly, there is a need for a technology mapper that does not have the deficiencies of the above-described techniques.
SUMMARY OF THE INVENTION
The above needs are met by a method and system for technology mapping that compares signatures of truth tables to determine whether part of a combinatorial block matches a technology cell. A preferred embodiment of the present invention accepts a Boolean tree describing the function of all or part of the combinatorial block and a cell of a technology library in the form of a string describing the function of the cell. The string is parsed to generate a Boolean tree describing the function of the library cell.
First and second truth tables are respectively generated from the Boolean tree representing the portion of the combinatorial block and the Boolean tree describing the function of the cell. Each truth table includes one or more inputs representing the one or more inputs to the nodes of the Boolean tree from which the truth table was generated. In addition, each truth table includes a signature describing the output of the Boolean tree from which the truth table was generated. Due to the nature of truth tables, a truth table representing the function of a combinatorial block or library cell can be described as a pair {I, S}, where I is an ordered list of the inputs and S is a signature such as an integer representing the output column of the truth table in decimal notation.
If the first and second truth tables match, then the portion of the combinatorial lock and the library cell described by the first and second truth tables also match. Two truth tables may match if the truth tables have the same number of inputs. Therefore, a referred embodiment of the present invention compares the two ordered lists of inputs to determine whether each list includes the same number of inputs. In addition, two truth tables having the same number of inputs match if the signatures of the truth tables also match. Accordingly, if each truth table has the same number of inputs, the signatures of the two truth tables are compared to determine whether the truth tables match, i.e., represent the same function.
If the signatures of the truth tables do not match, then it is possible that the signatures will match if the order of the inputs to the first or second truth tables is permuted. When generating the truth table representing the library cell, therefore, a preferred embodiment of the present invention also generates truth tables representing the cells having permutations of the inputs of the library cell. While there may be a large number of permutations, many cells have symmetric pins, which reduces the number of unique permutations. The truth
Bingham & McCutchen LLP
Cadence Design Systems Inc.
Le Uyen
Metjahic Safet
LandOfFree
Method and system for matching boolean signatures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for matching boolean signatures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for matching boolean signatures will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3129363