Method for preserving regularity during logic synthesis

Details Method for preserving regularity during logic synthesis Method for preserving regularity during logic synthesis

2000-05-24

2003-04-29

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06557159

ABSTRACT:

BACKGROUND OF INVENTION
1. Field of the Invention
This invention relates to methods for automated design of electronic devices, and more particularly, to methods for maintaining regularity in electronic circuit designs while increasing synthesis speed and quality.
2. Background of Related Art
The increasing complexity of microelectronic designs and the continuous development of fabrication processes, yielding smaller layouts, presents new challenges to existing design automation tools. It is widely acknowledged that future electronic design automation methodologies must be able to handle the challenges and opportunities inherent in very large designs. This particularly applies to the field of logic synthesis, as existing design sizes already present a considerable challenge to current synthesis tools.
Future synthesis tools are expected to handle millions of gates in a reasonable amount of time. However, traditional logic synthesis is not able to satisfy these increasing demands. Due to the amount of available topological and functional transformations and their non-incremental nature, it is generally difficult and computationally expensive to select an optimal subset of transformations and their respective sequence. Therefore, current synthesis methodologies rely mainly on the concept of trial and error, applying sequences of transformations until a satisfactory arrangement is found. This process, however, produces a tradeoff between efficiency and quality and generally, does not yield optimal results. In addition, results vary depending on the actual designs, hence the overall optimization is left to the experienced designer.
In logic synthesis of large designs, efficiency in determining places to apply transformations to the design is a desired goal. When a transform succeeds at a certain place, it would be desirable to apply it quickly at other places in the design with the same characteristics.
Another important challenge of logic synthesis is the preservation of regular design structures during the optimization process. Maintaining regularity has significant advantages to the physical design stages. In particular, placing regular structures in rows and columns, yields a much denser layout, decreasing wire length and delay, and simplifying the overall placement task. In addition, the layout of a regular design is more predictable at an early design stage. The extraction of regularity and its usage has been exploited and used extensively to obtain high-density layouts in placement. Special placement techniques, such as datapath placement, have been developed to take advantage of regular structures.
While it is widely acknowledged that generic logic synthesis destroys a substantial amount of structural regularity, particularly during logic minimization and technology mapping, previously published approaches focus on the extraction of regularity. The problem of maintaining regularity throughout the design flow has rarely been addressed, and to date, no known solutions have been presented. A commonly used concept to avoid destruction of regularity is to skip logic minimization and map the technology by manual assignment of library cells. This process not only demands a substantial amount of manual work, it is also unable to benefit from potential improvements in logic minimization algorithms and is therefore generally undesirable.
In conclusion, a need exists for methods to efficiently synthesize logic netlists while maintaining regularity and achieving high quality designs.
SUMMARY OF THE INVENTION
A method for maintaining regularity in a netlist according to the present invention determines a structural regularity. The method determines a group of structures having similar regularity signatures. In one embodiment of the present invention, a method for maintaining regularity in a netlist is described. The method determines structural regularity. In one step, the method applies transformations to all elements of a stage within a regular group. In another step, the method determines regularity signatures for all elements of that stage. The method also compares the regularity signatures of all elements of the stage to determine whether the regularity signatures are identical. Further, the method, upon determining that the regularity signatures are different, removes any changes applied by the transformation to the netlist.
In another embodiment of the invention, a method to speed up the logic synthesis of a netlist is described. The method determines regularity signatures for elements of a netlist. Furthermore, the method identifies a beneficial transformation to a place in the network. In another step, the method re-applies the same transformation to all others places which have an equivalent regularity signature.
According to yet another embodiment of the present invention, a method for maintaining regularity in a netlist during logic synthesis is disclosed. The method determines a global regularity for the netlist, determines a group of elements in the netlist having similar regularity signatures, and applies a transform to the group of elements.
The method further, determines a regularity signature for each element within the group, and determines whether the regularity signatures for each element are identical, if the signatures are different the method removes the changes to the netlist made by the transform.
The method is performed for each stage in the order of dataflow through the netlist.
The global regularity is determined by the method in accordance with the following relationship:
RI
p
=
1
Aavg
·
(
n
grp
+
n
nr
)
·
(
∑
i
=
1
n
nr
⁢
 
⁢
A
nr
i
+
∑
i
=
1
n
grp
⁢
 
⁢
(
A
grp
j
·
2
·
A
grp
j
h
i
+
w
i
)
)
-
1
where: RI
p
is the physical regularity index measuring the amount of global regularity that effectively improves area and delay cost functions in the final physical layout; n
grp
is the number of regular groups; n
nr
is the number of gates which are not assigned to a regular group; h is the group height; w is the group width; Aavg is the average physical area of a gate in the design; Anr
i
is the area of gate i not assigned to a regular group; and Agrp
j
is the area of the regular group, j.
The method classifies each element into a signature class according to regularity signatures. The method also identifies a place in the netlist to improve, identifies a class method when an improvement can be made, applies the class method to each class member, determines whether the class method is successful, and upon determining that the class method is unsuccessful, removes the changes made by the class method. The method also updates regularity signatures and classes.
According to the current embodiment, the method identifies the class method by applying a plurality of transforms to the place. The method determines which transform achieves a defined solution, and defines the successful transform as the class method.
The method determines success according to whether the regularity signatures for each class member are identical after the application of the class method.
An element, according to the method, includes a net, a gate, or both a net and a gate. The regularity signature includes a logic signature, a time signature, an area signature or a power signature. The regularity signature includes an adaptive signature for controlling changes in the netlist made by the transform. According to the method, the transform applies an action.
In yet another embodiment of the present invention, a method for maintaining regularity in a netlist during logic synthesis determines a global regularity for the netlist based on regularity, symmetry or dataflow. The method determines a group of elements having similar local regularity signatures within the netlist, applies a transform to the group of elements, and determines whether the local regularity signatures for each element are identical, removing changes to the netlist made by the transform if the signatures are different.
An element can include a net, a g

Affiliated with

Also associated with

Rating

Method for preserving regularity during logic synthesis 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 for preserving regularity during logic synthesis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for preserving regularity during logic synthesis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3055875