LET模型的時間語義編程語言

吳 昊，章 博，陳香蘭，王 超，李 曦

中國科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230026

在實(shí)時系統(tǒng)中，如一個汽車、機(jī)器人系統(tǒng)，系統(tǒng)的正確性同時取決于邏輯和時間的正確性。系統(tǒng)行為的定時、及時發(fā)生需要在軟件中明確指定，并在實(shí)時平臺上正確執(zhí)行。然而，現(xiàn)有的編程語言缺乏顯示表達(dá)系統(tǒng)時間屬性的語法結(jié)構(gòu)，為此實(shí)時系統(tǒng)領(lǐng)域逐漸衍生出了各種實(shí)時語言來顯示表達(dá)系統(tǒng)的時間屬性。

嵌入式實(shí)時系統(tǒng)編程模型根據(jù)其發(fā)展歷程和應(yīng)用場景的需求主要可以分為三類：有界執(zhí)行時間模型（bounded execution time，BET）[1]、零執(zhí)行時間模型（zero execution time，ZET）[2]以及邏輯執(zhí)行時間模型（logical execution time，LET）[3]。目前的實(shí)時編程語言便基于這三種編程模型。

有界執(zhí)行時間模型又叫作異步模型，模型通過優(yōu)先級決定任務(wù)的執(zhí)行順序，要求任務(wù)在既定的截止時間之前完成執(zhí)行。異步模型的代表性編程語言為Ada[4]。Ada通過調(diào)用時間控制函數(shù)來指定任務(wù)的時間屬性與時間行為，其運(yùn)行時系統(tǒng)是基于線程模型實(shí)現(xiàn)的執(zhí)行環(huán)境，在執(zhí)行環(huán)境里多個并發(fā)的Ada 任務(wù)異步交錯執(zhí)行。但在異步模型中，由于運(yùn)行時系統(tǒng)缺乏對任務(wù)時序行為的約束，可搶占線程在并發(fā)情況下的執(zhí)行過程具有不確定性，導(dǎo)致系統(tǒng)實(shí)際執(zhí)行的時序語義很難與模型層保持一致性，系統(tǒng)行為具有不可預(yù)測性。

零執(zhí)行時間模型又叫作同步模型，模型基于同步假設(shè)，即在邏輯上任務(wù)的執(zhí)行時間為零。同步模型抽象層次高，具有數(shù)學(xué)抽象能力，可采用形式化工具證明其行為正確性。同步模型主要刻畫任務(wù)的因果關(guān)系，通過邏輯時間表達(dá)任務(wù)的時間行為?；谕侥Ｐ偷木幊陶Z言有Esterel[5]、PRET-C[6]、Lustre[7]以及Signal[8]等。然而，在實(shí)際的物理平臺中，無法實(shí)現(xiàn)無限快的運(yùn)算速度，系統(tǒng)實(shí)際運(yùn)行過程中不可能按照ZET的時序假設(shè)運(yùn)行。

邏輯執(zhí)行時間模型介于異步模型和同步模型之間，模型為每個任務(wù)指定了一段邏輯執(zhí)行時間，任務(wù)只能在該時間段的開始和結(jié)束時刻分別執(zhí)行輸入和輸出過程，即進(jìn)行任務(wù)間的同步，而計(jì)算過程異步進(jìn)行，且計(jì)算結(jié)果必須在輸出時刻之前有效。LET 模型約束了決定任務(wù)時序行為的關(guān)鍵過程（輸入和輸出），能直接有效地刻畫任務(wù)的時間行為。

Giotto[9]、HTL[10]、TDL[11]等現(xiàn)有的基于LET 模型的編程語言，其語言只描述了系統(tǒng)的時間約束，而具體的功能代碼則通過C、Java 等常見的高級語言來實(shí)現(xiàn)；語言通過特定編譯器編譯為中間代碼E-code[12]，在執(zhí)行時，虛擬機(jī)E-machine[12]根據(jù)E-code 描述的時間行為驅(qū)動功能代碼的執(zhí)行，虛擬機(jī)本身則是運(yùn)行在實(shí)時操作系統(tǒng)之上。這種將時間控制程序和功能代碼分開的方式并不方便設(shè)計(jì)，希望通過擴(kuò)展一種高級語言的方式來實(shí)現(xiàn)一種實(shí)時編程語言。

本文提出一種基于C 擴(kuò)展的實(shí)時編程語言TBC。TBC基于LET編程模型，在語言層次上，從設(shè)計(jì)的時間需求出發(fā)，引入可觀測事件的概念，來簡化系統(tǒng)內(nèi)部的時間約束，降低系統(tǒng)響應(yīng)延遲，并通過擴(kuò)展的語法結(jié)構(gòu)來表達(dá)系統(tǒng)中的各種時間屬性。在編譯器層次，本文提出了一種針對實(shí)時編程語言的編譯技術(shù)，通過在編譯器前端增加相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示語法結(jié)構(gòu)中的時間屬性，同時對中間語言LLVM IR進(jìn)行時間指令擴(kuò)展，使其可以表示系統(tǒng)的時間行為。在之前的工作中作者提出了包含時間語義的指令集TTI[13]，將其作為編譯器的目標(biāo)指令。

1 實(shí)時語言框架

除了編程模型外，實(shí)時語言的區(qū)別主要在于其實(shí)現(xiàn)方式和編譯方式，本文針對這兩點(diǎn)提出一種實(shí)時語言設(shè)計(jì)框架，基于此架構(gòu)來設(shè)計(jì)實(shí)時語言TBC。如圖1所示，整個語言框架分為高級語言、中間語言和匯編語言三個層次。

圖1 語言設(shè)計(jì)整體架構(gòu)Fig.1 Overall architecture of language design

高級語言指實(shí)時語言本身，在本文中通過基于C擴(kuò)展語法結(jié)構(gòu)的方式來實(shí)現(xiàn)語言時間語義的擴(kuò)展。在這里語法結(jié)構(gòu)是指如if、for 一樣的語言結(jié)構(gòu)，通過編譯器來進(jìn)行分析處理，相對于Ada、RTOS通過API來指定時間屬性的方式，軟件程序更加簡單，不需要大量的代碼來設(shè)置定時器，處理不同的時間格式。同時如果程序使用某個平臺依賴的API，則該程序的運(yùn)行不再靈活，時間操作必須是平臺依賴的，更重要的是，語法結(jié)構(gòu)可以通過形式化的方式表示其語法和語義，并能對語義進(jìn)行驗(yàn)證。在高級語言層次，通過擴(kuò)展的語法結(jié)構(gòu)來表達(dá)多個任務(wù)并發(fā)執(zhí)行的時間語義。

現(xiàn)有的許多編程框架[14-15]或?qū)崟r語言基于RTOS來實(shí)現(xiàn)。如文獻(xiàn)[16]將實(shí)時語言Timed-C編譯成RTOS代碼，而本文將具有時間語義的指令集作為編譯器的目標(biāo)代碼，這使得目標(biāo)平臺不需要支持功能復(fù)雜的RTOS，只需要增加相應(yīng)定時器來支持時間語義指令的實(shí)現(xiàn)。

具體的，編譯器基于LLVM[17]編譯器框架，分為前端和后端，并將LLVM IR 作為編譯器的中間語言。擴(kuò)展的語法結(jié)構(gòu)在編譯器前端經(jīng)過分析處理轉(zhuǎn)換為中間語言中的時間指令，此時語法結(jié)構(gòu)所表示的任務(wù)并發(fā)的執(zhí)行行為轉(zhuǎn)換為時間指令所表示的串行執(zhí)行行為。最后中間語言通過編譯器后端轉(zhuǎn)換成具體的匯編語言，即中間語言中的時間指令映射到匯編語言中的時間指令。

高級語言中的語法結(jié)構(gòu)和中間語言及匯編語言中的時間指令都是為了約束各個層次中系統(tǒng)的時間行為，但為了便于系統(tǒng)設(shè)計(jì)者進(jìn)行編程，語法結(jié)構(gòu)應(yīng)表示更高層次的時間約束，如任務(wù)級的任務(wù)周期、任務(wù)優(yōu)先關(guān)系等；而時間指令應(yīng)該更注重平臺實(shí)現(xiàn)，表示時間操作更具體，如延遲操作delay等。

另外，本文注重時間的本身，即各層次語言都應(yīng)該明確語言中時間的連續(xù)離散與否、時間粒度等時間屬性。本文采用文獻(xiàn)[18]中時間域的概念來描述時間。時間域指時間所基于的一個數(shù)域（如R、N等），系統(tǒng)中的時間可取范圍為數(shù)域的值域。如圖1所示，各層次的時間隨著語言的轉(zhuǎn)換也進(jìn)行相應(yīng)的轉(zhuǎn)換。

2 TBC的語言模型

2.1 時間域

本文將數(shù)域N 作為語言TBC 的時間域，即在TBC中，時間為離散的，并且時間域上的時間粒度為一段實(shí)時間，如1 ms、1 μs等，系統(tǒng)中的動作發(fā)生在基于離散時間域的某個時間點(diǎn)上，多個動作可以發(fā)生在同一個時刻。

CCSL（clock constraint specification language）[19]是嵌入式實(shí)時系統(tǒng)的標(biāo)準(zhǔn)描述語言（UML）[20]中描述時鐘約束的規(guī)范語言，可以用來表示各種連續(xù)和離散的時鐘。本文通過CCSL來形式化地定義TBC的離散時間域，在TBC默認(rèn)時間粒度為1 ms，時間域通過CCSL定義為：

其中IdealClk在CCSL中表示一個連續(xù)時鐘，其單位為“s”，通過對該時鐘離散化可以得到一個離散時鐘。TBC的離散時間域std 通過一個以1 ms為tick間隔的離散時鐘來表示。

2.2 可觀測事件

在TBC 中，引入可觀測事件的概念。將系統(tǒng)中的事件根據(jù)外界環(huán)境是否可以觀測到，分為可觀測事件和不可觀測事件兩種。可觀測事件主要指獲取外部傳感器的信號、更新執(zhí)行器的值等動作，這些事件都和外部環(huán)境有直接的關(guān)聯(lián)。不可觀測事件主要指系統(tǒng)內(nèi)部各個任務(wù)之間的數(shù)據(jù)通訊等，這些事件不被外界環(huán)境可見，其時間行為對外界環(huán)境也沒有直接的影響。

從設(shè)計(jì)需求的角度來看，構(gòu)建實(shí)時系統(tǒng)時，所需的時間約束需求便是可觀測事件的時間約束，因此，主要關(guān)注可觀測事件的時間約束。本文以三元組(E,type,P)來表示可觀測事件的時間約束。其中E表示一個可觀測事件的標(biāo)識符；type為事件的種類，分為輸入事件I和輸出事件O；P表示事件發(fā)生的周期，為一段實(shí)時間，取時間粒度的整數(shù)倍。如：(E1,I,10)表示周期為10 ms的輸入事件E1。本文以一個事件集合的形式作為系統(tǒng)設(shè)計(jì)的時間約束需求。

2.3 時間行為

在TBC中，系統(tǒng)包括多個并發(fā)的周期性任務(wù)，每個任務(wù)分為相對獨(dú)立的I、C、O三部分。任務(wù)的輸入（輸出）可能包括一個或者多個事件來與外界或其他任務(wù)進(jìn)行交互，可以根據(jù)任務(wù)的輸入（輸出）是否包含可觀測事件，即是否與外界環(huán)境進(jìn)行通訊，將包含可觀測事件的輸入（輸出）叫作外部輸入（輸出），將包含不可觀測事件的輸入（輸出）叫作內(nèi)部輸入（輸出）。

本文主要關(guān)注外部輸入（輸出）的時間約束。外部輸入（輸出）本身蘊(yùn)含了兩種時間語義：外部輸入（輸出）首先作為LET編程模型的輸入（輸出），應(yīng)在邏輯執(zhí)行時間的開始（結(jié)束）時刻執(zhí)行；同時因?yàn)橥獠枯斎耄ㄝ敵觯┌丝捎^測事件，所以應(yīng)該滿足可觀測事件的時間約束。在TBC中，任務(wù)的邏輯執(zhí)行時間等于任務(wù)周期，因此在構(gòu)建任務(wù)時，通常將可觀測事件的周期作為其所在任務(wù)的任務(wù)周期。

內(nèi)部輸入（輸出）適用于任務(wù)之間的數(shù)據(jù)通訊，從外部環(huán)境無法觀測，其時間行為并不直接影響系統(tǒng)與外界環(huán)境的通訊，因此不專門考慮內(nèi)部輸入（輸出）的時間行為。從編程模型的角度來看，TBC實(shí)際上基于一種放松的LET模型。

2.4 TBC的LET模型

在單個任務(wù)內(nèi)部，擁有可觀測事件的外部輸入（輸出）基于時間觸發(fā)，每到任務(wù)邏輯執(zhí)行時間的開始時刻（結(jié)束時刻）便會觸發(fā)任務(wù)的外部輸入（外部輸出）的執(zhí)行。如圖2 所示，周期為T的任務(wù)T1 的外部輸入輸出分別在0時刻和T時刻進(jìn)行觸發(fā)執(zhí)行。

圖2 外部輸入輸出的時間行為Fig.2 Time behavior on external inputs and outputs

任務(wù)的內(nèi)部輸入輸出用于兩個數(shù)據(jù)相關(guān)任務(wù)的數(shù)據(jù)同步，兩個任務(wù)會在邏輯執(zhí)行時間的某個時間點(diǎn)進(jìn)行同步。如圖3 所示，兩個周期都為T的任務(wù)T1 和T2，兩任務(wù)數(shù)據(jù)相關(guān)，T2 依賴于T1 的計(jì)算結(jié)果；在0時刻，T2 讀取外界傳感器傳來的數(shù)據(jù)，并在對數(shù)據(jù)進(jìn)行計(jì)算后，在t1 時刻便通過內(nèi)部輸出和任務(wù)T2 的內(nèi)部輸入對計(jì)算結(jié)果進(jìn)行同步，任務(wù)T2 在t1 時刻得到T1 的計(jì)算結(jié)果后，再經(jīng)過自己的計(jì)算過程，在T時刻通過外部輸出向外輸出計(jì)算結(jié)果；t1 為基于離散時域的某個時刻，不過本文并不關(guān)注t1 時刻的具體數(shù)值，t1 時刻只需要處于T2 的計(jì)算過程完成之后以及T3 的計(jì)算過程開始之前。

圖3 內(nèi)部輸入輸出的時間行為Fig.3 Time behavior on internal inputs and outputs

TBC放松了LET編程模型的時間約束，允許任務(wù)存在內(nèi)部同步點(diǎn)，任務(wù)可在其邏輯執(zhí)行時間段內(nèi)進(jìn)行通信，消除了邏輯執(zhí)行時間模型中周期延遲問題，提升了系統(tǒng)響應(yīng)能力。如圖4所示，對于圖3中的兩個任務(wù)T1和T2，在一般的LET模型中，系統(tǒng)在0時刻獲取傳感器的數(shù)據(jù)，在2T時刻才會產(chǎn)生相應(yīng)的輸出；而在TBC中，如圖5所示，由于系統(tǒng)可以通過T1 的內(nèi)部輸出和T2 的內(nèi)部輸入在t1 時刻提前進(jìn)行同步，在T時刻便可向外產(chǎn)生同樣的輸出，提升了系統(tǒng)的響應(yīng)能力。TBC語言模型在保障系統(tǒng)與外界交互的時間行為不變的情況下，將系統(tǒng)的內(nèi)部同步提前，來降低系統(tǒng)的響應(yīng)延遲。

圖4 LET模型系統(tǒng)響應(yīng)延遲Fig.4 System response delay of LET model

圖5 TBC系統(tǒng)響應(yīng)延遲Fig.5 System response delay of TBC

當(dāng)系統(tǒng)出現(xiàn)欠采樣和過采樣的情況時，需要指定系統(tǒng)的時間行為來保障輸入與輸出關(guān)系的確定性，本文規(guī)定系統(tǒng)在短周期任務(wù)的第一個周期內(nèi)進(jìn)行同步。

如圖6所示，周期和諧的兩個任務(wù)T1 和T2，T1 周期為T2 的兩倍，在0 時刻T1 讀取傳感器數(shù)據(jù)，在T和2T時刻T2 向外界輸出結(jié)果，本文規(guī)定這種欠采樣情況下同步點(diǎn)t1 位于任務(wù)T2 的第一個周期內(nèi)，這樣保障T時刻和2T時刻的輸出結(jié)果對應(yīng)于0 時刻的輸入，輸入和輸出之間可以相互確定。

圖6 系統(tǒng)欠采樣的時間行為Fig.6 Time behavior of system under-sampling

同理，對于系統(tǒng)發(fā)生過采樣的情況，如圖7所示，周期和諧的兩個任務(wù)T1 和T2，T2 周期為T1 的兩倍，在0時刻和T時刻T1 讀取傳感器數(shù)據(jù)，在2T時刻T2 向外界輸出結(jié)果，本文規(guī)定兩任務(wù)的同步點(diǎn)t1 位于任務(wù)T1 的第一個周期內(nèi)，保障2T時刻的輸出結(jié)果對應(yīng)于0時刻的輸入，輸入和輸出之間關(guān)系可以確定。

圖7 系統(tǒng)過采樣的時間行為Fig.7 Time behavior of system over-sampling

任務(wù)中的輸入輸出過程，在邏輯層次被認(rèn)為是在觸發(fā)時刻瞬時執(zhí)行，在具體的物理執(zhí)行平臺上，輸入輸出過程勢必要花費(fèi)一段時間來執(zhí)行（即使時間很短），執(zhí)行過程處于一個時間執(zhí)行區(qū)間上。如圖8所示，對于外部輸入過程，邏輯層次在0時刻執(zhí)行，到物理層次上，其執(zhí)行在一個時間區(qū)間[0,t1]上，其中t1 為輸入的執(zhí)行時間長度；同理，對于外部輸出過程，邏輯層次在T時刻執(zhí)行，到物理層次上，其執(zhí)行在一個時間區(qū)間[t2,T]上。

圖8 時間映射Fig.8 Time mapping

對于內(nèi)部輸入輸出過程，在邏輯層次上，由于其并非在某確定時間點(diǎn)定時觸發(fā)，只需要滿足進(jìn)行同步的兩個輸入輸出，輸出過程在輸入過程之前執(zhí)行。

3 語法結(jié)構(gòu)

3.1 組件

本文用組件來統(tǒng)一表示任務(wù)中的I、C、O 過程。組件一共有五種：內(nèi)部輸入組件、外部輸入組件、計(jì)算組件、外部輸出組件、內(nèi)部輸出組件。每個組件會被分配一個執(zhí)行區(qū)間（slot），組件在執(zhí)行區(qū)間執(zhí)行時不可搶占，組件若提前執(zhí)行完成，可主動放棄處理器資源；對于任務(wù)的輸入輸出組件來說，執(zhí)行區(qū)間即為從邏輯層次映射到物理層次的時間區(qū)間。組件的執(zhí)行區(qū)間通常設(shè)置為大于或等于其最壞情況執(zhí)行時間（worst-case execution time，WCET）的值，避免組件執(zhí)行出現(xiàn)超時的情況。為了便于分析計(jì)算，執(zhí)行區(qū)間的長度以離散時域的時間粒度（ms）為單位，取整數(shù)值。

3.2 擴(kuò)展的語法結(jié)構(gòu)

如表1所示，TBC擴(kuò)展了7種時間語法結(jié)構(gòu)，來表示系統(tǒng)中的任務(wù)、各種組件及其時間屬性。

表1 擴(kuò)展的語法結(jié)構(gòu)Table 1 Extended syntax structure

Task語法結(jié)構(gòu)用于定義一個并發(fā)的LET任務(wù)，語法結(jié)構(gòu)顯示聲明了任務(wù)的兩個參數(shù)：任務(wù)的唯一標(biāo)識符以及任務(wù)周期。如Task(T1,50){…}表示一個周期為50 ms的LET 任務(wù)，Task 語法結(jié)構(gòu)大括號內(nèi)的部分為任務(wù)體，任務(wù)體由三個組件構(gòu)成，即一個輸入組件（內(nèi)部輸入組件或者外部輸入組件）、一個輸出組件（內(nèi)部輸出組件或者外部輸出組件）以及一個計(jì)算組件。

E_I 語法結(jié)構(gòu)和I 語法結(jié)構(gòu)分別代表外部輸入組件和內(nèi)部輸入組件，兩個語法結(jié)構(gòu)顯示聲明了任務(wù)輸入的兩個參數(shù)：輸入組件的標(biāo)識符以及組件的執(zhí)行區(qū)間長度；E_O語法結(jié)構(gòu)和O語法結(jié)構(gòu)分別代表外部輸出組件或者內(nèi)部輸出組件，兩個語法結(jié)構(gòu)顯示聲明了輸出組件的標(biāo)識符以及組件的執(zhí)行區(qū)間長度；與PRET-C和文獻(xiàn)[21]中的語言相同，TBC 采用全局變量作為任務(wù)間通訊方式。C語法結(jié)構(gòu)代表任務(wù)的計(jì)算組件，顯示聲明了組件標(biāo)識符和計(jì)算過程的執(zhí)行區(qū)間長度。

Pre 語法結(jié)構(gòu)規(guī)定了任務(wù)之間的數(shù)據(jù)依賴關(guān)系，包括兩個參數(shù)，分別表示屬于不同任務(wù)的內(nèi)部輸出組件和內(nèi)部輸入組件，任務(wù)通過這兩個組件會進(jìn)行數(shù)據(jù)同步。如對于兩個任務(wù)T1、T2,T2 數(shù)據(jù)依賴于T1,T2 擁有一個內(nèi)部輸入P2,T1 擁有一個內(nèi)部輸出P1，則可通過Pre(P1,P2)表示兩個任務(wù)之間的數(shù)據(jù)依賴關(guān)系。

3.3 形式化語法

本文通過擴(kuò)展的巴科斯范式（extended Backus-Naur form，EBNF）來形式化描述TBC的語法規(guī)則。EBNF是巴科斯范式（Backus-Naur form，BNF）的一種擴(kuò)展，通常作為計(jì)算機(jī)編程語言和形式語言的形式化語法表示方法。TBC 的EBNF 表示如下所示，其中"c_code"表示常規(guī)的C語言代碼。

4 編譯技術(shù)

本章將介紹TBC特有的編譯技術(shù)。編譯器通過對TBC程序中的時間語法結(jié)構(gòu)進(jìn)行分析處理，最終將其轉(zhuǎn)換為特定的匯編指令。

4.1 編譯器總體架構(gòu)

如圖9 所示，TBC 編譯器基于LLVM 編譯器框架，主要包括編譯器前端、IR和編譯器后端三部分。

圖9 編譯器總體架構(gòu)Fig.9 Compiler general architecture

TBC前端分為詞法分析、語法分析、分析調(diào)度、中間代碼生成四個過程。詞法分析和語法分析分別通過Flex 和Bison 工具來實(shí)現(xiàn)。與常規(guī)的編譯器不同，TBC程序經(jīng)過詞法分析和語法分析后除了生成抽象語法樹（abstract syntax tree，AST）以外，還會生成TBC 特有的中間表示DAG（directed acyclic graph）和TAST（timed AST）。DAG和TAST分別用于表示TBC程序中的時序關(guān)系和時間值信息。兩種中間表示接下來作為分析調(diào)度器的輸入，經(jīng)過靜態(tài)分析、調(diào)度后會生成系統(tǒng)全局的靜態(tài)調(diào)度表。在中間代碼生成階段，抽象語法樹會結(jié)合靜態(tài)調(diào)度表的調(diào)度信息生成LLVM的中間語言IR。

在TBC 編譯器中，本文基于IR 擴(kuò)展了具有時間操作的指令，使得IR擁有定時觸發(fā)的語義，這里將擴(kuò)展了時間指令的LLVM IR 叫作TIR（timed LLVM IR）。在編譯器的后端，將基于RISCV的時間語義指令集TTI作為后端的目標(biāo)指令集。

如圖10 所示，TBC 程序經(jīng)過編譯器各個步驟進(jìn)行了多次轉(zhuǎn)換，最終映射到匯編指令。在高級語言層次，TBC通過擴(kuò)展的語法結(jié)構(gòu)來表示程序中的時間語義；表示時間語義的語法結(jié)構(gòu)在編譯器前端轉(zhuǎn)換為中間表示TAST和DAG，分別表示程序中的時序關(guān)系和時間值信息；經(jīng)過分析調(diào)度后，程序中的時序關(guān)系和時間值信息再轉(zhuǎn)換為調(diào)度表所表示的串行時間行為；中間語言TIR通過擴(kuò)展時間操作指令，根據(jù)調(diào)度表中的調(diào)度信息以定時觸發(fā)的方式驅(qū)動系統(tǒng)運(yùn)行；最后經(jīng)過編譯器后端的指令映射，TIR中的時間指令最終轉(zhuǎn)換為具有時間語義的匯編指令TTI。

圖10 程序轉(zhuǎn)換流程Fig.10 Program translation flow

4.2 中間表示

在編譯器前端，程序的功能部分和時間控制部分被分開處理。TBC 對于功能部分的處理和普通編譯器相同，通過詞法分析和語法分析得到AST，并對AST 進(jìn)行相應(yīng)的的語義分析。為了使得編譯器能夠更好地分析處理時間，TBC編譯器將程序中所有與時間有關(guān)的信息分為時序關(guān)系和時間值信息兩部分，并分別用兩種中間數(shù)據(jù)結(jié)構(gòu)DAG圖和TAST表示。

DAG 圖用于表示組件之間的時序關(guān)系，時序關(guān)系分為兩種。DAG 圖如圖11 所示，圖中實(shí)線表示不同任務(wù)組件之間的時序關(guān)系，即程序中Pre 語法結(jié)構(gòu)所聲明的任務(wù)之間的數(shù)據(jù)依賴關(guān)系；圖中虛線表示LET任務(wù)內(nèi)固有的時序關(guān)系，即任務(wù)的計(jì)算組件要在輸入組件和輸出組件之間執(zhí)行。

圖11 DAG圖Fig.11 DAG figure

TAST 主要有兩個作用：一是用于表示系統(tǒng)的結(jié)構(gòu)層次，二是充當(dāng)一個特殊符號表。如圖12 所示，TAST展現(xiàn)了系統(tǒng)的整體結(jié)構(gòu)，根節(jié)點(diǎn)TBC 中每個分支代表了一個并發(fā)的LET任務(wù)，而每個任務(wù)則包含多個不同類型的組件節(jié)點(diǎn)。同時作為一個符號表，樹儲存著系統(tǒng)的時間值信息：每個任務(wù)節(jié)點(diǎn)儲存任務(wù)的周期值，每個組件節(jié)點(diǎn)儲存著組件的執(zhí)行區(qū)間長度。

圖12 TAST內(nèi)部結(jié)構(gòu)Fig.12 Internal structure of TAST

4.3 分析與調(diào)度

本文采用靜態(tài)調(diào)度的方式，在編譯器前端生成靜態(tài)調(diào)度表，調(diào)度表中指定了組件執(zhí)行的順序和具體時刻。

4.3.1 必要性分析

在得到TAST 后，編譯器便可以檢查系統(tǒng)可調(diào)度的必要條件，即任務(wù)利用率和系統(tǒng)利用率都是否小于等于1。具體的，將任務(wù)各組件執(zhí)行區(qū)間長度之和除以任務(wù)周期，作為任務(wù)的利用率，所有任務(wù)的利用率都必須要小于等于1，否則終止編譯，并給出錯誤信息。將一個超周期內(nèi)，系統(tǒng)執(zhí)行所有組件用時總和除以系統(tǒng)的超周期，作為系統(tǒng)的利用率，系統(tǒng)利用率必須小于1，否則同樣終止編譯，并給出錯誤信息。用P表示任務(wù)的周期，TT表示系統(tǒng)的超周期，其中TT為所有任務(wù)的最小公倍數(shù)，Ti(Mj)表示任務(wù)i的第j個組件，slot表示組件的執(zhí)行區(qū)間長度。必要性分析形式化表示如下，其中N表示系統(tǒng)任務(wù)數(shù)量，Ni表示第i個任務(wù)組件的數(shù)量。

4.3.2 調(diào)度表

在初步檢查滿足系統(tǒng)可調(diào)度的必要條件后，通過DAG 圖和TAST 中的信息進(jìn)行靜態(tài)調(diào)度。本文通過對多個周期任務(wù)進(jìn)行循環(huán)展開，來集成一個周期為超周期的大循環(huán)塊，靜態(tài)調(diào)度表中的每一個表項(xiàng)用于表示組件一次執(zhí)行的具體時間行為，可以通過三元組(M,t1,t2)來形式化表示，其中M表示組件的標(biāo)識符，t1 表示組件在循環(huán)塊中的開始執(zhí)行時間，t2 表示組件的執(zhí)行區(qū)間長度。

4.3.3 調(diào)度規(guī)則

對于系統(tǒng)復(fù)雜的情況，靜態(tài)調(diào)度有可能是個NP-hard問題，常通過啟發(fā)式算法等來解決。本文不涉及具體的調(diào)度算法，而是規(guī)定調(diào)度中所要遵循的調(diào)度規(guī)則，調(diào)度規(guī)則主要指靜態(tài)調(diào)度需要遵循的優(yōu)先關(guān)系，主要包括以下兩部分：

（1）靜態(tài)調(diào)度需要滿足DAG圖中指定的時序關(guān)系：同一任務(wù)的計(jì)算組件要在輸入組件和輸出組件之間執(zhí)行；進(jìn)行數(shù)據(jù)同步的兩個組件，輸入組件要在輸出組件之后執(zhí)行。

（2）對于一個實(shí)際的系統(tǒng)，會出現(xiàn)多個任務(wù)的外部輸入（輸出）同時定時觸發(fā)的情況，如兩個任務(wù)的外部輸入同時在0時刻觸發(fā)執(zhí)行，需要指定多個任務(wù)同時輸入（輸出）的優(yōu)先順序：首先根據(jù)RM 調(diào)度規(guī)則，即任務(wù)的周期越短，其輸入（輸出）越優(yōu)先執(zhí)行；若兩個任務(wù)的周期相同，則按照任務(wù)的標(biāo)識符的大小，如兩個周期相同的任務(wù)T1 和T2,T1 的輸入（輸出）優(yōu)先于T2 的輸入（輸出）。

4.3.4 調(diào)度表處理

調(diào)度表中兩個相鄰表項(xiàng)之間會出現(xiàn)存在空閑時間段的情況，如兩個相鄰的表項(xiàng)(M1,t1,t2),(M2,t3,t4)，如果t1+t2

4.4 中間語言

在IR層次，本文擴(kuò)展了具有時間操作的指令，使得IR可以表示調(diào)度表中組件串行執(zhí)行的時間行為。本文中將具有時間指令的LLVM IR叫作TIR。

在TIR 中，采用時間觸發(fā)的系統(tǒng)執(zhí)行模式[22]，根據(jù)調(diào)度表中預(yù)先安排的組件時序行為，來定時驅(qū)動組件的執(zhí)行，且一次只需要處理一個組件，時間觸發(fā)的方式不但可以提高系統(tǒng)的可預(yù)測性，更便于對系統(tǒng)功能和時序的正確性進(jìn)行驗(yàn)證。

TIR和TBC基于同樣的離散時間域，以1 ms為時間粒度，TIR 的時間觸發(fā)方式通過點(diǎn)時間來展現(xiàn)：對于調(diào)度表中的一個表項(xiàng)(M1,t1,t2)，代表了系統(tǒng)會在點(diǎn)時間t1 觸發(fā)組件M的開始執(zhí)行，與TBC的并發(fā)執(zhí)行語義不同，在TIR中，組件根據(jù)調(diào)度表中的信息串行執(zhí)行，執(zhí)行時間為組件的執(zhí)行區(qū)間長度。

TIR 擴(kuò)展了絕對延時指令delay_until 指令，其語義表示從當(dāng)前時間開始延遲到某個時間點(diǎn)，如delay_until i32 10表示延遲到系統(tǒng)時間點(diǎn)10 ms。

同時TIR 擴(kuò)展了兩條時間初始化指令timeinit 和timegran。timegran 用于設(shè)置系統(tǒng)的時間粒度，時間粒度為μs的整數(shù)倍，如timegran i32 2表示設(shè)置時間粒度為2 μs。timeinit指令用于設(shè)置當(dāng)前系統(tǒng)時間。

TIR 程序的整體結(jié)構(gòu)為一個大的循環(huán)，TIR 程序結(jié)構(gòu)如圖13所示，程序最開始時設(shè)置系統(tǒng)時間粒度為1 ms（與TBC 保持一致），每個循環(huán)開始時重置系統(tǒng)時間為0，每次循環(huán)系統(tǒng)按調(diào)度表中的調(diào)度信息定時執(zhí)行組件。

圖13 TIR程序結(jié)構(gòu)Fig.13 TIR program structure

對于調(diào)度表中的表項(xiàng)，將其映射到的TIR 指令如圖13所示，如果表項(xiàng)是一個組件表項(xiàng)，組件功能代碼的轉(zhuǎn)換和普通基于LLVM 架構(gòu)的編譯器相同。圖13 中，(M1,tstart1,tinterval1)是調(diào)度表中的第一個表項(xiàng)，組件M1從時刻tstart1=0 開始執(zhí)行，通過絕對延時指令delay_until保證M1 占用系統(tǒng)時間到tstart2=tstart1+tinterval1 時刻，因設(shè)置的執(zhí)行區(qū)間長度tinterval1 大于組件的WCET，不會出現(xiàn)超時的情況。

4.5 編譯器后端

TIR通過定時觸發(fā)的方式來驅(qū)動系統(tǒng)執(zhí)行，因此作為編譯器后端的目標(biāo)指令集需要支持TIR 的定時觸發(fā)語義。本文使用時間指令集TTI 作為TBC 編譯器的目標(biāo)指令集，TTI指令集是本實(shí)驗(yàn)室提出的具有時間語義的指令集，TTI 基于RISC-V 指令集進(jìn)行時間語義擴(kuò)展。RISC-V是一個典型的三操作數(shù)、加載-存儲形式的RISC 指令集架構(gòu)，其擴(kuò)展指令分為標(biāo)準(zhǔn)擴(kuò)展和非標(biāo)準(zhǔn)擴(kuò)展兩類，其中非標(biāo)準(zhǔn)擴(kuò)展作為一個高度特殊化的擴(kuò)展，由用戶根據(jù)功能需求自定義完成，TTI 指令集基于RISC-V非標(biāo)準(zhǔn)擴(kuò)展進(jìn)行定義。

在TTI 中，時間采用時間點(diǎn)的形式來表示，對于段時間，通過段時間的開始時間點(diǎn)和結(jié)束時間點(diǎn)來表示。

TTI擴(kuò)展了多個時間語義的指令，用來表示時間觸發(fā)的語義，擴(kuò)展的指令如下：

（1）時間管理指令：setti/getti 指令用于設(shè)置/獲取系統(tǒng)當(dāng)前時間點(diǎn)；settg 指令用于設(shè)置系統(tǒng)當(dāng)前時間粒度，為了和TIR的時間粒度統(tǒng)一，將TTI的時間粒度默認(rèn)設(shè)為1 ms。

（2）實(shí)時操作指令：delay指令用于將時間延遲到一個絕對時間點(diǎn)。

LLVM 的后端通?？梢苑譃橥ㄓ么a生成器和后端移植接口兩部分，而增加一個LLVM新后端主要指增加相關(guān)的后端移植接口。后端移植接口主要包括全局描述實(shí)現(xiàn)、寄存器描述實(shí)現(xiàn)、指令集描述實(shí)現(xiàn)、匯編輸出描述實(shí)現(xiàn)等。一般后端信息主要采用LLVM 架構(gòu)中的Tablegen 語言進(jìn)行后端的描述。TableGen 是LLVM 中用來專門描述目標(biāo)后端的語言，主要用于描述子目標(biāo)平臺、寄存器文件、調(diào)用慣例和指令集等目標(biāo)平臺相關(guān)信息。

TBC編譯器后端基于開源項(xiàng)目LLVM-RISCV進(jìn)行擴(kuò)展，擴(kuò)展主要包括TTI時間指令的擴(kuò)展和TIR時間指令與TTI時間指令之間的映射兩部分。本文通過Tablegen來描述指令的擴(kuò)展和指令的映射。

TIR與TTI的映射關(guān)系如表2所示，本文通過Tablegen中的DAG匿名匹配模式來實(shí)現(xiàn)指令的映射。

表2 指令映射Table 2 Instruction mapping

5 實(shí)驗(yàn)設(shè)計(jì)與分析

5.1 基于TBC構(gòu)建遙控車控制系統(tǒng)

本文通過一個遙控車控制實(shí)例來展示如何用TBC構(gòu)建實(shí)時系統(tǒng)。遙控車控制系統(tǒng)如下：遙控車每隔50 ms接受手柄的控制信號，根據(jù)控制信號，計(jì)算得到小車當(dāng)前的速度、加速度等狀態(tài)信息，以及控制小車電機(jī)轉(zhuǎn)動的PWM 波；小車每隔100 ms 將狀態(tài)信息通過zigbee 通訊模塊傳送給PC 端，使得小車的狀態(tài)信息可以被實(shí)時獲取；同時小車每隔50 ms 將PWM 波傳送給電機(jī)，電機(jī)驅(qū)動車輪轉(zhuǎn)動。以上信息可以規(guī)約為一個外部事件的集合：(E1,I,50),(E2,O,50),(E3,O,100) ；事件E1 表示接受手柄信號，E2 表示將PWM波傳送給電機(jī)，E3 表示將狀態(tài)信息傳送給PC端，該集合作為系統(tǒng)設(shè)計(jì)的時間需求。由此基于TBC模型構(gòu)建遙控車控制系統(tǒng)如表3 所示。遙控車控制系統(tǒng)包括三個并發(fā)的任務(wù)，其中任務(wù)T1 包含輸入事件E1，任務(wù)T2 和T3 的分別包含輸出事件E2 和E3。

表3 遙控車控制系統(tǒng)任務(wù)集Table 3 Task set of remote control vehicle system

遙控車控制系統(tǒng)如偽代碼1所示，其中com1到com5表示任務(wù)中的計(jì)算函數(shù)。任務(wù)T1 通過計(jì)算得到小車的狀態(tài)信息和PWM 波，通過內(nèi)部輸出P2 將這些數(shù)據(jù)傳送給其他任務(wù)，任務(wù)T2 和T3 分別通過內(nèi)部輸入P3和P5 獲得T1 的輸出數(shù)據(jù)。偽代碼1 中的第24、25 行“Pre(P2,P3)”“Pre(P2,P5)”用來表示三個任務(wù)之間的數(shù)據(jù)依賴關(guān)系。

偽代碼1遙控車控制系統(tǒng)TBC程序偽代碼

TBC程序經(jīng)過前端的分析調(diào)度后執(zhí)行序列如圖14所示。對于外部輸入輸出組件P1、P4 和P6，其執(zhí)行位于周期開始或結(jié)束的時刻，其余組件遵照調(diào)度規(guī)則中的優(yōu)先關(guān)系執(zhí)行。

圖14 組件執(zhí)行序列Fig.14 Component execution sequence

具體的調(diào)度表信息如下：(P1,0,1),(C1,1,10),(P2,11,1),(P3,12,1),(C2,13,5),(P5,18,1),(C3,19,10),(D,29,20),(P4,49,1),(P1,50,1),(C1,51,10),(P2,61,1),(P3,62,1),(C2,63,5),(D,68,30),(P4,98,1)(P6,99,1)。其中(D,29,20)和(D,68,30)表示系統(tǒng)空閑狀態(tài)，對應(yīng)圖14 中的空白部分。

程序經(jīng)過前端的分析調(diào)度以及后端的指令映射后，最后轉(zhuǎn)換為TTI 匯編代碼，匯編程序代碼如偽代碼2 所示，這里主要展示TTI程序的時間行為。

偽代碼2遙控車系統(tǒng)TTI程序偽代碼

其中第1行到第2行表示系統(tǒng)時間粒度的設(shè)置，第4行表示每次循環(huán)系統(tǒng)時間的重置，第5 行到第7 行則對應(yīng)三元組表項(xiàng)(P1,0,1)，用來控制組件P1 的時間行為。

本文使用實(shí)驗(yàn)室開發(fā)的專門支持TTI指令的RISCV仿真器來測試TBC 各方面性能，仿真器可精確模擬各TTI指令在流水線各段的行為，以此獲得系統(tǒng)運(yùn)行的具體時間行為（精確到時鐘cycle 級別），仿真器的頻率設(shè)置為1 MHz。

5.2 實(shí)驗(yàn)對比分析

除了通過TBC 來實(shí)現(xiàn)上述遙控車控制系統(tǒng)外，本文還通過傳統(tǒng)的LET模型，基于PSPM[15]編程框架來實(shí)現(xiàn)，PSPM運(yùn)行在stm32F407開發(fā)板上，開發(fā)板采用基于RAM架構(gòu)的CortexM4芯片，芯片具有168 MHz的時鐘頻率。

兩種實(shí)現(xiàn)方式的系統(tǒng)輸入輸出抖動如表4 所示。這里系統(tǒng)輸入輸出抖動是指系統(tǒng)實(shí)際I/O開始時間和系統(tǒng)設(shè)計(jì)時間的差值。基于傳統(tǒng)LET 模型的PSPM 編程框架，其底層通過FreeRTOS實(shí)時操作系統(tǒng)來實(shí)現(xiàn)，輸入輸出抖動由系統(tǒng)內(nèi)核開銷、時間調(diào)度器開銷導(dǎo)致，高達(dá)幾百個時鐘cycle；相比之下，TBC使用時間指令來保障系統(tǒng)行為的定時觸發(fā)，輸入輸出抖動由delay指令引起，其導(dǎo)致系統(tǒng)實(shí)際輸入輸出的時間比預(yù)期時間延遲一個時鐘cycle，遠(yuǎn)小于前者，具有更強(qiáng)的時間可預(yù)測性。

表4 系統(tǒng)輸入輸出抖動Table 4 System input and output jitter

表5為兩種實(shí)現(xiàn)方式的系統(tǒng)平均端到端延遲，其中端到端延遲1為從接收到遙控信號到輸出PWM波的時間，端到端延遲2為從接收到遙控信號到輸出狀態(tài)信息的時間。在傳統(tǒng)的LET模型中，任務(wù)之間只能在邏輯執(zhí)行時間的開始和結(jié)束時刻進(jìn)行交互，導(dǎo)致整個系統(tǒng)的端到端延遲時間較長；而TBC 的LET 模型與傳統(tǒng)的LET模型相比，增加了外部、內(nèi)部事件，允許任務(wù)在邏輯執(zhí)行時間內(nèi)與其他任務(wù)進(jìn)行交互，使得系統(tǒng)端到端延遲降低了大約50%。綜上，TBC采用了放松的LET模型，在提高了時間可預(yù)測性的同時，相對于傳統(tǒng)的LET模型降低了系統(tǒng)的端到端延遲。

表5 系統(tǒng)端到端延遲Table 5 System end-to-end latency

6 結(jié)束語

本文提出了一種基于LET 的時間語義編程語言TBC以及相應(yīng)的編譯技術(shù)。主要包含以下工作：

（1）提出一種實(shí)時語言設(shè)計(jì)和編譯的通用模型，基于此模型可以方便條理地設(shè)計(jì)一種實(shí)時語言。

（2）基于通用語言C，擴(kuò)展了具有時間語義的語法結(jié)構(gòu)，來實(shí)現(xiàn)實(shí)時語言TBC；同時基于LET模型，增加了可觀測事件的概念，旨在保證系統(tǒng)中與外界環(huán)境相關(guān)聯(lián)事件的時間行為，同時降低了系統(tǒng)的響應(yīng)延遲。

（3）提出了一種實(shí)時語言的編譯技術(shù)，通過在編譯器前端增加中間表示DAG 和TAST 來表示語法結(jié)構(gòu)中的時間屬性。同時通過對中間語言IR進(jìn)行時間指令擴(kuò)展，使得其可以定時觸發(fā)系統(tǒng)中的行為，并可以映射到特定的時間語義指令集。

未來的主要工作集中于TBC語言設(shè)計(jì)的完善。目前TIR中的時間和操作相對分離，并不能很好體現(xiàn)定時觸發(fā)的語義，計(jì)劃添加定時觸發(fā)指令TT，其語義為某操作在某時刻定時觸發(fā)執(zhí)行；TBC 中的任務(wù)皆為周期任務(wù)，對于系統(tǒng)中存在的非安全關(guān)鍵的非周期任務(wù)，可將其插入到空閑塊(D,t1,t2)中執(zhí)行，使其對周期任務(wù)的時間行為不產(chǎn)生影響。