Session 4C: New Techniques for Physical Design Optimization

4C-1 (Time: 10:15 - 10:40)

Title DPlace2.0: A Stable and Efficient Analytical Placement Based on Diffusion
Author Tao Luo, *David Z. Pan (Univ. of Texas, Austin, USA)
Abstract Nowadays a placement problem often involves multi-million objects and excessive fixed blockages. We present a new global placement algorithm that scales well to the modern large-scale circuit placement problems. We simulate the natural diffusion process to spread cells smoothly over the placement region, and use both analytical and discrete techniques to improve the wire length. Although any analytical wire length technique can be used in our new framework, by using the quadratic wire length model, the hessian of our formulation is extremely sparse compared with conventional formulations, which brings 24x speed up on quadratic solver. We also propose a wire linearization technique that transform quadratic star model into HPWL exactly. The overall runtime of our tool is close to the fastest placement tool in existing literature and significantly better than others. And meanwhile, we obtain competitive wire length results to the best known ones. The average total wire length is 2.2\% higher than mPL6, 0.2\%, 3.1\%, and 9.1\% better than FastPlace3.0, APlace2.0, and Capo10.2 respectively.

4C-2 (Time: 10:40 - 11:05)

Title Total Power Optimization Combining Placement, Sizing and Multi-Vt Through Slack Distribution Management
Author Tao Luo (Univ. of Texas, Austin, USA), David Newmark (Advanced Micro Devices, USA), *David Z. Pan (Univ. of Texas, Austin, USA)
Abstract Power dissipation is quickly becoming one of the most important limiters in nanometer IC design for leakage increases exponentially as the technology scaling down. However, power and timing are often conflicting objectives during optimization. In this paper, we propose a novel total power optimization flow under performance constraint. Instead of using placement, gate sizing, and multiple-Vt assignment techniques independently, we combine them together through the concept of slack distribution management to maximize the potential for power reduction. We propose to use the linear programming (LP) based placement and the geometric programming (GP) based gate sizing formulations to improve the slack distribution, which helps to maximize the total power reduction during the Vt-assignment stage. Our formulations include important practical design constraints, such as slew, noise and short circuit power, which were often ignored previously. We tested our algorithm on a set of industrial-strength manually optimized circuits from a multi-GHz 65nm microprocessor, and obtained very promising results. To our best knowledge, this is the first work that combines placement, gate sizing and Vt swapping systematically for total power (and in particular leakage) management.

4C-3 (Time: 11:05 - 11:30)

Title An Innovative Steiner Tree Based Approach for Polygon Partitioning
Author Yongqiang Lu, *Qing Su, Jamil Kawa (Synopsys, USA)
Abstract As device technology continues to scale past 65nm, the number of geometries added by the heavy application of resolution enhancement techniques (RET) continues to grow. This is a direct consequence of the 193nm lithography having to suffice for tighter geometries with every new node. As a result issues associated with mask data preparation (MDP) such as complexity, run time, and quality are growing in severity. As one major and core step in MDP, polygon partitioning converts the complex layout shapes into trapezoids suitable for mask writing. The partitioning run time and quality of the resulting polygon partitions directly impacts the cost, integrity, and quality of the written mask. In this work, we introduce an innovative approach to solve the polygon partition quality problem by constructing a variant Steiner minimal tree: minimal partition tree (MPT). We prove the equivalence between the MPT and the optimal polygon partition. Also, the search space for MPT is further reduced for the efficiency of the MPT algorithms. Finally, a generic MPT algorithm flow and a linear-time heuristic algorithm based on it are proposed. Experimental results show that this new approach and the associated proposed algorithm solve the polygon partitioning problems with very promising and high quality results.

4C-4 (Time: 11:30 - 11:55)

Title An MILP-Based Wire Spreading Algorithm for PSM-Aware Layout Modification
Author *Ming-Chao Tsai, Yung-Chia Lin, Ting-Chi Wang (Nat’l Tsing Hua Univ., Taiwan)
Abstract Phase shifting mask (PSM) is a promising resolution enhancement technique, which is used in the deep sub-wavelength lithography of the VLSI fabrication process. However, applying the PSM technique requires the layout to be free of phase conflict. In this paper, we present an MILP-based layout modification algorithm which solves the phase conflict problem by wire spreading. Unlike existing layout modification methods which first solves the phase conflict problem by removing edges from the layout-associated conflict graphs and then tries to revise the layout to match the resultant conflict graphs, our algorithm simultaneously considers the phase conflict problem and the feasibility of modifying the layout. The experimental results indicate that without increasing the chip size, the phase conflict problem can be well tackled with minimal perturbation to the layout.

4C-5 (Time: 11:55 - 12:08)

Title Low Power Clock Buffer Planning Methodology in F-D Placement for Large Scale Circuit Design
Author *Yanfeng Wang, Qiang Zhou, Yici Cai (Tsinghua Univ., China), Jiang Hu (Texas A&M Univ., USA), Xianlong Hong, Jinian Bian (Tsinghua Univ., China)
Abstract Traditionally, clock network layout is performed after cell placement. Such methodology is facing a serious problem in nanometer IC designs where people tend to use huge clock buffers for robustness against variations. That is, clock buffers are often placed far from ideal locations to avoid overlap with logic cells. As a result, both power dissipation and timing are degraded. In order to solve this problem, we propose a low power clock buffer planning methodology which is integrated with cell placement. A Bin-Divided Grouping algorithm is developed to construct virtual buffer tree, which can explicitly model the clock buffers in placement. The virtual buffer tree is dynamically updated during the placement to reflect the changes of latch locations. To reduce power dissipation, latch clamping is incorporated with the clock buffer planning. The experimental results show that our method can reduce clock power significantly by 21% on average.

4C-6 (Time: 12:08 - 12:21)

Title Power Grid Analysis Benchmarks
Author *Sani R. Nassif (IBM, USA)
Abstract Benchmarks are an immensely useful tool in performing research since they allow for rapid and clear comparison between different approaches to solving CAD problems. Recent experience from the placement and routing areas suggests that the ready availability of realistic industrial-size benchmarks can energize research in a given area, and can even lead to significant breakthroughs. To this end, we are making a number of power grid analysis benchmarks available for the public. These are all drawn from real designs, and vary over a reasonable range of size and difficulty thereby making studies of algorithm complexity possible. This paper documents the format for the various benchmarks, and give details for their access.
No Slides
Last Updated on: January 31, 2008