nach oben

Soft Computing

Erschienen in:

22.06.2019 | Methodologies and Application

A unified algorithm based on HTS and self-adapting PSO for the construction of octagonal and rectilinear SMT

verfasst von: Genggeng Liu, Zhisheng Chen, Zhen Zhuang, Wenzhong Guo, Guolong Chen

Erschienen in: Soft Computing | Ausgabe 6/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Steiner minimal tree (SMT) problem is an NP-hard problem, which is the best connection model for a multi-terminal net in global routing problem. This paper presents a unified algorithm for octagonal and rectilinear SMT construction based on hybrid transformation strategy (HTS) and self-adapting particle swarm optimization. Firstly, an effective HTS is proposed to enlarge the search space and improve the convergence speed. Secondly, the proposed HTS in the evolutionary process may produce an ineffective solution, and consequently the crossover and mutation operators of genetic algorithm (GA) based on union-find sets is proposed. Thirdly, a self-adapting strategy that can adjust the acceleration coefficients is proposed to further improve the convergence and the quality of the proposed algorithm. Finally, the hybrid transformation can be applied to GA and the proposed algorithm can be applied to rectilinear architecture. To our best knowledge, the proposed algorithm is the first unified algorithm to solve the SMT construction under both octagonal and rectilinear architecture. The experimental results show that the proposed algorithm can efficiently provide a better solution for SMT problem both in octagonal and rectilinear architectures than others. Moreover, the algorithm can obtain several topologies of SMT, which is beneficial for optimizing congestion in VLSI global routing stage.

Vorheriger Artikel A note on “Picture 2-tuple linguistic aggregation operators in multiple attribute decision making”

Nächster Artikel Fuzzy minimum spanning tree with interval type 2 fuzzy arc length: formulation and a new genetic algorithm

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Agrawal S, Silakari S (2014) FRPSO: Fletcher-Reeves based particle swarm optimization for multimodal function optimization. Soft Comput 18(11):2227–2243CrossRef

Alpert CJ (1998) The ISPD98 circuit benchmark suite. In: Proceedings of the 1998 international symposium on Physical design, pp 80–85

Arora T, Mose ME (2009) Ant colony optimization for power efficient routing in manhattan and non-manhattan VLSI architectures. In: Proceedings of the Swarm intelligence symposium, pp 137–144

Bhattacharya P, Khan A, Sarkar, SK (2014) A global routing optimization scheme based on ABC algorithm. In: Proceedings of the 2nd international conference on advanced computing, networking and informatics, pp 189–197CrossRef

Chang YJ, Lee YT, Gao JR, Wu PC, Wang TC (2010) NTHU-Route. 20: a robust global router for modern designs. IEEE Trans Comput Aid Des 29(12):1931–1944CrossRef

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

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

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

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

Dai KR, Liu WH, Li YL (2009) Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing. In: Proceedings of Asia and South Pacific Design Automation Conference, pp 570V575

Dai KR, Liu WH, Li YL (2012) NCTU-GR: Efficient simulated evolution-based rerouting and congestion-relaxed layer assignment on 3-D global routing. IEEE Trans VLSI Syst 20(3):459–472CrossRef

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, pp 39–43

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

Gottlieb J, Julstrom BA, Raidl GR, Rothlauf F (2001) Prufer Numbers: a poor representation of spanning trees for evolutionary search. In: Proceedings of the genetic and evolutionary computation conference, pp 343–350

Guo WZ, Liu GG, Chen GL, Peng SJ (2014) A hybrid multi- objective PSO algorithm with local search strategy for VLSI partitioning. Front Comput Sci 8(2):203–216MathSciNetCrossRef

Han Y, Ancajas DM, Chakraborty K, Roy S (2014) Exploring high-throughput computing paradigm for global routing. IEEE Trans VLSI Syst 22(1):155–167CrossRef

Held S, Muller D, Rotter D, Scheifele R, Traub V, Vygen J (2017) Global routing with timing constraints. IEEE Trans Comput Aid Des 1–17

Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, CambridgeCrossRef

Huang X, Guo W, Liu G, Chen G (2016) FH-OAOS: a fast four-step heuristic for obstacle-avoiding octilinear steiner tree construction. ACM Trans Des Automat Elec 21(3):1–31

Huang X, Guo W, Liu G, Chen G (2017) MLXR: multi- layer obstacle-avoiding X-architecture steiner tree construction for VLSI routing. Sci China Inform Sci 60(1):1–3CrossRef

Khan A, Laha S, Sarkar SK (2013) A novel particle swarm optimization approach for VLSI routing. In: Proceedings of advance computing conference, pp 258–262

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

Kundu S, Roy S, Mukherjee S (2016) SAT based rectilinear steiner tree construction. In: Proceedings of Appl. Theor Comput Commun Tech, pp 623–627

Kundu S, Roy S, Mukherjee S (2017) K-nearest neighbour (KNN) approach using SAT based technique for rectilinear steiner tree construction. In: Proceedings of embedded computer systems design, pp 1–5

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 G, Chen G, Guo W (2012) DPSO based octagonal steiner tree algorithm for VLSI routing. In: Proceedings of the 5th international conference on advanced computational intellligence, pp 383–387

Liu G, Guo W, Li R, Niu Y, Chen G (2015) XGRouter: high-quality global router in X-architecture with particle swarm optimization. Front Comput Sci 9(4):576–594CrossRef

Liu G, Guo W, Niu Y, Chen G, Huang X (2015) A PSO-based timing-driven Octilinear Steiner tree algorithm for VLSI routing considering bend reduction. Soft Comput 19(5):1153–1169MATHCrossRef

Liu G, Huang X, Guo W, Niu Y, Chen G (2015) Multilayer obstacle-avoiding X-architecture steiner minimal tree construction based on particle swarm optimization. IEEE Trans Cybern 45(5):989–1002

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–640CrossRef

Liu W, Kao W, Li Y, Chao K (2013) NCTU-GR 2.0: multithreaded collision-aware global routing with bounded-length maze routing. IEEE Trans Comput Aid Des 32(5):709–722CrossRef

Lv H, Zheng J, Zhou C, Zhou, C, Li K (2009) The convergence analysis of genetic algorithm based on space mating. In: Proceeding of the 5th international conference on natural computation, pp 557–562

Ma J, Yang B, Ma SH (2000) A near-optimal approximation algorithm for Manhattan Steiner Tree. J Soft 11(2):260–264 (in Chinese)

Manna S, Chakrabarti T, Sharma U, Sarkar SK (2015) Efficient VLSI routing optimization employing discrete differential evolution technique. In: Proceedings of Recent Trends in Information Systems, pp 461–464

Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Caltech Concurr Comput Progr C3P Rep 826: 1989

Numaoka C (1996) Bacterial evolution algorithm for rapid adaptation. In: Proceedings of European workshop on modelling autonomous agents in a multi-agent world, pp 139–148

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–1030CrossRef

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–255CrossRef

Rudolph G (1994) Convergence analysis of canonical genetic algorithms. IEEE Trans Neural Network 5(1):96–101MathSciNetCrossRef

Ruiz-Cruz R, Sanchez EN, Ornelas-Tellez F, Loukianov AG, Harley RG (2013) Particle swarm optimization for discrete-time inverse optimal control of a doubly fed induction generator. IEEE Trans Cybern 43(6):1698–1709CrossRef

Samanta T, Ghosal P, Rahaman H, Dasgupta PS (2006) A heuristic methiod for constructing hexagonal steiner minimal trees for routing in VLSI. In: 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 Digit Tec 5(1):36–48CrossRef

Scheifele R (2016) RC-aware global routing. In: IEEE/ACM international conference on computer-aided design, pp 1–8

Scheifele R (2017) Steiner trees with bounded RC-delay. Alogithmica 78(1):86–109MathSciNetMATHCrossRef

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

Siddiqi UF, Sait SM (2017) A game theory based post-processing method to enhance VLSI global routers. IEEE Access 5:1328–1339CrossRef

Thurber A, Xue G (1999) Computing hexagonal steiner trees using PCx for VLS. In: Proceedings of the 6th IEEE international conference on electronic, circuits, and system, pp 381–384

Wang D, Tan D, Liu L (2017) Particle swarm optimization algorithm: an overview. Soft Comput 1–22

Xu N, Hong XL (2009) Very large scale integration physical design theory and method. Tsinghua University Press, Tsinghua (in Chinese)

Xu X, Rong H, Trovati M, Liptrott M, Bessis N (2016) CS-PSO: chaotic particle swarm optimization algorithm for solving combinatorial optimization problems. Soft Comput 1–13

Xue B, Zhang MJ, Browne MN (2013) Particle swarm optimization for feature selection in classification: a multi-objective approach. IEEE Trans Cybern 43(6):1656–1671CrossRef

Yan JT (2008) Timing-driven octilinear steiner tree construction based on steiner-point reassignment and path reconstruction. ACM Trans Des Automat El 13(2):26MathSciNet

Zachariasen M (2003) GeoSteiner Homepage. Available: http://www.diku.dk/geosteiner

Zhu Q, Zhou H, Jing T, Hong XL, Yang Y (2005) Spanning graph-based nonrectilinear Steiner tree allgorithms. IEEE Trans Comput Aid Des 24(7):1066–1075CrossRef

Titel: A unified algorithm based on HTS and self-adapting PSO for the construction of octagonal and rectilinear SMT
verfasst von: Genggeng Liu
Zhisheng Chen
Zhen Zhuang
Wenzhong Guo
Guolong Chen
Publikationsdatum: 22.06.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 6/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-019-04165-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2020

MCDM based on new membership and non-membership accuracy functions on trapezoidal-valued intuitionistic fuzzy numbers

A holistic optimization approach for inverted cart-pendulum control tuning

A locally based feature descriptor for abnormalities detection

Hopf bifurcation of forced Chen system and its stability via adaptive control with arbitrary parameters

Solution of a fuzzy global optimization problem by fixed point methodology using a weak coupled contraction

Feature selection by recursive binary gravitational search algorithm optimization for cancer classification