A method, data processing system and computer program product for optimizing the placement of logic gates of a subcircuit in a physical synthesis flow. A Path Smoothing utility identifies one or more movable gates based on at least one selection criteria. A set of legalized candidate locations corresponding to one or more identified movable gates is generated. A disjunctive timing graph based on the generated set of legalized candidate locations is then generated. An optimal location of one or more movable gate(s) is determined using a recursive branch-and-bound search and stored in the computing device.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention generally relates to integrated circuit design tools and in particular to integrated circuit design tools that optimize area, performance, and signal integrity in integrated circuits.

2. Description of the Related Art

Existing methods have sought to improve the placement of negative-slack gates of a circuit in a physical synthesis flow. While several solutions to this problem exist, there are several drawbacks to these existing solutions. One major drawback of existing solutions is that these existing solutions consider only the placement of a single, movable gate within an integrated circuit design. In addition, existing physical synthesis optimization methods consider gates (i.e., clocked repeaters and unclocked repeaters, such as buffers and inverters) that are adjacent to a single, movable gate as unmovable. This designation of certain gates as unmovable can possibly over constrain gate placement optimization efforts.

One existing solution, known as the Rip Up and Move Boxes with Linear Evaluation (RUMBLE) utility, employs linear programming (LP) to consider the optimal placement of multiple gates under a linear delay model. Such use of LP assumes that subsequent buffer reinsertions (i.e., re-buffering) will be performed after the optimal gate locations have been ascertained. However, in later stages of refinement when re-buffering is not permitted, the linear delay model does not hold. Moreover, the presence of obstacles and keep-out regions on the chip circuit often limits the possible legal locations for a particular gate. When there are obstacles to gate placement, feasible candidate positions may need to be discretized, a task that cannot be performed by the LP formulation within RUMBLE.

Lastly, existing gate optimization techniques are based upon an exhaustive enumeration approach for finding an optimal solution to the problem of incremental timing-driven physical synthesis. Under exhaustive enumeration, every possible assignment of candidate locations for gate placement is attempted and solved. Thus, an exhaustive enumeration approach would fare poorly in large problem instances, as the number of possible gate assignments grows exponentially with the number of movable gates (i.e., with M movable gates and C candidates per gate, a total of MCgate assignments would be generated).

SUMMARY OF AN EMBODIMENT

Disclosed are a method, system, and computer program product for optimizing a timing-driven placement of one or more movable gates of a circuit in a physical synthesis flow using a non-linear delay model. A path smoothing utility is provided, which executes on a processing device/computer to: (a) identify one or more movable gates based on at least one selection criteria; (b) generate a set of legalized candidate locations corresponding to one or more identified movable gates; (c) generate a disjunctive timing graph based on the generated set of legalized candidate locations; (d) determine an optimal location of one or more movable gate(s) using a recursive branch-and-bound search; and (e) store the optimal location in the processing device/computer. According to one embodiment, in addition to gate placement, the disjunctive timing graph permits additional discrete transforms that are associated with a plurality of optimization variables. Such optimization variables include, but are not limited to gate repowering, gate voltage threshold (Vt) assignment, and wire sizing.

The above, as well as additional features of the present invention will become apparent in the following detailed written description.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

The illustrative embodiments provide a method, system, and computer program product for optimizing the placement of logic gates of a subcircuit in a physical synthesis flow, in accordance with one embodiment of the invention. Physical synthesis is the process of creating a specification for a physical integrated circuit (IC) given a logic circuit specification. As utilized herein, a logic gate is a computer circuit device with several inputs signals but only one output signal that can be activated by particular combinations of input signals. Moreover, combinations of logic gates are used to store information in sequential logic systems, forming a latch. In order to improve the overall circuit timing of a subcircuit, new locations for one or more movable logic gates are selected on a timing-driven basis by directly minimizing the signal delay of a source-to-sink timing arc. Timing arcs measure the signal delay between the inputs and outputs of sequential and/or combination

With reference now toFIG. 1, depicted is a block diagram representation of a data processing system (DPS)100. DPS100comprises at least one processor or central processing unit (CPU)105connected to system memory115via system interconnect/bus110. Also connected to system bus110is I/O controller120, which provides connectivity and control for input devices, of which pointing device (or mouse)125and keyboard127are illustrated, and output devices, of which display129is illustrated. Additionally, a multimedia drive128(e.g., CDRW or DVDRW drive) and Universal Serial Bus (USB) hub/port126are illustrated, coupled to I/O controller120. Multimedia drive128and USB hub/port126may operate as both input and output mechanisms for inserting removable storage devices therein. DPS100also comprises storage117, within which data/instructions/code may be stored. DPS100is also illustrated with a network interface card (NIC)150coupled to system bus110. NIC150enables DPS100to connect to one or more access networks, such as the Internet.

Notably, in addition to the above described hardware components of DPS100, various features of the invention are completed via software (or firmware) code or logic stored within system memory115or other storage (e.g., storage117) and executed by CPU105. In one embodiment, data/instructions/code from storage117populates the system memory115, which is also coupled to system bus110. System memory115is defined as a lowest level of volatile memory (not shown), including, but not limited to, cache memory, registers, and buffers. Thus, illustrated within system memory115are a number of software/firmware components, including operating system (OS)130(e.g., Microsoft Windows®, a trademark of Microsoft Corp; or GNU®/Linux®, registered trademarks of the Free Software Foundation and Linus Torvalds; or Advanced Interactive eXecutive —AIX®—, registered trademark of International Business Machines—IBM), Integrated Circuit (IC) Design application135, and Path Smoothing utility145. In actual implementation, components or code of OS130may be combined with those of IC Design application135and Path Smoothing utility145, collectively providing the various functional features of the invention when the corresponding code is executed by the CPU105. For simplicity, IC Design application135and Path Smoothing utility145are illustrated and described as a stand alone or separate software/firmware component, which is stored in system memory115to provide/support the specific novel functions described herein.

CPU105executes IC Design application135, Path Smoothing utility145as well as OS130, which supports the user interface features of IC Design application135and Path Smoothing utility145. In the illustrative embodiment, Path Smoothing utility145optimizes a timing state of an original subcircuit by determining a new optimized placement(s) of movable gate(s). Path Smoothing utility145assists IC Design application135, which simulates an IC design. In this regard, DPS100is being used as an IC design platform for Path Smoothing utility145and IC Design application135. The IC design application135is modified/enhanced with the functionality of Path Smoothing utility145. Among the software code/instructions provided by Path Smoothing utility145, and which are specific to the invention, are: (a) code for identifying one or more movable gates based on at least one selection criteria; (b) code for generating a set of legalized candidate locations corresponding to one or more identified movable gates; (c) code for generating a disjunctive timing graph based on the generated set of legalized candidate locations; (d) code for determining an optimal location of one or more movable gate(s) using a recursive branch-and-bound search; and (e) code for storing the optimal location in a computing device.

For simplicity of the description, the collective body of code that enables these various features is referred to herein as Path Smoothing utility145. According to the illustrative embodiment, when CPU105executes Path Smoothing utility145and IC Design application135within the context of an existing/generated IC design, DPS100initiates a series of functional processes that enable the above functional features as well as additional features/functionality, which are described below within the description ofFIGS. 2-5.

Those of ordinary skill in the art will appreciate that the hardware and basic configuration depicted inFIG. 1may vary. For example, other devices/components may be used in addition to or in place of the hardware depicted. The depicted example is not meant to imply architectural limitations with respect to the present invention. The data processing system depicted inFIG. 1may be, for example, an IBM System p5™ (a trademark of International Business Machines—IBM), a product of International Business Machines Corporation in Armonk, N.Y., running the AIX® operating system or LINUX® operating system.

Within the descriptions of the figures, similar elements are provided similar names and reference numerals as those of the previous figure(s). Where a later figure utilizes the element in a different context or with different functionality, the element is provided a different leading numeral representative of the figure number (e.g.,1xxforFIG. 1 and 2xxforFIG. 2). The specific numerals assigned to the elements are provided solely to aid in the description and not meant to imply any limitations (structural or functional) on the invention.

FIG. 2represents a flow chart illustrating the exemplary method200of optimizing the placement of logic gates of a subcircuit in a physical synthesis flow, according to an illustrative embodiment of the invention. Although the following methods illustrated inFIG. 2may be described with reference to components shown inFIG. 1and later shown inFIGS. 3-5, it should be understood that this exemplary method is merely for convenience and alternative components and/or configurations thereof can be employed when implementing the method. Key portions of the method may be completed by Path Smoothing utility145(FIG. 1). Path Smoothing utility145(FIG. 1) executes within DPS100(FIG. 1). Moreover, Path Smoothing utility145controls specific operations of/on DPS100. The method is described from the perspective of Path Smoothing utility145within the IC design platform of DPS100.

The process ofFIG. 2begins at initiator block201and proceeds to block205, at which the Path Smoothing utility145(FIG. 1) identifies one or more movable gate(s) within the circuit design for timing-driven placement optimization. In this regard, there are several selection criteria that can be used to identify these movable gate(s). Selection criteria include, but are not limited to, (i) the most critical gate(s) in a circuit, (ii) the most critical paths of a circuit, and (iii) the gate(s) having the largest slack differential between input timing point and output timing point.

As used herein, the following terms are defined:

“timing point” is a vertex in a timing graph; conventionally, all gate pins (input or output) in a circuit have an associated timing point; a timing arc is formed between two timing points;

“slack” at a timing point is defined as the difference between the required arrival time (RAT) at the timing point and the actual arrival time (AAT) at the timing point. A negative slack value indicates that the signal that is sent to the input of the timing point is actually arriving after its required arrival time. A positive slack value indicates that the signal is arriving before its required arrival time;
“critical gate” is a gate that is characterized as having a negative slack value;
“critical path” is a sequence of connected gates, whereby the combination of each connected gate is characterized as having an overall negative slack value; and
“slack differential” is defined as the difference between the smallest slack value of an output timing point and the largest slack value of an input timing point; or vice versa. A large slack differential, especially when either the input timing point or the output timing point has a negative slack value, indicates that the latch timing can likely be improved by moving the movable gate/latch.

Once a movable gate(s) is/are identified for placement optimization, Path Smoothing utility145generates a set of legalized candidate locations corresponding to one or more of the identified movable gates, as depicted in block210. In this regard, there are a number of different candidate location search strategies that can be implemented. Such strategies include, but are not limited to: (i) a cardinal direction approach, (ii) a legalized cardinal direction approach, and (iii) a nearest legal neighbor approach.

According to a cardinal direction approach, for a movable gate whose current placement/location coordinate on the chip is (x, y), Path Smoothing utility145would consider the following four candidate locations: (x+Δx, y), (x−Δx, y), (x, y+Δy), (x, y−Δy) for a given (Δx, Δy), in addition to the current placement/location coordinate of the movable gate. Under the above approach, the possibility exists that a candidate location is placed in a non-legalized location (i.e. an unrealizable location), such as a chip region containing a fixed macro or other obstacle. Another candidate location search strategy approach, the legalized cardinal direction approach, considers the closest legal (i.e., feasible) locations to each of the candidate locations identified in the cardinal direction approach (i.e., respecting blockages and large fixed macros). Further still, the nearest legal neighbor approach considers the n nearest legal locations that are closest to the movable gate's current coordinate, for a specified number n.

Referring now toFIG. 3, the exemplary method steps depicted in blocks205and210(ofFIG. 2) are further illustrated by exemplary subcircuit300. Subcircuit300represents a portion of a larger chip circuit (not shown). Subcircuit300includes a set of M movable gates302-306, a fixed source gate301, and a fixed sink gate307. A movable gate, as used herein, may represent sequential gates (i.e., latches, flip-flops, and the like) or combinational gates (i.e., AND/OR gates, buffers, inverters, and the like). Note that in order to isolate the subcircuit300from the larger chip circuit, Path Smoothing utility145must identify the boundaries of subcircuit300. This is achieved by a basic N-hop neighborhood approach, where any gate within N steps of a movable gate is included in the set of movable cells. The N-hop neighborhood approach requires both a forward sweep (to collect sinks) and a backward sweep (to collect sources), which are performed in tandem. In selecting subcircuit300, Path Smoothing utility145may remove intermediate buffers on a subset of nets, under the assumption that those nets will later be re-buffered. Since the presence or absence of these buffers does not change the logical function of the circuit, the correctness of the circuit is maintained.

As stated in combination with blocks205and210(ofFIG. 2), once the set of M movable gate(s)302-306have been identified, a set of legalized candidate locations corresponding to one or more identified movable gate(s)302-306is generated. Legalized candidate locations308-318are illustrated inFIG. 3. For example: (a) legalized candidate locations308,309correspond to movable gate302; (b) legalized candidate locations310,311,312correspond to movable gate303; (c) legalized candidate locations313,314correspond to movable gate304; (d) legalized candidate locations315,316correspond to movable gate305, and (e) legalized candidate locations317,318correspond to movable gate306. In the embodiment shown inFIG. 3, the candidate location search strategy implemented is the nearest legal neighbor approach, which is described above. Notably, under the nearest legal neighbor approach, candidate locations308-318are generated such that obstacle/fixed macro319on subcircuit300is avoided. Thus, the pre-legalization of a candidate location ensures the feasibility of placing a movable gate in the movable gate's respective candidate location(s).

Referring back to the flowchart illustrating method200(FIG. 2), once the legalized candidate locations308-318(FIG. 3) have been generated, method200continues to block215. According to block215, a disjunctive timing graph based on the generated set of legalized candidate locations308-318is generated. With reference now toFIG. 4, disjunctive timing graph400is illustrated. Timing graph400includes a vertex (i.e., point) for each fixed gate301,307, as well as a vertex for each legalized candidate location308-318of movable gate(s)302-306in subcircuit300. As a result, a timing arc for each pair (li, lj) of adjacent vertices (e.g., timing arcs a-b1, b1-c3, f1high-g, etc.) is constructed, specifying an estimate of the delay δ(li, lj) that would occur between the pair (li, lj) of adjacent vertices. For simplicity, disjunctive timing graph400has been restricted to show legalized candidate locations to new positions. However, in practical implementation, disjunctive timing graph would also include and consider the original locations of movable gates302-306.

It should be understood by persons of ordinary skill in the art that the correlation between the values of the various timing arcs is not assumed, and that any delay model can be used. For instance, half-perimeter wirelength (HPWL) can be used to create a linear-delay model if re-buffering will be performed as a post-processing step. In such case where rebuffering is performed, delay δ(li, lj) is a pure function of geometric location and calculated/evaluated as:
delay δ(li, lj)=τ*(abs(li.x−lj.x)+abs(li.y−lj.y));
where τ is a technology dependent parameter equal to the ratio of the delay of an optimally-buffered, arbitrarily-long wire segment to its length:

τ=delay⁢⁢(wire)length⁢⁢(wire)
Alternatively, if rebuffering will not occur, more elaborate and accurate timing models can be used. For instance, the Elmore delay model captures a quadratic function of wirelength on 2-pin nets:
delay δ(li, lj)=0.5*ro*co*(abs(li.x−lj.x)+abs(li.y−lj. y))2;
whereby corepresents the initial capacitance that is shared by all wires and gates.

Moreover, the delay between gates on higher degree nets can be estimated by a bounding-box model, or by querying a timing calculation tool (e.g., EinsTimer™, which is a trademark of International Business Machines, Inc.) that generates Steiner trees.

Once the delay values for each timing arc has been determined, the gate placement optimization problem is viewed as disjunctive timing graph400, whereby the term disjunctive refers to the fact that all combinations of delays are included. A traditional timing graph can be obtained from disjunctive timing graph400by selecting a single candidate location for each respective movable gate (e.g., movable gates “b”-“f”,302-306), and extracting the appropriate timing arcs. Moreover, it is important to note that the adjusted timing arcs of disjunctive timing graph400results from the combination of two optimization variables: gate placement and gate repowering (e.g., gate “f”,306has candidate locations “f1low”, “f1high”, “f2low”, “f2high” for high/low powered gates). However, disjunctive timing graph400permits discrete transforms associated with a plurality of optimization variables besides gate placement and gate repowering. Other optimization variables include, but are not limited to gate voltage threshold (Vt) assignment, wire sizing, and/or any other discrete transformation that has an effect on signal propagation timing (i.e., slack and net delay).

Referring again to the flowchart shown inFIG. 2, once disjunctive timing graph400(FIG. 4) is generated, method200continues to block220, whereby a recursive branch-and-bound search is employed to determine an optimal location of movable gate(s)302-306(FIG. 3). As used herein, the term optimal location refers to one or more coordinates of a candidate location that is associated with the maximum slack value that can be obtained from all possible gate assignments. Under the recursive branch-and-bound search, instead of exploring all possible gate assignments, some sets of gate assignments are pruned (i.e., discarded) from further search based on cost estimates calculated during the branch-and-bound search.

Turning now toFIG. 5, a branch-and-bound search tree500is shown. Search tree500includes internal nodes “b”-“f”. Each internal node b-f ofFIG. 5corresponds respectively to movable gate “b”-“f” ofFIG. 3. According to exemplary embodiment shown inFIG. 5, each internal node branches off depending on the number of legalized candidate locations (e.g.,308-318) that have been generated for a particular movable gate. As a result of such branching, an internal node may be represented by a plurality of nodes corresponding to the same movable gate (e.g., internal node “e” is comprised of four nodes, internal node “d” is comprised of three nodes, etc.). For example, internal node “b” branches off into two branches, “b1” and “b2”, which connect to the next internal node “c”. Branches “b1” and “b2” ofFIG. 5correspond to two different legalized candidate locations308,309for movable gate302(FIG. 3). Dashed lines501represent additional branches (not shown) branching from an internal node. Moreover, branches labeled f1L, f2L, f1H, f2H, represent branches having a particular combination of high (H) or low (L) powered gates at a specific placement. For simplicity, only the leftmost set of branches below internal node “f” has been labeled.

At every internal node “b”-“f” in the branch-and-bound search tree500, a relaxed variation of Static Timing Analysis (RSTA) is performed. RSTA shall now be explained within the context of a branch-and-bound search. For a particular source/sink pair, the weakest (i.e., best slack) timing arcs are propagated through the timing graph, thus providing an optimistic upper bound on a worst-case negative slack value. If each gate (i.e., fixed or movable) of the net has been instantiated with legalized candidate locations, the actual timing arc between those specific legalized candidate locations is used. Backtracking along search tree500occurs whenever the upper bound on the worst-case negative slack value of all candidate nets502is no better than that of the previously best found solution of gate assignments. Any partial gate assignment using a legalized candidate location that cannot improve upon the worst-case negative slack value in the best known solution (i.e., a full gate solution) is pruned. The recursive branch-and-bound search discards one or more gate assignments when an upper bound on a worst-case negative slack value is not realizable from the partial gate assignment. Pruned branch-and-bound search space is identified inFIG. 5by hatched regions505, for which no further static timing analysis is performed for internal nodes associated with a pruned gate assignment. RSTA is performed for internal nodes associated with a non-pruned partial gate assignment to obtain the upper bound on the worst-case negative slack value. As a result, branch-and-bound search employing RSTA greatly improves the time, system, and cost resources that would be ordinarily be expended, particularly in large problem instances.

Continuing with the flowchart described inFIG. 2, once the brand-and-bound search has been performed and optimal locations for gate placement has been determined, method200continues to decision block225. At decision block225, a determination is made whether a suitable termination criterion has been met, allowing Path Smoothing utility145(FIG. 1) to perform additional iterations if necessary. In this regard, there are several termination criteria that can be used to determine whether additional passes of the method steps depicted in blocks210-220are performed. Such termination criteria include, but are not limited to whether, (i) a maximum number of iterations of blocks210-220has been reached, (ii) a predefined limit on runtime has been reached, or (iii) no improvement in timing (i.e., slack value) on movable gate(s)302-306(FIG. 3) is observed from the most recent placement of movable gate(s)302-306. If one or more of the aforementioned termination criteria has been met, Path Smoothing utility145returns the best placement of movable gates302-306found across all iterations as the optimal solution for gate assignment (i.e., new or original gate assignment), as depicted in block235. However, if none of the termination criteria has been met, Path Smoothing utility145returns to block210, generating a new set of legalized candidate locations, and blocks215,220, and225are repeated. From block235, the optimal solution solution for gate assignment is stored in DPS100(FIG. 1), as depicted in block237. Method200terminates at end block240.

In the flow chart above (FIG. 2), one or more of the methods are embodied as a computer program product in a computer readable medium or containing computer readable code such that a series of steps are performed when the computer readable code is executed on a computing device. In some implementations, certain steps of the methods are combined, performed simultaneously or in a different order, or perhaps omitted, without deviating from the spirit and scope of the invention. Thus, while the method steps are described and illustrated in a particular sequence, use of a specific sequence of steps is not meant to imply any limitations on the invention. Changes may be made with regards to the sequence of steps without departing from the spirit or scope of the present invention. Use of a particular sequence is therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.

As will be further appreciated, the processes in embodiments of the present invention may be implemented using any combination of software, firmware, or hardware. As a preparatory step to practicing the invention in software, the programming code (whether software or firmware) will typically be stored in one or more machine readable storage mediums such as fixed (hard) drives, diskettes, optical disks, magnetic tape, semiconductor memories such as ROMs, PROMs, etc., thereby making an article of manufacture (or computer program product) in accordance with the invention. The article of manufacture containing the programming code is used by either executing the code directly from the storage device, by copying the code from the storage device into another storage device such as a hard disk, RAM, etc., or by transmitting the code for remote execution using transmission type media such as digital and analog communication links. The methods of the invention may be practiced by combining one or more machine-readable storage devices containing the code according to the present invention with appropriate processing hardware to execute the code contained therein. An apparatus for practicing the invention could be one or more processing devices and storage systems containing or having network access to program(s) coded in accordance with the invention.

Thus, it is important that while an illustrative embodiment of the present invention is described in the context of a fully functional computer (server) system with installed (or executed) software, those skilled in the art will appreciate that the software aspects of an illustrative embodiment of the present invention are capable of being distributed as a program product in a variety of forms, and that an illustrative embodiment of the present invention applies equally regardless of the particular type of media used to actually carry out the distribution. By way of example, a non exclusive list of types of media includes recordable type (tangible) media such as floppy disks, thumb drives, hard disk drives, CD ROMs, DVDs, and transmission type media such as digital and analogue communication links.