The week's pick
Reseach Article
VLSI Routing in Multiple Layers using Grid based Routing Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 93 - Number 16 |
| Year of Publication: 2014 |
| Authors: Sonali Sen |
10.5120/16303-6210
|
Sonali Sen . VLSI Routing in Multiple Layers using Grid based Routing Algorithms. International Journal of Computer Applications. 93, 16 ( May 2014), 41-45. DOI=10.5120/16303-6210
Abstract
Aim of this paper is to describe a multi-layer grid routing algorithm which gives a better result over the existing algorithms. Given a multilayer grid routing area, considered the global routing problem of selecting a maximum set of nets, such that every net can be routed entirely in one of the given layers without violating the physical capacity constraints. The contribution of this paper is of threefold. First, we formulate the problem as an integer linear program (ILP). Second, we write an algorithm which proposed identical routing layers for each net using global routing . Our algorithm gives results which are guaranteed to be within a certain range of the global optimal solution and runs in polynomial-time. Finally we demonstrate that the complexity of our algorithm can be significantly reduced in the worst case prediction.
References
- Naveed Sherwani ,"Algorithms for VLSI Physical Design Automation" ,Third Edition.
- David Szeszler, "Combinatorial Algorithms in VLSI Routing" PhD Dissertation, 2005.
- Ion I. Mandoiu ,"Application Algorithms for VLSI Routing" , Georgia Institute of Technology, August 2000.
- Mohamed Saad, Anthony Vanelli and Hu Zhang, "A Global Routing Algorithm in Multilayer IC" , Lehigh University, Report-08T-004 June 5,2008.
- J. Cong, M. Hossain and N. A. Sherwani, "A Multilayer Topological Planar Routing Algorithm in IC Layout Designs" , IEEE Transactions on Computer Aided Design of IC and Systems,Vol-12,no. 1,pp. 70-78, Jan -1993.
- J. Cong, C. C. Chang, "An Efficient Approach to Multilayer Assignment with an Application", IEEE Transactions on Computer Aided Design of IC and Systems, Vol-18, no. 5,pp. 608-620, Jan -1999.
Index Terms
Keywords