A PSO-based timing-driven Octilinear Steiner tree algorithm forVLSI routing considering bend reduction
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605470480 | ||
| 003 | CHVBK | ||
| 005 | 20210128100328.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150501xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s00500-014-1329-2 |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s00500-014-1329-2 | ||
| 245 | 0 | 2 | |a A PSO-based timing-driven Octilinear Steiner tree algorithm forVLSI routing considering bend reduction |h [Elektronische Daten] |c [Genggeng Liu, Wenzhong Guo, Yuzhen Niu, Guolong Chen, Xing Huang] |
| 520 | 3 | |a 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. | |
| 540 | |a Springer-Verlag Berlin Heidelberg, 2014 | ||
| 690 | 7 | |a Very large scale integration (VLSI) |2 nationallicence | |
| 690 | 7 | |a Performance-driven routing |2 nationallicence | |
| 690 | 7 | |a Octilinear Steiner tree (OST) |2 nationallicence | |
| 690 | 7 | |a Particle swarm optimization (PSO) |2 nationallicence | |
| 690 | 7 | |a Timing delay |2 nationallicence | |
| 690 | 7 | |a Number of bends |2 nationallicence | |
| 700 | 1 | |a Liu |D Genggeng |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | |
| 700 | 1 | |a Guo |D Wenzhong |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | |
| 700 | 1 | |a Niu |D Yuzhen |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | |
| 700 | 1 | |a Chen |D Guolong |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | |
| 700 | 1 | |a Huang |D Xing |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | |
| 773 | 0 | |t Soft Computing |d Springer Berlin Heidelberg |g 19/5(2015-05-01), 1153-1169 |x 1432-7643 |q 19:5<1153 |1 2015 |2 19 |o 500 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00500-014-1329-2 |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s00500-014-1329-2 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Liu |D Genggeng |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Guo |D Wenzhong |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Niu |D Yuzhen |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Chen |D Guolong |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Huang |D Xing |u College of Mathematics and Computer Science, Fuzhou University, 350116, Fuzhou, China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Soft Computing |d Springer Berlin Heidelberg |g 19/5(2015-05-01), 1153-1169 |x 1432-7643 |q 19:5<1153 |1 2015 |2 19 |o 500 | ||