International Journal of Computer
Trends and Technology

Research Article | Open Access | Download PDF

Volume 38 | Number 1 | Year 2016 | Article Id. IJCTT-V38P120 | DOI : https://doi.org/10.14445/22312803/IJCTT-V38P120

A Re-router for Reducing Wire Length in Multi- Layer No-Dogleg Channel Routing

Swagata Saha Sau, Rajat Kumar Pal

Citation :

Swagata Saha Sau, Rajat Kumar Pal, "A Re-router for Reducing Wire Length in Multi- Layer No-Dogleg Channel Routing," International Journal of Computer Trends and Technology (IJCTT), vol. 38, no. 1, pp. 110-118, 2016. Crossref, https://doi.org/10.14445/22312803/ IJCTT-V38P120

Abstract

The minimization of total wire length is one of the most key issue in VLSI physical design automation, as it reduces the cost of physical wiring required along with the electrical hazards of having long wires in the interconnection, power consumption, and signal propagation delay. So, it is still important as cost as well as high performance issue. The problem of reduced wire length routing solutions in no-dogleg reserved two-layer (VH) and multi-layer (ViHi, 2 ? i < dmax and ViHi+1, 2 ? i < dmax ? 1) channel routing is NP-hard, so, it is interesting to develop heuristic algorithms that compute routing solutions of as minimum total (vertical) wire length as possible. Here we propose two algorithms to reduce the total (vertical) wire length in channel routing problem. First we develop an efficient re-router Further_Reduced_Wire_Length (FRWL) to optimize the wire length in the reserved two-layer (VH) no-dogleg channel routing model and then we develop an algorithm Multi-Layer_Reduced_Wire_Length (MLRWL) to minimize the total (vertical) wire length in channel routing problem in the reserved multi-layer (ViHi, 2 ? i < dmax and ViHi+1, 2 ? i < dmax ? 1) no-dogleg Manhattan routing models, where vertical and horizontal layers of interconnect alternate. Experimental results computed for available benchmark instances indicate that the algorithms perform well.

Keywords

Channel routing problem, Manhattan routing, No-dogleg, Parametric difference, Wire length minimization, VLSI.

References

[1] C. J. Alpert, D. P. Mehta, S. S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, CRC Press, London, New York, 2009.
[2] S.-C. Fang, W.-S. Feng, S.-L. Lee, A new Efficient Approach to Multilayer Channel Routing Problem, Proc. of 29th ACM/IEEE Design Automation Conference, pp. 579-584, 1992.
[3] M. D. Formann Wagner, F. Wagner, Routing Through a Dense Channel with Minimum Total Wire Length, Proc. of Second Annual ACM-SIAM Symposium, pp. 475-482, 1991.
[4] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
[5] A. Hashimoto, J. Stevens, Wire Routing by Optimizing Channel Assignment within Large Apertures, Proc. of Eighth ACM Design Automation Workshop, pp. 155-169, 1971.
[6] C. Hong, Y. Kim, The Efficient Hybrid Approach to Channel Routing Problem, Intl. Journal of Advanced Science and Technology, vol. 42, pp. 61-68, 2012.
[7] J. Lienig, Introduction to Electromigration-aware Physical Design (Invited talk), Proc. of ISPD’06, pp. 39-46, 2006.
[8] P. Mitra, N. Ghoshal, R. K. Pal, A Graph Theoretic Approach to Minimize Total Wire Length in Channel Routing, Proc. of 18th IEEE Region 10 Intl. Conference on Convergent Technologies for the Asia-Pacific (IEEE TENCON 2003), vol. 1, pp. 414-418, 2003.
[9] R. K. Pal, Multi-Layer Channel Routing: Complexity and Algorithms, Narosa Publishing House, New Delhi (Also published from CRC Press, Boca Raton, USA and Alpha Science International Ltd., UK), 2000.
[10] R. K. Pal, A. K. Datta, S. P. Pal, M. M. Das, A. Pal, A General Graph Theoretic Framework for Multi-Layer Channel Routing, Proc. of Eighth VSI/IEEE Intl. Conference on VLSI Design, New Delhi, India, pp. 202-207, 1995.
[11] S. Saha Sau, R. Pal, An Efficient High Performance Parallel Algorithm to Yield Reduced Wire Length VLSI Circuits, Proc. of Fifth Intl. Conference on Computers and Devices for Communication (CODEC 2012), 2012.
[12] S. Saha Sau, A. Pal, T. N. Mandal, A. K. Datta, R. K. Pal, A. Chaudhuri, A Graph based Algorithm to Minimize Total Wire Length in VLSI Channel Routing, Proc. of 2011 IEEE Intl. Conference on Computer Science and Automation Engineering (CSAE), vol. 3, pp. 61-65, 2011.
[13] K. A. Somogyi, A. Recski, On the Complexity of the Channel Routing Problem in the Dogleg-free Multi-layer Manhattan Model, ACTA Polytechnica Hungarica, vol. 1, no. 2, 2004.
[14] T. Yoshimura, E. S. Kuh, Efficient Algorithms for Channel Routing, IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 1, pp. 25-35, 1982.