IJBTT

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

	International Journal of Computer Trends and Technology (IJCTT)
	© 2016 by IJCTT Journal
	Volume-38 Number-2
	Year of Publication : 2016
	Authors : Swagata Saha Sau, Rajat Kumar Pal
	DOI :  10.14445/22312803/IJCTT-V38P120

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) V38(2):110-118, August 2016. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.

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.

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.

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