(Back to Session Schedule)

The 24th Asia and South Pacific Design Automation Conference

Session 7C  Placement
Time: 10:20 - 12:00 Thursday, January 24, 2019
Location: Room Venus
Chairs: Ting-Chi Wang (National Tsing Hua University), Yasuhiro Takashima (University of Kitakyushu, Japan)

Best Paper Candidate
7C-1 (Time: 10:20 - 10:45)
TitleDiffusion Break-Aware Leakage Power Optimization and Detailed Placement in Sub-10nm VLSI
AuthorSun ik Heo (Samsung Electronics Co., Ltd., Republic of Korea), *Andrew B. Kahng, Minsoo Kim, Lutong Wang (UC San Diego, U.S.A.)
Pagepp. 550 - 556
Keywordleakage, placement, diffusion break, optimization, local layout effect
AbstractA diffusion break (DB) isolates two neighboring devices in a standard cell-based design and has a stress effect on delay and leakage power. In foundry sub-10nm design enablements, device performance is changed according to the type of DB – single diffusion break (SDB) or double diffusion break (DDB) – that is used in the library cell layout. Crucially, local layout effect (LLE) can substantially affect device performance and leakage. Our present work focuses on the 2nd DB effect, a type of LLE in which distance to the second-closest DB (i.e., a distance that depends on the placement of a given cell’s neighboring cell) also impacts performance of a given device. In this work, we implement a 2nd DB-aware timing and leakage analysis flow, and show how a lack of 2nd DB awareness can misguide current optimization in place-and-route stages. We then develop 2nd DB-aware leakage optimization and detailed placement heuristics. Experimental results in a scaled foundry 14nm technology indicate that our 2nd DB-aware analysis and optimization flow achieves, on average, 80% recovery of the leakage increment that is induced by the 2nd DB effect, without changing design performance.

7C-2 (Time: 10:45 - 11:10)
TitleMDP-trees: Multi-Domain Macro Placement for Ultra Large-Scale Mixed-Size Designs
Author*Yen-Chun Liu (National Taiwan University, Taiwan), Tung-Chieh Chen (Maxeda Technology Inc., Taiwan), Yao Wen Chang, Sy-Yen Kuo (National Taiwan University, Taiwan)
Pagepp. 557 - 562
KeywordPlacement, Macro Placement, Mixed-Size Placement
AbstractIn this paper, we present a new hybrid representation of slicing trees and multi-packing trees, called multi-domain-packing trees (MDP-trees), for macro placement to handle ultra large-scale multidomain mixed-size designs. A multi-domain design typically consists of a set of mixed-size domains, each with hundreds/thousands of large macros and (tens of) millions of standard cells, which is often seen in modern high-end applications (e.g., 4G LTE products and upcoming 5G ones). To the best of our knowledge, there is still no published work specifically tackling the multi-domain macro placement. Based on binary trees, the MDP-tree is very efficient and effective for handling macro placement with multiple domains. Previous works on macro placement can handle only single-domain designs, which do not consider the global interactions among domains. In contrast, our MDPtrees optimize the interconnections among domains and macro/cell positions simultaneously. The area of each domain is well reserved, and the macro displacement is minimized from initial macro positions of the design prototype. Experimental results show that our approach can significantly reduce both the average half-perimeter wirelength and the average global routing wirelength.

7C-3 (Time: 11:10 - 11:35)
TitleA Shape-Driven Spreading Algorithm Using Linear Programming for Global Placement
Author*Shounak Dhar (University of Texas at Austin, U.S.A.), Love Singhal, Mahesh A. Iyer (Intel Corporation, U.S.A.), David Z. Pan (University of Texas at Austin, U.S.A.)
Pagepp. 563 - 568
KeywordPlacement, Legalization, Spreading, Flow
AbstractIn this paper, we consider the problem of finding the global shape for placement of cells in a chip that results in minimum wirelength. Under certain assumptions, we theoretically prove that some shapes are better than others for purposes of minimizing wirelength, while ensuring that overlap-removal is a key constraint of the placer. We derive some conditions for the optimal shape and obtain a shape which is numerically close to the optimum. We also propose a linear-programming-based spreading algorithm with parameters to tune the resultant shape and derive a cost function that is better than total or maximum displacement objectives, that are traditionally used in many numerical global placers. Our new cost function also does not require explicit wirelength computation, and our spreading algorithm preserves to a large extent, the relative order among the cells placed after a numerical placer iteration. Our experimental results demonstrate that our shape-driven spreading algorithm improves wirelength, routing congestion and runtime compared to a bi-partitioning based spreading algorithm used in a state-of-the-art academic global placer for FPGAs.

7C-4 (Time: 11:35 - 12:00)
TitleFinding Placement-Relevant Clusters With Fast Modularity-Based Clustering
Author*Mateus Fogaça (Universidade Federal do Rio Grande do Sul, Brazil), Andrew B. Kahng (University of California, San Diego, U.S.A.), Ricardo Augusto da Luz Reis (Universidade Federal do Rio Grande do Sul, Brazil), Lutong Wang (University of California, San Diego, U.S.A.)
Pagepp. 569 - 576
KeywordPhysical Design, Floorplaning, placement, Clustering, Modularity
AbstractIn advanced technology nodes, IC implementation faces increasing design complexity as well as ever-more demanding design schedule requirements. This raises the need for new decomposition approaches that can help reduce problem complexity, in conjunction with new predictive methodologies that can help avoid bottlenecks and loops in the physical implementation flow. Notably, with modern design methodologies it would be very valuable to better predict final placement of the gate-level netlist: this would enable more accurate early assessment of performance, congestion and floorplan viability in the SOC floorplanning/RTL planning stages of design. In this work, we study a new criterion for the classic challenge of VLSI netlist clustering: how well netlist clusters “stay together” through final implementation. We propose use of several evaluators of this criterion. We also explore the use of modularity-driven clustering to identify natural clusters in a given graph without the tuning of parameters and size balance constraints typically required by VLSI CAD partitioning methods. We find that the netlist hypergraph-to-graph mapping can significantly affect quality of results, and we experimentally identify an effective recipe for weighting that also comprehends topological proximity to I/Os. Further, we empirically demonstrate that modularity-based clustering achieves better correlation to actual netlist placements than traditional VLSI CAD methods (our method is also 4X faster than use of hMetis for our largest testcases). Finally, we show a potential flow with fast “blob placement” of clusters to evaluate netlist and floorplan viability in early design stages; this flow can predict gate-level placement of 370K cells in 200 seconds on a single core.