A PSO-based timing-driven Octilinear Steiner tree algorithm for?VLSI routing considering bend reduction

详细信息    查看全文

• 作者：Genggeng Liu ; Wenzhong Guo ; Yuzhen Niu ; Guolong Chen ; Xing Huang
• 关键词：Very large scale integration (VLSI) ; Performance ; driven routing ; Octilinear Steiner tree (OST) ; Particle swarm optimization (PSO) ; Timing delay ; Number of bends
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：19
• 期：5
• 页码：1153-1169
• 全文大小：724 KB
• 参考文献：1. Agrawal S, Silakari S (2013) FRPSO: Fletcher–Reeves based particle swarm optimization for multimodal function optimization. Soft Comput 1-7
  2. Alfred, VA, John, EH, Jeffrey, U (1983) Data structures and algorithms. Addison-Wesley Longman Publishing, Boston
  3. Arora T, Mose ME (2009) Ant colony optimization for power efficient routing in manhattan and non-manhattan VLSI architectures. In: Swarm intelligence symposium, pp 137-44
  4. Balling, R (2003) The maximin fitness function: multiobjective city and regional planning. Proceedings of the 2nd international conference on evolutionary multi-criterion optimization. Faro, Portugal, pp. 1-15 CrossRef
  5. Beasley, JE (1990) OR-Library: distributing test problems by electronic Mail. J Oper Res Soc 41: pp. 1069-1072 CrossRef
  6. Boese KD, Kahng AB, Robins G (1993) Near optimal critical sink routing tree constructions. In: Proceedings of the ACM/IEEE design automation conference, pp 182-87
  7. Borah, M, Owens, RM, Irwin, MJ (1994) An edge-based heuristic for Steiner routing. IEEE Trans Comput Aided Design 13: pp. 1563-1568 CrossRef
  8. Bozorgzadeh, E, Kastner, R, Sarrafzadeh, M (2003) Creating and exploiting flexibility in rectilinear Steiner trees. IEEE Trans Comput Aided Design 22: pp. 605-615 CrossRef
  9. Carlos, ACC, Gregorio, TP, Maximino, SL (2004) Handling multiple objectives with particle swarm optimization. IEEE Trans Evol Comput 8: pp. 256-279 CrossRef
  10. Chen, G, Guo, W, Chen, Y (2010) A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Comput 14: pp. 1329-1337 CrossRef
  11. Chiang C, Chiang CS (2002) Octilinear steiner tree construction. In: Proceedings of the 45th midwest symposium on circuits and systems, pp 603-06
  12. Chu, C, Wong, YC (2008) FLUTE: fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design. IEEE Trans Comput Aided Design 27: pp. 70-83 CrossRef
  13. Clerc, M Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: Onwubolu, GC, Babu, BV eds. (2004) New optimization techniques in engineering. Springer, Berlin, pp. 219-239 CrossRef
  14. Cong, J, Kahng, AB, Robins, G, Sarrafzadeh, M, Wong, CK (1992) Provably good performance-driven global routing. IEEE Trans Comput Aided Design 11: pp. 739-752 CrossRef
  15. Conover, WJ (1999) Practical nonparametric statistics. Wiley, New York
  16. Costas, V, Konstantinos, E, Isaac, E (2012) Particle swarm optimization with deliberate loss of information. Soft Comput 16: pp. 1373-1392 CrossRef
  17. Coulston G (2003) Constructing exact octagonal steiner minimal trees. In: Proceedings of the 13th ACM Great Lakes symposium on VLSI, pp 1-
  18. Eberhar RC, Kennedy J (1995) A new optimizer using particles swarm theory. In: Proceedings of the 6th international symposium on micro machine and human science, Nagoya, pp 39-3
  19. Garey, M, Johnson, D (1997) The rectilinear steiner tree problem is NP-complete. SIAM J Appl Math 32: pp. 826-834 CrossRef
  20. Guo W, Park JH, Yang LT, Vasilakos AV, Xiong N, Chen G (2011) Design and analysis of a MST-based topology control scheme with PSO for wireless sensor networks. 2011 IEEE Asia-Pacific services computing conference. IEEE, Jeju Island, pp 360-67
  21. Guo, W, Xiong, N, Vasilakos, AV, Chen, G, Yu, C (2012) Distributed k-connected fault-tolerant topology control algorithms with PSO in future autonomic sensor systems. Int J Sens Netw 12: pp. 53-62 CrossRef
  22. Julstrom BA (
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

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.