(Back to Session Schedule)

The 21st Asia and South Pacific Design Automation Conference

Session 4C  Routing
Time: 10:20 - 12:00 Wednesday, January 27, 2016
Location: TF4204
Chairs: Iris Hui-Ru Jiang (National Chiao Tung University, Taiwan), Yao-Wen Chang (National Taiwan University, Taiwan)

4C-1 (Time: 10:20 - 10:45)
TitleMCMM Clock Tree Optimization based on Slack Redistribution Using a Reduced Slack Graph
Author*Rickard Ewetz, Cheng-Kok Koh (Purdue University, U.S.A.)
Pagepp. 366 - 371
KeywordCTO, clock, skew
AbstractModern clock networks are required to operate in multiple corners and in multiple modes (MCMM). An initially con- structed clock tree may contain different timing violations in different mode and corner combinations. Clock tree optimiza- tion (CTO) is employed to remove these timing violations. We propose a CTO framework based on slack redistribution us- ing a reduced slack graph. The main idea is to reduce the MCMM problem to an equivalent single-corner single-mode (SCSM) problem using delay adjustment linearization. Using the equivalent SCSM problem, a linear program is solved to determine a set of delay adjustments to remove the timing vi- olations. Next, the delay adjustments are realized using feasi- ble delay adjustment ranges. The experimental results show that the proposed framework obtains average reductions of 84% and 83% in the total negative slack and the worst neg- ative slack, respectively, at the expense of a 4% capacitive overhead.

4C-2 (Time: 10:45 - 11:10)
TitleDynamic Planning of Local Congestion from Varying-Size Vias for Global Routing Layer Assignment
AuthorDaohang Shi, Edward Tashjian, *Azadeh Davoodi (University of Wisconsin-Madison, U.S.A.)
Pagepp. 372 - 377
Keywordglobal routing, layer assignment, local congestion, detailed routing, via modeling
AbstractThis work is the first to present global routing models for capturing the impact of local congestion caused by varying-size vias. The models are then incorporated to dynamically drive a proposed layer assignment algorithm. This is also the first work to actually evaluate the impact of global routing solutions using a commercial detailed router. In our experiments we report fewer number of DRC violations by only changing the layer assignment at global routing, and detailed route using the Olympus-SoC of Mentor Graphics.

4C-3 (Time: 11:10 - 11:35)
TitleNegotiation-Based Track Assignment Considering Local Nets
Author*Man-Pan Wong (National Tsing Hua University, Taiwan), Wen-Hao Liu (Cadence Design Systems Inc., U.S.A.), Ting-Chi Wang (National Tsing Hua University, Taiwan)
Pagepp. 378 - 383
KeywordRoutability, congestion, track assignment
AbstractRoutability has become a very challenging issue in a modern VLSI design flow. Many works use global routing to estimate the routability in early design stages. However, global routing cannot accurately capture local congestion, so it is hard to detect the detailed routability issue. To more accurately estimate the detailed-routing routability, this paper presents a track-assignment-based routability estimator. In this work, wire segments called iroutes are extracted from a global routing result, and then the proposed negotiation-based algorithm assigns these iroutes to proper tracks and minimizes the overlaps between the iroutes. Based on the assignment result, we can judge which regions may have critical routability issues by seeing where more overlaps reside.

4C-4 (Time: 11:35 - 12:00)
TitleOrdered Escape Routing for Grid Pin Array Based on Min-cost Multi-commodity Flow
Author*Fengxian Jiao, Sheqin Dong (Tsinghua University, China)
Pagepp. 384 - 389
KeywordPCB Routing, Ordered Escape Routing, Min-cost Multi-commodity flow
AbstractOrdered Escape routing is a critical issue in high-speed PCB routing. In this paper, for the first time, a Min-cost Multi-commodity Flow (MMCF) approach is proposed to solve the ordered escape routing. The characteristic of grid pin array is analyzed and then a basic network model is used to convert ordered escape routing to MMCF model. To satisfy the constraints of ordered escape routing, three novel transformations, such as non-crossing transformation, ordering transformation and capacity transformation, are used to convert the basic network model to the final correct MMCF model. Experimental results show that our method achieves 100% routability for all the test cases. The method can get both a feasible solution and an optimal solution. Compared to published approaches, our method improves in both wire length and CPU time remarkably.