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

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

吳昊，章博，陳香蘭，王超，李曦中國科學技術(shù)大學計算機科學與技術(shù)學院，合肥230026在實時系統(tǒng)中，如一個汽車、機器人系統(tǒng)，系統(tǒng)的正確性同時取決于邏輯和時間的正確性。系統(tǒng)行為的定時、及時發(fā)生需要在軟件中明確指定，并在實時平臺上正確執(zhí)行。然而，現(xiàn)有的編程語言缺乏顯示表達系統(tǒng)時間屬性的語法結(jié)構(gòu)，為此實時系統(tǒng)領(lǐng)域逐漸衍生出了各種實時語言來顯示表達系統(tǒng)的時間屬性。嵌入式實時系統(tǒng)編程模型根據(jù)其發(fā)展歷程和應(yīng)用場景的需求主要可以分為三類：有界執(zhí)行時間模型（boundedexecutiontime，BET）[1]、零執(zhí)行時間模型（zeroexecutiontime，ZET）[2]以及邏輯執(zhí)行時間模型（logicalexecutiontime，LET）[3]。目前的實時編程語言便基于這三種編程模型。有界執(zhí)行時間模型又叫作異步模型，模型通過優(yōu)先級決定任務(wù)的執(zhí)行順序，要求任務(wù)在既定的截止時間之前完成執(zhí)行。異步模型的代表性編程語言為Ada[4]。Ada通過調(diào)用時間控制函數(shù)來指定任務(wù)的時間屬性與時間行為，其運行時系統(tǒng)是基于線程模型實現(xiàn)的執(zhí)行環(huán)境，在執(zhí)行環(huán)境里多個并發(fā)的Ada任務(wù)異步交錯執(zhí)行。但在異步模型中，由于運行時系統(tǒng)缺乏對任務(wù)時序行為的約束，可搶占線程在并發(fā)情況下的執(zhí)行過程具有不確定性，導(dǎo)致系統(tǒng)實際執(zhí)行的時序語義很難與模型層保持一致性，系統(tǒng)行為具有不可預(yù)測性。零執(zhí)行時間模型又叫作同步模型，模型基于同步假設(shè)，即在邏輯上任務(wù)的執(zhí)行時間為零。同步模型抽象層次高，具有數(shù)學抽象能力，可采用形式化工具證明其行為正確性。同步模型主要刻畫任務(wù)的因果關(guān)系，通過邏輯時間表達任務(wù)的時間行為?；谕侥Ｐ偷木幊陶Z言有Esterel[5]、PRET-C[6]、Lustre[7]以及Signal[8]等。然而，在實際的物理平臺中，無法實現(xiàn)無限快的運算速度，系統(tǒng)實際運行過程中不可能按照ZET的時序假設(shè)運行。邏輯執(zhí)行時間模型介于異步模型和同步模型之間，模型為每個任務(wù)指定了一段邏輯執(zhí)行時間，任務(wù)只能在該時間段的開始和結(jié)束時刻分別執(zhí)行輸入和輸出過程，即進行任務(wù)間的同步，而計算過程異步進行，且計算結(jié)果必須在輸出時刻之前有效。LET模型約束了決定任務(wù)時序行為的關(guān)鍵過程（輸入和輸出），能直接有效地刻畫任務(wù)的時間行為。Giotto[9]、HTL[10]、TDL[11]等現(xiàn)有的基于LET模型的編程語言，其語言只描述了系統(tǒng)的時間約束，而具體的功能代碼則通過C、Java等常見的高級語言來實現(xiàn)；語言通過特定編譯器編譯為中間代碼E-code[12]，在執(zhí)行時，虛擬機E-machine[12]根據(jù)E-code描述的時間行為驅(qū)動功能代碼的執(zhí)行，虛擬機本身則是運行在實時操作系統(tǒng)之上。這種將時間控制程序和功能代碼分開的方式并不方便設(shè)計，希望通過擴展一種高級語言的方式來實現(xiàn)一種實時編程語言。本文提出一種基于C擴展的實時編程語言TBC。TBC基于LET編程模型，在語言層次上，從設(shè)計的時間需求出發(fā)，引入可觀測事件的概念，來簡化系統(tǒng)內(nèi)部的時間約束，降低系統(tǒng)響應(yīng)延遲，并通過擴展的語法結(jié)構(gòu)來表達系統(tǒng)中的各種時間屬性。在編譯器層次，本文提出了一種針對實時編程語言的編譯技術(shù)，通過在編譯器前端增加相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示語法結(jié)構(gòu)中的時間屬性，同時對中間語言LLVMIR進行時間指令擴展，使其可以表示系統(tǒng)的時間行為。在之前的工作中作者提出了包含時間語義的指令集TTI[13]，將其作為編譯器的目標指令。1實時語言框架除了編程模型外，實時語言的區(qū)別主要在于其實現(xiàn)方式和編譯方式，本文針對這兩點提出一種實時語言設(shè)計框架，基于此架構(gòu)來設(shè)計實時語言TBC。如圖1所示，整個語言框架分為高級語言、中間語言和匯編語言三個層次。圖1語言設(shè)計整體架構(gòu)Fig.1Overallarchitectureoflanguagedesign高級語言指實時語言本身，在本文中通過基于C擴展語法結(jié)構(gòu)的方式來實現(xiàn)語言時間語義的擴展。在這里語法結(jié)構(gòu)是指如if、for一樣的語言結(jié)構(gòu)，通過編譯器來進行分析處理，相對于Ada、RTOS通過API來指定時間屬性的方式，軟件程序更加簡單，不需要大量的代碼來設(shè)置定時器，處理不同的時間格式。同時如果程序使用某個平臺依賴的API，則該程序的運行不再靈活，時間操作必須是平臺依賴的，更重要的是，語法結(jié)構(gòu)可以通過形式化的方式表示其語法和語義，并能對語義進行驗證。在高級語言層次，通過擴展的語法結(jié)構(gòu)來表達多個任務(wù)并發(fā)執(zhí)行的時間語義?，F(xiàn)有的許多編程框架[14-15]或?qū)崟r語言基于RTOS來實現(xiàn)。如文獻[16]將實時語言Timed-C編譯成RTOS代碼，而本文將具有時間語義的指令集作為編譯器的目標代碼，這使得目標平臺不需要支持功能復(fù)雜的RTOS，只需要增加相應(yīng)定時器來支持時間語義指令的實現(xiàn)。具體的，編譯器基于LLVM[17]編譯器框架，分為前端和后端，并將LLVMIR作為編譯器的中間語言。擴展的語法結(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è)計者進行編程，語法結(jié)構(gòu)應(yīng)表示更高層次的時間約束，如任務(wù)級的任務(wù)周期、任務(wù)優(yōu)先關(guān)系等；而時間指令應(yīng)該更注重平臺實現(xiàn)，表示時間操作更具體，如延遲操作delay等。另外，本文注重時間的本身，即各層次語言都應(yīng)該明確語言中時間的連續(xù)離散與否、時間粒度等時間屬性。本文采用文獻[18]中時間域的概念來描述時間。時間域指時間所基于的一個數(shù)域（如R、N等），系統(tǒng)中的時間可取范圍為數(shù)域的值域。如圖1所示，各層次的時間隨著語言的轉(zhuǎn)換也進行相應(yīng)的轉(zhuǎn)換。2TBC的語言模型2.1時間域本文將數(shù)域N作為語言TBC的時間域，即在TBC中，時間為離散的，并且時間域上的時間粒度為一段實時間，如1ms、1μs等，系統(tǒng)中的動作發(fā)生在基于離散時間域的某個時間點上，多個動作可以發(fā)生在同一個時刻。CCSL（clockconstraintspecificationlanguage）[19]是嵌入式實時系統(tǒng)的標準描述語言（UML）[20]中描述時鐘約束的規(guī)范語言，可以用來表示各種連續(xù)和離散的時鐘。本文通過CCSL來形式化地定義TBC的離散時間域，在TBC默認時間粒度為1ms，時間域通過CCSL定義為：其中IdealClk在CCSL中表示一個連續(xù)時鐘，其單位為“s”，通過對該時鐘離散化可以得到一個離散時鐘。TBC的離散時間域std通過一個以1ms為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è)計需求的角度來看，構(gòu)建實時系統(tǒng)時，所需的時間約束需求便是可觀測事件的時間約束，因此，主要關(guān)注可觀測事件的時間約束。本文以三元組(E,type,P)來表示可觀測事件的時間約束。其中E表示一個可觀測事件的標識符；type為事件的種類，分為輸入事件I和輸出事件O；P表示事件發(fā)生的周期，為一段實時間，取時間粒度的整數(shù)倍。如：(E1,I,10)表示周期為10ms的輸入事件E1。本文以一個事件集合的形式作為系統(tǒng)設(shè)計的時間約束需求。2.3時間行為在TBC中，系統(tǒng)包括多個并發(fā)的周期性任務(wù)，每個任務(wù)分為相對獨立的I、C、O三部分。任務(wù)的輸入（輸出）可能包括一個或者多個事件來與外界或其他任務(wù)進行交互，可以根據(jù)任務(wù)的輸入（輸出）是否包含可觀測事件，即是否與外界環(huán)境進行通訊，將包含可觀測事件的輸入（輸出）叫作外部輸入（輸出），將包含不可觀測事件的輸入（輸出）叫作內(nèi)部輸入（輸出）。本文主要關(guān)注外部輸入（輸出）的時間約束。外部輸入（輸出）本身蘊含了兩種時間語義：外部輸入（輸出）首先作為LET編程模型的輸入（輸出），應(yīng)在邏輯執(zhí)行時間的開始（結(jié)束）時刻執(zhí)行；同時因為外部輸入（輸出）包含了可觀測事件，所以應(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實際上基于一種放松的LET模型。2.4TBC的LET模型在單個任務(wù)內(nèi)部，擁有可觀測事件的外部輸入（輸出）基于時間觸發(fā)，每到任務(wù)邏輯執(zhí)行時間的開始時刻（結(jié)束時刻）便會觸發(fā)任務(wù)的外部輸入（外部輸出）的執(zhí)行。如圖2所示，周期為T的任務(wù)T1的外部輸入輸出分別在0時刻和T時刻進行觸發(fā)執(zhí)行。圖2外部輸入輸出的時間行為Fig.2Timebehavioronexternalinputsandoutputs任務(wù)的內(nèi)部輸入輸出用于兩個數(shù)據(jù)相關(guān)任務(wù)的數(shù)據(jù)同步，兩個任務(wù)會在邏輯執(zhí)行時間的某個時間點進行同步。如圖3所示，兩個周期都為T的任務(wù)T1和T2，兩任務(wù)數(shù)據(jù)相關(guān)，T2依賴于T1的計算結(jié)果；在0時刻，T2讀取外界傳感器傳來的數(shù)據(jù)，并在對數(shù)據(jù)進行計算后，在t1時刻便通過內(nèi)部輸出和任務(wù)T2的內(nèi)部輸入對計算結(jié)果進行同步，任務(wù)T2在t1時刻得到T1的計算結(jié)果后，再經(jīng)過自己的計算過程，在T時刻通過外部輸出向外輸出計算結(jié)果；t1為基于離散時域的某個時刻，不過本文并不關(guān)注t1時刻的具體數(shù)值，t1時刻只需要處于T2的計算過程完成之后以及T3的計算過程開始之前。圖3內(nèi)部輸入輸出的時間行為Fig.3TimebehavioroninternalinputsandoutputsTBC放松了LET編程模型的時間約束，允許任務(wù)存在內(nèi)部同步點，任務(wù)可在其邏輯執(zhí)行時間段內(nèi)進行通信，消除了邏輯執(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時刻提前進行同步，在T時刻便可向外產(chǎn)生同樣的輸出，提升了系統(tǒng)的響應(yīng)能力。TBC語言模型在保障系統(tǒng)與外界交互的時間行為不變的情況下，將系統(tǒng)的內(nèi)部同步提前，來降低系統(tǒng)的響應(yīng)延遲。圖4LET模型系統(tǒng)響應(yīng)延遲Fig.4SystemresponsedelayofLETmodel圖5TBC系統(tǒng)響應(yīng)延遲Fig.5SystemresponsedelayofTBC當系統(tǒng)出現(xiàn)欠采樣和過采樣的情況時，需要指定系統(tǒng)的時間行為來保障輸入與輸出關(guān)系的確定性，本文規(guī)定系統(tǒng)在短周期任務(wù)的第一個周期內(nèi)進行同步。如圖6所示，周期和諧的兩個任務(wù)T1和T2，T1周期為T2的兩倍，在0時刻T1讀取傳感器數(shù)據(jù)，在T和2T時刻T2向外界輸出結(jié)果，本文規(guī)定這種欠采樣情況下同步點t1位于任務(wù)T2的第一個周期內(nèi)，這樣保障T時刻和2T時刻的輸出結(jié)果對應(yīng)于0時刻的輸入，輸入和輸出之間可以相互確定。圖6系統(tǒng)欠采樣的時間行為Fig.6Timebehaviorofsystemunder-sampling同理，對于系統(tǒng)發(fā)生過采樣的情況，如圖7所示，周期和諧的兩個任務(wù)T1和T2，T2周期為T1的兩倍，在0時刻和T時刻T1讀取傳感器數(shù)據(jù)，在2T時刻T2向外界輸出結(jié)果，本文規(guī)定兩任務(wù)的同步點t1位于任務(wù)T1的第一個周期內(nèi)，保障2T時刻的輸出結(jié)果對應(yīng)于0時刻的輸入，輸入和輸出之間關(guān)系可以確定。圖7系統(tǒng)過采樣的時間行為Fig.7Timebehaviorofsystemover-sampling任務(wù)中的輸入輸出過程，在邏輯層次被認為是在觸發(fā)時刻瞬時執(zhí)行，在具體的物理執(zhí)行平臺上，輸入輸出過程勢必要花費一段時間來執(zhí)行（即使時間很短），執(zhí)行過程處于一個時間執(zhí)行區(qū)間上。如圖8所示，對于外部輸入過程，邏輯層次在0時刻執(zhí)行，到物理層次上，其執(zhí)行在一個時間區(qū)間[0,t1]上，其中t1為輸入的執(zhí)行時間長度；同理，對于外部輸出過程，邏輯層次在T時刻執(zhí)行，到物理層次上，其執(zhí)行在一個時間區(qū)間[t2,T]上。圖8時間映射Fig.8Timemapping對于內(nèi)部輸入輸出過程，在邏輯層次上，由于其并非在某確定時間點定時觸發(fā)，只需要滿足進行同步的兩個輸入輸出，輸出過程在輸入過程之前執(zhí)行。3語法結(jié)構(gòu)3.1組件本文用組件來統(tǒng)一表示任務(wù)中的I、C、O過程。組件一共有五種：內(nèi)部輸入組件、外部輸入組件、計算組件、外部輸出組件、內(nèi)部輸出組件。每個組件會被分配一個執(zhí)行區(qū)間（slot），組件在執(zhí)行區(qū)間執(zhí)行時不可搶占，組件若提前執(zhí)行完成，可主動放棄處理器資源；對于任務(wù)的輸入輸出組件來說，執(zhí)行區(qū)間即為從邏輯層次映射到物理層次的時間區(qū)間。組件的執(zhí)行區(qū)間通常設(shè)置為大于或等于其最壞情況執(zhí)行時間（worst-caseexecutiontime，WCET）的值，避免組件執(zhí)行出現(xiàn)超時的情況。為了便于分析計算，執(zhí)行區(qū)間的長度以離散時域的時間粒度（ms）為單位，取整數(shù)值。3.2擴展的語法結(jié)構(gòu)如表1所示，TBC擴展了7種時間語法結(jié)構(gòu)，來表示系統(tǒng)中的任務(wù)、各種組件及其時間屬性。表1擴展的語法結(jié)構(gòu)Table1ExtendedsyntaxstructureTask語法結(jié)構(gòu)用于定義一個并發(fā)的LET任務(wù)，語法結(jié)構(gòu)顯示聲明了任務(wù)的兩個參數(shù)：任務(wù)的唯一標識符以及任務(wù)周期。如Task(T1,50){…}表示一個周期為50ms的LET任務(wù)，Task語法結(jié)構(gòu)大括號內(nèi)的部分為任務(wù)體，任務(wù)體由三個組件構(gòu)成，即一個輸入組件（內(nèi)部輸入組件或者外部輸入組件）、一個輸出組件（內(nèi)部輸出組件或者外部輸出組件）以及一個計算組件。E_I語法結(jié)構(gòu)和I語法結(jié)構(gòu)分別代表外部輸入組件和內(nèi)部輸入組件，兩個語法結(jié)構(gòu)顯示聲明了任務(wù)輸入的兩個參數(shù)：輸入組件的標識符以及組件的執(zhí)行區(qū)間長度；E_O語法結(jié)構(gòu)和O語法結(jié)構(gòu)分別代表外部輸出組件或者內(nèi)部輸出組件，兩個語法結(jié)構(gòu)顯示聲明了輸出組件的標識符以及組件的執(zhí)行區(qū)間長度；與PRET-C和文獻[21]中的語言相同，TBC采用全局變量作為任務(wù)間通訊方式。C語法結(jié)構(gòu)代表任務(wù)的計算組件，顯示聲明了組件標識符和計算過程的執(zhí)行區(qū)間長度。Pre語法結(jié)構(gòu)規(guī)定了任務(wù)之間的數(shù)據(jù)依賴關(guān)系，包括兩個參數(shù)，分別表示屬于不同任務(wù)的內(nèi)部輸出組件和內(nèi)部輸入組件，任務(wù)通過這兩個組件會進行數(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形式化語法本文通過擴展的巴科斯范式（extendedBackus-Naurform，EBNF）來形式化描述TBC的語法規(guī)則。EBNF是巴科斯范式（Backus-Naurform，BNF）的一種擴展，通常作為計算機編程語言和形式語言的形式化語法表示方法。TBC的EBNF表示如下所示，其中"c_code"表示常規(guī)的C語言代碼。4編譯技術(shù)本章將介紹TBC特有的編譯技術(shù)。編譯器通過對TBC程序中的時間語法結(jié)構(gòu)進行分析處理，最終將其轉(zhuǎn)換為特定的匯編指令。4.1編譯器總體架構(gòu)如圖9所示，TBC編譯器基于LLVM編譯器框架，主要包括編譯器前端、IR和編譯器后端三部分。圖9編譯器總體架構(gòu)Fig.9CompilergeneralarchitectureTBC前端分為詞法分析、語法分析、分析調(diào)度、中間代碼生成四個過程。詞法分析和語法分析分別通過Flex和Bison工具來實現(xiàn)。與常規(guī)的編譯器不同，TBC程序經(jīng)過詞法分析和語法分析后除了生成抽象語法樹（abstractsyntaxtree，AST）以外，還會生成TBC特有的中間表示DAG（directedacyclicgraph）和TAST（timedAST）。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擴展了具有時間操作的指令，使得IR擁有定時觸發(fā)的語義，這里將擴展了時間指令的LLVMIR叫作TIR（timedLLVMIR）。在編譯器的后端，將基于RISCV的時間語義指令集TTI作為后端的目標指令集。如圖10所示，TBC程序經(jīng)過編譯器各個步驟進行了多次轉(zhuǎn)換，最終映射到匯編指令。在高級語言層次，TBC通過擴展的語法結(jié)構(gòu)來表示程序中的時間語義；表示時間語義的語法結(jié)構(gòu)在編譯器前端轉(zhuǎn)換為中間表示TAST和DAG，分別表示程序中的時序關(guān)系和時間值信息；經(jīng)過分析調(diào)度后，程序中的時序關(guān)系和時間值信息再轉(zhuǎn)換為調(diào)度表所表示的串行時間行為；中間語言TIR通過擴展時間操作指令，根據(jù)調(diào)度表中的調(diào)度信息以定時觸發(fā)的方式驅(qū)動系統(tǒng)運行；最后經(jīng)過編譯器后端的指令映射，TIR中的時間指令最終轉(zhuǎn)換為具有時間語義的匯編指令TTI。圖10程序轉(zhuǎn)換流程Fig.10Programtranslationflow4.2中間表示在編譯器前端，程序的功能部分和時間控制部分被分開處理。TBC對于功能部分的處理和普通編譯器相同，通過詞法分析和語法分析得到AST，并對AST進行相應(yīng)的的語義分析。為了使得編譯器能夠更好地分析處理時間，TBC編譯器將程序中所有與時間有關(guān)的信息分為時序關(guān)系和時間值信息兩部分，并分別用兩種中間數(shù)據(jù)結(jié)構(gòu)DAG圖和TAST表示。DAG圖用于表示組件之間的時序關(guān)系，時序關(guān)系分為兩種。DAG圖如圖11所示，圖中實線表示不同任務(wù)組件之間的時序關(guān)系，即程序中Pre語法結(jié)構(gòu)所聲明的任務(wù)之間的數(shù)據(jù)依賴關(guān)系；圖中虛線表示LET任務(wù)內(nèi)固有的時序關(guān)系，即任務(wù)的計算組件要在輸入組件和輸出組件之間執(zhí)行。圖11DAG圖Fig.11DAGfigureTAST主要有兩個作用：一是用于表示系統(tǒng)的結(jié)構(gòu)層次，二是充當一個特殊符號表。如圖12所示，TAST展現(xiàn)了系統(tǒng)的整體結(jié)構(gòu)，根節(jié)點TBC中每個分支代表了一個并發(fā)的LET任務(wù)，而每個任務(wù)則包含多個不同類型的組件節(jié)點。同時作為一個符號表，樹儲存著系統(tǒng)的時間值信息：每個任務(wù)節(jié)點儲存任務(wù)的周期值，每個組件節(jié)點儲存著組件的執(zhí)行區(qū)間長度。圖12TAST內(nèi)部結(jié)構(gòu)Fig.12InternalstructureofTAST4.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中的信息進行靜態(tài)調(diào)度。本文通過對多個周期任務(wù)進行循環(huán)展開，來集成一個周期為超周期的大循環(huán)塊，靜態(tài)調(diào)度表中的每一個表項用于表示組件一次執(zhí)行的具體時間行為，可以通過三元組(M,t1,t2)來形式化表示，其中M表示組件的標識符，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ù)的計算組件要在輸入組件和輸出組件之間執(zhí)行；進行數(shù)據(jù)同步的兩個組件，輸入組件要在輸出組件之后執(zhí)行。（2）對于一個實際的系統(tǒng)，會出現(xiàn)多個任務(wù)的外部輸入（輸出）同時定時觸發(fā)的情況，如兩個任務(wù)的外部輸入同時在0時刻觸發(fā)執(zhí)行，需要指定多個任務(wù)同時輸入（輸出）的優(yōu)先順序：首先根據(jù)RM調(diào)度規(guī)則，即任務(wù)的周期越短，其輸入（輸出）越優(yōu)先執(zhí)行；若兩個任務(wù)的周期相同，則按照任務(wù)的標識符的大小，如兩個周期相同的任務(wù)T1和T2,T1的輸入（輸出）優(yōu)先于T2的輸入（輸出）。4.3.4調(diào)度表處理調(diào)度表中兩個相鄰表項之間會出現(xiàn)存在空閑時間段的情況，如兩個相鄰的表項(M1,t1,t2),(M2,t3,t4)，如果t1+t2<t3，則說明系統(tǒng)在執(zhí)行兩個組件之間存在一段空閑時間，需要在隊列中加入特定的空閑塊(d,t2,t3-t2)來表示系統(tǒng)處于空閑狀態(tài)，其中d為空閑塊的標識符。調(diào)度表經(jīng)過處理后表項分為組件表項(m,t1,t2)和空閑表項(d,t1,t2)兩種，同時兩個相鄰的表項之間不存在時間間隔。<p>4.4中間語言在IR層次，本文擴展了具有時間操作的指令，使得IR可以表示調(diào)度表中組件串行執(zhí)行的時間行為。本文中將具有時間指令的LLVMIR叫作TIR。在TIR中，采用時間觸發(fā)的系統(tǒng)執(zhí)行模式[22]，根據(jù)調(diào)度表中預(yù)先安排的組件時序行為，來定時驅(qū)動組件的執(zhí)行，且一次只需要處理一個組件，時間觸發(fā)的方式不但可以提高系統(tǒng)的可預(yù)測性，更便于對系統(tǒng)功能和時序的正確性進行驗證。TIR和TBC基于同樣的離散時間域，以1ms為時間粒度，TIR的時間觸發(fā)方式通過點時間來展現(xiàn)：對于調(diào)度表中的一個表項(M1,t1,t2)，代表了系統(tǒng)會在點時間t1觸發(fā)組件M的開始執(zhí)行，與TBC的并發(fā)執(zhí)行語義不同，在TIR中，組件根據(jù)調(diào)度表中的信息串行執(zhí)行，執(zhí)行時間為組件的執(zhí)行區(qū)間長度。TIR擴展了絕對延時指令delay_until指令，其語義表示從當前時間開始延遲到某個時間點，如delay_untili3210表示延遲到系統(tǒng)時間點10ms。同時TIR擴展了兩條時間初始化指令timeinit和timegran。timegran用于設(shè)置系統(tǒng)的時間粒度，時間粒度為μs的整數(shù)倍，如timegrani322表示設(shè)置時間粒度為2μs。timeinit指令用于設(shè)置當前系統(tǒng)時間。TIR程序的整體結(jié)構(gòu)為一個大的循環(huán)，TIR程序結(jié)構(gòu)如圖13所示，程序最開始時設(shè)置系統(tǒng)時間粒度為1ms（與TBC保持一致），每個循環(huán)開始時重置系統(tǒng)時間為0，每次循環(huán)系統(tǒng)按調(diào)度表中的調(diào)度信息定時執(zhí)行組件。圖13TIR程序結(jié)構(gòu)Fig.13TIRprogramstructure對于調(diào)度表中的表項，將其映射到的TIR指令如圖13所示，如果表項是一個組件表項，組件功能代碼的轉(zhuǎn)換和普通基于LLVM架構(gòu)的編譯器相同。圖13中，(M1,tstart1,tinterval1)是調(diào)度表中的第一個表項，組件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í)行，因此作為編譯器后端的目標指令集需要支持TIR的定時觸發(fā)語義。本文使用時間指令集TTI作為TBC編譯器的目標指令集，TTI指令集是本實驗室提出的具有時間語義的指令集，TTI基于RISC-V指令集進行時間語義擴展。RISC-V是一個典型的三操作數(shù)、加載-存儲形式的RISC指令集架構(gòu)，其擴展指令分為標準擴展和非標準擴展兩類，其中非標準擴展作為一個高度特殊化的擴展，由用戶根據(jù)功能需求自定義完成，TTI指令集基于RISC-V非標準擴展進行定義。在TTI中，時間采用時間點的形式來表示，對于段時間，通過段時間的開始時間點和結(jié)束時間點來表示。TTI擴展了多個時間語義的指令，用來表示時間觸發(fā)的語義，擴展的指令如下：（1）時間管理指令：setti/getti指令用于設(shè)置/獲取系統(tǒng)當前時間點；settg指令用于設(shè)置系統(tǒng)當前時間粒度，為了和TIR的時間粒度統(tǒng)一，將TTI的時間粒度默認設(shè)為1ms。（2）實時操作指令：delay指令用于將時間延遲到一個絕對時間點。LLVM的后端通常可以分為通用代碼生成器和后端移植接口兩部分，而增加一個LLVM新后端主要指增加相關(guān)的后端移植接口。后端移植接口主要包括全局描述實現(xiàn)、寄存器描述實現(xiàn)、指令集描述實現(xiàn)、匯編輸出描述實現(xiàn)等。一般后端信息主要采用LLVM架構(gòu)中的Tablegen語言進行后端的描述。TableGen是LLVM中用來專門描述目標后端的語言，主要用于描述子目標平臺、寄存器文件、調(diào)用慣例和指令集等目標平臺相關(guān)信息。TBC編譯器后端基于開源項目LLVM-RISCV進行擴展，擴展主要包括TTI時間指令的擴展和TIR時間指令與TTI時間指令之間的映射兩部分。本文通過Tablegen來描述指令的擴展和指令的映射。TIR與TTI的映射關(guān)系如表2所示，本文通過Tablegen中的DAG匿名匹配模式來實現(xiàn)指令的映射。表2指令映射Table2Instructionmapping5實驗設(shè)計與分析5.1基于TBC構(gòu)建遙控車控制系統(tǒng)本文通過一個遙控車控制實例來展示如何用TBC構(gòu)建實時系統(tǒng)。遙控車控制系統(tǒng)如下：遙控車每隔50ms接受手柄的控制信號，根據(jù)控制信號，計算得到小車當前的速度、加速度等狀態(tài)信息，以及控制小車電機轉(zhuǎn)動的PWM波；小車每隔100ms將狀態(tài)信息通過zigbee通訊模塊傳送給PC端，使得小車的狀態(tài)信息可以被實時獲?。煌瑫r小車每隔50ms將PWM波傳送給電機，電機驅(qū)動車輪轉(zhuǎn)動。以上信息可以規(guī)約為一個外部事件的集合：(E1,I,50),(E2,O,50),(E3,O,100)；事件E1表示接受手柄信號，E2表示將PWM波傳送給電機，E3表示將狀態(tài)信息傳送給PC端，該集合作為系統(tǒng)設(shè)計的時間需求。由此基于TBC模型構(gòu)建遙控車控制系統(tǒng)如表3所示。遙控車控制系統(tǒng)包括三個并發(fā)的任務(wù)，其中任務(wù)T1包含輸入事件E1，任務(wù)T2和T3的分別包含輸出事件E2和E3。表3遙控車控制系統(tǒng)任務(wù)集Table3Tasksetofremotecontrolvehiclesystem遙控車控制系統(tǒng)如偽代碼1所示，其中com1到com5表示任務(wù)中的計算函數(shù)。任務(wù)T1通過計算得到小車的狀態(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.14Componentexecutionsequence具體的調(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)時間的重