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

汪 超 陳香蘭 章 博 李 曦 王 超 周學海

(中國科學技術大學計算機科學與技術學院 合肥 230027)

(wcwxy＠mail.ustc.edu.cn)

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

為了保證RTES系統的時間行為正確,要求其軟硬件系統具有時序確定性和可預測性[1].然而,現代計算機系統的體系結構、運行時環境、編程語言等各個抽象層次均缺乏精確的時間語義和表達時序屬性的顯式結構,使得系統設計者只能采用編程抽象之外的手段(如定時中斷)進行時序控制,導致控制和驗證程序的時序屬性或處理時序沖突十分困難,并且任何軟硬件改動都將對系統時序造成不可預測的影響,甚至不得不重新進行系統設計.尤為重要的是,由于上述機制內在的異步不確定性,難以建立系統的確定性抽象模型,并據此進行嚴謹的形式化時間行為分析,無法滿足硬實時安全性設計要求.

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

ISA層的基礎設施缺乏時間語義已經成為安全關鍵實時系統設計方法學的一個基礎性問題,需要重新考慮實時處理器的ISA和微體系結構組織.

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

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

本文的主要貢獻包括3個方面:

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

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

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

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

1 相關工作

本節對當前實時計算設計方法、時間屬性和行為建模、實時處理器設計3個方面的研究工作進行梳理.

1.1 實時計算設計方法

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

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

1.2 時間屬性和行為建模

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

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

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

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

時間自動機理論和時間觸發自動機理論對時間語義指令集的設計具有重要的指導意義,是研究時間語義完備性理論的重要參考.

1.3 實時處理器設計

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

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

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

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

2 背景知識

本節介紹具有時序確定性的系統構建范式時間觸發范式以及按照時間觸發范式構建的計算理論時間觸發自動機,介紹時間模型的分類.后文定義時間模型,參考時間觸發自動機理論設計了最小時間語義指令集TTI,并以時間觸發范式實現了實時處理器RPU.

2.1 時間觸發范式

事件觸發范式和時間觸發范式是2種截然不同的系統設計范式,本節參考文獻[13],對2種范式進行介紹.2種系統設計范式的核心區別是:在事件觸發系統(event-triggered systems,ET系統)中,重大事件的發生導致了響應活動的啟動;在時間觸發系統(time-triggered systems,TT系統)中,響應活動是在預定的時間點實時啟動的.

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

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

2.2 時間觸發自動機

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

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

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

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

2)S是有限狀態集合;

3)s0∈S是初始狀態;

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

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

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

其中,使用示不超過n的最大正整數.定義2中的第3條規則確保轉移的發生不會導致有整數時間點被跳過.

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

Fig.1 An example of time-triggered automaton圖1 時間觸發自動機示例

2.3 時間模型

時間模型是實時系統的理論核心,從時間線的構成、時間步進規則和事件觀測方法等3個方面刻畫和定義系統的時間行為.本文參考文獻[32],對描述時間模型3個方面的維度進行說明.

描述時間模型中時間線構成的維度有:

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

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

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

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

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

描述時間模型中時間步進規則的維度有:

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

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

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

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

另外,在分布式的場景下,時間有全局的或者是局部的之分.全局時間是指所有節點統一同步后產生的時間;局部時間是指每個節點內自己使用的時間.

3 實時機模型

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

3.1 實時機模型RTM

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

定義3.RTM機.RTM機對馮·諾依曼機進行擴充,如圖2所示:

Fig.2 RTM machine architecture圖2 RTM機結構模型

1)計算機系統由運算器、控制器、存儲器、標準時鐘和I/O設備等功能部件構成.

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

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

由于各個硬件平臺的時鐘設備不同,即使程序具有相同的時間語義,也無法得到相同的時間行為.RTM機引入標準時鐘,并據此定義其指令的時間語義,使具有時間語義的程序得到同一時間模型的支持,實現了程序的I/O時序行為物理平臺無關性.

定義4.RTM機時間模型.RTM機的時間模型定義為:

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

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

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

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

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

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

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

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

RTM機以“關注分離(separation of concerns)”和“構建正確(correct-by-construction)”為設計原則,區分邏輯控制與時域控制,為實現從時序可預測設計到時序確定性設計轉變奠定了理論基礎,利于實時程序代碼自動生成和化簡實時系統驗證的復雜度.

3.2 標準時鐘stdClk

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

定義5.標準時鐘stdClk.RTM機的標準時鐘std Clk是基于實時間域的物理時鐘,用于實時程序的時間行為控制.

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

基于標準時鐘stdClk,RTM機實時程序的邏輯執行與其時域控制具有確定性的松弛同步時序關系,如定理1,可以實現周期精確的系統時序行為.

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

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

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

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

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

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

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

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

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

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

Fig.3 Timing of using stdClk for controlling圖3 標準時鐘的控制時序

實時系統技術往往應用在分布式場景下.而RTM系統的時間行為基于標準時鐘,與運行平臺無關,故在實時分布式場景中應用RTM,只需要對標準時鐘進行同步.

根據標準時鐘提供的定時,設計帶有時間語義的指令集作為實時處理器軟硬件接口,可以提供at,delay-until和timestamp等控制時間行為的指令,支持邏輯執行時間模型和時間觸發等應用模式.

3.3 時間語義指令集TTI

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

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

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

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

2)時間觸發操作指令.ttiat/ttoat指令用于在指定時刻對I/O端口進行輸入/輸出;ttiat/ttoat指令的執行代表系統與外部環境的交互事件,會設置時間戳寄存器ts.

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

4)任務并發管理指令.tkend指令用于標志當前線程中任務的截止;addtk指令用于向硬件時間觸發調度表添加表項,即通過addtk指令設置好靜態的時間觸發調度表.

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

Fig.4 Example of translating TTA to TTI program圖4 TTA轉換為TTI程序示例

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

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

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

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

4 實時處理單元

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

4.1 RISC-V TTI

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

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

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

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

4.2 RPU的設計

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

圖5中的Decode模塊增加了對RISC-V TTI指令的譯碼,Control模塊增加了相應的控制.圖5中的Time Unit模塊負責管理std Clk,產生系統時間,如圖6所示.時間粒度寄存器保存通過settg指令設置的時間粒度;cnt寄存器直接接收標準時鐘進行自增,當cnt寄存器增長到與tg寄存器相等的時候,表示系統時間的時間寄存器ti自增;ti寄存器也可通過setti指令進行設置,通過getti指令進行讀取.

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

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

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

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

Fig.7 Structure of TT table圖7 TT表結構

Fig.8 FSM of thread switching圖8 線程切換狀態機

RPU是一款指令級時間可預測和任務級時間可預測的實時處理器.它支持標準時鐘,是RTM的實例;以TTI為軟硬件接口,從指令集體系結構層次為上層提供了時間語義;RPU的設計實現驗證了RTM和TTI的可行性.同時,RPU的時間觸發設計理念契合時間觸發通信協議,如TTP和Flex Ray等.將來,在分布式場景下,可以為RPU添加時間觸發通信協議接口,從而保證系統級時間可預測性.

4.3 時序結果

RPU的時間可預測性體現在其具有確定性的時序上,即TTI的指令在運行時都具有時序確定性,圖9、圖10和圖11顯示了系統時間生成的時序、時間觸發操作指令執行的時序和線程切換的時序.

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

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

圖10顯示的是時間觸發操作指令的運行時序,to信號表示當前EX段有一條ttiat或ttoat指令;idex_r1表示該指令的觸發時間,to_stall表示是否因tio指令產生了流水線阻塞.從圖10可知,在標為2的cpuClk一條tio指令進入流水線,在EX段等待時間變為20時時間觸發執行;在標為7的cpuClk,即ti到達20的下一個cpuClk周期開始執行.時間觸發操作指令的執行時序精確,抖動也是Tcpu＝40 ns.

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

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

圖9、圖10和圖11體現了RPU的時序確定性,時序確定有利于建立RPU的確定性抽象模型,并據此進行嚴謹的形式化時間行為分析,滿足硬實時安全性設計要求.

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

4.4 資源消耗

RPU基于CV32E40P實現.實現之前,本文對CV32E40P進行了裁剪,刪去了如硬件循環等影響處理器時序的功能.裁剪后CV32E40P的資源消耗如表4所示.本文關注FPGA資源消耗3個重要指標:查找表(lookup table,LUT)、FF(flip-flop)和BRAM(block ram),但是CV32E40P未用到BRAM,因此沒有列出BRAM數據.表5、表6測得RPU線程數為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的實現會增加LUT和FF資源的使用,FF的額外消耗多于LUT的額外消耗,這是由于RPU會更多地使用寄存器導致的.另外,LUT和FF的資源消耗隨著線程數大小的增長(表的每一列)和TT表大小的增長(表的每一行)線性增長.其中,資源消耗隨線程數的增加增長迅速,隨TT表大小的增加增長緩慢,符合設計時的預期.

5 LET應用示例

本節首先對LET模型和LET模型的3種實現語義進行簡單介紹,進而給出根據其中的交錯LET實現方案使用TTI對RPU編程的應用實例.

5.1 LET模型介紹

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

LET編程模型將任務的邏輯行為“輸入 計算-輸出”過程相分離,如圖12所示,定義了嚴格的輸入輸出時刻,要求在指定時刻輸入,在輸出時刻之前計算出結果,并能夠將輸出結果保持到指定時刻輸出,具有時間行為可預測、可組合和平臺無關性等重要特征,利于設計時進行系統行為驗證.

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

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

Fig.13 Example schedule of three semantics of LET implementation圖13 LET模型3種實現語義

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

5.2 RPU對LET的支持示例

本節通過示例RPU對邏輯執行時間模型的支持,說明RPU的應用能力,提供時間可預測的實時應用開發平臺.

本節使用的示例說明在自動駕駛中,假設有:

1)采集任務,負責通過傳感器采集數據,并進行數據預處理,周期為2 ms;

2)分析任務,對預處理之后的數據進行預定算法的分析和處理,得到響應數據,周期為1 ms,WCET為0.25 ms;

3)執行任務,將響應數據分發到執行器進行外部環境的控制,周期為2 ms,WCET為0.5 ms.

3個任務的數據依賴圖如圖14所示:

Fig.14 Data dependency graph of sample tasks圖14 示例任務的數據依賴圖

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

Fig.15 Interleaved LET implementation圖15 交錯LET語義實現方案

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

Fig.16 Example of LET implementation圖16 LET實現示例

6 總 結

由于現代計算機體系結構不顯式地提供時間語義支持,實時嵌入式系統設計只能依賴定時器的時鐘中斷進行時序控制,導致程序時間行為難以預測,且驗證困難,平臺依賴性高.

本文嘗試重新定義支持實時計算的處理器體系結構和指令集,使程序員可以準確描述任務、動作和操作的確定性時間行為語義,以滿足實時系統設計時域控制與值域控制相分離,時序行為可預測、可組合,且平臺無關等時間關鍵性要求.

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