No Access

INTEGRATED CIRCUIT CHANNEL ROUTING USING A PARETO-OPTIMAL GENETIC ALGORITHM

THEODORE W. MANIKAS

Department of Computer Science and Engineering, Southern Methodist University, POB 750122 Dallas, Texas 75275-0122, USA

https://doi.org/10.1142/S0218126612500417Cited by:0 (Source: Crossref)

Abstract

An important part of the integrated circuit design process is the channel routing stage, which determines how to interconnect components that are arranged in sets of rows. The channel routing problem has been shown to be NP-complete, thus this problem is often solved using genetic algorithms. The traditional objective for most channel routers is to minimize total area required to complete routing. However, another important objective is to minimize signal propagation delays in the circuit. This paper describes the development of a genetic channel routing algorithm that uses a Pareto-optimal approach to accommodate both objectives. When compared to the traditional channel routing approach, the new channel router produced layouts with decreased signal delay, while still minimizing routing area.

This paper was recommended by Regional Editor Eby Friedman.

Keywords:

References

T. Yoshimura and E. S. Kuh, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. CAD 1, 25 (1982), DOI: 10.1109/TCAD.1982.1269993. Crossref, Google Scholar
T. T. Ho, S. S. Iyengar and S. Q. Zheng, IEEE Trans. Comput.-Aided Design Integr. circuits syst. 10, 204 (1991), DOI: 10.1109/43.68407. Crossref, Web of Science, Google Scholar
T. G. Szymanski, IEEE Trans. Computer-Aided Des. of Integr. Circuits Syst. 4, 31 (1985), DOI: 10.1109/TCAD.1985.1270096. Crossref, Web of Science, Google Scholar
N. Gockelet al., A hybrid genetic algorithm for the channel routing problem, IEEE Int. Symp. Circuits and Systems (ISCAS ‘96)4 (1996) pp. 675–678. Google Scholar
R. K. Pal, D. Saha and S. S. Sarma, J. Phys. Sci. 11, 199 (2007). Web of Science, Google Scholar
B. B. Prahlada-Rao, L. M. Patnaik and R. C. Hansdah, A genetic algorithm for channel routing using inter-cluster mutation, IEEE World Congress on Computational Intelligence1 (1994) pp. 97–103. Google Scholar
A. Ruiz-Andino and J. J. Ruz, Integration of constraint programming and evolution programs: application to channel routing, Proc. 11th Int. Conf. Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE '98) (1998) pp. 448–459. Google Scholar
S. Salcedo-Sanz, Y. Xu and X. Yao, Genet. Program. Evolv. Mach. 6, 359 (2005), DOI: 10.1007/s10710-005-3295-z. Crossref, Google Scholar
S. Singha, T. Bhattacharya and S. R. B. Chaudhuri, An approach for reducing crosstalk in restricted channel routing using graph coloring problem and genetic algorithm, Proc. 2008 Int. Conf. on Computer and Electrical Engineering (ICCEE '08) (2008) pp. 807–811. Google Scholar
L. Wang, L. Zhou and W. Liu, FPGA Segmented Channel Routing Using Genetic Algorithms, Proc. IEEE Congr. Evol. Comp. (CEC) (2005) pp. 2161–2165. Google Scholar
J. P. Uyemura , Introduction to VLSI Circuits and Systems ( Wiley , 2001 ) . Google Scholar
H. Eskandari and C. Geiger, J. Heuristics 14, 203 (2008), DOI: 10.1007/s10732-007-9037-z. Crossref, Web of Science, Google Scholar
R. C. Purshouse and P. J. Fleming, IEEE Trans. Evol. Comput. 11, 770 (2007), DOI: 10.1109/TEVC.2007.910138. Crossref, Web of Science, Google Scholar
E. Zitzler and L. Thiele, IEEE Trans. Evol. Comput. 3, 257 (1999), DOI: 10.1109/4235.797969. Crossref, Web of Science, Google Scholar
R. Dewriet al., Optimal security hardening using multi-objective optimization on attack tree models of networks, Proc. 14th ACM Conf. Computer and Communications Security (2007) pp. 204–213. Google Scholar
D. E. Goldberg and K. Deb , Foundations of Genetic Algorithms , ed. G. Rawlins ( Morgan Kaufmann , 1991 ) . Google Scholar