{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T18:17:02Z","timestamp":1769192222397,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,3,2]],"date-time":"2015-03-02T00:00:00Z","timestamp":1425254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Fujian Province High School Science Fund for Distinguished Young Scholars","award":["JA12016"],"award-info":[{"award-number":["JA12016"]}]},{"name":"Fujian Natural Science Funds for Distinguished Young Scholar","award":["2014J06017"],"award-info":[{"award-number":["2014J06017"]}]},{"name":"Fujian Province Key Laboratory of Network Computing and Intelligent Information Processing Project","award":["2009J1007"],"award-info":[{"award-number":["2009J1007"]}]},{"name":"Program for New Century Excellent Talents in Fujian Province University","award":["JA13021"],"award-info":[{"award-number":["JA13021"]}]},{"DOI":"10.13039\/501100012166","name":"National Basic Research Program of China","doi-asserted-by":"crossref","award":["2011CB808003"],"award-info":[{"award-number":["2011CB808003"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11271002"],"award-info":[{"award-number":["11271002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2015,3,2]]},"abstract":"<jats:p>Obstacle-avoiding Steiner minimal tree (OASMT) construction has become a focus problem in the physical design of modern very large-scale integration (VLSI) chips. In this article, an effective algorithm is presented to construct an OASMT based on X-architecturex for a given set of pins and obstacles. First, a kind of special particle swarm optimization (PSO) algorithm is proposed that successfully combines the classic genetic algorithm (GA), and greatly improves its own search capability. Second, a pretreatment strategy is put forward to deal with obstacles and pins, which can provide a fast information inquiry for the whole algorithm by generating a precomputed lookup table. Third, we present an efficient adjustment method, which enables particles to avoid all the obstacles by introducing some corner points of obstacles. Finally, an excellent refinement method is discussed to further enhance the quality of the final routing tree, which can improve the quality of the solution by 7.93% on average. To our best knowledge, this is the first time to specially solve the single-layer obstacle-avoiding problem in X-architecture. Experimental results show that the proposed algorithm can further shorten wirelength in the presence of obstacles. And it achieves the best solution quality in a reasonable runtime among the existing algorithms.<\/jats:p>","DOI":"10.1145\/2699862","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T14:08:19Z","timestamp":1425391699000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Obstacle-Avoiding Algorithm in X-Architecture Based on Discrete Particle Swarm Optimization for VLSI Design"],"prefix":"10.1145","volume":"20","author":[{"given":"Xing","family":"Huang","sequence":"first","affiliation":[{"name":"Fu Zhou University, Fuzhou, Fujian, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Genggeng","family":"Liu","sequence":"additional","affiliation":[{"name":"Fu Zhou University, Fuzhou, Fujian, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenzhong","family":"Guo","sequence":"additional","affiliation":[{"name":"Fu Zhou University, Fuzhou, Fujian, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuzhen","family":"Niu","sequence":"additional","affiliation":[{"name":"Fu Zhou University, Fuzhou, Fujian, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guolong","family":"Chen","sequence":"additional","affiliation":[{"name":"Fu Zhou University, Fuzhou, Fujian, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,3,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2096571"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/639929.639944"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Midwest Symposium on Circuits and Systems (MWSCAS'02)","author":"Chiang C.","unstructured":"C. Chiang and C. S. Chiang . 2002. Octilinear Steiner tree construction . In Proceedings of the International Midwest Symposium on Circuits and Systems (MWSCAS'02) . IEEE, 1--6. C. Chiang and C. S. Chiang. 2002. Octilinear Steiner tree construction. In Proceedings of the International Midwest Symposium on Circuits and Systems (MWSCAS'02). IEEE, 1--6."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2013.08.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382665"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_2_1_7_1","volume-title":"New Optimization Techniques in Engineering","author":"Clerc M.","unstructured":"M. Clerc . 2004. Discrete particle swarm optimization, illustrated by the traveling salesman problem . In New Optimization Techniques in Engineering , Springer , 219--239. M. Clerc. 2004. Discrete particle swarm optimization, illustrated by the traveling salesman problem. In New Optimization Techniques in Engineering, Springer, 219--239."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/764808.764810"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 6th International Symposium on Micro Machine and Human Science (MHS'95)","author":"Eberhart R.","unstructured":"R. Eberhart and J. Kennedy . 1995. A new optimizer using particle swarm theory . In Proceedings of the 6th International Symposium on Micro Machine and Human Science (MHS'95) . 39--43. R. Eberhart and J. Kennedy. 1995. A new optimizer using particle swarm theory. In Proceedings of the 6th International Symposium on Micro Machine and Human Science (MHS'95). 39--43."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/238997.239033"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/74382.74410"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2238291"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024724.2024762"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Computer Aided Design (ICCAD'10)","author":"Huang T.","unstructured":"T. Huang and E. F. Young . 2010. Obstacle-avoiding rectilinear Steiner minimum tree construction: An optimal approach . In Proceedings of the International Conference on Computer Aided Design (ICCAD'10) . IEEE, 610--613. T. Huang and E. F. Young. 2010. Obstacle-avoiding rectilinear Steiner minimum tree construction: An optimal approach. In Proceedings of the International Conference on Computer Aided Design (ICCAD'10). IEEE, 610--613."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.896291"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1119772.1119955"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/330855.330961"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687405"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.917583"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2012.2185050"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529255.1529267"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2006098"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2004.826071"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCD.2005.45"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 7th Annual Conference on Evolutionary Programming (EP'98)","author":"Shi Y.","unstructured":"Y. Shi and R. Eberhart . 1998. Parameter selection in particle swarm optimization . In Proceedings of the 7th Annual Conference on Evolutionary Programming (EP'98) . 591--600. Y. Shi and R. Eberhart. 1998. Parameter selection in particle swarm optimization. In Proceedings of the 7th Annual Conference on Evolutionary Programming (EP'98). 591--600."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Congress on Evolutionary Computation (CEC'99)","author":"Shi Y.","unstructured":"Y. Shi and R. Eberhart . 1999. Empirical study of particle swarm optimization . In Proceedings of the Congress on Evolutionary Computation (CEC'99) . Y. Shi and R. Eberhart. 1999. Empirical study of particle swarm optimization. In Proceedings of the Congress on Evolutionary Computation (CEC'99)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/505348.505355"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344418.1344422"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.850862"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699862","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699862","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:59Z","timestamp":1750227419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699862"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,2]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3,2]]}},"alternative-id":["10.1145\/2699862"],"URL":"https:\/\/doi.org\/10.1145\/2699862","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,2]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}