caa a22 4500 605470480 CHVBK 20210128100328.0 cr unu---uuuuu 210128e20150501xx s 000 0 eng 10.1007/s00500-014-1329-2 doi (NATIONALLICENCE)springer-10.1007/s00500-014-1329-2 A PSO-based timing-driven Octilinear Steiner tree algorithm forVLSI routing considering bend reduction [Elektronische Daten] [Genggeng Liu, Wenzhong Guo, Yuzhen Niu, Guolong Chen, Xing Huang] Constructing a timing-driven Steiner tree is very important in VLSI performance-driven routing stage. Meanwhile, non-Manhattan architecture is supported by several manufacturing technologies and now well appreciated in the chip manufacturing circle. However, limited progress has been reported on the non-Manhattan performance-driven routing problem. In this paper, an efficient algorithm, namely, TOST_BR_MOPSO, is presented to construct the minimum-cost spanning tree with a minimum radius for performance-driven routing in Octilinear architecture (one type of the non-Manhattan architecture) based on multi-objective particle swarm optimization (MOPSO) and Elmore delay model. Edge transformation is employed in our algorithm to make the particles have the ability to achieve the optimal solution while Union-Find partition is used to prevent the generation of invalid solution. For the purpose of reducing the number of bends which is one of the key factors of chip manufacturability, we also present an edge-vertex encoding strategy combined with edge transformation. To our best knowledge, no approach has been proposed to optimize the number of bends in the process of constructing the non-Manhattan timing-driven Steiner tree. Moreover, the theorem of Markov chain is used to prove the global convergence of our proposed algorithm. Experimental results indicate that the proposed MOPSO is worthy of being studied in the field of multi-objective optimization problems, and our algorithm has a better tradeoff between the wire length and radius of the routing tree and has achieved a better delay value. Meanwhile, combining edge transformation with the encoding strategy, the proposed algorithm can significantly reduce nearly 20% in the number of bends. Springer-Verlag Berlin Heidelberg, 2014 Very large scale integration (VLSI) nationallicence Performance-driven routing nationallicence Octilinear Steiner tree (OST) nationallicence Particle swarm optimization (PSO) nationallicence Timing delay nationallicence Number of bends nationallicence Liu Genggeng College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut Guo Wenzhong College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut Niu Yuzhen College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut Chen Guolong College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut Huang Xing College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut Soft Computing Springer Berlin Heidelberg 19/5(2015-05-01), 1153-1169 1432-7643 19:5<1153 2015 19 500 https://doi.org/10.1007/s00500-014-1329-2 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00500-014-1329-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Liu Genggeng College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut NATIONALLICENCE 700 1- Guo Wenzhong College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut NATIONALLICENCE 700 1- Niu Yuzhen College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut NATIONALLICENCE 700 1- Chen Guolong College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut NATIONALLICENCE 700 1- Huang Xing College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China aut NATIONALLICENCE 773 0- Soft Computing Springer Berlin Heidelberg 19/5(2015-05-01), 1153-1169 1432-7643 19:5<1153 2015 19 500