| Circuit floorplanning and placement by look-ahead enabled recursive partitioning -> Monitor Keywords |
|
|
  Circuit floorplanning and placement by look-ahead enabled recursive partitioningUSPTO Application #: 20060190889Title: Circuit floorplanning and placement by look-ahead enabled recursive partitioning Abstract: Placement or floorplanning of an integrated circuit is performed by constructing legal layouts at every level of a hierarchy of subsets of modules representing the integrated circuit, by scalably incorporating legalization into each level of the hierarchy, so that satisfiability of constraints is explicitly enforced at every level, in order to eliminate backtracking and post-hoc legalization. (end of abstract) Agent: Gates & Cooper LLP Howard Hughes Center - Los Angeles, CA, US Inventors: Jingsheng Jason Cong, Michail Romesis, Joseph R. Shinnerl USPTO Applicaton #: 20060190889 - Class: 716008000 (USPTO) Related Patent Categories: Data Processing: Design And Analysis Of Circuit Or Semiconductor Mask, Circuit Design, Floorplanning The Patent Description & Claims data below is from USPTO Patent Application 20060190889. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS-REFERENCE TO RELATED APPLICATIONS [0001] This application is related to the following co-pending and commonly-assigned application: [0002] U.S. Provisional Patent Application Ser. No. 60/644,115, filed on Jan. 14, 2005, by Jingsheng J. Cong, Michail Romesis, and Joseph R. Shinnerl, entitled "CIRCUIT FLOORPLANNING AND PLACEMENT BY LOOK-AHEAD ENABLED RECURSIVE PARTITIONING," attorneys docket number 30435.169-US-P1 (2005-328); [0003] which application is incorporated by reference herein. BACKGROUND OF THE INVENTION [0005] 1. Field of the Invention [0006] The present invention relates to the design of integrated circuits, and more specifically, to circuit floorplanning and placement. [0007] 2. Description of the Related Art [0008] (Note: This application references to various publications as indicated in the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these publications ordered according to these reference numbers can be found below in the section entitled "References." Each of these publications is incorporated in its entirety by reference herein.) [0009] Fast floorplanning and placement are critical in the hierarchical physical design of Very Large Scale Integration (VLSI) circuits. System designers require a means of rapidly estimating the variation in performance of alternative architectures and logic designs. Multiscale and mixed-size placement algorithms typically solve some form of floorplanning or coarse placement problem at the first level of approximation, in order to generate an initial coarse layout for subsequent iterative refinement. With the reuse of intellectual property (IP) modules for multi-million-gate Application Specific Integrated Circuits (ASICs) and System-On-Chip (SOC) designs, most modern integrated circuit (IC) designs consist of a large number of standard cells mixed with many big macros, such as read-only memories (ROMs), random access memories (RAMs) and other IP modules. When clusters of standard cells are placed simultaneously with macros, the clusters may be treated as soft modules. [0010] Large-scale floorplanning. Many floorplanning algorithms have been developed in recent years, varying mostly in the representation of geometric relationships among modules. They can be divided into two major categories: slicing and non-slicing algorithms. The first slicing algorithms were developed in the 1980's (e.g. [31], [35]). In the 1990's, non-slicing algorithms became more popular, especially after the introduction of the BSG [30] and Sequence Pair [29] representations. Other non-slicing representations include TCG [28], B-tree [19], CBL [26], O-tree [24], and so on. Simulated Annealing (SA) has been used to minimize area and/or wirelength under each of these representations. [0011] Until a few years ago, the inherent slowness of SA was partially hidden by the lack of any need to floorplan more than 100 blocks at a time. Recently, however, growing numbers of IP blocks have increased the sizes of most floorplanning instances, prompting researchers to seek non-stochastic approaches. [0012] Ranjan et al. [32] proposed a two-stage fast floorplanning algorithm. In the first stage, a hierarchy is generated by top-down recursive bipartitioning. Cutline orientations are selected from the bottom up in a way that keeps subregion aspect ratios close to one. In the second stage, low temperature SA improves wirelength by reshaping blocks to produce a more compact layout. Final, total wirelength was comparable to or better than that obtained by an SA-based algorithm [35], with speed-up of over 1000.times. in predictor mode (high-speed) and 20.times. in constructor mode (high-effort). [0013] More recently, a fast algorithm called Traffic [33] has been used to generate high-quality floorplans without simulated annealing. Traffic also uses two stages. In the first stage, the blocks are divided into layers by linear multi-way partitioning. In the second stage, every layer is optimized individually; the blocks in each layer are separately arranged into rows and then moved among the rows to balance row widths and reduce wirelength. In the end, pairs of rows are squeezed tightly after being transformed into trapezoids. This final step leads to very compact floorplans, but it also increases wirelength, because the cells are ordered according to their heights. [0014] The impressive speedups obtained by the last two algorithms raise the question of whether a fast deterministic approach can be used to replace the widely used SA engine with the same or better solution quality. As commonly practiced, floorplanning by recursive bipartitioning makes no guarantee that the blocks assigned to a subregion can actually be shaped and arranged there without overlap. In this scenario, defining base cases may be difficult, as many base cases may fail to have legal solutions. [0015] Large-scale mixed-size placement. Compared to standard-cell placement, most of the increased difficulty in mixed-size placement is attributable to overlap removal, or legalization. Although in general legalization is NP-complete, legalization of a standard-cell placement is typically easy, because all standard cells have the same height and differ only in their widths. Most placement tools are able to produce legal standard-cell solutions, even when little white space is available, without sacrificing much wirelength. However, when large multi-row blocks are added to the design, placement becomes similar to floorplanning in complexity. In this context, it is often possible that even a good legalization algorithm can fail to find an overlap-free placement which retains the basic structure of a given global placement. Moreover, in designs of high row utilization, i.e., low white space, experiments show that publicly available state-of-the-art software may fail to find a legal solution altogether, even when a given global placement is known to be good in both wirelength and block density distribution. [0016] Currently, the best published wirelength results are obtained by methods requiring legalization after global placement. FengShui 5.1 [36] uses recursive-bisection with iterative deletion, iterative repartitioning, relaxed rows not aligned with standard cell rows ("fractional cut'"), and a simple Tetris-style approach to legalization. APlace [37, 38] employs a multiscale, force-directed formulation. [0017] Most other previously published correct-by-construction algorithms for mixed-size placement rely on simulated annealing in some crucial way. mPG [39] builds a cluster hierarchy for multiscale optimization in a physical-hierarchy-generation framework. mPG uses simulated annealing (SA) on the Sequence-Pair [40] floorplanning representation over nested grids at every level of the cluster hierarchy for legalization. Reliance on SA slows mPG down considerably. [0018] Capo 9.3[6] proceeds top down by cutsize-driven recursive bipartitioning until certain ad-hoc tests suggest that newly generated subproblems may be difficult to legalize. At that point, standard cells in each subproblem are clustered, and these clusters are treated as soft macros. SA-based fixed-outline floorplanning is then attempted on the hard macros and soft clusters for the given subregion. If it succeeds, the locations of the macros are then fixed, and further refinement proceeds on the declustered soft macros. If it fails, then the subproblem is merged with its sibling, the previous partition of the parent subproblem is discarded, and floorplanning is attempted for the parent subproblem. In principle, this backtracking may continue indefinitely until some ancestor is successfully floorplanned or until failure at the top level occurs. In practice, the ad-hoc tests used to determine when to commence floorplanning are observed to be good enough that backtracking is only rarely needed. However, when white space is particularly scarce, e.g., less than 4%, Capo 9.3 reports failures, presumably because its ad-hoc tests are insufficient to prevent floorplanning on subproblems that are too large for its SA-based floorplanner to solve scalably. [0019] In another alternative, CPLACE [32] proposed a partitioning-based placer that incorporates explicit legalization into every level of the top-down partitioning hierarchy. In CPLACE, this progressive legalization supports accurate modeling of complex constraints such as irregular images, fixed objects, fixed IOs, large objects, timing-driven placement, and free-space distribution. However, legalization at each level is performed after partitioning without any formal assurance of its success. [0020] Consequently, although many methods for the placement [1, 2, 3, 4, 6, 7, 8, 9, 10, 14] or floorplanning [5, 15] of integrated circuits have been developed in recent years, there remains a need in the art for improved methods of placement and floorplanning of integrated circuits, especially one where the need for post-hoc legalization is completely removed. The present invention satisfies that need. SUMMARY OF THE INVENTION [0021] The present invention describes a new paradigm for the floorplacement of any combination of fixed-shape and variable-shape modules under tight fixed-outline area constraints and a wirelength objective. (The term "floorplacement" is used to refer simultaneously to any combination of floorplanning and placement.) Dramatic improvement over traditional floorplacement methods is achieved by (i) explicit construction of strictly legal layouts for every partition block at every level of a top-down hierarchy and (ii) the use of these legal layouts at intermediate levels to guarantee legal, overlap free termination at the final bottom levels of the partitioning hierarchy. By scalably incorporating legalization into the hierarchical flow, post-hoc legalization is successfully eliminated. For large floorplanning benchmarks, the present invention generates solutions with half the wirelength of state-of-the art floorplanners in orders of magnitude less run time. In particular, compared to widely used simulated annealing based floorplanners, the present invention seeks to achieve 30.times. to 500.times. speedup with better wirelength results. The present invention also has application to large-scale mixed-sized placement. BRIEF DESCRIPTION OF THE DRAWINGS Continue reading... Full patent description for Circuit floorplanning and placement by look-ahead enabled recursive partitioning Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Circuit floorplanning and placement by look-ahead enabled recursive partitioning patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Circuit floorplanning and placement by look-ahead enabled recursive partitioning or other areas of interest. ### Previous Patent Application: Apparatus and method for electronic device design Next Patent Application: Method for realizing circuit layout Industry Class: Data processing: design and analysis of circuit or semiconductor mask ### FreshPatents.com Support Thank you for viewing the Circuit floorplanning and placement by look-ahead enabled recursive partitioning patent info. IP-related news and info Results in 2.22907 seconds Other interesting Feshpatents.com categories: Accenture , Agouron Pharmaceuticals , Amgen , AT&T , Bausch & Lomb , Callaway Golf |
||
