Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-01-20
2002-04-09
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06370677
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to Computer Aided Design (CAD) of integrated circuits and Electronic Design Automation (EDA), and more particularly to a system and method for preserving logic circuit design hierarchy throughout physical implementation of a design, particularly for placement and routing designs into Field Programmable Gate Arrays (FPGAs) and other programmable logic devices.
BACKGROUND OF THE INVENTION
In designing complex digital circuits and systems, the design usually moves through layers of abstraction from the most generally defined design to the final physical implementation, as illustrated in FIG.
1
. The designer usually begins by giving a behavioral description of the overall function of the desired part. Languages used for behavioral description are often similar to computer programming languages such as Pascal or C. The behavioral description is then simulated to check for accuracy, and is modified into a structural circuit description, known as a netlist, which represents connections between functional cells in a device that will implement the design. Hardware description languages, such as VERILOG and VHDL, may be used to recite the structural connections. (Some designers prefer to begin the design process at the structural level, using schematics, register transfer schemes or Structural VHDL, thereby bypassing the behavioral level entirely.) Next, the designer develops the physically implementable description of the design. In programmable logic, such implementable files are known as configuration data.
Because many useful digital circuit designs are extremely complex, most designers generate their designs using high level functions that are combinations of hierarchically related subcomponents to facilitate coding and understanding. The design tools then decompose the designer's description into the hierarchically related subcomponents for placing in the chip that will implement the design. The behavioral subcomponents do not necessarily correspond to different parts of a chip or architecture that will implement the functions (e.g., shift registers in one section, addressing circuitry in another), and, in fact, are usually unrelated to physical components that implement a circuit design. Instead, behavioral subcomponents are grouped according to function. It is advantageous to organize a design into hierarchical components, thinking at one time about a high level design, and at other times about details of each portion of the high level design. This technique, often referred to as “divide and conquer,” advantageously reduces the possibility of design errors, makes errors easier to correct and accelerates the design process.
The divide and conquer hierarchical design technique provides an additional advantage: dividing a design into hierarchical subcomponents introduces the possibility of reusing part of the design in other designs or in other components of the same design. Using hierarchical subsystems and subcomponents works well with libraries of self-contained modules for accomplishing specified functions and provides some of the advantages found in Object Oriented Programming, such as standardizing subcomponent interfaces and simplifying the editing and substitution processes. It is therefore desirable to do hierarchical design wherever possible.
Existing CAD and EDA software tools exploit hierarchy to a limited extent in the behavioral and structural stages of the design process. For example, schematic-capture-type EDA tools use graphical representations of reusable component symbols, each symbol representing an underlying circuit schematic. The schematic, in turn, comprises other symbols and their underlying circuits. Decomposition may continue through several levels until the most basic and primitive circuit element in the system is encountered.
Similarly, Hardware Description Language (HDL) tools incorporate hierarchy in a manner similar to a software program using subroutines. To represent a desired design, calls are made to predefined procedures which in themselves describe subsystems, and so on.
With both schematic-based and HDL tools, subsystems of a design can be reused multiple times within a single design. Such reuse can be hierarchical as well. For example, a first subsystem cell A may contain two instances of a second cell B, and the cell B may contain three instances of a third cell C. The whole design would therefore contain the equivalent of six instances of cell C.
FIG. 2
provides an illustration of this hierarchical design. In such hierarchical designs, each instance of a particular subsystem must be functionally identical to all other instances of that subsystem. If any changes are made to the definition of subsystem B (i.e., the function of the subsystem is changed) then all instances of that defined subsystem are changed.
In the early digital circuit design process, shown as the behavioral and structural stages in
FIG. 1
, there is a tendency for designers to disregard physical limitations on circuit structure and leave accommodation of such limitations for a later phase in the design process. Indeed, the early design steps are simpler where no account is taken of the constraints imposed by the hardware available for implementation. But such disregard can lead to problems later in the design process. Where hierarchy is easily used during design, fitting the design into a chosen architecture while maintaining a user's design hierarchy is a major challenge. The present invention addresses this challenge.
FIG. 2
illustrates a simple hierarchical design. System A includes two instances of subsystem B. Subsystem B includes three instances of subsystem C. All instances of a subsystem definition are identical. The logical design of
FIG. 2
is to be implemented in a physical programmable device such as an FPGA. As the designer moves towards the physical implementation, the idiosyncrasies of the hardware may make satisfying the fundamental requirement for uniformity among different instances of subsystems difficult to achieve. For example, the device area available to implement A may not be able to accommodate six uniform implementations of C placed uniformly within two implementations of B. Of course, using a larger physical device and placing subsystems C less densely makes it possible to implement the six instances of C identically, but this leads to increased cost and decreased efficiency. Such inefficiency leads to a considerable increase in configuration costs in terms of memory, processing power and time requirements.
There is therefore a need in the art for a method of physically implementing a hierarchical design so that the implementation is dense and all instances have identical characteristics such as timing. Such a combination of requirements has not been easy to meet, however.
We illustrate the challenge of implementing a hierarchical design in a reprogrammable Field Programmable Gate Array (FPGA). Reprogrammability allows the designer to effect design changes even after implementation. However, FPGAs have limited numbers of routing lines between configurable blocks. A design which has a large number of identical repeated instances of a cell may not fit efficiently into the resources provided by an available FPGA architecture if the hierarchy is maintained, and instances of the same design element may not have identical characteristics if the hierarchy is not maintained.
Conventional design tools and methods fail to address this problem of mismatch that occurs when a design structure is implemented in a physical environment. These tools flatten and remove the structural hierarchy from the design, thereby allowing total design placement without regard for natural boundaries in a hierarchical design or the presence of repeated cells. Flattening a design consists of replacing symbols which represent groups of objects with the objects themselves. A flattened representation of a design requires much more time and processing power to place and route for two reasons. First, ins
Buchanan Irene
Carruthers Colin
Do Thuan
Tachner Adam H.
Xilinx , Inc.
LandOfFree
Method and system for maintaining hierarchy throughout the... 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 maintaining hierarchy throughout the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for maintaining hierarchy throughout the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2885333