Crosstalk-Aware Global Routing in VLSI Design by Using a Shuffled Frog-Leaping Algorithm


  • Apichat Terapasirdsin Technology of Information System Management Division, Faculty of Engineering, Mahidol University, Nakhon Pathom, 73170, Thailand
  • Supaporn Kiattisin Technology of Information System Management Division, Faculty of Engineering, Mahidol University, Nakhon Pathom, 73170, Thailand



Optimization, crosstalk, shuffled frog leaping, signal coupling


Nowadays, very large scale integrated (VLSI) circuit technology is developing rapidly. It is necessary to consider many factors related to the VLSI circuit design. Interference is one of the factors that must be considered in high-frequency systems. The parasitic elements become serious limiting factors in the circuit. This research provided a method to reduce crosstalk energy by considering the transition of the signal. Crosstalk is the main capacitive effect which is elected by a high-coupling capacitance between lines. This study considers the wiring path signal with disturbance using the theory of optimization model, assisting in the search of the best sort in signal lines. The technique of a shuffled frog leaping algorithm (SFLA) is being used to search for the best value in arranged signal lines. The result will be minimal noise. The study finds that the arrangement using the SFLA causes only 36.42% of the noise. It was initially evident and 13.06%, when compared with the average all, is born noise value. These techniques can be applied in the design of arranging signal line in the VLSI circuits.


Download data is not yet available.

Author Biographies

Apichat Terapasirdsin, Technology of Information System Management Division, Faculty of Engineering, Mahidol University, Nakhon Pathom, 73170, Thailand

Apichat Terapasirdsin received his B.S. degree in electronics engineering (second class honors) in 1997 and the M.Eng. degree in computer engineering in 2000, both from the King Mongkut’s University of Technology Thonburi (KMUTT), Bangkok, Thailand. He was an affiliated student at the Department of Computer Science, the State University of New York at Binghamton (SUNY), USA, in 2008. He is currently a Ph.D. student in IT Management, Faculty of Engineering, Mahidol University, Thailand. His areas of research interest are optimization of VLSI design and computer architecture.

Supaporn Kiattisin, Technology of Information System Management Division, Faculty of Engineering, Mahidol University, Nakhon Pathom, 73170, Thailand

Supaporn Kiattisin received her B.Eng. degree in applied computer engineering from the Chiang Mai University, Chiang Mai, Thailand, in 1995, and the M.Eng. degree in electrical engineering and the Ph.D. degree in electrical and computer engineering from the King Mongkut’s University of Technology Thonburi, Bangkok, Thailand, in 1998 and 2006, respectively. She is currently the program director of Information Technology Management, Faculty of Engineering, Mahidol University, Thailand. Her research interests include computer vision, image processing, robot vision, signal processing, pattern recognition, artificial intelligence, IoT, IT management, digital technologies, big data, and enterprise architecture with TOGAF 9 certification. She is a member of the IEICE and TESA. She served as the Head of IEEE Thailand Chapter in Biomedical Engineering. She also served as the Chairman of the TimesSOC Transaction Thailand. She has expertise in enterprise architecture (EA), data sciences, information technology in E-government, and digital economy (DE).


R. K. Pal, ‘Multi-layer channel routing complexity and algorithms’ Boca Raton: CRC Press, 2000.

W. Wolf, ‘Logic gates: logic, circuits’, In Modern VLSI design: system-on-chip design, Upper Saddle River, NJ: Prentice Hall, pp. 169-172, 2002.

S. Saini and S. B. Mandalika, ‘A new bus coding technique to minimize crosstalk in VLSI bus’, In The 2011 3rd international conference on electronics computer technology, 2011.

E. Afzalan, M. A. Taghikhani and M. Sedighizadeh, ‘Optimal placement and sizing of DG in radial distribution networks using SFLA’, International Journal of Energy Engineering, vol. 2, no. 3, pp.73-77, 2012.

W. Wongthatsanekorn, ‘Reviewing and comparisons of five evolutionary-based algorithms’, The Journal of KMUTNB, vol.19, no.2, pp.285-290, 2009.

A. Terapasirdsin and N. Wattanapongsakorn, ‘Crosstalk aware global router in VLSI design’. In The 6th international joint conference on computer science and software engineering (JCSSE 2009), 2009.

M. Lampropoulos, B. M. Al-Hashimi and P. Rosinger, ‘Minimization of crosstalk noise, delay and power using a modified bus invert technique’, In The proceedings design, automation and test in Europe conference and exhibition, 2004.

K. N. Patel and I. L. Markov, ‘Error-correction and crosstalk avoidance in DSM busses’, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol.12, no.10, pp.1076-1080, 2004.

A. Terapasirdsin and N. Wattanapongsakorn, ‘Row-based design for wiring length and crosstalk minimization in ULSI chip’, In The 2nd international conference on electrical engineering/electronics, computer, telecommunications and information technology (ECTI-CON 2005), 2005.

H. Schmit and V. Chandra, ‘FPGA switch block layout and evaluation’, In The proceedings of the 2002 ACM/SIGDA 10th international symposium on field-programmable gate arrays, 2002.

C. Kuang-Chin and J. Jing-Yang, ‘A code generation algorithm of crosstalk-avoidance code with memory for low-power on-chip bus’, In The 2008 IEEE international symposium on VLSI design, automation and test (VLSI-DAT), 2008.

A. B. Kahng, S. Muddu, E. Sarto and R. Sharma, ‘Interconnect tuning strategies for high-performance ICs’, In The proceedings design, automation and test in Europe, 1998.

S. J. E. Wilton, ‘A crosstalk-aware timing-driven router for FPGAs’, In The proceedings of the 2001 ACM/SIGDA ninth international symposium on field programmable gate arrays, 2001.

Z. Junmou and E. G. Friedman, ‘Crosstalk noise model for shielded interconnects in VLSI-based circuits’, In The IEEE international [systems-on-chip] SOC conference, 2003.

N. A. Sherwani, ‘Design and fabrication of VLSI devices’, In Algorithms for VLSI physical design automation, New York: Springer US, pp. 39-74, 1999.

J. H. Holland, ‘Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence’, Cambridge, MA: MIT Press, 1992.

D. Chunjie, Z. Chengyu and S. P. Khatri, ‘Forbidden transition free crosstalk avoidance CODEC design’, In The 2008 45th ACM/IEEE design automation conference, 2008.

L. Macchiarulo, E. Macii and M. Poncino, ‘Wire placement for crosstalk energy minimization in address buses’, In The Proceedings 2002 Design, Automation and Test in Europe Conference and Exhibition, 2002.

W. W. Hines, D. C. Montgomery, D. M. Goldsman and C. M. Borror, ‘Finite sample spaces and enumeration: permutations, combinations’, In Probability and statistics in engineering, Hoboken, N.J.: John Wiley & Sons, pp. 15-16, 2003.

P. Merz and B. Freisleben, ‘A Genetic Local Search Approach to the Quadratic Assignment Problem’, In The proceedings of the 7th international conference on genetic algorithms, 1997.

J. Kennedy and R. Eberhart, ‘Particle swarm optimization’, In The proceedings of ICNN'95 - international conference on neural networks, 1995.

M. Dorigo, V. Maniezzo and A. Colorni, ‘Ant system: optimization by a colony of cooperating agents’, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no.1, pp.29-41, 1996.

P. Sotiriadis and A. Chandrakasan, ‘Bus energy minimization by transition pattern coding (TPC) in deep submicron technologies’, In The proceedings of the 2000 IEEE/ACM international conference on computer-aided design, 2000.

M. M. Eusuff and K. E. Lansey, ‘Optimization of water distribution network design using the shuffled frog leaping algorithm’, Journal of Water Resources Planning and Management, vol.129, no.3, pp.210-225, 2003.

J. William Paul Swartz, ‘Automatic layout of analog and digital mixed macro/standard cell integrated circuits’, Yale University, 1993.

D. Jariwala and J. Lillis, ‘On interactions between routing and detailed placement’, In The IEEE/ACM international conference on computer aided design, ICCAD-2004, 2004.






Smart Innovative Technology for Future Industry and Multimedia Applications