Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-03-25
2002-04-02
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06367058
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to methods for fitting logic cells in an electronic design. More specifically, the invention relates to the use of hardware to perform the fitting function during design of an electronic product.
During the design phase of a new electronic product (e.g., an integrated circuit), logic functions must be designed, tested, and ultimately laid-out on a substrate (e.g., silicon or other semiconductor). The layout component of this process typically involves placement of logic blocks at specified locations on the substrate and routing lines between the various logic blocks on the substrate. These functions are generically referred to as “place and route.”
In some electronic products—notably some programmable logic devices—the layout of logic on the substrate assumes a hierarchy. In this hierarchy, fundamental units of logic may be referred to as logic cells or logic elements. These logic cells may be grouped into larger blocks of logic that may be referred to as “logic array blocks” for example. These blocks of logic may, in turn, be grouped into rows and ultimately columns on the hardware device.
In such “hierarchical” electronic designs, the place and route design function may be supplemented by a “partitioning” function in which lower level logic elements (e.g., logic cells) are grouped into larger logic blocks (e.g., logic array blocks). It is these logic blocks that are then placed on the substrate in a manner analogous to a conventional placement operation in place and route. Lines between the logic blocks are then routed in a conventional routing fashion. Collectively, partitioning and place and route are referred to as “fitting” operations.
Modem tools for designing electronic products are implemented as software. This software may allow the designer to specify the desired functioning of the end device, as well as some architectural and logic constraints. The software tools can take this information and, with the designer's aid, develop Boolean, schematic, and ultimately hardware designs. In the design process, the software fits the logic onto the hardware device to provide the final design layout.
Typically the design software “compiles” a design to produce a hardware layout. Compilation takes as an input a user's specifications (including high and low level logic constraints, timing requirements, etc.) and then synthesizes that design and fits it onto a target hardware device. In the case of programmable devices, the resulting compiled electronic design is then used to program a blank (unprogrammed) device. Designs for application specific integrated circuits, including programmable logic devices and field programmable gate arrays, as well as non-programmable electronic devices such as gate arrays all may require compilation involving synthesis of logic functions and fitting.
Commonly the fitting operations occupy the vast majority of the compile time. For example, in some programmable logic devices, the partitioning operation can occupy as much as four-fifths of the time to compile a design. This is true even when the compiler uses “fast” algorithms which do not try each and every possible partition before settling on a “best” partition. Such algorithms often do find the truly best partition from among all possible partitions. However, there are also numerous instances when they converge on a less than optimal partition.
As electronic designs including programmable gate arrays, etc. become larger and more complex, the time required for software tools to compile and perform other design operations is growing rapidly. In fact, compile times increase quadratically with the number of logic gates in a design. For this reason, it is desirable to find methods and mechanisms for increasing the speed at which design tools perform their functions, such as compilation. It would be particularly desirable to find a way to increase the speed at which these tools perform the most computationally expensive tasks such as fitting.
SUMMARY OF THE INVENTION
The present invention provides a method and mechanism for speeding the fitting portion of electronic design compilation. Specifically, the invention provides for the use of hardware to perform the computations necessary for fitting an electronic design onto a substrate. This hardware may be used in conjunction with a conventional software design tool which is reserved for performing other design functions such as logic synthesis and technology mapping. In a preferred embodiment, the hardware tool performs the steps necessary to partition logic cells into logic blocks for use in a hierarchical electronic design. In a particularly preferred embodiment, the hardware tool is provided as a product term device which temporarily stores information defining a given partitioning problem and then calculates the quality of the partition for every possible partition employing the constraints of the stored partitioning problem.
One aspect of the invention provides a method of compiling an electronic design. The method may be characterized as performing calculations necessary for fitting on hardware designed or programmed for performing the calculation. Preferably, the hardware includes a plurality of product terms, arranged in an array on a programmable logic device for example. The product terms may be provided on an appropriate configured embedded array block of the programmable logic device.
When product terms are employed, they may store a representation” of the connections to logic cells via appropriately programmed memory elements on intersection of bitlines and wordlines of the product terms. From this arrangement, the system determines the “metric” of various fitting options for logic elements by controlling values on wordlines to the product terms. This allows the system to determine the best fitting option. This approach is particularly well adapted for determining the best of several the partitions of the logic cells into two or more logic blocks. When the hardware performs partitioning, the each of the wordline or pair of wordlines to the product terms represents a cell that is to be provided in one of two logic blocks. Each product term or pair of product terms represents a signal that is fed to one or more of the cells. Each set of inputs to the wordlines corresponds to a different partition. Multiple partitions of the logic cells to the logic blocks are compared by varying the wordline inputs and measuring the product term outputs. The outputs represent the number of interconnections that must be made to the logic block under consideration (as defined by input values on the wordlines). In some embodiments, determining which partition provides the best fit involves determining which partition has the lowest total number of connections to the logic block. In other embodiments, it involves a further consideration of a balance of connections between the logic blocks of the partitions.
Another aspect of this invention is the hardware device that performs the fitting operation. Such hardware may be characterized as a first product term array configured to (a) provide a representation of connections to a plurality of logic cells and (b) output the number of connections to a first logic block containing a first subset of the plurality of logic cells. The number of connections is determined by a first set of input values to the first product term array which first set of input values represent the first subset of logic cells in the first logic block. As noted, the input values to the product term array may be provided through wordlines to the product term array.
To generate the input values to these wordlines, the hardware device may employ a generation block which defines a plurality of patterns of input values to the product term array, with each pattern specifying a partition of the logic cells into the logic blocks. Preferably, the generation block includes a ROM storing multiple values, each corresponding to a partition of the logic cells into the logic blocks. In a specific embod
No associations
LandOfFree
Partitioning using hardware does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partitioning using hardware, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioning using hardware will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2816336