Scalable, partitioning integrated circuit layout system

Details Scalable, partitioning integrated circuit layout system Scalable, partitioning integrated circuit layout system

2001-10-30

2003-11-18

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C257S401000, C703S014000, C714S726000

Reexamination Certificate

active

06651235

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to computer software for automatically generating an integrated circuit layout.
2. Description of Related Art
An IC designer usually begins the IC design process by producing a register transfer language (RTL) “netlist” describing the IC circuit only in terms of the logic it carries out. For example a high level netlist may describe a cell connected to three node A, B and C using the equation C=A*B. This equation indicates only that the cell generates an output signal at node C that is the logical AND of signals appearing at nodes A and B. To test the logic of the circuit described by the netlist, the designer supplies the netlist and a “testbench” file as inputs to a circuit simulator. The circuit simulator then simulates the behavior of the circuit described by the netlist in response to a set of input signals described by the testbench file and produces output data describing the time-dependent behavior of signals at various nodes of the circuit. Since at this level the netlist models only the circuit logic, the simulator is only concerned with simulating circuit logic and does not attempt to simulate circuit timing.
Having used the simulator to verify the logic of the circuit, the designer typically uses a syntheses tools to create a “gate level” netlist that models the circuit as a set of interconnected circuit components (cells), wherein each cell is described by an entry in a cell library. IC components described as library cells may range from individual transistors and small components formed by several transistors such as logic gates up to very large components such as computer processors and memories. The cell library describes not only the logic performed by the cells, but also the time-dependent behavior of the cells. The boolean models of cell behavior are replaced with mathematical models that more accurately reflect the time-dependent behavior of the cells. For example, instead of modeling an AND gate by a simple boolean function C=A*B, a gate level netlist will model the AND gate with a mathematical expression having time as a variable and which describes the gate's input and output signals as analog voltages that change in magnitude over time in response to changes in input signal magnitudes. This more detailed netlist model of the circuit enables the circuit simulator to more accurately verify not only the circuit's logic but also the time-dependent behavior of the circuit. Thus by supplying a gate level netlist as input to a simulator, the designer can use the simulator to determine not only whether the AND gate carries out the required AND function, but also whether it does so quickly enough to meet various timing constraints for the circuit. However since the design at this point does not accurately model signal routing paths between the cells, the simulator output does not accurately take into account signal path delays between the cells.
After using the simulator to verify the time-dependent behavior of the circuit described by the gate level netlist, the circuit designer employs an automated placement and routing (P&R) tool to convert the gate level netlist into an IC layout describing how and where each cell is to be formed in the IC substrate and describing the signal routing paths within the IC that are to interconnect the cells. A typical placement and routing tool uses an algorithm which iteratively moves cells about on the substrate looking for a placement solution in which all cells fit within the substrate area allocated for the placement, that allows room for the routing paths needed to properly interconnect the cells and that satisfies various timing constraints on the circuit.
Once a P&R tool has created an IC layout satisfying all constraints, the designer may use a conventional netlist compiler to convert the layout back into another “layout level” netlist that accurately models the time-dependent behavior not only of the cells forming the IC but also of the routing structures that interconnect the cells. The designer may then again use a circuit simulator and other tools to verify the behavior of the circuit before sending the completed IC layout to an IC manufacturer.
Placement and Routing Tools
As illustrated in
FIG. 1
a placement and routing tool
10
converts a gate level netlist design of an integrated circuit into an IC layout satisfying various timing and spatial constraints supplied as input to the tool. A cell library
12
tells P&R tool
10
how to layout each cell referenced by the netlist and the P&R tool
10
determines an appropriate position within an IC substrate for each cell. P&R tool
10
also designs the routing structures that interconnect the cells. A netlist compiler
13
may then convert the IC layout back into a layout level netlist for use by simulation and verification tools
15
.
One way P&R tool
10
could determine an appropriate cell layout would be to randomly choose cell placements until it finds a placement that permits the cells to be appropriately interconnected in a manner that satisfies the various timing and other constraints. However for large ICs, it can take too long for a P&R tool to find a suitable placement by randomly generating and testing various cell placements to see if they can be appropriately routed. However various algorithms have been developed that reduce the amount of time a P&R tool needs to find acceptable cell placement.
FIG. 2
is a flow chart illustrating the process carried out by a typical P&R tool when generating an IC layout. The P&R tool makes use of a widely used placement and routing procedure making use of the well-known “min-cut” algorithm (steps
40
-
43
) for generating a cell placement in an IC substrate. The basic approach of the min-cut algorithm is to progressively divide the substrate area into smaller and smaller partitions and to allocate cells to each partition after each division in an attempt to minimize the number of connections between cells that must pass between partitions. This system helps to minimize the lengths of signal paths between cells by attempting to position highly interconnected cells near one another. Keeping signal paths short improves the chance that the P&R tool will be able to establish suitable routing paths between the cells because the routing paths require less space. Also since short paths have low signal path delays, keeping signal paths short improves the chances that the IC layout will satisfy various timing constraints.
FIG. 3
is a pictorial illustration of the min-cut process. Although ICs typically have thousands or millions of cells, for simplicity the example of
FIG. 3
assumes the IC design includes only 26 cells A-Z that are to be placed fit within a substrate area
14
. The first step of the process is to divide the substrate into two partitions
16
and
18
and randomly assign cells A-Z to the two partitions, thereby creating an initial “seed partitioning”
20
. The placement algorithm then tries to optimize the manner in which cells are allocated to the two partitions
16
and
18
by moving cells from partition-to-partition trying to find a placement that minimizes the number of cell-to-cell connections that cross between the two partition. For large ICs it would take too long to try all possible placement, so in many systems each cell is moved only once between partitions.
After attempting to optimize the placement of cells between the two initial partitions
16
and
18
, the algorithm divides partition
16
into two partitions
21
and
22
and divides partition
18
into two partitions
23
and
24
. It then tries to minimize the number of connections that cross partition lines between partitions
21
and
22
and by moving cells between partitions
21
and
22
. The system will also try to minimize the number of connections crossing partition lines between partitions
23
and
24
by moving cells between them. Since partitions
21
and
22
divide partition
16
, the system is free to move

Affiliated with

Also associated with

Rating

Scalable, partitioning integrated circuit layout system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scalable, partitioning integrated circuit layout system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable, partitioning integrated circuit layout system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3146063