一種具有時間語義的實時處理器模型

汪 超 陳香蘭 章 博 李 曦 王 超 周學(xué)海

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

(wcwxy＠m(xù)ail.ustc.edu.cn)

實時嵌入式系統(tǒng)(real-time embedded system,RTES)是航空航天、汽車和醫(yī)用儀器等安全關(guān)鍵設(shè)備的計算與控制核心,需要實時地與被控物理環(huán)境進(jìn)行交互,其功能的正確性不僅取決于計算結(jié)果的邏輯正確性,還取決于與外界交互的時間正確性.

為了保證RTES系統(tǒng)的時間行為正確,要求其軟硬件系統(tǒng)具有時序確定性和可預(yù)測性[1].然而,現(xiàn)代計算機(jī)系統(tǒng)的體系結(jié)構(gòu)、運(yùn)行時環(huán)境、編程語言等各個抽象層次均缺乏精確的時間語義和表達(dá)時序?qū)傩缘娘@式結(jié)構(gòu),使得系統(tǒng)設(shè)計者只能采用編程抽象之外的手段(如定時中斷)進(jìn)行時序控制,導(dǎo)致控制和驗證程序的時序?qū)傩曰蛱幚頃r序沖突十分困難,并且任何軟硬件改動都將對系統(tǒng)時序造成不可預(yù)測的影響,甚至不得不重新進(jìn)行系統(tǒng)設(shè)計.尤為重要的是,由于上述機(jī)制內(nèi)在的異步不確定性,難以建立系統(tǒng)的確定性抽象模型,并據(jù)此進(jìn)行嚴(yán)謹(jǐn)?shù)男问交瘯r間行為分析,無法滿足硬實時安全性設(shè)計要求.

本文重點討論指令集體系結(jié)構(gòu)(instruction set architecture,ISA)層次缺乏時間語義的問題.現(xiàn)代處理器的數(shù)字電路能夠以納秒級細(xì)粒度執(zhí)行,但常規(guī)ISA屏蔽了這一寶貴資源,未提供具有時間語義的指令集,程序員只能依賴操作系統(tǒng)的時間服務(wù)進(jìn)行粗粒度時序控制,其可預(yù)測時序粒度比硬件高幾個數(shù)量級.常規(guī)ISA所定義的處理器行為的正確性與其時序無關(guān),時序僅僅是計算性能指標(biāo),而不是正確性判據(jù).

ISA層的基礎(chǔ)設(shè)施缺乏時間語義已經(jīng)成為安全關(guān)鍵實時系統(tǒng)設(shè)計方法學(xué)的一個基礎(chǔ)性問題,需要重新考慮實時處理器的ISA和微體系結(jié)構(gòu)組織.

在先前的工作[2]中,我們嘗試提出一種具有時間語義的實時計算機(jī)體系結(jié)構(gòu)模型實時機(jī)(realtime machine,RTM),設(shè)計了一版具有時間語義的指令集TTI(time-triggered instruction set),分析了其硬件實現(xiàn)的可行性.本文進(jìn)一步完善RTM的定義,抽象出獨立的標(biāo)準(zhǔn)時鐘部件,明確中央處理器(central processing unit,CPU)時鐘和標(biāo)準(zhǔn)時鐘協(xié)同控制的模式.接著,本文以RTM為基礎(chǔ),結(jié)合時間觸發(fā)自動機(jī)(time-triggered automata,TTA)理論,重新定義TTI,為其增加執(zhí)行時間約束指令和任務(wù)并發(fā)管理指令,并探討了TTI指令集的時間語義完備性問題.最后,本文通過一款實時處理器——實時處理單元(real-time processing unit,RPU)的設(shè)計實現(xiàn)和應(yīng)用示例,驗證了TTI的時間語義表達(dá)能力.

加州大學(xué)伯克利分校(University of California,Berkeley,UCB)的PRET機(jī)[3]研究動機(jī)與我們相近.PRET小組提出了限定代碼段執(zhí)行時間的Deadline指令[4]和MTFD指令[5],并設(shè)計了Flex PRET處理器[6].但是,他們重點關(guān)注程序時序行為的可重復(fù)性,以輔助最壞執(zhí)行時間(worst-case execution time,WCET)分析,而我們以建立具有時間語義的計算機(jī)體系結(jié)構(gòu)為目標(biāo),為程序員提供表達(dá)和控制程序時序行為的時間語義指令集,作為實現(xiàn)時序確定性系統(tǒng)的基礎(chǔ)設(shè)施.

本文的主要貢獻(xiàn)包括3個方面:

1)提出支持時間語義的實時計算機(jī)體系結(jié)構(gòu)模型RTM.RTM以馮·諾依曼機(jī)為參照,通過添加標(biāo)準(zhǔn)時鐘stdClk,建立ISA層次的時間模型.stdClk作為定義系統(tǒng)時間語義的基礎(chǔ),允許程序員以實時間(real time)控制RTM機(jī)I/O操作的時間屬性.同時,stdClk與控制處理器執(zhí)行的CPU時鐘cpuClk協(xié)作,既最小化程序執(zhí)行時間和I/O時序抖動,又實現(xiàn)了程序的I/O時序行為物理平臺無關(guān)性.

2)提出作為RTM模型軟硬件接口的時間語義指令集TTI.TTI以TTA理論為基礎(chǔ)定義最小時間語義指令集,為程序員提供直接表達(dá)和控制程序時序行為的時間語義指令.

3)設(shè)計和實現(xiàn)實時處理器RPU.RPU基于RTM模型,為RISC-V指令集添加了TTI擴(kuò)展,保證指令集時間語義.同時,它采用硬件粗粒度多線程技術(shù)(coarse-grain multithreading,CMT),以時間觸發(fā)(time-triggered,TT)機(jī)制進(jìn)行線程調(diào)度,保證任務(wù)級時間語義.

邏輯執(zhí)行時間(logical execution time,LET)編程模型[7]是一種硬實時軟件模型.本文通過LET任務(wù)集的設(shè)計示例,驗證了上述工作的有效性.

1 相關(guān)工作

本節(jié)對當(dāng)前實時計算設(shè)計方法、時間屬性和行為建模、實時處理器設(shè)計3個方面的研究工作進(jìn)行梳理.

1.1 實時計算設(shè)計方法

傳統(tǒng)的實時嵌入式系統(tǒng)設(shè)計方法關(guān)注計算過程的時序可預(yù)測性,通過設(shè)計階段進(jìn)行時序分析來滿足系統(tǒng)的時間約束.可調(diào)度性分析(schedulability analysis)[8]和端到端分析(end-to-end analysis)[9]都以任務(wù)作為最小分析單位,以任務(wù)的WCET作為輸入.然而,現(xiàn)代計算機(jī)系統(tǒng)通過引入計算并行化和訪存緩存化等優(yōu)化機(jī)制來提升平均性能,導(dǎo)致系統(tǒng)出現(xiàn)嚴(yán)重的時序不確定性問題,任務(wù)的WCET難以緊致確定[10].本質(zhì)上,保證任務(wù)的WCET不是實時系統(tǒng)的目標(biāo),現(xiàn)有方法必須要在系統(tǒng)設(shè)計的同時進(jìn)行WCET分析以保證系統(tǒng)的時序正確性,這使系統(tǒng)開發(fā)變得復(fù)雜.另一方面,將任務(wù)作為最小單位的設(shè)計分析方法也無法保證任務(wù)內(nèi)/指令級操作的時間語義,即只能表達(dá)指令在一段時間內(nèi)執(zhí)行的語義,不能直接表達(dá)指令在某個時刻執(zhí)行的語義.

20世紀(jì)90年代以來,研究者逐步認(rèn)識到實時系統(tǒng)諸多問題的根源:實時計算難以依托在通用計算之上,實時系統(tǒng)領(lǐng)域需要重新定義計算機(jī)系統(tǒng)的各個層次[11-12].研究表明:采用構(gòu)件化軟件體系結(jié)構(gòu)、時間觸發(fā)執(zhí)行機(jī)制[13]和LET編程模型[7]構(gòu)建時序關(guān)鍵系統(tǒng)是實現(xiàn)實時系統(tǒng)時序隔離(temporal isolation)、可預(yù)測(predictability)、可組合(composability)和可擴(kuò)展(extensibility)的可行技術(shù)路線.DCW[14]在現(xiàn)代處理器上實現(xiàn)了反應(yīng)式可預(yù)測的LET編程框架,但受通用計算機(jī)體系結(jié)構(gòu)和任務(wù)執(zhí)行機(jī)制的限制,LET模型系統(tǒng)執(zhí)行效率低下,需要具有時間語義的ISA和時序行為確定的體系結(jié)構(gòu)支持.

1.2 時間屬性和行為建模

20世紀(jì)50年代,邏輯學(xué)家在數(shù)理邏輯(logic)框架中添加時間語義,建立了時態(tài)邏輯(temporal logic)框架,以表達(dá)和推理用時間修飾的謂詞.Pnuel將時態(tài)邏輯引入計算機(jī)科學(xué)領(lǐng)域[15].時態(tài)邏輯作為描述型的語義表達(dá)體系,適合系統(tǒng)建模和驗證,但是難以應(yīng)用于定義操作型語義的計算過程.

1991年Henzinger為符號變遷系統(tǒng)(labeled transition system,LTS)添加時間語義,提出時間遷移系統(tǒng)(timed transition system,TTS)模型[16],用于建模復(fù)雜的并發(fā)實時系統(tǒng).TTS采用一個全局的虛擬時鐘,時間域是實數(shù)集,時間隨著事件的發(fā)生隱式地不等間距地步進(jìn).在全局時鐘的度量下,TTS約束了轉(zhuǎn)移(transitions)發(fā)生時間的上下界,并用時間狀態(tài)序列(timed state sequences)刻畫系統(tǒng)的狀態(tài)變化.TTS作為LTS,重點關(guān)注系統(tǒng)所處狀態(tài)及其變遷,對狀態(tài)變遷時發(fā)生的計算說明較少.

1991—1994年,Alur和Dill為自動機(jī)模型添加時間語義,提出和完善了時間自動機(jī)(timed automata,TA)[17],用以建模實時系統(tǒng)隨著時間的發(fā)展而不斷變化的行為.時間自動機(jī)采用離散時間模型(discrete-time model),該時間模型要求時間序列是單調(diào)遞增的整數(shù)值,即時間域是正整數(shù)域.而它接受的時間詞(timed words)則采用稠密時間模型(dense-time model).時間詞是指一個由關(guān)聯(lián)實數(shù)時間值的符號組成的無窮序列.時間自動機(jī)采用多時鐘模型來表達(dá)系統(tǒng)的時間需求,通過系統(tǒng)時間與特定時刻的大于、小于和等于關(guān)系分別表達(dá)“在……之后”“在……之前”和“在……時刻”的時間語義.時間自動機(jī)可以用來形式化地建模和驗證實時系統(tǒng)的時間屬性.相比于TTS,TA直接通過描述系統(tǒng)的計算過程來刻畫系統(tǒng)的行為.另一方面,TTS只能約束轉(zhuǎn)移發(fā)生時間的上下界,而TA則可以直接表達(dá)操作發(fā)生于特定時刻的語義.

時間自動機(jī)基于多時鐘模型和事件觸發(fā).2004年Král和Mokrushin等人提出時間觸發(fā)自動機(jī)(TTA)[18].TTA基 于單時鐘模型,使用“[n]”和“(n)”表達(dá)“在n時刻”和“每n時刻”的時間語義.另外,時間觸發(fā)自動機(jī)接收數(shù)字化(digitalized)的時間詞.究其含義,時間自動機(jī)認(rèn)為計算系統(tǒng)從外界接收連續(xù)的信息,而時間觸發(fā)自動機(jī)認(rèn)為計算系統(tǒng)從外部設(shè)備接收處理后得到的數(shù)字信號.

時間自動機(jī)理論和時間觸發(fā)自動機(jī)理論對時間語義指令集的設(shè)計具有重要的指導(dǎo)意義,是研究時間語義完備性理論的重要參考.

1.3 實時處理器設(shè)計

Schoeberl小組進(jìn)行了一系列優(yōu)化硬件最壞執(zhí)行時間分析的研究.通用處理器的設(shè)計中,體系結(jié)構(gòu)層次的新技術(shù)如流水線、高速緩存、分支預(yù)測和亂序執(zhí)行等提升了系統(tǒng)的平均性能,但這些技術(shù)使程序的WCET分析越來越復(fù)雜,甚至難以進(jìn)行.JOP[19]是Java虛擬機(jī)的硬件實現(xiàn).JOP采用簡單的三段流水使Java程序的WCET分析更準(zhǔn)確.Patmos處理器[20]同樣以優(yōu)化WCET分析為目標(biāo),它采用為該目標(biāo)定制的類RISC指令集.同時,Patmos使用Method Cache作為指令Cache,使用Split Cache作為數(shù)據(jù)Cache,能夠提前預(yù)知指令延遲和執(zhí)行時間.Hahn和Reineke關(guān)注2種時序異常,設(shè)計具有嚴(yán)格訪存順序的SIC(strictly in-order core)[21].SIC具有單調(diào)性,消除了時序異常并簡化了WCET分析.

Roop小組對支持同步語義的反應(yīng)式處理器[22]進(jìn)行研究,希望通過在指令集中增加同步語義來直接支持執(zhí)行同步語言程序.同步編程語言[23]基于同步假設(shè),通過信號管理,如輪詢(polling)、發(fā)射(emission)和搶占(preemption)等進(jìn)行程序的同步,保證了并發(fā)行為的確定性,易于程序驗證.HiDRA[24]是一個實時系統(tǒng)的軟硬件協(xié)同設(shè)計方案,使用多個反應(yīng)式核REMIC[25]構(gòu)造全局異步局部同步(globally asynchronous locally synchronous,GALS)的體系結(jié)構(gòu),提供類Esterel語言的同步語義.STARPro[26]與HiDRA思想一致,但HiDRA支持類Esterel的同步語義,而STARPro旨在直接支持Esterel程序執(zhí)行.另外,Roop團(tuán)隊提出基于C語言擴(kuò)展的PRET-C同步語言,并提出支持PRET-C同步語義的微體系結(jié)構(gòu)ARPRET[27].ARPRET分為2部分:1)GPP實現(xiàn)通用計算;2)PFU負(fù)責(zé)調(diào)度和保證功能的時間屬性正確.

Lee小組提出PRET(precision timed)概念[3].他們認(rèn)為硬件體系結(jié)構(gòu)中的數(shù)字電路時鐘是精確的,但是通用計算指令集抽象掉了這個精確的時間,所以為了程序的時序行為可重復(fù),PRET機(jī)要向上層提供這一精確的時間.該小組研制了多款PRET處理器[4,6,28].Flex PRET處理器[6]從流水線、線程調(diào)度、時間指令、存儲系統(tǒng)4個方面對處理器的時間屬性進(jìn)行規(guī)范,并用時間指令DU(delay until)保證代碼的執(zhí)行時間下界,時間指令EE(exception on expire)保證代碼的執(zhí)行時間上界.此方案可以約束指令序列執(zhí)行時間的上下界,無法直接表達(dá)操作發(fā)生在某個時刻的語義.Wan和Li等人在文獻(xiàn)[29]中提出構(gòu)建時間語義指令集的思想,擬添加時間語義和操作語義綁定的指令,但該想法處于比較早期的階段.

總體而言,當(dāng)前實時處理器設(shè)計研究缺乏ISA層理論模型支持.在通用計算中,圖靈機(jī)[30]為通用計算機(jī)系統(tǒng)奠定堅實的理論基礎(chǔ),馮·諾依曼機(jī)[31]是通用計算機(jī)系統(tǒng)統(tǒng)一的實現(xiàn)模型.實時處理器理論基礎(chǔ)的缺乏,導(dǎo)致時間語義難以表達(dá),或表達(dá)能力邊界不確定,程序的時序行為難以形式化驗證.

2 背景知識

本節(jié)介紹具有時序確定性的系統(tǒng)構(gòu)建范式時間觸發(fā)范式以及按照時間觸發(fā)范式構(gòu)建的計算理論時間觸發(fā)自動機(jī),介紹時間模型的分類.后文定義時間模型,參考時間觸發(fā)自動機(jī)理論設(shè)計了最小時間語義指令集TTI,并以時間觸發(fā)范式實現(xiàn)了實時處理器RPU.

2.1 時間觸發(fā)范式

事件觸發(fā)范式和時間觸發(fā)范式是2種截然不同的系統(tǒng)設(shè)計范式,本節(jié)參考文獻(xiàn)[13],對2種范式進(jìn)行介紹.2種系統(tǒng)設(shè)計范式的核心區(qū)別是:在事件觸發(fā)系統(tǒng)(event-triggered systems,ET系統(tǒng))中,重大事件的發(fā)生導(dǎo)致了響應(yīng)活動的啟動;在時間觸發(fā)系統(tǒng)(time-triggered systems,TT系統(tǒng))中,響應(yīng)活動是在預(yù)定的時間點實時啟動的.

ET系統(tǒng)使用中斷機(jī)制感知外部事件的發(fā)生,2類主要的事件是P類事件(predictable events)和C類事件(chance events).對于P類事件,可以提前保留將來傳輸和處理它們所需的資源.而C類事件可能在短時間內(nèi)集中發(fā)生,這將超出ET系統(tǒng)的處理能力,系統(tǒng)必須有對這類事件的存儲能力,并適當(dāng)限制事件的感知.在ET系統(tǒng)中,判斷任務(wù)集滿足時間約束和找出可行的調(diào)度算法都是NP難的問題.因此在實踐中,ET系統(tǒng)往往采用靜態(tài)優(yōu)先級算法進(jìn)行運(yùn)行時調(diào)度,這導(dǎo)致ET系統(tǒng)的時間行為是運(yùn)行時上下文相關(guān)的,且不具有單調(diào)性,無法保證系統(tǒng)的時間可預(yù)測性.設(shè)計者只有通過模擬負(fù)載進(jìn)行廣泛的系統(tǒng)測試才能判斷ET系統(tǒng)的正確性.然而,C類事件的存在導(dǎo)致難以對ET系統(tǒng)進(jìn)行全面的測試.

TT系統(tǒng)使用輪詢機(jī)制獲取外部實體的狀態(tài).輪詢是周期性的,輪詢發(fā)生的時間序列被稱為觀測格(observation grid);系統(tǒng)根據(jù)狀態(tài)進(jìn)行響應(yīng),響應(yīng)發(fā)生的時間序列稱為響應(yīng)格(action grid).TT系統(tǒng)需要事件傳感器對外部事件進(jìn)行處理,形成系統(tǒng)需要的狀態(tài)信息.在TT系統(tǒng)的設(shè)計階段,設(shè)計者首先確定系統(tǒng)的觀測格和時間關(guān)鍵任務(wù)的最壞執(zhí)行時間,然后在編譯時期通過調(diào)度策略生成確定的調(diào)度表,在運(yùn)行時期執(zhí)行簡單的表查找來調(diào)度任務(wù).因此,TT系統(tǒng)的時間行為是運(yùn)行時上下文無關(guān)的,具有確定性.通過仔細(xì)的設(shè)計,TT系統(tǒng)的設(shè)計者可以精確地預(yù)測任務(wù)的時序行為和系統(tǒng)的時序行為.另一方面,觀測格和響應(yīng)格決定了TT系統(tǒng)的時基是離散的,離散時基確保每一種輸入情況都可以被觀察和再現(xiàn),因而TT系統(tǒng)的測試更加可構(gòu)造和系統(tǒng)化.

2.2 時間觸發(fā)自動機(jī)

時間觸發(fā)自動機(jī)[18]是基于事件的非即時可觀察性,對時間自動機(jī)進(jìn)行簡化而形成的計算模型.TTA是在時間觸發(fā)模式下運(yùn)行的有限狀態(tài)自動機(jī),接受定時語言的數(shù)字化版本.本質(zhì)上,TTA是數(shù)字計算機(jī)(或數(shù)字控制器)的時間表,描述了在給定時間點該計算機(jī)應(yīng)執(zhí)行的操作,可以轉(zhuǎn)換為計算機(jī)上的可執(zhí)行程序.

TTA采用一個全局參考時鐘,時間域為整數(shù)集N,它采用隱式的時間模型,把狀態(tài)變化的時刻作為隱式參考點.它接受的時間詞是數(shù)字化后的時間詞,更符合現(xiàn)代數(shù)字計算機(jī)的特征.TTA只能在滿足時序約束的整數(shù)時間點接收時間詞(消耗外部事件)和發(fā)生轉(zhuǎn)移.時序約束集合Θ包含周期性的和瞬時的(也稱非周期性的)2種時序約束,分別由a(n)和a[n]來表示.標(biāo)有a(n)的轉(zhuǎn)移表示每n個時間單位應(yīng)該檢查a是否已發(fā)生;標(biāo)有a[n]的轉(zhuǎn)移表示第n個時間單位應(yīng)該檢查a是否已發(fā)生.

定義1.時間觸發(fā)自動機(jī)[18].時間觸發(fā)自動機(jī)ATTA定義為四元組〈Σ,S,s0,T〉,其中:

1)Σ是有限字符表,字符代表事件;

2)S是有限狀態(tài)集合;

3)s0∈S是初始狀態(tài);

4)T?S×Σ?×Θ×S是轉(zhuǎn)移邊的有限集合.

注:Σ?是離散化后的Σ.

定義2.時間觸發(fā)自動機(jī)行為語義[18].初始狀態(tài)為(s0,0)的時間觸發(fā)自動機(jī)〈Σ,S,s0,T〉的語義由3個規(guī)則定義:表示(s1,ω,[n],s2)∈T,使用表示(s1,ω,(n),s2)∈T,使用n表

其中,使用示不超過n的最大正整數(shù).定義2中的第3條規(guī)則確保轉(zhuǎn)移的發(fā)生不會導(dǎo)致有整數(shù)時間點被跳過.

圖1是時間觸發(fā)自動機(jī)的一個示例,其中的null符號表示接收長度為0的時間詞,即不消耗事件發(fā)生轉(zhuǎn)移.在初始狀態(tài)S0時,自動機(jī)在第1個時間單位檢測開始命令b是否發(fā)生,如果b發(fā)生,自動機(jī)將接收b并遷移到運(yùn)行狀態(tài)S1.在運(yùn)行狀態(tài)S1時,自動機(jī)每1個時間單位檢測停止命令e是否發(fā)生,如果e發(fā)生,自動機(jī)將接收e并遷移到終止?fàn)顟B(tài)S3;每3個時間單位檢測正常信號r是否發(fā)生,如果r發(fā)生,自動機(jī)將接收r并仍遷移到運(yùn)行狀態(tài)S1;每3個時間單位檢測出錯信號w是否發(fā)生,如w發(fā)生,自動機(jī)將接收w并遷移到故障狀態(tài)S2.在故障狀態(tài)S2,系統(tǒng)會進(jìn)行復(fù)位,并在第5個時間單位遷移到S0狀態(tài).注意,如果在S1狀態(tài)未檢測到正常信號r的發(fā)生,狀態(tài)機(jī)也會停留在S1狀態(tài),但不會接收一個r事件.

Fig.1 An example of time-triggered automaton圖1 時間觸發(fā)自動機(jī)示例

2.3 時間模型

時間模型是實時系統(tǒng)的理論核心,從時間線的構(gòu)成、時間步進(jìn)規(guī)則和事件觀測方法等3個方面刻畫和定義系統(tǒng)的時間行為.本文參考文獻(xiàn)[32],對描述時間模型3個方面的維度進(jìn)行說明.

描述時間模型中時間線構(gòu)成的維度有:

1)離散的或者是稠密的.根據(jù)采用的時間域是離散集合還是稠密集合,時間模型分為離散時間模型和稠密時間模型.按照數(shù)學(xué)上集合連續(xù)性的概念,稠密時間模型又進(jìn)一步分為連續(xù)時間模型和非連續(xù)時間模型.如果系統(tǒng)同時采用了離散時間模型和稠密時間模型,則系統(tǒng)的時間模型為混合時間模型.

2)有界的或者是無窮的.按照系統(tǒng)生命周期內(nèi)的行為是否為周期性的,可以分為有界時間模型和無窮時間模型.

3)定序的或者是定量的.只能描述序的模型,能定序地定義時間關(guān)系,稱為定序時間模型;能夠描述序和時刻的模型,能定量地定義時間關(guān)系,稱為定量時間模型.

教師要加強(qiáng)對學(xué)生們優(yōu)秀的傳統(tǒng)文化的素質(zhì)教育，提升學(xué)生們的精神文化素養(yǎng)水平。傳統(tǒng)文化是中華民族文化最根本的積淀，傳統(tǒng)文化包含著豐富的愛國主義精神和優(yōu)秀的道德素質(zhì)文化，能夠不斷激發(fā)學(xué)生們的愛國熱情以及提升學(xué)生們的精神文化素養(yǎng)水平，教師要加強(qiáng)對學(xué)生們的愛國主義教育，讓學(xué)生們認(rèn)清什么是社會主義核心價值觀，樹立學(xué)生們的“天下興亡，匹夫有責(zé)”的高尚責(zé)任心和遠(yuǎn)大抱負(fù)，增強(qiáng)學(xué)生們的民族自豪感和自信心。其次要對學(xué)生們進(jìn)行倫理道德教育，積極推行儒學(xué)教育思想，倡導(dǎo)與人為善以及人與社會自然的和諧相處，樹立正確的社會主義榮辱觀，不斷塑造自我，培養(yǎng)自我優(yōu)秀的精神品質(zhì)和健康的人格。

4)線性的或者是分支的.線性時間模型為線性結(jié)構(gòu),能夠表示具有唯一未來行為的屬性.分支時間模型為樹結(jié)構(gòu),允許用戶陳述具有分支未來行為的屬性.已有研究表明線性時間模型和分支時間模型是可以相互轉(zhuǎn)化的.

描述時間模型中時間步進(jìn)規(guī)則的維度有:

1)物理的或者是邏輯的.物理時間是指物理設(shè)備提供的時間,隨實時間步進(jìn);邏輯時間是指使用某種邏輯關(guān)系對事件進(jìn)行排序形成的虛擬時間,隨事件發(fā)生步進(jìn).

描述時間模型中事件觀測方法的維度有:

1)顯示的或者是隱式的.顯示時間模型使用時域范圍內(nèi)的顯示術(shù)語,顯示表達(dá)時刻,有量詞可以對時間進(jìn)行描述;隱式時間模型無法描述時域量詞,隱含當(dāng)前時刻的概念,相對于當(dāng)前時刻對事件進(jìn)行排序,沒有量詞進(jìn)行度量.

2)絕對的或者是相對的.絕對時間是指使用點時間(即時刻)進(jìn)行描述的時間模型;相對時間則是指使用相對于當(dāng)前時間的段時間進(jìn)行描述的時間模型.

另外,在分布式的場景下,時間有全局的或者是局部的之分.全局時間是指所有節(jié)點統(tǒng)一同步后產(chǎn)生的時間;局部時間是指每個節(jié)點內(nèi)自己使用的時間.

3 實時機(jī)模型

本文提出RTM機(jī)模型以解決當(dāng)前處理器體系結(jié)構(gòu)層缺乏時間語義的問題.RTM機(jī)以馮·諾依曼機(jī)為基礎(chǔ),引入標(biāo)準(zhǔn)時鐘stdClk,并增加時間語義指令集.TTI指令集參考TTA模型定義最小時間語義指令集,允許程序員以實時間概念定義RTM機(jī)I/O操作的時間行為屬性.實時程序可以在基于RTM機(jī)的硬件平臺之間進(jìn)行時間語義一致的移植.

3.1 實時機(jī)模型RTM

計算機(jī)科學(xué)領(lǐng)域的時間概念相當(dāng)原始.圖靈機(jī)和馮·諾依曼機(jī)模型基于順序控制抽象,指令一條接一條執(zhí)行,時間先后關(guān)系(temporal succession)是當(dāng)前機(jī)器語言級唯一可用的時序關(guān)系.雖然定義馮·諾依曼機(jī)的程序邏輯行為無需顯式地引用量化時間概念,但無法滿足實時系統(tǒng)所需要的實時間約束定義.

定義3.RTM機(jī).RTM機(jī)對馮·諾依曼機(jī)進(jìn)行擴(kuò)充,如圖2所示:

Fig.2 RTM machine architecture圖2 RTM機(jī)結(jié)構(gòu)模型

1)計算機(jī)系統(tǒng)由運(yùn)算器、控制器、存儲器、標(biāo)準(zhǔn)時鐘和I/O設(shè)備等功能部件構(gòu)成.

2)標(biāo)準(zhǔn)時鐘用于操作定時,在保持馮·諾依曼機(jī)指令的邏輯功能不變的同時,增加約束特定操作的時序和限定操作序列(動作)的執(zhí)行時間等時序功能,支持構(gòu)建具有時間語義的指令集.

3)RTM機(jī)的指令字由操作碼、地址碼和定時碼構(gòu)成.操作碼定義操作的功能,地址碼指定操作數(shù)和下一條指令的地址,定時碼指定操作的時間屬性和約束.

由于各個硬件平臺的時鐘設(shè)備不同,即使程序具有相同的時間語義,也無法得到相同的時間行為.RTM機(jī)引入標(biāo)準(zhǔn)時鐘,并據(jù)此定義其指令的時間語義,使具有時間語義的程序得到同一時間模型的支持,實現(xiàn)了程序的I/O時序行為物理平臺無關(guān)性.

定義4.RTM機(jī)時間模型.RTM機(jī)的時間模型定義為:

1)時間線的構(gòu)成是離散的、定量的、線性的時間域N.

2)時間步進(jìn)規(guī)則是物理的,隨牛頓時間步進(jìn).3)事件觀測方法是顯示的、絕對的.

RTM機(jī)以支持緊致時間設(shè)計為目標(biāo),其核心思想不是簡單地在CPU中增加標(biāo)準(zhǔn)時鐘,而在于明確了時間行為控制抽象,并通過提供時間語義指令集,實現(xiàn)了時域控制的原子性和可組合性,并最小化(周期精確)定時抖動.

時間語義指令集的完備性問題是RTM機(jī)模型的一個基礎(chǔ)性問題,限定了RTM機(jī)的時間語義表達(dá)能力邊界.需要進(jìn)一步基于實時邏輯和時間自動機(jī)等理論框架對其進(jìn)行研究.我們給出一種支持時間觸發(fā)的RTM機(jī)時間語義指令集TTI.參考TTA模型,TTI指令集至少需要支持3種操作:

1)時間管理操作.獲取全局參考時間并設(shè)置時間參考點.

2)定時觸發(fā)輸入操作.無論是[n]還是(n),都需要定時對事件進(jìn)行采樣.

3)(n)原語的周期性操作.

參考以上需求,本文在3.3節(jié)中給出了TTI的定義.

RTM機(jī)以“關(guān)注分離(separation of concerns)”和“構(gòu)建正確(correct-by-construction)”為設(shè)計原則,區(qū)分邏輯控制與時域控制,為實現(xiàn)從時序可預(yù)測設(shè)計到時序確定性設(shè)計轉(zhuǎn)變奠定了理論基礎(chǔ),利于實時程序代碼自動生成和化簡實時系統(tǒng)驗證的復(fù)雜度.

3.2 標(biāo)準(zhǔn)時鐘stdClk

現(xiàn)代計算機(jī)系統(tǒng)主要有2種時鐘域:1)CPU時鐘cpuClk.用于驅(qū)動其數(shù)據(jù)通路中各個功能部件同步運(yùn)行.不同平臺的cpuClk時鐘頻率不同,與應(yīng)用程序的時序控制無關(guān).文獻(xiàn)[12]認(rèn)為該時鐘是精確的,但是通用計算機(jī)的ISA忽略了其時間精確性.2)操作系統(tǒng)和應(yīng)用程序提供定時中斷服務(wù)的時鐘.該時鐘與cpuClk異步,且時序粒度高幾個數(shù)量級,程序員依賴該時鐘進(jìn)行粗粒度時序控制.因此,為了精確控制系統(tǒng)的時序,需要定義新的時鐘.

定義5.標(biāo)準(zhǔn)時鐘stdClk.RTM機(jī)的標(biāo)準(zhǔn)時鐘std Clk是基于實時間域的物理時鐘,用于實時程序的時間行為控制.

標(biāo)準(zhǔn)時鐘的時間粒度依賴于應(yīng)用場景,對時間精度要求較高的系統(tǒng)可采用粒度小(如100 ns)的標(biāo)準(zhǔn)時鐘,對時間精度要求較為放松的系統(tǒng)可采用粒度較大(如50μs)的標(biāo)準(zhǔn)時鐘.引入標(biāo)準(zhǔn)時鐘后,現(xiàn)代計算機(jī)系統(tǒng)通過cpuClk驅(qū)動指令執(zhí)行,通過stdClk提供時域控制依據(jù).cpuClk與stdClk的協(xié)作,分離了實時計算系統(tǒng)中的邏輯控制和時域控制,即分離了驅(qū)動計算機(jī)運(yùn)行和控制計算機(jī)時序行為的時鐘,有利于支持確定的時間語義,便于形式化建模和分析.另一方面,通過標(biāo)準(zhǔn)時鐘來精確定時,保證程序員以統(tǒng)一的實時間抽象控制程序的時序行為,使得不同平臺上的定時程序具有時間行為一致性.

基于標(biāo)準(zhǔn)時鐘stdClk,RTM機(jī)實時程序的邏輯執(zhí)行與其時域控制具有確定性的松弛同步時序關(guān)系,如定理1,可以實現(xiàn)周期精確的系統(tǒng)時序行為.

定理1.std Clk與cpuClk的關(guān)系定理.假設(shè)std Clk的周期為Tstd,cpuClk的周期為Tcpu,并假設(shè)Tcpu＜Tstd,則它們有2種關(guān)系:

1)當(dāng)cpuClk與std Clk同步時,?n∈N,使得Tstd＝n×Tcpu.

2)當(dāng)cpuClk與stdClk異步時,?n∈N,0≤t＜Tcpu,使得Tstd＝n×Tcpu＋t.

證明.由模運(yùn)算可知,?0≤c＜b,使得a＝cmodb.即?0≤t＜Tcpu,使得Tstd＝tmodTcpu.當(dāng)cpuClk與std Clk同步時,cpuClk與std Clk上升沿重合,即t＝0,Tstd＝0 modTcpu,所以?n∈N,使得Tstd＝n×Tcpu.當(dāng)cpuClk與stdClk異步時,cpuClk與stdClk無特別關(guān)系,0≤t＜Tcpu,所以?n∈N,0≤t＜Tcpu,使得Tstd＝n×Tcpu＋t.證畢.

由定理1我們可以得到引理1.

引理1.假設(shè)stdClk上升沿發(fā)生時間為Ustd,該時間后下一個cpuClk上升沿發(fā)生時間為U ncpu,則它們滿足關(guān)系:

1)當(dāng)cpuClk與std Clk同步時,U ncpu－Ustd＝Tcpu.

2)當(dāng)cpuClk與stdClk異步時,0＜U ncpu－Ustd＜Tcpu.

在同步情況下,引理1顯然成立.異步情況下處于邊界情況,即差值為0或者Tcpu時,異步情況轉(zhuǎn)換為同步情況,可見異步情況同樣成立.

定理1和引理1說明,可以將stdClk與cpuClk的最小偏差控制在一個cpuClk周期以內(nèi),最小化程序時序和I/O時序抖動.定理1和引理1展示的控制時序如圖3所示.圖3(a)中,std Clk與cpuClk為同步關(guān)系,其控制抖動為Tcpu;圖3(b)中,stdClk與cpuClk為異步關(guān)系,其控制抖動小于Tcpu.

Fig.3 Timing of using stdClk for controlling圖3 標(biāo)準(zhǔn)時鐘的控制時序

實時系統(tǒng)技術(shù)往往應(yīng)用在分布式場景下.而RTM系統(tǒng)的時間行為基于標(biāo)準(zhǔn)時鐘,與運(yùn)行平臺無關(guān),故在實時分布式場景中應(yīng)用RTM,只需要對標(biāo)準(zhǔn)時鐘進(jìn)行同步.

根據(jù)標(biāo)準(zhǔn)時鐘提供的定時,設(shè)計帶有時間語義的指令集作為實時處理器軟硬件接口,可以提供at,delay-until和timestamp等控制時間行為的指令,支持邏輯執(zhí)行時間模型和時間觸發(fā)等應(yīng)用模式.

3.3 時間語義指令集TTI

RTM機(jī)的TTI指令集主要包含標(biāo)準(zhǔn)時鐘管理指令、時間觸發(fā)操作指令、執(zhí)行時間約束指令、任務(wù)并發(fā)管理指令4部分指令,以及時間粒度寄存器tg(time granularity)、時間寄存器ti和時間戳寄存器ts.其中,標(biāo)準(zhǔn)時鐘管理指令對系統(tǒng)的標(biāo)準(zhǔn)時鐘進(jìn)行管理,生成系統(tǒng)時間,規(guī)范其應(yīng)用方法;時間觸發(fā)操作指令定義操作和時間綁定的指令,保證了操作在指定時間觸發(fā)執(zhí)行;執(zhí)行時間約束指令參考PRET機(jī)[12],保證一段代碼的執(zhí)行時間上下界;任務(wù)并發(fā)管理指令摒棄傳統(tǒng)的使用中斷的軟件任務(wù)并發(fā)管理,提供確定性的硬件線程管理任務(wù)并發(fā)的能力.由于不同系統(tǒng)、甚至同一系統(tǒng)的不同運(yùn)行模式需要不同的時間粒度,時間粒度寄存器tg,用于用戶自定義時間粒度;時間寄存器ti表示當(dāng)前的系統(tǒng)時間,系統(tǒng)時間由系統(tǒng)根據(jù)標(biāo)準(zhǔn)時鐘和系統(tǒng)時間粒度生成;分布式系統(tǒng)中,時間戳(timestamp)是支持定序的重要數(shù)據(jù),時間戳寄存器ts保存系統(tǒng)與外界交互事件的時間戳.

Table 1 Functionality of TTI"s Instructions表1 TTI指令功能

TTI指令的功能如表1所示,表1中r1,r2和rd為通用寄存器.TTI指令集包括:

1)標(biāo)準(zhǔn)時鐘管理指令.setti/getti指令用于設(shè)置/獲取時間寄存器ti,即系統(tǒng)時間;settg指令用于設(shè)置時間粒度寄存器tg,即系統(tǒng)當(dāng)前時間粒度、時間向前自增的單位(time unit);getts指令用于獲取時間戳寄存器ts,即系統(tǒng)上一條時間觸發(fā)操作指令ttiat/ttoat的生效時間.

2)時間觸發(fā)操作指令.ttiat/ttoat指令用于在指定時刻對I/O端口進(jìn)行輸入/輸出;ttiat/ttoat指令的執(zhí)行代表系統(tǒng)與外部環(huán)境的交互事件,會設(shè)置時間戳寄存器ts.

3)執(zhí)行時間約束指令.delay指令用于約束代碼的最短執(zhí)行時間,即到該時間之前,delay指令會阻塞后續(xù)代碼執(zhí)行;mtfd指令用于約束代碼的最壞執(zhí)行時間,需要編譯時期的檢查配合完成,即保證執(zhí)行該指令的時間不超過指定時間.

4)任務(wù)并發(fā)管理指令.tkend指令用于標(biāo)志當(dāng)前線程中任務(wù)的截止;addtk指令用于向硬件時間觸發(fā)調(diào)度表添加表項,即通過addtk指令設(shè)置好靜態(tài)的時間觸發(fā)調(diào)度表.

TTI的正確執(zhí)行需要保證其邏輯正確性和時間正確性.

Fig.4 Example of translating TTA to TTI program圖4 TTA轉(zhuǎn)換為TTI程序示例

3.4 TTI的時間語義完備性分析

為了支持實時計算,需要回答RTM機(jī)應(yīng)該具有什么時間語義,或其最小時間指令集應(yīng)包含哪些指令等問題.RTM機(jī)的邏輯功能指令集與馮·諾依曼機(jī)指令集等價,而TTI指令集的時間語義應(yīng)至少具有與TTA相同的時間語義表達(dá)能力.

TTI能夠充分支持TTA的時間語義:1)支持TTA時間模型.TTA采用一個全局的參考時鐘,對應(yīng)TTI中由標(biāo)準(zhǔn)時鐘生成的系統(tǒng)時間ti.時間觸發(fā)自動機(jī)以進(jìn)入狀態(tài)作為時間參考點,TTI可以使用getti獲取當(dāng)前系統(tǒng)時間,然后使用該時刻作為參考點.2)支持a(n)語義.支持周期語義可以使用循環(huán)結(jié)合時間觸發(fā)操作指令來實現(xiàn).周期對應(yīng)循環(huán),獲取周期開始時的系統(tǒng)時間ti,使用ttiat在ti＋n時刻進(jìn)行輸入.如果輸入的是a,則發(fā)生狀態(tài)遷移;否則,進(jìn)入下一個周期.3)支持a[n]語義.支持瞬時語義使用ttiat完成即可.

TTI對時間觸發(fā)自動機(jī)語義的充分支持,意味著所有TTA可以轉(zhuǎn)換成TTI程序,即TTI是TTA時間語義完備的.一個簡單的轉(zhuǎn)換示例如圖4所示,圖4(a)中TTA從S0開始運(yùn)行,在第2個時間單位接收b事件轉(zhuǎn)移到S1;對應(yīng)圖4(b)中S0代碼段,S0代碼段使用getti獲取當(dāng)前系統(tǒng)時間,將其加2作為ttiat的執(zhí)行時刻,檢查ttiat輸入的事件是否為b,如果是,轉(zhuǎn)移到S1代碼段,否則永遠(yuǎn)停留在S0代碼段.圖4(a)在S1狀態(tài)時,TTA每1個時間單位檢測e事件是否發(fā)生,如果是,則接收e事件轉(zhuǎn)移到S0狀態(tài);對應(yīng)圖4(b)中S1代碼段,S1代碼段使用getti獲取當(dāng)前系統(tǒng)時間,將其加1作為ttiat的執(zhí)行時刻,檢查ttiat輸入的事件是否為e,如果是,轉(zhuǎn)移到S0代碼段,否則,跳轉(zhuǎn)到begin代碼段,等待下一個時間單位檢測e事件是否發(fā)生,實現(xiàn)周期語義.

4 實時處理單元

實時處理器RPU是RTM機(jī)的實例.4.1節(jié)基于RISC-V指令集[33]定義TTI指令集,形成RISCV TTI功能模塊.4.2節(jié)給出基于經(jīng)典五段流水設(shè)計的RPU的原理圖,RPU添加了粗粒度多線程和時間觸發(fā)執(zhí)行等確保時序?qū)傩缘臋C(jī)制.接著,本文以開源32位RISC-V處理器CV32E40P[34]為框架對RPU進(jìn)行實現(xiàn),并以軟核的方式部署到Xilinx Artix-7 XC7A100T FPGA上,實現(xiàn)時RPU采用的stdClk頻率為1 MHz,cpuClk頻率為25 MHz.4.3節(jié)和4.4節(jié)給出Xilinx Vivado 2019仿真和綜合得到的時序結(jié)果和資源消耗結(jié)果.

4.1 RISC-V TTI

RISC-V是一個典型的三操作數(shù)、加載 存儲形式的RISC指令集架構(gòu),由基礎(chǔ)指令集和擴(kuò)展指令集組成.基礎(chǔ)指令由基本整數(shù)指令構(gòu)成,擴(kuò)展指令分為標(biāo)準(zhǔn)擴(kuò)展和非標(biāo)準(zhǔn)擴(kuò)展兩大類.現(xiàn)階段的標(biāo)準(zhǔn)擴(kuò)展有乘法和除法擴(kuò)展(M)、原子指令擴(kuò)展(A)、單精度(F)和雙精度(D)運(yùn)算擴(kuò)展等.非標(biāo)準(zhǔn)擴(kuò)展作為一個高度特殊化的擴(kuò)展,允許用戶根據(jù)需求自定義完成.

本文基于RISC-V非標(biāo)準(zhǔn)擴(kuò)展對TTI指令集進(jìn)行定義,采用RISC-V預(yù)留的opcode域custom-0,根據(jù)funct3區(qū)分上述四類指令,如表2、表3所示.RISC-V TTI擴(kuò)展與原RISC-V指令集采用相同的尋址模式,有所不同的是,ttoat指令有3個操作數(shù),都是讀寄存器,即要從寄存器組中讀出r1,r2和r3寄存器,最后在r1指定的時刻將r3寫入r2表示的輸出端口上.本文的實現(xiàn)平臺,開源RISC-V核CV32E40P的通用寄存器組有3個寄存器讀端口,因此擴(kuò)展工作不會因為ttoat的特殊增加額外開銷.

Table 2 Word Format of R-Type Extended TTI Instructions表2 R類型TTI擴(kuò)展指令的指令字格式

Table 3 Word Format of Custom-Type Extended TTI Instructions表3 自定義類型TTI擴(kuò)展指令的指令字格式

4.2 RPU的設(shè)計

本節(jié)基于經(jīng)典五段流水線[35]給出以TTI為軟硬件接口的RPU的設(shè)計.相較于經(jīng)典五段流水新增/改動部分的原理圖如圖5所示.本文采用PLL分頻的方法產(chǎn)生1 MHz的標(biāo)準(zhǔn)時鐘std Clk,可參考其他文獻(xiàn)采用更加精確的實現(xiàn)方法.分頻的方法產(chǎn)生的std Clk與cpuClk周期是整倍數(shù)關(guān)系,且std Clk與cpuClk上升沿同步.由引理1可知,在本文的std Clk與cpuClk協(xié)同下,控制將會在std Clk生效后的Tcpu時間生效.

圖5中的Decode模塊增加了對RISC-V TTI指令的譯碼,Control模塊增加了相應(yīng)的控制.圖5中的Time Unit模塊負(fù)責(zé)管理std Clk,產(chǎn)生系統(tǒng)時間,如圖6所示.時間粒度寄存器保存通過settg指令設(shè)置的時間粒度;cnt寄存器直接接收標(biāo)準(zhǔn)時鐘進(jìn)行自增,當(dāng)cnt寄存器增長到與tg寄存器相等的時候,表示系統(tǒng)時間的時間寄存器ti自增;ti寄存器也可通過setti指令進(jìn)行設(shè)置,通過getti指令進(jìn)行讀取.

Fig.5 Block diagram of RPU(Only incremental part of classic pipelines)圖5 RPU原理圖:經(jīng)典五段流水改動部分

Fig.6 Block diagram of Time Unit圖6 Time Unit原理圖

時間觸發(fā)操作指令按照TT機(jī)制執(zhí)行.to信號生效后,RPU比較ti寄存器和r1,若ti＜r1,表示未到觸發(fā)時間,RPU通過Stall＆Flush模塊停頓流水線;若ti＝r1寄存器,RPU執(zhí)行當(dāng)前時間觸發(fā)操作指令,并將當(dāng)前ti寄存器值記錄到時間戳寄存器ts,ts寄存器可通過getts進(jìn)行讀取;若ti＞r1寄存器,表示系統(tǒng)發(fā)生時序錯誤異常.對TTI中時間觸發(fā)操作指令的實現(xiàn),保證了RPU指令級的時間可預(yù)測屬性.

RPU采用粗粒度多線程支持TTI的并發(fā)管理指令.CMT需要RPU有多套硬件上下文,體現(xiàn)在圖5中的PC Group和Regfile Group模塊.線程采用TT機(jī)制切換體現(xiàn)在圖5中的CMT Control模塊,該模塊根據(jù)由標(biāo)準(zhǔn)時鐘生成的ti進(jìn)行硬件線程控制.addtk指令會向TT Table中增加表項,RPU根據(jù)TT表控制線程切換.TT表結(jié)構(gòu)如圖7所示,它使用圖示結(jié)構(gòu)模擬隊列,圖7中的Time和ID寄存器組為數(shù)組,head和tail兩個寄存器為頭尾指針,通過ad d信號添加表項ad d_time和ad d_id;在表頭指定的時刻彈出head_time和head_id,進(jìn)行線程切換控制.線程也可通過執(zhí)行tkend表示當(dāng)前任務(wù)執(zhí)行完成,主動釋放RPU控制權(quán).CMT Control模塊中的FSM負(fù)責(zé)線程切換控制,其時序如圖8狀態(tài)機(jī)所示.FSM正常情況下運(yùn)行在S0狀態(tài),當(dāng)TT表彈出表頭或者線程執(zhí)行tkend釋放控制時,FSM跳轉(zhuǎn)到S1狀態(tài);在S1狀態(tài),RPU會清空IF段、ID段和EX段,保存正在執(zhí)行線程的PC,并執(zhí)行WB段,這3個任務(wù)可并行完成,FSM在下個cpuClk上升沿跳轉(zhuǎn)到S2;在S2狀態(tài),RPU執(zhí)行MM段,執(zhí)行MM段與執(zhí)行WB段要串行完成,所以需要單獨一個cpuClk;至此,上個線程的上下文保存完畢;在S3狀態(tài),RPU執(zhí)行線程切換,更改PC Group和Regfile Group中的ID寄存器,隨后進(jìn)入S0運(yùn)行新線程.對TTI中并發(fā)管理指令的實現(xiàn),保證了RPU任務(wù)級的時間可預(yù)測屬性.

Fig.7 Structure of TT table圖7 TT表結(jié)構(gòu)

Fig.8 FSM of thread switching圖8 線程切換狀態(tài)機(jī)

RPU是一款指令級時間可預(yù)測和任務(wù)級時間可預(yù)測的實時處理器.它支持標(biāo)準(zhǔn)時鐘,是RTM的實例;以TTI為軟硬件接口,從指令集體系結(jié)構(gòu)層次為上層提供了時間語義;RPU的設(shè)計實現(xiàn)驗證了RTM和TTI的可行性.同時,RPU的時間觸發(fā)設(shè)計理念契合時間觸發(fā)通信協(xié)議,如TTP和Flex Ray等.將來,在分布式場景下,可以為RPU添加時間觸發(fā)通信協(xié)議接口,從而保證系統(tǒng)級時間可預(yù)測性.

4.3 時序結(jié)果

RPU的時間可預(yù)測性體現(xiàn)在其具有確定性的時序上,即TTI的指令在運(yùn)行時都具有時序確定性,圖9、圖10和圖11顯示了系統(tǒng)時間生成的時序、時間觸發(fā)操作指令執(zhí)行的時序和線程切換的時序.

圖9是Time Unit模塊中對標(biāo)準(zhǔn)時鐘管理的時序圖.為了清楚表示時序,圖中波浪部分隱去若干cpuClk周期.圖9中系統(tǒng)設(shè)置的時間粒度tg＝100,即系統(tǒng)時間的單位是100μs.可以看出,在標(biāo)為2的cpuClk,cnt與tg相等,在標(biāo)為3的cpuClk,ti從原來的2變成了3,與引理1、4.1節(jié)中的分析吻合.結(jié)合ti,ti_w和ti_data信號在標(biāo)為5和標(biāo)為6的cpuClk的變化可知setti指令功能正確.整體來說,標(biāo)準(zhǔn)時鐘產(chǎn)生系統(tǒng)時間ti的過程時序精確,抖動總是Tcpu＝40 ns.

Fig.9 Timing of Time Unit圖9 Time Unit時序

圖10顯示的是時間觸發(fā)操作指令的運(yùn)行時序,to信號表示當(dāng)前EX段有一條ttiat或ttoat指令;idex_r1表示該指令的觸發(fā)時間,to_stall表示是否因tio指令產(chǎn)生了流水線阻塞.從圖10可知,在標(biāo)為2的cpuClk一條tio指令進(jìn)入流水線,在EX段等待時間變?yōu)?0時時間觸發(fā)執(zhí)行;在標(biāo)為7的cpuClk,即ti到達(dá)20的下一個cpuClk周期開始執(zhí)行.時間觸發(fā)操作指令的執(zhí)行時序精確,抖動也是Tcpu＝40 ns.

Fig.10 Timing of time-triggered operation圖10 時間觸發(fā)操作指令時序

圖11則展示了線程切換時序,head_time表示TT表中下一個切換發(fā)生時間,curr_stat表示FSM的當(dāng)前狀態(tài),thread_control表示FSM提供給RPU的控制信號,ID表示PC中的ID寄存器.圖11和圖8所示的線程切換狀態(tài)機(jī)吻合,說明RPU的并發(fā)管理同樣cpuClk周期精確,時間可預(yù)測.

圖9、圖10和圖11體現(xiàn)了RPU的時序確定性,時序確定有利于建立RPU的確定性抽象模型,并據(jù)此進(jìn)行嚴(yán)謹(jǐn)?shù)男问交瘯r間行為分析,滿足硬實時安全性設(shè)計要求.

Fig.11 Timing of thread switching圖11 線程切換時序

4.4 資源消耗

RPU基于CV32E40P實現(xiàn).實現(xiàn)之前,本文對CV32E40P進(jìn)行了裁剪,刪去了如硬件循環(huán)等影響處理器時序的功能.裁剪后CV32E40P的資源消耗如表4所示.本文關(guān)注FPGA資源消耗3個重要指標(biāo):查找表(lookup table,LUT)、FF(flip-flop)和BRAM(block ram),但是CV32E40P未用到BRAM,因此沒有列出BRAM數(shù)據(jù).表5、表6測得RPU線程數(shù)為2,4,8,16,32時,TT表項大小為4,8,16,32,64時LUT和FF的消耗.

Table 4 Resource Consumption Table of Modified CV32E40P表4 裁剪后CV32E40P的資源消耗表

Table 5 LUT Consumption Table of RPU表5 RPU LUT消耗表

Table 6 FF Consumption Table of RPU表6 RPU FF消耗表

從表5和表6可以看出,RPU的實現(xiàn)會增加LUT和FF資源的使用,FF的額外消耗多于LUT的額外消耗,這是由于RPU會更多地使用寄存器導(dǎo)致的.另外,LUT和FF的資源消耗隨著線程數(shù)大小的增長(表的每一列)和TT表大小的增長(表的每一行)線性增長.其中,資源消耗隨線程數(shù)的增加增長迅速,隨TT表大小的增加增長緩慢,符合設(shè)計時的預(yù)期.

5 LET應(yīng)用示例

本節(jié)首先對LET模型和LET模型的3種實現(xiàn)語義進(jìn)行簡單介紹,進(jìn)而給出根據(jù)其中的交錯LET實現(xiàn)方案使用TTI對RPU編程的應(yīng)用實例.

5.1 LET模型介紹

Henzinger和Kirsch等人借鑒ZET和BET模型各自的優(yōu)點,提出LET模型[7].采用LET模型時,任務(wù)總是在其激活區(qū)間的開始處讀數(shù)據(jù)和結(jié)束處寫數(shù)據(jù),使其可觀察的時序行為獨立于任務(wù)的物理執(zhí)行.LET確定了讀程序輸入到寫程序輸出之間所需的時間,而不考慮執(zhí)行程序所需的時間,具有平臺可移植性.雖然實際應(yīng)用時LET模型的資源(緩存、時間)利用率較低,但LET為控制工程師和軟件工程師提供了清晰的時序模型接口.2017年以來,隨著多核平臺下可預(yù)測性成為關(guān)鍵問題,工業(yè)界認(rèn)為LET對于解決多核混合安全關(guān)鍵應(yīng)用和分布式實時系統(tǒng)的通信確定性問題極具吸引力.

LET編程模型將任務(wù)的邏輯行為“輸入 計算-輸出”過程相分離,如圖12所示,定義了嚴(yán)格的輸入輸出時刻,要求在指定時刻輸入,在輸出時刻之前計算出結(jié)果,并能夠?qū)⑤敵鼋Y(jié)果保持到指定時刻輸出,具有時間行為可預(yù)測、可組合和平臺無關(guān)性等重要特征,利于設(shè)計時進(jìn)行系統(tǒng)行為驗證.

Fig.12 LET programming model圖12 LET編程模型

LET抽象中輸入和輸出都是零執(zhí)行時間的,然而現(xiàn)實中輸入和輸出操作需要一定的執(zhí)行時間,因此,在實踐中要盡量滿足LET模型零執(zhí)行時間的假設(shè).在考慮系統(tǒng)端到端延遲的情況下,LET模型主要可以分為3種實現(xiàn)語義[36],如圖13所示.

Fig.13 Example schedule of three semantics of LET implementation圖13 LET模型3種實現(xiàn)語義

圖13(a)和圖13(b)中P任務(wù)的周期為C任務(wù)的2倍,圖13(c)中P任務(wù)和C任務(wù)同周期.圖13(a)顯示的是LET的Giotto語義,它按照輸入輸出任務(wù)塊的因果關(guān)系確定執(zhí)行順序.圖13(b)顯示的是LET的交錯通信語義,在LET通信階段,每個任務(wù)的輸入輸出操作被合并為一組任務(wù),不同的任務(wù)組交錯執(zhí)行.基于任務(wù)鏈的LET語義可以在特定情況下優(yōu)化不可觀測事件的通信,降低通信開銷,優(yōu)化任務(wù)鏈的端到端延遲.圖13(c)顯示的是LET的Giotto語義和基于任務(wù)鏈的LET語義的對比,其上半部分是按照Giotto語義執(zhí)行的結(jié)果,下半部分是按照基于任務(wù)鏈的LET語義執(zhí)行的結(jié)果.從圖13中可以看出,基于任務(wù)鏈的LET語義具有更低的邏輯端到端延遲.

5.2 RPU對LET的支持示例

本節(jié)通過示例RPU對邏輯執(zhí)行時間模型的支持,說明RPU的應(yīng)用能力,提供時間可預(yù)測的實時應(yīng)用開發(fā)平臺.

本節(jié)使用的示例說明在自動駕駛中,假設(shè)有:

1)采集任務(wù),負(fù)責(zé)通過傳感器采集數(shù)據(jù),并進(jìn)行數(shù)據(jù)預(yù)處理,周期為2 ms;

2)分析任務(wù),對預(yù)處理之后的數(shù)據(jù)進(jìn)行預(yù)定算法的分析和處理,得到響應(yīng)數(shù)據(jù),周期為1 ms,WCET為0.25 ms;

3)執(zhí)行任務(wù),將響應(yīng)數(shù)據(jù)分發(fā)到執(zhí)行器進(jìn)行外部環(huán)境的控制,周期為2 ms,WCET為0.5 ms.

3個任務(wù)的數(shù)據(jù)依賴圖如圖14所示:

Fig.14 Data dependency graph of sample tasks圖14 示例任務(wù)的數(shù)據(jù)依賴圖

本文按照交錯LET的語義對示例任務(wù)集進(jìn)行編程,采用共享內(nèi)存進(jìn)行通信.圖15顯示了該任務(wù)集的任務(wù)分解和建模時序,圖14中的數(shù)據(jù)依賴體現(xiàn)為圖15中的虛線箭頭.其中,每個LET任務(wù)被分解為I,C,O三個子任務(wù),O和I兩個子任務(wù)被合并為一個OI子任務(wù)組,保證了該任務(wù)集的交錯LET語義,顯示出圖15所示時序.

Fig.15 Interleaved LET implementation圖15 交錯LET語義實現(xiàn)方案

圖15中OI子任務(wù)組在RPU上會執(zhí)行0.05 ms.圖16是使用TTI在擁有4線程的RPU上實現(xiàn)圖15所示時序的偽代碼.TT表在時間觸發(fā)地執(zhí)行線程切換時會彈出表頭項,對于圖15中以2 ms為周期的運(yùn)行系統(tǒng),需要一個額外任務(wù)負(fù)責(zé)向調(diào)度表添加每個周期的調(diào)度表項.圖16的代碼中,使用0號線程管理調(diào)度表;使用1號線程執(zhí)行各個任務(wù)的OI子任務(wù)組;使用2號線程執(zhí)行各個任務(wù)的C子任務(wù);使用3號線程執(zhí)行軟實時任務(wù),即當(dāng)硬實時任務(wù)執(zhí)行完,RPU處于空閑狀態(tài)時,會切換到3號線程執(zhí)行.結(jié)合4.2節(jié)展現(xiàn)的時序可知,圖16所示的代碼保證了圖15的交錯LET語義.

Fig.16 Example of LET implementation圖16 LET實現(xiàn)示例

6 總 結(jié)

由于現(xiàn)代計算機(jī)體系結(jié)構(gòu)不顯式地提供時間語義支持,實時嵌入式系統(tǒng)設(shè)計只能依賴定時器的時鐘中斷進(jìn)行時序控制,導(dǎo)致程序時間行為難以預(yù)測,且驗證困難,平臺依賴性高.

本文嘗試重新定義支持實時計算的處理器體系結(jié)構(gòu)和指令集,使程序員可以準(zhǔn)確描述任務(wù)、動作和操作的確定性時間行為語義,以滿足實時系統(tǒng)設(shè)計時域控制與值域控制相分離,時序行為可預(yù)測、可組合,且平臺無關(guān)等時間關(guān)鍵性要求.

實時處理器RPU基于RTM模型和TTI指令集,實驗表明其具備良好的實際應(yīng)用前景.未來,我們將進(jìn)一步完善所提出的實時處理器模型,并研究據(jù)此進(jìn)行實時系統(tǒng)時間安全屬性形式化推理和檢查的方法.同時,我們也將進(jìn)一步豐富RPU提供的實時服務(wù),更好地支持實時編程模型.