基于RPU 的TTI 程序設計和分析方法

高銀康 陳香蘭 龔小航 蔣濱澤 李 曦 周學海

（中國科學技術大學計算機科學與技術學院 合肥 230027）

（中國科學技術大學蘇州高等研究院 江蘇蘇州 215004）

（gaoyinkang@mail.ustc.edu.cn）

實時嵌入式系統（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+，基于實時處理單元（realtime processing unit，RPU），采用基于執行圖[7]的低級分析方法，分析了TTI 程序的時間行為，并且對TTI程序的時間語義指令進行時間安全性檢查，驗證其語義在執行時能夠得到正確表達. 本文提出的TFG+構建方法、時間行為分析方法以及時間安全性檢查方法適用于RPU 和其他可以運行TTI 指令集的處理器架構，若采用除RPU 外的其他架構，只需要修改執行圖的構建方法和執行圖節點屬性的計算方法即可.

本文的主要貢獻有3 個方面：

1） 提出TTI 程序的設計范式，明確TTI 程序可以表達的4 種時間語義，使編程人員能夠精確自然地表達上層的設計.

2） 提出TFG+，以表示TTI 程序，TFG+可以表達TTI 程序的控制流信息、用戶規定的時間行為以及平臺相關的時間屬性，為TTI 程序的分析和時間安全性檢查提供了依據.

3） 提出了TTI 程序的時間行為分析方法和時間安全性檢查方法，保證TTI 程序運行時指令的語義能夠正確表達.

1 相關工作

相關工作分為時間語義指令集、程序抽象表示和程序時間行為分析3 個方面進行介紹.

1.1 時間語義指令集

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]中對于指令的語義進行了詳細說明.

Table 1 Time Semantic Registers表1 時間語義寄存器

Table 2 Time Semantic Instructions表2 時間語義指令

目前時間語義指令集的相關工作僅說明了每條指令的語義和對應的硬件實現方案，缺乏時間語義指令集表達能力的說明，同時，沒有給出時間語義程序的設計范式，導致無法直接自然地定義上層模型中時間語義與底層時間語義程序的映射關系.

文獻[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 程序，所以省略任務并發管理指令的實現.

1.2 程序的表示

傳統程序進行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 的擴充，表達了更為豐富的時間語義，例如點時間語義.

1.3 程序時間行為分析

現有的程序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）.

2 TTI 程序設計流程

本節給出TTI 程序相關概念，以及設計TTI 程序的基本流程.

2.1 相關概念

由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+進行說明.

Fig.1 Example of execution cost圖1 執行開銷示例

定義2.執行開銷.vj為TFG+中節點，vi為vj的直接前驅節點，vj對應程序段的執行開銷為vi最后一條指令完成時間到vj最后一條指令完成時間的間隔.例如，在圖1 中，基本塊B的執行開銷為cB.

本文采用執行圖[7]的方法進行低級分析，以計算TFG+各個節點的執行開銷. 根據定義2，構建TFG+各節點執行圖時需要增加前驅節點的最后一條指令的執行信息.

2.2 TTI 程序設計流程

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 指令的輸入輸出操作會在規定的系統時刻內完成.

3 TTI 程序設計范式

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 程序設計規則.

3.1 絕對點時間

TTI 指令集中，可以通過setti 設置ctr 寄存器來設置系統時間. 整個系統運行前的準備工作完成后，需要使用settix0 指令，將系統時間置為0，表示系統開始運行，ttiat/ttoat 指令提供了定時輸入/輸出語義，可以使用settix0 指令和ttiat/ttoat 指令的組合，完成絕對點時間語義的表達.

圖2 給出絕對點時間的表達示例和實際運行的時序. 如圖2（a）所示，init 負責初始化系統，設置時間粒度寄存器tgr 等，完成后使用settix0 將ctr 設置為0，表示系統啟動. task1 中，設計時需要在系統時間為20時進行輸出，所以使用ttoat 指令，并將指定觸發時間的寄存器（圖2（a）中寄存器a0）設置為20.

Fig.2 Example of absolute timed semantic圖2 絕對點時間語義示例

如圖2（b）所示，init 任務初始化系統，并通過setti 指令將ctr 寄存器設置為0，系統啟動，task1 在某一時刻調度執行，且tast1 中ttoat 指令在系統時間為20 時生效，即ttoat 指令的輸出操作發生在系統時間20 和21 之間. 如果將ttoat 指令替換成ttiat 指令，則表示輸入操作的發生在系統時間20 和21 之間.

3.2 絕對段時間

絕對段時間和絕對點時間類似，在系統初始化完成后，通過settix0 指令將系統時間置為0，表示系統啟動，然后在需要限制的代碼段后使用delay/mtfd指令，表達絕對段時間約束.

圖3 給出絕對段時間的表達示例和實際運行的時序. 如圖3（a）所示，init 負責初始化并啟動系統. task2中，設計時規定delay 指令前程序執行時間最少為20，所以將寄存器a0 設置為20，使用delay 指令，控制程序的絕對段時間行為.

Fig.3 Example of absolute timing semantic圖3 絕對段時間語義示例

如圖3（b）所示，task2 在某一時刻調度執行，且task2 中delay 指令需要保證前驅代碼段的執行時間大于等于20. 如果將delay 指令替換成mtfd 指令，需要保證前驅代碼段的執行時間小于20.

3.3 相對點時間

用戶需要表達相對于系統某一時刻的點時間行為. 這里的“某一時刻”，可以是設計時確定的系統時刻，這樣相對點時間語義就可以轉化為絕對點時間語義，TTI 指令的實現可以轉化為上述絕對點時間語義的實現方式. 所以這里主要分析的“某一時刻”，指的是系統運行前無法確定系統時間的時刻，可以使用TTI 指令集中提供的getti 指令和ttiat/ttoat 指令組合的方式表達. 圖4 給出此種情況下，相對點時間的表達示例和實際運行的時序.

Fig.4 Example of relative timed semantic圖4 相對點時間語義示例

如圖4（a）所示，在task3 中，用戶需要相對getti指令20 個時間單位執行輸出操作. TTI 指令對此種語義的實現為：設置getti 指令，獲取當前系統時間，存放在a0 中，再通過addi 指令加上相對時間20，作為ttoat 指令的觸發時間.

如圖4（b）所示，由于getti 前程序段的執行時間不確定，所以getti 獲取的系統時間也需要根據實際運行情況確定，假設的getti 執行時系統時間為x，ttoat 指令也會在相對于getti 指令20 個時間單位的x+20 生效.

3.4 相對段時間

用戶需要表達相對于系統某一時刻在一段時間內的程序行為. “某一時刻”和上述相對點時間中的一樣，這里主要分析在運行時確定的系統時刻. 圖5給出此類情況下，相對段時間的表達示例和實際運行的時序.

Fig.5 Example of relative timing semantic圖5 相對段時間語義示例

如圖5（a）所示，在task4 中，用戶需要getti 指令后的代碼段執行至少20 個時間單位. TTI 指令對此種語義的實現和相對點時間語義類似，只需要把ttoat指令改為delay 指令.

如圖5（b）所示，可以表達getti 指令和delay 指令間的代碼段至少執行20 個時間單位.

3.5 TTI 程序設計規則

考慮時間語義指令實際使用場景和TTI 程序時間安全性檢查的可行性，TTI 程序需要遵守2 個規則：

1） 為保證TTI 程序的時間行為的確定性，時間語義指令集不會出現在程序的某一分支中.

2） 對于運行時確定的相對時間語義，getti 指令和對應的時間語義指令之間只有通用計算指令，不會出現其他時間語義指令.

4 TFG+定義

TTI 程序時間行為分析和時間安全性檢查，需要構建整個程序的抽象表示. 本文對TFG 擴展，以TFG+表示TTI 程序，TFG+可以表達TTI 程序的控制流信息、用戶規定的時間行為以及平臺相關的時間屬性. 如表3 所示，TFG+由3 部分組成：圖結構、程序屬性、平臺相關屬性.

Table 3 TFG+ Definition表3 TFG+定義

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的偏移.

Fig.6 Description of platform dependent property coff圖6 平臺相關屬性coff 說明

如算法1 所示，給出TFG+構建算法.

算法1.TFG+構建算法.

輸入：TTI 程序prog；

輸出：時間語義節點集合ATP，ATdP，RTP，RTdP，相對基準點集合RBP，基本塊節點集合F，邊集合E.

① （N,E） ←fCFG（prog）；

② forN中的每個節點i

③ （ATP,ATdP,RTP,RTdP,RBP,F,E）←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 對應相對段時間語義節點，使用菱形表示.

Fig.7 Examples of TFG+圖7 TFG+示例

傳統程序的CFG 只能表達程序中的控制流，即指令執行的時間先后關系（temporal succession）；TFG在CFG 的基礎上擴展時間點（timing point），可以表達代碼段的時間行為；TFG+相比TFG 加入了點時間語義節點，可以表達時間和操作相結合的點時間行為. 所以TFG+的表達能力強于TFG 和CFG，可以表達更為豐富的時間語義.

5 時間行為分析和時間安全性檢查

針對文獻[4]提到的RPU 的硬件結構，使用基于執行圖的低級分析方法，計算TFG+基本塊節點和時間語義節點的平臺相關屬性，同時對時間語義節點進行時間安全性檢查.

5.1 基于RPU 的執行圖

RPU 為5 段流水處理器，對應的流水段的集合為S={IF,ID,EX,MM,WB}，分別對應取指段、譯碼段、執行段、訪存段、寫回段. TFG+中每個節點對應的指令集合為I={i1,i2, …，in}. 執行圖的節點集合為VXG，且VXG?S×I，例如，對于（IF,ij） ∈VXG，表示指令ij∈I處于流水段IF∈S. 執行圖的邊集合為EXG，且EXG?VXG×VXG，表示執行圖節點間的時序依賴. 執行圖的邊分為2 類，如圖8（b）所示，為了區分這2 類邊，在執行圖中使用實線和虛線分別表示，且δ(v,im)→(w,in)∈{0,1}表示2 種邊，對于實線邊δ(v,im)→(w,in)= 1，對于虛線邊δ(v,im)→(w,in)= 0.

Fig.8 Example of execution graph圖8 執行圖示例

現有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）完成后開始，此類邊用實線表示，且δ(v,im)→(w,in)= 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），此類邊用虛線表示，且δ(v,im)→(w,in)= 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←fvertex（prog）；

② forVXG中每個節點（v, im）

③ ifv=IF

④EXG←{（IF, im） → （IF, im+1）, （IF, im） →（ID, im）}∪EXG；

⑤ else

⑥EXG←{（v, im） → （v, im+1）, （v, im） →（fnextstage（v）, im）, （v, im） →（fprestage（v）, im+1）}∪EXG；

⑦ end if

⑧ ifim與im+1存在數據冒險

⑨EXG←{（MM, im） → （EX, im+1）}∪EXG；

⑩ end if

? ifim和im+1存在控制冒險

?EXG←{（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）的δ(v,im)→(fprestage(v),im+1)= 0，其余邊均為δ(v,im)→(w,in)= 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）.

5.2 執行圖節點屬性

對于整個執行圖來說，資源集合R={IF,ID,EX,MM,WB}表示和節點執行相關的所有資源的集合，A={ar|r∈R}表示對于當前執行圖中所有資源的釋放時間.

現在給出執行圖中的每個節點的屬性，以及每個屬性的計算過程，各屬性中提到的時間均以cpuClk周期為單位.

假設流水段v、指令im，對應執行圖中節點（v,im）.

1）λ(v,im)，表示指令im在流水段v從就緒到完成需要花費的時間.

計算過程為：如表4 所示，給出RPU 各類指令在各個流水段花費的時間. 時間指令ttiat，ttoat，delay，需要在流水線的執行段判斷系統時間是否到達預設的時間，如果沒有到達預設時間，要進行延時操作，所以在執行段存在的延遲時間 τ需要根據前驅代碼段的執行時間進行判斷. 而mtfd 指令沒有具體實現，所以不考慮mtfd 在每個流水段的執行時間. RPU 采用理想的存儲架構，即訪問指令存儲器和數據存儲器均為1 個cpuClk 周期，對于其他類型的存儲架構，可以進行額外分析，確定指令在各流水段的執行時間，再進行后續的計算. 例如，假設需要考慮指令Cache 的命中或缺失，且指令Cache 命中時的訪存時間為1 個cpuClk 周期，系統設計者可以通過指令Cache 分析，確定每條指令的Cache 命中情況，若Cache 命中，則該指令在取指段的執行時間為1 個cpuClk 周期，若Cache 缺失，則該指令在取值段的執行時間將會大于1 個cpuClk 周期，所以表4 中所示的所有指令在取指段的執行時間為1+，表示取值時間最小為1 個cpuClk 周期，而具體值需要根據分析確定，同理，訪存指令和ttiat/ttoat 指令的在訪存段的執行時間也為1+，具體的訪存和定時輸入輸出的時間需要結合實際運行情況分析確定.

Table 4 Execution Time of the Instructions in Each Pipeline Stage of RPU表4 指令在RPU 各流水段的執行時間

2）E(v,im)={∈{0,1}|r∈R}，表示處在流水段v的指令im開始執行是否會受到R中某個資源的影響.

計算過程為：如果節點（v,im）本身執行依賴于資源r∈R，那么=1. 另外，如果節點（v,im）任意前驅節點（x,ij），即（x,ij） → （v,im）∈EXG，存在=1，則=1.

3）D(v,im)={|r∈R}，表示資源釋放到指令在流水段就緒執行之間的延遲時間，即R中某個資源釋放與處在流水段v的指令im開始執行的時間間隔.

計算過程為：對于資源r∈R，考慮（v,im）的所有前驅節點（x,ij），即（x,ij） → （v,im）∈EXG，從資源r釋放到節點（v,im）就緒的延遲時間為

4）ρ(v,im)，表示指令im在流水段v的就緒時間，即指令im在流水段v可以開始執行的時間.

計算過程為：節點（v,im）的就緒時間為

5.3 平臺相關屬性分析和時間安全性檢查

整個分析和驗證流程如圖9 所示，首先分析TFG+中由普通指令構成的基本塊節點的平臺相關屬性；再結合TFG+中的控制流信息分析時間語義節點的平臺相關屬性；最后，根據每個時間語義節點的語義要求以及平臺相關屬性的分析結果，對每個時間語義節點進行時間安全性檢查，驗證TTI 程序運行時指令的語義能否正確表達.

Fig.9 Flow graph of temporal behavior analysis and semantic verification圖9 時間行為分析和語義驗證流程圖

下面分別介紹基本塊節點和時間語義節點的平臺相關屬性確定和時間安全性檢查的流程.

1）基本塊節點

對于基本塊節點，只需要確定基本塊的執行開銷. 首先對TFG+中每個基本塊節點構建執行圖，再根據5.2 節中執行圖節點屬性，確定基本塊的執行開銷.

定理1.基本塊節點執行開銷定理. 基本塊節點bb∈BB，基本塊最后一條指令為in，基本塊前一條指令為i-1，整個基本塊的執行開銷為

證明. 基本塊最后一條指令為in，基本塊前一條指令為i-1，當前基本塊的執行開銷為

即

假設，對于節點（WB,i-1）和（WB,in）的關鍵資源分別為α ∈R，β ∈R，即

由于RPU 為順序執行的5 段流水線，對于資源集合R={IF,ID,EX,MM,WB}，（WB,i-1）會依賴于所有的5 個資源. 由此可得

考慮基本塊前驅指令為時間語義指令的情況，即i-1為ttiat，ttoat，delay，對于時間語義指令i-1在執行段產生的延遲，以τ(EX,i-1)表示，由于指令i-1在執行段本身存在1 個時鐘周期的執行時間，故節點（EX,i-1）執行時間λ(EX,i-1)=1+τ(EX,i-1)，而執行圖（WB,i-1），（WB,in）節點的D(WB,i-1)和D(WB,in)均會受到τ(EX,i-1)的影響，所以最后執行開銷的計算不會因為延遲時間τ(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→，映射時間語義節點到該指令延遲判斷時間和前一條指令執行完成時間的差值，以及映射相對基準點到對應的getti 指令讀取ctr 的時間和前一條指令執行完成時間的差值. 設計這一函數是為了提升TTI 程序時間行為分析的緊致程度，由于RPU 底層體系結構采用流水線機制，時間語義指令與獲取系統時間指令的執行會和該指令的前驅指令重疊，所以在計算該類指令相應操作開始執行的系統時間時，需要考慮該類指令與其前驅指令由于重疊執行而產生的時間影響. 假設v∈ATP∪ATdP∪RTP∪RTdP∪RBP，v對應指令i0和指令i0的前驅指令i-1，構建指令i0和指令i-1的執行圖，由于延遲判斷、獲取ctr 均在執行段進行，所以tjitter相當于計算指令i0在執行段就緒時間與前驅指令i-1在寫回段完成時間的差值，即

根據上述基本塊節點執行開銷中式（1）的證明過程可得

⑤tWCET：V×V→ N，映射TFG+的2 個節點到這2 個節點及2 個節點間所有節點對應程序段的WCET. 假設有節點v1和v2，v1到v2所有節點的執行開銷已知.TFG+給出了節點間控制流信息，而程序循環次數等流事實可以由額外的分析或用戶指定的方式給出，最后，tWCET（v1,v2）可以通過IPET 得出.

現對TTI 程序中4 種時間語義進行時間行為分析并進行時間安全性檢查.

1）絕對點時間語義節點. 假設絕對點時間語義節點為vatdp∈ATdP.vatdp預設系統時間和最近一個前驅絕對點時間語義節點預設系統時間的差值為

如果vatdp沒有前驅的絕對點時間語義節點，那么tpre（vatdp） =start，所以

將單位轉化為cpuClk 周期為

考慮vatdp對應指令和前一條指令重疊執行，程序從tpre（vatdp） 對應指令執行完成到vatdp對應指令的延遲判斷階段（執行段）消耗的CPU 時鐘周期為

如圖10 所示，絕對點時間語義節點2 種執行時序圖中vatdp和tpre（vatdp）對應指令分別為in和in-1. 圖10（a），TTI 程序執行到絕對點時間語義節點時，系統時間小于預設時間，需要延遲的執行時序圖；圖10（b），TTI程序執行到絕對點時間語義節點時，系統時間等于預設時間，不需要延遲的執行時序圖.

平臺相關屬性計算分3 部分：

①節點延遲. 根據TFG+中的平臺相關屬性定義，tpre（vatdp）對應指令執行完成相對于系統時刻開始的偏移時間為coff（tpre（vatdp））. 如圖10（a）所示，vatdp對應指令在執行段需要的延遲時間為

②執行開銷. 計算前驅代碼段最壞執行情況下vatdp的執行開銷.vatdp對應指令i0，指令i0前一條指令i-1，構建i0和i-1的執行圖. 此時，i0在執行段的延遲時間已知，所以λ(EX,i0)也已知，和基本塊節點的執行開銷計算過程一致，由式（1）可知：

③相對于系統時刻開始的偏移. 點時間語義節點對應指令的操作時間為to，RPU 中ttiat（ttoat）輸入（輸出）操作的時間為訪存段1 個cpuClk 周期的訪存開銷，加上寫回段1 個cpuClk 周期的寫回開銷，所以to共2 個cpuClk 周期. 另外指令在執行段除了額外的延遲時間，還存在1 個cpuClk 周期的執行時間. 如圖10 所示，點時間語義節點完成執行相對于系統時刻的偏移為

時間安全性檢查為：絕對點時間語義節點vatdp，要求輸入輸出開始和完成在tATdP（vatdp）和tATdP（vatdp） +1 之間. 由于采用延遲機制，輸入輸出操作的開始時間一定大于等于tATdP（vatdp），現在只需要操作的完成時間小于tATdP（vatdp） + 1 即可，所以對于TFG+中的絕對點時間語義節點需要滿足要求：

2）絕對段時間語義節點. 假設絕對段時間語義節點vatp∈ATP. 和絕對點時間語義節點相同，首先計算vatp預設系統時間和最近一個前驅絕對點時間語義節點預設系統時間的差值，并轉化為CPU 時鐘周期，即

如果vatp對應指令mtfd，那么平臺相關屬性均為0，只需要驗證mtfd 語義. 而通過延遲實現的指令delay，語義一定能得到滿足，所以只需要計算平臺相關屬性.

下面討論delay 平臺相關屬性計算. 如圖11 所示，delay 節點2 種執行時序圖，其中vatdp和tpre（vatdp）對應指令分別為in和in-1，圖11（a）為delay 節點需要延遲的執行時序圖，圖11（b）為不需要延遲的執行時序圖. 程序從tpre（vatp）執行完成到vatp的延遲判斷階段（執行段）消耗的cpuClk 周期為

Fig.11 Timing diagram of absolute timing semantic圖11 絕對段時間語義時序圖

平臺相關屬性計算分為3 部分：

①節點延遲. 和絕對點時間語義節點的分析過程相同，vatp對應指令在執行段需要的延遲時間為

② 執行開銷. 計算前驅代碼段最壞執行情況下vatp的執行開銷.vatp對應指令i0，指令i0前一條指令i-1，構建i0和i-1的執行圖，由式（1）可知：

下面討論mtfd 指令時間安全性檢查.vatp對應mtfd 指令要求指令前代碼段的完成時間小于等于tATP（vatp），所以需要滿足要求：

3）相對點時間語義節點. 此處的相對語義，均指運行時確定的相對點時間語義. 運行時確定的相對點時間語義通過getti 和ttiat（ttoat）指令組合的形式表達，如圖12（a）所示，運行時確定的相對點時間語義的時序圖，getti 指令獲取系統時間處在1 個系統時刻內，在系統時刻的具體位置需要根據執行情況確定. 為保證系統運行時時間語義指令的正確性，如圖12（b）所示，在時間安全性檢查時，假設getti 指令在系統時刻最后讀取系統時間. 而對于相對點時間語義指令的延遲時間等平臺相關屬性，則根據前驅代碼段最壞執行情況進行分析.

Fig.12 Timing diagram of relative timed semantic圖12 相對點時間語義時序圖

假設相對點時間語義節點為vrtdp∈RTdP，對應的相對基準點為vrbp∈RBP.vrbp對應的getti 指令會在EX段讀取系統時間，所以從getti 讀取系統時間（EX段）到vrtdp的延遲判階段（執行段）消耗的cpuClk 周期，還需要加上getti 指令執行段、訪存段、寫回段的執行時間，對于RPU 來說為3 個CPU 時鐘周期，結果為

平臺相關屬性計算分2 部分：①節點延遲. 如圖13 所示，vrbp對應的getti 指令在執行段的時間相對于系統時刻開始的偏移為offset，該偏移時間受到vatp前一個絕對點時間語義節點或程序開始時間的影響，圖13 中假設getti 指令的前一個絕對點時間語義指令為in-1. 首先，tpre（vrtdp）對應指令執行完成到vrbp對應getti 指令的執行段的時間為

Fig.13 Timing diagram of getti instruction execution圖13 getti 指令執行時序圖

vrbp對應的getti 指令執行段相對于系統時刻開始的偏移時間為

vrtdp在執行段的延遲時間為

②執行開銷.vrtdp對應指令i0，指令i0前一條指令i-1，構建i0和i-1的執行圖. 由式（1）可知：

下面討論時間安全性檢查.vrbp對應的getti 指令獲取的系統時間，會受到前驅代碼段的執行時間的影響，只考慮前驅代碼段的最壞執行情況，不一定能保證后續相對點時間語義指令的正確性. 圖14（a）顯示前驅代碼最好執行情況下，vrbp和vrtdp間程序的允許執行時間tb；圖14（b）顯示前驅代碼最壞執行情況下，vrbp和vrtdp間程序的允許執行時間tw. 圖14 中，getti 指令最好執行情況下獲取到的系統時間為y，getti 指令最壞執行情況下獲取到的系統時間為x，存在y＜x，顯然tw＞tb.

Fig.14 Example of impact of getti instruction predecessor code fragment圖14 getti 指令前驅代碼段的影響示例

如圖14（b）所示，驗證時假設vrbp讀取系統時間，發生在系統時刻最后，vrtdp對應指令的操作時間為to，所以為保證相對點時間語義的正確性，需滿足3 個要求：

第1 個要求保證相關程序段的執行時間不超過限定時間；第2 個要求保證輸入輸出操作的時間不超過限定時間，其中加1 為vrtdp對應指令在執行段除了延遲以外的1 個cpuClk 周期；第3 個要求保證程序段執行以及輸出輸入操作的時間不超過限定時間.

4）相對段時間語義節點. 假設相對段時間語義節點為vrtp∈RTP，對應的相對基準點為vrbp∈RBP. 和相對點時間語義節點相同，從getti 讀取系統時間（執行段）到vrtp的延遲判階段（執行段）消耗的CPU 時鐘周期為

和絕對段時間語義節點相同，如果vrtp對應指令為mtfd，tjitter（vrtp）=0，且只需驗證mtfd 語義. delay 指令，只需要計算平臺相關屬性.

delay 指令平臺相關屬性計算分2 部分：

①節點延遲. 和相對點時間語義節點相同，tpre（vrtp）對應指令執行完成到vrbp對應getti 指令的執行段的時間為

vrbp對應的getti 指令執行段相對于系統時刻開始的偏移時間為

vrtp在執行段的延遲時間為

②執行開銷.vrtp對應指令i0，指令i0前一條指令i-1，構建指令i0和i-1執行圖，由式（1）可知：

下面討論mtfd 指令時間安全性檢查. 和相對點時間語義驗證相同，考慮getti 指令執行的最壞情況.假設vrbp對應getti 指令執行段讀取系統時間發生在系統時刻最后，所以為保證相對段時間語義的正確性，需滿足要求：

6 TTI 程序示例

本節給出TTI 程序示例，并對TTI 程序進行時間行為分析和時間安全性檢查，最后通過在RPU 上實際部署運行，驗證時間行為分析和時間安全性檢查的正確性. 本節主要有2 個應用示例，分別為自動駕駛示例和防抱死系統示例.

6.1 自動駕駛示例

本文采用文獻[4]中給出的自動駕駛示例. 假設一個自動駕駛系統中有3 個任務：1）采集任務，傳感器采集數據，進行數據預處理，周期為2 ms；2）分析任務，對預處理之后的數據進行分析和處理，得到響應數據，周期為1 ms；3）執行任務，將響應數據分發到執行器，周期為2 ms.

使用交錯LET 語義對任務集進行實現，圖15 顯示了該任務集的任務分解和建模時序，虛線箭頭體現了任務的數據依賴關系. 其中，每個任務被分解為3 個子任務，分別為I，C，O，其中O 和I 這2 個子任務被合并為一個OI 子任務組，保證了該任務集的交錯LET 語義.

Fig.15 Interleaved LET implementation圖15 交錯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 各硬件線程上的程序.

Fig.16 Example of autonomous driving program圖16 自動駕駛程序示例

現在給出運行自動駕駛示例的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 子任務中都需要分別表達輸入和輸出絕對點時間語義，且對應不同的系統時間. 另外給出每個任務被調度執行的系統時間.

Table 5 Example of Tasks Properties表5 任務屬性示例

現在給出自動駕駛示例中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+中程序屬性和平臺相關屬性.

Fig.17 Task t3oi program and TFG+圖17 任務t3oi 程序和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 周期：

RPU 在系統時間為6 時執行t3oi 任務，任務開始相對于系統時刻開始的偏移為0，所以coff(start)=0.計算從任務開始執行到v1的延遲判斷階段消耗的cpuClk 周期，由式（4）可得

由于t3oi 在執行ttoat 前的準備工作的WCET 為200 個cpuClk 周期，即

對于v1延遲判斷時間和前一條指令執行完成時間的差值tjitter（v1），需要構建執行圖，如圖18 所示，其中 τ表示ttoat 指令在執行段的延遲時間. 根據式（2），執行圖節點信息可得

Fig.18 Example of task t3oi execution graph圖18 任務t3oi 執行圖示例

由式（5），節點v1對應指令的延遲時間為τ=td(v1)，且

如圖17 所示，根據節點v1的延遲時間和執行圖中節點信息，由式（6），節點v1執行開銷為

由式（7），相對于系統時刻的偏移為

對于RPU 來說，輸入操作的時間to= 2，所以

最后，進行時間安全性檢查，即

節點v1對應ttoat 指令的語義可以得到保證.

對于v2的平臺相關屬性的計算和v1類似，給出v2平臺相關屬性的計算結果. 節點v2和節點v1的預設時間相同，所以節點v2的延遲時間為td(v2)=0，執行開銷為ct(v2)=1，相對于系統時刻開始的偏移為coff(v2)=4，所以v2的語義也通過驗證.

至此任務t3oi 時間行為分析和語義驗證完成，其他時間語義程序的分析和驗證過程類似. 圖19 為自動駕駛示例在RPU 上的運行時序圖. 在圖19 中，給出每個絕對點時間語義指令生效的實時間，將表5中每個時間語義指令預設時間轉化為實時間后，和圖15 進行比較可知，語義均正確表達，同時，LET 語義也得到保證.

Fig.19 Runtime time diagram of RPU threads圖19 RPU 線程運行時序圖

6.2 防抱死系統示例

防抱死系統（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. 各部分連接起來構成一個自反饋系統.

Fig.20 ABS control model圖20 ABS 控制模型

ABS 模型中除控制器外的其余部分在模擬物理環境以及作為傳感器輸入，控制器部分通過特定算法控制整個ABS，而且控制器部分的算法具有硬實時性、周期性、I/O 特性等，適合使用LET 編程模型.圖21 所示為控制器部分的具體構成，控制器部分的輸入為轉差s和車輛速度vv，輸出為剎車扭矩Tb，其中控制器部分可以根據轉差的大小調整輸出的剎車扭矩，車輛速度用來判斷是否需要防抱死控制，當車輛速度小于規定的最小速度vmin，不需要進行防抱死控制. 由于車輛轉差在0.2 時，車輪和地面產生的摩擦力最大，剎車效果最好，所以控制器部分的目的在于通過調整剎車扭矩的大小，將車輪和地面的轉差維持在0.2 左右，控制器部分會比較當前轉差和0.2的差值，并將結果通過一個bang-bang 控制器輸出為正負信號，液壓系統（hydraulic system）通過接收該信號來調整剎車扭矩，最后控制系統將剎車扭矩輸出，以實現對車輪的控制.

Fig.21 ABS controller part圖21 ABS 控制器部分

如圖22 所示，ABS 模型中控制器部分對應的TTI 程序，其中控制器部分算法采用交錯語義的LET編程模型實現，和6.1 節自動駕駛示例不同，ABS 控制器部分代碼將LET 中的OI 子任務和C 任務合并在一個TTI 程序中.

Fig.22 TTI program of controller part圖22 控制器部分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 程序后續循環的時序正確性也可以得到保證.

Fig.23 TFG+ of controller algorithm圖23 控制器算法的TFG+

經過時間行為分析和時間安全性檢查圖23 所示控制器部分TTI 程序中時間語義指令均能正確執行，圖24 顯示控制器部分TTI 程序第1 輪和第2 輪循環在RPU 上運行的時序圖. 圖24 中O 表示定時輸出指令，I1 和I2 分別表示2 條定時輸入指令，第1輪循環的時間為0～2 ms，第2 輪循環的時間為2～4 ms. 根據圖24 可知，定時輸入、定時輸出操作均在規定的系統時刻內完成，符合ABS 中控制器部分對于時序的要求.

Fig.24 Runtime time diagram of controller part圖24 控制器部分運行時序圖

7 總 結

通用計算機在指令集架構中沒有提供時間語義指令，導致上層控制模型中的時間行為無法精確自然地映射至程序代碼，控制精度大大降低，系統的實時性受到影響.

本文在已經提出的TTI 指令集基礎上，總結了TTI 指令集可以表達的4 種時間語義，以此來描述復雜系統的時間行為. 并且提出了TTI 程序的表示TFG+，同時，基于RPU 給出了分析TTI 程序時間行為和時間安全性檢查的方法.

未來，我們將進一步完善TTI 指令集相關工作，對TTI 指令集語義進行形式化說明，以及擴展TFG+對并發語義的支持.

作者貢獻聲明：高銀康提出思想、撰寫論文；陳香蘭、龔小航、蔣濱澤、李曦、周學海提供論文撰寫指導和修改意見.