Method and system for timing and area driven binary and/or...

Details Method and system for timing and area driven binary and/or... Method and system for timing and area driven binary and/or...

2000-08-24

2003-02-11

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06519743

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of computer-based logic synthesis for converting a logic circuit design into a representation based upon cells of a target library. The invention relates more specifically to a method for finding the best children nodes for a match of simple gates while improving overall area and respecting time constraints by minimizing slack.
2. Background Art
Today's logic circuits are so complex that they require computer-based techniques to help designers in their task. The flow of conception takes advantage of several techniques to transform an abstract representation of a design into a technology-dependant netlist (representation of the same design using cells of a target library). During this flow, techniques like behavioral synthesis, floor planning, placement, . . . are used. The invention focuses on one of the techniques called Logic Synthesis. Logic Synthesis takes an abstract representation of the design made of combinatorial blocks (single-output, multiple-input boolean equations) described by Directed Acyclic Graphs (DAG) and separated by sequential states. These DAGs are also often called Boolean Zones. Logic Synthesis performs abstract optimizations on the combinatorial and sequential parts and maps these parts on the target library. The Technology Mapper is in charge of taking a boolean zone and mapping it into the target library by covering boolean nodes with library cells.
Technology mapping is often done in four steps: In a first step, it partitions the Boolean Zone into a set of interconnected Logic Cones and Buffer Trees. A Logic Cone is defined as set of fanout-free interconnected
2
-input AND gates and
2
-input OR gates delimited by multi-fanout nodes, inverters, and buffers. A Buffer tree is a set of interconnected inverters, buffers (sometimes reduced to a simple multi-fanout wire) delimited by
2
-input AND gates,
2
-input OR gates and by Boolean Zone terminals. For instance, in
FIG. 1
, the Boolean Zone of
FIG. 1
a
has been partitioned into three Logic Cones and Buffer trees as shown in
FIG. 1
b.
In a second step, the Logic Cones and the Buffer Trees are sorted in a Forward BFS (Breadth First Search) order.
In a third step, the Logic Cones are tiled one by one, respecting the sorting done in the second step. During the Tiling, the inputs of a Logic Cone are assumed to be available both in direct and inverted form. Also, the Tiling tries to tile the Logic Cone both in direct and inverted form, the best ones being kept. At each node, it iterates through all the library available cells and asks the Matcher if the current cell can cover the current node. The task of the Matcher is to analyze whether that covering is possible either in direct or inverted form. If the answer is affirmative, the Matcher produces the correspondence between the current cell inputs terminals and the frontier nodes driving that current cell as well as the polarity of these terminals. When the tiler reaches the root node of a logic cone, it selects the best cover for that logic cone. That selection induces a polarity on that logic cone, as well as on all the logic cone input terminals.
In a fourth step, the buffer trees are buffered one by one, respecting the logic cone input and output polarities specified by the tiler.
Definition
The Logic Cone Tiler visits the logic cone nodes in a BFS order from the inputs to the output. At each node, in a first phase, the Logic Cone Tiler first invokes the matcher with a given matchable library cell. The matcher produces a list of matches, each of which being composed of the following information:
the matched cell, that is the library cell it could match to the current node;
the polarity of the match of the appropriate gate output connector;
the children nodes reached by that match;
the correspondence between the children nodes and the gate input connectors;
the polarity of each of the children nodes.
For instance, in the case of the
FIG. 2
, the matcher invoked for the node n would produce a set of information such as the one presented in FIG.
2
.
Expandable node: Operator Node of a Logic Cone that has the same function as its father.
Reachable children: Set of all the deepest nodes of a Logic Cone that can be covered by expandable nodes.
Slack: Difference between the original network required time and the best mapping arrival time. The slack information is computed by the tiler each time a cover is selected. As the Tiler is working on a bottom-up approach, this slack information is always available to the matcher.
Theory of Operation
The Three Main Phases of Binary AND/OR Matching
The matching is performed in three separate phases:
First phase is to verify whether the match is feasible or not. For simple cells (AND, OR, NAND, NOR) we just have to verify that the number of inputs is less than the size of the reachable children list.
Second phase is to find the children. It will be seen below that the Binary AND/OR matcher can either find several possible matches, or select one. Note that during this phase we do not need to know the function of the cell we are matching.
Third phase is the polarity assignment. We now need to know the exact function of the gate in order to assign the polarities on the outputs and on the inputs.
Output
Input
Gate
Logic Node
Polarity
Polarities
And
And
Direct
Direct
Or
Inverted
Inverted
Nand
And
Inverted
Direct
Or
Direct
Inverted
Or
And
Inverted
Inverted
or
Direct
Direct
Nor
And
Direct
Inverted
Or
Inverted
Direct
Selecting The Best Match
For a given cell, on a given node of the Logic Cone, we can have several matches, depending on the list of children we are going to choose as shown in FIG.
3
.
To select the ‘best’ match, we need to identify the ‘best’ children.
If the boolean Matcher does not select a match, the tiler will eventually have the choice of a list of many different children. Just to give an idea of the number of possibilities:
#nb of
2-
3
4
5
6
7
8
9
reachable
inputs
inputs
inputs
inputs
inputs
inputs
inputs
inputs
children
gate
gate
gate
gate
gate
gate
gate
gate
4
1
2
1
—
—
—
—
—
8
1
2
5
 6
 6
 4
 1
—
16 
1
2
5
14
26
44
69
94
Note that the problem of the gate pin assignment is not addressed here, but can be handled by the tiler through symmetry classes.
SUMMARY OF THE INVENTION
While the background art describes an algorithm where either the first list of children identified is returned to the tiler, or all the lists (exhaustive approach) are returned to the tiler, the present invention address the shortcomings of the background art by providing a method for finding the best match from a target library of simple logic cells for a complex logic circuit conception. The inventive method is flexible and can be adapted to several cost functions or criteria.
The inventive method finds the best children nodes for a match of simple gates (AND, OR, NAND, NOR). The method allows one to improve the overall area of the final design while respecting the time constrains. It also allows one to smartly speed up the tiler process as this process does not have to investigate exhaustive lists of possible children. Two preferred embodiments are disclosed. One such embodiment is designed to improve slack time and the other is designed to minimize required area.
The invention therefore provides a method for converting a logic design into a logic representation based upon cells of a target library; the method comprising the steps of: a) converting said logic design into a plurality of Boolean zones; b) partitioning the Boolean zones into a set of interconnected logic cones and buffer trees; c) sorting the logic cones in a forward breadth first search order and tiling the logic cones one after another; d) selecting that part of each such logic cone having the worst slack; e) in each logic cone sorting all possible children nodes to form a pile in decreasing order of their associated slack; f) expanding the first expandable node on the pile of sorted children nodes; g) resorting the pil

Affiliated with

Also associated with

Rating

Method and system for timing and area driven binary and/or... 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 timing and area driven binary and/or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for timing and area driven binary and/or... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3165797