Relocation of components for post-placement optimization

Method and apparatus for post-placement optimization of resources for connections is described. To optimize resource placement, search windows are generated responsive to driver and load components, as well as to a connection between the driver and load components. Adding in a straight-line path search window may be used as an alternative where a bypassed resource is to be relocated. Using connection-based optimization in combination with driver- and resource-based optimization results in improved optimization with negligible impact on runtime.

FIELD OF THE INVENTION

The present invention relates generally to placement of components, and more particularly to placement optimization of integrated circuit components.

BACKGROUND OF THE INVENTION

Integrated circuits are formed of many circuit elements, commonly referred to for placement as resources, cells, components, logic blocks and the like. In other words, components for an integrated design are placed relative to one another in what is known as a placement process. Data input to a conventional placer tool includes associations between components, such as connectivity data. A signal path may comprise multiple connections as three or more components or resources may be used to create a signal path. Multiple signal paths form a network of components, and that signal paths have associated target delays. After placement and routing of components, a conventional placement optimizer was used to improve placement to facilitate operating an integrating circuit at an increasingly higher clock frequency.

Conventional placement optimizers or optimizations are component or logic block based. Such conventional optimizers pick up components from an existing placement and attempt to find a better location or site to place such components of an integrated circuit. If a component site under consideration is empty, a proposed or tentative component placement may be used to evaluate for improvement in path or connection. If, however, a proposed site is presently occupied by another component, component locations are temporarily swapped to evaluate whether a connection or path delay improves. Evaluation of whether or not improvement results from moving a component to an open site or swapping components is done with a placement cost function. A placement cost function responsive to a tentative relocation of the component or swap of components is evaluated to estimate effect of such a proposed repositioning in order to select a best resulting cost, such as a lower delay time, a smaller die size, fewer connections, and the like.

Due to the number of components forming an integrated circuit, especially a complex integrated circuit, it is impractical for purposes of runtime reasons to attempt to evaluate repositioning of all possible component relocations. As not all possible relocations are attempted, optimizer quality depends on which components are tried and how tried sites for such components to be placed or relocated are selected. Conventional optimizers select sites within a small window centered about a current component position under consideration for repositioning. By limiting relocation of a component to within a window centered about such a component, runtime is reduced for purposes of optimization. However, a limited window also limits distance by which a component may be repositioned, and thus limits the degree of improvement one may obtain by optimization should a better solution be found outside such a window.

Accordingly, it would be both desirable and useful to provide optimization means that allows more room for improvement than that previously afforded by prior optimizers but which has negligible impact on runtime as compared with runtime of such prior optimization means.

SUMMARY OF THE INVENTION

An aspect of the invention is a post-placement optimization process. Provided is a simulation of an integrated circuit having simulated connections with associated delays. Collected are critical connections from the simulated connections having associated negative slack times, and the critical connections collected are ranked responsive to the negative slack times. A critical connection is selected from the ranking having a driver component and a load component. Component windows for the critical connection selected and a connection window for the critical connection selected are generated. Determined are overlaps between the connection window and each of the component windows to provide a first and a second search window. A first site is selected in the first search window for the driver component, and a second site is selected in the second search window for the load component. Costs of the first site and the second site are compared to select a cost.

An aspect of the present invention is a method for simulating relocation a component of an integrated circuit having a plurality of components coupled to one another by interconnects, where the interconnects have associated delays. Identified is at least one connection having a driver and a load component. A first component sample window is generated in response to the driver component. A second component sample window is generated in response to the load component. A connection window is generated in response to the at least one connection. A driver window is generated in response to overlap between the connection window and the first component window. A load window is generated in response to overlap between the connection window and the second component window. A site for relocating the component is determined, and the component is relocated to the location.

An aspect of the present invention is a method for simulating relocation of a component of an integrated circuit having a plurality of components coupled to one another by interconnects, where the interconnects have associated delays. A bypass component is identified. A driver component and a load component of the bypass component are selected. A first component sample window and a second component sample window are generated in response to the driver and load components, respectively. A connection window is generated in response to the at least one connection. A path window is generated responsive to the driver component and the load component. A driver window is generated in response to overlap between the connection window and the first component window. A load window is generated in response to overlap between the connection window and the second component window. Determined is a site for relocating the component, and the component is relocated to the location.

DETAILED DESCRIPTION OF THE DRAWINGS

FIG. 1is a top view block diagram of an exemplary embodiment of an integrated circuit100. Integrated circuit100comprises a plurality of components of which components100,101,102,103and104are used to provide a signal path. Components101and102are coupled to one another via connection111. Components102and103are coupled to one another via connection112. Components103and104are coupled to one another via connection113. Input placement data includes which components are to be connected to one another. Conventionally, connection delay estimates associated with connections between components are provided with placement data, such as at least in part based on connection length. Though only one path is shown here for purposes of clarity, it is well known that an integrated circuit comprises a multiplicity of signal paths or networks. It will be apparent from the description that follows that the present invention may be used to optimize a multiplicity of signal paths of an integrated circuit though only a single path optimization is illustratively shown for purposes of clarity.

Referring toFIG. 2A, there is shown integrated circuit100ofFIG. 1having component sample windows201,202, and203in accordance of one or more aspects of the present invention. For purposes of clarity, a source and a destination component are selected for improvement; however, it will be apparent that other components may be selected. Component sample window201is for a source or driver component102. Component sample window201is centered about driver component102with a component epsilon or delta of two components. Notably, an epsilon of fewer or more than two components may be used for component sample window201. Furthermore, it is not necessary that component sample window201be centered about component102, and thus an off-centered component sample window may be used.

Component sample window202is similar to component sample window201, except that component sample window202is for load component103. Source or driver component102is connected by connection112to destination or load component103, of course as indicate by input data. Direction of arrows is used to indicate signal propagation direction, namely, from an output of a component to an input of another component. Accordingly, component sample windows201and202define areas for possibly sampling components proximal to source and destination resources of connection112.

Component sample window203defines a third area. This third area is defined at least in part by connection112, or more particularly location of source component102and destination component103, and thus includes at least a portion of areas defined for possibly sampling components proximal to resources used for connection112. In other words, components sample window203is defined at least in part by a connection between two resources. Because windows201and202are generated at least in partial response to location of resources102and103, connection window203, also defined at least in part by resources102and103, will have overlapping areas. These overlapping areas are illustratively shown as driver window204and load window205.

Areas of driver window204and load window205are respectively less than areas of component sample window201and202. However, inFIG. 2Bthere is shown a top view block diagram of the integrated circuit100ofFIG. 1with a connection window213having a one-component epsilon in accordance with one or more aspects of the present invention. Thus, areas of driver window204and load window205may be expanded, as illustratively shown inFIG. 2B, by increasing component epsilon as compared to that shown inFIG. 2A. In other words, connection window213is formed having at least one component separation from resource components102and103. Accordingly, driver window214and load window215have larger intersecting areas with components sample windows201and202as compared with driver window204and load window205ofFIG. 2A. Notably, though a one-component epsilon separation from resource components102and103is illustratively shown, a larger epsilon separation may be used from resource components.

Accordingly, it should be appreciated that instead of just looking at blocks to be optimized by relocation, both position of blocks as well as their connectivity is used for evaluation. This is done by means of creating a connection window, such as connection window203or213, for identifying respective resource windows, such as resource windows204,205and214,215. By having a driver window and a load window, a driver resource may be checked for relocation within a load window, and a load resource may be checked for relocation within a driver window, as described below in more detail. Post-placement analysis may be used for optimizing one or more connections by relocation of a resource.

FIG. 3is a top view block diagram of the integrated circuit ofFIG. 1after component relocation for improvement of the path ofFIG. 1in accordance with one or more aspects of the present invention. InFIG. 3, a hypothetical new location is shown for resource102in load window215ofFIG. 2to illustratively show optimized connections311and312for coupling resources.

Referring toFIG. 4, there is shown a process flow diagram of an exemplary embodiment of an optimization process400in accordance with one or more aspects of the present invention. As described above, an estimate of connection delays is provided for an integrated circuit as part of placement input data at step399.

At step416a check is made to determine whether or not any of the connections are critical. By critical, it is meant that a connection has a negative slack time. A negative slack time indicates that a delay for a connection is in excess of a delay target. Thus, optimization process400may be used in order to improve connection delays. Accordingly, connections that already meet or exceed a target delay are not optimized. Alternatively, connections already meeting or exceeding a target delay may be optimized with process400. However, for purposes of clarity, if there are no critical connections at step416, optimization process400ends at step417.

If, however, there are connections with negative slack, then at step401, all such critical connections for an integrated circuit having a simulated placement and routing are collected. At step402critical connections are sorted into a ranked order. This facilitates identifying the most critical connections from the collection of the critical connections. The most critical connections will have the greatest negative slack, namely, are furthest away from a target delay.

At step403, a critical connection is selected from the ranking of step402. A first critical connection obtained from such a ranking may be the connection with greatest negative slack, or at least equivalent to the most critical connection, to affect the greatest benefit for runtime costs. At step404, obtained are a driver component and a load component for such a critical connection obtained at step403.

At step405, a connection window is generated responsive to the driver and load component selected at step404. Such a connection window, such as connection window203or213, may or may not have an epsilon component. At step406, as sample window for a load component of step404is generated, such as component sample window202. At step407, a sample window is generated for a driver component selected at step404, such as component sample window201.

At step408, a load window is generated. Such a load window is generated in response to area overlap of a connection window generated at step405and a sample area window for a load component window generated at step406. Examples of load windows are load windows205and215.

At step409, a driver window is generated. Such a driver window is generated in response to area overlap of a connection window generated at step405and a sample window for a driver component generated at step407. Examples of driver windows are driver windows204and214.

At step410, an optimal driver location is determined. Step410may be implemented with a function call made to a driver location optimization subroutine.

It should be understood that the term “optimal” and derivatives thereof as used herein is limited to the context of a connection having respective resource windows, such as driver and load windows, and optimization goals. It is not meant to include an optimal location as among all possible solutions of relocation of a resource anywhere on an integrated circuit. Furthermore, it should be appreciated that the depending on the type of optimization, such as “Greedy,” “Hill Climbing” and “Simulated Annealing,” among other well-known types of optimizations, an optimal location is viewed in terms of goals ascribed by one or more optimizations employed.

At step411, an optimal load location is determined. Step411may be implemented with a function call made to a load location optimization subroutine.

Determination of optimal driver location and determination of an optimal load location as in steps410and411is described in more detail with respect toFIGS. 5A and 5B.

At step412, either an optimal location for a driver or an optimal location for a load, as determined in steps410and411, respectively, is selected. In other words, only one of these two possible locations is selected for step413, where such a component is relocated. Thus, in step413, either a driver component or a load component is relocated to either a load window or a driver window, respectively. Notably, it may be established that there was no available optimization for a particular critical connection, and thus, at step413the relocate component operation would be nullity. In other words, there would be no relocation at step413.

Optionally, at step414a check is made regarding whether to examine another critical connection. It is not necessary that all critical connections be optimized prior to re-estimating delay. This is, in part, because by updating timing information for one or more critical connections, the total number of critical connections may be reduced, and thus runtime may be reduced in response to having fewer critical connections to address. However, if another critical connection is to be optimized, then another critical connection is obtained from the ranking at step403. A next critical connection obtained from the ranking may be a next most critical connection, again in order to at least attempt to obtain the most improvement for optimization runtime.

If another critical connection is not to be optimized as determined at step414, then optionally at step415a check is made regarding re-estimating connection delays. Once a critical connection has been relocated for improvement, such relocation usually impacts other connections. However, at step415, it may be found that a critical connection cannot be optimized and thus re-estimating may not prove effective. Accordingly, optimization process400may end at step417.

However, usually after optimization, it will be desirable to re-estimate delays for connections. Thus, optimization process400will usually proceed to step399for re-estimating after optional step415. Such re-estimating done post optimization of at least one critical connection should produce a different set of critical connections, or at least a different set of negative slacks with respect to such critical connections. Accordingly, if there are any remaining critical connections at step416after re-estimating at step399, then a new set of critical connections is collected at step401. In this iterative manner, an integrated circuit may be optimized for both placement of resources or components responsive to their associated connectivity.

Referring toFIGS. 5A and 5B, there are shown process flow diagrams of exemplary embodiments of driver and load location optimization subroutines510and511, respectively, in accordance with one or more aspects of the present invention. With continued reference toFIGS. 5A and 5Band renewed reference toFIGS. 2A,2B and4, though subroutines may more directly form a portion of optimization process400, for purposes for clarity, optimization process400is described as calling up subroutines510and511at steps410and411, respectively.

Driver location optimization subroutine510, at step501, obtains a site from a load window as a proposed driver site. In other words, driver subroutine510will attempt to find a location for a source component in a load window, such as load window205or215.

At step502, locations of a current driver and a proposed driver location or site are recorded. For example, driver component102may be relocated to location212of load window215. Notably, if location215was available, then a tentative placement could be made without resource swapping. However, if location212were already occupied, then the current occupant would temporarily swap or switch locations with driver component102.

At step503, cost of the proposed driver site is determined. Notably, this cost may take into account slack times of two separate connections, such as connections311and312ofFIG. 3, depending on location of a driver resource with respect to a path of which it is an element.

Evaluation of relocation cost may be done in terms slack time change. At step504, a current driver site cost or slack time is compared with a slack time for a proposed location of such a driver. At step505, the more favored cost may be retained along with an associated site or location for such a driver. The retained cost and associated location are retained as a current driver cost and location. By maintaining a most favored cost as associated with a location with a driver as a current placement, a subsequent iteration may be compared against that retained cost. Of course, location is retained in order to know how to obtain a lesser cost.

At step506, there is a check as to whether another site in a load window is to be evaluated. In other words, there is a check to determine if all sites in a load window have been evaluated. If another site in a load window is to be checked, another site is obtained from such a load window at step501as a proposed driver site. If no other site in a load window is to be checked subroutine510returns to optimization process400.

Load location optimization subroutine511is similar to driver location optimization subroutine510. However, rather than attempting to place a source component in a load window, an attempt is made to place a load component in a driver window, such as placing load component103in a driver window204or214. At step511a site from a driver window is obtained as a proposed load site. At step512, an record of locations of a current and a proposed load site is made. Again, a proposed load site may or may not involve swapping resources depending on site availability. At step513, a cost for a proposed load site is determined. Again, this cost may be stated in terms of slack time. At step514a comparison is made between a proposed load site cost and a current load site cost. As it should be understood, a current load site cost, as well as a current driver site cost in step504, for a first iteration of subroutine510or511may be base on a delay established by an initial estimating of connections delays at step399, in contrast to re-estimating for connection delays at step399.

At step515, a more favored cost and associated site are retained as a current load cost and location. For example, location222of driver window214may result in a better slack time than a current location of load component103. Thus, continuing the example, location222, as well as associated slack time of relocated load component103to location222, is retained.

At step516, a check for another site in a driver window, such as driver window215, is made. If there is another site to be checked in a driver window, then another site is obtained from that driver window as a proposed load site at step511. If there is no other site to be checked in a driver window at step516, then subroutine511returns to optimization process400.

With respect to subroutines510and511, it is stated above that a more favored cost is retained. However, it should be understood that more “favored” does not necessarily mean best. Again, what is retained will depend in part on the optimization being used. For example, by using a Hill Climbing optimization paradigm a higher cost may be retained even if it temporarily produces a larger or more negative slack time. This is because if we always used a Greedy optimization paradigm, namely, one that only accepts the best slack time between alternatives, it is possible to select local minima. Allowing up hill moves in a controlled manner is a way to avoid selecting a local minimum over a better non-local minimum.

One way to do this is to define an iteration of optimization process400as n function calls, for n a number greater than one, of subroutines510and511. In each operation, a best available move for a current situation is done even if it were to go “uphill,” such as a larger negative slack time. After an iteration of n operations, a best result found for an operation would be investigated to determine whether it was better than a result of a previous iteration. If it was better than a result of a previous iteration it would be accepted and if was worse than a previous result of a prior iteration it would be rejected. So even though a resulting algorithm would be using a Greedy optimization on an iteration level it would allow uphill moves in an operation level in order avoid being trapped in a local minima.

As mentioned with respect to step402, critical connections may be ranked by negative slack time. Though using slack time as a primary criterion for sorting, it is possible to use other criteria for sorting critical connections. For example, critical connections may be sorted based on a secondary criterion of logic level. For example, critical connections may be sorted by the number of logic levels between connections and source of a timing path. By using such a secondary criterion, consistency in terms of directionality object moves is introduced to avoid situations where different sections of a path may move away from each other while optimizing a connection or portion of such a path (“subpath”).

Furthermore, a list of potential sites may be extended beyond load window and driver window to include sites close to a connection of a critical path, as shown with respect toFIG. 6.

FIG. 6is a top view block diagram of the integrated circuit ofFIG. 1having a path connection window in accordance with one or more aspects of the present invention. Resources601,602,603and604form a path or subpath, along with connections with respective connections611,612and613. Rather than using a connection window as between a resource602and a resource603, as previously described, a connection window620and a path window623from resource601to resource603are generated bypassing resource602.

Component sample windows621and622are generated about resources601and603, respectively. Windows621and622may be epsilon windows, such as one or more components, though an epsilon of one is shown inFIG. 6. An intersection region or area as between sample component windows621and622and connection windows620defines respective load and driver windows. As in the example ofFIG. 6, load and driver windows are equivalent to component sample windows622and621, respectively, for clarity windows621and622are hereinafter referred to as driver window621and load window622.

Path window623is generated by generating a straight line from driver resource601to load resource603, bypassing resource602, where such a line has a delta component width. Such a delta width is at least a portion of a component width. Though a horizontal path window623is shown inFIG. 6, a diagonal or vertical path window may be formed. For a diagonal path window, some components may fall on a boundary. Accordingly, boundary conditions may be used. For example, a threshold percentage of a component must be met for such a component to be considered within a path window.

Sites within window623, load window622and driver window621are used to determine whether an intermediate resource, namely resource602, between resources601and603may be relocated within such windows621,622and623. Notably, because there may be overlap between sampling sites in each of windows621and623, or622and623, sites may be processed twice. To avoid such unnecessary duplication, a filter may be used such that each site is only processed once. Furthermore, other restrictions may be used for sampling sites. For example, sites may be restricted to path window623and areas within driver and load windows621and622, respectively, that intersect path window623.

With respect to relocation of resource602, if a location702provides a better solution than present location of resource602, then a more optimal result may be attained with respect to path delay as illustratively shown inFIG. 7.FIG. 7is a top view block diagram of the integrated circuit ofFIG. 1after component relocation for improvement of the path ofFIG. 6in accordance with one or more aspects of the present invention. InFIG. 7, connections611and612ofFIG. 6have been replaced with connections711and712, respectively, as resource602has been moved to location702for a better result.

FIG. 8is a process flow diagram of an exemplary embodiment of an optimization process800in accordance with one or more aspects of the present invention. With continuing reference toFIG. 8and renewed reference toFIG. 6, optimization process800comprises many of the same steps of optimization process400ofFIG. 4except that a resource is “bypassed.” Accordingly, much of the description of those previously described steps is not repeated here for purposes of clarity.

At step804, a component to be bypassed for optimizing is selected. Notably, the resource ultimately is used in the path, and thus is not bypassed in this sense. However, the component is bypassed for determining areas of possible relocation sites. This selection in the context of an intermediate resource of a path or subpath effectively selects driver and load components connected to such a component to be bypassed. This bypassed resource is connected to at least one critical connection. Steps405through409are repeated, as previously described, but for using driver and load resources of a bypassed component. At step811, a path window, such as path window623, is generated in response to driver and load resources selected at step804.

At step811, cost of relocating a bypassed resource, such as component602, to sites in path, driver and load windows, such as windows623,621and622, is determined. Notably, as described above, one or more optimization criteria may be used for selecting a site from possible sites associated with search windows. Notably, unlike steps410and411where there is an attempt to move a component of one type to a window of another type, a new location for a bypassed resource is checked in search windows of both types, as well as a path window. Notably, in a first alternative, from at least one to less than all search windows may be checked to reduce runtime. In a second alternative, only a portion of sites may be checked to reduce runtime. Moreover, a combination of the first and the second alternative may be used, as well as a combination of any of the above.

At step812, an optimal location of site evaluated in driver, load and path windows is selected. Such selection is made based on costs determined at step811. At step813, a bypassed component is relocated to a site within one of load, drive or subpath windows provided, however, such site provides an improvement over a current location of such a bypassed component.

FIG. 9is a block diagram of an exemplary embodiment of a computer system900that may be put in communication with a signal-bearing medium906in accordance with one or more aspects of the present invention. Computer system900comprises memory903which may be programmed with all or a portion of a timing engine901, estimator908and placer902. Estimator908may include or have access to timing engine901to obtain delay timing information for possible connectivity. Placer902is used to place components, as described above. Memory903is coupled to processor904, and optionally is coupled to input/output (I/O) interface905for direct memory addressing. Processor904is coupled to I/O interface905.

Signal-bearing medium906may comprise instructions907in the form of one or more programs or routines, including, but not limited to, subroutines, which, when executed by computer system900, cause execution of all or a portion of an optimization process in accordance with one or more aspects of the present invention. Instructions907may comprise all or a portion of instructions for routines400,800, as well as all or a portion of instructions for subroutines510,511.

One or more aspects of the invention are implemented as one or more program products for use with a computer system such as, for example, computer system900. The program(s) of the program product defines functions of the one or more aspects and can be contained on a variety of signal/bearing media, which include, but are not limited to: (i) information permanently stored on non-writable storage media (e.g., read-only memory devices within a computer such as CD-ROM disks readable by a CD-ROM drive); (ii) alterable information stored on writable storage media (e.g., floppy disks within a diskette drive or hard-disk drive); or (iii) information conveyed to a computer by a communications medium, such as through a computer or telephone network, including wireless communications. The latter embodiment specifically includes information downloaded from the Internet and other networks. Such signal-bearing media, when carrying computer-readable instructions that direct the functions of the invention, represent one or more aspects of the invention.

While the foregoing is directed to the preferred embodiment of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow. For example, though windows were shown for picking possible relocation sites, such possible relocation sites may be selected without windows by indexing off of driver and load sites with at least a one-component epsilon.

All trademarks are the property of their respective owners.