Article(id=1327010979310842848, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327010748263411889, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202331042, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1703433600000, receivedDateStr=2023-12-25, revisedDate=1723392000000, revisedDateStr=2024-08-12, acceptedDate=1725292800000, acceptedDateStr=2024-09-03, onlineDate=1794313672138, onlineDateStr=2026-11-10, pubDate=1743436800000, pubDateStr=2025-04-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794313672138, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794313672138, creator=13701087609, updateTime=1794313672138, updator=13701087609, issue=Issue{id=1327010748263411889, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='4', pageStart='821', pageEnd='1089', issueExtLink='null', onlineDate='null', pubDate='1743436800000', pubDateStr='2025-04-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313617052, creator='13701087609', updateTime=1794376751260, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275552727217083, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327010748263411889, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275552727217084, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327010748263411889, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=930, endPage=949, ext={EN=ArticleExt(id=1327010979692524513, articleId=1327010979310842848, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture, columnId=1327010913338634647, journalTitle=Journal of Computer Research and Development, columnName=Architecture, runingTitle=null, highlight=null, articleAbstract=

Ensuring deadlock-free data transmission in the network-on-chip (NoC) is a prerequisite for providing reliable communication services for multi-processor system-on-chip (MPSoC), directly determining the availability of NoC and even MPSoC. Existing general-purpose deadlock-free strategies are oriented to arbitrary topologies, making it challenging to utilize the features and advantages of a specific topology. Moreover, these strategies may even increase network latency, power consumption, and hardware complexity. In addition, due to significant differences in the regular network between routing-level and protocol-level deadlocks, existing solutions struggle to simultaneously address both types of deadlock issues, affecting MPSoC reliability. We propose a deadlock-free strategy with synchronous Hamiltonian rings based on the inherent Hamiltonian characteristics of the triplet-based many-core architecture (TriBA). This method uses the topology’s symmetric axes and Hamiltonian edge to allocate independent store-and-forward buffers for data transmission, preventing protocol-level deadlocks and improving data transfer speed. Additionally, we design a directional determination method for data transmission within the same buffer using cyclic linked-list technology. This method ensures data independence and synchronous forward transmission, eliminates routing-level deadlocks, and reduces data transfer latency. Based on optimizing redundant calculations in look-ahead routing algorithms, we propose a deadlock-free routing mechanism called Hamiltonian shortest path routing (HamSPR) based on a synchronous Hamiltonian ring. GEM5 simulation results show that, compared with existing solutions in the TriBA, HamSPR reduces average packet latency and power consumption in synthetic traffic patterns by 18.78%−65.40% and 6.94%−34.15%, respectively, while improving throughput by 8.00%−59.17%. In the PARSEC benchmark, HamSPR achieves maximum reductions of 16.51% in application runtime and 42.75% in average packet latency, respectively. Moreover, compared with 2D-Mesh, TriBA demonstrates an application performance improvement of 1%−10% in PARSEC benchmark.

, authors=Chunfeng Li1, Soliman Karim1, Weixing Ji2, Feng Shi1, *, authorsList=Chunfeng Li, Soliman Karim, Weixing Ji, Feng Shi, authorCompany=null, correspAuthors=Feng Shi, authorNote=

born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

, 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=1327010988542504972, articleId=1327010979310842848, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=基三众核架构中基于同步哈密顿环的无死锁策略, columnId=1325489904427344387, journalTitle=计算机研究与发展, columnName=体系结构, runingTitle=null, highlight=null, articleAbstract=

确保片上网络(network-on-chip,NoC)中的数据传输无死锁,是NoC为多处理器片上系统(multi-processor system-on-chip,MPSoC)提供可靠通信服务的前提,决定了NoC甚至MPSoC的可用性. 现有的通用防死锁策略难以发挥出特定拓扑结构的自身特点和优势,甚至可能会增加网络延迟、功耗以及硬件复杂性. 另外,由于路由级和协议级死锁存在显著差异,现有无死锁方案较难同时解决这2类死锁问题,影响了MPSoC的可靠性. 利用基三众核架构(triplet-based many-core architecture,TriBA)中拓扑结构自身具有的哈密顿特性提出了基于同步哈密顿环的无死锁策略,该策略依据拓扑结构自身的对称轴和哈密顿边对数据传输进行分类,预防了协议级死锁并提高了数据传输速度;同时使用循环链表技术判断同一缓冲区内数据同步传输方向,消除了路由级死锁并降低了数据传输延迟. 在优化前瞻路由算法基础上,设计了基于同步哈密顿环的无死锁路由机制HamSPR(Hamiltonian shortest path routing). GEM5仿真结果表明,与TriBA现有方法相比,HamSPR在合成流量下的平均数据包延迟和功耗分别降低了8.78% ~ 65.40% 和6.94% ~ 34.15%,吞吐量提高了8.00% ~ 59.17%;在PARSEC测试集下的应用运行时间和平均数据包延迟分别最高实现了16.51%和42.75%的降低. 与2D-Mesh架构相比,TriBA在PARSEC测试集下的应用性能实现了1% ~ 10%的提升.

, authors=李春峰1, KarimSoliman1, 计卫星2, 石峰1, *, authorsList=李春峰, KarimSoliman, 计卫星, 石峰, authorCompany=null, correspAuthors=石峰, authorNote=

1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

, correspAuthorsNote=
石峰()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=1rdPaix6OB0aRgWJvDE5ag==, magXml=Po8BnGLQ9hzx5z8iGMo/lQ==, pdfUrl=null, pdf=11CQQPKz9Od1O3BvXRRVdA==, pdfFileSize=2425989, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=fd2CND1SxbO+LYNtRD2JUA==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=TgzzOyU3cgqgL7rJHIxeqw==, mapNumber=null, fund=null)}, authors=[Author(id=1327010989096153108, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=lichunfeng@bit.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010989226176534, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989096153108, language=EN, stringName=Chunfeng Li, firstName=Chunfeng, middleName=null, lastName=Li, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, bio={"content":"

born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

"}, bioImg=null, bioContent=

born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010989314256919, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989096153108, 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北京理工大学计算机学院 北京 100081, bio={"img":"xzSDPmK717gFogwqTMt3sQ==","content":"

1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

"}, bioImg=xzSDPmK717gFogwqTMt3sQ==, bioContent=

1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)])]), Author(id=1327010989419114521, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=1327010989612052507, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989419114521, language=EN, stringName=Soliman Karim, firstName=Soliman, middleName=null, lastName=Karim, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, bio={"content":"

born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

"}, bioImg=null, bioContent=

born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010989784018972, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989419114521, language=CN, stringName=KarimSoliman, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1北京理工大学计算机学院 北京 100081, bio={"img":"iUCFvJSCybKtvAXpoQriuw==","content":"

1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

"}, bioImg=iUCFvJSCybKtvAXpoQriuw==, bioContent=

1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)])]), Author(id=1327010989968568350, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, orderNo=2, 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=1327010990102786080, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989968568350, language=EN, stringName=Weixing Ji, firstName=Weixing, middleName=null, lastName=Ji, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2School of Artificial Intelligence, Beijing Normal University, Beijing 100875, bio={"content":"

born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

"}, bioImg=null, bioContent=

born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010991809867809, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989968568350, language=CN, stringName=计卫星, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2北京师范大学人工智能学院 北京 100875, bio={"img":"6kChVRrTyqxqejhxSE+soQ==","content":"

1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

"}, bioImg=6kChVRrTyqxqejhxSE+soQ==, bioContent=

1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988966129680, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=2, ext=[AuthorCompanyExt(id=1327010988978712593, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988966129680, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Artificial Intelligence, Beijing Normal University, Beijing 100875), AuthorCompanyExt(id=1327010988991295506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988966129680, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2北京师范大学人工智能学院 北京 100875)])]), Author(id=1327010991952474148, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=bitsf@bit.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327010992099274790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010991952474148, language=EN, stringName=Feng Shi, firstName=Feng, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, bio={"content":"

born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

"}, bioImg=null, bioContent=

born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010992166383655, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010991952474148, 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北京理工大学计算机学院 北京 100081, bio={"img":"DDdSztygY05xuhrlLuBdcA==","content":"

1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

"}, bioImg=DDdSztygY05xuhrlLuBdcA==, bioContent=

1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)])])], keywords=[Keyword(id=1327010992313184296, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, orderNo=1, keyword=many-core processors), Keyword(id=1327010992422236201, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, orderNo=2, keyword=network-on-chip), Keyword(id=1327010992531288106, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, orderNo=3, keyword=triplet-based many-core architecture), Keyword(id=1327010992602591275, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, orderNo=4, keyword=Hamiltonian characteristics), Keyword(id=1327010992678088748, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, orderNo=5, keyword=routing algorithm), Keyword(id=1327010992749391917, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, orderNo=6, keyword=deadlock prevention), Keyword(id=1327010992816500782, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, orderNo=1, keyword=众核处理器), Keyword(id=1327010992900386863, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, orderNo=2, keyword=片上网络), Keyword(id=1327010992971690032, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, orderNo=3, keyword=基三众核架构), Keyword(id=1327010993042993201, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, orderNo=4, keyword=哈密顿特性), Keyword(id=1327010993164628018, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, orderNo=5, keyword=路由算法), Keyword(id=1327010993235931187, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, orderNo=6, keyword=死锁预防)], refs=[Reference(id=1327010998671749214, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Yazdanpanah F, Afsharmazayejani R. A systematic analysis of power saving techniques for wireless network-on-chip architectures[J]. Journal of Systems Architecture, 2022, 126: 102485, articleTitle=null, refAbstract=null), Reference(id=1327010998743052383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Della Vecchia G, Sanges C. A recursively scalable network VLSI implementation[J]. Future Generation Computer Systems, 1988, 4(3): 235−243, articleTitle=null, refAbstract=null), Reference(id=1327010998810161248, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=石峰,陈旭,尹飞,等. 基于 S3 变换的 TriBA-Net 最短路径路由机制[J]. 中国科学:信息科学,2018,48(1):100−114, articleTitle=null, refAbstract=null), Reference(id=1327010998881464417, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Feng, Chen Xu, Yin Fei, et al. A shortest path routing mechanism based on S3 for TriBA-Net[J]. SCIENTIA SINICA Informationis, 2018, 48(1): 100−114 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327010998948573282, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=张洋,王达,叶笑春,等. 众核处理器片上网络的层次化全局自适应路由机制[J]. 计算机研究与发展,2016,53(6):1211−1220, articleTitle=null, refAbstract=null), Reference(id=1327010999015682147, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Yang, Wang Da, Ye Xiaochun, et al. A global hierarchical adaptive routing mechanism in many-core processor network-on-chip[J]. Journal of Computer Research and Development, 2016, 53(6): 1211−1220 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327010999078596708, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Feng Yinxiao, Xiang Dong, Ma Kaisheng. Heterogeneous die-to-die interfaces: Enabling more flexible chiplet interconnection systems[C]//Proc of the 56th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2023: 930−943, articleTitle=null, refAbstract=null), Reference(id=1327011000747929701, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Bakhouya M, Suboh S, Gaber J, et al. Analytical performance comparison of 2D mesh, wk-recursive, and spidergon nocs [C/OL]//Proc of the 19th IEEE Int Symp on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). Piscataway, NJ: IEEE, 2010[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/5470784, articleTitle=null, refAbstract=null), Reference(id=1327011000840204391, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=石峰,魏增辉,王一拙,等. 一种多/众核架构TriBA-CMPs的布局布线方案tMesh:中国,CN107526894A[P]. 2017-12-29, articleTitle=null, refAbstract=null), Reference(id=1327011000924090472, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Feng, Wei Zenghui, Wang Yizhuo, et al. A layout and routing scheme named tMesh for a multi/many-core architecture TriBA-CMPs: China, CN107526894A[P]. 2017-12-29 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327011001075085417, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Braham C C, Ji Weixinga, Zhang Lingyu. The design and implementation of a hierarchical network on chip[J]. Procedia Engineering, 2012, 29: 2966−2974, articleTitle=null, refAbstract=null), Reference(id=1327011001226080362, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Feng Shi, Yang Zhang. Design and evaluation of low-latency and shortest-path routing algorithm for triplet-based hierarchical interconnection network[J]. Journal of Testing and Evaluation, 2013, 41(4): 541−550, articleTitle=null, refAbstract=null), Reference(id=1327011001452572779, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Khan HUR, Shi Feng, Ji Weixing, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29): 3363−3371, articleTitle=null, refAbstract=null), Reference(id=1327011001578401900, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Zuo, Zuo Qi, Li Jiaxin. Triplet-based topology for on-chip networks[J]. WSEAS Transactions on Computers, 2009, 8(3): 516−525, articleTitle=null, refAbstract=null), Reference(id=1327011001700036717, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Xue Licheng, Shi Feng, Ji Weixing. 3D floorplanning of low-power and area-efficient network-on-chip architecture[J]. Microprocessors and Microsystems, 2011, 35(5): 484−495, articleTitle=null, refAbstract=null), Reference(id=1327011001767145582, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Yang, Shi Feng, Zuo Qi, et al. Express router microarchitecture for triplet-based hierarchical interconnection network[C]//Proc of the 14th IEEE Int Conf on High Performance Computing and Communication & 9th IEEE Int Conf on Embedded Software and Systems. Piscataway, NJ: IEEE, 2012: 295−302, articleTitle=null, refAbstract=null), Reference(id=1327011001838448751, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Xiaojun, Shi Feng, Zhang Hong. KLSAT: An application mapping algorithm based on Kernighan–Lin partition and simulated annealing for a specific WK-recursive NoC architecture[C]//Proc of the 16th IFIP WG 10.3 Int Conf on Network and Parallel Computing. Berlin: Springer, 2019: 31−42, articleTitle=null, refAbstract=null), Reference(id=1327011001955889264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Hong, Wang Xiaojun. KGT: An application mapping algorithm based on Kernighan–Lin partition and genetic algorithm for WK-recursive NoC architecture[C]//Proc of the 17th Int Conf on Intelligent Computing Theories and Application (ICIC). Berlin: Springer, 2021: 86−101, articleTitle=null, refAbstract=null), Reference(id=1327011002098495601, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Shi Feng, Li Jiaxin, Bai Ziru. Performance of triplet-based interconnection strategy for multi-core on-chip processors[C]//Proc of the 11th IEEE Int Conf on High Performance Computing and Communications. Piscataway, NJ: IEEE, 2009: 163−170, articleTitle=null, refAbstract=null), Reference(id=1327011002266267762, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Wang Xiaojun, Shi Feng, Zhang Hong. A novel speedup evaluation for multicore architecture based topology of on-chip memory[C]//Proc of the 10th Int Symp on Parallel Architectures, Algorithms and Programming. Berlin: Springer, 2019: 35−47, articleTitle=null, refAbstract=null), Reference(id=1327011002434039923, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Feng Yinxiao, Xiang Dong, Ma Kaishen. A scalable methodology for designing efficient interconnection network of chiplets [C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1059−1071, articleTitle=null, refAbstract=null), Reference(id=1327011002543091828, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Kasan H, Kim J. VVQ: Virtualizing virtual channel for cost-efficient protocol deadlock avoidance[C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1072−1084, articleTitle=null, refAbstract=null), Reference(id=1327011002606006389, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Romanov A Y, Myachin N M, Lezhnev E V, et al. Ring-Split: Deadlock-free routing algorithm for circulant networks on chip[J]. Micromachines, 2023, 14(1): 141, articleTitle=null, refAbstract=null), Reference(id=1327011002668920950, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Kwauk G, Kang S, Kasan H, et al. Boomgate: Deadlock avoidance in non-minimal routing for high-radix networks[C]//Proc of the 2021 IEEE Int Sym on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2021: 696−708, articleTitle=null, refAbstract=null), Reference(id=1327011002727641207, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Flich J, Skeie T, Mejia A, et al. A survey and evaluation of topology-agnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(3): 405−425, articleTitle=null, refAbstract=null), Reference(id=1327011002803138680, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Wu Yibo, Wang Liang, Wang Xiaohang, et al. A deflection-based deadlock recovery framework to achieve high throughput for faulty NoCs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(10): 2170−2183, articleTitle=null, refAbstract=null), Reference(id=1327011002866053241, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=Razavi S, Sarbazi-Azad H. The triangular pyramid: Routing and topological properties[J]. Information Sciences, 2010, 180(11): 2328−2339, articleTitle=null, refAbstract=null), Reference(id=1327011002945745018, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Nengchung, Yen Chengpang, Chu Chihping. Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model[J]. Journal of Systems Architecture, 2005, 51(3): 165−183, articleTitle=null, refAbstract=null), Reference(id=1327011003046408315, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=El-Obaid A. Three-dimension Hamiltonian broadcast wormhole-routing[J]. International Journal of Computer Networks & Communications, 2015, 7(3): 31−46, articleTitle=null, refAbstract=null), Reference(id=1327011003105128572, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Xu, Shi Feng, Yin Fei, et al. An efficient distributed minimal routing algorithm for triplet-based WK-recursive network[C]//Proc of the 20th IEEE Int Conf on High Performance Computing and Communications; 16th IEEE Int Conf on Smart City; 4th IEEE Int Conf on Data Science and Systems (HPCC/SmartCity/DSS). Piscataway, NJ: IEEE, 2018: 547−554, articleTitle=null, refAbstract=null), Reference(id=1327011003159654525, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Fan Dongrui, Zhang Hao, Wang Da, et al. Godson-T: An efficient many-core processor exploring thread-level parallelism[J]. IEEE Micro, 2012, 32(2): 38−47, articleTitle=null, refAbstract=null), Reference(id=1327011003218374782, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Parasar M, Farrokhbakht H, Jerger N E, et al. DRAIN: Deadlock removal for arbitrary irregular networks[C]//Proc of the 2020 IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2020: 447−460, articleTitle=null, refAbstract=null), Reference(id=1327011003277095039, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Dally W J, Towles B P. Principles and Practices of Interconnection Networks[M]. Amsterdam: Elsevier, 2004, articleTitle=null, refAbstract=null), Reference(id=1327011003335815296, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Ramey C. Tile-GX100 manycore processor: Acceleration interfaces and architecture[C/OL]//Proc of the 23rd IEEE on Hot Chips Symp. Piscataway, NJ: IEEE, 2011[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/7477491, articleTitle=null, refAbstract=null), Reference(id=1327011003411312769, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=Wentzlaff D, Griffin P, Hoffmann H, et al. On-chip interconnection architecture of the tile processor[J]. IEEE Micro, 2007, 27(5): 15−31, articleTitle=null, refAbstract=null), Reference(id=1327011003470033026, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=Sodani A, Gramunt R, Corbal J, et al. Knights landing: Second-generation intel Xeon Phi product[J]. IEEE Micro, 2016, 36(2): 34−46, articleTitle=null, refAbstract=null), Reference(id=1327011003545530499, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Rahman R. Intel Xeon Phi Coprocessor Architecture and Tools: The Guide for Application Developers[M]. Berlin: Springer, 2013, articleTitle=null, refAbstract=null), Reference(id=1327011005210669188, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Qiao Baojun, Shi Feng, Ji Weixing. A new hierarchical interconnection network for multi-core processor[C]//Proc of the 2nd IEEE Conf on Industrial Electronics and Applications. Piscataway, NJ: IEEE, 2007: 246−250, articleTitle=null, refAbstract=null), Reference(id=1327011005302943877, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Zuo, Shi Feng. A shortest path routing algorithm in triplet-based network[J]. Transactions of Beijing Institute of Technology, 2009, 29(5): 410−414, articleTitle=null, refAbstract=null), Reference(id=1327011005378441350, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Yang, Shi Feng, Ji Weixing, et al. SPORT: A shortest path routing algorithm for triplet-based hierarchical interconnection[J]. Transactions of Beijing institute of Technology, 2013, 33(1): 57−61, articleTitle=null, refAbstract=null), Reference(id=1327011005445550215, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=Chen Xu, Shi Feng, Yin Fei, et al. A novel look-ahead routing algorithm based on graph theory for triplet-based network-on-chip router[J]. IEICE Electronics Express, 2018, 15(8): 1−12, articleTitle=null, refAbstract=null), Reference(id=1327011005512659080, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=39, rfOrder=41, authorNames=null, journalName=null, refType=null, unstructuredReference=石峰,阮生强,尹飞,等. 基于尖端子图分类传输数据的基三核间网络防死锁方法:中国,CN112698960B[P]. 2022-08-09, articleTitle=null, refAbstract=null), Reference(id=1327011005596545161, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=39, rfOrder=42, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Feng, Ruan Shenqiang, Yin Fei, et al. A deadlock prevention method for inter-core networks based on apex-subgraph classification for data transmission in triplet-based architecture: China, CN112698960B[P]. 2022-08-09 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327011005667848330, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=40, rfOrder=43, authorNames=null, journalName=null, refType=null, unstructuredReference=Tutte W T. Graph Theory[M]. Cambridge, UK: Cambridge University Press, 2001, articleTitle=null, refAbstract=null), Reference(id=1327011005739151499, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=41, rfOrder=44, authorNames=null, journalName=null, refType=null, unstructuredReference=Levine G N. The classification of deadlock prevention and avoidance is erroneous[J]. ACM SIGOPS Operating Systems Review, 2005, 39(2): 47−50, articleTitle=null, refAbstract=null), Reference(id=1327011005802066060, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=42, rfOrder=45, authorNames=null, journalName=null, refType=null, unstructuredReference=Binkert N, Beckmann B, Black G, et al. The GEM5 simulator[J]. ACM SIGARCH Computer Architecture News, 2011, 39(2): 1−7, articleTitle=null, refAbstract=null), Reference(id=1327011005877563533, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=43, rfOrder=46, authorNames=null, journalName=null, refType=null, unstructuredReference=Bharadwaj S, Yin J, Beckmann B, et al. Kite: A family of heterogeneous interposer topologies enabled via accurate interconnect modeling[C/OL]//Proc of the 57th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2020[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/9218539, articleTitle=null, refAbstract=null), Reference(id=1327011005953061006, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=44, rfOrder=47, authorNames=null, journalName=null, refType=null, unstructuredReference=Sun Cheng, Chen C H O, Kurian G, et al. DSENT―A tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling[C]//Proc of the 6th IEEE/ACM Int Symp on Networks-on-Chip. Piscataway, NJ: IEEE, 2012: 201−210, articleTitle=null, refAbstract=null), Reference(id=1327011006028558479, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=45, rfOrder=48, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhan Xusheng, Bao Yungang, Bienia C, et al. PARSEC3.0: A multicore benchmark suite with network stacks and SPLASH-2X[J]. ACM SIGARCH Computer Architecture News, 2017, 44(5): 1−16, articleTitle=null, refAbstract=null), Reference(id=1327011006095667344, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=46, rfOrder=49, authorNames=null, journalName=null, refType=null, unstructuredReference=Parasar M, Jerger N E, Gratz P V, et al. SWAP: Synchronized weaving of adjacent packets for network deadlock resolution[C]//Proc of the 52nd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2019: 873−885, articleTitle=null, refAbstract=null), Reference(id=1327011006187942033, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=47, rfOrder=50, authorNames=null, journalName=null, refType=null, unstructuredReference=Joshi B, Thakur M K. Genetic algorithm-and cuckoo search algorithm-based routing optimizations in network-on-chip[J]. Arabian Journal for Science and Engineering, 2023, 48(8): 9635−9644, articleTitle=null, refAbstract=null), Reference(id=1327011006271828114, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=48, rfOrder=51, authorNames=null, journalName=null, refType=null, unstructuredReference=Luo Yaoying, Meyer M C, Jiang Xin, et al. A hotspot-pattern-aware routing algorithm for networks-on-chip[C]//Proc of the 13th IEEE Int Symp on Embedded Multicore/Many-core Systems-on-Chip (MCSoC). Piscataway, NJ: IEEE, 2019: 229−235, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)]), AuthorCompany(id=1327010988966129680, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=2, ext=[AuthorCompanyExt(id=1327010988978712593, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988966129680, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Artificial Intelligence, Beijing Normal University, Beijing 100875), AuthorCompanyExt(id=1327010988991295506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988966129680, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2北京师范大学人工智能学院 北京 100875)])], figs=[ArticleFig(id=1327010993374343220, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 1, caption=Illustration of routing-level and protocol-level deadlocks generation in NoC, figureFileSmall=bPROxh5UN9k+U9Fc2/I6Zw==, figureFileBig=fd2CND1SxbO+LYNtRD2JUA==, tableContent=null), ArticleFig(id=1327010993433063477, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图1, caption=NoC中路由级和协议级死锁产生示意图, figureFileSmall=bPROxh5UN9k+U9Fc2/I6Zw==, figureFileBig=fd2CND1SxbO+LYNtRD2JUA==, tableContent=null), ArticleFig(id=1327010993621807158, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 2, caption=Illustration of deadlock-free strategy based on synchronized Hamiltonian rings, figureFileSmall=KNNk5uHwOao7etMNAxFIJA==, figureFileBig=gk9SQJVyyCZntgz4uL8DUg==, tableContent=null), ArticleFig(id=1327010993697304631, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图2, caption=基于同步哈密顿环的无死锁策略示意图, figureFileSmall=KNNk5uHwOao7etMNAxFIJA==, figureFileBig=gk9SQJVyyCZntgz4uL8DUg==, tableContent=null), ArticleFig(id=1327010993751830584, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 3, caption=Illustration of TriBA-NoC topology structure, figureFileSmall=0UmPx2MsWezeM4xni9ywsA==, figureFileBig=n7BWkR2PXaX59lwUed/9RA==, tableContent=null), ArticleFig(id=1327010993911214137, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图3, caption=TriBA-NoC的拓扑结构示意图, figureFileSmall=0UmPx2MsWezeM4xni9ywsA==, figureFileBig=n7BWkR2PXaX59lwUed/9RA==, tableContent=null), ArticleFig(id=1327010994099957818, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 4, caption=Illustration of layout and wiring for TriBA-NoC[7], figureFileSmall=f2+aLDr7oTEKQjQSNidobg==, figureFileBig=5DKqbnAMFJBs4oTdHK6tjQ==, tableContent=null), ArticleFig(id=1327010994188038203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图4, caption=TriBA-NoC的布局布线示意图[7], figureFileSmall=f2+aLDr7oTEKQjQSNidobg==, figureFileBig=5DKqbnAMFJBs4oTdHK6tjQ==, tableContent=null), ArticleFig(id=1327010994305478716, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 5, caption=Illustration of the different routing subgraphs in $ {TC}^{F} $, as well as the transmission modes and paths, figureFileSmall=xbV1ZQBUdPEDN2900JorQw==, figureFileBig=FYfn4Lik5u4ivNcPBF/4XQ==, tableContent=null), ArticleFig(id=1327010994431307837, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图5, caption= $ {TC}^{F} $中不同的路由子图及传输模式和路径示意图, figureFileSmall=xbV1ZQBUdPEDN2900JorQw==, figureFileBig=FYfn4Lik5u4ivNcPBF/4XQ==, tableContent=null), ArticleFig(id=1327010994527776830, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 6, caption=H-path between apex $ {1}^{F} $and $ {2}^{F} $ (taking $ TC^3 $ for example), figureFileSmall=Rr8L8ZfTumFSH5s/oEio/w==, figureFileBig=3YpccZcBI6HuXjs2pDxGyw==, tableContent=null), ArticleFig(id=1327010994590691391, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图6, caption= $ {TC}^{F} $尖端$ {1}^{F} $和$ {2}^{F} $之间的H-路径(以$ {TC}^{3} $为例), figureFileSmall=Rr8L8ZfTumFSH5s/oEio/w==, figureFileBig=3YpccZcBI6HuXjs2pDxGyw==, tableContent=null), ArticleFig(id=1327010996297773120, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 7, caption=H-cycle between apex of $ {TC}^{F} $ (taking $ TC^3 $ for example), figureFileSmall=Zq1LrHpzkeRiJPrct7A7QQ==, figureFileBig=6qmGVv0iPWGMww7jf4uNww==, tableContent=null), ArticleFig(id=1327010996390047809, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图7, caption= $ {TC}^{F} $尖端之间的哈密顿环(以$TC^{3} $为例), figureFileSmall=Zq1LrHpzkeRiJPrct7A7QQ==, figureFileBig=6qmGVv0iPWGMww7jf4uNww==, tableContent=null), ArticleFig(id=1327010996545237058, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 8, caption=Virtual Hamiltonian ring flow in $ {TC}^{3} $, figureFileSmall=D/1R2gw2l36WTphnLBnRLg==, figureFileBig=Od76TnNMomYvlFIJNJXqxg==, tableContent=null), ArticleFig(id=1327010996645900355, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图8, caption= $ {TC}^{3} $中的虚拟哈密顿环流, figureFileSmall=D/1R2gw2l36WTphnLBnRLg==, figureFileBig=Od76TnNMomYvlFIJNJXqxg==, tableContent=null), ArticleFig(id=1327010996708814916, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 9, caption=H-path betwee 1f and 2f in apex TCf and its associated symmetry axis, figureFileSmall=bzb3DNfoRMJVXnfpUoSudA==, figureFileBig=7/NiyFfnImV05i6wdX6OAw==, tableContent=null), ArticleFig(id=1327010996855615557, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图9, caption= $ {TC}^{f} $尖端$ {1}^{f} $和$ {2}^{f} $之间的$ \mathrm{H} $-路径及其相关对称轴, figureFileSmall=bzb3DNfoRMJVXnfpUoSudA==, figureFileBig=7/NiyFfnImV05i6wdX6OAw==, tableContent=null), ArticleFig(id=1327010996943695942, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 10, caption=Example of symmetry axis selection and maximum edge determination in a deadlock-free strategy based on synchronous Hamiltonian rings, figureFileSmall=Kll+yegeeIfMTA8UH36vIA==, figureFileBig=sCPx9Kz20b4gQeDlhsT3CA==, tableContent=null), ArticleFig(id=1327010996998221895, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图10, caption=基于同步哈密顿环的无死锁策略中对称轴选择和最大边判断示例, figureFileSmall=Kll+yegeeIfMTA8UH36vIA==, figureFileBig=sCPx9Kz20b4gQeDlhsT3CA==, tableContent=null), ArticleFig(id=1327010997073719368, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 11, caption=Block diagram of the pipeline hardware implementation for routing computation, figureFileSmall=SQw2WaBA6O9gbMPz2bpEzA==, figureFileBig=+IOORLxNKBL02igQtJJgVA==, tableContent=null), ArticleFig(id=1327010997145022537, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图11, caption=路由计算流水线硬件实现模块图, figureFileSmall=SQw2WaBA6O9gbMPz2bpEzA==, figureFileBig=+IOORLxNKBL02igQtJJgVA==, tableContent=null), ArticleFig(id=1327010997220520010, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 12, caption=Router microarchitecture implemented in GEM5 for HamSPR, figureFileSmall=Vfvf/xfvQ4XOpaxRlbAtCw==, figureFileBig=Qo1mxb6e9Omm4lqhFPL/GA==, tableContent=null), ArticleFig(id=1327010997300211787, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图12, caption=HamSPR在GEM5中路由器微架构的实现, figureFileSmall=Vfvf/xfvQ4XOpaxRlbAtCw==, figureFileBig=Qo1mxb6e9Omm4lqhFPL/GA==, tableContent=null), ArticleFig(id=1327010997384097868, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 13, caption=Average data packet latency and throughput of different routing algorithms in$ {TC}^{3} $under synthetic traffic patterns, figureFileSmall=8vswimSEXgisnyzlmK3oSg==, figureFileBig=F9bMKYqTFvEI8Kd5fSLTdA==, tableContent=null), ArticleFig(id=1327010997484761165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图13, caption= $ {TC}^{3} $中不同路由算法在合成流量模式下的平均数据包延迟和吞吐量, figureFileSmall=8vswimSEXgisnyzlmK3oSg==, figureFileBig=F9bMKYqTFvEI8Kd5fSLTdA==, tableContent=null), ArticleFig(id=1327010997560258638, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 14, caption=Normalized runtime and average data packet latency of different routing algorithms in $ {TC}^{3} $ under PARSEC applications, figureFileSmall=v3sFZwe4R7gfkwO91tD+1Q==, figureFileBig=J/t2m87RHXPEBsvgKWX7hA==, tableContent=null), ArticleFig(id=1327010997728030799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图14, caption= $ {TC}^{3} $中不同路由算法在PARSEC应用程序下的归一化运行时间和平均数据包延迟, figureFileSmall=v3sFZwe4R7gfkwO91tD+1Q==, figureFileBig=J/t2m87RHXPEBsvgKWX7hA==, tableContent=null), ArticleFig(id=1327010997782556752, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 15, caption=Average data packet hops of different routing algorithms in $ {TC}^{3} $ under PARSEC applications, figureFileSmall=WryKcQkxMzvwhPm40wiSLw==, figureFileBig=EUqVlz/StPvpCUjMwRJYwg==, tableContent=null), ArticleFig(id=1327010997853859921, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图15, caption= $ {TC}^{3} $中不同路由算法在PARSEC应用程序下的平均数据包跳数, figureFileSmall=WryKcQkxMzvwhPm40wiSLw==, figureFileBig=EUqVlz/StPvpCUjMwRJYwg==, tableContent=null), ArticleFig(id=1327010997912580179, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 16, caption=Runtime and average data packet latency of routing algorithms with different architectures under PARSEC applications, figureFileSmall=0m7OoRHJJQ+xgQuaL88L/g==, figureFileBig=GOIYwsSwkYDRVwJvtUAC7Q==, tableContent=null), ArticleFig(id=1327010997967106132, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图16, caption=不同架构的路由算法在PARSEC应用程序下的运行时间和平均数据包延迟, figureFileSmall=0m7OoRHJJQ+xgQuaL88L/g==, figureFileBig=GOIYwsSwkYDRVwJvtUAC7Q==, tableContent=null), ArticleFig(id=1327010998034214997, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Figure 17, caption=Normalized average data packet power consumption of different routing algorithms in $ {TC}^{3} $ under the synthetic traffic and PARSEC applications, figureFileSmall=m7yRkfVUgSYmgznNQ5icZA==, figureFileBig=KSi707LALqPOJdntmZ7n9Q==, tableContent=null), ArticleFig(id=1327010998109712470, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=图17, caption= $ {TC}^{3} $中不同路由算法在合成流量和PARSEC应用程序下的归一化平均数据包功耗, figureFileSmall=m7yRkfVUgSYmgznNQ5icZA==, figureFileBig=KSi707LALqPOJdntmZ7n9Q==, tableContent=null), ArticleFig(id=1327010998172627031, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Table 1, caption=Routing Solutions Schemes Under TriBA Architecture, figureFileSmall=null, figureFileBig=null, tableContent=
算法对比方法延迟
($ \downarrow $)
吞吐量
($ \uparrow $)
功耗
($ \downarrow $)
路由级
死锁
协议级
死锁
注:$ \downarrow $ 表示降低;$ \uparrow $ 表示提升;√ 表示满足;× 表示不满足.
Look-up Table[11]2D-Mesh√√×√×
DDRA[35]××
Min-DDRA[36]DDRA√××
DM4T[27]DDRA√√×√×
SPORT[37]DDRA和
Min-DDRA
√××
SPR4T[3]SPORT√√××
LA4T[38]DDRA和SPORT√√√×√
HamSPR(本文)SPR4T和LA4T√√√√√
), ArticleFig(id=1327010998235541592, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=表1, caption=

TriBA架构下的路由解决方案

, figureFileSmall=null, figureFileBig=null, tableContent=
算法对比方法延迟
($ \downarrow $)
吞吐量
($ \uparrow $)
功耗
($ \downarrow $)
路由级
死锁
协议级
死锁
注:$ \downarrow $ 表示降低;$ \uparrow $ 表示提升;√ 表示满足;× 表示不满足.
Look-up Table[11]2D-Mesh√√×√×
DDRA[35]××
Min-DDRA[36]DDRA√××
DM4T[27]DDRA√√×√×
SPORT[37]DDRA和
Min-DDRA
√××
SPR4T[3]SPORT√√××
LA4T[38]DDRA和SPORT√√√×√
HamSPR(本文)SPR4T和LA4T√√√√√
), ArticleFig(id=1327010998327816281, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Table 2, caption=Simulation Parameters in SE and FS Modes, figureFileSmall=null, figureFileBig=null, tableContent=
模式参数数值
SE节点数27
仿真和预热/周期40000,1000
虚拟网络和通道3,4
路由器延迟/周期4
线路延迟/周期1
死锁阈值/周期150
缓存一致性协议Garnet Standalone
数据包交换Wormhole
Flit大小/b128
SA分配策略Round-Robin
CPU频率/GHz1.0
FSISAx86
系统内核x86-Linux-kernel-4.19.83
CPU类型x86KVMCPU,2.0 GHz
L1 cachePrivate, 16 KB, 2-way associative,
64 B block size
L2 cacheShared, 2 MB, 8-way associative,
64 B block size
内存类型SimpleMemory,3 GB
缓存一致性协议MESI Two Level
基准测试集规模simsmall
), ArticleFig(id=1327010998399119450, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=表2, caption=

SE模式和FS模式下的仿真参数

, figureFileSmall=null, figureFileBig=null, tableContent=
模式参数数值
SE节点数27
仿真和预热/周期40000,1000
虚拟网络和通道3,4
路由器延迟/周期4
线路延迟/周期1
死锁阈值/周期150
缓存一致性协议Garnet Standalone
数据包交换Wormhole
Flit大小/b128
SA分配策略Round-Robin
CPU频率/GHz1.0
FSISAx86
系统内核x86-Linux-kernel-4.19.83
CPU类型x86KVMCPU,2.0 GHz
L1 cachePrivate, 16 KB, 2-way associative,
64 B block size
L2 cacheShared, 2 MB, 8-way associative,
64 B block size
内存类型SimpleMemory,3 GB
缓存一致性协议MESI Two Level
基准测试集规模simsmall
), ArticleFig(id=1327010998483005531, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=EN, label=Table 3, caption=Performance Variation of HamSPR Compared with Other Algorithms with Different Network Scales, figureFileSmall=null, figureFileBig=null, tableContent=
网络规模平均数据包延迟降低/%吞吐量提升/%
TableSPR4TLA4TTableSPR4TLA4T
946.6743.8440.7527.2926.2921.21
2748.2845.7839.4627.3527.3519.69
8145.3543.9437.6425.8626.5618.74
24345.9542.9837.1726.0826.4419.22
方差1.20531.04222.06310.46620.16910.8597
), ArticleFig(id=1327010998571085917, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, language=CN, label=表3, caption=

HamSPR在不同网络规模下相比其他算法的性能差异

, figureFileSmall=null, figureFileBig=null, tableContent=
网络规模平均数据包延迟降低/%吞吐量提升/%
TableSPR4TLA4TTableSPR4TLA4T
946.6743.8440.7527.2926.2921.21
2748.2845.7839.4627.3527.3519.69
8145.3543.9437.6425.8626.5618.74
24345.9542.9837.1726.0826.4419.22
方差1.20531.04222.06310.46620.16910.8597
)], 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.202331042, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202331042, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202331042, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202331042, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1743436800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
基三众核架构中基于同步哈密顿环的无死锁策略
李春峰 1 , KarimSoliman 1 , 计卫星 2 , 石峰 1, *
计算机研究与发展 | 体系结构 2025,62(4): 930-949
收起
收藏切换
计算机研究与发展 |体系结构 2025 , 62 (4) : 930 -949
基三众核架构中基于同步哈密顿环的无死锁策略
全屏
[Author(id=1327010989096153108, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=lichunfeng@bit.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010989226176534, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989096153108, language=EN, stringName=Chunfeng Li, firstName=Chunfeng, middleName=null, lastName=Li, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, bio={"content":"

born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

"}, bioImg=null, bioContent=

born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010989314256919, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989096153108, 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北京理工大学计算机学院 北京 100081, bio={"img":"xzSDPmK717gFogwqTMt3sQ==","content":"

1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

"}, bioImg=xzSDPmK717gFogwqTMt3sQ==, bioContent=

1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)])]), Author(id=1327010989419114521, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, 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=1327010989612052507, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989419114521, language=EN, stringName=Soliman Karim, firstName=Soliman, middleName=null, lastName=Karim, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, bio={"content":"

born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

"}, bioImg=null, bioContent=

born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010989784018972, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989419114521, language=CN, stringName=KarimSoliman, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1北京理工大学计算机学院 北京 100081, bio={"img":"iUCFvJSCybKtvAXpoQriuw==","content":"

1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

"}, bioImg=iUCFvJSCybKtvAXpoQriuw==, bioContent=

1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)])]), Author(id=1327010989968568350, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, orderNo=2, 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=1327010990102786080, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989968568350, language=EN, stringName=Weixing Ji, firstName=Weixing, middleName=null, lastName=Ji, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2School of Artificial Intelligence, Beijing Normal University, Beijing 100875, bio={"content":"

born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

"}, bioImg=null, bioContent=

born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010991809867809, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010989968568350, language=CN, stringName=计卫星, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2北京师范大学人工智能学院 北京 100875, bio={"img":"6kChVRrTyqxqejhxSE+soQ==","content":"

1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

"}, bioImg=6kChVRrTyqxqejhxSE+soQ==, bioContent=

1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988966129680, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=2, ext=[AuthorCompanyExt(id=1327010988978712593, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988966129680, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Artificial Intelligence, Beijing Normal University, Beijing 100875), AuthorCompanyExt(id=1327010988991295506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988966129680, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2北京师范大学人工智能学院 北京 100875)])]), Author(id=1327010991952474148, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=bitsf@bit.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327010992099274790, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010991952474148, language=EN, stringName=Feng Shi, firstName=Feng, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, *, address=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, bio={"content":"

born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

"}, bioImg=null, bioContent=

born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010992166383655, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, authorId=1327010991952474148, 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北京理工大学计算机学院 北京 100081, bio={"img":"DDdSztygY05xuhrlLuBdcA==","content":"

1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

"}, bioImg=DDdSztygY05xuhrlLuBdcA==, bioContent=

1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327010988848689165, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, xref=1, ext=[AuthorCompanyExt(id=1327010988861272078, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081), AuthorCompanyExt(id=1327010988882243599, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010979310842848, companyId=1327010988848689165, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1北京理工大学计算机学院 北京 100081)])])]
李春峰1 , KarimSoliman1, 计卫星2, 石峰1, *
作者信息
  • 1北京理工大学计算机学院 北京 100081
  • 2北京师范大学人工智能学院 北京 100875
通讯作者:
石峰()
作者简介:

1995年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

1991年生. 博士研究生. CCF学生会员. 主要研究方向为计算机体系结构、高性能计算

1980年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为计算机体系结构、高性能计算、代码检测与分析

1961年生. 博士,教授,博士生导师. 主要研究方向为计算机体系结构、高性能计算

Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture
Chunfeng Li1 , Soliman Karim1, Weixing Ji2, Feng Shi1, *
Affiliations
  • 1School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081
  • 2School of Artificial Intelligence, Beijing Normal University, Beijing 100875
  • born in 1995. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

    born in 1991. PhD candidate. Student member of CCF. His main research interests include computer architecture and high-performance computing

    born in 1980. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include computer architecture, high-performance computing, and code detection and analysis

    born in 1961. PhD, professor, PhD supervisor. His main research interests include computer architecture and high-performance computing

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

确保片上网络(network-on-chip,NoC)中的数据传输无死锁,是NoC为多处理器片上系统(multi-processor system-on-chip,MPSoC)提供可靠通信服务的前提,决定了NoC甚至MPSoC的可用性. 现有的通用防死锁策略难以发挥出特定拓扑结构的自身特点和优势,甚至可能会增加网络延迟、功耗以及硬件复杂性. 另外,由于路由级和协议级死锁存在显著差异,现有无死锁方案较难同时解决这2类死锁问题,影响了MPSoC的可靠性. 利用基三众核架构(triplet-based many-core architecture,TriBA)中拓扑结构自身具有的哈密顿特性提出了基于同步哈密顿环的无死锁策略,该策略依据拓扑结构自身的对称轴和哈密顿边对数据传输进行分类,预防了协议级死锁并提高了数据传输速度;同时使用循环链表技术判断同一缓冲区内数据同步传输方向,消除了路由级死锁并降低了数据传输延迟. 在优化前瞻路由算法基础上,设计了基于同步哈密顿环的无死锁路由机制HamSPR(Hamiltonian shortest path routing). GEM5仿真结果表明,与TriBA现有方法相比,HamSPR在合成流量下的平均数据包延迟和功耗分别降低了8.78% ~ 65.40% 和6.94% ~ 34.15%,吞吐量提高了8.00% ~ 59.17%;在PARSEC测试集下的应用运行时间和平均数据包延迟分别最高实现了16.51%和42.75%的降低. 与2D-Mesh架构相比,TriBA在PARSEC测试集下的应用性能实现了1% ~ 10%的提升.

众核处理器  /  片上网络  /  基三众核架构  /  哈密顿特性  /  路由算法  /  死锁预防

Ensuring deadlock-free data transmission in the network-on-chip (NoC) is a prerequisite for providing reliable communication services for multi-processor system-on-chip (MPSoC), directly determining the availability of NoC and even MPSoC. Existing general-purpose deadlock-free strategies are oriented to arbitrary topologies, making it challenging to utilize the features and advantages of a specific topology. Moreover, these strategies may even increase network latency, power consumption, and hardware complexity. In addition, due to significant differences in the regular network between routing-level and protocol-level deadlocks, existing solutions struggle to simultaneously address both types of deadlock issues, affecting MPSoC reliability. We propose a deadlock-free strategy with synchronous Hamiltonian rings based on the inherent Hamiltonian characteristics of the triplet-based many-core architecture (TriBA). This method uses the topology’s symmetric axes and Hamiltonian edge to allocate independent store-and-forward buffers for data transmission, preventing protocol-level deadlocks and improving data transfer speed. Additionally, we design a directional determination method for data transmission within the same buffer using cyclic linked-list technology. This method ensures data independence and synchronous forward transmission, eliminates routing-level deadlocks, and reduces data transfer latency. Based on optimizing redundant calculations in look-ahead routing algorithms, we propose a deadlock-free routing mechanism called Hamiltonian shortest path routing (HamSPR) based on a synchronous Hamiltonian ring. GEM5 simulation results show that, compared with existing solutions in the TriBA, HamSPR reduces average packet latency and power consumption in synthetic traffic patterns by 18.78%−65.40% and 6.94%−34.15%, respectively, while improving throughput by 8.00%−59.17%. In the PARSEC benchmark, HamSPR achieves maximum reductions of 16.51% in application runtime and 42.75% in average packet latency, respectively. Moreover, compared with 2D-Mesh, TriBA demonstrates an application performance improvement of 1%−10% in PARSEC benchmark.

many-core processors  /  network-on-chip  /  triplet-based many-core architecture  /  Hamiltonian characteristics  /  routing algorithm  /  deadlock prevention
李春峰, KarimSoliman, 计卫星, 石峰. 基三众核架构中基于同步哈密顿环的无死锁策略. 计算机研究与发展, 2025 , 62 (4) : 930 -949 . DOI: 10.7544/issn1000-1239.202331042
Chunfeng Li, Soliman Karim, Weixing Ji, Feng Shi. Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture[J]. Journal of Computer Research and Development, 2025 , 62 (4) : 930 -949 . DOI: 10.7544/issn1000-1239.202331042
随着科学计算、人工智能以及数据挖掘等领域的快速发展,并行处理大规模计算任务的场景需求日益增加,这对现代多处理器片上系统(multi-processor system-on-chip,MPSoC)中的通信架构提出了严峻挑战. 设计无死锁、高性能、可扩展和模块化的片上通信架构成为提升MPSoC性能的重要手段[1]. 基三众核架构(triplet-based many-core architecture,TriBA)是一种以WKd,h(d代表度,h代表网络的级数)递归结构[2]作为核间互连拓扑的新型片上网络架构[3]. 与当前主流2D-Mesh架构[4-5]相比,基于WK3,F(F为层数)的TriBA具有更高的可扩展性[6]、独特的拓扑优势[3]和相似的Tile化布局布线方式[7]. 前期研究结果表明,TriBA在通信负载、吞吐量、网络延迟以及功耗等方面与2D-Mesh相比具有明显优势[8-16]. 另外,TriBA的片上内存网络相比于2D-Mesh架构具有更高的可扩展性[17]. 在相同的缓存命中率和网络规模下,其片上Cache加速比大约是2D-Mesh的3倍,并且该加速比随着网络规模的增加保持不变. 相比于扩展性有限的2D-Mesh架构[18],TriBA更具潜力应用在未来的MPSoC中.
由于片上网络(network-on-chip,NoC)中的物理资源有限,因此采用共享的方式以实现资源的最大化利用. 但当网络中存在循环资源依赖链而无法完成数据转发时,就会发生死锁. 随着网络的规模和复杂性逐渐增加,死锁发生的频率会越来越高[19]. 无死锁是NoC设计中最重要的问题,因为它是实现高效可靠的片上通信的前提,决定了NoC甚至MPSoC是否可用[19]. 最近相关工作表明[18-21],无论是在MPSoC还是Chiplet中,死锁问题依然面临较为严峻的挑战. 通用的防死锁策略能够解决任意拓扑结构中出现的路由级或者协议级死锁,但难以发挥特定拓扑结构的特点和优势,甚至还会增加网络的延迟、功耗以及硬件复杂性,降低MPSoC的性能. 例如,针对任意循环网络的Ring-Split无死锁策略,通过采用非循环子网来绕过死锁,但这会带来较高的功耗以及硬件复杂性等问题[20];针对任意不规则网络的死锁恢复(deadlock removal for arbitrary irregular networks,DRAIN)方法,由于会产生额外的控制存储开销,并不适合大规模的MPSoC[21];针对任意规则网络的基于链路权重的防死锁策略,当网络负载较重或某些链路频繁出现拥塞时,需重新优化链路权重以保持通信通畅,这不但会消耗额外的功耗,而且不正确的权重配置可能会导致死锁的发生[22];针对任意规则或不规则网络的死锁检测恢复策略,需要实时检测并对陷入死锁的数据包及时地处理,这会导致NoC产生较高的硬件开销和逻辑复杂性[23]. 另外,由于路由级和协议级死锁发生原理存在显著差异,现有无死锁方案难以同时解决规则网络中的这2类死锁问题[19-21],影响了MPSoC的可靠性.
哈密顿路径或者哈密顿环能够以线性或者循环的方式进行有效通信,这有益于提高网络的通信效率[24]. 另外,哈密顿性存在于大多数片上拓扑结构中(如2D-Mesh,Torus),它是实现无死锁路由算法的基础之一[25],也是设计无死锁策略最有效的方法之一[26].
因此,本文针对现有无死锁方案无法较好地适用于TriBA架构而限制了架构的可用性和可靠性问题[11,27],在对TriBA中的哈密顿特性等相关拓扑理论进行深入研究的基础上,提出了基于同步哈密顿环的无死锁策略. 该策略是首次针对TriBA架构提出的能够同时解决路由级和协议级死锁,并且在不产生额外开销(延迟、功耗)的情况下提升网络性能和可靠性的无死锁方法. 该方法对于其他具有哈密顿特性的众核架构(如中国科学院计算技术研究所提出的Godson-T众核架构[28])解决同类问题也具有重要的借鉴意义. 本文的主要贡献有3方面:
1) 设计了针对TriBA拓扑结构的对称轴和最大哈密顿边层次判断算法. 该算法能够在拓扑结构自身具有的对称轴基础上为不同类型的数据传输确定所经过的最大哈密顿边层次,从而为其选择独立的存储转发缓冲区,预防了不同数据传输之间的相互依赖和资源竞争,消除了潜在的协议死锁并提高了数据传输速度.
2) 采用循环链表技术设计了同一哈密顿环内数据传输方向判断方法. 该方法能够将同一哈密顿环中的数据传输总体按照顺时针和逆时针方向进行划分,结合全局时钟同步能够消除同一哈密顿环内不同方向的数据传输因竞争缓冲区而产生的路由级死锁,降低了数据传输延迟.
3) 优化了现有的前瞻路由(look ahead shortest path routing,LA4T)算法中存在的冗余计算,并在此基础上设计了基于同步哈密顿环的无死锁路由(Hamiltonian shortest path routing,HamSPR)机制. GEM5仿真结果表明,本文提出的方法优于TriBA现有的无死锁路由方案和采用X-Y和West-first无死锁路由的2D-Mesh架构,能够进一步提高架构的通信性能和可用性.
路由级死锁[29]和协议级死锁[19]是当前NoC中主要存在的2类死锁问题. 当多个数据包保留在网络缓冲区并等待其他数据包占用的缓冲区变得可用时,就会发生路由级死锁,如图1(a)所示. 通过对数据传输施加一些规则或者限制能够消除该类死锁问题,如在2D-Mesh架构中,通过设置转弯限制以避免网络中出现循环依赖的维序路由[22];采用基于不同链路权重的查表路由[30];限制非最小路由的BoomGate方法[21]等. 当不同消息类别(例如请求、响应)的数据包被迫相互等待时,就会发生协议级死锁,如图1(b)所示. 通过采用虚拟网络、死锁恢复等方案能够解决这类死锁问题,如在虚拟化虚拟队列(virtualizing virtual queues,VVQ)[19]方法中通过虚拟化虚拟通道以创建VVQ缓冲区架构从而避免发生协议死锁,以及在DRAIN[29]方法中通过定期排出(即强制移动)网络中可能涉及循环依赖的数据包以从潜在的死锁中恢复. 尽管协议级死锁发生的频率相比于路由级死锁相对较低[19],但同时解决网络中潜在的路由级和协议级死锁,对于提高网络的可靠性至关重要[30]. 由于路由级死锁和协议级死锁存在显著差异,目前已有的死锁解决方案大多只针对规则网络中的其中一类死锁问题,并且一些解决方案可能会带来额外的延迟、功耗和硬件复杂性,显著影响了架构的性能和通用性[20-21,29-30]. 例如,在一些基于2D-Mesh的多核处理器中,用户可能需要执行特定于应用程序的优化[31-32]或是需要构建环形网络[33-34]以加速计算或消除死锁.
表1汇总了TriBA现有的路由解决方案,其中只有Look-up Table,DM4T,LA4T解决了潜在的路由级死锁或协议级死锁,其余算法均未考虑潜在的死锁问题,其主要原因有2点:1)现有的通用防死锁方案一方面可能会产生额外的开销或带来较高的硬件复杂性,影响架构的性能和可用性;另一方面现有方案大都只能解决路由级死锁或协议级死锁,影响了架构的可靠性. 2)TriBA中存在众多环形路径,并且每一条路径在路由过程中都可能成为关键路径,不同环形路径之间的相互交叉以及关键路径的多变导致难以开发出高效的无死锁策略. 因此,研究能够同时解决路由级死锁和协议级死锁,又不影响架构的性能和可靠性的无死锁策略,成为提高TriBA架构的通信性能和可用性的关键. 石峰等人[39]提出了一种基于尖端子图分类传输数据的防死锁方法,但该方法仅针对架构中出现的协议级死锁,并且未探讨相关路由算法及其性能. 该方法是针对TriBA拓扑特性而设计的,也是本文主要对比的方法之一.
如图2所示,本文根据基三拓扑结构中具有的哈密顿特性提出了一种基于同步哈密顿环的无死锁策略,该策略同时采用了分类数据传输(如1级哈密顿环、2级哈密顿环)和同步数据传输(路由器全局时钟同步)的方案,并结合同类数据传输方向划分和局部类气泡(空槽)流控方法,能够同时消除网络中潜在的路由级死锁和协议级死锁,提升架构的通信性能和可靠性. 由于该策略是根据拓扑结构自身具有的哈密顿特性而设计的,因此不影响架构的通用性.
TriBA的拓扑结构是递归拓扑WKd,h[2]的一个特例WK3,F(度为3, 层数为F). 参照图论的命名风格,将TriBA拓扑命名为$ {TC}^{F} $(F为层数),它可以通过递归的方式构成[3]. TriBA的片上存储网络是一种三叉树网络,其将所有分布式cache模块连接到一起形成一个多级片上cache结构(层次化分组内共享). 通过将TriBA与其内存网络融合在一起能够形成一种新的众核架构TriBA-NoC,如图3所示,其中TriBA作为通信子网络TriBA-cNoC(TriBA communication NoC),三叉树作为内存子网络TriBA-mNoC(TriBA memory NoC). 另外,虽然TriBA-NoC具有3D风格的特点,但却能够以瓦片(Tile)的方式集成在2D的硅平面上,如图4所示,并采用与Chiplet相同的设计理念,在实现晶圆面积的最佳使用效率的同时能够实现相同单元模块的重用[7]. 由于本文主要研究对象为TriBA,因此对于TriBA-mNoC不做过多探讨.
使用$ {TC}^{F} $表示TriBA的拓扑结构,结合图论方法对$ {TC}^{F} $进行以下定义:
定义1. 图$ {{{TC}}}^{{{F}}}=\left\{{{V}}({{{TC}}}^{{{F}}}),{{E}}({{{TC}}}^{{{F}}})\right\} $,其中顶点集$ {{V}}({{{TC}}}^{{{F}}})=\left\{{{{x}}}_{{{F}}}… {{{x}}}_{2}{{{x}}}_{1}|{{{x}}}_{{{f}}}\in \mathbb{T}\right\} $,边集${E}({{{TC}}}^{{{F}}})= \{{\bar{{{x}}}}_{{{F}}… {{f}}+1} \cdot $ a$ {{}}{{{b}}}^{{{f}}-1}\leftrightarrow {\bar{{{x}}}}_{{{F}}…{{f}}+1}{{b}}\,{{{a}}}^{{{f}}-1}\;|\; {{a}},{{b}}\in \mathbb{T};\; $${{a}} < {{b}};{{f}}\in \mathbb{N}; \; {{f}}=1,2,… ,{{F}}; $ $ {\bar{x}}_{{{F}}…{{f}}+1}\in {\mathbb{T}}^{{{F}}-{{f}}}\} $.
说明:${\mathbb{T}} = \left\{ {1,2,3} \right\} $为TriBA的三文字集,用于命名${{TC}}^{{F}} $的顶点,其二进制编码形式为$\hat{\mathbb{T}}=\{01,10,11\} $(下同). 由若干${\mathbb{T}} $中文字符组成的序列称为文字串,${{x}}_{{F}}…{{x}}_2{{x}}_1 $是长度为${{F}} $的文字串,其中文字符${{x_i}} \in {\mathbb{T}}, 1 \leqslant {{i}} \leqslant {{F}} $,${{x}}_{{F}}''{{x}}_{{F}}' … {{x}}_1''{{x}}_1' $为其二进制表示形式,${{x}}_{{F}}'' $表示二进制数第2位,${{x}}_{{F}}' $表示二进制数第1位,如111的二进制表示为010101. ${{x}}^{{f}} $表示${\mathbb{T}} $中${{f}} $个相同文字${{x}} $构成的文字串,用$\bar{{x}} $表示内容和长度已知文字串,如$\bar{{x}}_{{{m}}…{{n}}} $表示${{x}}_{{m}}…{{x}}_{{n}} $. ${\mathbb{T}}^{{F}} $为三文字集的笛卡儿幂集,表示为$\{{{{x}}_{{F}}}… {{{x}}_2}{{{x}}_1}|{{{x}}_{{i}}} \in {\mathbb{T}},{{i}} = 1,2, …, F\} $,即所有可能的长度为${{F}} $的文字串的集合. ${{b}}^{{{f}}-1} $表示为${{f}}-{{1}} $个b的文字串(${{b}}\in{\mathbb{T}} $). ${{x}}_{{F}}…{{x}}_2{{x}}_1 \leftrightarrow {{y}}_{{F}}…{{y}}_2{{y}}_1 $形式表示顶点${{x}}_{{F}}…{{x}}_2{{x}}_1 $和${{y}}_{{F}}…{{y}}_2{{y}}_1 $之间的双向边. ${\mathbb{N}} $是自然数集. ${{F}} $是给定的自然数.
在TriBA-NoC中,内核之间通过TriBA-cNoC子网进行互连,片上cache之间通过TriBA-mNoC子网互连,内核与cache间则通过TriBA-mNoC实现互连. 例如在图3中,节点(或内核)111,112,113与节点11$ \varepsilon $(L2 cache)相连,节点(L2 cache)11$ \varepsilon $,(L2 cache)12$ \varepsilon $,(L2 cache)13$ \varepsilon $与节点1$ \varepsilon \varepsilon $(L3 cache)相连,剩余不同节点间的连接关系以此类推. TriBA-NoC布局布线示意图如图4所示.
当进行核间数据传输时,跨越整个$ {TC}^{F} $图的情况并不多,更多的传输是在它的子图中进行. 例如在图5(a)中,当需要计算顶点$ \bar{s} $ 到顶点 $ \bar{t} $的最短路径(即距离)时,相关计算只需要聚焦到$ {TC}^{3} $子图中即可,而不需要在整个$ {TC}^{F} $上进行计算. 因此,将路由计算发生在同时覆盖路由起点和路由终点的最小子图称为焦点路由图$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $(focus routing graph,FRG),其中$ f $($ f < F $)表示该图的规模(层数),有时$ f $也可能被一个超节点名所取代.
$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{m}^{f} $(maximum subgraph of FRG,MSG)在$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的基础上进行定义,旨在路由计算过程中能够准确定位路由起点和路由终点的具体位置,并准确给出最短路径,如图5(a)中的$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{1}^{3} $,$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{3}^{3} $,$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{2}^{3}. {\mathrm{M}\mathrm{S}\mathrm{G}}_{m}^{f} $中的$ f $与$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $相同,$ m $表示$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的尖端顶点$ {v}^{f} $所在的焦点路由子图,其中$ m,v\in \mathbb{T} $,$ v $表示尖端节点名,如图3中$ {TC}^{3} $的$ 111 $($ {1}^{3} $),$ 222({2}^{3}) $,$ 333({3}^{3}) $节点. 注意:$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{m}^{f} $是$ {TC}^{f-1} $类子图,$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $是$ {TC}^{f} $类子图,$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{m}^{f} $中$ f $可能像$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $那样被超节点名取代. 另外,在$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{m}^{f} $的基础上针对$ {TC}^{F} $拓扑特性定义了数据传输的不同模式和路径,如图5(b)所示.
在图论中,哈密顿路径是指在无向图中,经过每个顶点1次且只有1次的路径. 若是在哈密顿路径中起点和终点是同一个节点,则这条哈密顿路径就构成了一个哈密顿环[40]. $ {TC}^{F} $的哈密顿性是指其拥有哈密顿路径(Hamiltonian path)和哈密顿环(Hamiltonian cycle),下文简称$ \mathrm{H} $-路径和$ \mathrm{H} $-环.
定义2. 在$ {TC}^{F} $中的任意两尖端节点间存在一条路径,若它的起始节点为其中一个尖端节点,终点为另一个尖端节点,并且经过$ {TC}^{F} $中的每个顶点1次且仅1次,则称这条路径为$ \mathrm{H} $-路径,如图6所示.
定义3. 在$ {TC}^{F} $中,若H-路径的起点和终点为同一个顶点,并且该路径穿越每个顶点1次且仅1次,则将这个闭合H-路径称为H-环,如图7所示.
$ {TC}^{F} $的哈密顿性有益于解决架构中的流式计算或者防死锁问题,并且$ {TC}^{F} $的每个子图都具有哈密顿环这一特征,因此该特性不受网络规模的影响.
本节根据$ {TC}^{F} $自身具有的哈密顿特性,首先介绍$ {TC}^{F} $中哈密顿最大边及其环流的构造方法;其次阐述$ {TC}^{F} $中的对称点及对称轴判断方法,并设计相应的判断算法;再次介绍根据对称轴为$ {TC}^{F} $中的数据传输选择不同层次的哈密顿边并划分不同类型的缓冲区方法,以及设计相应的算法;最后,介绍使用链表技术划分同一哈密顿环内的数据传输方向判断方法.
在$ {TC}^{F} $哈密顿环的基础上,以圆环的风格将$ {TC}^{F} $的哈密顿环路重新绘制,如图8所示,并对环路进一步的分解. 从图8中的哈密顿环可以发现,在运行时刻虽然$ {TC}^{F} $的边上随机遍布着沿边传输的各个方向的数据,但在宏观上呈现了一种沿着哈密顿环的流动,将其称为虚拟哈密顿环流(virtual Hamiltonian ring,H-ring),简称环流. 为了进一步理解哈密顿环流,定义了 $ {TC}^{F} $中的哈密顿边和非哈密顿边.
定义4. 按照图8中哈密顿圆环的画法,规定在圆环中哈密顿边位于圆环的最外侧,内侧向心方向依次出现链接2个顶点、链接2个$ {TC}^{1} $、链接2个$ {TC}^{2} $等的非哈密顿边,这些边的层次依次称为2,3,4,…,哈密顿边是第1层边.
如图8所示,那些非哈密顿边链接的节点为哈密顿环上的“捷径”(如图8中的虚线和点划线). 在最短路径路由机制的约束下(数据传输始终选择最短的路径),数据在哈密顿环和捷径间进行跳跃. 如果认为“捷径”上的数据在哈密顿路径中的传输使用了自己的独立通道,那么在$ {TC}^{F} $上的数据传输“逻辑上”形成了沿着F个独立逻辑通道的传输. 如在图8中将$ {TC}^{3} $逻辑上划分为3个环,每个环的级别取决于最大哈密顿边的层次.
接下来,将进一步探讨如何确定数据传输所经过的最大边层次,从而正确地为数据传输分配独立的缓冲区.
要想使通信数据“逻辑上”在自己独立的通道中传输,技术上必然分时复用相同的物理通道,即通过独享各自数据类型对应的存储转发缓冲区来实现. 而对通信数据所使用缓冲区类型的判断,需在路由计算的同时,根据对称轴判断哈密顿路径结构和走向情况. 为此给出下述对称轴相关的定义、定理和算法.
定义5. 在子图$ {TC}^{f}\subseteq {TC}^{F} $平面图示中,2尖端$ {p}^{f} $和$ {q}^{f} $间的哈密顿路径($ {TC}^{F} $的哈密顿路径的一部分)中点(或称对称点)为尖端$ {k}^{f} $,该顶点或其所在对称轴记为$ { \bar{x}}_{F…f+1}{A}_{k}^{f} $,如图9所示,其中$ { \bar{x}}_{F…f+1} $是$ {TC}^{f} $名(长度为$ F-f $的文字串),$ p,q,k\in \mathbb{T} $且$ p\ne q\ne k $.
定理1. 任意一个$ {TC}^{f}\subseteq {TC}^{F}$尖端节点都是另外2个尖端节点间哈密顿路径的中点,即该尖端沿该哈密顿路径到另外2个尖端节点的距离相同.
证明. 对$ {TC}^{f} $规模$ f $应用数学归纳法,以尖端$ {3}^{f} $到尖端$ {1}^{f} $和$ {2}^{f} $的哈密顿距离为例证明定理1,其他情况可类似证明.
1)基础步骤:$ f=1 $时,即$ {TC}^{1} $尖端节点3到另外2尖端1和2的哈密顿距离均为1.
2)归纳步骤:当$ f > 1 $时,$ {TC}^{f} $由3个$ {TC}^{f-1} $及3个互连单边构成,如图9所示. 根据归纳步骤,尖端$ {3}^{f-1} $到所在$ {TC}^{f-1} $另外2个尖端的哈密顿距离相等,即2个距离$ \overline{ab} $和$ \overline{a{b}'} $相等. 而根据$ {TC}^{F} $中任何2个尖端顶点间H-路径的长度为$ {3}^{F}-1 $,距离$ \overline{bc} $和$ \overline{{b}'{c}'} $均为$ {3}^{f-1} $,于是定理1得证. 证毕.
定理2. 对称轴为$ { \bar{x}}_{F… f+1}{A}_{k}^{f} $的图$ {TC}^{f} \subseteq TC^{F} $由对称轴分别为$ { \bar{x}}_{F…f+1}p{A}_{q}^{f-1} $,$ { \bar{x}}_{F…f+1}k{A}_{k}^{f-1} $,$ { \bar{x}}_{F…f+1}q{A}_{p}^{f-1} $的$ {TC}^{f-1} $子图及互连单边构成,其中$ { \bar{x}}_{F…f+1} $是$ {TC}^{f} $名,$ p,q,k\in \mathbb{T} $且$ p\ne q\ne k $.
证明. 对$ {TC}^{f} $的$ f $应用数学归纳法,这里以它的对称轴是$ { \bar{x}}_{F… f+1}{A}_{3}^{f} $为例证明,其他情况可类似证明.
1)基础步骤: $ f=1 $时(如图9中的$ {TC}^{1} $),如果3顶点的$ {TC}^{1} $的名字为$ { \bar{x}}_{F-1} $,则它的对称轴为$ { \bar{x}}_{F…2}{A}_{3}^{1} $,即对称点$ { \bar{x}}_{F…2} $3,至于定理2中的子图则为单个顶点. 而当$ f=2 $时(图9中的$ {TC}^{2} $),如它的对称轴是$ { \bar{x}}_{F… 3}{A}_{3}^{2} $,此时,其3个$ {TC}^{1} $子图的对称轴按定理2所述分别为$ { \bar{x}}_{F…3}1{A}_{2}^{1} $,$ { \bar{x}}_{F…3}3{A}_{3}^{1} $,$ { \bar{x}}_{F… 3}2{A}_{1}^{1} $,对称点分别为$ { \bar{x}}_{F… 3}12 $,$ { \bar{x}}_{F… 3}33 $,$ { \bar{x}}_{F… 3}21 $,与定理1所述情况相同.
2)归纳步骤: $ f > 2 $ 时,$ {TC}^{f} $由3个$ {TC}^{f-1} $及3个互连单边构成,如果$ {TC}^{f} $的对称点为$ { \bar{x}}_{F…f+1}{A}_{3}^{f} $,显然考虑到3个$ {TC}^{f-1} $的哈密顿路径片段的端点情况,位于$ {TC}^{f} $左下角的$ {TC}^{f-1} $的对称点必然是$ { \bar{x}}_{F…f+1}1{2}^{f-1} $,对称轴为$ { \bar{x}}_{F…f+1}1{A}_{2}^{f-1} $;位于正上方的$ {TC}^{f-1} $的对称点是$ { \bar{x}}_{F…f+1}3{3}^{f-1} $,对称轴为$ { \bar{x}}_{F…f+1}3{A}_{3}^{f-1} $;位于右下方的$ {TC}^{f-1} $的对称点必然是$ { \bar{x}}_{F…f+1}2{1}^{f-1} $,对称轴为$ { \bar{x}}_{F…f+1}2{A}_{1}^{f-1} $;故定理2得证. 证毕.
定理2中图$ {TC}^{f} $的对称轴与其构成子图对称轴的关系是,如果图的对称轴是$ { \bar{x}}_{F…f+1}{A}_{k}^{f} $,则层码$ {x}_{f}=k $构成子图的对称轴$ { \bar{x}}_{F…f+1}k{A}_{k}^{f-1} $与此轴重合;层码$ {x}_{f}= p $构成的子图对称轴$ { \bar{x}}_{F… f+1}{A}_{q}^{f-1} $与$ { \bar{x}}_{F… f+1}{A}_{q}^{f} $重合;层码$ {x}_{f}=q $构成的子图对称轴$ { \bar{x}}_{F…f+1}j{A}_{p}^{f} $与$ { \bar{x}}_{F…f+1}{A}_{p}^{f} $重合;其$ p,q,k\in \mathbb{T} $且$ p\ne q\ne k $,如图9所示. 例如,213$ {A}_{2}^{4} $是名称为213的$ {TC}^{4} $子图,其对称轴/顶点是该$ {TC}^{4} $的尖端$ {\text{2}}^{\text{4}} $或顶点2132222. 再例如,$ {TC}^{4} $对称轴$ { \bar{x}}_{F…5}{A}_{1}^{4} $可以展开一层后,下一个层次3个$ {TC}^{3} $子图的对称点分别为$ { \bar{x}}_{F…5}2{A}_{3}^{3} $,$ { \bar{x}}_{F… 5}1{A}_{1}^{3} $,$ { \bar{x}}_{F… 5}3{A}_{2}^{3} $;每个对称轴所在子图均可根据定理2继续深入展开,例如$ { \bar{x}}_{F…5}3{A}_{2}^{3} $所在$ {TC}^{3} $子图继续展开后的$ {TC}^{2} $子图对称轴分别为$ { \bar{x}}_{F… 5}31{A}_{3}^{2} $,$ { \bar{x}}_{F…5}32{A}_{2}^{2} $,$ { \bar{x}}_{F… 5}33{A}_{1}^{2} $.
根据定理1和定理2,设计了$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的对称轴判断算法DetAxiSym(determine the axis of symmetry),具体如下:
算法1. $ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的对称轴判断算法DetAxiSym.
输入:源节点 $ {s}_{F}… {{s}_{2}s}_{1} $,目标节点 $ {t}_{F}… {{t}_{2}t}_{1} $,当前通信模式 $ TP $;
输出:$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的对称轴$ { \bar{x}}_{F…f+1}{A}_{x}^{f} $(变量Axis标识).
① begin
② if ($ {s}_{F}\ne {t}_{F} $) then
③  if($ {TP}_{0} $或$ {TP}_{1} $)then
④    Axis $ \leftarrow $ $ 3{A}_{3}^{F-1} $;
⑤  else if ($ {TP}_{2}\mathrm{或}{TP}_{3} $)then
⑥    Axis $ \leftarrow $ $ 2{A}_{2}^{F-1} $;
⑦  else Axis $ \leftarrow $ $ 1{A}_{1}^{F-1} $;/*此时通信模式为$ {TP}_{4} $或 $ {TP}_{5} $*/
⑧  end if
⑨  return Axis;
⑩ end if
⑪ Axis $ \leftarrow {s}_{F}{A}_{{s}_{F}}^{F-1} $;/*$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f}\subset {\mathrm{F}\mathrm{R}\mathrm{G}}^{F} $时的初始对称 轴*/
⑫ for($ i=F-1 $;$ i\ge f+1 $;$ i-- $)do
⑬  if$ ({s}_{i}\ne {s}_{i-1}) $then
⑭    $ s\leftarrow \mathbb{T}({s}_{i} $,$ {s}_{i-1}) $;/*选择$ \mathbb{T} $中不等于$ {s}_{i} $和$ {s}_{i-1} $ 的字符*/
⑮    Axis $ \leftarrow { \bar{x}}_{F… i+1}\times {s}_{i}{A}_{s}^{i-1} $;/*原Axis的值为 $ { \bar{x}}_{F…i+1}{A}_{x}^{i} $*/
⑯  else Axis $ \leftarrow $ $ { \bar{x}}_{F… i+1}{\times {s}_{i-1}A}_{{s}_{i-1}}^{i-1} $;
⑰  end if
⑱ end for
⑲ return Axis;
⑳ end
以$ {TC}^{3} $为例,详细介绍节点间数据传输的对称轴择选过程. 如图10(a)所示,若节点n(133)与节点m(213)进行通信,首先根据节点n和m的文字串的第1位不同($ {s}_{3}\ne {t}_{3} $)判断通信所在的$ \text{FRG} $为3($ f= F=3 $),接着在最短路径路由的约束下可判断此时的通信类型为$ {TP}_{0} $,最后根据算法1(行④)可判断对称轴为$ 3{A}_{3}^{2} $(即333节点所在对称轴);若节点e(121)与节点p(122)通信,首先根据节点e和p文字串的第1和第2位相同($ {s}_{3}={t}_{3},{s}_{2}={t}_{2} $)而第3位不同(即$ {s}_{3}\ne {t}_{3} $),判断通信所在的$ \text{FRG} $为1(即$ f=1 $),接着设置初始对称轴为$ {1A}_{1}^{2} $(111节点所在对称轴,算法1行⑪),然后根据节点e中的字符$ {s}_{2} $和$ {s}_{1} $不相等(算法1行⑬),从$ \mathbb{T}=\left\{1,\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }2,\mathrm{ }3\right\} $中选择不等于$ {s}_{2} $和$ {s}_{1} $的字符3(算法1行⑭),最后修改初始对称轴为$ {12A}_{3}^{1} $(123节点所在对称轴,算法1行⑮). 其余情况与上述相同就不在此赘述. 根据不同对称轴所对应非哈密顿边的特点不同,定义了不同层次的边,如图10(b)所示.
路由核心计算在等价$ {{TP}}_{\text{0}} $传输模式($ {\text{MSG}}_{1}^{F}\mathrm{内}\mathrm{的} $节点与$ {\text{}\text{MSG}}_{2}^{F} $中的节点通信记为TP0)中进行,如图5(b)所示,但随$ \text{FRG}\text{} $的位置不同,它的哈密顿环形状也会随之发生变化. 所以路由核心计算在得到转发端口后,还必须确定该数据将使用的缓冲区类型,即确定相应的传输属于$ {{TP}}_{\text{0}} $样式下的哪个哈密顿环. 其中,缓冲区类型按照哈密顿环流所经过的最大哈密顿边或非哈密顿边层次编号,如图8所示. 第1层哈密顿环对应哈密顿边,缓冲区为TYPE-I型;第$ 2\sim F $层环流对应第$ 2\sim F $层非哈密顿边,相应的缓冲区类型是TYPE-II~TYPE-F. 接下来以$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{3} $为例,详细介绍缓冲区判断原理及过程.
如图10(b)所示,若节点$ \bar{s} $与$ \bar{t} $通信,首先判断此时通信所在的最大$ \text{FRG}\text{} $为3,在最短路径路由的约束下,数据传输路径选择Path A,根据算法1获得相应的对称点k及其该点所在的对称轴;其次判断节点$ \bar{s} $与$ \bar{t} $所在的$ \text{MSG} $分别为$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{1}^{3} $和$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{2}^{3} $,此时$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{1}^{3} $内的节点与$ {\mathrm{M}\mathrm{S}\mathrm{G}}_{2}^{3} $内的节点通过路径Path A通信,则必然经过对称轴所对应的最大层次边$ b\leftrightarrow b' $;最后确定节点$ \bar{s} $与$ \bar{t} $通信经过的最大哈密顿边层次为4,并将其分配到4-Level H-ring缓冲区中进行数据传输. 节点$ \bar{s} $与$ \bar{s}' $通信缓冲区判断类似,其所经历的最大哈密顿边层次为3. 综上所述,在$ {TP}_{0} $传输模式下,对称轴分别为$ { \bar{x}}_{F…f+1}{A}_{1}^{f} $,$ { \bar{x}}_{F…f+1}{A}_{2}^{f} $,$ { \bar{x}}_{F…f+1}{A}_{3}^{f} $下的Path A和Path B通信数据缓冲区类型判断算法GetBufType(get buffer type)如下:
算法2. 缓冲区类型判断算法GetBufType.
输入:焦点路由图$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $,当前传输路径Path,对称轴Axis,源节点$ { \bar{x}}_{F…f+1}{s}_{f}… {s}_{2}{s}_{1}, $目标节点 $ { \bar{x}}_{F…f+1}{t}_{f}… {{t}_{2}t}_{1} $;
输出:当前通信经历的最高边层次MaxLevelNum.
① begin
② if(Path $ == $ Path B)then
③  if($ f==F $)then /*$ f $和F来自$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $和源节点*/
④   return $ {MaxLevelNum}\leftarrow F $;
⑤  else if(Axis $ == $ $ { \bar{x}}_{F…f+1}{A}_{3}^{f} $)then
⑥   return $ {MaxLevelNum}\leftarrow f $;
⑦  else
⑧   return $ {MaxLevelNum}\leftarrow f $+1;/*Axis为 $ { \bar{x}}_{F…f+1}{A}_{1}^{f} $或$ { \bar{x}}_{F…f+1}{A}_{2}^{f} $*/
⑨  end if
⑩ end if
⑪ if(Axis $ == $ $ { \bar{x}}_{F…f+1}{A}_{1}^{f} $)then /*Path $ == $ Path A*/
⑫  for($ i $=1;$ i $≤$ f $−1;$ i $++)do
⑬   if($ i\;\text{mod}\;2 \ne0\&\&({s}_{f-i}==3\left|\right|{t}_{f-i}== $ $ 2)) $then
⑭    MaxLevelNum $ \leftarrow $ $ f -i+1$,break;
⑮   end if
⑯   if($ i\;\text{mod}\;2 \ne 0\& \&({s}_{f-i}==1\left|\right|{t}_{f-i}== $ $ 3)) $then
⑰     MaxLevelNum $ \leftarrow $ $ f $−$ i $,break;
⑱   end if
⑲   if($ i\;\text{mod}\;2==0\& \&({s}_{f-i}==1\left|\right|{t}_{f-i}== $$ 3)) $then
⑳     MaxLevelNum $ \leftarrow $ $ f $−$ i $+1,break;
㉑   end if
㉒   if($ i\;\text{mod}\;2==0\& \&({s}_{f-i}==3\left|\right|{t}_{f-i}== $$ 2)) $then
㉓     MaxLevelNum $ \leftarrow $ $ f $−$ i $,break;
㉔   end if
㉕  end for
㉖  return MaxLevelNum;
㉗ end if
㉘ if(Axis $ == $ $ { \bar{x}}_{F…f+1}{A}_{2}^{f} $)then
㉙  for ($ i $=1;$ i $≤$ f $−1;$ i $++) do
㉚   if($ i\;\text{mod}\;2 \ne 0\& \&({s}_{f-i}==1\left|\right|{t}_{f-i}== $ $ 3)) $then
㉛     MaxLevelNum $ \leftarrow $ $ f $−$ i $+1,break;
㉜   end if
㉝   if($ i\;\text{mod}\;2 \ne 0 \& \&({s}_{f-i}==3\left|\right|{t}_{f-i}== $ $ 2)) $then
㉞     MaxLevelNum $ \leftarrow $ $ f $−$ i $,break;
㉟   end if
㊱   if($ i\;\text{mod}\;2==0 \& \&({s}_{f-i}==3\left|\right|{t}_{f-i}== $$ 2)) $then
㊲     MaxLevelNum $ \leftarrow $ $ f $−$ i $+1,break;
㊳   end if
㊴   if($ i\;\text{mod}\;2==0 \& \&({s}_{f-i}==1\mathrm{ }\left|\right|{t}_{f-i}== $ $ 3 $)) then
㊵     MaxLevelNum $ \leftarrow $ $ f $−$ i $,break;
㊶   end if
㊷  end for
㊸  return MaxLevelNum;
㊹ end if
㊺ return MaxLevelNum$ \leftarrow $ $ f $+1;/*Axis为 $ { \bar{x}}_{F…f+1}{A}_{3}^{f} $*/
㊻ end
在算法2中,首先根据不同的传输路径(Path A 或 Path B)划分数据传输可能经过的最大哈密顿边层次(行②⑪). 当路由算法选择Path B时,由于$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{F} $的哈密顿环与其内的$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f}\text{} $哈密顿路径不同,因此需根据所在的焦点路由图分别进行数据类型判断(行③ ~ ⑩);当路由算法选择Path A时,数据传输经过的最高层次边与$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的$ f $值、源节点在$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $中的位置和源节点所在$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $的子图对称轴均有关,需根据$ f $值和$ F $值进一步判断(行⑪ ~ ㊹). 另外,根据TriBA的旋转对称性,可以将其他通信模式下的缓冲区类型计算通过置换群[3]$ {\mathbb{S}}_{3} $变换至$ {{TP}}_{\text{0}} $传输模式下进行,并通过$ {\mathbb{S}}_{3}^{-1} $逆变换返回输出结果即可.
通过对数据传输划分独立的缓冲区类型,可以使$ {TC}^{F} $中不同的数据通信限制在自己独立的通道中而不相互干扰. 但如果一个独立的传输通道中既存在沿哈密顿环的顺时针传输又存在逆时针传输(如图8所示),当2个不同方向的数据传输相遇时,就可能会出现阻塞和资源竞争,从而导致长时间等待、高负载时甚至可能引发死锁. 因此,为了避免出现上述问题,通过采用循环链表将$ {TC}^{F} $上的同一缓冲区中的数据传输在通信发起起点时确定消息所属的传输方向,从而将其划分到哈密顿顺时针传输通道或哈密顿逆时针传输通道上,并且后续的传输始终在同一通道中进行,避免在同一哈密顿环的传输通道中因出现2个不同方向的传输而可能产生的资源竞争问题.
本文以$ {TC}^{3} $为例(如图8所示)阐述划分方法:
1) 建立循环链表. 以111节点为链表的头节点,按照顺时针方向依次链接环上的所有节点,尾节点为112.
2) 循环动态查询. 假设源节点为A,目标节点为B,当通信建立时,在通信起点的链表上以从前往后的方向(顺时针)和从后往前的方向(逆时针)分别查找节点A,查到后标记为新的节点$ {A}' $和$ {A}'' $,以$ {A}' $和$ {A}'' $为新起点分别从顺时针方向和逆时针方向计算距离节点B的距离,记为 $ {Dis\_A}' $和 $ {Dis\_A}'' $
3) 划分传输方向. 比较$ {Dis\_A}' $和$ {Dis\_A}'' $的距离,若$ {Dis\_A}' \leqslant {Dis\_A}'' $则该数据传输方向为顺时针方向(标记为1),否则为逆时针方向(标记为0).
由于数据传输方向的划分只需要在通信发起时确定,因此只需要查询1次即可,该方法不同于基于查表的路由需要多次查询以确定每一次的转发端口.
LA4T 路由算法是一种前瞻式路由算法,该算法能够根据当前节点转发端口、尖端节点名以及所在的焦点路由图$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $,推断下一节点的转发端口,从而提高数据包转发效率[30,38]. 但该算法没有考虑通信数据自身所隐含的信息(例如数据包跳数),导致仍然需要在每次转发时计算Path A和Path B路径长度并进行对比,这相对来说比较耗时. 在LA4T算法的基础上为通信数据增加了当前数据包跳数变量Hops,通过判断Hops是否等于0,来判断当前数据包所处节点是否为通信源节点,若为通信源节点则需计算路径长度并进行对比,输出当前节点和下一节点的转发端口;否则直接根据当前数据包所携带的转发端口推断下一节点的转发端口并输出. 改进的LA4T在传输模式为TP0时的具体算法如下.
算法3. 改进后的LA4T路由算法.
输入:起始节点 $ s={s}_{F}''{s}_{F}'… {s}_{1}''{s}_{1}' $,目标节点 $ {t=t}_{F}''{t}_{F}'… {t}_{1}''{t}_{1}' $,当前节点$ {c=c}_{F}''{c}_{F}'… {c}_{1}''{c}_{1}' $,当前焦点路由图$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $级数$ f $,当前数据包跳数Hops,当前节点转发端口cur-outport;
输出:下一节点转发端口next-outport.
① begin
② if(Hops $ == $ 0)then /*当前节点为源节点*/
③   Dis(Path A)$ = $ $ {s}_{f-1}'… {s}_{1}' $ $ + $ $ {t}_{f-1}''… {t}_{1}'' $ $ + $1;
④   Dis(Path B)$ =({ \bar{s}}_{f-1}''… { \bar{s}}_{1}'' $$\oplus $$ { \bar{s}}_{f-1}'… { \bar{s}}_{1}')+$ $( \bar{t}\,''_{ f-1}… \bar{t}\,''_{1} \oplus \bar{t}\,'_{ f-1}… \bar{t}\,'_{1})+{2}^{f-1}+1 $;
⑤  if Dis(Path A)$ \le $ Dis(Path B)then
⑥    cur-outport $ = $ 2;/*更新当前节点转发端口*/
⑦    next-outport $ = $ reasoning(s,$ {v}_{2}^{f} $);/*计算下 一节点转发端口*/
⑧  else then
⑨    cur-outport $ = $ 3;
⑩    next-outport $ = $ reasoning(s,$ {v}_{3}^{f} $);
⑪  end if
⑫  return next-outport;
⑬ end if
⑭ if(cur-outport $ == $ 2)then/*当前节点非源节点*/
⑮   next-outport $ = $ reasoning(c,$ {v}_{2}^{f} $);/*推理下一 节点转发端口*/
⑯ end if
⑰ if (cur-outport $ == $ 3) then
⑱  next-outport $ = $ reasoning(c,$ {v}_{3}^{f} $);
⑲ end if
⑳ return next-outport;
㉑ end
在算法3中,当前焦点路由图$ {\mathrm{F}\mathrm{R}\mathrm{G}}^{f} $可根据当前节点和目标节点名进行计算,当前数据包跳数Hops和当前节点转发端口cur-outport(端口命名见图5(a))可从头节点直接获取,并且默认值为0. 在计算路径长度Dis(Path A)和Dis(Path B)时需将节点名的二进制数$ s'_{f-1}… {s}_{2}'{s}_{1}' $等转化为十进制数,符号“+”表示普通的数值加号,符号“$\oplus $”表示逻辑位或运算,$ \bar{s} $表示逻辑位取反运算. reasoning(c,$ {v}_{2}^{f} $)表示根据当前节点c和尖端节点$ {v}_{2}^{f} $($ f $为当前节点焦点路由图级数,2表示当前尖端节点为2)来推理下一节点转发端口. 另外,可以将其他通信模式下的路由计算通过置换群$ {\mathbb{S}}_{3} $变换至$ {{TP}}_{\text{0}} $传输模式下进行,并通过逆变换返回输出端口即可. 由于篇幅有限,关于LA4T算法的其他详细信息请参见文献[38].
当通信数据进入节点后(Hops=0),其转发目标端口需要根据当前节点和目标节点的编码信息进行路由计算,由于TriBA节点拥有的4个端口(包括当地内核)接收到的数据都需经过相同算法计算,因此使用流水线方式实现相应的计算,如图11所示. 考虑到流水线过程的整个设计规模较大,因篇幅有限,仅对流水过程中的4个重要模块功能做简要介绍:
1) 数据准备阶段(PREP). 该阶段主要完成当前通信模式、当前焦点路由图的层数计算,对应算法3的部分输入.
2) $ {TP}_{0} $模式等价距离计算阶段(EDIS). 该阶段主要计算当前节点和目标节点在$ {{TP}}_{\text{0}} $传输模式下的等价节点($ {\mathbb{S}}_{3} $变换后的节点),然后计算等价节点之间的路由距离. 对应算法3的行③④,其中$ {\mathbb{S}}_{3} $变换相关计算可参考LA4T算法原文[38].
3) 等价模式备选路径比较阶段(PCMP). 该阶段的主要完成对Path A 和 Path B备选路径的长度比较,进而给出等价模式中的转发端口,以及预测下个节点处的备选转发端口(该端口与Path A和Path B相关,在下个流水段 FWDP 才能具体给出转发端口的选择). 对应算法3中行⑤~⑫的部分内容.
4) 转发端口判定阶段(FWDP). 将PCMP输出的在等价模式$ {TP}_{0} $下的转发端口通过$ {\mathbb{S}}_{3}^{-1} $逆变换到原模式,作为备选转发端口. 接着判断当前节点若是尖端时需要对消息转发进行特殊处理,最终根据所满足的具体条件给出最终转发端口. 对应算法3中行⑤ ~ ⑲部分内容.
在通信发起节点,首先需要根据当前节点和目的节点的信息计算此次数据传输在其生命周期中将要经历的最大哈密顿边层次,进而为其分配相应的缓冲区,并规定在其生命周期结束前始终保持缓冲区不变,保证不同缓冲区之间的独立数据传输;其次,需要计算数据传输方向,并为其分配虚拟通道,规定每次数据转发需在规定的虚拟通道中进行,从而能够有效避免在同一个哈密顿环中因相向的数据传输而产生的资源竞争问题. 根据以上原理,设计了缓冲区选择和控制(buffer select and control,BufSanCon)算法,具体算法内容如下:
算法4. 缓冲区选择和控制算法BufSanCon.
输入:起始节点 $ s={ \bar{x}}_{F…f+1}{s}_{f}… {{s}_{2}s}_{1} $,目标节点$ t={ \bar{x}}_{F… f+1}{t}_{f}… {{t}_{2}t}_{1} $,焦点路由图$ {\text{FRG}}^{\mathit{f}} $;
输出:当前传输缓冲区类型Buffer_Type和传输虚拟通道VC.
① begin
② Buffer_Type,Ham_OriDirection $ \leftarrow $ $ -1 $;
③ Path,TP $ \leftarrow $计算当前传输路径和通信模式;
④ Axis $ \leftarrow $ call(DetAxiSym);/*计算对称轴*/
⑤ Buffer_Type $ \leftarrow $call(GetBufType);/*计算缓冲区 类型*/
⑥ Ham_OriDirection $ \leftarrow $call(RecurLinList);/*计算 传输方向, RecurLinList为循环链表*/
⑦ if(Ham_OriDirection $ == $ 0)then
⑧   VC $ \leftarrow $分配Buffer_Type中的逆时针VC;
⑨ else then
⑩   VC $ \leftarrow $分配Buffer_Type中的顺时针VC;
⑪ end if
⑫ return Buffer_Type,VC;
⑬ end
通过将改进的LA4T路由算法和BufSanCon算法结合在一起,TriBA能够获得新的无死锁路由机制,命名为哈密顿最短路径路由(Hamiltonian shortest path routing,HamSPR)机制.
形成死锁的4个必要条件为互斥、请求与保持、不可剥夺以及循环等待,如果打破其中的任意一个就可能预防死锁的发生[41]. 本文从消息的传输行为出发,提出了基于同步哈密顿环的死锁预防策略来分别解决可能出现的路由级和协议级死锁,具体无死锁说明如下:
1) 采用分组传输和分时复用的策略预防协议级死锁. 在$ {TC}^{F} $中,将所有的数据传输按照其在整个传输生命周期过程中经历的最大哈密顿边层数进行划分,形成若干组,并为不同的组分配独立的缓冲区,规定数据在整个传输生命周期中保持组别不变,保证不同组之间的独立数据传输,不会相互交叉和干扰. 另外,采用分时复用的策略解决不同组之间对于同一物理通道的竞争. 通过制定上述策略,从而打破形成死锁的必要条件之一——循环等待.
2) 采用同步且划分传输方向的策略预防路由级死锁. 在同一哈密顿环内,规定数据在同一时刻进行同步向前传输,预防前后数据因竞争同一虚拟通道而可能出现的请求和保持现象. 另外,通过将同一哈密顿环内不同方向(顺时针和逆时针)的数据传输限制在自己的独立通道中,保证在同一个缓冲区中的顺时针和逆时针传输相互独立且互不交叉,进一步预防了在同一缓冲区中数据传输可能出现的资源竞争. 通过制定上述策略,能够打破形成死锁的必要条件之一——请求和保持.
在本节中,通过使用修改后的GEM5[42]仿真平台中内嵌的Garnet 3.0片上网络模拟器[43]和DSENT工具[44],分别在系统仿真(system emulation,SE)模式下使用合成流量以及在全系统(full system,FS)模式下使用PARSEC[45]基准测试集测试了HamSPR路由机制的性能. 另外,在仿真过程中为了实现独立的、可操作的不同通信通道以减少其他通信的干扰,使用了虚拟网络和虚拟通道技术.
图12为HamSPR在GEM5中实现的路由器微架构,该路由器由3部分组成,分别为消息接收(message receive,MsgRec)单元、消息处理(message process,MsgPro)单元和消息转发(message pass,MsgPass)单元. MsgRec单元分别由3个输入缓冲区(虚拟网络)和1个本地内核组成,其中每一个缓冲区中包含4个虚拟通道(virtual channel,VC),而本地内核负责消息的接收和新消息的发送. MsgPro单元则主要负责消息头节点信息的处理,包括路由计算、虚拟通道分配、缓冲区及虚拟通道的选择和控制以及交叉开关分配,其中缓冲区及虚拟通道的选择和控制只针对新的消息头节点,并且其在交叉开关分配之前. MsgPass单元则由一组4×4交叉开关组成,负责消息的转发.
为了全面评估HamSPR的性能,选取了TriBA中具有代表性的查找表路由算法Table、最短路径路由算法SPR4T和改进后的向前查找路由算法LA4T作为对比方法. Table采用基于不同链路权重的防死锁方法[11],SPR4T和LA4T采用基于尖端数据分类的防死锁方法[39].
在SE模式下,选取位补码(bit-complement)、位旋转(bit-rotation)、统一随机(uniform-random)和转置(transpose)这4种常用的流量模式,以平均数据包延迟(总延迟周期$ \text{/} $接收数据包)、吞吐量(数据包$ \text{/} $(节点×周期))和平均数据包功耗(总功耗$ \text{/} $接收数据包)为评价指标评估4种不同路由算法的性能. 在FS模式下,分别测试PARSEC中12种来自不同领域的应用程序的运行时间、平均数据包功耗、平均数据包延迟和平均数据包跳数(总跳数$ \text{/} $接收数据包). 另外,以Table算法测试数据为基准,分别计算了其他算法的归一化运行时间和归一化平均数据包功耗.
仿真实验配置如下:处理器:Intel® Xeon® CPU E3-1225 v5 @3.31 GHz;缓存:L1-256 KB,L2-1.0 MB,L3-8.0 MB;操作系统:Ubuntu (20.04.6 LTS);DSENT工艺模型为11 nm (tri-gate). 另外,为每个缓冲区设置了1个空槽,以保证哈密顿环中的数据传输能够正常地运行而不发生阻塞. 基于X-Y和West-first算法的2D-Mesh除了使用2D-Mesh的网络拓扑、X-Y和West-first路由算法外,其余在FS模式下的仿真参数均与TriBA相同. SE模式和FS模式下的具体仿真参数见表2. 其余仿真参数均遵循GEM5仿真器以及Garnet 3.0和DSENT中指定的默认值.
在SE模式下,所有模拟核心不执行实际指令,它们只充当流量注入器,将数据包引入网络. 这种方法使系统独立于指令集体系结构(ISA),并使内存子系统保持静默,从而实现对模拟系统中网络性能的更精确评估[42]. 如图13所示,评估了4种不同路由算法分别在bit-complement,uniform-random,transpose,bit-rotation流量模式下的平均数据包延迟和吞吐量. 由于Table未对不同的数据传输进行分类,只是根据不同链路的权重来判断无死锁的传输路径,并且在数据传输过程中由于多次计算路径权重而可能产生较高的延迟,使其性能不如其他3种算法. 而采用基于尖端数据分类的SPR4T和LA4T算法表现出了比Table更优的性能. 其中,由于LA4T采用了前瞻路由策略,相比于SPR4T能够有效减少路由器流水线级数、提高数据转发效率,从而实现了更低的延迟和更高的吞吐量. 尽管该类防死锁方法能够根据数据包目的地址将所有的数据传输分为3类,并且每类中的数据传输独占各自的缓冲区,有效地防止协议级死锁. 但是LA4T没有考虑不同传输类之间的潜在数据干扰以及同类之间的缓冲区竞争问题. HamSPR相比于其他3种方法表现了更优的性能,这主要受益于高效的“环流传输”策略. HamSPR采用了以下4种策略保障了网络中数据包能够沿着环流快速地传输:1)根据数据包经历的最大哈密顿边层次为其分配独立的存储转发缓冲区,避免了不同缓冲区之间的数据传输干扰;2)对同一缓冲区的不同数据传输划分了传输方向并分配独立的虚拟通道,避免同一缓冲区内数据传输对虚拟通道的竞争;3)路由器采用全局时钟同步策略,保证了环流中的数据同步向前传输;4)在每个缓冲区中设置了空槽,从而确保即使在负载较高的情况下环流依然能够正常的运行.
相比于Table,SPR4T,LA4T方法,HamSPR在4种流量模式下分别实现了18.18% ~ 65.40%的平均数据包延迟降低以及8.00%~59.17%的吞吐量提升. 另外,除了HamSPR方法,在bit-complement流量下的其他算法均表现出了较低的吞吐量,其原因是数据包在网络中出现了较高的等待延迟. 当尝试将死锁阈值修改为文献[46]中的128周期时,其他3种算法在较高的注入率(大于0.8)就会因数据包等待周期超过死锁阈值而产生死锁. 在uniform-random流量模式下,当注入率超过0.9时HamSPR的吞吐量呈现出了下降的趋势,其原因可能是在有限的缓冲区数量下当向网络中注入的数据包超过网络的饱和值时,哈密顿环流中传递的数据包一直处于满载的状态,此时需要等待环流中出现新的空闲缓冲区才能向其中注入新的数据包,从而导致网络的吞吐量略微降低.
从图14中能够发现,每个程序的性能改进并不相同,这与各个程序的通信模式相关[45]. HamSPR在通信密集型的程序中表现出了较明显的性能优势,例如在canneal程序中与其他3种算法相比,HamSPR分别降低了8.60%,12.72%,2.84%的程序运行时间. 而对于像streamcluster和x264类型的程序,它们要么在多个CPU之间表现出高通信需求(高负载),要么在短时间内产生更多的网络流量(突发流量),使其性能变化较明显,相比于基线分别降低了13.20%和14.90%的运行时间. HamSPR相比于其他算法的性能优势可归因于2点:1)HamSPR中的不同哈密顿环之间相互独立,减少了不同数据包之间的相互干扰,提高了数据传输速度;2)哈密顿环中的各个数据包同步向前传输,避免了因前方缓冲区被占用而出现等待的现象,降低了数据包之间的等待延迟.
从互连网络中获得较明显的性能改进的应用程序往往与较低的数据包延迟和平均数据包跳数有关[30]. 如图14和图15所示,HamSPR相比于其他算法在平均数据包延迟和平均数据包跳数方面分别实现了平均22.20%和16.11%的降低. 由于HamSPR采用了同步哈密顿环的数据传输方式,与其他路由算法相比不需要费时地查找路由表操作,并且在每一次转发时不需要相对复杂的计算步骤,其采用的高效的同步传输机制和独立的数据传输方式使其能够实现较快的数据传输. 因此,相比于其他算法,HamSPR能够有效提高数据传输效率,与基线x264相比最高可实现42.75%的平均数据包延迟降低. 此外,由于受到应用程序通信模式的影响,HamSPR在部分应用程序上表现出了与其他路由算法相同或略高的平均数据包延迟,例如blackscholes 和swaptions. 这可能是由于当应用程序的通信密度较低、通信之间的干扰较小,并且对于缓冲区的竞争不高时,整个网络处于未饱和的状态. 因此不能完全发挥出基于哈密顿环的数据传输方式的优势,导致在平均数据包延迟上HamSPR与其他路由算法基本保持一致.
为了进一步分析基于HamSPR算法的TriBA架构性能,在一个包含9个核心的网络配置中比较了使用X-Y和West-first算法的2D-Mesh(Mesh-XY,Mesh-West-first)和使用HamSPR算法的TriBA(TriBA-HamSPR)在运行PARSEC测试集下的性能. X-Y和West-first算法作为2D-Mesh典型的无死锁分布式确定性和自适应路由算法,被广泛地研究和使用[47-48]. 图16展示了Mesh-XY,Mesh-West-first,TriBA-HamSPR在运行不同应用程序时的性能比较. 对于各种应用程序,TriBA-HamSPR相对于Mesh-XY和Mesh-West-first在程序运行时间和平均数据包延迟方面分别实现了1.00% ~ 10.04%和5.34 %~ 20.32%的降低,特别在通信密集型应用程序(如dedup和swaptions)中尤为显著. 这主要归因于TriBA拓扑具有的哈密顿特性和旋转变换特性[3]. 基于哈密顿的路由算法在解决潜在的死锁问题的同时能够借助哈密顿环流实现较高的通信速率,而特有的旋转对称性降低了路由的复杂性和计算负载[3],在一定程度上提高了数据包的传输效率.
在SE模式下,测试了HamSPR相比其他算法在不同网络规模下的平均数据包延迟和吞吐量的性能变化情况,如表3所示. 其中平均数据包延迟的降低和吞吐量的提升分别为4种不同流量模式下的平均值. 从表3中的方差数值可知,随着网络规模的变化,HamSPR算法相比于Table,SPR4T,LA4T算法在平均数据包延迟和吞吐量上的性能变化并未发生较大的波动,即HamSPR及其防死锁原理的网络性能并未受到网络规模的较大影响,具有良好的可扩展性.
在本节中,利用DSENT在11 nm工艺技术下评估了NoC中路由器和链路的总功耗以及路由器的面积. 图17(a)展示了4种路由算法在4种流量模式下的归一化平均数据包功耗,相比于基线(Table算法),HamSPR在4种不同注入率下的平均数据包功耗实现了平均19.16%的降低. 以上功耗的降低可归因于HamSPR能够借助哈密顿环流实现更高的数据包传输速度,从而随着注入率的增加能够获得比其他算法更优的吞吐量. HamSPR在PARSEC基准测试集下的平均数据包功耗几乎等于或者小于其他3种算法,如图17(b)所示. 这表明在运行相同的应用程序时,本文设计的基于同步哈密顿环的无死锁策略即使同时采用了不同的方案来消除潜在的路由级死锁和协议级死锁,也没有因此给整个网络带来明显的功耗增加.
NoC中的路由器主要由缓冲区、交叉开关、交换分配器、路由计算等功能模块组成. 通过使用DSENT计算TriBA架构在GEM5中的路由器面积可知,缓冲区占据了整个路由器面积的67.67%,交叉开关和交换分配器分别占据了路由器面积的19.36%和3.27%,而其余组件(消息处理单元等)共同占据了剩余9.70%的面积. 相比于Table,SPR4T,LA4T算法,HamSPR的BVSC计算单元通过增加计算和逻辑电路以实现缓冲区及虚拟通道的选择和控制,导致路由器面积相比于其他算法平均增加了约1.50%. 考虑到HamSPR整体性能优势,额外的面积开销所带来的影响是可以接受的.
本文针对具有哈密顿特性的基三众核架构提出了基于同步哈密顿环的无死锁路由策略,该策略能够将网络中的数据传输根据其所经历的最大哈密顿边层次进行分组,并且组内的数据传输独用各自的传输通道,同时结合了全局时钟同步和局部类气泡流控方法,这样做具有以下好处:1)不同组间的数据传输相互独立,避免了不同类型数据传输的相互干扰和资源竞争,在解决潜在的协议级死锁的同时提高了数据传输速度;2)不同组内的数据传输独用各自的虚拟通道且同步向前传输,避免了同一组内前后数据传输因竞争缓冲区而产生的路由级死锁,并降低了数据传输延迟;3)由于是从拓扑结构自身出发设计的死锁解决方案,因此对于任何的流量场景不需做任何的优化即可解决死锁,不影响架构的通用性. GEM5仿真实验结果表明,本文所提出的方法与TriBA中现有的解决方案以及采用X-Y和West-first无死锁路由的2D-Mesh架构相比均具有明显的性能优势. 本文工作进一步提高了TriBA-NoC架构的通信性能和可用性,使其更具潜力应用在未来的MPSoC上. 此外,由于在其他众多拓扑结构中,如2D-Mesh,Torus等都存在哈密顿特性,因此本文提出的方法对于其他众核架构,如Godson-T同时解决同类问题具有较高的借鉴意义.
另外,本文提出的基于同步哈密顿环的无死锁策略还有需要完善的地方:1)目前该策略面向拓扑已知的TriBA架构,影响了其适用性;2)对于大型或者超大型规模的网络,需要较多的缓冲区资源. 未来将做3点改进:1)修改当前的对称轴、缓冲区判断等算法,使其能够适用于任何具有哈密顿特性的多核架构;2)采用转注策略,动态调整网络的拥塞程度,最小化使用缓冲区资源;3)识别故障链路,并借鉴循环网络中的容错机制以避开故障链路,提高网络的容错性.
作者贡献声明:李春峰提出研究思路、设计算法和实验方案、进行实验验证和数据分析,并撰写和修改论文;Karim Soliman 参与实验验证和数据分析;计卫星参与论文审阅与修订;石峰负责全文结构设计与指导,并审阅与修订论文.

参考文献 引证文献
排序方式:
1
Yazdanpanah F, Afsharmazayejani R. A systematic analysis of power saving techniques for wireless network-on-chip architectures[J]. Journal of Systems Architecture, 2022, 126: 102485
2
Della Vecchia G, Sanges C. A recursively scalable network VLSI implementation[J]. Future Generation Computer Systems, 1988, 4(3): 235−243
3
石峰,陈旭,尹飞,等. 基于 S3 变换的 TriBA-Net 最短路径路由机制[J]. 中国科学:信息科学,2018,48(1):100−114
Shi Feng, Chen Xu, Yin Fei, et al. A shortest path routing mechanism based on S3 for TriBA-Net[J]. SCIENTIA SINICA Informationis, 2018, 48(1): 100−114 (in Chinese)
4
张洋,王达,叶笑春,等. 众核处理器片上网络的层次化全局自适应路由机制[J]. 计算机研究与发展,2016,53(6):1211−1220
Zhang Yang, Wang Da, Ye Xiaochun, et al. A global hierarchical adaptive routing mechanism in many-core processor network-on-chip[J]. Journal of Computer Research and Development, 2016, 53(6): 1211−1220 (in Chinese)
5
Feng Yinxiao, Xiang Dong, Ma Kaisheng. Heterogeneous die-to-die interfaces: Enabling more flexible chiplet interconnection systems[C]//Proc of the 56th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2023: 930−943
6
Bakhouya M, Suboh S, Gaber J, et al. Analytical performance comparison of 2D mesh, wk-recursive, and spidergon nocs [C/OL]//Proc of the 19th IEEE Int Symp on Parallel &amp; Distributed Processing, Workshops and Phd Forum (IPDPSW). Piscataway, NJ: IEEE, 2010[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/5470784
7
石峰,魏增辉,王一拙,等. 一种多/众核架构TriBA-CMPs的布局布线方案tMesh:中国,CN107526894A[P]. 2017-12-29
Shi Feng, Wei Zenghui, Wang Yizhuo, et al. A layout and routing scheme named tMesh for a multi/many-core architecture TriBA-CMPs: China, CN107526894A[P]. 2017-12-29 (in Chinese)
8
Braham C C, Ji Weixinga, Zhang Lingyu. The design and implementation of a hierarchical network on chip[J]. Procedia Engineering, 2012, 29: 2966−2974
9
Feng Shi, Yang Zhang. Design and evaluation of low-latency and shortest-path routing algorithm for triplet-based hierarchical interconnection network[J]. Journal of Testing and Evaluation, 2013, 41(4): 541−550
10
Khan HUR, Shi Feng, Ji Weixing, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29): 3363−3371
11
Wang Zuo, Zuo Qi, Li Jiaxin. Triplet-based topology for on-chip networks[J]. WSEAS Transactions on Computers, 2009, 8(3): 516−525
12
Xue Licheng, Shi Feng, Ji Weixing. 3D floorplanning of low-power and area-efficient network-on-chip architecture[J]. Microprocessors and Microsystems, 2011, 35(5): 484−495
13
Zhang Yang, Shi Feng, Zuo Qi, et al. Express router microarchitecture for triplet-based hierarchical interconnection network[C]//Proc of the 14th IEEE Int Conf on High Performance Computing and Communication &amp; 9th IEEE Int Conf on Embedded Software and Systems. Piscataway, NJ: IEEE, 2012: 295−302
14
Wang Xiaojun, Shi Feng, Zhang Hong. KLSAT: An application mapping algorithm based on Kernighan–Lin partition and simulated annealing for a specific WK-recursive NoC architecture[C]//Proc of the 16th IFIP WG 10.3 Int Conf on Network and Parallel Computing. Berlin: Springer, 2019: 31−42
15
Zhang Hong, Wang Xiaojun. KGT: An application mapping algorithm based on Kernighan–Lin partition and genetic algorithm for WK-recursive NoC architecture[C]//Proc of the 17th Int Conf on Intelligent Computing Theories and Application (ICIC). Berlin: Springer, 2021: 86−101
16
Shi Feng, Li Jiaxin, Bai Ziru. Performance of triplet-based interconnection strategy for multi-core on-chip processors[C]//Proc of the 11th IEEE Int Conf on High Performance Computing and Communications. Piscataway, NJ: IEEE, 2009: 163−170
17
Wang Xiaojun, Shi Feng, Zhang Hong. A novel speedup evaluation for multicore architecture based topology of on-chip memory[C]//Proc of the 10th Int Symp on Parallel Architectures, Algorithms and Programming. Berlin: Springer, 2019: 35−47
18
Feng Yinxiao, Xiang Dong, Ma Kaishen. A scalable methodology for designing efficient interconnection network of chiplets [C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1059−1071
19
Kasan H, Kim J. VVQ: Virtualizing virtual channel for cost-efficient protocol deadlock avoidance[C]//Proc of the 2023 IEEE Int Symp on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2023: 1072−1084
20
Romanov A Y, Myachin N M, Lezhnev E V, et al. Ring-Split: Deadlock-free routing algorithm for circulant networks on chip[J]. Micromachines, 2023, 14(1): 141
21
Kwauk G, Kang S, Kasan H, et al. Boomgate: Deadlock avoidance in non-minimal routing for high-radix networks[C]//Proc of the 2021 IEEE Int Sym on High-Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2021: 696−708
22
Flich J, Skeie T, Mejia A, et al. A survey and evaluation of topology-agnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(3): 405−425
23
Wu Yibo, Wang Liang, Wang Xiaohang, et al. A deflection-based deadlock recovery framework to achieve high throughput for faulty NoCs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(10): 2170−2183
24
Razavi S, Sarbazi-Azad H. The triangular pyramid: Routing and topological properties[J]. Information Sciences, 2010, 180(11): 2328−2339
25
Wang Nengchung, Yen Chengpang, Chu Chihping. Multicast communication in wormhole-routed symmetric networks with Hamiltonian cycle model[J]. Journal of Systems Architecture, 2005, 51(3): 165−183
26
El-Obaid A. Three-dimension Hamiltonian broadcast wormhole-routing[J]. International Journal of Computer Networks & Communications, 2015, 7(3): 31−46
27
Chen Xu, Shi Feng, Yin Fei, et al. An efficient distributed minimal routing algorithm for triplet-based WK-recursive network[C]//Proc of the 20th IEEE Int Conf on High Performance Computing and Communications; 16th IEEE Int Conf on Smart City; 4th IEEE Int Conf on Data Science and Systems (HPCC/SmartCity/DSS). Piscataway, NJ: IEEE, 2018: 547−554
28
Fan Dongrui, Zhang Hao, Wang Da, et al. Godson-T: An efficient many-core processor exploring thread-level parallelism[J]. IEEE Micro, 2012, 32(2): 38−47
29
Parasar M, Farrokhbakht H, Jerger N E, et al. DRAIN: Deadlock removal for arbitrary irregular networks[C]//Proc of the 2020 IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2020: 447−460
30
Dally W J, Towles B P. Principles and Practices of Interconnection Networks[M]. Amsterdam: Elsevier, 2004
31
Ramey C. Tile-GX100 manycore processor: Acceleration interfaces and architecture[C/OL]//Proc of the 23rd IEEE on Hot Chips Symp. Piscataway, NJ: IEEE, 2011[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/7477491
32
Wentzlaff D, Griffin P, Hoffmann H, et al. On-chip interconnection architecture of the tile processor[J]. IEEE Micro, 2007, 27(5): 15−31
33
Sodani A, Gramunt R, Corbal J, et al. Knights landing: Second-generation intel Xeon Phi product[J]. IEEE Micro, 2016, 36(2): 34−46
34
Rahman R. Intel Xeon Phi Coprocessor Architecture and Tools: The Guide for Application Developers[M]. Berlin: Springer, 2013
35
Qiao Baojun, Shi Feng, Ji Weixing. A new hierarchical interconnection network for multi-core processor[C]//Proc of the 2nd IEEE Conf on Industrial Electronics and Applications. Piscataway, NJ: IEEE, 2007: 246−250
36
Wang Zuo, Shi Feng. A shortest path routing algorithm in triplet-based network[J]. Transactions of Beijing Institute of Technology, 2009, 29(5): 410−414
37
Zhang Yang, Shi Feng, Ji Weixing, et al. SPORT: A shortest path routing algorithm for triplet-based hierarchical interconnection[J]. Transactions of Beijing institute of Technology, 2013, 33(1): 57−61
38
Chen Xu, Shi Feng, Yin Fei, et al. A novel look-ahead routing algorithm based on graph theory for triplet-based network-on-chip router[J]. IEICE Electronics Express, 2018, 15(8): 1−12
39
石峰,阮生强,尹飞,等. 基于尖端子图分类传输数据的基三核间网络防死锁方法:中国,CN112698960B[P]. 2022-08-09
Shi Feng, Ruan Shenqiang, Yin Fei, et al. A deadlock prevention method for inter-core networks based on apex-subgraph classification for data transmission in triplet-based architecture: China, CN112698960B[P]. 2022-08-09 (in Chinese)
40
Tutte W T. Graph Theory[M]. Cambridge, UK: Cambridge University Press, 2001
41
Levine G N. The classification of deadlock prevention and avoidance is erroneous[J]. ACM SIGOPS Operating Systems Review, 2005, 39(2): 47−50
42
Binkert N, Beckmann B, Black G, et al. The GEM5 simulator[J]. ACM SIGARCH Computer Architecture News, 2011, 39(2): 1−7
43
Bharadwaj S, Yin J, Beckmann B, et al. Kite: A family of heterogeneous interposer topologies enabled via accurate interconnect modeling[C/OL]//Proc of the 57th ACM/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2020[2024-05-22]. https://ieeexplore.ieee.org/abstract/document/9218539
44
Sun Cheng, Chen C H O, Kurian G, et al. DSENT―A tool connecting emerging photonics with electronics for opto-electronic networks-on-chip modeling[C]//Proc of the 6th IEEE/ACM Int Symp on Networks-on-Chip. Piscataway, NJ: IEEE, 2012: 201−210
45
Zhan Xusheng, Bao Yungang, Bienia C, et al. PARSEC3.0: A multicore benchmark suite with network stacks and SPLASH-2X[J]. ACM SIGARCH Computer Architecture News, 2017, 44(5): 1−16
46
Parasar M, Jerger N E, Gratz P V, et al. SWAP: Synchronized weaving of adjacent packets for network deadlock resolution[C]//Proc of the 52nd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2019: 873−885
47
Joshi B, Thakur M K. Genetic algorithm-and cuckoo search algorithm-based routing optimizations in network-on-chip[J]. Arabian Journal for Science and Engineering, 2023, 48(8): 9635−9644
48
Luo Yaoying, Meyer M C, Jiang Xin, et al. A hotspot-pattern-aware routing algorithm for networks-on-chip[C]//Proc of the 13th IEEE Int Symp on Embedded Multicore/Many-core Systems-on-Chip (MCSoC). Piscataway, NJ: IEEE, 2019: 229−235
2025年第62卷第4期
112
52
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202331042
  • 接收时间:2023-12-25
  • 首发时间:2026-11-10
  • 出版时间:2025-04-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2023-12-25
  • 修回日期:2024-08-12
  • 录用日期:2024-09-03
基金
作者信息
    1北京理工大学计算机学院 北京 100081
    2北京师范大学人工智能学院 北京 100875

通讯作者:

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

扫描看全文

引用本文
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
关闭全屏