Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4626906 | Applied Mathematics and Computation | 2015 | 13 Pages |
Abstract
Routing is a very important step in VLSI physical design. A set of nets are routed under delay and resource constraints in multi-net global routing. In this paper a delay-driven congestion-aware global routing algorithm is developed, which is a heuristic based method to solve a multi-objective NP-hard optimization problem. The proposed delay-driven Steiner tree construction method is of O(n2logn) complexity, where n is the number of terminal points and it provides n-approximation solution of the critical time minimization problem for a certain class of grid graphs. The existing timing-driven method (Hu and Sapatnekar, 2002) has a complexity O(n4) and is implemented on nets with small number of sinks. Next we propose a FPTAS Gradient algorithm for minimizing the total overflow. This is a concurrent approach considering all the nets simultaneously contrary to the existing approaches of sequential rip-up and reroute. The algorithms are implemented on ISPD98 derived benchmarks and the drastic reduction of overflow is observed.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Radhamanjari Samanta, Adil I. Erzin, Soumyendu Raha, Yuriy V. Shamardin, Ivan I. Takhonov, Vyacheslav V. Zalyubovskiy,