Article(id=1329381561658618522, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329381463562236291, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202220730, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1661097600000, receivedDateStr=2022-08-22, revisedDate=1681833600000, revisedDateStr=2023-04-19, acceptedDate=null, acceptedDateStr=null, onlineDate=1794878863013, onlineDateStr=2026-11-17, pubDate=1704124800000, pubDateStr=2024-01-02, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794878863013, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794878863013, creator=13701087609, updateTime=1794878863013, updator=13701087609, issue=Issue{id=1329381463562236291, tenantId=1146029695717560320, journalId=1324759914146529478, year='2024', volume='61', issue='1', pageStart='1', pageEnd='270', issueExtLink='null', onlineDate='null', pubDate='1704124800000', pubDateStr='2024-01-02', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794878839626, creator='13701087609', updateTime=1794899256120, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1329467096993477032, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329381463562236291, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1329467096997671337, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329381463562236291, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=98, endPage=119, ext={EN=ArticleExt(id=1329381561948025499, articleId=1329381561658618522, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Design and Analysis Method of TTI Program Based on RPU, columnId=1327010444570637032, journalTitle=Journal of Computer Research and Development, columnName=Computer Achitecture, runingTitle=null, highlight=null, articleAbstract=

Real-time embedded system (RTES) needs to guarantee not only logical correctness of the calculation results, but also temporal correctness of the interaction with outside world, so low-level programs must be able to accurately express time behavior in upper-level models. TTI instruction set (time-triggered instruction set) is proposed to try to solve the problem of the lack of timing semantics at the computer instruction set architecture level, and the realization of real-time processing unit (RPU) based on TTI instruction set proves the feasibility and effectiveness of TTI instruction set. However, the current work lacks research on design and analysis method of TTI program. Therefore, based on TTI instruction set and RPU, we propose four types of timing semantics that TTI instruction set can express, give the design paradigm of TTI program. Then, we define the representation of TTI program time behavior — TFG+, which is an extension of TFG. TFG+ distinguishes timing semantic instructions and the common code segments in the TTI program, and TFG+ can represent the control flow information of TTI program, the time behavior specified by the user, and the time attributes related to hardware platform. Finally, we propose time analysis method of TTI program and time safety checking method, which provide the basis for the design and deployment of TTI program.

, authors=Yinkang Gao, Xianglan Chen, Xiaohang Gong, Binze Jiang, Xi Li*, Xuehai Zhou, authorsList=Yinkang Gao, Xianglan Chen, Xiaohang Gong, Binze Jiang, Xi Li, Xuehai Zhou, authorCompany=null, correspAuthors=Xi Li, authorNote=

born in 1998. Master candidate. His main research interest includes computer architecture

born in 1977. PhD. Her main research interest includes system software

born in 1999. Master candidate. His main research interest includes computer architecture

born in 2000. Master candidate. His main research interest includes computer architecture

born in 1963. Professor. His main research interest includes computer architecture

born in 1966. Professor. His main research interest includes computer architecture

, correspAuthorsNote=null, copyrightStatement=Copyright © 2024 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=1329381569074148059, articleId=1329381561658618522, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=基于RPU的TTI程序设计和分析方法, columnId=1325489904427344387, journalTitle=计算机研究与发展, columnName=体系结构, runingTitle=null, highlight=null, articleAbstract=

实时嵌入式系统不仅要保证计算结果的逻辑正确性,还要确保与外界交互的时序正确性,所以底层程序要能精确表达上层模型中的时间行为. TTI指令集(time-triggered instruction set)的提出尝试解决计算机指令集体系结构层次缺少时间语义的问题,并且基于TTI指令集实现的实时处理单元(real-time processing unit,RPU)证明了TTI指令集的可行性和有效性. 但是目前的工作缺少对于TTI程序设计和分析方法的研究. 所以,基于TTI指令集和RPU,提出了TTI指令集可以表达的4种时间语义,给出了TTI程序的设计范式. 并且构建了TTI程序时间行为的表示方法——TFG+,TFG+是对TFG的扩展,TFG+区分了TTI程序中时间语义指令和普通代码段,可以表示TTI程序的控制流信息、用户规定的时间行为和TTI程序平台相关的时间属性. 最后,提出了TTI程序的时间分析方法以及时间安全性检查方法,为TTI程序的设计和部署提供了依据.

, authors=高银康, 陈香兰, 龚小航, 蒋滨泽, 李曦*, 周学海, authorsList=高银康, 陈香兰, 龚小航, 蒋滨泽, 李曦, 周学海, authorCompany=null, correspAuthors=李曦, authorNote=

1998年生. 硕士研究生. 主要研究方向为计算机系统结构

1977年生. 博士. 主要研究方向为系统软件

1999年生. 硕士研究生. 主要研究方向为计算机系统结构

2000年生. 硕士研究生. 主要研究方向为计算机系统结构

1963年生. 教授. 主要研究方向为计算机系统结构

1966年生. 教授. 主要研究方向为计算机系统结构

, correspAuthorsNote=
李曦()
, copyrightStatement=版权所有 © 2024 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=csHVJ8nXxIXKYg41/yENZw==, magXml=9jPdtzRkF4gJIVc3C8YTgw==, pdfUrl=null, pdf=ofbMyS4sGKxImQAMeOZV9Q==, pdfFileSize=3829487, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=wf1A7eENSJ/0syOXUHxupg==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=M7PZkfa4pk73bOIdvvkVXQ==, mapNumber=null, fund=null)}, authors=[Author(id=1329381569455829731, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=gaoyinkang@mail.ustc.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329381569522938596, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569455829731, language=EN, stringName=Yinkang Gao, firstName=Yinkang, middleName=null, lastName=Gao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1998. Master candidate. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1998. Master candidate. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381569585853157, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569455829731, language=CN, stringName=高银康, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"lU6i7oQHfY+qeJSNp7dAag==","content":"

1998年生. 硕士研究生. 主要研究方向为计算机系统结构

"}, bioImg=lU6i7oQHfY+qeJSNp7dAag==, bioContent=

1998年生. 硕士研究生. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381569652962023, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=1329381569736848105, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569652962023, language=EN, stringName=Xianglan Chen, firstName=Xianglan, middleName=null, lastName=Chen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1977. PhD. Her main research interest includes system software

"}, bioImg=null, bioContent=

born in 1977. PhD. Her main research interest includes system software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381569820734186, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569652962023, language=CN, stringName=陈香兰, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"CmPB7rxjRqbZjp4c1yvWQw==","content":"

1977年生. 博士. 主要研究方向为系统软件

"}, bioImg=CmPB7rxjRqbZjp4c1yvWQw==, bioContent=

1977年生. 博士. 主要研究方向为系统软件

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381569892037356, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=1329381569967534829, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569892037356, language=EN, stringName=Xiaohang Gong, firstName=Xiaohang, middleName=null, lastName=Gong, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1999. Master candidate. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1999. Master candidate. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570043032302, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569892037356, language=CN, stringName=龚小航, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"nZqECxjAgbxMh5GJFD90cg==","content":"

1999年生. 硕士研究生. 主要研究方向为计算机系统结构

"}, bioImg=nZqECxjAgbxMh5GJFD90cg==, bioContent=

1999年生. 硕士研究生. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381570110141168, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329381570181444337, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570110141168, language=EN, stringName=Binze Jiang, firstName=Binze, middleName=null, lastName=Jiang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 2000. Master candidate. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 2000. Master candidate. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570252747506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570110141168, language=CN, stringName=蒋滨泽, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"hR4XQwe1XR7co1XfWl4IqQ==","content":"

2000年生. 硕士研究生. 主要研究方向为计算机系统结构

"}, bioImg=hR4XQwe1XR7co1XfWl4IqQ==, bioContent=

2000年生. 硕士研究生. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381570357605108, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=llxx@ustc.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329381570420519669, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570357605108, language=EN, stringName=Xi Li, firstName=Xi, middleName=null, lastName=Li, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1963. Professor. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1963. Professor. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570491822838, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570357605108, language=CN, stringName=李曦, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"3kpefHFcc8ZRkOsoxAksMQ==","content":"

1963年生. 教授. 主要研究方向为计算机系统结构

"}, bioImg=3kpefHFcc8ZRkOsoxAksMQ==, bioContent=

1963年生. 教授. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381570567320312, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=5, 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=1329381570630234873, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570567320312, language=EN, stringName=Xuehai Zhou, firstName=Xuehai, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1966. Professor. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1966. Professor. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570697343738, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570567320312, language=CN, stringName=周学海, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"tRfUtmdqOpH9O28NjtUwtg==","content":"

1966年生. 教授. 主要研究方向为计算机系统结构

"}, bioImg=tRfUtmdqOpH9O28NjtUwtg==, bioContent=

1966年生. 教授. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null)], keywords=[Keyword(id=1329381570793812731, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, orderNo=1, keyword=real-time embedded system (RTES)), Keyword(id=1329381570877698812, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, orderNo=2, keyword=timing predictability), Keyword(id=1329381570953196285, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, orderNo=3, keyword=timed instruction set), Keyword(id=1329381571037082366, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, orderNo=4, keyword=real-time processor), Keyword(id=1329381571104191231, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, orderNo=5, keyword=WCET analysis), Keyword(id=1329381571158717184, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, orderNo=1, keyword=实时嵌入式系统), Keyword(id=1329381571230020353, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, orderNo=2, keyword=时间可预测性), Keyword(id=1329381571288740610, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, orderNo=3, keyword=时间语义指令集), Keyword(id=1329381571397792515, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, orderNo=4, keyword=实时处理器), Keyword(id=1329381571456512772, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, orderNo=5, keyword=WCET分析)], refs=[Reference(id=1329381580214219586, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=Henzinger T, Horowitz B, Kirsch C. Giotto: A time-triggered language for embedded programming[C]// Proc of the 1st EMSOF. New York: ACM, 2001: 166−184, articleTitle=null, refAbstract=null), Reference(id=1329381580306494275, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=Bui D, Lee E, Liu I, et al. Temporal isolation on multiprocessing architectures[C]// Proc of the 48th Design Automation Conf. New York: ACM, 2011: 274−279, articleTitle=null, refAbstract=null), Reference(id=1329381580373603140, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=Lee E, Reineke J, Zimmer M. Abstract PRET machines[C]// Proc of the 38th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 2017: 1−11, articleTitle=null, refAbstract=null), Reference(id=1329381580465877829, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=汪超,陈香兰,章博,等. 一种具有时间语义的实时处理器模型[J]. 计算机研究与发展,2021,58(6):1176−1191, articleTitle=null, refAbstract=null), Reference(id=1329381580587512646, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=Wang Chao, Chen Xianglan, Zhang Bo, et al. A real-ime processor model with timing semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176−1191 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329381580663010119, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Natarajan S, Broman D. Timed C: An extension to the C programming language for real-time systems[C]// Proc of the 24th IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2018: 227−239, articleTitle=null, refAbstract=null), Reference(id=1329381580734313288, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Natarajan S, Broman D. Temporal property-based testing of a timed C compiler using time-flow graph semantics[C/OL]// Proc of the 23rd Forum for Specification and Design Languages. Piscataway, NJ: IEEE, 2020 [2023-02-24].https://doi.org/10.1109/FDL50818.2020.9232935, articleTitle=null, refAbstract=null), Reference(id=1329381580801422153, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Rochange C, Sainrat P. A context-parameterized model for static analysis of execution times[M]// Transactions on High-Performance Embedded Architectures and Compilers II. Berlin: Springer, 2009: 222−241, articleTitle=null, refAbstract=null), Reference(id=1329381580872725322, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Lee E. What is real time computing? A personal view[J]. IEEE Design and Test, 2018, 35(2): 64−72, articleTitle=null, refAbstract=null), Reference(id=1329381580931445579, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Lickly B, Liu I, Kim S, et al. Predictable programming on a precision timed architecture[C]// Proc of the 11th Int Conf on Compilers, Architectures and Synthesis for Embedded Systems. New York: ACM, 2008: 137−146, articleTitle=null, refAbstract=null), Reference(id=1329381580990165836, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Zimmer M, Broman D, Shaver C, et al. FlexPRET: A processor platform for mixed-criticality systems[C]// Proc of the 19th 2014 IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2014: 101−110, articleTitle=null, refAbstract=null), Reference(id=1329381581053080397, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Turing A M. On computable numbers, with an application to the entscheidung sproblem[J]. Proceedings of the London Mathematical Society, 1937, 2(1): 230−265, articleTitle=null, refAbstract=null), Reference(id=1329381581120189262, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Von Neumann J. First draft of a report on the EDVAC[J]. IEEE Annals of the History of Computing, 1993, 15(4): 27−75, articleTitle=null, refAbstract=null), Reference(id=1329381581183103823, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Knial P, Mokrushin L, Thiagarajan P S, et al. Timed vs time-triggered automata[C]// Proc of the 15th Int Conf on Concurrency Theory. Berlin: Springer, 2004: 340−354, articleTitle=null, refAbstract=null), Reference(id=1329381581246018384, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Waterman A S. Design of the RISC-V instruction set architecture[D]. Berkeley, CA: University of California, Berkeley, 2016, articleTitle=null, refAbstract=null), Reference(id=1329381581334098769, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Hennessy J L, Patterson D A. Computer Architecture: A quantitative Approach[M]. San Francisco: Margan Kaufmann, 2011, articleTitle=null, refAbstract=null), Reference(id=1329381581405401938, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Boldt M, Traulsen C, von Hanxleden R. Worst case reaction time analysis of concurrent reactive programs[J]. Electronic Notes in Theoretical Computer Science, 2008, 203(4): 65−79, articleTitle=null, refAbstract=null), Reference(id=1329381581480899412, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Berry G, Gonthier G. The Esterel synchronous programming language: Design, semantics, implementation[J]. Science of Computer Programming, 1992, 19(2): 87−152, articleTitle=null, refAbstract=null), Reference(id=1329381581564785494, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Andalam S, Roop P, Girault A, et al. PRET-C: A new language for programming precision timed architectures[D]. Grenoble, France: Institut National de Recherche en Informatique et en Automatique, 2009, articleTitle=null, refAbstract=null), Reference(id=1329381581673837399, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Roop P S, Andalam S, von Hanxleden R, et al. Tight WCRT analysis of synchronous C programs[C]// Proc of the 12th Int Conf on Compilers, Architecture, and Aynthesis For Embedded Systems. New York: ACM, 2009: 205−214, articleTitle=null, refAbstract=null), Reference(id=1329381581732557656, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Cooper K D, Harvey T J, Waterman T. Building a control-flow graph from scheduled assembly code[R]. Texas: Rice University, 2002, articleTitle=null, refAbstract=null), Reference(id=1329381581820638041, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Kirner R, Knoop J, Prantl A, et al. WCET analysis: The annotation language challenge[C]// Proc of the 7th Int Workshop on Worst-Case Execution Time Analysis. Schloss Dagstuhl: Leibniz-Zentrum für Informatik, 2007: 83−99, articleTitle=null, refAbstract=null), Reference(id=1329381581925495642, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Asavoae M, Maiza C, Raymond P. Program semantics in model-based WCET analysis: A state of the art perspective[C]// Proc of the 13th Int Workshop on Worst-Case Execution Time Analysis. Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, 2013: 32−41, articleTitle=null, refAbstract=null), Reference(id=1329381581988410203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Cousot P, Cousot R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints[C]// Proc of the 4th ACM SIGACT-SIGPLAN Symp on Principles of Programming Languages. New York: ACM, 1977: 238−252, articleTitle=null, refAbstract=null), Reference(id=1329381582042936156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Fields B, Rubin S, Bodik R. Focusing processor policies via critical-path prediction[C]// Proc of the 28th Annual International Symp on Computer Architecture. Piscataway, NJ: IEEE, 2001: 74−85, articleTitle=null, refAbstract=null), Reference(id=1329381582097462109, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Li Xianfeng, Roychoudhury A, Mitra T. Modeling out-of-order processors for WCET analysis[J]. Real-Time Systems, 2006, 34(3): 195−227, articleTitle=null, refAbstract=null), Reference(id=1329381582168765278, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Ferdinand C, Heckmann R. aiT: Worst-case Execution Time Prediction by Static Program Analysis[M]// Building the Information Society. Berlin: Springer, 2004: 377−383, articleTitle=null, refAbstract=null), Reference(id=1329381582244262751, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Li Xianfeng, Liang Yun, Mitra T, et al. Chronos: A timing analyzer for embedded software[J]. Science of Computer Programming, 2007, 69(1/2/3): 56−67, articleTitle=null, refAbstract=null), Reference(id=1329381582298788704, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Allabriga C, Cassé H, Rochange C, et al. OTAWA: An open toolbox for adaptive WCET analysis[C]//Proc of the 8th IFIP Int Workshop on Software Technolgies for Embedded and Ubiquitous Systems. Berlin: Springer, 2010: 35−46, articleTitle=null, refAbstract=null), Reference(id=1329381582361703265, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Puschner P, Koza C. Calculating the maximum execution time of real-time programs[J]. Real-Time Systems, 1989, 1(2): 159−176, articleTitle=null, refAbstract=null), Reference(id=1329381582433006434, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Shaw A C. Reasoning about time in higher-level language software[J]. IEEE Transactions on Software engineering, 1989, 15(7): 875−889, articleTitle=null, refAbstract=null), Reference(id=1329381582495920995, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Li Y T S, Malik S. Performance analysis of embedded software using implicit path enumeration[C]// Proc of the 1st ACM SIGPLAN 1995 Workshop on Languages, Compilers, & Tools For Real-Rime Rystems. New York: ACM , 1995: 88−98, articleTitle=null, refAbstract=null), Reference(id=1329381582558835556, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Lawes J. Car Brakes: A Guide to Upgrading, Repair and Maintenance[M]. Marlborough, UK: The Crowood Press, 2014, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329381569279668956, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, xref=null, ext=[AuthorCompanyExt(id=1329381569288057565, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, companyId=1329381569279668956, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027), AuthorCompanyExt(id=1329381569296446174, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, companyId=1329381569279668956, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=中国科学技术大学计算机科学与技术学院 合肥 230027)]), AuthorCompany(id=1329381569367749343, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, xref=null, ext=[AuthorCompanyExt(id=1329381569380332256, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, companyId=1329381569367749343, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Suzhou Institute for Advanced Research, University of Science and Technology of China, Suzhou, Jiangsu 215004), AuthorCompanyExt(id=1329381569388720865, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, companyId=1329381569367749343, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=中国科学技术大学苏州高等研究院 江苏苏州 215004)])], figs=[ArticleFig(id=1329381571590730501, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 1, caption=Example of execution cost, figureFileSmall=GWjKxBRa27twRqBxL9bSAQ==, figureFileBig=wf1A7eENSJ/0syOXUHxupg==, tableContent=null), ArticleFig(id=1329381571662033670, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图1, caption=执行开销示例, figureFileSmall=GWjKxBRa27twRqBxL9bSAQ==, figureFileBig=wf1A7eENSJ/0syOXUHxupg==, tableContent=null), ArticleFig(id=1329381571875943175, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 2, caption=Example of absolute timed semantic, figureFileSmall=9FJ0ZlXvfCdENyeJtMmVQw==, figureFileBig=XllgybyTKyHFBhn9UJTXjQ==, tableContent=null), ArticleFig(id=1329381571943052040, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图2, caption=绝对点时间语义示例, figureFileSmall=9FJ0ZlXvfCdENyeJtMmVQw==, figureFileBig=XllgybyTKyHFBhn9UJTXjQ==, tableContent=null), ArticleFig(id=1329381572001772297, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 3, caption=Example of absolute timing semantic, figureFileSmall=XpnQHOwIyPK24hX1gKrLYA==, figureFileBig=0QBS9V0vLyyv/LrkuX/ytA==, tableContent=null), ArticleFig(id=1329381572085658378, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图3, caption=绝对段时间语义示例, figureFileSmall=XpnQHOwIyPK24hX1gKrLYA==, figureFileBig=0QBS9V0vLyyv/LrkuX/ytA==, tableContent=null), ArticleFig(id=1329381572152767243, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 4, caption=Example of relative timed semantic, figureFileSmall=waKUT7pF2XSuZMEQqx+kXA==, figureFileBig=EOvAvK90/5R8gOcCc/MB5A==, tableContent=null), ArticleFig(id=1329381572215681804, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图4, caption=相对点时间语义示例, figureFileSmall=waKUT7pF2XSuZMEQqx+kXA==, figureFileBig=EOvAvK90/5R8gOcCc/MB5A==, tableContent=null), ArticleFig(id=1329381572282790669, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 5, caption=Example of relative timing semantic, figureFileSmall=/gLZXZFEMdmv83u0PTs3FQ==, figureFileBig=0Dhyz/Uo1Qx2GuAhKPxAhg==, tableContent=null), ArticleFig(id=1329381572358288142, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图5, caption=相对段时间语义示例, figureFileSmall=/gLZXZFEMdmv83u0PTs3FQ==, figureFileBig=0Dhyz/Uo1Qx2GuAhKPxAhg==, tableContent=null), ArticleFig(id=1329381572421202703, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 6, caption=Description of platform dependent property coff, figureFileSmall=FZcXChFtOScQYen6lPBOpg==, figureFileBig=SfxBqHkDsolrCh6eWZxLfw==, tableContent=null), ArticleFig(id=1329381572475728656, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图6, caption=平台相关属性coff说明, figureFileSmall=FZcXChFtOScQYen6lPBOpg==, figureFileBig=SfxBqHkDsolrCh6eWZxLfw==, tableContent=null), ArticleFig(id=1329381572538643217, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 7, caption=Examples of TFG+, figureFileSmall=hhlNGANZzJnurlxWSin8kg==, figureFileBig=LiVkiZENkM43hZ/lEoaBBw==, tableContent=null), ArticleFig(id=1329381572651889426, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图7, caption=TFG+示例, figureFileSmall=hhlNGANZzJnurlxWSin8kg==, figureFileBig=LiVkiZENkM43hZ/lEoaBBw==, tableContent=null), ArticleFig(id=1329381572718998291, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 8, caption=Example of execution graph, figureFileSmall=mainKUE99wLDCd9nhSYG1A==, figureFileBig=0s/FkOHH58yWySDbeKlZ7w==, tableContent=null), ArticleFig(id=1329381572790301460, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图8, caption=执行图示例, figureFileSmall=mainKUE99wLDCd9nhSYG1A==, figureFileBig=0s/FkOHH58yWySDbeKlZ7w==, tableContent=null), ArticleFig(id=1329381572869993237, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 9, caption=Flow graph of temporal behavior analysis and semantic verification, figureFileSmall=TYVdDsDOLZ65MHZDZafO4A==, figureFileBig=b+U0mBb/CooJWSbZAJ7NsQ==, tableContent=null), ArticleFig(id=1329381574774207254, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图9, caption=时间行为分析和语义验证流程图, figureFileSmall=TYVdDsDOLZ65MHZDZafO4A==, figureFileBig=b+U0mBb/CooJWSbZAJ7NsQ==, tableContent=null), ArticleFig(id=1329381574837121815, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 10, caption=Timing diagram of absolute timed semantic, figureFileSmall=yjK9aSXgAGvc1JHLsTj0Sg==, figureFileBig=Ejp6K/pafn5rdHQxxYs6wA==, tableContent=null), ArticleFig(id=1329381574908424984, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图10, caption=绝对点时间语义时序图, figureFileSmall=yjK9aSXgAGvc1JHLsTj0Sg==, figureFileBig=Ejp6K/pafn5rdHQxxYs6wA==, tableContent=null), ArticleFig(id=1329381574971339546, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 11, caption=Timing diagram of absolute timing semantic, figureFileSmall=Q/PiQyM4IzmAFcvWMYC8jA==, figureFileBig=StVnB7V34QMw/hHjQFVONA==, tableContent=null), ArticleFig(id=1329381575042642715, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图11, caption=绝对段时间语义时序图, figureFileSmall=Q/PiQyM4IzmAFcvWMYC8jA==, figureFileBig=StVnB7V34QMw/hHjQFVONA==, tableContent=null), ArticleFig(id=1329381575105557276, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 12, caption=Timing diagram of relative timed semantic, figureFileSmall=qCqk6ROZ/4w4WXqSOp8AGg==, figureFileBig=Q2mr4UHAJZqEb+v8px/Dgw==, tableContent=null), ArticleFig(id=1329381575176860445, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图12, caption=相对点时间语义时序图, figureFileSmall=qCqk6ROZ/4w4WXqSOp8AGg==, figureFileBig=Q2mr4UHAJZqEb+v8px/Dgw==, tableContent=null), ArticleFig(id=1329381575256552222, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 13, caption=Timing diagram of getti instruction execution, figureFileSmall=1ffXkxS7VG8Ll9iTazM8OA==, figureFileBig=sKEaXsQgiN88pYK0kSTs0A==, tableContent=null), ArticleFig(id=1329381575361409823, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图13, caption=getti指令执行时序图, figureFileSmall=1ffXkxS7VG8Ll9iTazM8OA==, figureFileBig=sKEaXsQgiN88pYK0kSTs0A==, tableContent=null), ArticleFig(id=1329381575424324384, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 14, caption=Example of impact of getti instruction predecessor code fragment, figureFileSmall=E76UCuhO7WLQmPmrn6ouog==, figureFileBig=MMPMUZFJiI3lsEIZujKbrA==, tableContent=null), ArticleFig(id=1329381575499821858, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图14, caption=getti指令前驱代码段的影响示例, figureFileSmall=E76UCuhO7WLQmPmrn6ouog==, figureFileBig=MMPMUZFJiI3lsEIZujKbrA==, tableContent=null), ArticleFig(id=1329381575562736419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 15, caption=Interleaved LET implementation, figureFileSmall=viggtpBidD/bj6KE5Gu6fQ==, figureFileBig=8d7HxBKY/8/SP5JRRIGFcg==, tableContent=null), ArticleFig(id=1329381575625650980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图15, caption=交错LET语义实现, figureFileSmall=viggtpBidD/bj6KE5Gu6fQ==, figureFileBig=8d7HxBKY/8/SP5JRRIGFcg==, tableContent=null), ArticleFig(id=1329381575684371237, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 16, caption=Example of autonomous driving program, figureFileSmall=z/MxD49n7xoGzF4fhXBCRQ==, figureFileBig=yLPyCUbM1dQtc0z0AqmlRA==, tableContent=null), ArticleFig(id=1329381575751480102, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图16, caption=自动驾驶程序示例, figureFileSmall=z/MxD49n7xoGzF4fhXBCRQ==, figureFileBig=yLPyCUbM1dQtc0z0AqmlRA==, tableContent=null), ArticleFig(id=1329381575810200359, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 17, caption=Task t3oi program and TFG+, figureFileSmall=26cqFGPRk5E1SpA0iXXX/A==, figureFileBig=23+S6W+ps+k+DkY5wKHMzA==, tableContent=null), ArticleFig(id=1329381575864726312, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图17, caption=任务t3oi程序和TFG+, figureFileSmall=26cqFGPRk5E1SpA0iXXX/A==, figureFileBig=23+S6W+ps+k+DkY5wKHMzA==, tableContent=null), ArticleFig(id=1329381575923446569, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 18, caption=Example of task t3oi execution graph, figureFileSmall=rRzBtbBlxZ+cyLoA8hBaKg==, figureFileBig=prPpAw05mB/G9p6WqeFxSw==, tableContent=null), ArticleFig(id=1329381575986361130, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图18, caption=任务t3oi执行图示例, figureFileSmall=rRzBtbBlxZ+cyLoA8hBaKg==, figureFileBig=prPpAw05mB/G9p6WqeFxSw==, tableContent=null), ArticleFig(id=1329381576053469996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 19, caption=Runtime time diagram of RPU threads, figureFileSmall=WNanATQ55mB1eU6DUIplbw==, figureFileBig=Un43aMiIMWKjWXBHtsOGhw==, tableContent=null), ArticleFig(id=1329381576112190253, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图19, caption=RPU线程运行时序图, figureFileSmall=WNanATQ55mB1eU6DUIplbw==, figureFileBig=Un43aMiIMWKjWXBHtsOGhw==, tableContent=null), ArticleFig(id=1329381576183493422, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 20, caption=ABS control model, figureFileSmall=dK4wHV1yc4gEFCiMSX4Z7A==, figureFileBig=vEFWIxAkYdc50WGiW/HfaQ==, tableContent=null), ArticleFig(id=1329381576246407983, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图20, caption=ABS控制模型, figureFileSmall=dK4wHV1yc4gEFCiMSX4Z7A==, figureFileBig=vEFWIxAkYdc50WGiW/HfaQ==, tableContent=null), ArticleFig(id=1329381576334488368, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 21, caption=ABS controller part, figureFileSmall=AR13dn/NPufzJYHodD2C6w==, figureFileBig=R64H6RsOhohgMSPBLJ1FEQ==, tableContent=null), ArticleFig(id=1329381576414180145, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图21, caption=ABS控制器部分, figureFileSmall=AR13dn/NPufzJYHodD2C6w==, figureFileBig=R64H6RsOhohgMSPBLJ1FEQ==, tableContent=null), ArticleFig(id=1329381576519037746, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 22, caption=TTI program of controller part, figureFileSmall=LkHQ/RZbFJ3kK80G0EuNcQ==, figureFileBig=LcnXTpCMNmeCd5Jokktzwg==, tableContent=null), ArticleFig(id=1329381576607118131, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图22, caption=控制器部分TTI程序, figureFileSmall=LkHQ/RZbFJ3kK80G0EuNcQ==, figureFileBig=LcnXTpCMNmeCd5Jokktzwg==, tableContent=null), ArticleFig(id=1329381576678421300, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 23, caption=TFG+ of controller algorithm, figureFileSmall=u+k+2r/d0aOLOvbZQtWRVQ==, figureFileBig=3unJNR3HiF9Jg3Qv34l8vQ==, tableContent=null), ArticleFig(id=1329381576770695989, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图23, caption=控制器算法的TFG+, figureFileSmall=u+k+2r/d0aOLOvbZQtWRVQ==, figureFileBig=3unJNR3HiF9Jg3Qv34l8vQ==, tableContent=null), ArticleFig(id=1329381576825221942, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Figure 24, caption=Runtime time diagram of controller part, figureFileSmall=Cl+dthMcBUZ1NDeDdgHfZw==, figureFileBig=MDdtsR+KPUSpM3yGe0zpgA==, tableContent=null), ArticleFig(id=1329381576913302327, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=图24, caption=控制器部分运行时序图, figureFileSmall=Cl+dthMcBUZ1NDeDdgHfZw==, figureFileBig=MDdtsR+KPUSpM3yGe0zpgA==, tableContent=null), ArticleFig(id=1329381576988799800, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Table 1, caption=

Time Semantic Registers

, figureFileSmall=null, figureFileBig=null, tableContent=
寄存器名称助记符描述
时间粒度寄存器tgr系统时间粒度
时间寄存器ctr系统当前时间
时间戳寄存器tsr保存上一个时间触发操作发生的时间
), ArticleFig(id=1329381579467633465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=表1, caption=

时间语义寄存器

, figureFileSmall=null, figureFileBig=null, tableContent=
寄存器名称助记符描述
时间粒度寄存器tgr系统时间粒度
时间寄存器ctr系统当前时间
时间戳寄存器tsr保存上一个时间触发操作发生的时间
), ArticleFig(id=1329381579543130938, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Table 2, caption=

Time Semantic Instructions

, figureFileSmall=null, figureFileBig=null, tableContent=
类型汇编指令
系统时间管理指令settg rs1 getti rd
setti rs1   getts rd
时间触发操作指令ttiat rd, (rs2), rs1
ttoat rs3, (rs2), rs1
执行时间约束指令delay rs1
mtfd r1
任务并发管理指令tkend
addtk rs1, rs2
), ArticleFig(id=1329381579622822715, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=表2, caption=

时间语义指令

, figureFileSmall=null, figureFileBig=null, tableContent=
类型汇编指令
系统时间管理指令settg rs1 getti rd
setti rs1   getts rd
时间触发操作指令ttiat rd, (rs2), rs1
ttoat rs3, (rs2), rs1
执行时间约束指令delay rs1
mtfd r1
任务并发管理指令tkend
addtk rs1, rs2
), ArticleFig(id=1329381579752846140, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Table 3, caption=

TFG+ Definition

, figureFileSmall=null, figureFileBig=null, tableContent=
组成部分具体构成
图结构ATP,绝对段时间语义节点集合.
ATdP,绝对点时间语义节点集合.
RTP,相对段时间语义节点集合.
RTdP,相对点时间语义节点集合.
RBP,相对基准点集合.
BB,基本块节点集合.
start,开始节点.
V={start}∪ATP∪ATdP∪RTP∪RTdP∪RBP∪BB,节点集合.
E = V × V,边集合.
程序属性ttg,表示时间粒度寄存器的值.
tstart,{start} →$\mathbb{N}$,映射开始节点到任务开始执行的系统时间.
tATP,ATP →$\mathbb{N}$,映射ATP中节点到系统时间.
tATdP,ATdP →$\mathbb{N}$,映射ATdP中节点到系统时间.
tRTP,RTP →$\mathbb{N}$,映射RTP中节点到系统时间.
tRTdP,RTdP →$\mathbb{N}$,映射RTdP中节点到系统时间.
平台相关
属性
cf,BB →$\mathbb{N}$,映射基本块节点到执行开销.
ct,ATP∪ATdP∪RTP∪RTdP →$\mathbb{N}$,时间语义节点对应指令的前驱代码段最坏执行情况的前提下,映射时间语义节点到执行开销.
cd,ATP∪ATdP∪RTP∪RTdP →$\mathbb{N}$,时间语义节点对应指令的前驱代码段最坏执行情况的前提下,映射时间语义节点到延迟时间.
coff,{start}∪ATdP→$\mathbb{N}$,映射开始节点到任务开始时间相对于某一系统时刻的偏移时间;绝对点时间语义节点对应指令的前驱代码段最坏执行情况的前提下,映射绝对点时间语义节点到节点对应指令执行完成相对于某一系统时刻的偏移
时间.
), ArticleFig(id=1329381579836732221, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=表3, caption=

TFG+定义

, figureFileSmall=null, figureFileBig=null, tableContent=
组成部分具体构成
图结构ATP,绝对段时间语义节点集合.
ATdP,绝对点时间语义节点集合.
RTP,相对段时间语义节点集合.
RTdP,相对点时间语义节点集合.
RBP,相对基准点集合.
BB,基本块节点集合.
start,开始节点.
V={start}∪ATP∪ATdP∪RTP∪RTdP∪RBP∪BB,节点集合.
E = V × V,边集合.
程序属性ttg,表示时间粒度寄存器的值.
tstart,{start} →$\mathbb{N}$,映射开始节点到任务开始执行的系统时间.
tATP,ATP →$\mathbb{N}$,映射ATP中节点到系统时间.
tATdP,ATdP →$\mathbb{N}$,映射ATdP中节点到系统时间.
tRTP,RTP →$\mathbb{N}$,映射RTP中节点到系统时间.
tRTdP,RTdP →$\mathbb{N}$,映射RTdP中节点到系统时间.
平台相关
属性
cf,BB →$\mathbb{N}$,映射基本块节点到执行开销.
ct,ATP∪ATdP∪RTP∪RTdP →$\mathbb{N}$,时间语义节点对应指令的前驱代码段最坏执行情况的前提下,映射时间语义节点到执行开销.
cd,ATP∪ATdP∪RTP∪RTdP →$\mathbb{N}$,时间语义节点对应指令的前驱代码段最坏执行情况的前提下,映射时间语义节点到延迟时间.
coff,{start}∪ATdP→$\mathbb{N}$,映射开始节点到任务开始时间相对于某一系统时刻的偏移时间;绝对点时间语义节点对应指令的前驱代码段最坏执行情况的前提下,映射绝对点时间语义节点到节点对应指令执行完成相对于某一系统时刻的偏移
时间.
), ArticleFig(id=1329381579908035390, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Table 4, caption=

Execution Time of the Instructions in Each Pipeline Stage of RPU

, figureFileSmall=null, figureFileBig=null, tableContent=
指令类型IFIDEXMMWB
通用计算指令1+1111
分支指令1+1111
访存指令1+111+1
标准时钟管理指令1+1111
ttiat/ttoat1+1$\tau $+11+1
delay1+1$\tau $+11+1
mtfd
), ArticleFig(id=1329381579983532863, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=表4, caption=

指令在RPU各流水段的执行时间

, figureFileSmall=null, figureFileBig=null, tableContent=
指令类型IFIDEXMMWB
通用计算指令1+1111
分支指令1+1111
访存指令1+111+1
标准时钟管理指令1+1111
ttiat/ttoat1+1$\tau $+11+1
delay1+1$\tau $+11+1
mtfd
), ArticleFig(id=1329381580054836032, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=EN, label=Table 5, caption=

Example of Tasks Properties

, figureFileSmall=null, figureFileBig=null, tableContent=
任务程序类型语义类型和时间语义指令
对应系统时间
任务开始
系统时间
t1oiTTI程序绝对点时间语义(输出):5
绝对点时间语义(输入):5
4
t2oi1TTI程序绝对点时间语义(输出):3
绝对点时间语义(输入):3
2
t2oi2TTI程序绝对点时间语义(输出):43
绝对点时间语义(输入):43
42
t3oiTTI程序绝对点时间语义(输出):7
绝对点时间语义(输入):7
6
t1c普通程序18
t2c1普通程序8
t2c2普通程序44
t3c普通程序54
), ArticleFig(id=1329381580113556289, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, language=CN, label=表5, caption=

任务属性示例

, figureFileSmall=null, figureFileBig=null, tableContent=
任务程序类型语义类型和时间语义指令
对应系统时间
任务开始
系统时间
t1oiTTI程序绝对点时间语义(输出):5
绝对点时间语义(输入):5
4
t2oi1TTI程序绝对点时间语义(输出):3
绝对点时间语义(输入):3
2
t2oi2TTI程序绝对点时间语义(输出):43
绝对点时间语义(输入):43
42
t3oiTTI程序绝对点时间语义(输出):7
绝对点时间语义(输入):7
6
t1c普通程序18
t2c1普通程序8
t2c2普通程序44
t3c普通程序54
)], 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.202220730, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202220730, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202220730, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202220730, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1704124800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
基于RPU的TTI程序设计和分析方法
高银康 , 陈香兰 , 龚小航 , 蒋滨泽 , 李曦 * , 周学海
计算机研究与发展 | 体系结构 2024,61(1): 98-119
收起
收藏切换
计算机研究与发展 |体系结构 2024 , 61 (1) : 98 -119
基于RPU的TTI程序设计和分析方法
全屏
[Author(id=1329381569455829731, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=gaoyinkang@mail.ustc.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329381569522938596, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569455829731, language=EN, stringName=Yinkang Gao, firstName=Yinkang, middleName=null, lastName=Gao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1998. Master candidate. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1998. Master candidate. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381569585853157, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569455829731, language=CN, stringName=高银康, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"lU6i7oQHfY+qeJSNp7dAag==","content":"

1998年生. 硕士研究生. 主要研究方向为计算机系统结构

"}, bioImg=lU6i7oQHfY+qeJSNp7dAag==, bioContent=

1998年生. 硕士研究生. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381569652962023, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=1329381569736848105, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569652962023, language=EN, stringName=Xianglan Chen, firstName=Xianglan, middleName=null, lastName=Chen, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1977. PhD. Her main research interest includes system software

"}, bioImg=null, bioContent=

born in 1977. PhD. Her main research interest includes system software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381569820734186, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569652962023, language=CN, stringName=陈香兰, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"CmPB7rxjRqbZjp4c1yvWQw==","content":"

1977年生. 博士. 主要研究方向为系统软件

"}, bioImg=CmPB7rxjRqbZjp4c1yvWQw==, bioContent=

1977年生. 博士. 主要研究方向为系统软件

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381569892037356, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, 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=1329381569967534829, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569892037356, language=EN, stringName=Xiaohang Gong, firstName=Xiaohang, middleName=null, lastName=Gong, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1999. Master candidate. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1999. Master candidate. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570043032302, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381569892037356, language=CN, stringName=龚小航, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"nZqECxjAgbxMh5GJFD90cg==","content":"

1999年生. 硕士研究生. 主要研究方向为计算机系统结构

"}, bioImg=nZqECxjAgbxMh5GJFD90cg==, bioContent=

1999年生. 硕士研究生. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381570110141168, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329381570181444337, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570110141168, language=EN, stringName=Binze Jiang, firstName=Binze, middleName=null, lastName=Jiang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 2000. Master candidate. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 2000. Master candidate. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570252747506, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570110141168, language=CN, stringName=蒋滨泽, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"hR4XQwe1XR7co1XfWl4IqQ==","content":"

2000年生. 硕士研究生. 主要研究方向为计算机系统结构

"}, bioImg=hR4XQwe1XR7co1XfWl4IqQ==, bioContent=

2000年生. 硕士研究生. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381570357605108, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=llxx@ustc.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329381570420519669, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570357605108, language=EN, stringName=Xi Li, firstName=Xi, middleName=null, lastName=Li, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1963. Professor. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1963. Professor. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570491822838, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570357605108, language=CN, stringName=李曦, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"3kpefHFcc8ZRkOsoxAksMQ==","content":"

1963年生. 教授. 主要研究方向为计算机系统结构

"}, bioImg=3kpefHFcc8ZRkOsoxAksMQ==, bioContent=

1963年生. 教授. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1329381570567320312, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, orderNo=5, 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=1329381570630234873, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570567320312, language=EN, stringName=Xuehai Zhou, firstName=Xuehai, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1966. Professor. His main research interest includes computer architecture

"}, bioImg=null, bioContent=

born in 1966. Professor. His main research interest includes computer architecture

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329381570697343738, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329381561658618522, authorId=1329381570567320312, language=CN, stringName=周学海, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"tRfUtmdqOpH9O28NjtUwtg==","content":"

1966年生. 教授. 主要研究方向为计算机系统结构

"}, bioImg=tRfUtmdqOpH9O28NjtUwtg==, bioContent=

1966年生. 教授. 主要研究方向为计算机系统结构

, aboutCorrespAuthor=null)}, companyList=null)]
高银康 , 陈香兰, 龚小航, 蒋滨泽, 李曦* , 周学海
作者信息
  • 中国科学技术大学计算机科学与技术学院 合肥 230027
  • 中国科学技术大学苏州高等研究院 江苏苏州 215004
通讯作者:
李曦()
作者简介:

1998年生. 硕士研究生. 主要研究方向为计算机系统结构

1977年生. 博士. 主要研究方向为系统软件

1999年生. 硕士研究生. 主要研究方向为计算机系统结构

2000年生. 硕士研究生. 主要研究方向为计算机系统结构

1963年生. 教授. 主要研究方向为计算机系统结构

1966年生. 教授. 主要研究方向为计算机系统结构

Design and Analysis Method of TTI Program Based on RPU
Yinkang Gao , Xianglan Chen, Xiaohang Gong, Binze Jiang, Xi Li* , Xuehai Zhou
Affiliations
  • School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027
  • Suzhou Institute for Advanced Research, University of Science and Technology of China, Suzhou, Jiangsu 215004
  • born in 1998. Master candidate. His main research interest includes computer architecture

    born in 1977. PhD. Her main research interest includes system software

    born in 1999. Master candidate. His main research interest includes computer architecture

    born in 2000. Master candidate. His main research interest includes computer architecture

    born in 1963. Professor. His main research interest includes computer architecture

    born in 1966. Professor. His main research interest includes computer architecture

出版时间: 2024-01-02 doi: 10.7544/issn1000-1239.202220730
文章导航
收藏切换

实时嵌入式系统不仅要保证计算结果的逻辑正确性,还要确保与外界交互的时序正确性,所以底层程序要能精确表达上层模型中的时间行为. TTI指令集(time-triggered instruction set)的提出尝试解决计算机指令集体系结构层次缺少时间语义的问题,并且基于TTI指令集实现的实时处理单元(real-time processing unit,RPU)证明了TTI指令集的可行性和有效性. 但是目前的工作缺少对于TTI程序设计和分析方法的研究. 所以,基于TTI指令集和RPU,提出了TTI指令集可以表达的4种时间语义,给出了TTI程序的设计范式. 并且构建了TTI程序时间行为的表示方法——TFG+,TFG+是对TFG的扩展,TFG+区分了TTI程序中时间语义指令和普通代码段,可以表示TTI程序的控制流信息、用户规定的时间行为和TTI程序平台相关的时间属性. 最后,提出了TTI程序的时间分析方法以及时间安全性检查方法,为TTI程序的设计和部署提供了依据.

实时嵌入式系统  /  时间可预测性  /  时间语义指令集  /  实时处理器  /  WCET分析

Real-time embedded system (RTES) needs to guarantee not only logical correctness of the calculation results, but also temporal correctness of the interaction with outside world, so low-level programs must be able to accurately express time behavior in upper-level models. TTI instruction set (time-triggered instruction set) is proposed to try to solve the problem of the lack of timing semantics at the computer instruction set architecture level, and the realization of real-time processing unit (RPU) based on TTI instruction set proves the feasibility and effectiveness of TTI instruction set. However, the current work lacks research on design and analysis method of TTI program. Therefore, based on TTI instruction set and RPU, we propose four types of timing semantics that TTI instruction set can express, give the design paradigm of TTI program. Then, we define the representation of TTI program time behavior — TFG+, which is an extension of TFG. TFG+ distinguishes timing semantic instructions and the common code segments in the TTI program, and TFG+ can represent the control flow information of TTI program, the time behavior specified by the user, and the time attributes related to hardware platform. Finally, we propose time analysis method of TTI program and time safety checking method, which provide the basis for the design and deployment of TTI program.

real-time embedded system (RTES)  /  timing predictability  /  timed instruction set  /  real-time processor  /  WCET analysis
高银康, 陈香兰, 龚小航, 蒋滨泽, 李曦, 周学海. 基于RPU的TTI程序设计和分析方法. 计算机研究与发展, 2024 , 61 (1) : 98 -119 . DOI: 10.7544/issn1000-1239.202220730
Yinkang Gao, Xianglan Chen, Xiaohang Gong, Binze Jiang, Xi Li, Xuehai Zhou. Design and Analysis Method of TTI Program Based on RPU[J]. Journal of Computer Research and Development, 2024 , 61 (1) : 98 -119 . DOI: 10.7544/issn1000-1239.202220730
实时嵌入式系统(real-time embedded system,RTES)通常应用于安全关键领域,此类系统需要实时和外界环境交互,因此不仅要保证计算结果的逻辑正确性,还要确保与外界交互的时序正确性.
实时领域的程序设计中,高层的编程模型含有时间语义,如逻辑执行时间(logical execution time,LET)编程模型[1],而在底层的指令集架构(instruction set architecture,ISA)层面缺乏时间语义,导致编程人员无法直接控制底层程序的时序行为. 现阶段实时系统设计和分析的主要方法是,计算底层程序的执行时间,并以此作为程序时序控制的依据,但是由于程序中不确定的分支跳转指令,以及硬件体系结构(流水线、Cache、分支预测等)影响,传统程序的执行时间分析,总是悲观地分析程序在最坏情况下的执行时间(worse case execution time,WCET),而为了保证程序时序行为的正确,就必须依据WCET进行资源的过度分配,使高层的编程模型不能精确且自然地映射至底层程序.
造成这一问题的原因是通用体系结构的ISA没有可以表达时间语义的指令,所以和LET等实时编程模型的表达能力存在差距. 针对该问题,最有效的方法是规定程序中每一条指令的执行时间,但是这样会限制底层硬件体系结构的发展[2]. 为平衡时间语义表达能力和执行性能的问题,Lee等人[3]提出PRET(precision timed)概念,并提出了限定代码段执行时间的指令,一定程度上提升了底层指令集的表达能力. 文献[4]提出了TTI指令集(time-triggered instruction set),与Lee小组工作相比,增加了时间和操作相结合的定时指令,使指令集的表达能力进一步提升,本文的分析和验证都依据TTI指令集进行,并且将使用了TTI指令集的程序称为TTI程序.
Lee等人[3]和文献[4]中对于指令集扩展的工作,仅给出了时间语义指令集的定义和实现方案,并没有说明指令集可以表达的时间语义和相应的时间语义程序设计范式,导致实时系统设计者在进行上层模型至底层程序的映射时缺乏理论依据. TTI指令集通过不同指令组合可以表达丰富的时间语义,为了映射上层设计,需要给出TTI程序的设计范式,明确TTI程序可以表达的语义类型.
TTI程序运行时,时间语义指令的执行会受到前驱代码段执行时间的影响,为了保证指令的时间语义在执行时能够得到正确表达,需要对TTI程序进行时间行为分析. 例如,对于TTI指令集中定时输出指令ttoat,指令语义要求在预设时间点完成输出操作,而ttoat指令会在前驱代码段执行完成后开始执行,所以需要计算ttoat指令前驱代码段的WCET,保证该WCET小于ttoat指令预设的时间点,以此保证定时语义的正确表达. 并且传统程序的时间行为分析,会以整个程序(任务)为单位,给出程序(任务)的WCET,而TTI程序需要计算时间语义指令间程序段的WCET,并结合时间语义指令的语义要求进行时间安全性检查,验证指令运行时的正确性,所以需要改进传统程序的WCET分析方法,提出针对时间语义程序的时间行为分析方法.
本文依据文献[4]所述工作,首先提出了TTI程序的设计范式,说明了TTI指令集的表达能力,明确TTI程序可以表达的4种语义. 同时,对Timed C[5]系列工作中提出的程序时间行为的表示TFG[6]进行扩展,提出了TTI程序的表示TFG+,描述了TTI程序的控制流信息、用户规定的时间行为和平台相关的时间属性. 最后,根据TFG+,基于实时处理单元(real-time processing unit,RPU),采用基于执行图[7]的低级分析方法,分析了TTI程序的时间行为,并且对TTI程序的时间语义指令进行时间安全性检查,验证其语义在执行时能够得到正确表达. 本文提出的TFG+构建方法、时间行为分析方法以及时间安全性检查方法适用于RPU和其他可以运行TTI指令集的处理器架构,若采用除RPU外的其他架构,只需要修改执行图的构建方法和执行图节点属性的计算方法即可.
本文的主要贡献有3个方面:
1) 提出TTI程序的设计范式,明确TTI程序可以表达的4种时间语义,使编程人员能够精确自然地表达上层的设计.
2) 提出TFG+,以表示TTI程序,TFG+可以表达TTI程序的控制流信息、用户规定的时间行为以及平台相关的时间属性,为TTI程序的分析和时间安全性检查提供了依据.
3) 提出了TTI程序的时间行为分析方法和时间安全性检查方法,保证TTI程序运行时指令的语义能够正确表达.
相关工作分为时间语义指令集、程序抽象表示和程序时间行为分析3个方面进行介绍.
Lee在文献[8]中从“实时”概念出发,总结了多种对于实时性的定义. Lee[8]认为根据不同的需求和角度,“实时”概念有6种定义:快速计算、优先调度、对数据流的计算、有界执行、程序的时间语义和网络的时间语义. 其中,在对程序的时间语义的阐述中,Lee[8]认为实时系统设计和部署时,由于现在的通用计算ISA中不存在时间语义,需要在更高层次重新引入时间语义,但是通用计算ISA和高层次模型关于时间语义表达能力上存在的差距,会导致实际系统设计时的诸多问题,所以需要在实时系统设计的各个抽象层次引入时间语义.
根据上述观点,Lee等人[2]认为通用计算机指令集隐藏了底层体系结构中精确的数字电路时钟,为了控制程序的时间行为,计算机要向高层次模型提供这一精确时间. 对于时序的控制,Lee等人[2]定义了ISA层需要具备的4种能力:1)限定程序块执行时间下界;2)程序块执行超过限定时间,程序块完成后分支跳转;3)程序块执行超过限定时间,立即分支跳转;4)限定程序块执行时间的上界. 文献[2]较早地提出了ISA层在时序控制方法需要具有的时间语义,但是没有说明上层模型到底层指令的映射关系,没有给出相应的设计范式,同时,Lee等人[2]认为时间语义指令集只需要“限定代码段执行时间”,没有关于点时间语义的论述.
Lee等人[2]对通用计算指令集进行扩展,增加指令DU(delay until)保证代码执行时间下界,指令MTFD(meet the final deadline)保证代码执行时间上界. 并且依据此设计了处理器PTARM[9]和FlexPRET[10]. 此方法可以限定代码的执行时间,但是无法直接表达操作发生在某个时刻的语义,所以该指令集的表达能力依旧有限.
文献[4]从实时理论出发,类比通用计算中图灵机为通用计算系统的理论基础[11],冯•诺依曼机是通用计算机系统统一的实现模型[12],提出了具有时间语义的实时计算机体系结构模型实时机(real-time machine,RTM),RTM在冯•诺依曼机5大部件的基础上扩展了标准时钟(stdClk)部件,至此处理器时钟(cpuClk)负责实时处理器的值域控制,标准时钟负责实时处理器的时域控制. 基于RTM的理论指导,文献[4]结合时间触发自动机(time-triggered automata,TTA)理论[13],定义了时间语义指令集TTI. 相比于Lee等人[2]提出的限定代码执行时间的时间语义指令集,TTI指令集不仅具有限定代码执行时间上下界的delay,mtfd指令,还增加了时间和操作相结合的定时指令ttiat,ttoat,以及任务并发管理指令,进一步扩展了指令集的表达能力. 下面详细介绍TTI指令集的定义和实现.
TTI指令集包含时间语义寄存器和时间语义指令2部分. 表1给出了时间语义寄存器. 时间粒度寄存器(time granularity register),用来设置TTI程序的时间粒度,以满足不同系统或不同工作模式的时间粒度要求;时间寄存器(current time register),用来表示系统时间,根据时间粒度寄存器生成,即标准时钟的上升沿累计值等于时间粒度寄存器时系统时间寄存器的值加1;时间戳寄存器(time stamp register),用来保存上一次时间触发操作的系统时间. 如表2所示,TTI指令集中共有10条时间语义指令,按照功能分为4部分. 文献[4]中对于指令的语义进行了详细说明.
目前时间语义指令集的相关工作仅说明了每条指令的语义和对应的硬件实现方案,缺乏时间语义指令集表达能力的说明,同时,没有给出时间语义程序的设计范式,导致无法直接自然地定义上层模型中时间语义与底层时间语义程序的映射关系.
文献[4]基于TTI指令集的定义,扩展RISC-V指令集[14],实现了可以执行TTI指令集的RPU. RPU基于经典5段流水[15]实现,即流水线分为取指段、译码段、执行段、访存段和写回段5个阶段. 下面给出TTI指令集的实现.
1)系统时间管理指令. 此类指令的功能是对标准时钟进行管理,生成系统时间. 执行段,settg指令设置tgr,setti指令设置ctr. 写回段,getti指令读取ctr中保存的当前系统时间到目的寄存器,getts指令读取tsr保存的上一时间触发操作发生时间到目的寄存器.
2)时间触发操作指令. 此类指令的特点是操作和时间绑定,规定操作在指定系统时间触发执行. 执行段,比较ctr的值和指令预设时间,若ctr小于指令预设时间,产生stall信号停顿流水线,直到ctr等于指令预设时间,执行时间触发操作指令. 后续指令ttiat/ttoat在访存段和写回段的操作和普通load/store指令相同.
3)执行时间约束指令. 此类指令的功能是保证代码段执行时间的上下界. delay指令用于约束代码执行时间的下界;mtfd指令用于约束代码执行时间的上界. 执行段,delay指令会比较ctr的值和指令预设时间,若ctr小于指令预设时间,表示未到延时时间,产生stall信号停顿流水线,直到ctr等于指令预设时间,才继续指令的执行. 对于mtfd指令,RPU没有相关实现,mtfd指令只作为代码中的检查点,用于时间安全性检查.
4)任务并发管理指令. 此类指令的功能是摒弃传统的使用中断的软件任务并发管理,提供确定的硬件线程管理任务并发的能力. 本文不考虑多线程TTI程序,所以省略任务并发管理指令的实现.
传统程序进行WCET分析时,可以将程序表示为控制流图(control flow graph,CFG),在CFG中程序以基本块(basic block)为单位进行划分,基本块间的依赖关系通过CFG中基本块间的边进行表达. 后续许多程序表示都是对CFG的扩充.
文献[16]中提出了CKAG(concurrent kep assembler graph),用来表示使用了处理器KEP(kiel Esterel processor)指令集的程序,KEP是可以运行同步语言Esterel[17]的专用处理器,而CKAG的提出是为了计算同步语言程序最坏情况反应时间(worst case reaction time,WCRT). 同步语言PRET-C[18]为了计算WCRT也提出了PRET-C程序的表示TCCFG(timed concurrent control flow graph)[19].
文献[6]中提出TFG的概念,用来表示Timed C[5]程序,进行Timed C编译器正确性检查,Timed C程序的TFG在CFG的基础上,添加了表达段时间语义的时间点(timing point,TP). 另外,FG定义了图中每个节点的时间属性,至此TFG不仅可以表达程序的控制流信息,还可以表达用户规定的时间行为,以及平台相关的时间属性,但是Timed C程序的TFG受限于Timed C语言,只是表达了段时间语义. 本文结合TTI程序提出了TFG+,是对TFG的扩充,表达了更为丰富的时间语义,例如点时间语义.
现有的程序WCET分析方法分为基于测量的WCET分析和静态WCET分析. 静态WCET分析,由流分析(flow analysis)、低级分析(low-level analysis)和WCET计算(WCET computation)组成.
1)流分析. 首先通过分析程序结构,构建程序的表示,例如CFG[20];然后由程序员手动[21]或通过自动分析[22]给出程序循环边界(loop bound)等流事实(flow fact).
2)低级分析. 目的是结合硬件体系结构分析CFG中每个基本块的执行时间,常用的方法有抽象解释(abstract interpretation)[23]、基于执行图(execution graph)[5, 24-25]的分析方法. 抽象解释方法的WCET分析工具有aiT[26],而基于执行图的WCET分析工具有Chronos[27],OTAWA[28].
3)WCET计算. 目的是计算整个程序最坏情况下的执行时间,现有基于语法树的WCET计算方法[29-30]和基于CFG的WCET计算方法[31]. 基于CFG,整个程序的执行时间可以表示为每个基本块执行时间的加权和,权值为每个基本块的执行次数. 通过分析CFG节点依赖关系和流事实,给出对每个基本块执行次数的约束,采用整数线性规划(integer linear program,ILP)方法,最大化整个程序的执行时间表达式,该方法被称为隐式路径枚举技术(implicit path enumeration technique,IPET).
本节给出TTI程序相关概念,以及设计TTI程序的基本流程.
由1.1节TTI指令集的实现可知,TTI指令集中时间语义指令在RPU流水线执行段的行为会受到指令预设系统时间和当前系统时间寄存器ctr的值的影响,编程人员需要依据系统时间设计TTI程序的时间行为. 下面给出TTI程序中“系统时间”这一概念的定义.
定义1. 系统时间. TTI程序中系统时间是以系统时刻为单位的离散值,系统时刻指的是一段实时间,系统时刻的大小由实时应用需要的时间粒度决定,TTI程序时间语义指令中的预设时间均以系统时刻为单位,根据不同需求,不同TTI程序的系统时刻也不相同.
如果实时应用需要的时间粒度为1 ms,即1个系统时刻为1 ms,那么系统时间20对应的实时间为20 ms. RPU使用标准时钟(stdClk),结合时间粒度寄存器tgr,更新系统时间寄存器ctr的值. 对于实时应用规定的时间粒度,TTI程序可以使用settg指令设置时间粒度寄存器tgr,tgr的值应该设置为tg×f,其中tg为实时应用需要的时间粒度,f为stdClk的频率,假设stdClk的频率为 1 MHz,而实时应用需要的时间粒度为1 ms,则时间粒度寄存器tgr应该设置为0.001 s×1 MHz,即tgr值为1000. 假设实时应用的时间粒度需求变得更为紧致,为0.1 ms,那么tgr应该设置为100.
除了控制TTI程序时序行为的stdClk,RPU存在驱动数据通路各个功能部件同步运行的cpuClk,根据文献[4]中给出的“stdClk和cpuClk关系定理”可知,stdClk和cpuClk存在同步和异步2种关系,在本文中只考虑同步情况,即stdClk的周期TstdClk和cpuClk的周期TcpuClk的关系为TstdClk = n×TcpuClk.
TFG+使用不同节点表示TTI程序中的时间语义指令和普通指令构成的基本块. 由于RPU流水线中同时存在多条指令,TFG+中2个连续节点对应的时间语义指令或基本块的执行会有所重叠. 如图1所示,基本块A的执行时间为tA,基本块B的执行时间为tB,基本块A和基本块B的整体执行时间为tAB,tA + tB > tAB. 文献[5]给出了执行开销的概念,现在结合TFG+进行说明.
定义2. 执行开销. vj为TFG+中节点,vi为vj的直接前驱节点,vj对应程序段的执行开销为vi最后一条指令完成时间到vj最后一条指令完成时间的间隔. 例如,在图1中,基本块B的执行开销为cB.
本文采用执行图[7]的方法进行低级分析,以计算TFG+各个节点的执行开销. 根据定义2,构建TFG+各节点执行图时需要增加前驱节点的最后一条指令的执行信息.
TTI程序的设计流程有3步:
1)对于给出的高层编程模型,分离其时间语义和功能语义,对于上层模型的时间语义,选择合适的TTI程序设计范式进行表达,再结合相应的功能代码,给出对应的TTI程序.
2)构建TTI程序的TFG+,表达TTI程序中的控制流信息、用户规定的程序时间行为以及平台相关的时间属性.
3)基于RPU或其他可以运行TTI指令集的处理器,结合TFG+中控制流信息,构建TFG+每个节点的执行图,基于执行图分析TFG+中每个节点平台相关的时间属性,并根据TFG+用户规定的程序时间行为,进行时间安全性检查.
由于RPU采用的是顺序取指、顺序执行的模式,ttiat,ttoat,delay,mtfd指令的执行会受到前驱代码段执行时间的影响,时间安全性检查是为了保证系统运行时,这些指令的时间语义能正确表达. 时间安全性检查会分析时间语义指令前驱代码段最坏情况下的执行时间,如果前驱代码段的最坏情况下执行时间较长,执行到时间语义指令时系统时间大于预设时间,此时mtfd指令约束代码段执行时间上界的语义被违反,且ttiat,ttoat指令在规定系统时刻完成输入输出操作的语义也被违反;如果前驱代码段执行时间较短,执行到时间语义指令时,系统时间小于指令预设时间,显然满足mtfd指令约束代码段执行时间上界的语义,而ttiat,ttoat,delay指令会停滞流水线,直到RPU的系统时间等于指令预设的时间,此时满足delay指令约束代码段执行时间下界的语义,由于ttiat,ttoat指令语义要求在规定系统时刻完成输入输出操作,所以还需要验证ttiat,ttoat指令的输入输出操作会在规定的系统时刻内完成.
TTI指令集可以通过不同的指令组合表达丰富的时间语义,用来满足用户对于程序时间行为的控制需求. 现在给出TTI指令集能够表达的4种时间语义:
1)绝对点时间语义(absolute timed semantic). 相对于系统0时刻的点时间约束,即规定自系统启动到某一确定时间点的系统行为.
2)绝对段时间语义(absolute timing semantic). 相对于系统0时刻的段时间约束,即规定自系统启动,某一段时间的系统行为.
3)相对点时间语义(relative timed semantic). 相对于某一时刻的点时间约束,即自系统某一时刻到规定时间点的系统行为.
4)相对段时间语义(relative timing semantic). 相对于某一时刻的段时间约束,即自系统某一时刻,规定时间段内的系统行为.
相对时间语义中的“某一时刻”,分为2种情况:
1)设计时确定的时刻. 在系统设计时,已知该时刻的系统时间. 例如,相对时刻是规定的绝对点时间,那么这里相对时间语义中的相对时刻就是系统设计时已知,此时的相对时间语义可以转化成绝对时间语义,即绝对时间等于相对的系统时间加上相对语义预设的系统时间.
2)运行时确定的时刻. 在系统设计时,不能确定该时刻的系统时间,系统时间需要根据系统实际运行情况分析. 例如,相对时刻是系统某一数据输入时刻,该数据输入对应的指令执行完成时间会受到前驱代码段的影响,数据输入的系统时间只有在系统运行时才能确定. 此时的相对时间语义,不能转化成绝对时间语义.
下面介绍TTI指令集对上述时间语义的实现,给出TTI程序设计范式和TTI程序设计规则.
TTI指令集中,可以通过setti设置ctr寄存器来设置系统时间. 整个系统运行前的准备工作完成后,需要使用setti x0指令,将系统时间置为0,表示系统开始运行,ttiat/ttoat指令提供了定时输入/输出语义,可以使用setti x0指令和ttiat/ttoat指令的组合,完成绝对点时间语义的表达.
图2给出绝对点时间的表达示例和实际运行的时序. 如图2(a)所示,init负责初始化系统,设置时间粒度寄存器tgr等,完成后使用setti x0将ctr设置为0,表示系统启动. task1中,设计时需要在系统时间为20时进行输出,所以使用ttoat指令,并将指定触发时间的寄存器(图2(a)中寄存器a0)设置为20.
如图2(b)所示,init任务初始化系统,并通过setti指令将ctr寄存器设置为0,系统启动,task1在某一时刻调度执行,且tast1中ttoat指令在系统时间为20时生效,即ttoat指令的输出操作发生在系统时间20和21之间. 如果将ttoat指令替换成ttiat指令,则表示输入操作的发生在系统时间20和21之间.
绝对段时间和绝对点时间类似,在系统初始化完成后,通过setti x0指令将系统时间置为0,表示系统启动,然后在需要限制的代码段后使用delay/mtfd指令,表达绝对段时间约束.
图3给出绝对段时间的表达示例和实际运行的时序. 如图3(a)所示,init负责初始化并启动系统. task2中,设计时规定delay指令前程序执行时间最少为20,所以将寄存器a0设置为20,使用delay指令,控制程序的绝对段时间行为.
如图3(b)所示,task2在某一时刻调度执行,且task2中delay指令需要保证前驱代码段的执行时间大于等于20. 如果将delay指令替换成mtfd指令,需要保证前驱代码段的执行时间小于20.
用户需要表达相对于系统某一时刻的点时间行为. 这里的“某一时刻”,可以是设计时确定的系统时刻,这样相对点时间语义就可以转化为绝对点时间语义,TTI指令的实现可以转化为上述绝对点时间语义的实现方式. 所以这里主要分析的“某一时刻”,指的是系统运行前无法确定系统时间的时刻,可以使用TTI指令集中提供的getti指令和ttiat/ttoat指令组合的方式表达. 图4给出此种情况下,相对点时间的表达示例和实际运行的时序.
如图4(a)所示,在task3中,用户需要相对getti指令20个时间单位执行输出操作. TTI指令对此种语义的实现为:设置getti指令,获取当前系统时间,存放在a0中,再通过addi指令加上相对时间20,作为ttoat指令的触发时间.
如图4(b)所示,由于getti前程序段的执行时间不确定,所以getti获取的系统时间也需要根据实际运行情况确定,假设的getti执行时系统时间为x,ttoat指令也会在相对于getti指令20个时间单位的x+20生效.
用户需要表达相对于系统某一时刻在一段时间内的程序行为. “某一时刻”和上述相对点时间中的一样,这里主要分析在运行时确定的系统时刻. 图5给出此类情况下,相对段时间的表达示例和实际运行的时序.
如图5(a)所示,在task4中,用户需要getti指令后的代码段执行至少20个时间单位. TTI指令对此种语义的实现和相对点时间语义类似,只需要把ttoat指令改为delay指令.
如图5(b)所示,可以表达getti指令和delay指令间的代码段至少执行20个时间单位.
考虑时间语义指令实际使用场景和TTI程序时间安全性检查的可行性,TTI程序需要遵守2个规则:
1) 为保证TTI程序的时间行为的确定性,时间语义指令集不会出现在程序的某一分支中.
2) 对于运行时确定的相对时间语义,getti指令和对应的时间语义指令之间只有通用计算指令,不会出现其他时间语义指令.
TTI程序时间行为分析和时间安全性检查,需要构建整个程序的抽象表示. 本文对TFG扩展,以TFG+表示TTI程序,TFG+可以表达TTI程序的控制流信息、用户规定的时间行为以及平台相关的时间属性. 如表3所示,TFG+由3部分组成:图结构、程序属性、平台相关属性.
1)图结构. 使用不同节点表示多种时间语义和TTI程序其他组成部分,主要分为:①绝对时间语义节点,包括绝对段时间语义节点(absolute timing point)、绝对点时间语义节点(absolute timed point);②运行时确定的相对时间语义节点,首先是相对时间语义的相对基准点(relative base point),然后分别是相对段时间语义节点(relative timing point)、相对点时间语义节点(relative timed point);③普通指令构成的基本块(basic block)节点;④程序的开始(start)节点. 最后,由TTI程序中的指令执行顺序,构成TFG+中的边. ttiat,ttoat指令根据表达的语义,对应绝对(相对)点时间语义节点;delay,mtfd指令根据表达的语义,对应绝对(相对)段时间语义节点;getti指令对应相对基准点.
2)程序属性. 表示TTI程序平台无关的时间属性,TFG+程序属性中提到的时间均为系统时间. 程序属性包括时间粒度寄存器的值、TTI程序的开始时间、绝对(相对)点(段)时间语义节点对应的预设系统时间.
3)平台相关属性. TTI程序平台相关的时间属性,TFG+平台相关属性中提到的执行开销和时间均以cpuClk周期为单位. 对于普通指令构成的基本块,需要计算每个基本块的执行开销. 对于时间语义节点,该节点对应的时间语义指令需要根据前驱代码段的运行时间,决定时间语义指令的执行开销,为了保证该类指令的时间语义在运行时的正确表达,现在考虑在指令前驱代码段最坏执行情况的前提下,时间语义指令需要的延迟时间和执行开销. 由于TTI程序的时序依赖于stdClk,而逻辑控制依赖于cpuClk,且stdClk周期TstdClk为 cpuClk周期Tcpuclk的整数倍,所以1个系统时刻内包含多个cpuClk周期,所以对于绝对点时间语义节点,需要给出在该节点对应的绝对点时间语义指令前驱代码段最坏执行情况的前提下,绝对点时间指令执行完成相对于某一系统时刻的偏移时间,同理,需要给出任务开始执行相对于某一系统时刻的偏移时间. 如图6所示的平台相关属性coff说明,假设存在绝对点时间语义节点vatdp∈ATdP,且vatdp对应的指令为iatdp,在iatdp的前驱代码段最坏执行情况的前提下,iatdp在系统时间x执行完成,而实际上iatdp会在系统时间x内的某一时间点完成,coff(vatdp)为图6中所示vatdp对应指令执行完成相对于系统时间x的偏移.
如算法1所示,给出TFG+构建算法.
算法1. TFG+构建算法.
输入:TTI程序prog;
输出:时间语义节点集合ATP,ATdP,RTP,RTdP,相对基准点集合RBP,基本块节点集合F,边集合E.
① (N, E) $ \leftarrow $fCFG(prog);
② for N中的每个节点i
③  (ATP, ATdP, RTP, RTdP, RBP, F, E) $ \leftarrow $        partition(i);
④ end for
算法1中,行①对应的fCFG (prog),将prog中时间语义指令当作普通指令构建CFG,输出CFG中的节点集合N和边集合E. 行③中的partition(i),对CFG节点进一步划分,节点i中的时间语义指令(ttiat,ttoat,delay,mtfd)以及获取系统时钟指令(getti)划分为单独节点,并将划分后的节点和边加入对应集合,输出i划分后的各种时间语义节点集合、相对基准点集合、基本块节点集合以及边集合.
图7为具有不同时间语义的TTI程序片段和对应的部分TFG+. 图7(a)TTI程序中使用ttoat指令,表达绝对点时间语义,在TFG+中,ttoat指令对应绝对点时间语义节点,使用平行四边形表示,普通代码段根据程序结构,划分成基本块,对应基本块节点,使用矩形表示. 图7(b)使用delay指令,表达绝对段时间语义,使用圆形表示. 图7(c)使用getti指令和ttoat指令组合,表达运行时确定的相对点时间语义,getti对应相对基准点,使用梯形表示,ttoat指令对应相对点时间语义节点,使用三角形表示. 图7(d)使用getti指令和delay指令组合,表达运行时确定的相对段时间语义,getti对应相对基准点,delay对应相对段时间语义节点,使用菱形表示.
传统程序的CFG只能表达程序中的控制流,即指令执行的时间先后关系(temporal succession);TFG在CFG的基础上扩展时间点(timing point),可以表达代码段的时间行为;TFG+相比TFG加入了点时间语义节点,可以表达时间和操作相结合的点时间行为. 所以TFG+的表达能力强于TFG和CFG,可以表达更为丰富的时间语义.
针对文献[4]提到的RPU的硬件结构,使用基于执行图的低级分析方法,计算TFG+基本块节点和时间语义节点的平台相关属性,同时对时间语义节点进行时间安全性检查.
RPU为5段流水处理器,对应的流水段的集合为S={IF, ID, EX, MM, WB},分别对应取指段、译码段、执行段、访存段、写回段. TFG+中每个节点对应的指令集合为I={i1, i2, …,in}. 执行图的节点集合为VXG,且VXG$ \subseteq $S×I,例如,对于(IF, ij) ∈ VXG,表示指令ij ∈ I处于流水段IF ∈ S. 执行图的边集合为EXG,且EXG$ \subseteq $VXG×VXG,表示执行图节点间的时序依赖. 执行图的边分为2类,如图8(b)所示,为了区分这2类边,在执行图中使用实线和虚线分别表示,且$ {\delta _{(v,{i_m}) \to (w,{\text{ }}{i_n})}} $∈{0, 1}表示2种边,对于实线边$ {\delta _{(v,{i_m}) \to (w,{\text{ }}{i_n})}} $= 1,对于虚线边$ {\delta _{(v,{i_m}) \to (w,{\text{ }}{i_n})}} $= 0.
现有v ∈ S,w∈S,im∈I,in∈I,在执行图中存在节点(v, im)∈VXG,(w, in)∈VXG,且(v, im) → (w, in) ∈EXG,基于此详细说明这2类边.
1) (w, in)只可以在(v, im)完成后开始,此类边用实线表示,且$ {\delta _{(v,{i_m}) \to (w,{\text{ }}{i_n})}} $= 1. 具体来说分为4种情况. ①对于多条指令,RPU顺序发射、顺序执行,即(IF, im−1) → (IF, im),(ID, im−1) → (ID, im),(EX, im−1) → (EX, im),(MM, im−1) → (MM, im),(WB, im−1) → (WB, im),其中im−1和im为2条连续指令. ②对于某一条指令,RPU顺序执行,即(IF, im) → (ID, im),(ID, im) → (EX, im),(EX, im) → (MM, im),(MM, im) → (WB, im). ③数据冒险. RPU使用数据旁路解决大部分数据冒险,而针对只能由延迟流水线解决的数据冒险,即2条连续指令,第1条是访存输入指令,第2条指令需要使用第1条指令的访存结果,需要在执行图中对此种情况构建相应的依赖关系,即存在边(MM, im−1) → (EX, im). ④控制冒险. 采用阻塞流水线的方式解决控制冒险,对于一条分支跳转指令,下一条指令的取指需要延迟到分支指令在执行段产生结果后,即存在边(EX, im−1) → (IF, im).
2) (w, in)可以和(v, im)同时开始,但是不能早于(v, im),此类边用虚线表示,且$ {\delta _{(v,{i_m}) \to (w,{\text{ }}{i_n})}} $= 0. 此类边分为4类,(ID, im−1) → (IF, im),(EX, im−1) → (ID, im),(MM, im−1) → (EX, im),(WB, im−1) → (MM, im),其中im−1和im为2条连续指令.
算法2给出基于RPU的执行图构建算法.
算法2. 基于RPU的执行图构建算法.
输入:程序段prog;
输出:执行图节点集合VXG,执行图边集合EXG.
① VXG $ \leftarrow $fvertex(prog);
② for VXG中每个节点(v, im)
③  if v = IF
④   EXG$ \leftarrow ${(IF, im) → (IF, im+1), (IF, im) →      (ID, im)}∪EXG;
⑤  else
⑥    EXG$ \leftarrow ${(v, im) → (v, im+1), (v, im) →      (fnextstage(v), im), (v, im) →      (fprestage(v), im+1)}∪EXG;
⑦  end if
⑧  if im与im+1存在数据冒险
⑨    EXG$ \leftarrow ${(MM, im) → (EX, im+1)}∪EXG;
⑩  end if
⑪  if im和im+1存在控制冒险
⑫   EXG$ \leftarrow ${(EX, im) → (IF, im+1)}∪EXG;
⑬  end if
⑭ end for
算法2中,行① fvertex (prog)构建执行图中所有的节点,行④和行⑥中构建多条指令顺序发射、顺序执行以及一条指令顺序执行相关的边,行⑥中fnextstage (v)表示流水段v的下一流水段,fprestage (v)表示流水段v的上一流水段,并且除了(v, im) → (fprestage (v), im+1)的$ {\delta _{(v,{i_m}) \to ({f_{{\text{prestage}}}}(v),{\text{ }}{i_{m + 1}})}} $= 0,其余边均为$ {\delta _{(v,{i_m}) \to (w,{\text{ }}{i_n})}} $= 1.
算法2仅适用于RPU,对于其他支持TTI指令集的不同硬件架构,需要根据具体的架构特点对算法2进行修改. 例如,可以通过修改流水段集合适应不同流水线级数的处理器,对于指令间由于资源竞争而产生的结构冒险问题可以在执行图中添加相应类型的依赖边来体现等.
如图8所示,具体的程序段和对应的执行图,假设TFG+中节点包含指令i0,i1,i2,i3,计算节点执行开销需要考虑前驱节点最后一条指令i−1,所以构建 i−1,i0,i1,i2,i3的执行图. i−1和i0存在控制冒险,所以存在边(EX, i−1) → (IF, i0),i2和i3存在数据冒险,所以存在边(MM, i2) → (EX, i3).
对于整个执行图来说,资源集合R={IF, ID, EX, MM, WB}表示和节点执行相关的所有资源的集合,A={ar | r∈R}表示对于当前执行图中所有资源的释放时间.
现在给出执行图中的每个节点的属性,以及每个属性的计算过程,各属性中提到的时间均以cpuClk周期为单位.
假设流水段v、指令im,对应执行图中节点(v, im).
1)${\lambda _{(v,{i_m})}}$,表示指令im在流水段v从就绪到完成需要花费的时间.
计算过程为:如表4所示,给出RPU各类指令在各个流水段花费的时间. 时间指令ttiat,ttoat,delay,需要在流水线的执行段判断系统时间是否到达预设的时间,如果没有到达预设时间,要进行延时操作,所以在执行段存在的延迟时间$\tau $需要根据前驱代码段的执行时间进行判断. 而mtfd指令没有具体实现,所以不考虑mtfd在每个流水段的执行时间. RPU采用理想的存储架构,即访问指令存储器和数据存储器均为1个cpuClk周期,对于其他类型的存储架构,可以进行额外分析,确定指令在各流水段的执行时间,再进行后续的计算. 例如,假设需要考虑指令Cache的命中或缺失,且指令Cache命中时的访存时间为1个cpuClk周期,系统设计者可以通过指令Cache分析,确定每条指令的Cache命中情况,若Cache命中,则该指令在取指段的执行时间为1个cpuClk周期,若Cache缺失,则该指令在取值段的执行时间将会大于1个cpuClk周期,所以表4中所示的所有指令在取指段的执行时间为1+,表示取值时间最小为1个cpuClk周期,而具体值需要根据分析确定,同理,访存指令和ttiat/ttoat指令的在访存段的执行时间也为1+,具体的访存和定时输入输出的时间需要结合实际运行情况分析确定.
2)$ {E_{(v,{i_m})}} = \{ e_{(v,{i_m})}^r \in \{ 0,1\} |r \in R\} $,表示处在流水段v的指令im开始执行是否会受到R中某个资源的影响.
计算过程为:如果节点(v, im)本身执行依赖于资源r∈R,那么$ e_{(v,{i_m})}^r $=1. 另外,如果节点(v, im)任意前驱节点(x, ij),即(x, ij) → (v, im)∈EXG,存在$ e_{(x,{i_j})}^r $=1,则$ e_{(v,{i_m})}^r $=1.
3)$ {D_{(v,{i_m})}} = \{ d_{(v,{i_m})}^r|r \in R\} $,表示资源释放到指令在流水段就绪执行之间的延迟时间,即R中某个资源释放与处在流水段v的指令im开始执行的时间间隔.
计算过程为:对于资源r∈R,考虑(v, im)的所有前驱节点(x, ij),即(x, ij) → (v, im)∈EXG,从资源r释放到节点(v, im)就绪的延迟时间为
$ d_{(v,{i_m})}^r = \mathop {\max }\limits_{(x,{i_j}) \to (v,{i_m})} (e_{(x,{i_j})}^r \times (d_{(x,{i_j})}^r + {\delta _{(x,{i_j}) \to (v,{i_m})}} \times {\lambda _{(x,{i_j})}})) . $
4)${\rho _{(v,{i_m})}}$,表示指令im在流水段v的就绪时间,即指令im在流水段v可以开始执行的时间.
计算过程为:节点(v, im)的就绪时间为
$ {\rho _{(v,{i_m})}} = \mathop {\max }\limits_{r \in R} (e_{(v,{i_m})}^r \times (d_{(v,{i_m})}^r + {a^r})) . $
整个分析和验证流程如图9所示,首先分析TFG+中由普通指令构成的基本块节点的平台相关属性;再结合TFG+中的控制流信息分析时间语义节点的平台相关属性;最后,根据每个时间语义节点的语义要求以及平台相关属性的分析结果,对每个时间语义节点进行时间安全性检查,验证TTI程序运行时指令的语义能否正确表达.
下面分别介绍基本块节点和时间语义节点的平台相关属性确定和时间安全性检查的流程.
1)基本块节点
对于基本块节点,只需要确定基本块的执行开销. 首先对TFG+中每个基本块节点构建执行图,再根据5.2节中执行图节点属性,确定基本块的执行开销.
定理1. 基本块节点执行开销定理. 基本块节点bb∈BB,基本块最后一条指令为in,基本块前一条指令为i−1,整个基本块的执行开销为
$ {c_{\text{f}}}(bb) \leqslant \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_n})}^r - d_{(WB,{i_{ - 1}})}^r) + ({\lambda _{(WB,{i_n})}} - {\lambda _{(WB,{i_{ - 1}})}})) . $
证明. 基本块最后一条指令为in,基本块前一条指令为i−1,当前基本块的执行开销为
$ {c_{\mathrm{f}}}(bb) = ({\rho _{(WB,{i_n})}} + {\lambda _{(WB,{i_n})}}) - ({\rho _{(WB,{i_{ - 1}})}} + {\lambda _{(WB,{i_{ - 1}})}}) \text{,} $
即
$ {c_{\mathrm{f}}}(bb) = ({\rho _{(WB,{i_n})}} - {\rho _{(WB,{i_{ - 1}})}}) + ({\lambda _{(WB,{i_n})}} - {\lambda _{(WB,{i_{ - 1}})}}). $
假设,对于节点(WB, i−1)和(WB, in)的关键资源分别为$ \alpha \in R $,$ \beta \in R $,即
$ {\rho _{(WB,{i_{ - 1}})}} = d_{(WB,{i_{ - 1}})}^\alpha + {a^\alpha } \text{,} $
$ {\rho _{(WB,{i_n})}} = d_{(WB,{i_n})}^\beta + {a^\beta } \text{,} $
$ {\rho _{(WB,{i_n})}} - {\rho _{(WB,{i_{ - 1}})}} = d_{(WB,{i_n})}^\beta - d_{(WB,{i_{ - 1}})}^\alpha + {a^\beta } - {a^\alpha } . $
由于RPU为顺序执行的5段流水线,对于资源集合R={IF, ID, EX, MM, WB},(WB, i−1)会依赖于所有的5个资源. 由此可得
$ d_{(WB,{i_{ - 1}})}^\alpha + {a^\alpha } \geqslant d_{(WB,{i_{ - 1}})}^\beta + {a^\beta } \text{,} $
$ {a^\beta } \leqslant d_{(WB,{i_{ - 1}})}^\alpha + {a^\alpha } - d_{(WB,{i_{ - 1}})}^\beta \text{,} $
$ {\rho _{(WB,{i_n})}} - {\rho _{(WB,{i_{ - 1}})}} \leqslant d_{(WB,{i_n})}^\beta - d_{(WB,{i_{ - 1}})}^\beta \text{,} $
$ {c_{\text{f}}}(bb) \leqslant (d_{(WB,{i_n})}^\beta - d_{(WB,{i_{ - 1}})}^\beta ) + ({\lambda _{(WB,{i_n})}} - {\lambda _{(WB,{i_{ - 1}})}}) \text{,} $
$ {c_{\text{f}}}(bb) \leqslant \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_n})}^r - d_{(WB,{i_{ - 1}})}^r) + ({\lambda _{(WB,{i_n})}} - {\lambda _{(WB,{i_{ - 1}})}})) . $
考虑基本块前驱指令为时间语义指令的情况,即i−1为ttiat,ttoat,delay,对于时间语义指令i−1在执行段产生的延迟,以$ {\tau _{(EX,{i_{ - 1}})}} $表示,由于指令i−1在执行段本身存在1个时钟周期的执行时间,故节点(EX, i−1)执行时间$ {\lambda _{(EX,{i_{ - 1}})}} = 1 + {\tau _{(EX,{i_{ - 1}})}} $,而执行图(WB, i−1),(WB, in)节点的$ {D_{(WB,{i_{ - 1}})}} $和$ {D_{(WB,{i_n})}} $均会受到$ {\tau _{(EX,{i_{ - 1}})}} $的影响,所以最后执行开销的计算不会因为延迟时间$ {\tau _{(EX,{i_{ - 1}})}} $而产生额外的问题. 证毕.
2)时间语义节点
TFG+中时间语义节点的平台相关属性分析和时间安全性检查,沿着TFG+控制流进行,所以在下述分析中,假设当前时间语义节点的所有前驱时间语义节点均完成平台相关属性分析和时间安全性检查.
首先介绍时间语义节点分析需要的映射函数.
①next:{start}∪ATP∪ATdP∪RTP∪RTdP∪RBP → V,映射时间语义节点、开始节点、相对基准点到邻接后继节点.
② pre:ATP∪ATdP∪RTP∪RTdP∪RBP → V,映射时间语义节点、相对基准点到邻接前驱节点.
③ tpre:ATP∪ATdP∪RTP∪RTdP∪RBP → ATdP∪{start},映射时间语义节点、相对基准点到距该节点最近的一个前驱绝对点时间语义节点,如果没有这样的前驱绝对点时间语义节点,则映射到开始节点.
④tjitter:ATP∪ATdP∪RTP∪RTdP∪RBP →$\mathbb{Z}$,映射时间语义节点到该指令延迟判断时间和前一条指令执行完成时间的差值,以及映射相对基准点到对应的getti指令读取ctr的时间和前一条指令执行完成时间的差值. 设计这一函数是为了提升TTI程序时间行为分析的紧致程度,由于RPU底层体系结构采用流水线机制,时间语义指令与获取系统时间指令的执行会和该指令的前驱指令重叠,所以在计算该类指令相应操作开始执行的系统时间时,需要考虑该类指令与其前驱指令由于重叠执行而产生的时间影响. 假设v∈ATP∪ATdP∪RTP∪RTdP∪RBP,v对应指令i0和指令i0的前驱指令i−1,构建指令i0和指令i−1的执行图,由于延迟判断、获取ctr均在执行段进行,所以tjitter相当于计算指令i0在执行段就绪时间与前驱指令i−1在写回段完成时间的差值,即
$ {t_{\text{jitter}}}(v) = {\rho _{(EX,{i_0})}} - ({\rho _{(WB,{i_{ - 1}})}} + {\lambda _{(WB,{i_{ - 1}})}}) . $
根据上述基本块节点执行开销中式(1)的证明过程可得
$ {t_{\text{jitter}}}(v) \leqslant \mathop {\max }\limits_{r \in R} (d_{(EX,{i_0})}^r - d_{(WB,{i_{ - 1}})}^r - {\lambda _{(WB,{i_{ - 1}})}}) . $
⑤tWCET:V×V→$\mathbb{N}$,映射TFG+的2个节点到这2个节点及2个节点间所有节点对应程序段的WCET. 假设有节点v1和v2,v1到v2所有节点的执行开销已知. TFG+给出了节点间控制流信息,而程序循环次数等流事实可以由额外的分析或用户指定的方式给出,最后,tWCET(v1, v2)可以通过IPET得出.
现对TTI程序中4种时间语义进行时间行为分析并进行时间安全性检查.
1)绝对点时间语义节点. 假设绝对点时间语义节点为vatdp∈ATdP. vatdp预设系统时间和最近一个前驱绝对点时间语义节点预设系统时间的差值为
$ dif f = {t_{ATdP}}({v_{{\text{atdp}}}}) - {t_{ATdP}}(tpre({v_{{\text{atdp}}}})) . $
如果vatdp没有前驱的绝对点时间语义节点,那么tpre(vatdp) = start,所以
$ dif f = {t_{ATdP}}({v_{{\text{atdp}}}}) - {t_{start}} . $
将单位转化为cpuClk周期为
$ dif {f_{{\text{cpuClk}}}} = dif f \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} . $
考虑vatdp对应指令和前一条指令重叠执行,程序从tpre(vatdp) 对应指令执行完成到vatdp对应指令的延迟判断阶段(执行段)消耗的CPU时钟周期为
$ cost = {t_{{\text{WCET}}}}(next(tpre({v_{{\text{atdp}}}})),pre({v_{{\text{atdp}}}})) + {t_{\text{jitter}}}({v_{{\text{atdp}}}}) . $
如图10所示,绝对点时间语义节点2种执行时序图中vatdp和tpre(vatdp)对应指令分别为in和in−1. 图10(a),TTI程序执行到绝对点时间语义节点时,系统时间小于预设时间,需要延迟的执行时序图;图10(b),TTI程序执行到绝对点时间语义节点时,系统时间等于预设时间,不需要延迟的执行时序图.
平台相关属性计算分3部分:
①节点延迟. 根据TFG+中的平台相关属性定义,tpre(vatdp)对应指令执行完成相对于系统时刻开始的偏移时间为coff(tpre(vatdp)). 如图10(a)所示,vatdp对应指令在执行段需要的延迟时间为
$ {c_{\text{d}}}({v_{{\text{atdp}}}}) = \max (dif {f_{{\text{cpuClk}}}} - cost - {c_{{\text{off}}}}(tpre({v_{{\text{atdp}}}})),0) . $
②执行开销. 计算前驱代码段最坏执行情况下vatdp的执行开销. vatdp对应指令i0,指令i0前一条指令i−1,构建i0和i−1的执行图. 此时,i0在执行段的延迟时间已知,所以${\lambda _{(EX,{i_0})}}$也已知,和基本块节点的执行开销计算过程一致,由式(1)可知:
$ {c_{\text{t}}}({v_{{\text{atdp}}}}) \leqslant \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_0})}^r - d_{(WB,{i_{ - 1}})}^r) + ({\lambda _{(WB,{i_0})}} - {\lambda _{(WB,{i_{ - 1}})}})) . $
③相对于系统时刻开始的偏移. 点时间语义节点对应指令的操作时间为to,RPU中ttiat(ttoat)输入(输出)操作的时间为访存段1个cpuClk周期的访存开销,加上写回段1个cpuClk周期的写回开销,所以to共2个cpuClk周期. 另外指令在执行段除了额外的延迟时间,还存在1个cpuClk周期的执行时间. 如图10所示,点时间语义节点完成执行相对于系统时刻的偏移为
$ {c_{{\text{off}}}}({v_{{\text{atdp}}}}) = \max (cost + {c_{{\text{off}}}}(tpre({v_{{\text{atdp}}}})) - dif {f_{{\text{cpuClk}}}},0) + ({t_{\text{o}}} + 1) . $
时间安全性检查为:绝对点时间语义节点vatdp,要求输入输出开始和完成在tATdP(vatdp)和tATdP(vatdp) + 1之间. 由于采用延迟机制,输入输出操作的开始时间一定大于等于tATdP(vatdp),现在只需要操作的完成时间小于tATdP(vatdp) + 1即可,所以对于TFG+中的绝对点时间语义节点需要满足要求:
$ {c_{{\text{off}}}}({v_{{\text{atdp}}}}) < {t_{{\text{tg}}}} \times \dfrac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} . $
2)绝对段时间语义节点. 假设绝对段时间语义节点vatp∈ATP. 和绝对点时间语义节点相同,首先计算vatp预设系统时间和最近一个前驱绝对点时间语义节点预设系统时间的差值,并转化为CPU时钟周期,即
$ dif {f_{{\text{cpuClk}}}} = dif f \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} .$
如果vatp对应指令mtfd,那么平台相关属性均为0,只需要验证mtfd语义. 而通过延迟实现的指令delay,语义一定能得到满足,所以只需要计算平台相关属性.
下面讨论delay平台相关属性计算. 如图11所示,delay节点2种执行时序图,其中vatdp和tpre(vatdp)对应指令分别为in和in−1,图11(a)为delay节点需要延迟的执行时序图,图11(b)为不需要延迟的执行时序图. 程序从tpre(vatp)执行完成到vatp的延迟判断阶段(执行段)消耗的cpuClk周期为
$ cost = {t_{{\text{WCET}}}}(next(tpre({v_{{\text{atp}}}})),pre({v_{{\text{atp}}}})) + {t_{\text{jitter}}}({v_{{\text{atp}}}}) . $
平台相关属性计算分为3部分:
①节点延迟. 和绝对点时间语义节点的分析过程相同,vatp对应指令在执行段需要的延迟时间为
$ {t_{\text{d}}}({v_{{\text{atp}}}}) = \max (dif {f_{{\text{cpuClk}}}} - cost - {c_{{\text{off}}}}(tpre({v_{{\text{atp}}}})),0) . $
② 执行开销. 计算前驱代码段最坏执行情况下vatp的执行开销. vatp对应指令i0,指令i0前一条指令i−1,构建i0和i−1的执行图,由式(1)可知:
$ {c_{\text{t}}}({v_{{\text{atp}}}}) \leqslant \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_0})}^r - d_{(WB,{i_{ - 1}})}^r) + ({\lambda _{(WB,{i_0})}} - {\lambda _{(WB,{i_{ - 1}})}})) . $
下面讨论mtfd指令时间安全性检查. vatp对应mtfd指令要求指令前代码段的完成时间小于等于tATP(vatp),所以需要满足要求:
$ dif {f_{{\text{cpuClk}}}} \geqslant {t_{{\text{WCET}}}}(next(tpre({v_{{\text{atp}}}})),pre({v_{{\text{atp}}}})) + {c_{{\text{off}}}}(tpre({v_{{\text{atp}}}})) . $
3)相对点时间语义节点. 此处的相对语义,均指运行时确定的相对点时间语义. 运行时确定的相对点时间语义通过getti和ttiat(ttoat)指令组合的形式表达,如图12(a)所示,运行时确定的相对点时间语义的时序图,getti指令获取系统时间处在1个系统时刻内,在系统时刻的具体位置需要根据执行情况确定. 为保证系统运行时时间语义指令的正确性,如图12(b)所示,在时间安全性检查时,假设getti指令在系统时刻最后读取系统时间. 而对于相对点时间语义指令的延迟时间等平台相关属性,则根据前驱代码段最坏执行情况进行分析.
假设相对点时间语义节点为vrtdp∈RTdP,对应的相对基准点为vrbp∈RBP. vrbp对应的getti指令会在EX段读取系统时间,所以从getti读取系统时间(EX段)到vrtdp的延迟判阶段(执行段)消耗的cpuClk周期,还需要加上getti指令执行段、访存段、写回段的执行时间,对于RPU来说为3个CPU时钟周期,结果为
$ cost = {t_{{\text{WCET}}}}(next({v_{{\text{rbp}}}}),pre({v_{{\text{rtdp}}}})) + {t_{\text{jitter}}}({v_{{\text{rtdp}}}}) + 3 . $
平台相关属性计算分2部分:①节点延迟. 如图13所示,vrbp对应的getti指令在执行段的时间相对于系统时刻开始的偏移为offset,该偏移时间受到vatp前一个绝对点时间语义节点或程序开始时间的影响,图13中假设getti指令的前一个绝对点时间语义指令为in−1. 首先,tpre(vrtdp )对应指令执行完成到vrbp对应getti指令的执行段的时间为
$ cost' = {t_{{\text{WCET}}}}(next(tpre({v_{{\text{rtdp}}}})),pre({v_{{\text{rbp}}}})) + {t_{\text{jitter}}}({v_{{\text{rbp}}}}) . $
vrbp对应的getti指令执行段相对于系统时刻开始的偏移时间为
$ \begin{split}&of fset = (cost' + {c_{{\text{off}}}}(tpre({v_{{\text{rtdp}}}}))) -\\ & \left\lfloor {(cost' + {c_{{\text{off}}}}(tpre({v_{{\text{rtdp}}}}))) \times \frac{{{T_{{\text{cpuClk}}}}}}{{{T_{{\text{stdClk}}}} \times {t_{{\text{tg}}}}}}} \right\rfloor \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}}.\end{split} $
vrtdp在执行段的延迟时间为
$ {t_{\text{d}}}({v_{{\text{rtdp}}}}) = \max ({t_{RTdP}}({v_{{\text{rtdp}}}}) \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} - cost - of f set,0) . $
②执行开销. vrtdp对应指令i0,指令i0前一条指令i−1,构建i0和i−1的执行图. 由式(1)可知:
$ {c_{\text{t}}}({v_{{\mathrm{rtdp}}}}) \leqslant \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_0})}^r - d_{(WB,{i_{ - 1}})}^r) + ({\lambda _{(WB,{i_0})}} - {\lambda _{(WB,{i_{ - 1}})}})) . $
下面讨论时间安全性检查. vrbp对应的getti指令获取的系统时间,会受到前驱代码段的执行时间的影响,只考虑前驱代码段的最坏执行情况,不一定能保证后续相对点时间语义指令的正确性. 图14(a)显示前驱代码最好执行情况下,vrbp和vrtdp间程序的允许执行时间tb;图14(b)显示前驱代码最坏执行情况下,vrbp和vrtdp间程序的允许执行时间tw. 图14中,getti指令最好执行情况下获取到的系统时间为y ,getti指令最坏执行情况下获取到的系统时间为 x,存在y < x,显然tw > tb.
如图14(b)所示,验证时假设vrbp 读取系统时间,发生在系统时刻最后,vrtdp对应指令的操作时间为to,所以为保证相对点时间语义的正确性,需满足3个要求:
$ cost < {t_{RTdP}}({v_{{\text{rtdp}}}}) \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} \text{,} $
$ {t_{\text{o}}} + 1 < {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} \text{,} $
$ cost + {t_{\text{o}}} + 1 < {t_{RTdP}}({v_{{\text{rtdp}}}}) \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} . $
第1个要求保证相关程序段的执行时间不超过限定时间;第2个要求保证输入输出操作的时间不超过限定时间,其中加1为vrtdp对应指令在执行段除了延迟以外的1个cpuClk周期;第3个要求保证程序段执行以及输出输入操作的时间不超过限定时间.
4)相对段时间语义节点. 假设相对段时间语义节点为vrtp∈RTP,对应的相对基准点为vrbp∈RBP. 和相对点时间语义节点相同,从getti读取系统时间(执行段)到vrtp的延迟判阶段(执行段)消耗的CPU时钟周期为
$ cost = {t_{{\text{WCET}}}}((next({v_{{\text{rbp}}}})),pre({v_{{\text{rtp}}}})) + {t_{\text{jitter}}}({v_{{\text{rtp}}}}) + 3 . $
和绝对段时间语义节点相同,如果vrtp对应指令为mtfd,tjitter (vrtp )=0,且只需验证mtfd语义. delay指令,只需要计算平台相关属性.
delay指令平台相关属性计算分2部分:
①节点延迟. 和相对点时间语义节点相同,tpre(vrtp)对应指令执行完成到vrbp对应getti指令的执行段的时间为
$ cost' = {t_{{\text{WCET}}}}(next(tpre({v_{{\text{rtp}}}})),pre({v_{{\text{rbp}}}})) + {t_{\text{jitter}}}({v_{{\text{rbp}}}}) .$
vrbp对应的getti指令执行段相对于系统时刻开始的偏移时间为
$ \begin{split}&of fset = (cost' + {c_{{{of f}}}}(tpre({v_{{\text{rtp}}}}))) -\\ &\left\lfloor {(cost' + {c_{{\text{off}}}}(tpre({v_{{\text{rtp}}}}))) \times \frac{{{T_{{\text{cpuCl}}k}}}}{{{T_{{\text{stdClk}}}} \times {t_{{\text{tg}}}}}}} \right\rfloor \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}}. \\ \end{split} $
vrtp在执行段的延迟时间为
$ {t_{\text{d}}}({v_{{\text{rtp}}}}) = \max ({t_{RTP}}({v_{{\text{rtp}}}}) \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} - cost - of fset,0) . $
②执行开销. vrtp对应指令i0,指令i0前一条指令i−1,构建指令i0和i−1执行图,由式(1)可知:
$ {c_{\text{t}}}({v_{{\text{rtp}}}}) \leqslant \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_0})}^\beta - d_{(WB,{i_{ - 1}})}^\beta ) + ({\lambda _{(WB,{i_0})}} - {\lambda _{(WB,{i_{ - 1}})}})) . $
下面讨论mtfd指令时间安全性检查. 和相对点时间语义验证相同,考虑getti指令执行的最坏情况. 假设vrbp对应getti指令执行段读取系统时间发生在系统时刻最后,所以为保证相对段时间语义的正确性,需满足要求:
$ cost < ({t_{RTP}}({v_{{\text{rtp}}}}) - 1) \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} . $
本节给出TTI程序示例,并对TTI程序进行时间行为分析和时间安全性检查,最后通过在RPU上实际部署运行,验证时间行为分析和时间安全性检查的正确性. 本节主要有2个应用示例,分别为自动驾驶示例和防抱死系统示例.
本文采用文献[4]中给出的自动驾驶示例. 假设一个自动驾驶系统中有3个任务:1)采集任务,传感器采集数据,进行数据预处理,周期为2 ms;2)分析任务,对预处理之后的数据进行分析和处理,得到响应数据,周期为1 ms;3)执行任务,将响应数据分发到执行器,周期为2 ms.
使用交错LET语义对任务集进行实现,图15显示了该任务集的任务分解和建模时序,虚线箭头体现了任务的数据依赖关系. 其中,每个任务被分解为3个子任务,分别为I,C,O,其中O和I这2个子任务被合并为一个OI子任务组,保证了该任务集的交错LET语义.
任务1对应采集任务,t1oi对应采集任务的OI子任务组,t1c对应采集任务的C任务. 任务2对应分析任务,t2oi1对应分析任务第1个周期的OI子任务组,t2c1对应分析任务第1个周期的C任务,同理,t2oi2,t2c2分别对应分析任务第2个周期的OI子任务和C任务. 任务3对应执行任务,t3oi对应执行任务的OI子任务组,t3c对应执行任务的C任务. 最后自动驾驶示例的实现代码如图16所示,RPU提供了硬件多线程机制,所以将任务分类放置在不同的硬件线程上,其中0号硬件线程(thread 0)用于初始化系统,1号硬件线程(thread 1)用于执行OI子任务,2号硬件线程(thread 2)用于执行C任务,3号硬件线程(thread 3)用于执行软实时任务. 可以使用TTI指令集中的并发管理指令,控制硬件线程的调度时间,从而确定硬件线程上每个任务的调度时间. 如图16所示,为自动驾驶系统在RPU各硬件线程上的程序.
现在给出运行自动驾驶示例的RPU参数,RPU的cpuClk频率为25 MHz,TcpuClk为0.04 μs,stdClk频率为1MHz,TstdClk为1 μs,stdClk和cpuClk同步,且时间粒度为25,即1个系统时刻为25 μs.
如表5所示,给出LET实例中每个任务程序的属性. 任务1、任务2、任务3对应的C任务是普通程序,OI子任务是TTI程序,每个OI子任务中都需要分别表达输入和输出绝对点时间语义,且对应不同的系统时间. 另外给出每个任务被调度执行的系统时间.
现在给出自动驾驶示例中C任务WCET分析结果,t1c的WCET为0.5 ms,t2c1和t2c2的WCET为0.25 ms,t3c的WCET为0.5 ms. 自动驾驶示例中每个任务的OI子任务的程序结构类似,所以使用t3oi作为例子进行说明. 如图17所示,t3oi任务对应TTI程序和TFG+,图17中省略部分分别表示t3oi在指令ttoat执行前的准备工作和指令ttiat执行后的处理工作,此部分由普通指令构成,所以在TFG+中对此部分的普通基本块节点进行省略. 下面给出TFG+中程序属性和平台相关属性.
1)程序属性. 除时间粒度,TFG+此类属性的单位均为系统时刻. TFG+中时间粒度ttg = 25,任务开始系统时间tstart = 6,ttoat指令对应绝对点时间语义节点v1∈ATdP,ttiat指令对应绝对段时间语义节点v2∈ATdP,ttoat指令预设系统时间为tATdP(v1) = 7,ttiat指令的预设系统时间为tATdP(v2) = 7.
2)平台相关属性. TFG+此类属性的单位均为cpuClk周期. t3oi在指令ttoat前的准备工作的最坏情况下的执行开销为200个cpuClk周期,以及指令ttiat后的处理工作的最坏情况下的执行开销为300个cpuClk周期. 首先,计算节点v1的平台相关属性,并验证节点v1对应ttoat指令的语义. 根据式(3),计算节点v1预设时间和任务开始时间的差值并转化为cpuClk周期:
$ \begin{split}dif {f_{{\text{cpuClk}}}} = &({t_{ATdP}}({v_1}) - {t_{start}}) \times {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} = \\ &(7 - 6) \times 25 \times 25 = 625.\end{split} $
RPU在系统时间为6时执行t3oi任务,任务开始相对于系统时刻开始的偏移为0,所以$ {c_{{\text{off}}}}(start) = 0 $. 计算从任务开始执行到v1的延迟判断阶段消耗的cpuClk周期,由式(4)可得
$ cost = {t_{{\text{WCET}}}}(next(start),pre({v_1})) + {t_{\text{jitter}}}({v_1}). $
由于t3oi在执行ttoat前的准备工作的WCET为200个cpuClk周期,即
$ {t_{{\text{WCET}}}}(next(start),pre({v_1})) = 200 . $
对于v1延迟判断时间和前一条指令执行完成时间的差值tjitter(v1),需要构建执行图,如图18所示,其中$\tau $表示ttoat指令在执行段的延迟时间. 根据式(2),执行图节点信息可得
$ \begin{gathered}{t_{\text{j}}}({v_1}) = \mathop {\max }\limits_{r \in R} (d_{(EX,{i_0})}^r - d_{(WB,{i_{ - 1}})}^r - {\lambda _{(WB,{i_{ - 1}})}}) = \\ 3 - 4 - 1 = - 2, \\ \end{gathered} $
$ \begin{gathered}cost = {t_{{\text{WCET}}}}(next(start),pre({v_1})) + {t_{\text{jitter}}}({v_1})= \\ 200 - 2 = 198. \\ \end{gathered} $
由式(5),节点v1对应指令的延迟时间为$ \tau = {t_{\text{d}}}({v_1}) $,且
$ \begin{gathered}{t_{\text{d}}}({v_1}) = \max (dif {f_{{\text{cpuClk}}}} - cost - {c_{{\text{off}}}}(start),0) = \\ 625 - 198 - 0 = 427. \\ \end{gathered} $
如图17所示,根据节点v1的延迟时间和执行图中节点信息,由式(6),节点v1执行开销为
$ \begin{gathered}{c_{\text{t}}}({v_1}) = \mathop {\max }\limits_{r \in R} ((d_{(WB,{i_0})}^r - d_{(WB,{i_{ - 1}})}^r) + ({\lambda _{(WB,{i_0})}} - {\lambda _{(WB,{i_{ - 1}})}}) ) =\\ (432 - 4) + (1 - 1) = 428. \\ \end{gathered} $
由式(7),相对于系统时刻的偏移为
$ {c_{{\text{off}}}}({v_1}) = \max (cost + {c_{{\text{off}}}}(start) - dif {f_{{\text{cpuClk}}}},0) + ({t_{\text{o}}} + 1) .$
对于RPU来说,输入操作的时间to = 2,所以
$ {c_{{\text{off}}}}({v_1}) = 0 + (2 + 1) = 3 .$
最后,进行时间安全性检查,即
$ {c_{{\text{off}}}}({v_1}) < {t_{{\text{tg}}}} \times \frac{{{T_{{\text{stdClk}}}}}}{{{T_{{\text{cpuClk}}}}}} \text{,} $
节点v1对应ttoat指令的语义可以得到保证.
对于v2的平台相关属性的计算和v1类似,给出v2平台相关属性的计算结果. 节点v2和节点v1的预设时间相同,所以节点v2的延迟时间为$ {t_{\text{d}}}({v_2}) = 0 $,执行开销为$ {c_{\text{t}}}({v_2}) = 1 $,相对于系统时刻开始的偏移为$ {c_{{\text{off}}}}({v_2}) = 4 $,所以v2的语义也通过验证.
至此任务t3oi时间行为分析和语义验证完成,其他时间语义程序的分析和验证过程类似. 图19为自动驾驶示例在RPU上的运行时序图. 在图19中,给出每个绝对点时间语义指令生效的实时间,将表5中每个时间语义指令预设时间转化为实时间后,和图15进行比较可知,语义均正确表达,同时,LET语义也得到保证.
防抱死系统(anti-lock braking system, ABS)是为了防止车轮在紧急刹车过程中车轮抱死而导致车辆失控的控制系统,ABS最早于1950年在文献[32]中提出,现在广泛应用在车辆的刹车控制系统中. 本文采用LET编程模型,实现ABS中的控制器部分,并且将LET模型映射至TTI程序,通过时间行为分析和时间安全性检查验证时间语义指令的正确性,最后部署到RPU上,验证TTI程序的功能和时序的正确性.
如图20所示,ABS的控制模型有5个部分:车辆、车轮、转差、摩擦以及控制器. 车辆部分的输入为摩擦系数mu,输出为车辆速度vv,以及地面对车轮的摩擦力Ff;车轮部分的输入为来自地面的摩擦力Ff以及控制器部分施加给车轮的刹车扭矩Tb,输出为车轮的角速度ww;转差部分的输入为车辆的速度vv,以及车轮的角速度ww,输出为轮胎和地面的转差s;摩擦部分的输入为转差s,输出当前车轮相对地面的摩擦系数mu;控制器部分的输入为转差s,以及车辆的速度vv,输出为应当施加给车轮的刹车扭矩Tb. 各部分连接起来构成一个自反馈系统.
ABS模型中除控制器外的其余部分在模拟物理环境以及作为传感器输入,控制器部分通过特定算法控制整个ABS,而且控制器部分的算法具有硬实时性、周期性、I/O特性等,适合使用LET编程模型. 图21所示为控制器部分的具体构成,控制器部分的输入为转差s和车辆速度vv,输出为刹车扭矩Tb,其中控制器部分可以根据转差的大小调整输出的刹车扭矩,车辆速度用来判断是否需要防抱死控制,当车辆速度小于规定的最小速度vmin,不需要进行防抱死控制. 由于车辆转差在0.2时,车轮和地面产生的摩擦力最大,刹车效果最好,所以控制器部分的目的在于通过调整刹车扭矩的大小,将车轮和地面的转差维持在0.2左右,控制器部分会比较当前转差和0.2的差值,并将结果通过一个bang-bang控制器输出为正负信号,液压系统(hydraulic system)通过接收该信号来调整刹车扭矩,最后控制系统将刹车扭矩输出,以实现对车轮的控制.
如图22所示,ABS模型中控制器部分对应的TTI程序,其中控制器部分算法采用交错语义的LET编程模型实现,和6.1节自动驾驶示例不同,ABS控制器部分代码将LET中的OI子任务和C任务合并在一个TTI程序中.
图22中寄存器a7中的值表示控制算法的周期,可以根据具体的需求确定,控制算法会在周期开始,使用ttoat指令定时输出上一轮计算得到的刹车扭矩,使用ttiat指令定时输入本轮计算刹车扭矩需要的转差和车辆速度,然后经过图22中所示计算过程,确定本轮需要输出的刹车扭矩.
运行图22所示控制器部分TTI程序的RPU参数和6.1节中自动驾驶示例相同. 控制算法的执行周期为2 ms. 如图23所示,控制器部分TTI程序对应的部分TFG+. 该TFG+是将TTI程序中循环展开构建,对应TTI程序中第1轮循环和第2轮循环,其中第1轮循环为图22中行①~⑬内容,该轮循环中绝对点时间语义指令需要在0 ms完成相应操作;第2轮循环为图22中行④~⑬内容,且第2轮循环中的行⑤⑥的时间语义指令分别对应TFG+中的绝对点时间语义节点v1,v2,v3,这3个节点对应指令需要在2 ms完成相应操作. 显然如果图23中TFG+对应的TTI程序可以通过时间安全性检查,则图22中TTI程序后续循环的时序正确性也可以得到保证.
经过时间行为分析和时间安全性检查图23所示控制器部分TTI程序中时间语义指令均能正确执行,图24显示控制器部分TTI程序第1轮和第2轮循环在RPU上运行的时序图. 图24中O表示定时输出指令,I1和I2分别表示2条定时输入指令,第1轮循环的时间为0~2 ms,第2轮循环的时间为2~4 ms. 根据图24可知,定时输入、定时输出操作均在规定的系统时刻内完成,符合ABS中控制器部分对于时序的要求.
通用计算机在指令集架构中没有提供时间语义指令,导致上层控制模型中的时间行为无法精确自然地映射至程序代码,控制精度大大降低,系统的实时性受到影响.
本文在已经提出的TTI指令集基础上,总结了TTI指令集可以表达的4种时间语义,以此来描述复杂系统的时间行为. 并且提出了TTI程序的表示TFG+,同时,基于RPU给出了分析TTI程序时间行为和时间安全性检查的方法.
未来,我们将进一步完善TTI指令集相关工作,对TTI指令集语义进行形式化说明,以及扩展TFG+对并发语义的支持.
作者贡献声明:高银康提出思想、撰写论文;陈香兰、龚小航、蒋滨泽、李曦、周学海提供论文撰写指导和修改意见.

参考文献 引证文献
排序方式:
1
Henzinger T, Horowitz B, Kirsch C. Giotto: A time-triggered language for embedded programming[C]// Proc of the 1st EMSOF. New York: ACM, 2001: 166−184
2
Bui D, Lee E, Liu I, et al. Temporal isolation on multiprocessing architectures[C]// Proc of the 48th Design Automation Conf. New York: ACM, 2011: 274−279
3
Lee E, Reineke J, Zimmer M. Abstract PRET machines[C]// Proc of the 38th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 2017: 1−11
4
汪超,陈香兰,章博,等. 一种具有时间语义的实时处理器模型[J]. 计算机研究与发展,2021,58(6):1176−1191
Wang Chao, Chen Xianglan, Zhang Bo, et al. A real-ime processor model with timing semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176−1191 (in Chinese)
5
Natarajan S, Broman D. Timed C: An extension to the C programming language for real-time systems[C]// Proc of the 24th IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2018: 227−239
6
Natarajan S, Broman D. Temporal property-based testing of a timed C compiler using time-flow graph semantics[C/OL]// Proc of the 23rd Forum for Specification and Design Languages. Piscataway, NJ: IEEE, 2020 [2023-02-24].https://doi.org/10.1109/FDL50818.2020.9232935
7
Rochange C, Sainrat P. A context-parameterized model for static analysis of execution times[M]// Transactions on High-Performance Embedded Architectures and Compilers II. Berlin: Springer, 2009: 222−241
8
Lee E. What is real time computing? A personal view[J]. IEEE Design and Test, 2018, 35(2): 64−72
9
Lickly B, Liu I, Kim S, et al. Predictable programming on a precision timed architecture[C]// Proc of the 11th Int Conf on Compilers, Architectures and Synthesis for Embedded Systems. New York: ACM, 2008: 137−146
10
Zimmer M, Broman D, Shaver C, et al. FlexPRET: A processor platform for mixed-criticality systems[C]// Proc of the 19th 2014 IEEE Real-Time and Embedded Technology and Applications Symp. Piscataway, NJ: IEEE, 2014: 101−110
11
Turing A M. On computable numbers, with an application to the entscheidung sproblem[J]. Proceedings of the London Mathematical Society, 1937, 2(1): 230−265
12
Von Neumann J. First draft of a report on the EDVAC[J]. IEEE Annals of the History of Computing, 1993, 15(4): 27−75
13
Knial P, Mokrushin L, Thiagarajan P S, et al. Timed vs time-triggered automata[C]// Proc of the 15th Int Conf on Concurrency Theory. Berlin: Springer, 2004: 340−354
14
Waterman A S. Design of the RISC-V instruction set architecture[D]. Berkeley, CA: University of California, Berkeley, 2016
15
Hennessy J L, Patterson D A. Computer Architecture: A quantitative Approach[M]. San Francisco: Margan Kaufmann, 2011
16
Boldt M, Traulsen C, von Hanxleden R. Worst case reaction time analysis of concurrent reactive programs[J]. Electronic Notes in Theoretical Computer Science, 2008, 203(4): 65−79
17
Berry G, Gonthier G. The Esterel synchronous programming language: Design, semantics, implementation[J]. Science of Computer Programming, 1992, 19(2): 87−152
18
Andalam S, Roop P, Girault A, et al. PRET-C: A new language for programming precision timed architectures[D]. Grenoble, France: Institut National de Recherche en Informatique et en Automatique, 2009
19
Roop P S, Andalam S, von Hanxleden R, et al. Tight WCRT analysis of synchronous C programs[C]// Proc of the 12th Int Conf on Compilers, Architecture, and Aynthesis For Embedded Systems. New York: ACM, 2009: 205−214
20
Cooper K D, Harvey T J, Waterman T. Building a control-flow graph from scheduled assembly code[R]. Texas: Rice University, 2002
21
Kirner R, Knoop J, Prantl A, et al. WCET analysis: The annotation language challenge[C]// Proc of the 7th Int Workshop on Worst-Case Execution Time Analysis. Schloss Dagstuhl: Leibniz-Zentrum für Informatik, 2007: 83−99
22
Asavoae M, Maiza C, Raymond P. Program semantics in model-based WCET analysis: A state of the art perspective[C]// Proc of the 13th Int Workshop on Worst-Case Execution Time Analysis. Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, 2013: 32−41
23
Cousot P, Cousot R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints[C]// Proc of the 4th ACM SIGACT-SIGPLAN Symp on Principles of Programming Languages. New York: ACM, 1977: 238−252
24
Fields B, Rubin S, Bodik R. Focusing processor policies via critical-path prediction[C]// Proc of the 28th Annual International Symp on Computer Architecture. Piscataway, NJ: IEEE, 2001: 74−85
25
Li Xianfeng, Roychoudhury A, Mitra T. Modeling out-of-order processors for WCET analysis[J]. Real-Time Systems, 2006, 34(3): 195−227
26
Ferdinand C, Heckmann R. aiT: Worst-case Execution Time Prediction by Static Program Analysis[M]// Building the Information Society. Berlin: Springer, 2004: 377−383
27
Li Xianfeng, Liang Yun, Mitra T, et al. Chronos: A timing analyzer for embedded software[J]. Science of Computer Programming, 2007, 69(1/2/3): 56−67
28
Allabriga C, Cassé H, Rochange C, et al. OTAWA: An open toolbox for adaptive WCET analysis[C]//Proc of the 8th IFIP Int Workshop on Software Technolgies for Embedded and Ubiquitous Systems. Berlin: Springer, 2010: 35−46
29
Puschner P, Koza C. Calculating the maximum execution time of real-time programs[J]. Real-Time Systems, 1989, 1(2): 159−176
30
Shaw A C. Reasoning about time in higher-level language software[J]. IEEE Transactions on Software engineering, 1989, 15(7): 875−889
31
Li Y T S, Malik S. Performance analysis of embedded software using implicit path enumeration[C]// Proc of the 1st ACM SIGPLAN 1995 Workshop on Languages, Compilers, &amp; Tools For Real-Rime Rystems. New York: ACM , 1995: 88−98
32
Lawes J. Car Brakes: A Guide to Upgrading, Repair and Maintenance[M]. Marlborough, UK: The Crowood Press, 2014
2024年第61卷第1期
61
30
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202220730
  • 接收时间:2022-08-22
  • 首发时间:2026-11-17
  • 出版时间:2024-01-02
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2022-08-22
  • 修回日期:2023-04-19
基金
作者信息
    中国科学技术大学计算机科学与技术学院 合肥 230027
    中国科学技术大学苏州高等研究院 江苏苏州 215004

通讯作者:

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

扫描看全文

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