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

• Agrawal S, Silakari S (2013) FRPSO: Fletcher–Reeves based particle swarm optimization for multimodal function optimization. Soft Comput 1–17

• Alfred VA, John EH, Jeffrey U (1983) Data structures and algorithms. Addison-Wesley Longman Publishing, Boston

  MATH  Google Scholar 

• 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–144

• 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

  Chapter  Google Scholar 

• Beasley JE (1990) OR-Library: distributing test problems by electronic Mail. J Oper Res Soc 41(11):1069–1072

  Article  Google Scholar 

• 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–187

• Borah M, Owens RM, Irwin MJ (1994) An edge-based heuristic for Steiner routing. IEEE Trans Comput Aided Design 13(12):1563–1568

  Article  Google Scholar 

• Bozorgzadeh E, Kastner R, Sarrafzadeh M (2003) Creating and exploiting flexibility in rectilinear Steiner trees. IEEE Trans Comput Aided Design 22(5):605–615

  Article  Google Scholar 

• Carlos ACC, Gregorio TP, Maximino SL (2004) Handling multiple objectives with particle swarm optimization. IEEE Trans Evol Comput 8(3):256–279

  Article  Google Scholar 

• Chen G, Guo W, Chen Y (2010) A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Comput 14(12):1329–1337

  Article  Google Scholar 

• Chiang C, Chiang CS (2002) Octilinear steiner tree construction. In: Proceedings of the 45th midwest symposium on circuits and systems, pp 603–606

• Chu C, Wong YC (2008) FLUTE: fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design. IEEE Trans Comput Aided Design 27(1):70–83

  Article  Google Scholar 

• Clerc M (2004) Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: Onwubolu GC, Babu BV (eds) New optimization techniques in engineering. Springer, Berlin, pp 219–239

  Chapter  Google Scholar 

• Cong J, Kahng AB, Robins G, Sarrafzadeh M, Wong CK (1992) Provably good performance-driven global routing. IEEE Trans Comput Aided Design 11:739–752

  Article  Google Scholar 

• Conover WJ (1999) Practical nonparametric statistics. Wiley, New York

  Google Scholar 

• Costas V, Konstantinos E, Isaac E (2012) Particle swarm optimization with deliberate loss of information. Soft Comput 16(8):1373–1392

  Article  Google Scholar 

• Coulston G (2003) Constructing exact octagonal steiner minimal trees. In: Proceedings of the 13th ACM Great Lakes symposium on VLSI, pp 1–6

• 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–43

• Garey M, Johnson D (1997) The rectilinear steiner tree problem is NP-complete. SIAM J Appl Math 32:826–834

  Article  MathSciNet  Google Scholar 

• 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–367

• 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(1):53–62

  Article  Google Scholar 

• Julstrom BA (2001) Encoding rectilinear Steiner trees as lists of edges. In: Proceeding of the 2001 ACM symposium on applied computing, New York, pp 356–360

• Ho TY, Chang YW, Chen SJ (2007) Full-chip nanometer routing techniques. Springer, Berlin

  Book  Google Scholar 

• Hou H, Hu J, Sapatnekar SS (1999) Non-hanan routing. IEEE Trans Comput Aided Des 18(4):436–444

  Article  Google Scholar 

• Hu J, Sapatnekar S (2001) A survey on multi-net global routing for integrated circuits. Inter VLSI J 31(1):1–49

  Article  MATH  Google Scholar 

• Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. In: Proceedings of the world multiconference on systemics, cybernetics and informatics, Piscataway, pp 4104–4109

• Koh CK, Madden PH (2000) Manhattan or non-manhattan? a study of alternative VLSI routing architectures. In: Proceedings of Great Lake symposium on VLSI, pp 47–52

• Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10(3):263–282

  Article  Google Scholar 

• Liang J, Hong X, Jing T (2007) G-Tree: gravitation-direction-based rectilinear Steiner minimal tree construction considering bend reduction. Proceedings of the 7th international conference on ASIC. IEEE, Guilin, pp 1114–1117

• Liu G, Chen G, Guo W (2012) DPSO based octagonal steiner tree algorithm for VLSI routing. 2012 IEEE fifth international conference on advanced computational intellligence. IEEE, Nanjing, pp 383–387

• Liu G, Chen G, Guo W, Chen Z (2011) DPSO-based rectilinear steiner minimal tree construction considering bend reduction. In: Proceedings of the 7th international conference on natural computation, pp 1161–1165

• Liu H, Cai Z, Wang Y (2010) Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Appl Soft Comput 10(2):629–640

  Article  Google Scholar 

• Pan QK, Tasgetiren MF, Liang YC (2006) A discrete particle swarm optimization algorithm for the permutation flowshop sequecing problem with makespan criteria. In: Proceedings of the 26th SGAI international conference on innovative techniques and applications of artificial intelligence, Cambridge, pp 19–31

• Peng S, Chen G, Guo W (2010) A multi-objective algorithm based on discrete PSO for VLSI partitioning problem. In: Proceedings of the 2nd international conference on quantitative logic and soft computing, Jimei, pp 651–660

• Rada-Vilela J, Zhang M, Seah W (2013) A performance study on synchronicity and neighborhood size in particle swarm optimization. Soft Comput 17(6):1019–1030

  Article  Google Scholar 

• Ratnaweera A, Halgamuge SK, Watson HC (2004) Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Trans Evol Comput 8(3):240–255

  Article  Google Scholar 

• Samanta T, Ghosal P, Rahaman H, Dasgupta PS (2006) A heuristic methiod for constructing hexagonal steiner minimal trees for routing in VLSI. In: 2006 IEEE international symposium on circuits and systems, pp 1788–1791

• Samanta T, Rahaman H, Dasgupta PS (2011) Near-optimal Y-routed delay trees in nanometric interconnect design. IET Comput Digital Tech 5(1):36–48

  Article  Google Scholar 

• Sarrafzadeh M, Feng LK, Wong CK (1994) Single-layer global routing. IEEE Trans Comput Aided Design 13(1):38–47

  Article  Google Scholar 

• Seo DY, Lee DT (1999) On the complexity of bicriteria spanning tree problems for a set of points in the plane. PhD Dissertation, Northwestern University

• Shen Y, Liu Q, Guo W (2011) Obstacle-avoiding rectilinear steiner minimum tree construction based on discrete particle swarm optimization. In: Proceedings of the 2011 seventh international conference on natural computation, pp 2179–2183

• Shi YH, Eberhart RC (1998) A modified particle swarm optimizer. In: Proceedings of the IEEE international conference of evolutionary computation, Piscataway, pp 69–73

• Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

  Article  Google Scholar 

• Teig S (2002) The X architecture: not your fathers diagonal wiring. In: Proceedings of the ACM international workshop system level interconnect prediction, pp 33–37

• Warme DM, Winter P, Zachariasen M (1998) Exact algorithms for plane steiner tree problems: a computational study., Advances in Steiner TreesKluwer Academic Publishers, Dordrecht

  Google Scholar 

• Yan JT (2006) Dynamic tree reconstruction with application to timing-constrained congestion-driven global routing. IEE Proc Comput Digital Tech 153(2):117–129

  Article  Google Scholar 

• Yan JT (2008) Timing-driven octilinear steiner tree construction based on steiner-point reassignment and path reconstruction. ACM Trans Design Autom Electron Syst 13(2):26

  Article  Google Scholar 

• Yehea II, Eby GF, Jose LN (1999) Equivalent elmore delay for RLC trees. In: Proceedings of the 36th design automation conference, pp 715–720

• Zhu Q, Zhou H, Jing T, Hong X, Yang Y (2005) Spanning graph-based nonrectilinear steiner tree algorithms. IEEE Trans Comput Aided Design 24(7):1066–1075

  Article  Google Scholar 

• Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. Swiss Federal Institute of Technology, Zurich

• Zitzler E, Laumanns M, and Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. In: Giannakoglou KC, Tsahalis DT, Periaux J, Papailiou KD, Fogarty T (eds) Evolutionary methods for design optimization and control with applications to industrial problems. International Center for Numerical Methods in Engineering, pp 95–100

• Zitzler E, Thiele L, Laumanns M et al (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7:117–132

  Article  Google Scholar 

Download references