Abstract:
Optimizing circuits having a congested placement with a timing critical placement map includes identifying critical circuit components in the placement map and determining failing circuit components in the placement map; determining “non-critical” circuit components safe to be moved; removing selected non critical from the placement map; and optimizing the critical circuit components in a new partial placement image of said map; and reinserting the “non -critical” circuit components back into said placement image. The optimization is performed by circuit transformation operating in congested regions of the placement image enabling cell insertion and modifications that increase cell size.

Description:
FIELD OF THE INVENTION 
     The present invention relates to a method of enabling the optimization of circuits in a physically blocked or congested placement image while preserving the existing placements of timing critical circuits. More specifically, it is a method of inserting or modifying circuits by inserting at exact placement locations in the presence of interference or congestion. 
     BACKGROUND 
     Circuit timing in modern VLSI design is greatly impacted by the placement of circuits within the design image. The relative physical placements impact the wire delays and circuit delays due to changes in length as well as changes in capacitance and resistance between the circuits. It is therefore important to know or estimate the circuit placements during timing closure, allowing circuit optimizations to assess and measure the viability of cell changes. Such methods are crucial in helping prevent optimizations from creating congestion or cell overlaps which can counteract timing closure efforts. 
     Timing closure tools rely on a variety of estimations throughout the timing closure process, and operations in the physical placement domain also leverage this behavior. Tools use the approximations to help reduce computation complexity and decrease turn around time. During the initial phases of optimization a design will usually have a multitude of timing problems that require attention. Using estimates allows for fast optimization, and helps take down gross problems quickly. As the timing of the chip improves and the timing closure flow progresses, automated flows increase the accuracy of their estimations to ensure the tool is working on the right problems. 
     Placement driven synthesis provides multiple placement techniques allowing circuit transformations to repair timing violations, including estimated modes and high accuracy modes. One estimated technique is the bin-based placement model. This model divides the placement image into a collection of regions containing circuits, called bins. The bin based model allows for a fast computation of bin size and provides a mechanism to compute the relative circuit location which can be used by steiner wire calculations as a first order approximation for full chip timing. This model allows optimizations to make relatively quick decisions on whether a particular section of a chip will support an increase of physical cell size. A placement legalization Step is required after making any changes to realize the final circuit placements. 
     As timing closure progresses, it becomes advantageous to accurately predict the impact of placement related changes on the design. This can be achieved by restricting placement legalization and using a high accuracy incremental exact-placement model. The high accuracy placement technique available to optimizations is exact placement. In this exact placement, model the optimization insert cells into existing open-placement locations. The placements are legal and will not produce overlaps. The benefit of this technique is that the optimization can evaluate the real placements that allow measuring the timing to a high degree of accuracy. Because the method does not require legalization there are no side effects to existing logic. The drawback of that technique is that localized areas of congestion and physical image fragmentation can make it difficult to find existing open placement locations, especially for larger circuit sizes. 
       FIG. 1A  of the prior art illustrates a section of the chip that is under optimization using the exact placement model. In the example, the cell labeled “O” is optimized and a circuit optimization determines that a buffer is needed to repair a violation. In the illustration the “x” mark denotes the requested target placement location of the new cell, whereas the cell labeled “A” is the desired size of the open placement location. 
       FIG. 1B  shows a prior art exemplary outcome of an optimization using an exact placement model. In the example, the placement tool was able to find an open placement location near the target location. Upon finding the open placement location, the optimization can decide whether the open placement location is suitable to repair the violation under consideration. 
     Although the estimated model offers a fast way to optimize circuits with consideration to the physical domain, the primary drawback of the model is that it requires circuit legalization to correct overlaps. The legalization may have deleterious effects on the critical path timing. 
     A drawback of the exact placement model is that it requires open space in the existing placement image for new additions or modifications within proximity to the net under optimization. The open space can be unfounded due to congestion or design fragmentation. In other scenarios, the open space may be too far outside of the wiring bounding box, causing the optimization to evaluate a free location that would otherwise fail due to electrical or timing constraints. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the present invention will be understood and appreciated more fully from the following detailed description, taken in conjunction with the accompanying drawings in which: 
         FIG. 1A  is a sample physical region of a chip image along with the desired cell to be inserted into the image and the desired placement location, as known in the prior art. 
         FIG. 1B  is a new cell inserted into an existing open placement location, as known in the prior art. 
         FIG. 2  is a flow chart according to one embodiment of the invention; 
         FIG. 3A  is a visual representation of the placement image prior to Step  206  in an embodiment of the invention. 
         FIG. 3B  is a visual representation of the placement image after Step  206  in an embodiment of the invention. The cells labeled “NC” are non-critical. 
         FIG. 3C  is a visual representation of the placement image after Step  207  in an embodiment of the invention. 
         FIG. 3D  is a visual representation of the placement image after Step  208  in an embodiment of the invention. 
         FIG. 3E  is an exemplary visual representation of the placement image after Step  209  in an embodiment of the invention. 
         FIG. 3F  is an exemplary visual representation of the placement image after Step  213  in an embodiment of the invention. 
         FIG. 4  is a flow chart according to one embodiment of the invention as it pertains to a late timing optimization. 
         FIG. 5  is a flow chart according to one embodiment of the invention as it pertains to repairing hold timing violations. 
     
    
    
     SUMMARY 
     In one aspect, an embodiment enables optimizations to find open exact placement locations in a congested placement image for buffer insertion or other cell size manipulation, improving hold timing take-down while limiting side effects to critical setup slacks. The embodiment provides a seamless mechanism that allows newly inserted and/or manipulated cells to automatically displace non-critical cells. 
     In another aspect, an embodiment provides a timing critical placement image map, usable for optimization in which only the critical-circuit components exist in the placement image map, and are locked in place during subsequent placement image legalization. 
     In yet another aspect, an embodiment incorporates a combination that provides flexibility of an estimated placement model, wherein less critical logic are moved at the behest of critical paths that require the image resource along with the placement precision of the exact model for the critical logic under optimization. 
     In still another aspect, an embodiment provides circuit transformation optimizations to operate in congested regions of the placement image, enabling cell insertion and modifications that increase cell size that would otherwise be prohibited. At the same time, it enables optimizations to measure the high accuracy timing that is afforded by obtaining legal physical placement locations. The characteristic allows optimizations to operate on timing critical logic and make progress on difficult paths while preserving the timing of a surrounding critical logic. 
     In a further aspect, a method is provided for optimizing circuits having a congested placement with a timing critical placement map including: using a computer, identifying critical circuit components in a placement map and determining failing circuit components in said placement map; determining non-critical circuit components safe to be moved; removing selected non-critical circuit components from said placement map to generate a new partial placement map; optimizing said critical circuit components in said new partial placement map; and reinserting said non-critical circuit components back into said placement map. 
     DETAILED DESCRIPTION 
     In the following description, numerous specific details are set forth to provide a thorough understanding of embodiments of the present invention. However, it can be recognized that embodiments of the disclosure can be practiced without the specific details. 
     The timing closure flows includes a placement-driven synthesis. This type of flow is usually iterative, and the accuracy of the timing models increases as the overall chip timing improves. At the onset of placement-driven synthesis, an estimated placement model (such as bin based) is widely used, but as the timing critical paths are fully realized, the tools naturally attempt to limit design perturbation. The critical-only incremental placement model provides a continuum between the coarse placement model and the exact placement model. 
     The timing critical-only incremental placement model operates on a legally placed design. Like the exact placement model, it also allows optimizations to search for open placement locations, helping to ensure that critical path changes are measured precisely. However, unlike the exact placement model, the timing critical-only model alters the physical image by removing the timing non-critical cells, creating an appearance of free space and can allow progress in locally congested regions that were otherwise impossible. Further, the timing critical-only model locks timing critical cells in place. This feature ensures that the circuit modifications performed will withstand legalization and that surrounding logic does not degrade. 
     The timing critical-only incremental placement model is well suited for hold timing violation repairs. The hold timing closure is usually deferred until after a setup timing optimization has been performed, leaving the tool with several challenges. The setup timing closure may leave the placement image restricted or fragmented, inhibiting the hold-fail optimization from inserting or modifying the logic to repair those violations. The hold timing closure tool may also limit the introduction of new problems since the bulk of the setup timing optimization is already performed. 
     A hold violation repair is only an illustrative example of optimizations that can be used in which any logic optimization working with exact placement locations—as any design automation physical synthesis tool does—will benefit from that approach. By way of an example, inserting buffers or inverters on delay wires, resizing gates to larger faster gates and the like, potentially can increase the area of the design. 
     Moreover, the definition of what is critical logic (also referred to as critical circuit components) is flexible as well. It may be the logic having a failing slack, or it may be the logic in a highly congested region that is likely to cause disruption if an overlap is allowed. A key aspect of an embodiment of the invention is that only the non-critical logic will be allowed to move once the optimization has been completed and the overlaps are resolved. This approach works to minimize any negative impact to the non-critical logic that was not included in the incremental placement model. To do this, it can leverage well known methods of smooth spreading to ameliorate any overlaps created by the incremental critical-only model. 
     Referring to  FIG. 2 , a flow chart is described according to one embodiment. In Step  200 , the flow chart identifies timing non-critical logic that can be moved to repair existing violations. The timing non-critical gate refers to a circuit in which a change to its physical placement will not degrade the timing below an acceptable threshold or introduce a new timing violation. One or several criterion can be used to determine the non-critical aspect of a gate including setup slack, hold slack, slew, capacitance, and the like. The circuit timing can be measured against a threshold value which can be further adjusted by increasing or decreasing the set of non-critical candidates. 
       FIG. 3A  illustrates an example of an initial placement image, and  FIG. 3B  depicts the same image after identification of the non-critical cells. Upon determining the set of timing non-critical gates in the cell image, Step  201  temporarily removes the non-critical cells from the exact placement image. This step does not change the placement of the circuits, instead it simply removes them from the placement image, creating the appearance of a free space that, otherwise, may not be present to the optimization. 
       FIG. 3C  is a visual representation of the circuit image following Step  201  and represents a view of the placement image seen during optimization. Step  202  proceeds with the optimization of any failing gates using the exact placement model. Because non-critical gates were removed from the placement image, the optimization can find and use placement resources that previously were not available. 
     Referring to  FIG. 3D , a post-optimization takes place after two circuits were inserted into the image with exact placements. Upon completion of the optimization, in Step  203 , the non-critical circuits that were removed from the placement image are reinstated. 
     Referring to  FIG. 3E , a further example is shown that illustrates two placement overlaps that were created in the circuit optimization in Step  202 . Step  204  checks and determines whether any placement overlaps exists. If there are no placement overlaps, the program proceeds to Step  205 . 
     To resolve the placement overlaps, Step  206  locks the cell placement of all critical logic in the chip image. A critical circuit is a set of all other circuits not in the set of non-critical circuits as identified in Step  200 . Locking the critical logic prevents future placement legalization from changing the placements of the circuits, ensuring that their timing does not degrade. New cells added by Step  206  are also present in the placement image, and are, therefore, in the set of the critical cells and their placements are legal. 
     Step  207  initiates the process of legalizing the placement image. Placement algorithms can be applied to resolve the overlaps, preferably by way of smooth-spreading techniques that minimize the magnitude of individual cell displacements. 
     Referring to  FIG. 3F , an example is illustrated of the non-critical cell movement that can occur during the legalization process. Step  208  restores the original placement characteristics of the cell by removing any cell locks or fix-in-place directives that were applied by Step  206 . Step  209  terminates the process. 
     Referring to  FIG. 4 , flow chart  400  illustrates a slow chip design optimization of a chip using an incremental exact placement. Step  401  determines whether the design is of good quality. In the example, a design is deem to be of good quality when the slacks meet or exceed a late slack threshold, i.e., which is the metric under optimization. Branching to a decision block follows. If the response is ‘Yes’, the flow chart branches to Step  412 , i.e., to the END. If the answer is ‘No’, it branches to Step  403 , wherein the timing late mode non-critical logic is identified, e.g., having a slack greater than the desired slack and further that is not in a locally dense area. In Step  404 , any non-critical logic is removed from the placement. Step  405  illustrates a new space that is now available, allowing optimizing critical logic in a partial placement image with a selected late mode optimization that includes, for example, resizing and/or buffering. 
     Next, Step  406  shows the optimization completed, and the non-critical logic returns to the image map. In Step  407 , a decision determines whether placement overlaps exist. Referring to the decision block, if the answer is ‘No’, the task is completed and the flow chart terminates (END). Otherwise, in Step  409 , a lock/fix of the critical logic is put in place, and is followed by Step  410 , wherein the non-critical logic is legalized. Next, it branches to Step  411  in which the critical logic is unlocked/reverse fix. In Step  412 , the optimization terminates. 
     Referring now to  FIG. 5 , an exemplary embodiment pertaining to the hold violation repairs is illustrated. Referring to the diagram, Steps  500 - 505  make a first attempt to resolve the hold violations without perturbation before proceeding to Step  506  which may introduce minimal perturbation. Step  500  initiates by checking the design for the worst hold slack. It is advantageous for the placement image at that Step to be fully realized with each cell in the design having legal placements, which allows an accurate measurement of chip timing and successive circuit optimization. Step  501  checks and determines whether the worst hold slack exceeds a user specified threshold. If the logic is greater than the threshold of failure, then the flow terminates by proceeding to Step  502 . If slack violations do exist below the threshold, then the flow advances to Step  503 . 
     In Step  503 , the optimization repairs the design using the exact placement model. In the model, the hold repair optimizations can find existing open placement locations for new or pre-existing logic, making it possible for the tool to perform circuit change without disturbing the existing logic. A benefit of the present strategy is that the surrounding logic does not move, thereby preserving its timing. Step  504  again checks to determine whether the previous optimizations are closed on the hold failures. If the design is indeed closed, then the optimization proceeds to Step  505 , ending the optimizations. Otherwise, if any hold violations still remain, the flow advances to Step  506 . In this Step, the flow identifies the non-critical logic that can be displaced to allow for the repair to hold violations. (Note: the critical logic includes circuits in which a change to its physical placement can degrade the timing but the delta in slack will still be above an acceptable threshold or does not introduce a new timing violation). One or several criteria may be used to determine the non-critical aspect of a gate including, setup slack, hold slack, slew, capacitance, and the like. The circuit timing can be measured against a threshold value which can be further adjusted to increase or to decrease the set of non-critical candidates. Upon determining the set of timing non-critical gates in the cell image, Step  507  temporarily removes them from the exact placement image. This step does not alter the placement of the circuits, instead it simply removes them from the placement image, creating the appearance of free space that otherwise would not be present during the optimization. 
     Referring back to  FIG. 3C , a visual representation illustrates the circuit image following Step  507 , i.e., a view of the placement image as seen during optimization by the exact placement model. Step  508  proceeds with the optimization of any failing gates using the exact placement model. Since non-critical gates were removed from the placement image, the optimization will find and use placement resources that were previously not available. 
     Referring now back to  FIG. 3D , the post-optimization illustrates following two circuits having been inserted in the image in exact placements. Upon completing the optimization, Step  509  reinstates the non-critical circuits that were removed from the placement image. 
     Referring back to  FIG. 3E , two placement overlaps that were created during circuit optimizations previously described in Step  508  are illustrated. Step  510  checks to determine whether placement overlaps exists. If no placement overlaps are present, the program proceeds to Step  511 . To resolve the placement overlaps, Step  512  locks or fixes-in-place the cell placement of all the critical logic in the chip image, the critical circuit being the set of all the other circuits not in the set of non-critical circuits as previously identified in Step  506 . In Step  513 , locking the critical logic prevents the future placement legalization from changing the placements of the circuits, thereby ensuring that their timing will not degrade. New cells inserted into the placement image are also in the set of critical cells, their placements being legal. 
     Step  513  initiates the process of legalizing the placement image. It is at this phase that placement algorithms can be applied to resolve overlaps, preferably through the use of smooth-spreading techniques that minimize the magnitude of individual cell displacements.  FIG. 3F  is an example of the non-critical cell movement occurring during the legalization phase. 
     Step  514  restores the original placement characteristics of the cell by removing any cell locks or fixing-in-place directives that were applied at Step  512 . Finally, Step  515  brings the flow to an END. 
     Embodiments of the present invention provide a method of enabling the optimization of circuits in a physically blocked or congested placement image while preserving the existing placements of timing critical circuits. More specifically it is a method of inserting or modifying circuits by inserting at exact placement locations in the presence of interference or congestion. 
     While the present disclosure has been particularly shown and described with respect to preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in forms and details may be made without departing from the spirit and scope of the present disclosure. It is therefore intended that the present disclosure not be limited to the exact forms and details described and illustrated, but fall within the scope of the appended claims.