信息物理融合系統(tǒng)WCET分析工具與挑戰(zhàn)

文/羅韶杰 張立臣

1 信息物理融合系統(tǒng)WCET相關(guān)概念

信息物理系統(tǒng)是這樣一類系統(tǒng)：其通過集成先進(jìn)的感知、計(jì)算、通信和控制等信息技術(shù)以及自動(dòng)化控制技術(shù)，構(gòu)建了物理世界與信息世界中人、機(jī)、物、環(huán)境和信息等因素通過高效協(xié)同適時(shí)交互以達(dá)到相互映射的復(fù)雜系統(tǒng)，其實(shí)現(xiàn)了系統(tǒng)里面資源自動(dòng)配置和運(yùn)行的三個(gè)需求：按需響應(yīng)、快速迭代和動(dòng)態(tài)優(yōu)化。信息物理融合系統(tǒng)具有實(shí)時(shí)的特性和需求，所以其調(diào)度需要以任務(wù)的WCET作為輸入之一，因此WCET分析是CPS任務(wù)調(diào)度的基礎(chǔ)之一。

一個(gè)任務(wù)的最壞執(zhí)行時(shí)間指的是此任務(wù)在特定的硬件平臺(tái)上去執(zhí)行所需要的時(shí)間長(zhǎng)度的最大值。最壞執(zhí)行時(shí)間的分析是具有實(shí)時(shí)性要求的系統(tǒng)的調(diào)度分析中最重要的事情之一。實(shí)時(shí)計(jì)算的主要特征是在給定時(shí)間內(nèi)或在給定期限內(nèi)完成計(jì)算的要求。計(jì)算或執(zhí)行時(shí)間通常在某種程度上取決于輸入數(shù)據(jù)和其他可變條件。然后重要的是找到最壞情況下的執(zhí)行時(shí)間（WCET）并驗(yàn)證它足夠短以滿足所有情況下的截止期限。

2 WCET分析的類別

WCET 分析可以分成靜態(tài)分析、動(dòng)態(tài)測(cè)量和混合方法共3 類方法。動(dòng)態(tài)測(cè)量方法指的是直接在目標(biāo)環(huán)境中運(yùn)行程序，通過盡可能多的測(cè)試用例來得出程序的WCET。因此其測(cè)量工具有模擬器、邏輯分析儀和示波器等，主要應(yīng)用在工業(yè)上。靜態(tài)分析方法則通過抓取和分析程序代碼，綜合程序所有可能的輸入，系統(tǒng)運(yùn)行狀態(tài)和軟硬件間平臺(tái)及交互的前提下，對(duì)軟硬件進(jìn)行建模分析以確定其最壞執(zhí)行時(shí)間，而無需真實(shí)地運(yùn)行程序。靜態(tài)分析首先進(jìn)行代碼的高層分析和結(jié)合硬件的低層分析，然后通過3種方法之一求解WCET，分別是基于路徑的、基于隱藏路徑的和基于語(yǔ)法樹的分析方法?；旌戏椒ㄖ傅氖墙Y(jié)合靜態(tài)分析和動(dòng)態(tài)測(cè)量?jī)煞N方法，綜合考慮并求解WCET的方法。

3 WCET分析的工具

現(xiàn)有的一些工具使用的是程序的純靜態(tài)分析；而其他的另一些工具將靜態(tài)分析與程序部分執(zhí)行時(shí)間的動(dòng)態(tài)測(cè)量相結(jié)合，即使用的是混合方法。下面列舉幾種常用的工具，除此之外還有OTAWA、MTime、TuBound等工具。

3.1 aiT

AbsInt的aiT是一個(gè)時(shí)間驗(yàn)證工具。采用靜態(tài)WCET分析用于計(jì)算任務(wù)實(shí)際WCET的安全上限。它的目標(biāo)處理器范圍較為廣，從簡(jiǎn)單的體系結(jié)構(gòu)到較為復(fù)雜的體系結(jié)構(gòu)都有。aiT的主要輸入是二進(jìn)制可執(zhí)行文件，從中重構(gòu)控制流程圖。在這個(gè)圖上，進(jìn)行了幾個(gè)靜態(tài)分析來計(jì)算每個(gè)指令的執(zhí)行時(shí)間。然后使用全局路徑分析來計(jì)算任務(wù)的整體WCET界限。然后將分析結(jié)果可視化給用戶。

3.2 Bound-T

Bound-T是芬蘭航天中心為歐洲航天協(xié)會(huì)開發(fā)的一個(gè)WCET分析工具，其由Tidorum Ltd.公司進(jìn)行商業(yè)分銷和支持，基于可執(zhí)行代碼進(jìn)行靜態(tài)WCET 分析，因?yàn)锽ound-T是通過從可執(zhí)行文件中提取和解碼二進(jìn)制指令來構(gòu)造控制流和調(diào)用圖，所以其分析過程是獨(dú)立于程序的源代碼的，因此可以對(duì)不同的語(yǔ)言開發(fā)的程序進(jìn)行WCET 分析。Bound-T專注于具有可預(yù)測(cè)時(shí)序的微控制器。不考慮高速緩存和其他具有非常動(dòng)態(tài)性的硬件組件。

4 WCET分析面臨的挑戰(zhàn)

WCET的動(dòng)態(tài)測(cè)量方法由于其用例范圍可能是無限的，無法完全覆蓋到，因此使用這種方法得出來的分析值可能會(huì)低于真實(shí)的WCET值，若使用這種小于真實(shí)WCET的值來分配時(shí)間給實(shí)時(shí)任務(wù)，可能會(huì)造成任務(wù)無法按時(shí)完成從而導(dǎo)致不可預(yù)料的后果。

在靜態(tài)分析WCET方面，與大多數(shù)程序分析應(yīng)用程序不同，WCET工具必須分析機(jī)器代碼，而不僅僅是源代碼。這意味著分析依賴于目標(biāo)處理器，因此WCET工具通常會(huì)有幾個(gè)不同的版本，每個(gè)版本分別對(duì)應(yīng)著每個(gè)支持的目標(biāo)處理器甚至每個(gè)具有特定緩存和內(nèi)存接口的目標(biāo)系統(tǒng)。機(jī)器代碼分析的某些部分也可能依賴于生成機(jī)器代碼的編譯器。例如，switch case語(yǔ)句中的控制流分析可能對(duì)編譯器通過地址表使用跳轉(zhuǎn)的慣用方法很敏感。然而現(xiàn)在處理器和編譯器的種類繁多，內(nèi)部的技術(shù)也不盡相同，導(dǎo)致現(xiàn)有的WCET分析工具無法全部或廣泛顧及到。

通常，WCET工具使用簡(jiǎn)化近似值，從而確定WCET的上限，而非真正的WCET。真正的WCET和所求得的上限之間的差異，在某些情況下可能比較大，即估算的WCET精確度在某些情況下可能較低，導(dǎo)致分配給任務(wù)的時(shí)間和臨界資源可能會(huì)過多，而造成較大的時(shí)空資源的浪費(fèi)。對(duì)于大多數(shù)真實(shí)的、非平凡的程序來說，完全自動(dòng)的WCET分析是不可能的，這意味著仍然需要手動(dòng)注釋或斷言來定義諸如循環(huán)迭代邊界之類的基本信息。對(duì)此類注釋的需求以及注釋的編寫形式取決于WCET工具和要分析的目標(biāo)程序。

5 結(jié)束語(yǔ)

自21世紀(jì)以來，世界上的信息化水平越來越高，越來越普及，并滲透進(jìn)了物理世界。物理世界和信息世界早已不是互相獨(dú)立的個(gè)體了，信息物理融合系統(tǒng)就是一個(gè)印證，信息物理融合系統(tǒng)廣泛應(yīng)用于智能電網(wǎng)、車聯(lián)網(wǎng)和自動(dòng)駕駛等和我們生活息息相關(guān)的諸多領(lǐng)域，WCET分析作為CPS的重要基礎(chǔ)技術(shù)之一，其發(fā)展?fàn)縿?dòng)著CPS。

WCET分析領(lǐng)域發(fā)展了二三十年，取得了一些成果，但也存在著很多不足，面臨著很多挑戰(zhàn)，因此需要更多的相關(guān)領(lǐng)域人員參與其研究，結(jié)合高速發(fā)展的現(xiàn)代科學(xué)技術(shù)，推進(jìn)WCET的進(jìn)一步發(fā)展，使其更好地造福CPS和更多的領(lǐng)域。