Site News  |   Monitor Keywords  |   Monitor Archive  |   Organizer  |   Account Info  |

Method for optimization of logic circuits for routability improvement

Method for optimization of logic circuits for routability improvement description/claims

This application is a Continuation of U.S. application Ser. No. 10/780,140 filed on Feb. 17, 2004, which is incorporated by reference herein in its entirety.

1. Field of the Invention

The present invention relates to circuits and, more particularly, to electronic circuit design.

2. Description of the Related Art

A major goal in the design of Very Large Scale Integration (“VLSI”) chips and other integrated circuits is to combine logic synthesis methods with physical design optimization methods to meet timing, area, and other design objectives of the chip. Physical design optimization methods include methods for placement and methods for routing. Logic synthesis methods determine the type and connectivity of circuits used to implement the functionality of the chip. Placement methods assign and alter the physical locations of the circuits on the chip. Routing methods modify the physical path and wire type of the connections between the circuits.

As the size of the VLSI chip grows, the problem of design closure increases correspondingly at a geometric rate. Design closure is the process of getting a chip design ready to be submitted for manufacturing. Design closure ensures that timing along all paths in the circuit operate at least as fast as some pre-defined speed in the presence of various electrical interactions, such as capacitive coupling. During this process, locations are selected for all of the components making up the design, and those components are connected or routed with some wiring resources.

A key design parameter that affects design closure significantly is routability of the circuit. The routability of the circuit is a measurement of the relative ease of making appropriate connections on the chip implementing the design. In some cases, this may be impossible to do; that is, the chip is said to be unroutable. However, when it is possible, the relative ease of making appropriate connections on the chip implementing the design is measured by the density of wiring resources that is required per unit area of the chip. This density measurement describes the wiring congestion on the chip. Routability (or wiring congestion) affects the performance, noise sensitivity, yield, area, and power of the design.

Two of the steps in the design closure process which are relevant here are logic synthesis and physical design. Logic synthesis transforms a textual representation of the design into a boolean representation, and maps the boolean representation down onto circuits and connections. The circuits and connections are the basic building blocks in which the physical design operates. Physical design takes the circuits and assigns them physical locations on the chip for implementing the design. The logical connections are converted into physical connections taking the form of wires and accompanying wiring paths between the connected elements.

Logical synthesis comprises two optimization stages: (1) a technology independent stage and (2) a technology dependent stage. Optimizations of the technology independent stage are independent on the type of technology that will be used to implement the design. On the other hand, optimizations of the technology dependent stage are dependent on the type of technology that will be used to implement the design. Each of these stages are comprised of a one or more optimization steps. The application of one of these steps is known as a transformation or transform

The technology independent stage comprises transforming a register transfer level textual description of the design into a set of boolean equations. The set of boolean equations are then optimized for a set of given metrics such that they will, at the completion of all the steps in the full synthesis process including technology mapping and physical synthesis, lead to a good implementation for delay, area and power. Because the technology independent stage does not know the exact technological components that will be associated with the boolean equations, the optimizations in this stage must use measurements or metrics based on the equations to approximate the area and delay of the entire set of equations. The area is approximated with a literal count, which is a measure of the number of connections or edges in a graph representing all of the boolean equations. For example, assume a set of boolean equations for an output A would be of the form X=A and B, B=C and D. Here the literal count is 4 since the number of connections are 4. The connection between area and literal count is directly proportional, meaning that each literal is assumed to consume some positive, finite, yet unknown, amount of area. The technology independent optimizations attempt to minimize the amount of area that will be consumed by the equations because smaller implementations are more likely to fit within the area defined by a chip.

The delay of the design is approximated in the technology independent phase of logic synthesis by a number of levels in the boolean equation. A set of logic equations comprising a set of input signals and output signals may be represented by a graph with nodes (which represent gates) and edges (which represent connections) between the inputs and outputs. The paths between inputs and outputs comprises gates and connections encountered during a traversal of the graph from input to output. Each path comprises gates and connections. The number of levels for an output signal in the equation is the maximum number of connections from any given input signal to the output signal. There is a directly proportional relationship between delay and number of levels, meaning that each level is assumed to consume a positive and finite, yet unknown, amount of delay. The technology independent optimizations attempt to minimize the amount of delay that will be consumed by the equations because faster implementations are more likely to achieve design closure.

While the technology independent synthesis optimizations attempt to measure the size and speed of the circuit, no metrics exist to determine where the literals will be placed or how many wiring paths will want to follow similar routes, which correlates strongly with the routability of the design. So while the basic structure of the design implementation is defined by the form of the boolean equations at the end of the technology independent optimization phase, no attempt has been made to measure the wiring characteristics of the design.

The second stage of logic synthesis, which generally follows the technology independent optimization stage, is the technology dependent stage. In this stage, the boolean equations are mapped onto a set of gates that exist in some predefined technology specific library. This mapping has both logical and electrical components. The logical component says that all logic described in the boolean equations must be mapped to one or more gates, while the electrical component ensures that the electrical characteristics of the gate are not violated and that the desired speed of the design can be achieved. An example of an electrical characteristic is as follows: the amplitude of the signal transmitted from one gate is sufficiently large to cause a reaction when received by a connected gates. The strength of these transmitted signals also determines the speed at which the design will operate. This mapping to gates is done within the structure defined by the boolean equations coming out of the technology independent optimization stage of logic synthesis.

After this technology dependent mapping to gates has been completed, the physical design process can begin. Physical design consists of two main components, placement and routing. During placement, locations on a chip are assigned for each of the gates coming out of the technology dependent optimization phase of logic synthesis. Based on this placement, routing then creates physical wires between the connected gates. It is not until the locations of the gates are assigned that even a crude approximation can be made about the routability of the design. While delay receives attention early in the design process, if all of the connections between the design components cannot be made, the design cannot be implemented. Poor routability of the design also creates longer wires in the design, causing a degradation in timing. If the inability to route the design or the inability to meet timing due to poor routability is discovered only during the physical design process, a designer must return to the technology independent logic synthesis phase to alter the way the design was optimized. However, since those optimizations have no concept of a routability metric, it is difficult to direct those optimizations toward a criteria that cannot be measured.

Physical design information is generally not available early in the logic synthesis stage. Therefore, existing optimizations and transformations in the logic synthesis stage, which are primarily targeted towards timing and area, generally do not consider their impact on routability. Significant decisions regarding the circuit structure are made early in logic synthesis such as during the technology independent logic optimization step. Optimizations in this step use a literal count as a metric for optimization, and, therefore, do not adequately capture the intrinsic entanglement of the circuit. Two circuit design models with identical literal counts may have significantly different routability characteristics after physical design.

It is widely acknowledged that current electronic design automation must be able to handle the challenges and opportunities of finer-featured fabrication processes. These processes are fundamentally premised on the principle of separation of concerns in which a complex design flow is serialized into a sequence of manageable steps that are loosely coupled. In this scenario, decisions made in the early stages of design flow become binding constraints on later stages. Such serialization potentially gives less optimal designs than a process that simultaneously considers all design aspects. This is unavoidable, however, due to the practical infeasibility of concurrent optimization of all design parameters, and is deemed acceptable as long as the constraints that are fed forward by one step to the next can be met. The process breaks down, however, when these constraints become unsatisfiable (e.g., the chip becomes unroutable, and falls short of the expected yield). The typical action in such cases is to go back to the earlier steps and iterate through the steps so as to revisit earlier design stages to change suspected problematic decisions. Such iteration has become particularly necessary between the logic synthesis and placement steps.

Ideally, the time-wasting iteration between logic synthesis and placement in today's design methodologies could be eliminated by fusing these stages to simultaneously optimize the logical structure as well the spatial placement of a circuit.

Steps in technology dependent logic synthesis and placement have been combined to produce a wide variety of methods. Techniques which optimize both the logical and physical characteristics are referred to as physical synthesis. Although, there is work in the area of physical synthesis that combines later stages of logic synthesis with placement, the early stages of logic synthesis are not adequately integrated with placement.

Wire planning evaluates the placement characteristics of circuits during logic synthesis and approaches the same problem from a different angle. The wire planning approach assumes that the locations of pins at the boundary of the region being optimized are known. Constraints are generated from placement models and synthesis is performed using the constraints. Although the locations of chip/partition Inputs/Outputs are typically available, assumptions about locations for pins surrounding the small region consisting of a few gates in which local optimizations (e.g., factorizations) are being performed is generally difficult to preserve during full chip placement.

• Provisional Patent
• Utility Patent

• What Is a Patent?
• What Is a Trademark or Servicemark?
• What Is a Copyright?
• Patent Laws