Article(id=1327018689104294476, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327018536993665336, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202440069, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1706976000000, receivedDateStr=2024-02-04, revisedDate=1738857600000, revisedDateStr=2025-02-07, acceptedDate=1740931200000, acceptedDateStr=2025-03-03, onlineDate=1794315510297, onlineDateStr=2026-11-10, pubDate=1753977600000, pubDateStr=2025-08-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794315510297, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794315510297, creator=13701087609, updateTime=1794315510297, updator=13701087609, issue=Issue{id=1327018536993665336, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='8', pageStart='1833', pageEnd='2124', issueExtLink='null', onlineDate='null', pubDate='1753977600000', pubDateStr='2025-08-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794315474031, creator='13701087609', updateTime=1794376881014, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327276097470837643, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327018536993665336, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327276097470837644, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327018536993665336, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=1948, endPage=1961, ext={EN=ArticleExt(id=1327018689318203981, articleId=1327018689104294476, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards, columnId=1325489901852041729, journalTitle=Journal of Computer Research and Development, columnName=Computer Architecture, runingTitle=null, highlight=null, articleAbstract=

Routing is considered as an essential component in the design of printed circuit board (PCB). Current existing PCB designs mostly rely on the process results from electronic design automation tools, and traditional automatic routing research often focuses on the only general bus routing without considering bus groups to be determined during the routing process. Due to the absence of general bus grouping, there may be situations where there are more nets in one group than in the other groups, resulting in larger line width and line clearance occupied by this group when compared with other bus groups in the original bus routing, thereby posing new challenges to effective and efficient routing. To overcome this drawback, we focus on studying PCB group routing. In this study, a group routing algorithm based on a weighted directed graph is proposed. A Hanan grid graph is constructed, containing the only merged edges and their adjacent relationships. Following this, a weighted directed graph is developed using the merged edge information to represent the routing resources on the circuit board. For routing planning, a heuristic search algorithm equipped with multi-wire avoidance features is utilized. The routing situations are then classified into several potential scenarios, with each considered separately, to accomplish detailed routing and obtain a final result of group routing. Results from experiments demonstrate that 100% routability is consistently achieved by using the algorithm on complex industrial examples that have been previously tested, and that the design rule constraints of all benchmark industrial PCB cases are not violated.

, authors=Xinguo Deng1, Xinhong Zhang1, Jiarui Chen1, *, Qinghai Liu2, 3, Chuandong Chen4, authorsList=Xinguo Deng, Xinhong Zhang, Jiarui Chen, Qinghai Liu, Chuandong Chen, authorCompany=null, correspAuthors=Jiarui Chen, authorNote=

born in 1975. PhD, associate professor. His main research interest includes electronic design automation

born in 1998. Master. His main research interest includes electronic design automation

born in 1981. PhD, associate professor. His main research interest includes electronic design automation

born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

born in 1982. PhD, associate professor. His main research interest includes electronic design automation

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327018694267482738, articleId=1327018689104294476, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=一种基于带权有向图的印刷电路板群组布线算法, columnId=1325489904427344387, journalTitle=计算机研究与发展, columnName=体系结构, runingTitle=null, highlight=null, articleAbstract=

布线是印刷电路板设计中的重要一环. 现有的印刷电路板设计多依赖于电子设计自动化工具的处理,而传统的自动布线研究多聚焦于总线布线,没有将布线时确定的群组作为研究对象. 由于未经总线分组,可能存在群组中线网较多的情况,这将导致群组所占据的线宽与线间距比原先总线布线中各总线组分别占据的线宽与线间距更大,从而给实际布线带来了新的挑战. 为此,提出一种基于带权有向图的群组布线算法. 首先构建仅含有合并边以及它们之间邻接关系的Hanan网格图. 接着,利用合并边信息构建带权有向图,完成对电路板上布线资源的表示. 然后,使用一种具有多线避让功能的启发式搜索算法来进行布线规划. 最后,通过将布线归类为数种可能的情况分别考虑,完成详细布线并得到群组布线的最终结果. 实验结果表明,所提算法在已经测试过的工业界复杂例子上均能达到100%的布通率,并且不会违反所有工业印刷电路板基准用例的设计规则约束.

, authors=邓新国1, 张鑫泓1, 陈家瑞1, *, 刘清海2, 3, 陈传东4, authorsList=邓新国, 张鑫泓, 陈家瑞, 刘清海, 陈传东, authorCompany=null, correspAuthors=陈家瑞, authorNote=

1975年生. 博士,副教授. 主要研究方向为电子设计自动化

1998年生. 硕士. 主要研究方向为电子设计自动化

1981年生. 博士,副教授. 主要研究方向为电子设计自动化

1982年生. 博士,教授. CCF会员,主要研究方向为图论及应用、组合优化、电子设计自动化

1982年生. 博士,副教授. 主要研究方向为电子设计自动化

, correspAuthorsNote=
陈家瑞()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=oty8933zmLVFsZtF9zotkA==, magXml=ohayZV1N/993WtV9sUWCbA==, pdfUrl=null, pdf=JxYnIsSNiXuR4qKMJrRnQA==, pdfFileSize=1785792, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=JTruqVRMYHBayw1PenE+vQ==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=/V417v1LrUtVoDfqdLVbtQ==, mapNumber=null, fund=null)}, authors=[Author(id=1327018694850491008, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=xgdeng@fzu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018694930182786, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018694850491008, language=EN, stringName=Xinguo Deng, firstName=Xinguo, middleName=null, lastName=Deng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1975. PhD, associate professor. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1975. PhD, associate professor. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018696599515780, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018694850491008, language=CN, stringName=邓新国, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1福州大学计算机与大数据学院 福州 350108, bio={"img":"97sVJ+FD4BAmM73tuiQ6lQ==","content":"

1975年生. 博士,副教授. 主要研究方向为电子设计自动化

"}, bioImg=97sVJ+FD4BAmM73tuiQ6lQ==, bioContent=

1975年生. 博士,副教授. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)])]), Author(id=1327018696679207558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018696750510728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696679207558, language=EN, stringName=Xinhong Zhang, firstName=Xinhong, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1998. Master. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1998. Master. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018696821813897, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696679207558, language=CN, stringName=张鑫泓, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1福州大学计算机与大数据学院 福州 350108, bio={"img":"RY7/jrveuBrl+sPLFaHCsw==","content":"

1998年生. 硕士. 主要研究方向为电子设计自动化

"}, bioImg=RY7/jrveuBrl+sPLFaHCsw==, bioContent=

1998年生. 硕士. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)])]), Author(id=1327018696888922764, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=jrchen@fzu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327018696951837326, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696888922764, language=EN, stringName=Jiarui Chen, firstName=Jiarui, middleName=null, lastName=Chen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1981. PhD, associate professor. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1981. PhD, associate professor. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018697014751887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696888922764, language=CN, stringName=陈家瑞, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1福州大学计算机与大数据学院 福州 350108, bio={"img":"s1CevtU4glDM0m7wq/6BIw==","content":"

1981年生. 博士,副教授. 主要研究方向为电子设计自动化

"}, bioImg=s1CevtU4glDM0m7wq/6BIw==, bioContent=

1981年生. 博士,副教授. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)])]), Author(id=1327018697098637969, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018697186718356, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697098637969, language=EN, stringName=Qinghai Liu, firstName=Qinghai, middleName=null, lastName=Liu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108
3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024, bio={"content":"

born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

"}, bioImg=null, bioContent=

born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018697274798741, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697098637969, language=CN, stringName=刘清海, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2福州大学离散数学中心 福州 350108
3中国福建光电信息科学与技术创新实验室 福州 350024, bio={"img":"WXs/QQuU2vk3lFmu5E0mmQ==","content":"

1982年生. 博士,教授. CCF会员,主要研究方向为图论及应用、组合优化、电子设计自动化

"}, bioImg=WXs/QQuU2vk3lFmu5E0mmQ==, bioContent=

1982年生. 博士,教授. CCF会员,主要研究方向为图论及应用、组合优化、电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694573666934, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=2, ext=[AuthorCompanyExt(id=1327018694586249847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694573666934, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694598832760, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694573666934, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2福州大学离散数学中心 福州 350108)]), AuthorCompany(id=1327018694674330233, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=3, ext=[AuthorCompanyExt(id=1327018694682718842, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694674330233, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024), AuthorCompanyExt(id=1327018694691107451, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694674330233, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中国福建光电信息科学与技术创新实验室 福州 350024)])]), Author(id=1327018697337713303, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018697392239257, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697337713303, language=EN, stringName=Chuandong Chen, firstName=Chuandong, middleName=null, lastName=Chen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, address=4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1982. PhD, associate professor. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1982. PhD, associate professor. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018697480319642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697337713303, language=CN, stringName=陈传东, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, address=4福州大学物理与信息工程学院 福州 350108, bio={"img":"mz4LRyKcOsBiSW7mI1+FEg==","content":"

1982年生. 博士,副教授. 主要研究方向为电子设计自动化

"}, bioImg=mz4LRyKcOsBiSW7mI1+FEg==, bioContent=

1982年生. 博士,副教授. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694770799228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=4, ext=[AuthorCompanyExt(id=1327018694779187837, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694770799228, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694787576446, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694770799228, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4福州大学物理与信息工程学院 福州 350108)])])], keywords=[Keyword(id=1327018697568400027, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, orderNo=1, keyword=electronic design automation (EDA)), Keyword(id=1327018697622925980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, orderNo=2, keyword=printed circuit board), Keyword(id=1327018697698423453, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, orderNo=3, keyword=group routing), Keyword(id=1327018697761338014, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, orderNo=4, keyword=weighted directed graph), Keyword(id=1327018697815863967, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, orderNo=5, keyword=path planning), Keyword(id=1327018697878778528, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, orderNo=1, keyword=电子设计自动化), Keyword(id=1327018697941693089, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, orderNo=2, keyword=印刷电路板), Keyword(id=1327018698021384866, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, orderNo=3, keyword=群组布线), Keyword(id=1327018698092688035, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, orderNo=4, keyword=带权有向图), Keyword(id=1327018698176574116, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, orderNo=5, keyword=路径规划)], refs=[Reference(id=1327018702375072453, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Hsu J, Hung G, Tseng J, et al. High-speed data center PCB design challenges and findings by Intel® automatic in-board characterization[C/OL]//Proc of the 17th Int Microsystems, Packaging, Assembly and Circuits Technology Conf. Piscataway, NJ: IEEE, 2022[2024-04-08]. https://ieeexplore.ieee.org/document/9966724, articleTitle=null, refAbstract=null), Reference(id=1327018702442181318, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Tan Yan. Algorithmic studies on PCB routing[D]. Urbana-Champaign: University of Illinois at Urbana-Champaign, 2010, articleTitle=null, refAbstract=null), Reference(id=1327018702505095879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Lin S T, Wang H H, Kuo C Y, et al. A complete PCB routing methodology with concurrent hierarchical routing[C]//Proc of the 58th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2021: 1141−1146, articleTitle=null, refAbstract=null), Reference(id=1327018702576399048, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Lin T C, Merrill D, Wu Y Y, et al. A unified printed circuit board routing algorithm with complicated constraints and differential pairs[C]//Proc of the 26th Asia and South Pacific Design Automation Conf. New York: ACM, 2021: 170−175, articleTitle=null, refAbstract=null), Reference(id=1327018702651896521, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=邓新国,叶似锦,陈家瑞,等. 结合改进A*算法与拆线重布的有序逃逸布线[J]. 电子与信息学报,2021,43(6):1609−1616, articleTitle=null, refAbstract=null), Reference(id=1327018702719005386, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Deng Xinguo, Ye Sijin, Chen Jiarui, et al. Ordered escape routing combining improved A* algorithm with rip-up and reroute[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1609−1616 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327018702794502859, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Save Y D, Rakhi R, Shambhulingayya N D, et al. Oscad: An open source EDA tool for circuit design, simulation, analysis and PCB design[C]//Proc of the 20th Int Conf on Electronics, Circuits, and Systems. Piscataway, NJ: IEEE, 2013: 851−854, articleTitle=null, refAbstract=null), Reference(id=1327018702861611724, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Goyal P, Agrawal H, Paradiso J A, et al. BoardLab: PCB as an interface to EDA software[C]//Proc of the 26th Annual ACM Symp on the Djunct Publication of the User Interface Software and Technology. New York: ACM, 2013: 19−20, articleTitle=null, refAbstract=null), Reference(id=1327018702920331981, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Wane S, Patton R, Gross N. Unification of instrumentation and EDA tooling platforms for enabling smart chip-package-PCB-probe arrays co-design solutions using advanced RFIC technologies[C/OL]//Proc of the 2018 IEEE Conf on Antenna Measurements & Applications (CAMA). Piscataway,NJ:IEEE,2018[2024-04-08]. https://ieeexplore.ieee.org/document/8530652, articleTitle=null, refAbstract=null), Reference(id=1327018702983246542, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Sherwani N A. Algorithms for VLSI Physical Design Automation[M]. 3rd ed. Berlin: Springer, 2012, articleTitle=null, refAbstract=null), Reference(id=1327018703046161103, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Fang S C, Chang K E, Feng W S, et al. Constrained via minimization with practical considerations for multi-layer VLSI/PCB routing problems[C]//Proc of the 28th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 1991: 60−65, articleTitle=null, refAbstract=null), Reference(id=1327018703138435792, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Cong, Jin Huilin, Chen Jienan, et al. A hierarchy MCTS algorithm for the automated PCB routing[C]//Proc of the 16th Int Conf on Control & Automation. Piscataway, NJ: IEEE, 2020: 1366−1371, articleTitle=null, refAbstract=null), Reference(id=1327018703205544657, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Kahng A B,Lienig J. 超大规模集成电路物理设计:从图分割到时序收敛[M]. 于永斌,冯策,徐宁,等,译. 2版. 北京:机械工业出版社,2024, articleTitle=null, refAbstract=null), Reference(id=1327018703281042130, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Kahng A B, Lienig J. Software Engineering: A Practitioner's Approach[M]. Translated by Yu Yongbin, Feng Ce, Xu Ning, et al. 2nd ed. Beijing: China Machine Press, 2024 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327018703352345299, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Kong Hui, Ma Qiang, Yan Tan, et al. An optimal algorithm for finding disjoint rectangles and its application to PCB routing[C]//Proc of the 47th Design Automation Conf. Piscataway, NJ: IEEE, 2010: 212−217, articleTitle=null, refAbstract=null), Reference(id=1327018703444619988, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Jixin, Xu Ning, Liu Mingyu. FanoutNet: A neuralized PCB fanout automation method using deep reinforcement learning[C]//Proc of the 37th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2023: 8554−8561, articleTitle=null, refAbstract=null), Reference(id=1327018703528506069, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=He Youbiao, Li Hebi, Jin Tian, et al. Circuit routing using Monte Carlo tree search and deep reinforcement learning[C/OL]//Proc of the 2022 Int Symp on VLSI Design, Automation and Test. Piscataway, NJ: IEEE, 2022[2024-04-08]. https://ieeexplore.ieee.org/document/9768074, articleTitle=null, refAbstract=null), Reference(id=1327018703599809238, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=刘郭庆,钱宇华,张亚宇,等. 给定预算下基于相对熵置信区间的蒙特卡洛树搜索最优动作识别算法[J]. 计算机研究与发展,2023,60(8):1780−1794, articleTitle=null, refAbstract=null), Reference(id=1327018703662723799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Liu Guoqing, Qian Yuhua, Zhang Yayu, et al. Best action identification algorithm in Monte Carlo tree search based on relative entropy confidence interval with given budget[J]. Journal of Computer Research and Development, 2023, 60(8): 1780−1794 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327018703725638360, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Goh Y, Jung D, Hwang G, et al. Consumer electronics product manufacturing time reduction and optimization using AI-based PCB and VLSI circuit designing[J]. IEEE Transactions on Consumer Electronics, 2023, 69(3): 240−249, articleTitle=null, refAbstract=null), Reference(id=1327018703805330137, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Hung S C, Chen Hao, Sun Fankeng, et al. A DAG-based algorithm for obstacle-aware topology-matching on-track bus routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(3): 533−546, articleTitle=null, refAbstract=null), Reference(id=1327018703872439002, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Jingsong, Kuang Jian, Zhao Guowei, et al. PROS 2.0: A plug-in for routability optimization and routed wirelength estimation using deep learning[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 42(1): 164−177, articleTitle=null, refAbstract=null), Reference(id=1327018703939547867, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang H T, Fujita M, Cheng C K, et al. SAT-based on-track bus routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(4): 735−747, articleTitle=null, refAbstract=null), Reference(id=1327018703994073820, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Jingsong, Liu Jinwei, Chen Gengjie, et al. MARCH: Maze routing under a concurrent and hierarchical scheme for buses[C/OL]//Proc of the 56th Annual Design Automation Conf 2019. Piscataway, NJ: IEEE, 2019[2024-04-08]. https://ieeexplore.ieee.org/document/8807035, articleTitle=null, refAbstract=null), Reference(id=1327018705655018205, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Kim D, Do S, Lee S Y, et al. Compact topology-aware bus routing for design regularity[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(8): 1744−1749, articleTitle=null, refAbstract=null), Reference(id=1327018705734709982, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Cheng Yihao, Yu Taochun, Fang Shaoyun. Obstacle-avoiding length-matching bus routing considering nonuniform track resources[J]. IEEE Transactions on Very Large Scale Integration Systems, 2020, 28(8): 1881−1892, articleTitle=null, refAbstract=null), Reference(id=1327018705847956191, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Yan Jintai, Chen Zhiwei. Obstacle-aware length-matching bus routing[C]//Proc of the 2011 Int Symp on Physical Design. New York: ACM, 2011: 61−68, articleTitle=null, refAbstract=null), Reference(id=1327018705936036576, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Yan Jintai,Chen Zhiwei. Obstacle-aware length-matching bus routing[C]//Proc of the 2011 Int Symp on Physical Design. New York:ACM,2011:61−68, articleTitle=null, refAbstract=null), Reference(id=1327018706015728353, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Yan Jintai. Single-layer obstacle-aware multiple-bus routing considering simultaneous escape length[J]. IEEE Transactions on Components, Packaging and Manufacturing Technology, 2022, 12(6): 902−915, articleTitle=null, refAbstract=null), Reference(id=1327018706103808738, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Kong Hui, Yan Tan, Wong M D F. Automatic bus planner for dense PCBs[C]//Proc of the 46th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2009: 326−331, articleTitle=null, refAbstract=null), Reference(id=1327018706196083427, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Wu Peici, Ma Qiang, Wong M D F. An ILP-based automatic bus planner for dense PCBs[C]//Proc of the 18th Asia and South Pacific Design Automation Conf. Piscataway, NJ: IEEE, 2013: 181−186, articleTitle=null, refAbstract=null), Reference(id=1327018706271580900, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Tang Hao, Liu Genggeng, Chen Xiaohua, et al. A Survey on Steiner tree construction and global routing for VLSI design[J]. IEEE Access, 2020, 8: 68593-68622, articleTitle=null, refAbstract=null), Reference(id=1327018706351272677, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Tang Hao,Liu Genggeng,Chen Xiaohua,et al. A Survey on Steiner tree construction and global routing for VLSI design[J]. IEEE Access,2020,8:68593-68622, articleTitle=null, refAbstract=null), Reference(id=1327018706468713190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Zachariasen M. A catalog of Hanan grid problems[J]. Networks, 2001, 38(2): 76−83, articleTitle=null, refAbstract=null), Reference(id=1327018706540016359, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=赵奇,赵阿群. 一种基于A*算法的多径寻由算法[J]. 电子与信息学报,2013,35(4):952−957, articleTitle=null, refAbstract=null), Reference(id=1327018706632291048, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhao Qi, Zhao Aqun. A multi-path routing algorithm base on A* algorithm[J]. Journal of Electronics & Information Technology, 2013, 35(4): 952−957 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327018706703594217, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=马博宇,徐宁,吴皓莹,等. 面向柔性电路通道区的自动布线算法[J]. 计算机辅助设计与图形学学报,2022,34(8):1179−1185, articleTitle=null, refAbstract=null), Reference(id=1327018706783285994, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Ma Boyu, Xu Ning, Wu Haoying, et al. Routing Algorithm for flexible printed circuit channel area[J]. Journal of Computer-Aided Design & Computer Graphics, 2022, 34(8): 1179−1185 (in Chinese), articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)]), AuthorCompany(id=1327018694573666934, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=2, ext=[AuthorCompanyExt(id=1327018694586249847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694573666934, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694598832760, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694573666934, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2福州大学离散数学中心 福州 350108)]), AuthorCompany(id=1327018694674330233, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=3, ext=[AuthorCompanyExt(id=1327018694682718842, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694674330233, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024), AuthorCompanyExt(id=1327018694691107451, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694674330233, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中国福建光电信息科学与技术创新实验室 福州 350024)]), AuthorCompany(id=1327018694770799228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=4, ext=[AuthorCompanyExt(id=1327018694779187837, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694770799228, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694787576446, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694770799228, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4福州大学物理与信息工程学院 福州 350108)])], figs=[ArticleFig(id=1327018698306597541, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 1, caption=Flow chart of grouping routing algorithm, figureFileSmall=BVIqlFw+EKEseLdDBP/xNg==, figureFileBig=JTruqVRMYHBayw1PenE+vQ==, tableContent=null), ArticleFig(id=1327018698386289318, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图1, caption=群组布线算法流程图, figureFileSmall=BVIqlFw+EKEseLdDBP/xNg==, figureFileBig=JTruqVRMYHBayw1PenE+vQ==, tableContent=null), ArticleFig(id=1327018698562450087, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 2, caption=Schematic diagram of grid construction, figureFileSmall=7dViCFJ8JDJx2HTtLYh5OA==, figureFileBig=SJZe3SNkca3evEkI06KXRg==, tableContent=null), ArticleFig(id=1327018698625364648, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图2, caption=网格构建示意图, figureFileSmall=7dViCFJ8JDJx2HTtLYh5OA==, figureFileBig=SJZe3SNkca3evEkI06KXRg==, tableContent=null), ArticleFig(id=1327018698688279209, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 3, caption=Several cases of constructing edges when vertices correspond to merged edges are parallel to each other, figureFileSmall=70+CZO3/IIJKYgZE/ON+ng==, figureFileBig=X0BYaCDJpaR8+m741mhhBw==, tableContent=null), ArticleFig(id=1327018698746999466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图3, caption=顶点对应合并边相互平行时构造边的几种情形, figureFileSmall=70+CZO3/IIJKYgZE/ON+ng==, figureFileBig=X0BYaCDJpaR8+m741mhhBw==, tableContent=null), ArticleFig(id=1327018698805719723, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 4, caption=Several cases of constructing edges when vertices correspond to merging edges are perpendicular to each other, figureFileSmall=cuaNVFa9jYB8sVLOLjllhg==, figureFileBig=juqWfaMbbG0Uzm6fgEJBow==, tableContent=null), ArticleFig(id=1327018698864439980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图4, caption=顶点对应合并边相互垂直时构造边的几种情形, figureFileSmall=cuaNVFa9jYB8sVLOLjllhg==, figureFileBig=juqWfaMbbG0Uzm6fgEJBow==, tableContent=null), ArticleFig(id=1327018698927354541, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 5, caption=Schematic diagram of guidelines, figureFileSmall=6M2u1SlCJhMBAY4/KeETjA==, figureFileBig=Dyb7YDR1MKcjyAgAnyJ2lw==, tableContent=null), ArticleFig(id=1327018698990269102, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图5, caption=引导线示意图, figureFileSmall=6M2u1SlCJhMBAY4/KeETjA==, figureFileBig=Dyb7YDR1MKcjyAgAnyJ2lw==, tableContent=null), ArticleFig(id=1327018699057377967, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 6, caption=Construction result of weighted directed graph G, figureFileSmall=AjxyDjoCi+OQiLsQrHfFqQ==, figureFileBig=ZmVGVtswgmEgYVUYSc8GJw==, tableContent=null), ArticleFig(id=1327018699116098224, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图6, caption=带权有向图G构造结果, figureFileSmall=AjxyDjoCi+OQiLsQrHfFqQ==, figureFileBig=ZmVGVtswgmEgYVUYSc8GJw==, tableContent=null), ArticleFig(id=1327018699187401393, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 7, caption=Schematic diagram of four limiting relationships of acquisition points, figureFileSmall=U/a2viVo6ugAsMP2lN510Q==, figureFileBig=W4zrInaLMasGk8nNrPBrPQ==, tableContent=null), ArticleFig(id=1327018699271287474, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图7, caption=取点的4种限制关系示意图, figureFileSmall=U/a2viVo6ugAsMP2lN510Q==, figureFileBig=W4zrInaLMasGk8nNrPBrPQ==, tableContent=null), ArticleFig(id=1327018699334202035, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 8, caption=Schematic diagram of path planning and detailed routing, figureFileSmall=wv+UbhiRu0fNKp4jjg1Uqg==, figureFileBig=FMUEbeaJ5trzgqGQxMbMiw==, tableContent=null), ArticleFig(id=1327018699397116596, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图8, caption=路径规划以及详细布线示意图, figureFileSmall=wv+UbhiRu0fNKp4jjg1Uqg==, figureFileBig=FMUEbeaJ5trzgqGQxMbMiw==, tableContent=null), ArticleFig(id=1327018699460031157, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 9, caption=Schematic diagram of vector and relative position judgment, figureFileSmall=q5XMU6iaRGYxlJcGtaQlQA==, figureFileBig=wTOqGIGpfPVJ65DepsdbGg==, tableContent=null), ArticleFig(id=1327018701196473014, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图9, caption=向量与相对位置判断示意图, figureFileSmall=q5XMU6iaRGYxlJcGtaQlQA==, figureFileBig=wTOqGIGpfPVJ65DepsdbGg==, tableContent=null), ArticleFig(id=1327018701271970487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 10, caption=Routing results of PCB4 when weight(e) is 0, figureFileSmall=xD3Bb5/YZQqKJlKVi/QyDg==, figureFileBig=xYl6lzB0X5CG1SfbmhbLeQ==, tableContent=null), ArticleFig(id=1327018701347467960, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图10, caption=权重weight(e)为0时的PCB4布线结果, figureFileSmall=xD3Bb5/YZQqKJlKVi/QyDg==, figureFileBig=xYl6lzB0X5CG1SfbmhbLeQ==, tableContent=null), ArticleFig(id=1327018701443936953, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 11, caption=Routing results of PCB4when weight(e) is 100, figureFileSmall=ICTV1VZ22vp23QXpsG8qWg==, figureFileBig=pa7+Avv6cSBaeGaEOvdILQ==, tableContent=null), ArticleFig(id=1327018701523628730, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图11, caption=权重weight(e)为100时的PCB4布线结果, figureFileSmall=ICTV1VZ22vp23QXpsG8qWg==, figureFileBig=pa7+Avv6cSBaeGaEOvdILQ==, tableContent=null), ArticleFig(id=1327018701578154683, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 12, caption=Routing results of PCB8, figureFileSmall=WoKH2n1OOEVjq5n0zHkzbQ==, figureFileBig=c/Q0G4PAJZnXv1Uz+hij5A==, tableContent=null), ArticleFig(id=1327018701645263548, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图12, caption=PCB8布线结果, figureFileSmall=WoKH2n1OOEVjq5n0zHkzbQ==, figureFileBig=c/Q0G4PAJZnXv1Uz+hij5A==, tableContent=null), ArticleFig(id=1327018701745926845, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Figure 13, caption=Routing results of PCB9 after pre-layering when weight(e) is 100, figureFileSmall=bcb1tPxTKkMf0mkGOloe7w==, figureFileBig=qc2z4oQL/tQ1KCsz7HNJTw==, tableContent=null), ArticleFig(id=1327018701813035710, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=图13, caption=经预先分层后权重weight(e)为100时PCB9的布线结果, figureFileSmall=bcb1tPxTKkMf0mkGOloe7w==, figureFileBig=qc2z4oQL/tQ1KCsz7HNJTw==, tableContent=null), ArticleFig(id=1327018701884338879, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Table 1, caption=Statistics for Benchmark Printed Circuit Board Design, figureFileSmall=null, figureFileBig=null, tableContent=
设计引脚数焊盘数过孔数未布线线网数总线群组组数
PCB11010051
PCB21010551
PCB316322281
PCB4204031101
PCB5204031102
PCB63016312155
PCB78417286423
PCB81402861731404
PCB96121231
), ArticleFig(id=1327018701976613568, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=表1, caption=

基准印刷电路板设计统计

, figureFileSmall=null, figureFileBig=null, tableContent=
设计引脚数焊盘数过孔数未布线线网数总线群组组数
PCB11010051
PCB21010551
PCB316322281
PCB4204031101
PCB5204031102
PCB63016312155
PCB78417286423
PCB81402861731404
PCB96121231
), ArticleFig(id=1327018702039528129, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Table 2, caption=Comparison of Routing Results of Each Algorithm, figureFileSmall=null, figureFileBig=null, tableContent=
设计布通率 /%运行时间 /sDRV次数
FreeRoutingCadance Allegro本文算法FreeRoutingCadance Allegro本文算法FreeRoutingCadance Allegro本文算法
注:“-”表示设计无法在软件上运行,或者运行时间超过1 h.
PCB11001001000.030.0080.001000
PCB21001001000.110.0250.003000
PCB31001001000.70.190.023100
PCB41001001001.50.350.041300
PCB51001001001.50.370.048300
PCB693.31001008.22.40.21700
PCB757.197.610094.713.22.11520
PCB8-64.8100-109.716.4-1060
), ArticleFig(id=1327018702131802818, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=表2, caption=

各算法的布线结果比较

, figureFileSmall=null, figureFileBig=null, tableContent=
设计布通率 /%运行时间 /sDRV次数
FreeRoutingCadance Allegro本文算法FreeRoutingCadance Allegro本文算法FreeRoutingCadance Allegro本文算法
注:“-”表示设计无法在软件上运行,或者运行时间超过1 h.
PCB11001001000.030.0080.001000
PCB21001001000.110.0250.003000
PCB31001001000.70.190.023100
PCB41001001001.50.350.041300
PCB51001001001.50.370.048300
PCB693.31001008.22.40.21700
PCB757.197.610094.713.22.11520
PCB8-64.8100-109.716.4-1060
), ArticleFig(id=1327018702203105987, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=EN, label=Table 3, caption=Comparison of Group Routing Performance of Each Algorithm, figureFileSmall=null, figureFileBig=null, tableContent=
设计FreeRoutingCadance Allegro本文算法
$ \mathcal{C}_{WL} $$ \mathcal{C}_{S} $$ \mathcal{C}_{C} $$\mathcal {C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $$\mathcal {C}_{WL} $$ \mathcal{C}_{S} $$\mathcal {C}_{C} $$\mathcal {C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $$\mathcal {C}_{WL} $$ \mathcal{C}_{S} $$\mathcal {C}_{C} $$\mathcal {C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $
注:“-”表示设计无法在软件上运行,或者运行时间超过1 h.
PCB11.041.674.046.751.011.003.505.511.161.671.003.83
PCB21.061.674.216.941.122.001.004.121.161.501.003.66
PCB31.072.004.367.431.171.501.003.671.291.321.003.61
PCB41.052.334.567.941.211.861.004.071.391.351.003.74
PCB51.052.334.567.941.142.001.004.141.171.221.003.39
PCB61.342.753.988.071.402.501.004.901.372.401.004.77
PCB71.202.134.297.621.201.821.004.021.181.601.003.78
PCB8----1.351.901.004.251.371.721.004.09
), ArticleFig(id=1327018702270214852, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, language=CN, label=表3, caption=

各方法的群组布线性能比较

, figureFileSmall=null, figureFileBig=null, tableContent=
设计FreeRoutingCadance Allegro本文算法
$ \mathcal{C}_{WL} $$ \mathcal{C}_{S} $$ \mathcal{C}_{C} $$\mathcal {C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $$\mathcal {C}_{WL} $$ \mathcal{C}_{S} $$\mathcal {C}_{C} $$\mathcal {C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $$\mathcal {C}_{WL} $$ \mathcal{C}_{S} $$\mathcal {C}_{C} $$\mathcal {C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $
注:“-”表示设计无法在软件上运行,或者运行时间超过1 h.
PCB11.041.674.046.751.011.003.505.511.161.671.003.83
PCB21.061.674.216.941.122.001.004.121.161.501.003.66
PCB31.072.004.367.431.171.501.003.671.291.321.003.61
PCB41.052.334.567.941.211.861.004.071.391.351.003.74
PCB51.052.334.567.941.142.001.004.141.171.221.003.39
PCB61.342.753.988.071.402.501.004.901.372.401.004.77
PCB71.202.134.297.621.201.821.004.021.181.601.003.78
PCB8----1.351.901.004.251.371.721.004.09
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202440069, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440069, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202440069, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202440069, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1753977600000, fullTextJson=null, articleText=null, reference=null)
收藏切换
一种基于带权有向图的印刷电路板群组布线算法
邓新国 1 , 张鑫泓 1 , 陈家瑞 1, * , 刘清海 2, 3 , 陈传东 4
计算机研究与发展 | 体系结构 2025,62(8): 1948-1961
收起
收藏切换
计算机研究与发展 |体系结构 2025 , 62 (8) : 1948 -1961
一种基于带权有向图的印刷电路板群组布线算法
全屏
[Author(id=1327018694850491008, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=xgdeng@fzu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018694930182786, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018694850491008, language=EN, stringName=Xinguo Deng, firstName=Xinguo, middleName=null, lastName=Deng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1975. PhD, associate professor. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1975. PhD, associate professor. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018696599515780, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018694850491008, language=CN, stringName=邓新国, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1福州大学计算机与大数据学院 福州 350108, bio={"img":"97sVJ+FD4BAmM73tuiQ6lQ==","content":"

1975年生. 博士,副教授. 主要研究方向为电子设计自动化

"}, bioImg=97sVJ+FD4BAmM73tuiQ6lQ==, bioContent=

1975年生. 博士,副教授. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)])]), Author(id=1327018696679207558, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018696750510728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696679207558, language=EN, stringName=Xinhong Zhang, firstName=Xinhong, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1998. Master. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1998. Master. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018696821813897, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696679207558, language=CN, stringName=张鑫泓, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1福州大学计算机与大数据学院 福州 350108, bio={"img":"RY7/jrveuBrl+sPLFaHCsw==","content":"

1998年生. 硕士. 主要研究方向为电子设计自动化

"}, bioImg=RY7/jrveuBrl+sPLFaHCsw==, bioContent=

1998年生. 硕士. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)])]), Author(id=1327018696888922764, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=jrchen@fzu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327018696951837326, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696888922764, language=EN, stringName=Jiarui Chen, firstName=Jiarui, middleName=null, lastName=Chen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1981. PhD, associate professor. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1981. PhD, associate professor. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018697014751887, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018696888922764, language=CN, stringName=陈家瑞, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1福州大学计算机与大数据学院 福州 350108, bio={"img":"s1CevtU4glDM0m7wq/6BIw==","content":"

1981年生. 博士,副教授. 主要研究方向为电子设计自动化

"}, bioImg=s1CevtU4glDM0m7wq/6BIw==, bioContent=

1981年生. 博士,副教授. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694481392243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=1, ext=[AuthorCompanyExt(id=1327018694493975156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1College of Computer and Data Science, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694502363765, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694481392243, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1福州大学计算机与大数据学院 福州 350108)])]), Author(id=1327018697098637969, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018697186718356, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697098637969, language=EN, stringName=Qinghai Liu, firstName=Qinghai, middleName=null, lastName=Liu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108
3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024, bio={"content":"

born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

"}, bioImg=null, bioContent=

born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018697274798741, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697098637969, language=CN, stringName=刘清海, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2福州大学离散数学中心 福州 350108
3中国福建光电信息科学与技术创新实验室 福州 350024, bio={"img":"WXs/QQuU2vk3lFmu5E0mmQ==","content":"

1982年生. 博士,教授. CCF会员,主要研究方向为图论及应用、组合优化、电子设计自动化

"}, bioImg=WXs/QQuU2vk3lFmu5E0mmQ==, bioContent=

1982年生. 博士,教授. CCF会员,主要研究方向为图论及应用、组合优化、电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694573666934, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=2, ext=[AuthorCompanyExt(id=1327018694586249847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694573666934, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694598832760, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694573666934, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2福州大学离散数学中心 福州 350108)]), AuthorCompany(id=1327018694674330233, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=3, ext=[AuthorCompanyExt(id=1327018694682718842, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694674330233, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024), AuthorCompanyExt(id=1327018694691107451, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694674330233, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3中国福建光电信息科学与技术创新实验室 福州 350024)])]), Author(id=1327018697337713303, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327018697392239257, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697337713303, language=EN, stringName=Chuandong Chen, firstName=Chuandong, middleName=null, lastName=Chen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, address=4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108, bio={"content":"

born in 1982. PhD, associate professor. His main research interest includes electronic design automation

"}, bioImg=null, bioContent=

born in 1982. PhD, associate professor. His main research interest includes electronic design automation

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327018697480319642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, authorId=1327018697337713303, language=CN, stringName=陈传东, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, address=4福州大学物理与信息工程学院 福州 350108, bio={"img":"mz4LRyKcOsBiSW7mI1+FEg==","content":"

1982年生. 博士,副教授. 主要研究方向为电子设计自动化

"}, bioImg=mz4LRyKcOsBiSW7mI1+FEg==, bioContent=

1982年生. 博士,副教授. 主要研究方向为电子设计自动化

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327018694770799228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, xref=4, ext=[AuthorCompanyExt(id=1327018694779187837, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694770799228, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108), AuthorCompanyExt(id=1327018694787576446, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327018689104294476, companyId=1327018694770799228, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4福州大学物理与信息工程学院 福州 350108)])])]
邓新国1 , 张鑫泓1, 陈家瑞1, * , 刘清海2, 3, 陈传东4
作者信息
  • 1福州大学计算机与大数据学院 福州 350108
  • 2福州大学离散数学中心 福州 350108
  • 3中国福建光电信息科学与技术创新实验室 福州 350024
  • 4福州大学物理与信息工程学院 福州 350108
通讯作者:
陈家瑞()
作者简介:

1975年生. 博士,副教授. 主要研究方向为电子设计自动化

1998年生. 硕士. 主要研究方向为电子设计自动化

1981年生. 博士,副教授. 主要研究方向为电子设计自动化

1982年生. 博士,教授. CCF会员,主要研究方向为图论及应用、组合优化、电子设计自动化

1982年生. 博士,副教授. 主要研究方向为电子设计自动化

A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards
Xinguo Deng1 , Xinhong Zhang1, Jiarui Chen1, * , Qinghai Liu2, 3, Chuandong Chen4
Affiliations
  • 1College of Computer and Data Science, Fuzhou University, Fuzhou 350108
  • 2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108
  • 3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024
  • 4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108
  • born in 1975. PhD, associate professor. His main research interest includes electronic design automation

    born in 1998. Master. His main research interest includes electronic design automation

    born in 1981. PhD, associate professor. His main research interest includes electronic design automation

    born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

    born in 1982. PhD, associate professor. His main research interest includes electronic design automation

出版时间: 2025-08-01 doi: 10.7544/issn1000-1239.202440069
文章导航
收藏切换

布线是印刷电路板设计中的重要一环. 现有的印刷电路板设计多依赖于电子设计自动化工具的处理,而传统的自动布线研究多聚焦于总线布线,没有将布线时确定的群组作为研究对象. 由于未经总线分组,可能存在群组中线网较多的情况,这将导致群组所占据的线宽与线间距比原先总线布线中各总线组分别占据的线宽与线间距更大,从而给实际布线带来了新的挑战. 为此,提出一种基于带权有向图的群组布线算法. 首先构建仅含有合并边以及它们之间邻接关系的Hanan网格图. 接着,利用合并边信息构建带权有向图,完成对电路板上布线资源的表示. 然后,使用一种具有多线避让功能的启发式搜索算法来进行布线规划. 最后,通过将布线归类为数种可能的情况分别考虑,完成详细布线并得到群组布线的最终结果. 实验结果表明,所提算法在已经测试过的工业界复杂例子上均能达到100%的布通率,并且不会违反所有工业印刷电路板基准用例的设计规则约束.

电子设计自动化  /  印刷电路板  /  群组布线  /  带权有向图  /  路径规划

Routing is considered as an essential component in the design of printed circuit board (PCB). Current existing PCB designs mostly rely on the process results from electronic design automation tools, and traditional automatic routing research often focuses on the only general bus routing without considering bus groups to be determined during the routing process. Due to the absence of general bus grouping, there may be situations where there are more nets in one group than in the other groups, resulting in larger line width and line clearance occupied by this group when compared with other bus groups in the original bus routing, thereby posing new challenges to effective and efficient routing. To overcome this drawback, we focus on studying PCB group routing. In this study, a group routing algorithm based on a weighted directed graph is proposed. A Hanan grid graph is constructed, containing the only merged edges and their adjacent relationships. Following this, a weighted directed graph is developed using the merged edge information to represent the routing resources on the circuit board. For routing planning, a heuristic search algorithm equipped with multi-wire avoidance features is utilized. The routing situations are then classified into several potential scenarios, with each considered separately, to accomplish detailed routing and obtain a final result of group routing. Results from experiments demonstrate that 100% routability is consistently achieved by using the algorithm on complex industrial examples that have been previously tested, and that the design rule constraints of all benchmark industrial PCB cases are not violated.

electronic design automation (EDA)  /  printed circuit board  /  group routing  /  weighted directed graph  /  path planning
邓新国, 张鑫泓, 陈家瑞, 刘清海, 陈传东. 一种基于带权有向图的印刷电路板群组布线算法. 计算机研究与发展, 2025 , 62 (8) : 1948 -1961 . DOI: 10.7544/issn1000-1239.202440069
Xinguo Deng, Xinhong Zhang, Jiarui Chen, Qinghai Liu, Chuandong Chen. A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards[J]. Journal of Computer Research and Development, 2025 , 62 (8) : 1948 -1961 . DOI: 10.7544/issn1000-1239.202440069
电子设备广泛应用于与国家基础设施和民众生活紧密相关的各项领域. 在这些设备中,印刷电路板(printed circuit board,PCB)被誉为“电子产品之母”. PCB不仅为电子元器件提供了电子元器件的支持和电气连接,还承担着电路的载体角色,是电子设备不可或缺的核心组成部分[1].
当前,随着集成电路技术的迅猛发展,PCB的复杂度也在显著增加. 这种复杂度体现在多个方面:不断增加的线网(net)和引脚(pin)数量、多达十数层的PCB层数、极高的引脚密度、独特的物理限制以及高速PCB设计所带来的信号完整性问题[1]等,这就使得无法像过去那样仅仅使用人工对设计规则予以逐一检查,因此,以往那种借由个人经验进行的PCB手工布线成为了一项耗时且容易出错的工作[2],传统的设计流程变得不再适用[3-5]. 有鉴于此,复杂的PCB设计现多依赖于电子设计自动化(electronic design automation,EDA)工具处理以实现布线效率的优化,以最大限度地满足电子设计周期的需求[6-8]. 利用EDA进行的PCB设计,通常包括原理图绘制、结构设计、布局、布线等流程[9],其中布线问题是最为关键的问题之一[10-11].
在具有复杂线网的PCB电路布线问题中,群组布线问题尤为重要. 此问题涉及将人工指定的多个线网视作群组,继而将它们以彼此相邻、长度相近的布线方式加以连接. 如何在不违反设计规则约束(design rule constraints,DRC)的条件下有效利用有限的布线空间并提高布线成功率是群组布线需要研究的关键问题.
本文主要贡献有3点:
1)在使用Hanan网格方法构图后,在构图过程中引入一种面合并算法以及合并边方法以缩减原始Hanan网格的规模,在有效减少后续构建带权有向图的复杂度的同时,解决了传统方法得到的网格构图通常有一定量冗余信息的问题.
2)提出一种基于带权有向图的群组布线算法,利用得到的合并边及其位置关系等信息构建带权有向图,实现对群组布线问题的数学建模,从而克服传统网格化方法易受网格精度以及网格数量限制的缺陷.
3)提出一种与路径规划算法相适配的详细布线算法,将详细布线问题分解为多种基本情形考虑,设计数种基本线形以应对各种可能的布线情形,使算法具备实际应用价值,避免详细布线算法与路径规划算法不适配的问题.
PCB布线问题通常可被划为逃逸布线(escape routing)与区域布线(area routing)两个阶段[12],逃逸布线阶段主要负责将线网从引脚布线至组件边界,区域布线阶段则负责对逃逸至组件边界的线网进行连接,而群组布线一般在区域布线阶段进行. 群组布线问题就具体场景而言,又可简化为若干子问题,典型的有总线布线. 总线布线与群组布线的区别在于,它会在布线前预先进行分组,将预计需要一起布线的线网划分为一组总线[13],而群组布线可以在布线时确定群组,也可以进行交互式布线,具有较大的灵活性. 印刷电路板群组布线是商业布线工具中重要的组成部分,然而,关于印刷电路板群组布线问题的相关研究却鲜少出现在近年来的公开文献当中,因而对该问题的研究只能参考其子问题——总线布线. 对于总线布线而言,其中一种分类依据是根据布线时有无轨道约束其被划分为有轨道总线布线问题和无轨道总线布线问题. 由于未经总线分组,可能存在群组中线网较多的情况,这将导致群组中线网所占用的总线宽比原先总线布线中各总线组分别占据的线宽更大,从而给实际布线带来新的挑战.
有些研究不针对特定阶段的布线问题,而是专注于更一般的印刷电路板自动布线问题. 如Lin等人[3]提出了一种具有并发分层布线功能的全阶段印刷电路板布线方法,该方法基于布尔可满足性问题(Boolean satisfiability problem,SAT),但是该方法只适用于解决球栅阵列(ball grid array,BGA)封装的印刷电路板布线问题[14]. Lin等人[4]则提出了一种全板布线算法,在构图阶段使用了均分网格,可以对非BGA封装进行布线,并且可以进行多层差分对布线. 但是该方法在复杂情况下的布通率难以达到100%[14]. He等人[15]提出了一种两阶段印刷电路板布线算法,该算法的2个阶段分别为基于蒙特卡洛树搜索[16](Monte Carlo tree search,MCTS)的全局布线和基于A*的详细布线,能够进行BGA和非BGA封装布线. 但是该方法是一种布线仿真方法,所使用的例子为简化后的现实电路,是一种理想化的场景,因而无法直接应用于复杂的工业界样例[17].
印刷电路板有轨道总线布线问题只允许在给定的布线轨道上进行布线. 对于这一问题,Hung等人[18]提出了一种基于有向无环图(directed acyclic graph,DAG)的总线布线算法. 该算法利用最长公共子序列(longest common subsequence, LCS)、Dijkstra算法以及拆线重布的方法优化布线. 然而,问题在于,可能会产生大量的间距违规,并且在初始拥塞区域过多时,无法有效消除拥塞[19]. Zhang等人[20]提出了一种基于迷宫布线和SAT的总线布线算法. 基于多级框架的总线布线器MARCH[21]是一种基于并发和多层次方案的总线迷宫布线方法,它由粗粒度的拓扑感知路径规划和细粒度的轨道分配组成,应用了有效的拆线布线方案. Kim等人[22]提出了一种拓扑感知总线布线算法,使用专门针对总线级别的3D平铺网格进行布线拓扑生成. 但是这些算法大都聚焦于有轨道总线布线问题,具有一定的特殊性,通常难以扩展到更加一般的无轨道约束总线布线问题.
近年来,也有几种算法被提出以解决无轨道约束的某些总线布线问题,它们通常需要依赖网格来进行路径规划和实际布线. 其中一些算法事先预置均分网格. Cheng等人[23]提出了一种考虑障碍物的长度匹配总线布线算法,该算法利用先深度优先搜索后广度优先搜索的思想进行布线,并在流程中加入了拆线重布环节. Yan等人[24-25]提出了基于长度匹配的总线布线算法,利用带权无向图表示区域之间的布线资源,并使用最大流算法寻找线网匹配. 上述算法将特殊设计约束即长度匹配约束作为考虑重点.
另一些算法则构建Hanan网格. Kong等人[26]通过构建冲突图和更新Hanan网格来规划路径,使用关键割减少拥塞. Wu等人[27]采用整数线性规划(integer linear programming,ILP)方法,在动态的Hanan网格图上完成全局总线布线,该算法同样利用关键割方法解决拥塞问题. ILP方法可以提供总线布线的全局视图,但可能需要相当长的时间[28].
为解决群组布线问题,本文提出一种使用面合并算法缩减Hanan网格规模,利用基于带权有向图的群组布线算法,在有效表示电路板上的布线资源的同时避免传统网格方法易受网格精度和数量限制的缺陷. 同时采用具有多线避让功能的启发式搜索算法,该搜索算法在自动布线的同时也支持人工引导布线方向,这在有效降低时间开销的同时保证了布线质量. 最后该算法使用了一种适用于所提出的路径规划算法的详细布线算法,具有较高的运行效率.
首先输入一组需要进行群组布线的双端线网(net)$ \mathcal{N} $,这些线网所包含的一组引脚(pin)$ \mathcal{P} $,还有印刷电路板上的一系列障碍物如过孔(via)、禁行区等以及印刷电路板的分层信息,此外还有一系列设计规则约束等. 给定双端线网的每对引脚必须在不违反设计规则约束的前提下相互连接. 印刷电路板群组布线问题需要遵循的设计规则约束如下:
1)由2点确定的最短轨迹即最小线长必须大于等于允许的最小线宽;
2)走线必须满足线与线之间、线与各种障碍物之间的最小线间距;
3)同层的走线之间不允许存在交叉;
4)走线拐角角度必须是135°且走线方向必须与印刷电路板板的x轴呈45°的整数倍;
5)所有引脚的走线尽量汇聚;
6)所有引脚的走线拓扑尽量相似;
7)所有引脚的走线长度尽量相近.
该问题的目标是在不违反设计规则约束的前提下,最大化连接的线网对数,即布通率应尽可能的高;在此基础上,布线时间应尽可能的短.
群组布线算法流程如图1所示. 首先,构建Hanan网格图,并在构建完成后对它进行边合并. 接着,利用前述得到的合并边信息构建带权有向图,完成对电路板上布线资源的表示. 然后,利用一种具有多线避让功能的启发式搜索算法来进行布线的边序列搜索,继而进行路径规划. 最后,通过将布线归类为数种可能的情况分别考虑,完成详细布线并得到群组布线的最终结果. 在详细布线步骤前,若线网未规划完毕,就会重新进行启发式搜索,直到完成所有失败线网的路径规划为止.
为了能够有效记录PCB中的各种布线资源,例如各器件、各障碍物的大小和坐标,以及它们之间的相互位置关系等,传统的做法是将它们以网格图的方式加以表示. 典型的网格图有Hanan网格图. 在几何学中,对平面中有限点的集合构造Hanan网格将会对集合中的每个点构造横线以及竖线[29]. 而在实际应用中,Hanan网格在构图时会对集中的每个点进行横向或是纵向延伸,直到延伸线碰触到其他器件的边界抑或是PCB板边界为止. 器件如焊盘、通孔的边界会在考虑器件与走线之间的最小间距之后以矩形包围盒的方式予以体现. 随后,在构图结束时,该方法便能够得到顶点、边以及网格之间的邻接关系.
Hanan网格图,构建示意图如图2(a)所示. 从示意图中不难看出,Hanan网格构图存在有易受网格精度影响的缺陷. 以Hanan网格$ {c}_{1} $也即面$ {c}_{1} $为例,显然当走线线宽超过该网格的宽度时,走线便无法从竖直方向顺利通过,因而对布线资源造成了浪费. 更糟糕的是,当网格的划分越稠密时,这一问题便会越明显,在极端情况下甚至可能存在无法布线的情况. 有鉴于此,本文提出了构造基于Hanan网格图的面合并以及合并边算法以克服这一缺陷.
为了有效缩减问题规模,需要对Hanan网格图进行面合并. 算法首先需要确定面合并的顺序,不失一般性,算法按从左到右,自下而上的顺序进行面合并. 假设整体布线方向为水平方向. 以下给出面合并算法,算法从对角线、纵向以及横向3个方向尝试进行面合并,在面合并遇到障碍物或是相邻面存在宽度小于线宽与线间距之和时停止.
面合并算法步骤如算法1所示.
算法1. 面合并算法.
输入:Hanan网格图$ H $;
输出:面合并后的Hanan网格图$ {H}' $.
① 设图$ H $中所有面的集合为$ F $,图$ H $中所有障碍 物包围盒的边集合为$ Ob $,由面的左下角坐 标组成的最小优先队列$ Q\ne \varnothing $,ℓ=1;
② while ℓ≤3
③  for $ f\in F $
④   if 当前面$ f $的任意一条边$ e $与$ Ob $中的所有 边$ obst $都不存在相交 then
⑤     $ Q\leftarrow Q.push\left(\left\langle{{f}_{\rm lbx},{f}_{\rm lby}}\right\rangle\right) $;
⑥   end if
⑦  end for
⑧  while $ Q\ne \varnothing $
⑨   选择$ Q $中队首元素对应的面$ f $,面$ f $的左 下角坐标为$ {f}_{\rm lb}\left\langle{{f}_{\rm lbx},{f}_{\rm lby}}\right\rangle $,右上角坐标为 $ {f}_{\rm rt}\left\langle{{f}_{\rm rtx},{f}_{\rm rty}}\right\rangle $,它们之间构成区域面积;
⑩  end while
⑪  while 当前区域面积内的面均存在于$ Q $中
⑫   if 当前区域的相邻面的长或宽不大于线 宽与线间距之和 then
⑬    break;
⑭   else
⑮    if ℓ=1 then
⑯     根据图$ H $的邻接关系寻找位区域面 积斜右上方的面$ {f}_{\rm rt}' $,该面左下角顶 点与区域面积右上方顶点重合. 令 $ {f}_{\rm rt}' $的右上角坐标为$ {f}_{\rm rt}'\left\langle{{f}_{\rm rtx}',{f}_{\rm rty}'}\right\rangle $,若 $ {f}_{\rm lb} $与$ {f}_{\rm rt}' $围成的区域中的面均存在于 $ Q $中,则$ {f}_{\rm lb} $与$ {f}_{\rm rt}' $之间构成区域面积;
⑰    end if
⑱    if ℓ=2 then
⑲     根据图$ H $的邻接关系寻找与区域面 积正上方的面$f'_{{{\rm top}}} $,该面右下角顶点 与区域面积右上方顶点重合. 令$f'_{{{\rm top}}} $ 的右上角坐标为$f'_{{{\rm top}}} $〈$f'_{\rm rtx}, f'_{\rm rty} $〉,若$ {f}_{\rm lb} $ 与$ {f}_{\rm rt}' $围成的区域中的面均存在于$ Q $ 中,则$ {f}_{\rm lb} $与$ {f}_{\rm rt}' $之间构成区域面积;
⑳    end if
㉑    if ℓ=3 then
㉒     根据图$ H $的邻接关系寻找与面积正 右方的面$f'_{{{\rm right}}} $,该面左上角顶点与区 域面积右上方顶点重合,令$f'_{{\rm right}} $的 右上角坐标为$f'_{{\rm right}} $〈$f'_{\rm rtx}, f'_{\rm rty} $〉,若$ {f}_{\rm lb} $与 $f'_{{{\rm rt}}} $围成的区域中的面均存在于$ Q $ 中,则$ {f}_{\rm lb} $与$ {f}_{\rm rt}' $之间构成区域面积;
㉓    end if
㉔  end while
㉕    让包含在区域面积中的面f从$ Q $中出队;
㉖    if (区域包含的面f的个数)>1 then
㉗     根据区域面积更新集合$ F $,将区域作 为合并面,更新图$ H $中区域包含的 所有面的邻接关系;
㉘    end if
㉙     ℓ++;
㉚ end while
㉛ return 合并面后的Hanan网格图$ {H}' $.
算法1行②的循环在常数项时间内可以完成. 在行③~⑦使用了1次循环,时间复杂度为$ O\left(n\right) $. 而算法的主要时间花费则集中在行⑧~㉘中所包含的步骤,它包含了2次循环,最坏时间复杂度为$ O({n}^{2}) $. 综上,算法的整体时间复杂度为$ O({n}^{2}) $.
当整体布线方向为竖直方向时,只需将算法1中的行⑱和行㉑交换即可. 假设图2(a)中线段AA′以及线段BB′的长度小于线宽与线间距之和,其他部分除非长度与这些线段相等,否则长度均大于线宽与线间距之和. 根据算法1,首先在图2(a)中选择位于左下角的Hanan网格$ {c}_{3} $,继而沿对角线向右上方进行扩展. 由于扩展后得到的合并面$ m{c}_{1} $,其相邻面$ {c}_{2} $的宽度小于线宽与线间距之和,因此此次合并无效. 而在扫描至Hanan网格$ {c}_{4} $时,根据算法将其扩展至合并面$ {mc}_{2} $,在检查后发现此次合并有效,因此合并面$ {mc}_{2} $便能够得到保留.
而传统的Hanan网格构图,只能在构图结束后得到合并边中的数段短边,以图2(b)为例,在Hanan点$ {v}_{1} $与$ {v}_{2} $之间,它仅仅能得到其中的8段短边,这将对后续的布线规划造成困难. 有鉴于此,本文提出了一种边合并方法. 该方法将障碍物包围盒或者边界线都视为障碍物线,以图2(b)为例,它能够得到以Hanan点$ {v}_{1} $,$ {v}_{2} $为端点的一整条合并边. 该方法的具体步骤为:首先,扫描所有Hanan边,之后,对位于障碍物线之间且具有相同横坐标或纵坐标的线段进行合并,所得到的边即为合并边. 在得到合并边之后,将位于障碍物线之间且具有相同横坐标或纵坐标的线段予以删除. 重复这一过程,便能够得到全部合并边.
这一阶段主要是利用合并边构造带权有向图的算法,将合并边的邻接关系以及通道容量大小保存至有向图中.
算法将所有合并边按照一定顺序进行排序,不失一般性,可将竖直边按照竖直坐标从小到大排序,水平边同理. 随后,算法将排序后的每一条合并边都抽象为有向图$ G $中的2个顶点$ {v}_{i_1}^{dir_1},{v}_{i_2}^{{d}{i}{r}_2} $,以水平边为例,它表示了布线的2个方向,即走线从上往下穿过该边(顶点的方向dir记作up)以及走线从下往上穿过该边(顶点的方向dir记作down),竖直边同理(顶点的方向dir分别记作left,right). 所有顶点构成顶点的集合$ V(G) $.
随后,算法从顶点集合$ V(G) $中按照排序后的顺序取出顶点对$ {v}_{i}^{{d}{i}{r}_i} $,$ {v}_{j}^{{d}{i}{r}_j} $,并尝试在它们之间构造边$ {e}_{ij} $. 它们所对应的合并边记作$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $在图例中${HE}_{{v}_{1}} $简化为$l_1 $,以此类推. 构造时遵循以下原则:
1)若$ {HE}_{{v}_{i}} $和$ HE_{{v}_{j}} $相互平行,则有:
diri和dirj方向相反的顶点对之间不能构造边.图3(a)所示,走线显然无法在从上往下穿过$ {HE}_{{v}_{1}} $的同时再从下往上穿过$ {HE}_{{v}_{2}} $,因此顶点$ {v}_{1}^{\mathrm{u}\mathrm{p}} $和$ {v}_{2}^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}} $之间无法构造边.
$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $之间若不存在相错关系,则它们之间不能构造边. 如图3(b)所示,走线在穿过$ {HE}_{{v}_{1}} $和$ {HE}_{{v}_{2}} $的过程中,必然会经过其他顶点对应的合并边(图中未直接画出),因此顶点$ {v}_{1}^{\rm up} $和$ {v}_{2}^{\rm up} $之间无法构造边.
$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $之间若有障碍物,则它们之间不能构造边. 示意图如图3(c)所示.
若$ {v}_{i}^{{d}{i}{r}_i} $或$ {v}_{j}^{{d}{i}{r}_j} $已经存在相互平行的连边,则不能构造边. 如图3(d)所示,不妨设此时坐标已经按照y轴坐标从大到小排序(从小到大排序同理),则$ {v}_{1}^{\rm up} $和$ {v}_{2}^{\rm up} $将先行构造边,该边记作$ {e}_{12} $. 显然此时在$ {v}_{1}^{\rm up} $和$ {v}_{3}^{\mathrm{u}\mathrm{p}} $之间便无法再构造边,因为走线在通过$ {v}_{1}^{\rm up} $之后,必须先经过$ {v}_{2}^{\rm up} $才能到达$ {v}_{3}^{\rm up} $.
边的容量$ cap({e}_{ij}) $按$ H E_{v_{i}} $与$ H E_{v_{j}} $之间投影的交叠长度计算. 如图3(e)所示,$ {HE}_{{v}_{1}} $在合并边$ {HE}_{{v}_{2}} $上的投影为线段AB,线段AB的长度即为边的容量$ cap({e}_{ij}) $.
2)若$ {HE}_{{v}_{i}} $和$ {HE}_{{v}_{j}} $相互垂直,则有:
$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $之间若不存在交叉关系,则它们之间不能构造边. 图4(a)所示,走线在穿过$ {HE}_{{v}_{1}} $和$ {HE}_{{v}_{2}} $的过程中,必然会经过其他顶点对应的合并边(图4(a)未直接画出),因此顶点$ {v}_{1}^{\mathrm{u}\mathrm{p}} $和$ {v}_{2}^{\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t}} $之间无法构造边.
$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $之间若存在障碍物则不能构造边,示意图如图4(b)所示.
$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $之间若相交,则交叉点将线段$ {HE}_{{v}_{i}} $及$ {HE}_{{v}_{j}} $分割为4个部分,分别记做$ {HE}_{{v}_{i1}} $,$ {HE}_{{v}_{i2}} $以及$ {HE}_{{v}_{j1}} $,$ {HE}_{{v}_{j2}} $. 每条走线每次有且只能通过其中2条线段所围成的区域. 不失一般性,不妨设走线可能通过的其中2条线段为$ {HE}_{{v}_{i1}} $以及$ {HE}_{{v}_{j1}} $. 边的容量$ cap({e}_{ij}) $按$ {HE}_{{v}_{i1}} $和$ {HE}_{{v}_{j1}} $长度的最小值计算. 如图4(c)所示,交叉点D将线段AA′以及线段BB′分割为AD,DA′,BD,DB′,根据合并边所允许走线的通过方向不难得出,走线将会自上往下穿过线段AD继而从左向右穿过线段DB′,此时便能够得到边的容量$ cap({e}_{ij}) $即是线段AD以及线段DB′两者长度中的较小者.
为了有效缩减问题规模,算法在实际构造边时进行了一定简化. 首先根据起始点及终点器件的坐标分布,确定整体布线方向. 以整体布线方向从左到右为例,在实际构造带权有向图时可以省略构造表示,允许走线从右往左穿过的合并边的顶点. 其他方向同理.
为了实现群组布线的聚集效果,在自动布线流程中引入了一种自动生成引导线的方法. 所谓的引导线是一条曲线,在实际布线过程中,算法希望所有走线的路径都能够尽可能地贴近引导线. 在通常的PCB设计中,起始点及终点都是相互分离的. 因此,可以计算所有器件起始和终点引脚中心点的均值坐标,如下所示:
$ X=\dfrac{1}{n}{\displaystyle\sum\limits_{i=1}^{n}{x}_{i}} , $
$ Y=\dfrac{1}{n}{\displaystyle\sum\limits_{i=1}^{n}{y}_{i}}. $
然后,便能够利用这2个坐标确定一条引导线. 如图5(a)所示,算法在双端线网的2个引脚之间创建了一条引导线,它是连接2个引脚中心的一条直线.
对于合并边的权重,做出如下规定:1)与引导线相交的合并边的权重规定为0,以图5(b)为例,合并边$ {HE}_{v2} $,$ {HE}_{v3} $,$ {HE}_{v5} $,$ {HE}_{v6} $,$ {HE}_{v7} $的权重I2,I3,I5,I6,I7均被设置为0;2)若合并边与引导线不存在交点,如图5(b)中的I1,I4,则计算它们之间的最小距离,且如果这一最小距离大于设置的阈值T,则将该合并边视作障碍物,这将有效加速之后进行的搜索过程. 由此,如果算法能够在顶点$ {{v}_{i}}^{{d}{i}{r}_{i}} $与$ {{v}_{j}}^{{d}{i}{r}_{j}} $与之间构造边$ {e}_{ij} $,则令边$ {e}_{ij} $的权重$ weight({e}_{ij}) $为合并边$ {HE}_{vi} $和$ {HE}_{vj} $的权重之和.
为了能够让群组布线的结果灵活适应各种复杂的工业化需求,达到人工预期的良好效果,算法同样支持人工指定引导线. 由于人工指定的引导线通常是一条曲线,因此,实际处理时算法需要根据一定的精度,首先对引导线进行采样,将其转换为多段首尾相接的线段. 如图5(c)所示,引导线通过采样,被重新转换为线段AB,BC,CD,DE,EF. 线段化后的引导线的处理方式与自动生成的引导线的处理方式相同.
最后,算法得到了所有顶点构成的集合$ V\left(G\right) $、所有边构成的集合$ E\left(G\right) $、所有边的容量以及所有边的权值. 这样,算法便得到了基于合并边的带权有向图$ G $.
图6展示了在某个简化的局部,完整的带权有向图$ G $的构造结果. 图6(a)中,合并边l1,l2,l3按照规则可以被抽象为图6(b)所示的带权有向图$ G $,其中带权有向边的容量和权重没有具体给出.
这一阶段算法将会利用启发式的搜索算法,从图$ G $中逐线逐网地寻找连接起点与终点的迹.
首先算法将环绕在起始器件周围,且走线必然穿过的一条合并边标记为起始顶点,同理,算法将环绕在结束器件周围,且走线必然穿过的一条合并边标记为结束顶点. 接着,算法将起始顶点的权重设置为0,在图$ G $中以A*搜索的方式不断试探寻找下一顶点,直到寻找到结束顶点为止. 然后,算法对顶点序列进行逆序,从而得到有效的顶点序列. 最后,算法根据有效的顶点序列以及2个顶点确定图中一条有向边的原则,得到有效的边序列. 在A*搜索的过程中,算法如下设置权重:
$ F\left(n\right)=aG\left(n\right)+bH\left(n\right)+c\times weight\left(e\right) , $
其中$ F\left(n\right) $是A*搜索算法的总体代价,$ G\left(n\right) $是从起始顶点到当前位置的实际路径开销[30]. $ { weight }(e) $是边权重,表示从上一个顶点到当前搜索顶点的边的权重. $ a $,$ b $,$ c $是常数,算法可以通过改变$ a $,$ b $,$ c $的值从而强调不同的引导效果. ${G}\left(n\right) $可以通过下列递推式计算得到:
$ {G\left(n\right)}_{i}={G\left(n\right)}_{i-1}+{cost}_{i} , $
其中$ {G\left(n\right)}_{i} $表示第1到第$ i $段规划路径的实际开销,$ {cost}_{i} $表示第$ i $段规划路径的实际开销. $ {cost}_{i} $在实际计算中被设置为第$ i-1 $段规划路径的终点与当前搜索到的顶点所对应合并边中点的连线长度.
H(n)是估价函数,它是一种启发式函数,表示了从当前位置到终点的预估距离. 对于预估距离的计算,通常会使用曼哈顿距离或是欧几里得距离. 设起点为$ s({x}_{1},{y}_{1}) $,终点为$ t({x}_{2},{y}_{2}) $,则曼哈顿距离的定义为:
$ {dist}_{\rm Manhattan}\left(s,t\right)=\left|{x}_{1}-{x}_{2}\right|+|{y}_{1}-{y}_{2}| . $
欧几里得距离的定义为:
$ {dist}_{\rm Manhattan}\left(s,t\right)={({x}_{1}-{x}_{2})}^{2}+{({y}_{1}-{y}_{2})}^{2}. $
为加速计算过程,算法选用曼哈顿距离进行计算. 在实际计算中,$ H(n) $由当前顶点所对应合并边的中点到结束顶点的曼哈顿距离得到.
算法2给出了与数据结构相适配的A*搜索算法,算法从起点开始,不断地搜索出open列表中$ F $值最大的顶点,直到达到终点,然后通过回溯得到有效的顶点序列,继而通过2点确定一条边的方式确定有效的边序列.
算法2. A*搜索算法.
输入:图$ G $,起始顶点Vstart,结束顶点Vend;
输出:由一系列不重复的边组成的集合所表示的一条迹W.
① 设最小优先队列QOPEN=$\varnothing $,QCLOSE=$\varnothing $,搜索过程 中拜访过的顶点及其前继顶点的集合 Vvisited=$\varnothing $,有效的顶点集合$ V=\varnothing $;
② QOPEN. push(〈0,Vstart〉);
③ while QOPEN ≠ $\varnothing $
④ 选择${F} $值Fnext最小的F同时需要满足与加入的  上一组序列间没有障碍物,cap(enext) 大于线  宽与线间距之和的顶点$V_{\rm next}\in $QOPEN, QCLOSE.   push(〈Fnext,Vnext〉);
⑤   Vvisited←Vvisited∪{Vnext→Vcur};
⑥  if Vnext=Vend then
⑦   while Vnext≠Vstart
⑧     V←V∪Vnext;
⑨    根据Vnext搜索Vvisited得到Vcur=Vnext→ Vcur;
⑩     Vnext=Vcur;
⑪   end while
⑫  end if
⑬  将$ V $逆序存放$ { reverse (V) } $;
⑭  设vi=Vstart;
⑮  for $v \in V $
⑯   if v≠Vstart
⑰    设$ {v}_{i}=v $;
⑱    根据$ {v}_{i} $,$ {v}_{j} $搜索$ G $得到边$ {E}_{ij} $;
⑲     $ W\leftarrow W\cup {E}_{ij} $,$ {v}_{i}{=v}_{j} $;
⑳    return W,找到有效路径序列;
㉑   else
㉒    计算顶点Vnext的所有邻接节点 negis(Vnext)的$ F $;
㉓  end if
㉔  for $neig \in neigs $
㉕     QOPEN←QOPEN.push(〈neig,Fneig〉);
㉖   end for
㉗  end for
㉘ end while
㉙ return 未找到的有效路径序列.
在结束一次路径搜索后,需要对得到的边序列中所包含的每条边的容量进行更新. 在对所有起始顶点重复上述搜索过程后,便能得到所有线网的有效路径规划顶点序列以及有效路径规划边序列,它们分别代表了走线将会穿过的合并边的序列以及这些合并边之间的位置关系.
这一阶段算法对路径规划得到的顶点序列以及边序列,通过限制关系在各个顶点所对应的合并边上进行取点,得到的点集就是路径规划.
除开始顶点以及结束顶点以外,算法每次取出与当前顶点邻接的前后2条边. 由于带权有向图$ G $中的每条边由2个顶点确定,而每个顶点则对应了构图中的1条实际合并边,因此,实际上算法每次取出的是构图中的3条合并边,而它们之间的位置关系对取点位置有不同限制.
现对取点时存在的几种限制关系进行讨论. 如图7所示,假设布线整体方向为从左向右,显然3条合并边之间存在相互平行、前2条边平行而当前边与后一条边垂直、前2条边垂直而当前边与后一条边平行、当前边与前后2条边都垂直4种情况. 图7(a)展示的是3条合并边相互平行的情况,算法需要在边序列中向后寻找一条与它们相互垂直的合并边. 设curredgestart.x为当前合并边起点的横坐标,curredgeend.x为当前合并边终点的横坐标,$ crossedge.x $为位于序列之后,且与当前合并边相互垂直的第1条合并边的横坐标,$ \mathrm{m}\mathrm{i}\mathrm{n} $定义为取括号内两者的最小值. 则取点范围为
$ {P}_{\rm range}=[{curredge}_{\rm start}.x,\mathrm{m}\mathrm{i}\mathrm{n}({curredge}_{\rm end}.x, crossedge.x\left)\right]. $
图7(b)展示的是前2条边平行且当前边与后一条边垂直的情况. 设$ nextedge.x $为下一条合并边的横坐标,在这种情况下,此时的取点范围为
$ {P}_{\rm range}=[{curredge}_{\rm start}.x,\mathrm{m}\mathrm{i}\mathrm{n}({curredge}_{\rm end}.x, nextedge.x\left)\right]. $
图7(c)展示的是前2条边垂直而当前边与后一条边平行的情况. 设$ preedge.x $为上一条合并边的横坐标,$ \mathrm{m}\mathrm{a}\mathrm{x} $定义为取括号内两者的最大值,在这种情况下,此时的取点范围为.
$ {P}_{\rm range}=[\mathrm{max}\left(preedge.x,{curredge}_{\rm start}.x\right) ,{curredge}_{\rm end}.x] . $
图7(d)展示的是当前边与前后2条边都垂直的情况. 在这种情况下,此时的取点范围为
$ \begin{split}{P}_{\rm range}=\;&[\mathrm{max}\left(preedge.x,{curredge}_{\rm start}.x\right) ,\\&\mathrm{min}\left({curredge}_{\rm end}.x,nextedge.x\right)] .\end{split} $
以布线整体方向从左向右为例,若上一个取点在当前合并边上的投影点落在所允许的取点范围之内,那么优先将其作为选点. 如图8所示,根据这一原则,在合并边$ H E_{2} $上,算法选择点$ {v}_{1} $的投影点$ v_{2} $作为选点. 如果此时的取点范围包括了边界,则考虑在边界的另一端进行取点. 若以上条件均不满足,则算法需要在相对于走线穿过的方向及合并边上所允许的取点范围之内尽量靠右的位置进行取点,间隔一个线宽与线间距之和的距离,以最大限度地减少布线空间的浪费. 实际判断取点位置是否为布线方向右侧时,算法首先将布线方向分为东、南、西、北、东南、西南、东北、西北8个方向,以图9为例,当前布线穿过方向显然为东北,此时以斜率为1且朝向x,y轴正半轴的方向向量dir表示. 然后,在合并边AB上取中点M,然后分别取中点M到2端点A,B的方向向量,分别记做MA以及MB. 现在分别计算叉积dot1以及dot2:
$ {\boldsymbol{d}\boldsymbol{o}\boldsymbol{t}}_{1}=\boldsymbol{d}\boldsymbol{i}\boldsymbol{r}\times \boldsymbol{M}\boldsymbol{A} \text{,} $
$ {\boldsymbol{d}\boldsymbol{o}\boldsymbol{t}}_{2}=\boldsymbol{d}\boldsymbol{i}\boldsymbol{r}\times \boldsymbol{M}\boldsymbol{B} . $
接着判断叉积dot1, dot2的正负,若叉积为正,则向量之间的夹角为顺时针,若叉积为负,则为逆时针. 算法规定与dir之间夹角呈顺时针的向量所指向的方向为布线方向的右侧. 显然图9中MB方向为布线方向的右侧.
以图8为例,根据这一原则,在合并边$ H E_{3} $上,算法将取点范围内尽量靠近右侧的点$ v_{3} $作为选点. 考虑到同一条合并边可能会被多条走线穿过,所以算法在每次取点时都必须与上一条穿过该合并边的走线的取点保持一个线宽与线间距之和的距离. 重复上述过程,算法便能够得到所有线网的路径规划序列,这些序列以点集的形式予以表示.
路径规划阶段得到了所有线网完整的路径规划序列,但是这样的路径规划的直接连线结果违反了DRC. 以图8为例,此时路径规划后的走线角度并非135°. 因此,算法需要在此基础上进行详细布线,以得到最终满足DRC的布线结果.
算法每次所要处理的是路径规划序列中的一条线段,显然这一条线段是由2个点确定的. 算法将需要详细布线的一条线段的起点定义为入点,而相应的终点则定义为出点.
为了缩减问题规模,算法将详细布线所面临的场景分为了2种最为基本的情形:2条合并边之间相互平行以及2条合并边之间相互垂直,不妨设此时的路径规划线段走向为自左向右. 对于2条合并边之间相互平行的情形又可细分为2种情况:一是入点与出点的纵坐标相同(如图8中的点$ {v}_{1} $,$ v_{2} $). 此时不做任何调整,直接进入下一条线段的详细布线环节. 二是入点与出点的纵坐标不同(如图8中的点$ v_{8} $,$ v_{9} $). 对于这类情况,算法首先利用入点与出点的坐标信息构造布线矩形区域,该矩形区域需要恰好包含这2个点. 由于先前构造带权有向图时对连边之间存在障碍物的情形进行了限制,因此,该矩形区域内不可能存在任何障碍物. 然后,算法在矩形区域内进行详细布线. 详细布线时遵循面积最小原则,即出点顺时针沿着矩形边界到达入点所走过的路径,以及经由详细布线后所得到的线段,它们之间所围成的多边形面积必须尽可能小. 显然,算法需要让转折的长度尽可能小,在考虑到DRC中的最小线长限制后,让转折的长度取最小线宽即可.
对于2条合并边之间相互垂直的情形,不失一般性的,设此时的路径规划线段走向为自左向上(如图8中的点$ v_{2} $,$ v_{3} $). 对于这类情况,处理方法与2条合并边之间相互平行且入点与出点纵坐标不同的情况类似.
布线完成后检查起点线段与上一条线段的终点线段之间是否垂直,若是,则在起点线段开始处增加一转折,转折的长度同样取最小线宽即可.
对于其他走向的路径规划线段,算法在参照上述处理方法的同时进行相应的坐标变换即可. 在对所有路径规划线段应用详细布线算法后,便能够得到完整的符合DRC的详细布线结果.
算法使用C++作为编程语言进行实现. 所有实验都在配备了Intel® Xeon® Platinum 8260 CPU @ 2.40 GHz和128 GB内存的单台服务器上进行. 表1展示了来自于工业界的基准用例. 其中PCB5在PCB4的基础上将线网划分为2个群组. PCB9仅用于测试分层效果.
群组布线的布线质量可以通过采用一些评价指标进行评价. 群组布线的布线代价的计算方法由式(13)给出:
$ \mathcal{C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}=\alpha \mathcal{C}_{WL}+\beta \mathcal{C}_{S}+\gamma \mathcal{C}_{C} . $
总体布线代价${\mathcal C_{{\text{total}}}}$由3个部分加权求和得到,在不考虑DRC的情况下,${\mathcal C_{{\text{total}}}}$的值越小则说明群组布线的布线效果越好. $ \alpha $,$ \beta $,$ \gamma $表示权重,均可取1,所有群组的线长相似性代价${\mathcal C_{WL}}$、线段数代价${\mathcal C_S}$、紧凑性代价${\mathcal C_C}$的计算式的计算方法分别由式(14)~(16)所示.
$ {\mathcal C}_{WL}=\dfrac{1}{n}{\displaystyle\sum\limits_{i=1}^{n}\frac{\mathrm{m}\mathrm{a}\mathrm{x}({WL}_{W}^{i})}{\mathrm{m}\mathrm{i}\mathrm{n}({WL}_{W}^{i})}} , $
$ {\mathcal C}_{S}=\dfrac{1}{n}{\displaystyle\sum\limits_{i=1}^{n}\frac{\max({N}_{S}^{i})}{\min({N}_{S}^{i})}} , $
$ {\mathcal C}_{C}=\dfrac{1}{n}{\displaystyle\sum\limits_{i=1}^{n}\frac{\mathrm{m}\mathrm{i}\mathrm{n}({W}_{S}^{i})}{{\hat{W}}_{S}}} , $
其中$ {\mathcal C}_{WL} $由每个群组$ i $的单独相似性代价累加得到,$ n $则代表了当前布线输入的群组数. $ {\rm max} (WL_{W}^{i}) $表示群组$ i $中线长最长的线网的线长,$ \mathrm{m}\mathrm{i}\mathrm{n}({WL}_{W}^{i}) $表示群组$ i $中线长最短的线网的线长. $ {\mathcal C}_{WL} $的值越小则所有群组线网的整体布线线长越接近. $ \text{max}({N}_{S}^{i}) $表示群组$ i $中所包含的线段的数量最多的线网的段数,$ \min({N}_{S}^{i}) $表示群组$ i $中的段数下界,取群组$ i $中所有线网段数最小值即可. $ {\mathcal C}_{S} $的值越小则布线的拓扑相似性越高. $ \text{m}\mathrm{i}\mathrm{n}({W}_{S}^{i}) $表示群组$ i $中线段S所占据的宽度的最小值,计算$ {W}_{S} $时需要分别计算群组$ i $中最外层的2个线网与线段$S $的最小距离,两者中的较小者即为$ \mathrm{m}\mathrm{i}\mathrm{n}({W}_{S}^{i}) $. $ {\hat{W}}_{S} $则取线网的线宽与线间距之和. $ {\mathcal C}_{C} $的值越小则布线的汇聚程度越高,而更高的汇聚程度能够有效地节约布线空间,从而尽可能减少给后续布线带来的困难.
将本文算法与2个最先进的布线器FreeRouting以及Cadance Allegro进行比较.2个布线器都使用了默认设置,并在实验中应用了相同的设计输入以及DRC. 而本文算法采用的是默认生成引导线的模式. 本文选择了组件之间相互远离的基准用例,以便清楚地展示布线结果. 通过比较3款布线器的布通率(正确地完成布线的线网占总线网数的比率[31])、运行时间和违反设计规则(design rule violation,DRV)的次数总结了实验结果. 如表2所示,本文算法在布通率、运行时间和DRV次数方面优于FreeRouting和Cadance Allegro. 值得注意的是,本文算法以及Cadance Allegro可以完成总线或群组布线,而FreeRouting只能完成单线布线. 此外,Cadance Allegro以及FreeRouting无法在实际布线前进行相应的路径规划,这往往会导致一系列拥塞问题,继而在布线过程中需要频繁地进行拆线重布,这造成了大量的时间浪费. 更糟糕的是,FreeRouting在一些布线发生拥塞的情况下会尝试设置过孔,从而进行跨层布线,这种做法将会使PCB板层数增加,从而导致制造成本与制造难度大大增加.
表3通过使用式(14)~(16)对3款布线器的布线性能指标进行比较. 其中式(13)中α,β,γ的取值均为1,它们分别代表了群组布线同一群组中所有线网的布线线长尽量相近、所有线网的布线尽量汇聚以及所有线网的布线拓扑尽量相似的需求. 表3中$ {\mathcal C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $表示总体布线代价,$ {\mathcal C}_{WL} $,$ {\mathcal C}_{S} $,$ {\mathcal C}_{C} $和${\mathcal C}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} $这些指标的值越小则布线效果越好. 如表3所示,在线长相似性代价方面,由于FreeRouting是以单线布线的布线结果进行对比的,不具备聚集布线的能力,因此通常来说它的线长相似性最好,而Cadance Allegro在自动布线阶段采取的是聚集布线策略,这种策略在进行切角处理后往往会占据大量的布线空间,且在面对复杂例子时难以达到100%的布通率. 本文算法在某些例子上没有达到最佳的线长相似性,但也在可接受的范围内. 在线段数代价方面本文算法较优,这也意味着本文算法具有较好的布线拓扑相似性. 在紧凑性代价方面,本文算法以及Cadance Allegro在面对有障碍物布线时都能保持最优,这也就意味着相邻线网之间都能保持最小线间距,而不具备聚集布线能力的FreeRouting在该指标上与本文算法以及Cadance Allegro有着较大差距. 本文算法在总体布线代价方面优于FreeRouting和Cadance Allegro,这就意味着,总体而言,本文算法对于群组布线问题有着更佳的效果.
图10、图11显示了使用本文算法在PCB4上的布线结果,能够清晰地展示本文算法的优势. 本文算法将PCB板上的过孔、焊盘等视作障碍物. 图10中,本文算法将式(3)中的权重weight(e)设置为0,从而屏蔽了引导线的功能,此时群组走线退化为单线布线. 图11中,本文算法将式(3)中的权重weight(e)设置为100,从而强调了引导线的引导效果. 此时算法在左侧从上到下第5个焊盘与第6个焊盘中间出发,到右侧从上到下第5个焊盘与第6个焊盘中间中止,自动生成了1条引导线,并在参数设置时强调了引导线的引导作用,这将对这10根线网的路径规划产生汇聚作用,从而满足群组布线的要求. 图12则显示了本文算法在复杂例子上的布线结果. 图13显示的是预先分配各引脚的层后,实施群组布线的布线效果,其中左边第1,2行矩形焊盘(红色)与第3行矩形焊盘(蓝色)分别位于不同层,走线未发生交叉. 实验结果表明,本文算法对于PCB设计的群组布线任务是适用且高效的.
本文提出了一种用于PCB设计的群组布线算法,该算法考虑了PCB设计中的DRC.算法利用构造带权有向图的方式实现了群组布线问题的数学建模,在有效表示电路板上的布线资源的同时避免了传统网格方法易受网格精度以及网格数量限制的缺陷. 此外,本文算法采用具有多线避让功能的启发式搜索算法,且支持人工指定引导线以引导布线方向,在有效降低时间开销的同时保证了布线质量. 最后,提出了一种简洁有效且与本文提出的路径规划算法相适配的群组布线方案. 与FreeRouting和Cadance Allegro相比,实验结果显示了本文算法的优越性.
作者贡献声明:邓新国负责方案设计和论文的撰写以及修改;张鑫泓负责完成实验、数据分析和论文的撰写以及修改;陈家瑞负责方案设计并修改论文;刘清海提出方案的概念和证明思路;陈传东提出指导意见并修改论文.

参考文献 引证文献
排序方式:
1
Hsu J, Hung G, Tseng J, et al. High-speed data center PCB design challenges and findings by Intel® automatic in-board characterization[C/OL]//Proc of the 17th Int Microsystems, Packaging, Assembly and Circuits Technology Conf. Piscataway, NJ: IEEE, 2022[2024-04-08]. https://ieeexplore.ieee.org/document/9966724
2
Tan Yan. Algorithmic studies on PCB routing[D]. Urbana-Champaign: University of Illinois at Urbana-Champaign, 2010
3
Lin S T, Wang H H, Kuo C Y, et al. A complete PCB routing methodology with concurrent hierarchical routing[C]//Proc of the 58th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2021: 1141−1146
4
Lin T C, Merrill D, Wu Y Y, et al. A unified printed circuit board routing algorithm with complicated constraints and differential pairs[C]//Proc of the 26th Asia and South Pacific Design Automation Conf. New York: ACM, 2021: 170−175
5
邓新国,叶似锦,陈家瑞,等. 结合改进A*算法与拆线重布的有序逃逸布线[J]. 电子与信息学报,2021,43(6):1609−1616
Deng Xinguo, Ye Sijin, Chen Jiarui, et al. Ordered escape routing combining improved A* algorithm with rip-up and reroute[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1609−1616 (in Chinese)
6
Save Y D, Rakhi R, Shambhulingayya N D, et al. Oscad: An open source EDA tool for circuit design, simulation, analysis and PCB design[C]//Proc of the 20th Int Conf on Electronics, Circuits, and Systems. Piscataway, NJ: IEEE, 2013: 851−854
7
Goyal P, Agrawal H, Paradiso J A, et al. BoardLab: PCB as an interface to EDA software[C]//Proc of the 26th Annual ACM Symp on the Djunct Publication of the User Interface Software and Technology. New York: ACM, 2013: 19−20
8
Wane S, Patton R, Gross N. Unification of instrumentation and EDA tooling platforms for enabling smart chip-package-PCB-probe arrays co-design solutions using advanced RFIC technologies[C/OL]//Proc of the 2018 IEEE Conf on Antenna Measurements & Applications (CAMA). Piscataway,NJ:IEEE,2018[2024-04-08]. https://ieeexplore.ieee.org/document/8530652
9
Sherwani N A. Algorithms for VLSI Physical Design Automation[M]. 3rd ed. Berlin: Springer, 2012
10
Fang S C, Chang K E, Feng W S, et al. Constrained via minimization with practical considerations for multi-layer VLSI/PCB routing problems[C]//Proc of the 28th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 1991: 60−65
11
Zhang Cong, Jin Huilin, Chen Jienan, et al. A hierarchy MCTS algorithm for the automated PCB routing[C]//Proc of the 16th Int Conf on Control & Automation. Piscataway, NJ: IEEE, 2020: 1366−1371
12
Kahng A B,Lienig J. 超大规模集成电路物理设计:从图分割到时序收敛[M]. 于永斌,冯策,徐宁,等,译. 2版. 北京:机械工业出版社,2024
Kahng A B, Lienig J. Software Engineering: A Practitioner's Approach[M]. Translated by Yu Yongbin, Feng Ce, Xu Ning, et al. 2nd ed. Beijing: China Machine Press, 2024 (in Chinese)
13
Kong Hui, Ma Qiang, Yan Tan, et al. An optimal algorithm for finding disjoint rectangles and its application to PCB routing[C]//Proc of the 47th Design Automation Conf. Piscataway, NJ: IEEE, 2010: 212−217
14
Zhang Jixin, Xu Ning, Liu Mingyu. FanoutNet: A neuralized PCB fanout automation method using deep reinforcement learning[C]//Proc of the 37th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2023: 8554−8561
15
He Youbiao, Li Hebi, Jin Tian, et al. Circuit routing using Monte Carlo tree search and deep reinforcement learning[C/OL]//Proc of the 2022 Int Symp on VLSI Design, Automation and Test. Piscataway, NJ: IEEE, 2022[2024-04-08]. https://ieeexplore.ieee.org/document/9768074
16
刘郭庆,钱宇华,张亚宇,等. 给定预算下基于相对熵置信区间的蒙特卡洛树搜索最优动作识别算法[J]. 计算机研究与发展,2023,60(8):1780−1794
Liu Guoqing, Qian Yuhua, Zhang Yayu, et al. Best action identification algorithm in Monte Carlo tree search based on relative entropy confidence interval with given budget[J]. Journal of Computer Research and Development, 2023, 60(8): 1780−1794 (in Chinese)
17
Goh Y, Jung D, Hwang G, et al. Consumer electronics product manufacturing time reduction and optimization using AI-based PCB and VLSI circuit designing[J]. IEEE Transactions on Consumer Electronics, 2023, 69(3): 240−249
18
Hung S C, Chen Hao, Sun Fankeng, et al. A DAG-based algorithm for obstacle-aware topology-matching on-track bus routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(3): 533−546
19
Chen Jingsong, Kuang Jian, Zhao Guowei, et al. PROS 2.0: A plug-in for routability optimization and routed wirelength estimation using deep learning[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 42(1): 164−177
20
Zhang H T, Fujita M, Cheng C K, et al. SAT-based on-track bus routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(4): 735−747
21
Chen Jingsong, Liu Jinwei, Chen Gengjie, et al. MARCH: Maze routing under a concurrent and hierarchical scheme for buses[C/OL]//Proc of the 56th Annual Design Automation Conf 2019. Piscataway, NJ: IEEE, 2019[2024-04-08]. https://ieeexplore.ieee.org/document/8807035
22
Kim D, Do S, Lee S Y, et al. Compact topology-aware bus routing for design regularity[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(8): 1744−1749
23
Cheng Yihao, Yu Taochun, Fang Shaoyun. Obstacle-avoiding length-matching bus routing considering nonuniform track resources[J]. IEEE Transactions on Very Large Scale Integration Systems, 2020, 28(8): 1881−1892
24
Yan Jintai, Chen Zhiwei. Obstacle-aware length-matching bus routing[C]//Proc of the 2011 Int Symp on Physical Design. New York: ACM, 2011: 61−68
Yan Jintai,Chen Zhiwei. Obstacle-aware length-matching bus routing[C]//Proc of the 2011 Int Symp on Physical Design. New York:ACM,2011:61−68
25
Yan Jintai. Single-layer obstacle-aware multiple-bus routing considering simultaneous escape length[J]. IEEE Transactions on Components, Packaging and Manufacturing Technology, 2022, 12(6): 902−915
26
Kong Hui, Yan Tan, Wong M D F. Automatic bus planner for dense PCBs[C]//Proc of the 46th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2009: 326−331
27
Wu Peici, Ma Qiang, Wong M D F. An ILP-based automatic bus planner for dense PCBs[C]//Proc of the 18th Asia and South Pacific Design Automation Conf. Piscataway, NJ: IEEE, 2013: 181−186
28
Tang Hao, Liu Genggeng, Chen Xiaohua, et al. A Survey on Steiner tree construction and global routing for VLSI design[J]. IEEE Access, 2020, 8: 68593-68622
Tang Hao,Liu Genggeng,Chen Xiaohua,et al. A Survey on Steiner tree construction and global routing for VLSI design[J]. IEEE Access,2020,8:68593-68622
29
Zachariasen M. A catalog of Hanan grid problems[J]. Networks, 2001, 38(2): 76−83
30
赵奇,赵阿群. 一种基于A*算法的多径寻由算法[J]. 电子与信息学报,2013,35(4):952−957
Zhao Qi, Zhao Aqun. A multi-path routing algorithm base on A* algorithm[J]. Journal of Electronics & Information Technology, 2013, 35(4): 952−957 (in Chinese)
31
马博宇,徐宁,吴皓莹,等. 面向柔性电路通道区的自动布线算法[J]. 计算机辅助设计与图形学学报,2022,34(8):1179−1185
Ma Boyu, Xu Ning, Wu Haoying, et al. Routing Algorithm for flexible printed circuit channel area[J]. Journal of Computer-Aided Design & Computer Graphics, 2022, 34(8): 1179−1185 (in Chinese)
2025年第62卷第8期
98
39
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202440069
  • 接收时间:2024-02-04
  • 首发时间:2026-11-10
  • 出版时间:2025-08-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2024-02-04
  • 修回日期:2025-02-07
  • 录用日期:2025-03-03
基金
作者信息
    1福州大学计算机与大数据学院 福州 350108
    2福州大学离散数学中心 福州 350108
    3中国福建光电信息科学与技术创新实验室 福州 350024
    4福州大学物理与信息工程学院 福州 350108

通讯作者:

陈家瑞()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202440069
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏