ISPD 2000 Abstracts

Session 1: Technology Trends [p. 2]

Circuit Design Challenges Beyond 0.18 Micron

S. Borkar (Intel)

How Thin is the ICE? How Variability and Yield Drive Physical Design

S. Nassif (IBM)

Interconnect Design and Analysis Issues in High Performance ICs

A.Devgan (IBM)

Session 2: Developments in Routing [p. 3]

Requirements for Models of Achievable Routing [p. 4]

A. B. Kahng, S. Mantik, D. Stroobandt (UCLA)

Models of achievable routing, i.e., chip wireability, rely on estimates of available and required routing resources. Required routing resources are estimated from placement, or (a priori) using wirelength estimation models. Available routing resources are estimated by calculating a nominal "supply", then taking into account such factors as the efficiency of the router and the impact of vias. Models of achievable routing can be used to optimize interconnect process parameters for future designs or to supply objectives that guide layout tools to promising solutions. Such models must be accurate in order to be useful, and must support empirical verification and calibration by actual routing results. In this paper, we discuss the validation of such models and we apply our validation process to three existing models. We find notable inaccuracies in the existing models when matched against real data. We then present a thorough analysis of the assumptions underlying these models; based on this analysis, we discuss requirements for predictors of routing resources within models of achievable routing.

DUNE: A Multi-Layer Gridless Routing System with Wire Planning [p. 12]

J. Cong, J. Fang, K.-Y. Khoo (UCLA)

In this paper, we present a multi-layer gridless detailed routing system with wire planning for deep sub-micron (DSM) physical designs. It includes a multi-layer gridless detailed routing engine that can efficiently route point-to-point connections, and a wire planning algorithm that uses exact gridless design rules (variable width and variable spacing) to accurately estimate the routing resources and distribute nets into routing regions. The wire planning method also enables efficient rip-up and reroute in gridless routing. Unlike previous approaches which explore alternatives of blocked nets by gradually tightening the design rules, our planning based approach can take the exact gridless rules and resolve the congestion and blockage at a higher level. Our experimental result shows that using the wire planning algorithm in our detailed routing system can improve the routability and also speed up the run time by 3-17 times.

Provably Good Global Routing by a New Approximation Algorithm for Multicommodity Flow [p. 19]

C. Albrecht (Univ. of Bonn)

We show how that new approximation algorithms by Garg and K&ooul;nemann for the multicommodity flow problem can be modified to solve the linear programming relaxation of the global routing problem. The algorithm presented here also provides a solution of the dual linear problem, thus gives a lower bound on the optimum maximum relative congestion. Our computation results with recent IBM processor chips show that this approach can be used in practice even for large chips and that it is superior on difficult instances where rip-up and reroute algorithms fail.

Exact Switchbox Routing with Search Space Reduction [p. 26]

F. Schmiedle, D. Unruh, B. Becker (Albert-Ludwigs Univ.)

We present an approach for exact switchbox routing that complements traditional routing techniques. It is particularly well suited for an application to dense problem instances and the completion of routing in subregions which turn out to be difficult for routing tools based on heuristic methods. The exact router proposed used symbolic methods i.e. MDDs (Multi-valued Decision Diagrams) for representation of the routing space. All possible solutions to the routing problem are represented by one single MDD and once this MDD is given, routability can be decided within constraint time. To reduce the search space of possible routing solutions, so-called forced cells are computed. Finally, experimental results are given. They show the feasibility and the practicability of the approach.

Zero-Skew Clock Tree Construction by Simultaneous Routing, Wire Sizing and Buffer Insertion [p. 33]

I-M. Liu (Univ. of Texas-Austin), T.-L. Chou (Intel), A. Aziz and D. F. Wong (Univ. of Texas-Austin)

We propose an integrated clock tree construction algorithm which performs simultaneous routing, wire sizing and buffer insertion. In existing approaches, wire sizing and clock buffer insertion are typically applied sequentially after a clock tree is generated and routed, i.e., they are done as post-processing steps. None of the known methods can perform clock routing while simultaneously considering wire sizing and buffer insertion. We introduce wire widths and levels of buffers inserted as variables in forming merging segments in the proposed Integrated Deferred-Merge Embedding (IDME) algorithm. As a result, more zero-skew merging locations are made possible and the clock trees generated are zero-skew by construction. Our experiments show that by taking the advantage offered by wire sizing, we are able to minimize phase delay as well as to reduce wire length and use less buffers.

Panel 1: The Bottom-10 Problems in EDA [p. 39]

Session 3: Issues in Interconnect [p. 40]

Pseudo Pin Assignment with Crosstalk Noise Control [p. 41]

C.-C. Chang, J. Cong (UCLA)

This paper presents a new pseudo pin assignment (PPA) algorithm with crosstalk noise control in multi-layer gridless general-area routing. We propose a two-step approach that considers obstacles and minimizes the estimated number of vias under crosstalk noise constraints. Without crosstalk noise control in PPA, the average noise after detailed routing of our test cases is 0.13-0.22 V_DD with up to 8% of nets larger than 0.3 V_DD. However, if the noise constraint of each net is set of 0.3 V_DD in PPA, the average noise reduces 15% -31% to 0.11-0.15 V_DD with no crosstalk noise violations. Even without rip-out and reroute, the detailed routing completion rate is 95%-99% and the ratio of vias to nets is only 0.7-1.2.

Aggressor Alignment for Worst-Case Coupling Noise [p. 48]

L.H. Chen, M. Marek-Sadowska (UCSB)

In this paper we study signal alignment resulting in maximum peak interconnect crosstalk noise. We consider two cases. In the first one we assume that arbitrary arrival times of input signals are feasible. In the second case we assume that timing windows are given for each aggressor input. We propose a simple procedure to find aggressor alignment for worst-case coupling in both cases.
Keywords: Crosstalk noise, aggressor alignment, interconnect coupling, signal integrity, timing window

Simultaneous Shield Insertion and Net Ordering for Capacitive and Inductive Coupling Minimization [p. 55]

L. He, K. M. Lepak (Univ. of Wisconsin)

In this paper, we first show that existing net ordering formulations to minimize noise are no longer valid with presence of inductive noise, and shield insertion is needed to minimize inductive noise. We then formulate two simultaneous shield insertion and net ordering (SINO) problems: the optimal SINO/NF problem to find a min-area SINO solution that is free of capacitive and inductive noise, and the optimal SINO/NB problem to find a min-area SINO solution that is free of capacitive noise and is under the given inductive noise bound. We reveal that both optimal SINO problems are NP-hard, and propose effective approximate algorithms for the two problems. Experiments show that our SINO/NB algorithm uses from 15% to 57% fewer shield wires when compared to separated net ordering and shield insertion procedure. Furthermore, under practical noise bounds, the SINO/NB solutions use from 44% to 67% fewer shield wires when compared to SINO/NF solutions, and use 10% to 40% fewer shield wires when compared to the theoretical lower bound for optimal SINO/NF solutions. Additionally, all our algorithms are extremely efficient to finish all examples in a few seconds. To the best of our knowledge, it is the first work that presents an in-depth study on the simultaneous shield insertion and net ordering problem to minimize both capacitive and inductive noise.
Keywords: VLSI design automation, noise minimization, shielding, net ordering.

Wire Packing: A Strong Formulation of Crosstalk-Aware Chip-Level Track/Layer Assignment with an Efficient Integer Programming Solution [p. 61]

R. Kay (Intel), R. A. Rutenbar (CMU)

By focusing on chip-wide slices of the global routing grid, making a few mild geometric assumptions about layer use, and suitably abstracting pin details, we derive an extremely efficient integer linear programming (ILP) formulation for track/layer assignment. The key technical insight is to model all constraints - both geometric and crosstalk - as cliques in an appropriate conflict graph; these cliques can be extracted quickly from the interval structures of wires in a slice. We develop a "strong" linear relaxation of this problem that almost always yields the integral optimum; this solution gives us directly the maximum number of wires that can pack legally without crosstalk risk. Experiments on synthetic netlists that match statistics of wire layouts from industrial 0.25um designs demonstrate that we can pack 100 - 1000 wires optimally, or with at worst a very few overflows, in seconds.

A Two Moment RC Delay Metric for Performance Optimization [p. 69]

C. J. Alpert, A. Devgan, C. Kashyap (IBM)

For performance optimization tasks such as floorplanning, placement, buffer insertion, wire sizing, and global routing, the Elmore RC delay metric [3] remains popular due to its simple closed form expression, fast computation speed, and fidelity with respect to simulation. More accurate delay computation methods are typically either CPU intensive or difficult to implement. To bridge this gap between accuracy and simplicity, we propose the D2M RC delay metric, which is virtually as simple and fast as the Elmore metric but is bounded above by the Elmore delay, yet it rarely is more than a few percent below the actual delay. Consequently, the metric behaves like the Elmore metric in that it generally overestimates delay, but with consistently less error. Further, the metric is extremely accurate at the far end of RC lines.

Session 4: Challenges for EDA - Analog and Incremental [p. 75]

Layout Tools for Analog ICs and Mixed-Signal SoCs: A Survey [p. 76]

R. Rutenbar (CMU), J. M. Cohn (IBM)

Layout for analog circuits has historically been a time consuming, manual, trial-and-error task. The problem is not so much the size (in terms of the number of active devices) of these designs, but rather the plethora of possible circuit and device interactions: from the chip substrate, from the devices and interconnects themselves, from the chip package. In this short survey we enumerate briefly the basic problems faced by those who need to do layout for analog and mixed-signal designs, and survey the evolution of the design tools and geometric/electrical optimization algorithms that have been directed at these problems.

Incremental Physical Design [p. 84]

J. Cong, (UCLA), M. Sarrafzadeh (Northwestern U)

Incremental modification and optimization in VLSI Computer-Aided Design (CAD) is of fundamental importance. However, it has not been investigated as a discipline. Previous research and development effort is very unfocused and incomplete. Comprehensive study of incremental algorithms and solutions in the context of CAD tool development is an open area of research with a great deal of potential. Full understanding and focused participation in research and development in the area of incremental and dynamic would help us cope with the complexity of present day VLSI systems and facilitates concurrent optimization. In this paper we formulate and survey fundamental problems in incremental physical design. Preliminary solutions to a subset of these problems will be outlined.

Session 5: Expanding the Realm of Physical Design [p. 93]

Itanium^TM Processor Clock Design [p. 94]

U. Desai, S. Tam, R. Kim, J. Zhang, S. Rusu (Intel)

The Itanium processor is Intel's first 64-bit microprocessor [1] and features a highly parallel architecture fabricated using the 0.18um process. This higher integration of features requires a significant silicon real estate and high clock loading. These factors, coupled with more prominent on-die variations because of reduced device geometries, call for special techniques to manage the clock design. The Itanium processor employs very well balanced clock routing along with distributed deskew buffers (DSK) to achieve low skew. The Itanium^TM processor also includes additional features to aid performance tuning and timing debug. This paper highlights the salient features of the Itanium processor clock design and presents clock characterization data from initial silicon.
KEYWORDS: Itanium^TM processor, IA-64, clock distribution, deskew, On-Die-Clock-Shrink.

Methodology for Repeater Insertion Management in the RTL, Layout, Floorplan and Fullchip Timing Databases of the Itanium^TM Microprocessor [p. 99]

R. McInerney, K. Leeper, T. Hill, H. Chan, B. Basaran, L. McQuiddy (Intel)

In this paper, we describe a methodology for inserting repeaters into the RTL, Layout, Floorplan and Fullchip timing databases of the Itanium^TM processor.
Keywords: Microprocessors, floorplan, repeaters, routing, timing, estimation, RC delay.

Buffer Minimization in Pass Transistor Logic [p. 105]

H. Zhou (Synopsys), A. Aziz (UT-Austin)

With the shrinking feature sizes and increasing transistor counts on chips, the push for higher speed and lower power makes it necessary to look for alternative design styles which offer better performance characteristics than static CMOS. Among them, pass transistor logic (PTL) circuits give great promise. Since the delay in a pass-transistor chain is quadratically proportional to the number of stages, and a signal may degenerate when passing through a transistor, buffers are necessary to guarantee performance and restore signal strength in PTL circuits. In this paper, we first analyze the effects of buffer insertion on a circuit and give the sufficient and necessary condition for safe buffer insertion. Then the buffer minimization problem is formulated, which asks for a minimum number of buffers to make sure that no path has length longer than a given upper bound. Although NP-hard in general, we show that, when buffers are required on multiple fan-outs, it can be solved linearly. We also consider the case when buffers are inverters, where phase assignment are done on MCNC logic synthesis and optimization benchmarks; compared with a level-by-level insertion,a large number of buffers are saved.

A Performance Optimization Method by Gate Sizing using Statistical Static Timing Analysis [p. 111]

M. Hashimoto, H. Onodera (Kyoto U.)

We propose a gate resizing method for delay and power optimization that is based on statistical static timing analysis. Our method focuses on the component of timing uncertainties due to local random fluctuation. Utilizing our method, over-design of a circuit can be eliminated and high-performance and high-reliability LSI design can be realized. The effectiveness of our method can reduce relay and power dissipation from the circuits optimized without the consideration of fluctuation.

Simulating Frequency-Dependent Current Distribution for Inductance Modeling of On-Chip Copper Interconnects [p. 117]

L.-F. Chang, K.-J. Chang, R. Mathews (Frequency Technology)

500+ MHz designs using deep-submicron (DSM) copper interconnects require accurate and efficient modeling of cladding-metals' frequency-dependent impedance [1]. In this paper, for the first time, we simulate and describe the current distribution inside a copper-based interconnect in a rich set of multi-line structures. The difference of the resistivities of copper alloy and the cladding metals causes a non-monotonic current density versus cross-wire axis relation. The same situation does not occur for the state-of-the-art aluminum processes. It enlarges the inductance by more than 12 percent. Simulating the frequency dependence of the inductance with this property, we find that PEEC [2][3] can simulate cladded wire profile to achieve accurate inductance extraction. Other approximate methods result in inaccurate and lower inductance values. A new modeling methodology based on library look-up is then proposed to make an efficient field-solver based extraction flow for realistic DSM designs.
KEYWORDS: Copper interconnect, skin-effect current distribution, cladding material, electromagnetic field solvers.

Session 6: Poster Papers [p. 121]

Datapath Routing Based on a Decongestion Metric [p. 122]

S. Raman, S. S. Sapatnekar (U. Minnesota), C. J. Alpert (IBM)

For a four-layer datapath routing environment, we present an algorithm that considers all the nets simultaneously. Routing probabilities are calculated for potential routing regions and consolidated into a congestion metric. This is followed by an iterative diversion technique where the region with the maximum congestion metric is repetitively relaxed until the track probabilities crystallize into integer values of 1 and 0. We have run the algorithm on large test cases and achieved significant routability within a small number of available tracks.

Optimal Reliable Crosstalk Driven Interconnect Optimization [p. 128]

I. H.-R. Jiang, S.-R. Pan, Y.-W. Chang, J.-Y. Jou (National Chiao-Tung U.)

As technology advances apace, crosstalk becomes a design metric of comparable importance to area and timing. This paper focuses mainly on the crosstalk issue, specifically on the impacts of physical design and process variation on crosstalk. While the feature size shrinks below 0.35 um, the impact of process variation on crosstalk increases rapidly. Hence, a crosstalk insensitive design is desirable in the ultra-deep submicron regime. In this paper, crosstalk sensitivity is referred to as the influence of process variation on crosstalk in a circuit. We show that the lower bound of crosstalk sensitivity grows quadratically, while that of crosstalk increases linearly. Therefore, designers should also consider crosstalk sensitivity, when optimizing other design objectives, such as crosstalk, area, and delay. According to our modeling, these objectives are all in posynomial forms, and thus the multi-objective optimization problem can optimally be solved by Lagrangian relaxation. Experimental results show that our method is effective and efficient. For instance, a circuit of 2856 gates and 5272 wires is optimized using only 46 minute runtime and 2.8 MB memory on a SUN UltraSPARC II 300 workstation. In particular, by relaxing Lagrange multipliers to the critical paths, it takes only two iterations for all solutions to converge to the global optimal, which is much more efficient than related previous work. This relaxation scheme provides a key insight into the rapid convergence in Lagrangian relaxation.

A Hybrid Dynamic / Quadratic Programming Algorithm for Interconnect Tree Optimization [p. 134]

Y.-Y. Mo, C. C. N. Chu (Iowa State U.)

In this paper, we present an algorithm for delay minimization of interconnect trees by simultaneous buffer insertion/sizing and wire sizing. The algorithm integrates the quadratic programming approach to handle a wire branch [1] into the dynamic programming framework [2]. Our experimental results show that our hybrid dynamic/quadratic programming algorithm is faster, more accurate, and uses much less memory than the pure dynamic programming approach.

Critical Area Computation for Missing Material Defects in VLSI Circuits [p. 140]

E. Papadopoulou (IBM)

We address the problem of computing critical area for missing material defects in a circuit layout. The extraction of critical area is the main computational problem in VLSI yield prediction. Missing material defects cause open circuits and are classified into breaks and via-blocks. Our approach is based on the L 1 medial axis of polygons and the weighted L 1 Voronoi diagram of segments. The critical area problem for both breaks and via-blocks is reduced to a weighted L 1 Voronoi diagram of segments. This reduction results in a plane sweep algorithm to compute critical area in one pass. The time complexity is O(n log n) in the case of breaks and O(n log n + K) in the case of via-blocks, where n is the size of the input and K is bounded by the number of interacting vias (in practice K is small). The critical area computation assumes square defects and reflects all possible defect sizes following the D(r) = r²₀/ r³ defect size distribution. The method is presented for rectilinear layouts.

Multi-Center Congestion Estimation and Minimization During Placement [p. 147]

M. Wang, X. Yang, K. Eguro, M. Sarrafzadeh (Northwestern U.)

As technology advances, more and more issues need to be considered in the placement stage, e.g., wirelength, congestion, timing, coupling. It is very hard to consider all of them together at the same time. Thus it is good if we can optimize one cost function without affecting others. In this paper, we will study methods to optimize congestion in placement without inflicting degradations/violations in other objectives or constraint. We give a mathematical equation to predict the overflow within a region using a normal distribution approximation. According to experiments, this equation does give a good estimation of overflow. We used this equation to find the smallest regions which have enough routing resource to alleviate the congestion and propose the flexible expansion scheme in our multi-center congestion reduction (MC²R) algorithm. Experimental results show that generally there is a correlation between the amount of reduction in congestion and the amount of change made to the placement: the more we change the placement, the more reduction in congestion we will get. However, the flexible expansion scheme is very effective in helping us reduce congestion while making only little change to the placement. Comparing to the full expansion scheme (49% congestion reduction and 6.5% change in placement), the flexible expansion scheme together with MC² R algorithm can reduce congestion by almost the same amount (42%) with much less change made to the placement. (1.8%).

A Snap-On Placement Tool [p. 153]

X. Yang, M. Wang, K. Eguro, M. Sarrafzadeh (Northwestern U.)

??? The standard cell placement problem has been extensively studied in the past twenty years. Many approaches were proposed and proven effective in practice. However, successful placement tools need enormous time in the course of development. In this paper we propose a new snap-on placement tool, which is based on multilevel hierarchical placement method. It has great flexibility to combine existing packages and techniques in its top-down framework. In addition, it can be used to build a good placement tool in a short amount of time. Some important issues in multilevel hierarchical placement are discussed here. We investigate the behavior of net-cut and wirelength objectives in global placement problem, propose a +??? level clustering technique and design a new top-down placement method based on partitioning, annealing and +??? level technique. We also work on the trade-off between solution quality and running time during the hierarchical placement. Experimental results show that strength of proposed placement tool, it produces very good results on all benchmarks and the best known result on the largest MCNC benchmark. (avql).

???

A Practical Clock Tree Synthesis for Semi-Synchronous Circuit [p. 159]

M. Toyonaga, K. Kurokawa, T. Yasui (Matsushita), A. Takahashi (Tokyo Institute)

In this paper, we propose a new clock tree synthesis method for semi-synchronous circuits. A clock tree obtained by the proposed method is a multi-level multi-way clock tree such that a clock-input timing of each register is a multiple of a predefined unit delay and the length of interconnection from a parent node to its child is upper bounded. The clock trees are constructed for several practical circuits. The size of each clock tree is comparable to a zero skew clock tree. In order to assure the practical quality, they are examined under the five delay conditions, which cover various environmental and manufacturing conditions. As a result, they are proved stable under each condition and improve the clock speed up to 17.3 % against the zero skew clock trees.
Keywords: Semi-synchronous, clock-input timing, clock scheduling, environmental and manufacturing conditions, zero skew clock tree, various timing clock tree.

Panel 2: EDA and the Internet [p. 165]

Session 7: Floorplanning and Partitioning [p. 167]

An Enhanced Perturbing Algorithm for Floorplan Design Using the O-tree Representation [p. 168]

Y. Pang, C.-K. Cheng (UCSD), T. Yoshimura (NEC)

Recently, a deterministic algorithm based on the O-tree representation has been proposed. This method generates excellent layout results on MCNC test cases with O(n³) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n²). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time.

Floorplan Area Minimization using Lagrangian Relaxation [p. 174]

F. Y. Young (Chinese U. of Hong Kong), C. C. N. Chu (Iowa State U.), W. S. Luk, Y. C Wong (Synopsys)

Floorplan area minimization is an important problem because many modules have shape flexibilities during the floorplanning stage. Area minimization in general non-slicing floorplan is a complicated problem. Many previous works have attempted to tackle this problem [9; 6; 5; 1] using heuristics or numerical methods but none of them can solve it optimally and efficiently. In this paper, we show how this problem can be solved optimally by a geometric programming using Lagrangian relaxation. The resulting Lagrangian relaxation subproblem is so simple that the size of each module can be found in constant time. We implemented our idea in a simulated annealing framework based on the sequence pair representation. The area minimization procedure is invoked in every iteration of the annealing process but the total execution time is still very much faster than that of the most updated previous work [4]. For a benchmark data with 49 modules, we take 19.5 hours using a 270 MHz Sun Ultra 5 while the convex programming approach in [4] takes seven days using a 250 MHz DEC Alpha. This area minimization method will be applicable to any other floorplanning algorithm which uses constraint graphs to find module positions in the final packing.

Planning Buffer Locations by Network Flows [p. 180]

X. Tang, D. F. Wong (UT-Austin)

The problem of planning the locations of large number of buffers is of utmost importance in deep submicron VLSI design. Recently, Cong et al in p1] proposed an algorithm to directly address this problem. Given a placement of circuit blocks, a key step in [1] is to use the free space between the circuit blocks for inserting as many buffers as possible. This step is very important because if all buffers can be inserted into existing spaces, no expansion of chip area would be needed. An effective greedy heuristic was used in [1] for this step. In this paper, we give a polynomial-time optimal algorithm for solving the problem of inserting maximum number of buffers into the free space between the circuit blocks. In the case where the "costs" of placing a buffer at different locations are different, we can guarantee to insert maximum number of buffers with minimum total cost. Our algorithm is based on efficient min-cost network-flow computations.

Routability-Driven Repeater Block Planning for Interconnect-Centric Floorplanning [p. 186]

P. Sarkar, V. Sundararaman, C.-K. Koh (Purdue U.)

In this paper, we present a repeater block planning algorithm for interconnect-centric floorplanning. We introduce the concept of independent feasible regions for repeaters and derive an analytical formula for their computation. We develop a routability-driven repeater clustering algorithm to perform repeater block planning based on iterative deletion. The goal is to obtain a high quality solution for the repeater block locations so that performance-driven interconnect synthesis at the routing stage can be carried out with ease, while minimizing the chip area. Experimental results show that our method increases the percentage of all global nets that meet their target delays from 67.5% in [8] to 85%. Meanwhile, our approach is able to minimize the expected routing congestion, making it easier for performance-driven routers to synthesize global nets that require the insertion of repeaters to meet timing constraints.

Multilevel Cooperative Search: Application to the Circuit / Hypergraph Partitioning Problem [p. 192]

M. Ouyang (U. Nebraska-Lincoln), M. Toulouse (U. Manitoba), K. Thulasiraman (U. Oklahoma), F. Glover (U. Colorado), J. Deogun (U. Nebraska-Lincoln)

In this paper, we present an adaptation for hypergraph partitioning of the multilevel cooperative search paradigm first introduce by Toulouse, Thulasiraman, and Glover [15]. We also introduce a new approach for coarsening hypergraphs, and describe a parallel implementation of this algorithm on the SGI O200 system. Experiments on ISPD98 benchmark suite of circuits show, for 4-way and 8-way partitioning, a reduction of 3% to 15% on hyperedge-cut compared to hMETIS. Bisections of hypergraphs based on our algorithm also outperforms hMETIS, although more modestly.

Session 8: Complexity and Overlapping Design Space [p. 199]

Coping with Physical Design Problem Sizes in the Post-Moore's Law Era

T. Gao, P. Parakh (Monterey)

Physopt

S. Krishnamoorty, S. Thakur (Synopsys)

Session 9: Floorplanning: Use and Abuse [p. 200]

What is a Floorplan? [p. 201]

R. Otten (TU-Delft)

This paper surveys the more important floorplan models and their use in the backend of chip design. Floorplans are here considered as data structures that capture the relative positions of objects in a plane. This is in correspondence with how they were introduced in design automation in the early eighties: as a generalization of placement, that is the manipulation of geometrically fixed objects in order to get an overlap-free arrangement of these objects in a plane region. The introduction of the floorplanning concept not only liberated back-end design from its (manual) puzzle character and its intractable and sometimes even undecidable problems, but also enabled hierarchical design, even taking a functional hierarchy and transforming it by stepwise refinement into a floorplan with a compatible representation. The elegance of that procedure was so overpowering that many identified floorplanning with hierarchical back-end design. That floorplanning proves to be a powerful notion by itself becomes once more apparent, since almost all modern effective "placement" procedures are in essence floorplanning followed by packing or some other "legalization" stage.

Classical Floorplanning Harmful? [p. 207]

A. B. Kahng (UCLA)

Classical floorplanning formulations may lead researchers to solve the wrong problems. This paper points out several examples, including (i) the preoccupation with packing-driven, as opposed to connectivity-driven, problem formulations and benchmarking standards; (ii) the preoccupation with rectangular (and L or T shaped) block shapes; and (iii) the lack of attention to algorithm scalability, fixed-die layout requirements, and the overall RTL-down methodology context. The right problem formulations must match the purpose and context of prevailing RTL-down design methodologies, and must be neither overconstrained nor underconstrained. The right solution ingredients are those which are scalable while delivering good solution quality according to relevant metrics. We also describe new problem formulations and solution ingredients, notably a perfect rectilinear floorplanning formulation that seeks zero-whitespace, perfectly packed rectilinear floorplans in a fixed-die regime. The paper closes with a list of questions for future research.

Panel Discussion : The Right Floorplanning Formulations for Future Chip Implementation Methodologies [p. 214]