陳芳園，丁亞軍,張冬松,吳 飛,任秀江

(1.江南計(jì)算技術(shù)研究所,江蘇 無錫 214083;2.中國人民解放軍鎮(zhèn)江船艇學(xué)院,江蘇 鎮(zhèn)江 212000;3.上海工程技術(shù)大學(xué)電子電氣工程學(xué)院,上海 201620)

面向WCET分析的實(shí)時(shí)多核體系結(jié)構(gòu)研究

陳芳園1，丁亞軍1,張冬松2,吳 飛3,任秀江1

(1.江南計(jì)算技術(shù)研究所,江蘇 無錫 214083;2.中國人民解放軍鎮(zhèn)江船艇學(xué)院,江蘇 鎮(zhèn)江 212000;3.上海工程技術(shù)大學(xué)電子電氣工程學(xué)院,上海 201620)

隨著工藝技術(shù)的發(fā)展以及嵌入式實(shí)時(shí)應(yīng)用范圍的不斷擴(kuò)大和需求的不斷提升，多核處理器必將憑其高性能和低功耗特性應(yīng)用到嵌入式實(shí)時(shí)領(lǐng)域中。但是，多核處理器體系結(jié)構(gòu)很難甚至無法滿足實(shí)時(shí)系統(tǒng)的實(shí)時(shí)限制和對(duì)WCET的可預(yù)測(cè)性要求。從多核中的共享資源入手，分析多核中的片上共享資源(共享Cache、片上互連)和片外共享資源(片外存儲(chǔ))對(duì)WCET分析的影響，探討了各種干擾下的WCET分析方法。介紹了兩種多核WCET分析模型：多核靜態(tài)WCET分析模型和多核混合WCET分析模型；同時(shí)，針對(duì)嵌入式實(shí)時(shí)應(yīng)用提出了多核設(shè)計(jì)原則。

多核體系結(jié)構(gòu)；嵌入式實(shí)時(shí)系統(tǒng)；實(shí)時(shí)任務(wù)；WCET

1 引言

現(xiàn)實(shí)世界的實(shí)際需求促進(jìn)了實(shí)時(shí)系統(tǒng)的產(chǎn)生和發(fā)展，隨著電子技術(shù)和計(jì)算機(jī)技術(shù)的飛速發(fā)展，實(shí)時(shí)系統(tǒng)的應(yīng)用范圍也在不斷擴(kuò)大，如汽車、航空、遠(yuǎn)程通訊、空間系統(tǒng)、醫(yī)療圖像和消費(fèi)類電子設(shè)備等。這些領(lǐng)域的發(fā)展迫切需要提供性能更強(qiáng)大、操作更靈活、效能比更高的微處理器系統(tǒng)，以滿足實(shí)時(shí)應(yīng)用的需求。而當(dāng)今處理器市場(chǎng)中的片上多核處理器[1]已以其強(qiáng)大的優(yōu)勢(shì)成為主流，其多核結(jié)構(gòu)也必將應(yīng)用到嵌入式實(shí)時(shí)系統(tǒng)，以滿足實(shí)時(shí)系統(tǒng)日益增長(zhǎng)的需求。當(dāng)前，高端嵌入式應(yīng)用正朝著多核處理器平臺(tái)的方向不斷發(fā)展[2]。例如，ARM11 MPCore[3]已經(jīng)完成多核實(shí)現(xiàn)，包括8段流水線、Cache和動(dòng)態(tài)分支預(yù)測(cè)等；IBM/Sony/Toshiba Cell體系結(jié)構(gòu)[1, 4]也被應(yīng)用于高性能嵌入式多核處理器中?？梢灶A(yù)見，隨著技術(shù)的發(fā)展和應(yīng)用需求的增加，多核處理器也必將進(jìn)入到嵌入式實(shí)時(shí)領(lǐng)域中，以促進(jìn)嵌入式實(shí)時(shí)應(yīng)用的大力發(fā)展。

盡管多核處理器可以為嵌入式系統(tǒng)帶來諸多好處，但目前多核處理器卻很難甚至不能應(yīng)用于嵌入式實(shí)時(shí)系統(tǒng)中。這是因?yàn)閷?shí)時(shí)系統(tǒng)必須保證任務(wù)滿足時(shí)間限制，也就是說，實(shí)時(shí)系統(tǒng)的正確性不僅僅體現(xiàn)在程序執(zhí)行的結(jié)果，還體現(xiàn)在任務(wù)的執(zhí)行時(shí)間不能超過截止期的要求。其任務(wù)的執(zhí)行如果不能滿足對(duì)截止時(shí)間的要求，會(huì)降低系統(tǒng)服務(wù)的級(jí)別，甚至造成系統(tǒng)崩潰。因此，獲得任務(wù)安全、準(zhǔn)確的最壞情況執(zhí)行時(shí)間WCET(Worst Case Execution Time)是至關(guān)重要的。通常研究者可以使用靜態(tài)分析方法和基于測(cè)量的方法來計(jì)算WCET。但是，這些方法的精確性和有效性高度依賴于實(shí)際處理器平臺(tái)的可預(yù)測(cè)性，也就是說，處理器體系結(jié)構(gòu)決定了這些方法的實(shí)際可行性以及結(jié)果的精確性。研究表明，工業(yè)界仍在使用的WCET分析方法對(duì)于復(fù)雜的處理器結(jié)構(gòu)，例如多核處理器體系結(jié)構(gòu)，不再適用。這種對(duì)處理器體系結(jié)構(gòu)的高度依賴性引起了設(shè)計(jì)者對(duì)WCET分析的關(guān)注。

事先獲知任務(wù)的WCET估值是實(shí)時(shí)系統(tǒng)調(diào)度及可調(diào)度性分析的前提，也是檢查實(shí)時(shí)系統(tǒng)的性能是否滿足要求的依據(jù)。研究者已經(jīng)對(duì)WCET分析深入研究了幾十年[5]，然而，這些研究都假設(shè)每個(gè)任務(wù)的WCET是可確定的，然后基于WCET進(jìn)行全局的調(diào)度分析[6]。這種方法對(duì)于單核處理器系統(tǒng)和傳統(tǒng)的具有獨(dú)立存儲(chǔ)的多處理器來說是有效的。隨著處理器體系結(jié)構(gòu)的發(fā)展，研究者開始考慮Cache、流水線和分支預(yù)測(cè)對(duì)單個(gè)任務(wù)執(zhí)行時(shí)間的影響[7,8]。然而，此時(shí)的WCET分析仍然假設(shè)任務(wù)是獨(dú)立的，不會(huì)產(chǎn)生相關(guān)性或資源共享。文獻(xiàn)[9,10]也只考慮了單核結(jié)構(gòu)中任務(wù)搶占引起的Cache效果。隨著復(fù)雜的多核體系結(jié)構(gòu)的出現(xiàn)以及多核在嵌入式實(shí)時(shí)中應(yīng)用的必然趨勢(shì)，嵌入式實(shí)時(shí)系統(tǒng)的WCET的分析變得越來越復(fù)雜，無法再保證WCET的可確定性。在當(dāng)前的具有共享資源的多核結(jié)構(gòu)中，例如對(duì)共享的、復(fù)雜存儲(chǔ)結(jié)構(gòu)的訪問，每個(gè)任務(wù)的WCET取決于全局系統(tǒng)調(diào)度，任務(wù)之間對(duì)共享資源的干擾給時(shí)序分析提出了挑戰(zhàn)，以往傳統(tǒng)的WCET分析將不再適用于多核結(jié)構(gòu)。

多核的片上共享資源和片外共享資源的處理方式對(duì)時(shí)間的可預(yù)測(cè)性有著重要的影響，例如共享二級(jí)Cache、片上互連、片外存儲(chǔ)等，這些硬件共享資源使得實(shí)時(shí)系統(tǒng)中的WCET分析越來越復(fù)雜，隨著多核處理器在嵌入式實(shí)時(shí)應(yīng)用領(lǐng)域中的應(yīng)用越來越廣泛，這個(gè)問題亟待解決。

2 實(shí)時(shí)多核體系結(jié)構(gòu)中Cache敏感的WCET分析

處理器和主存儲(chǔ)器間的速度差距對(duì)多核而言是一個(gè)突出的矛盾，為了緩解訪存性能瓶頸，多核處理器通常設(shè)置包括Cache和局部存儲(chǔ)器等在內(nèi)的多級(jí)存儲(chǔ)層次。但是，在多核處理器中內(nèi)核共享Cache等存儲(chǔ)資源，對(duì)于嵌入式實(shí)時(shí)系統(tǒng)而言，對(duì)這些資源的共享和競(jìng)爭(zhēng)除了會(huì)進(jìn)一步影響到處理器性能的提高外，多核中并行任務(wù)在共享存儲(chǔ)上的競(jìng)爭(zhēng)還會(huì)導(dǎo)致任務(wù)間的干擾，這種干擾使得多核系統(tǒng)的時(shí)序可預(yù)測(cè)性變得更加復(fù)雜。

在多核結(jié)構(gòu)中，運(yùn)行在一個(gè)核上的任務(wù)可能會(huì)破壞二級(jí)Cache中的一些數(shù)據(jù)，而這些數(shù)據(jù)正是運(yùn)行在另一個(gè)核上的任務(wù)所需要的。因此，在多核結(jié)構(gòu)中，任務(wù)的最壞情況執(zhí)行時(shí)間不能與其他任務(wù)分離開孤立地進(jìn)行估計(jì)，這一點(diǎn)與單核處理器系統(tǒng)截然不同。從本質(zhì)上講，多核面臨的挑戰(zhàn)是模擬和預(yù)測(cè)運(yùn)行在不同核上的并行程序的Cache行為(這不同于單核處理器系統(tǒng)中的順序程序)，實(shí)時(shí)多核系統(tǒng)中WCET估計(jì)的最大問題就是如何預(yù)測(cè)Cache行為。因此，任務(wù)的WCET不能再與其他任務(wù)分離開獨(dú)立地進(jìn)行分析，無法利用單核針對(duì)Cache的WCET分析方法。

目前還很少有研究考慮多核平臺(tái)中的WCET分析。在多核結(jié)構(gòu)中，有一些任務(wù)在執(zhí)行時(shí)會(huì)產(chǎn)生大量的存儲(chǔ)到二級(jí)Cache的訪問，如果在調(diào)度時(shí)減少這種線程的同時(shí)調(diào)度，則可以降低二級(jí)Cache競(jìng)爭(zhēng)[11]。Anderson J H等人[12,13]使用這種策略來提高Cache性能，以滿足實(shí)時(shí)限制。這些工作假設(shè)實(shí)時(shí)線程的WCET事先已知。然而，事實(shí)上盡管提高Cache性能可以直接降低平均執(zhí)行代價(jià)，但是在這些系統(tǒng)模型中仍然很難獲得每個(gè)實(shí)時(shí)線程的WCET。

WCET領(lǐng)域的研究者認(rèn)為，在共享Cache的多核結(jié)構(gòu)中，設(shè)計(jì)一個(gè)可以精確捕捉多核競(jìng)爭(zhēng)的分析方法非常困難。當(dāng)前，只有文獻(xiàn)[14～16]研究了共享Cache的多核中的WCET。

文獻(xiàn)[14]為了避免多核中由二級(jí)Cache引起的干擾問題，利用page-coloring技術(shù)以及調(diào)度策略將Cache進(jìn)行了劃分，該研究將并行運(yùn)行的硬實(shí)時(shí)任務(wù)的Cache分離開來，從而消除了任務(wù)間的干擾。文獻(xiàn)[15]基于共享Cache的多核平臺(tái)分析了線程間的Cache沖突，探討了共享二級(jí)Cache的多核結(jié)構(gòu)中的WCET分析問題。但是，該研究基于的是一個(gè)直接映射的二級(jí)指令Cache，當(dāng)今的多核結(jié)構(gòu)一般采用的是組相連Cache；其次該研究只探討了雙核結(jié)構(gòu)、兩個(gè)任務(wù)(一個(gè)硬實(shí)時(shí)任務(wù)，一個(gè)非硬實(shí)時(shí)任務(wù))下的WCET估計(jì)，當(dāng)核的數(shù)量和任務(wù)數(shù)量增加時(shí)其分析不再有效。文獻(xiàn)[16]描述的方法無法擴(kuò)展任務(wù)大小和任務(wù)數(shù)量。

多核中共享Cache導(dǎo)致最壞情形的不可預(yù)測(cè)性和不可分析性主要是由體干擾[15]引起的。在Cache結(jié)構(gòu)中為了可以進(jìn)行并行操作通常將Cache劃分為多個(gè)體,當(dāng)兩個(gè)存儲(chǔ)請(qǐng)求試圖同時(shí)訪問同一個(gè)體時(shí)，片上互連仲裁器為了避免沖突將把一個(gè)訪問操作延遲一段時(shí)間。這種影響稱為體干擾或者體沖突。如圖1所示。

Figure 1 Bank interruption圖1 體干擾

在圖1中，兩個(gè)線程同時(shí)訪問同一個(gè)存儲(chǔ)體M1，在仲裁器的仲裁下第二個(gè)線程被延遲了數(shù)個(gè)時(shí)鐘周期。針對(duì)這種干擾設(shè)計(jì)者需要確定這種干擾引起的上界延遲UBD(Upper Bound Delay)的大小。該延遲要根據(jù)任務(wù)的類型(實(shí)時(shí)任務(wù)、非實(shí)時(shí)任務(wù))區(qū)別分析。一般對(duì)于實(shí)時(shí)系統(tǒng)而言，實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于非實(shí)時(shí)任務(wù)的優(yōu)先級(jí)，在這個(gè)原則下實(shí)時(shí)任務(wù)不會(huì)受到非實(shí)時(shí)任務(wù)的影響。但是，也存在一種情況使得非實(shí)時(shí)任務(wù)影響實(shí)時(shí)任務(wù)的訪問：在實(shí)時(shí)任務(wù)訪問Cache的前一個(gè)時(shí)鐘周期恰好有一個(gè)非實(shí)時(shí)任務(wù)對(duì)Cache進(jìn)行了訪問。此時(shí)，該實(shí)時(shí)任務(wù)必須等待非實(shí)時(shí)任務(wù)完成才可以開始Cache訪問，則實(shí)時(shí)任務(wù)由于非實(shí)時(shí)任務(wù)的影響而延遲的時(shí)間為：

UBDNHRT=Lbank-1

(1)

其中，Lbank指Cache體訪問時(shí)間。

另一方面，實(shí)時(shí)任務(wù)由于其他實(shí)時(shí)任務(wù)而需要等到其他實(shí)時(shí)任務(wù)請(qǐng)求完成，則由實(shí)時(shí)任務(wù)引起的上界延遲為：

UBDHRT=(NHRT-1)·Lbank

(2)

其中，NHRT指多核中的核數(shù)目或Cache仲裁中的緩沖隊(duì)列大小。

綜合兩種影響可以得到當(dāng)前實(shí)時(shí)任務(wù)由于共享Cache訪問競(jìng)爭(zhēng)而引起的上界延遲為：

UBD=(NHRT-1)×Lbank+

Lbank-1 =NHRT×Lbank-1

(3)

公式(2)中考慮的任務(wù)優(yōu)先級(jí)仲裁策略使用的是Round-Robin。而在嵌入式實(shí)時(shí)系統(tǒng)中，任務(wù)的優(yōu)先級(jí)一般是固定的，此時(shí)實(shí)時(shí)任務(wù)的延遲應(yīng)與其優(yōu)先級(jí)相關(guān),優(yōu)先級(jí)最大的實(shí)時(shí)任務(wù)無論何時(shí)都會(huì)優(yōu)先執(zhí)行，其延遲只會(huì)出現(xiàn)公式(1)中的情況，并且此時(shí)該任務(wù)可以是非實(shí)時(shí)任務(wù)也可以是實(shí)時(shí)任務(wù)。而對(duì)于優(yōu)先級(jí)最低的實(shí)時(shí)任務(wù)，其延遲可以由公式(3)確定，對(duì)于中間級(jí)別的實(shí)時(shí)任務(wù)需要針對(duì)其優(yōu)先級(jí)來分析，但是其延遲大小卻無法確定。

3 實(shí)時(shí)多核體系結(jié)構(gòu)中片上互連敏感的WCET分析

在多核結(jié)構(gòu)中，多個(gè)任務(wù)可以在每個(gè)核上并行執(zhí)行，并行任務(wù)會(huì)同時(shí)對(duì)片上互連發(fā)出請(qǐng)求。當(dāng)片上互連接受某個(gè)任務(wù)的訪問請(qǐng)求時(shí)，根據(jù)互連的方式來決定訪問請(qǐng)求的授權(quán)。此時(shí)，一個(gè)線程可能會(huì)延遲另一個(gè)線程的執(zhí)行時(shí)間，即產(chǎn)生互連干擾(或通信沖突)。這種干擾使得在進(jìn)行多核的WCET估計(jì)時(shí)，相對(duì)于單核中的獨(dú)占總線而言，變得比較復(fù)雜。

目前針對(duì)總線干擾復(fù)雜化WCET分析的問題主要有兩種解決方法：一是消除總線競(jìng)爭(zhēng)，二是簡(jiǎn)化總線仲裁策略。

對(duì)于消除總線競(jìng)爭(zhēng)，文獻(xiàn)[17]提出了一個(gè)系統(tǒng)級(jí)任務(wù)映射與調(diào)度的框架。在這個(gè)研究中，為了避免有關(guān)總線競(jìng)爭(zhēng)的問題，設(shè)計(jì)者使用了所謂的附加總線模型，即假定任務(wù)的執(zhí)行時(shí)間與總線內(nèi)存訪問競(jìng)爭(zhēng)影響很小。在這種模型下設(shè)計(jì)者忽略了總線競(jìng)爭(zhēng)對(duì)任務(wù)執(zhí)行時(shí)間的影響。作者的實(shí)驗(yàn)表明，在總線負(fù)載小于50%時(shí)這種模型具有較好的近似性。但是，這種方法存在兩個(gè)嚴(yán)重的問題：(1)為了使附加模式可用必須保持較低的總線利用率；(2)即使在較低的總線利用率情況下也無法對(duì)任何最壞的行為提供可靠的保證。

線程由于總線干擾所引起的延遲與總線仲裁策略密切相關(guān)?？梢哉?qǐng)求訪問總線的實(shí)例稱為總線Master。目前有設(shè)計(jì)者對(duì)簡(jiǎn)化總線仲裁策略展開了研究，由多種總線仲裁策略來處理多個(gè)總線Master請(qǐng)求，控制總線訪問順序的中央總線仲裁器具有一定的確定性。每個(gè)請(qǐng)求訪問總線的Master必須獲得仲裁器的授權(quán)才可以開始訪問總線。

對(duì)于Round-Robin仲裁策略，一個(gè)實(shí)時(shí)任務(wù)的最大延遲界定于同時(shí)請(qǐng)求總線的任務(wù)總數(shù)。圖2顯示了多個(gè)實(shí)時(shí)任務(wù)同時(shí)向總線發(fā)出請(qǐng)求的情形。

Figure 2 Bus interruption圖2 總線干擾

此時(shí)實(shí)時(shí)任務(wù)的等待時(shí)間取決于其在請(qǐng)求隊(duì)列中的位置。對(duì)于HRTk而言，必須等待前面的任務(wù)都完成了才會(huì)獲得總線使用權(quán)，并且在這期間其他任何新的總線請(qǐng)求都會(huì)在HRTk之后執(zhí)行。所以,對(duì)于一個(gè)實(shí)時(shí)任務(wù)，當(dāng)該任務(wù)恰好處于實(shí)時(shí)任務(wù)請(qǐng)求隊(duì)列的最后時(shí)，其延遲最大。所以，一個(gè)實(shí)時(shí)任務(wù)的上界延遲為：

UBDHRT=(NHRT-1)×Lbus

(4)

其中，NHRT是同時(shí)運(yùn)行的硬實(shí)時(shí)任務(wù)數(shù)，一般是多核結(jié)構(gòu)中的內(nèi)核數(shù)量；Lbus是總線完成一個(gè)請(qǐng)求的時(shí)間。

一般對(duì)于實(shí)時(shí)系統(tǒng)而言，實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于非實(shí)時(shí)任務(wù)的優(yōu)先級(jí)，在這個(gè)原則下實(shí)時(shí)任務(wù)不會(huì)受到非實(shí)時(shí)任務(wù)的影響。但是，與Cache中類似，也存在一種情況使得非實(shí)時(shí)任務(wù)影響實(shí)時(shí)任務(wù)的訪問：在實(shí)時(shí)任務(wù)訪問總線前一個(gè)時(shí)鐘周期恰好有一個(gè)非實(shí)時(shí)任務(wù)對(duì)總線進(jìn)行了訪問。則此時(shí)實(shí)時(shí)任務(wù)由于非實(shí)時(shí)任務(wù)而延遲的時(shí)間為：

UBDNHRT=Lbus-1

(5)

綜合實(shí)時(shí)任務(wù)和非實(shí)時(shí)任務(wù)請(qǐng)求，實(shí)時(shí)任務(wù)的上界延遲為:

UBD=Lbus-1+(NHRT-1)×

Lbus=NHRT×Lbus-1

(6)

根據(jù)底層硬件結(jié)構(gòu)分析中得到的這個(gè)總線請(qǐng)求上界延遲，在靜態(tài)分析的計(jì)算階段加入這個(gè)影響即可得到一個(gè)實(shí)時(shí)任務(wù)安全的WCET。

在多核結(jié)構(gòu)中，基于總線的WCET估計(jì)方法已經(jīng)展開了初步的研究；對(duì)于其他互連方式，由于實(shí)際應(yīng)用的限制，目前并未有相關(guān)的研究。但是，隨著工藝和計(jì)算機(jī)技術(shù)的高速發(fā)展，多核中的核數(shù)目將越來越多，其互連結(jié)構(gòu)也將由簡(jiǎn)單的、只能處理單一請(qǐng)求的總線轉(zhuǎn)變?yōu)榻Y(jié)構(gòu)復(fù)雜、可以同時(shí)處理多個(gè)請(qǐng)求的片上網(wǎng)絡(luò)、交叉開關(guān)、點(diǎn)到點(diǎn)通信等片上互連結(jié)構(gòu)。

4 實(shí)時(shí)多核體系結(jié)構(gòu)中片外存儲(chǔ)敏感的WCET分析

之前的研究都是集中在由訪問片上資源而引起的干擾(共享二級(jí)Cache、片上互連)，而在多核結(jié)構(gòu)中片外共享存儲(chǔ)對(duì)任務(wù)執(zhí)行時(shí)間以及WCET估計(jì)也有很大的影響。文獻(xiàn)[15,16]等關(guān)注于WCET估計(jì)中由片上共享資源引起的干擾，例如Cache和總線。然而，在多核結(jié)構(gòu)中由片外共享存儲(chǔ)系統(tǒng)引起的干擾對(duì)任務(wù)的執(zhí)行時(shí)間和WCET估計(jì)也有著非常重要的影響[18],所以在多核的WCET分析中設(shè)計(jì)者需要考慮由片外存儲(chǔ)引起的干擾影響。

目前針對(duì)片外共享存儲(chǔ)也有相關(guān)的研究，AkessonB等人[19]設(shè)計(jì)了一個(gè)片上多處理器的存儲(chǔ)控制器Predator，該存儲(chǔ)控制器給每個(gè)任務(wù)分配了指定的帶寬，同時(shí)要求用戶指定每個(gè)任務(wù)的優(yōu)先級(jí)，PaolieriM等人在硬實(shí)時(shí)多核系統(tǒng)設(shè)計(jì)了一個(gè)可預(yù)測(cè)的存儲(chǔ)控制器AMC，該控制器可以減少WCET估計(jì)中的存儲(chǔ)干擾因素，提供了一個(gè)可預(yù)測(cè)的存儲(chǔ)訪問時(shí)間，可以實(shí)現(xiàn)緊湊的WCET估計(jì)計(jì)算。

基于多核的片外共享存儲(chǔ)資源，研究者展開了片外存儲(chǔ)可預(yù)測(cè)控制器的研究，針對(duì)某種常用的存儲(chǔ)設(shè)備設(shè)計(jì)一個(gè)存儲(chǔ)控制器，在保證可預(yù)測(cè)的前提下獲得一個(gè)較好的性能。研究者在其設(shè)計(jì)中分析存儲(chǔ)請(qǐng)求的執(zhí)行時(shí)間，計(jì)算存儲(chǔ)請(qǐng)求的上界延遲UBD對(duì)WCET估值的影響，最后進(jìn)行WCET分析。

(1)存儲(chǔ)請(qǐng)求的執(zhí)行時(shí)間。

不同的存儲(chǔ)操作有不同的延遲，存儲(chǔ)讀操作和存儲(chǔ)寫操作的延遲已在特定的存儲(chǔ)設(shè)備中設(shè)定。定義tIL為存儲(chǔ)請(qǐng)求由于前一個(gè)請(qǐng)求而延遲的最大時(shí)間值。tIL的大小與下列兩個(gè)因素密切相關(guān)：①在同一體中激活兩個(gè)連續(xù)的行的最小時(shí)間間隔tIB；②數(shù)據(jù)總線用于傳輸請(qǐng)求的時(shí)間，即tBURST×Nbanks(Nbanks是指存儲(chǔ)設(shè)備的體個(gè)數(shù))。所以，對(duì)于同一體的兩個(gè)活動(dòng)間的最小間隔時(shí)間tIB至少等于tRC。然而，根據(jù)之前的請(qǐng)求類型的不同(例如讀或?qū)懖僮?，tIB會(huì)隨之改變，因此產(chǎn)生了四種類型的延遲：tILRR：前一個(gè)請(qǐng)求是讀操作，當(dāng)前操作也是讀操作；：tILRW前一個(gè)請(qǐng)求是讀操作，當(dāng)前操作是寫操作；tILWW前一個(gè)請(qǐng)求是寫操作，當(dāng)前操作也是寫操作；tILWR前一個(gè)請(qǐng)求是寫操作，當(dāng)前操作是讀操作。

(2)計(jì)算存儲(chǔ)請(qǐng)求UBD。

在計(jì)算WCET估計(jì)時(shí)需要考慮每個(gè)存儲(chǔ)請(qǐng)求最大可能的tIL，定義為：

tILWORST=max{(tILRR,tILRW,tILWW,tILWR}

(7)

此時(shí)無需再考慮所有任務(wù)的存儲(chǔ)訪問序列在WCET計(jì)算中引起的存儲(chǔ)干擾影響，因?yàn)樽顗那樾我呀?jīng)考慮過。因此，存儲(chǔ)請(qǐng)求的UBD取決于tILWORST和同時(shí)運(yùn)行的實(shí)時(shí)任務(wù)和非實(shí)時(shí)任務(wù)產(chǎn)生的干擾。假定實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于非實(shí)時(shí)任務(wù)的優(yōu)先級(jí)，而在實(shí)時(shí)任務(wù)間采用循環(huán)策略，則上界延遲UBD可以定義為：

①針對(duì)實(shí)時(shí)任務(wù)，最壞的情況是多核中同時(shí)執(zhí)行的所有實(shí)時(shí)任務(wù)同時(shí)發(fā)出訪存請(qǐng)求，此時(shí)任務(wù)的最大延遲由同時(shí)執(zhí)行的實(shí)時(shí)任務(wù)數(shù)界定，即：

UBDHRT=(NHRT-1)×tILWORST

(8)

②即使實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于非實(shí)時(shí)任務(wù)，但是也有可能恰好在非實(shí)時(shí)任務(wù)請(qǐng)求發(fā)送到主存后一個(gè)時(shí)鐘周期時(shí)到達(dá)，此時(shí)最大延遲由tILWORST界定，即：

UBDNHRT=tILWORST-1

(9)

綜上所述，實(shí)時(shí)任務(wù)存儲(chǔ)請(qǐng)求的最大延遲為：

UBD=UBDNHRT+UBDHRT=

NHRT×tILWORST-1

(10)

利用WCET計(jì)算模式在WCET分析中加入U(xiǎn)BD因素，即在分析實(shí)時(shí)任務(wù)時(shí)，將每個(gè)任務(wù)獨(dú)立運(yùn)行，但是存儲(chǔ)控制器在該任務(wù)進(jìn)行存儲(chǔ)訪問時(shí)總是將該操作延遲UBD。此時(shí),該任務(wù)的執(zhí)行模式考慮了該任務(wù)所有可能受到的、來自其他任務(wù)的、最壞情況下的最大延遲。

5 實(shí)時(shí)多核系統(tǒng)中的WCET模型

對(duì)于多核而言，傳統(tǒng)的針對(duì)單核結(jié)構(gòu)的WCET估計(jì)技術(shù)不再適用于現(xiàn)在復(fù)雜的多核處理器結(jié)構(gòu)，因此，需要對(duì)WCET針對(duì)新的體系結(jié)構(gòu)特性進(jìn)行分析。對(duì)于復(fù)雜的硬件結(jié)構(gòu)而言，動(dòng)態(tài)硬件模擬仍然存在很多問題，WCET估計(jì)分析時(shí)間較長(zhǎng)，并且有可能產(chǎn)生較大的WCET估計(jì)。而靜態(tài)WCET分析可以獲得安全的上限值。因此研究者試圖使用靜態(tài)分析方法或者混合的方法來進(jìn)行多核的WCET估計(jì)，在混合方法中使用測(cè)量的方法來增強(qiáng)或替代底層靜態(tài)分析。針對(duì)多核復(fù)雜的硬件結(jié)構(gòu)和已有的成熟的單核WCET估計(jì)方法，可以通過采用混合的WCET估計(jì)方法來對(duì)多核結(jié)構(gòu)進(jìn)行WCET估計(jì)，這樣不僅可以節(jié)約時(shí)間，有效利用已有技術(shù)和方法，而且可以使設(shè)計(jì)者更專注于底層硬件結(jié)構(gòu)的分析。文獻(xiàn)[13]采用以下步驟設(shè)計(jì)了一個(gè)多核系統(tǒng)中的混合WCET估計(jì)模型：

(1)針對(duì)多核中的共享資源(片上共享資源Cache和總線、片外共享存儲(chǔ)資源)，分析這些共享資源給任務(wù)執(zhí)行帶來的影響，計(jì)算任務(wù)最大延遲時(shí)間：上界延遲UBD。

(2)在多核硬件結(jié)構(gòu)中設(shè)置一個(gè)延遲表和一個(gè)延遲部件，延遲表用于記錄上界延遲UBD，延遲部件用于將任務(wù)訪問貢獻(xiàn)資源的操作進(jìn)行延遲，延遲大小為對(duì)應(yīng)的延遲表中記錄的UBD。

(3)使用WCET計(jì)算模型進(jìn)行WCET估計(jì)，即：在底層硬件多核結(jié)構(gòu)中將每個(gè)任務(wù)單獨(dú)執(zhí)行(與任務(wù)在單核中獨(dú)立執(zhí)行一樣)，但是在執(zhí)行的過程中將任務(wù)每個(gè)訪問共享資源的操作延遲一定的時(shí)間。

在該WCET估計(jì)模型中將任務(wù)在最壞情形下執(zhí)行：任務(wù)每次訪問共享資源都受到干擾，都需要延遲一段時(shí)間，這種計(jì)算模型考慮了該任務(wù)所有可能受到的、來自其他任務(wù)的、最壞情況下的最大延遲，所以在該情形下一定可以保證WCET估計(jì)的有效性。

雖然上述模型可以得到一個(gè)有效的WCET估計(jì)，但是對(duì)其精度和效率都還沒有進(jìn)行研究和比較，所以還需要對(duì)WCET分析的精度和WCET分析方法的性能進(jìn)行研究。

6 結(jié)束語

實(shí)時(shí)系統(tǒng)必須保證任務(wù)滿足時(shí)間限制，通常研究者可以使用靜態(tài)分析方法和基于測(cè)量的方法來計(jì)算WCET。但是，這些方法的精確性和有效性高度依賴于實(shí)際處理器平臺(tái)的可預(yù)測(cè)性，也就是說，處理器體系結(jié)構(gòu)決定了這些方法的實(shí)際可行性以及結(jié)果的精確性。工業(yè)界仍在使用的WCET估計(jì)分析方法對(duì)于復(fù)雜的處理器，例如多核處理器，不再適用，這是由于多核結(jié)構(gòu)中的共享資源使得實(shí)時(shí)任務(wù)間互相產(chǎn)生了干擾，任務(wù)的執(zhí)行時(shí)間和WCET不能再獨(dú)立進(jìn)行分析。多核中的多任務(wù)在同時(shí)運(yùn)行時(shí)由于競(jìng)爭(zhēng)共享資源，例如共享Cache、片上互連、片外存儲(chǔ)，使得任務(wù)的最壞情況下執(zhí)行時(shí)間無法再利用單核中的WCET分析方法得到，設(shè)計(jì)者需要針對(duì)多核中的共享資源重新進(jìn)行WCET分析。

對(duì)于一個(gè)應(yīng)用于實(shí)時(shí)系統(tǒng)的多核結(jié)構(gòu)而言，其最重要的一個(gè)因素是要保證可預(yù)測(cè)性，即一個(gè)任務(wù)在多核中運(yùn)行可以預(yù)測(cè)出其WCET以進(jìn)行后續(xù)的實(shí)時(shí)任務(wù)調(diào)度。多核時(shí)序可預(yù)測(cè)結(jié)構(gòu)的設(shè)計(jì)原則是要在嵌入式硬實(shí)時(shí)系統(tǒng)中保證可預(yù)測(cè)性、較好的最壞情況下性能。在進(jìn)行可預(yù)測(cè)實(shí)時(shí)多核設(shè)計(jì)時(shí)應(yīng)盡量遵循如下原則[20]：

(1)結(jié)構(gòu)與應(yīng)用相關(guān)，即針對(duì)特定的嵌入式硬實(shí)時(shí)系統(tǒng)進(jìn)行多核結(jié)構(gòu)設(shè)計(jì)，在提高最壞情況下性能的同時(shí)保證可靠的、精確的可預(yù)測(cè)性。

(2)簡(jiǎn)化設(shè)計(jì)中的部件結(jié)構(gòu)，在保證可預(yù)測(cè)性的前提下將那些與性能無關(guān)的特性取消。例如，在以存儲(chǔ)系統(tǒng)性能界定系統(tǒng)性能的系統(tǒng)中可以盡量簡(jiǎn)化流水線結(jié)構(gòu)。

(3)盡量減少系統(tǒng)中共享資源的干擾，可以在不影響性能的前提下盡量避免構(gòu)建共享Cache或存儲(chǔ)。

在將應(yīng)用程序集映射到目標(biāo)體系結(jié)構(gòu)中時(shí)盡量避免引入應(yīng)用程序間的共享干擾。

[1] International technology roadmap for semiconductors 2008 update[EB/OL].[2008-08-21]. http://public.itrs.net.

[2] Davis R I, Burns A. A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[R]. Technical Report YCS-2009-443, Department of Computer Science University of York, 2009.

[3] Hirata K, Goodacre J. Arm mpcore:The streamlined and scalable arm11 processor core[C]∥Proc of Design ASP-DAC’07, 2007:747-748.

[4] Pham D C, Aipperspach T, Boerstler D, et al. Overview of the architecture, circuit design, and physical implementation of a first-generation cell processor[J]. IEEE Journal of Solid-State Circuits, 2006,41(1):179-196.

[5] Puschner P, Burns A. A review of worst-case execution-time analysis[J]. Real-Time Systems, 2000,18(2/3):115-127.

[6] Thiele L, Wilhelm R. Design for timing predictability[J]. Real-Time Systems, 2004,28(2/3):157-177.

[7] Li Y T S, Malik S, Wolfe A. Cache modeling for real-time software:Beyond direct mapped instruction caches[C]∥Proc of IEEE Real-Time Systems Symposium, 1996:254-263.

[8] Theiling H,Ferdinand C,Wilhelm R.Fast and precise WCET prediction by separated cache and path analysis [J]. Real-Time Systems, 2000,18(2/3):157-179.

[9] Ramaprasad H, Mueller F. Bounding preemption delay within data cache reference patterns for real-time tasks[C]∥Proc of Real-Time and Embedded Technology and Applications Symposium, 2005:71-80.

[10] Staschulat J, Schliecker S, Ernst R. Scheduling analysis of real-time systems with precise modeling of cache related preemption delay[C]∥Proc of ECRTS’05, 2005:41-48.

[11] Fedorova A, Seltzer M, Small C, et al. Throughput-oriented scheduling on chip multithreading systems[R]. Technical Report TR-17-04, Cambridge:Harvard University, 2005.

[12] Anderson J H, Calandrino J M. Parallel real-time task scheduling on multicore platforms[C]∥Proc of RTSS’06, 2006:89-100.

[13] Calandrino J M, Anderson J H. Cache-aware real-time scheduling on multicore platforms:Heuristics and a case study[C]∥Proc of ECRTS’08, 2008:299-308.

[14] Nan Guan, Stigge M, Wang Yi, et al. Cache-aware scheduling and analysis for multicores[C]∥Proc of EMSOFT’09, 2009:245-254.

[15] Paolieri M, Quinones E, Cazorla F J, et al. Hardware support for WCET analysis of hard real-time multicore systems[J]∥ACM SIGARCH Computer Architecture News, 2009,37(3):57-68.

[16] Rosen J, Andrei A, Eles P, et al. Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip[C]∥Proc of Real-Time Systems Symposium, 2007:49-60.

[17] Bertozzi D, Guerri A, Milano M, et al. Communication-aware allocation and scheduling framework for stream-oriented multi-processor systems-on-chip[C]∥Proc of DATE’06, 2006:3-8.

[18] Burger D, Goodman J R, K?gi A. Memory bandwidth limitations of future microprocessors[C]∥Proc of ISCA’96, 1996:78-89.

[19] Akesson B,Goossens K,Ringhofer M.Predator:A predictable SDRAM memory controller[C]∥Proc of CODES+ISSS, 2007:251-256.

[20] Wilhelm R, Grund D, Reineke J, et al. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems[J]. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 2009,28(7):966-978.

CHEN Fang-yuan,born in 1982,PhD,engineer,her research interests include computer architecture, and real-time system.

Research of real-time multi-core architecture for WCET analysis

CHEN Fang-yuan1，DING Ya-jun1，ZHANG Dong-song2，WU Fei3，REN Xiu-jiang1
(1.Jiangnan Institute of Computing Technology,Wuxi 214083;2.Zhenjiang Watercraft College of PLA,Zhenjiang 212000;3.College of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)

With the development of technology and the increasing growth of applications and requirements in embedded real-time systems, multi-core processors will be adopted in embedded real-time systems for its high performance and low power features. However, the multi-core architecture is hard, even impossible to satisfy the requirement of real-time and the predictability of WCET. Starting with the shared resources, we analyze the influence of on-chip shared resources and off-chip resources on WCET analysis, and discuss various WCET methods. Two WCET models are introduced: multi-core static WCET model and multi-core hybrid WCET model. At last, the multi-core design rule for the real-time application is proposed.

multi-core architecture;embedded real-time system;real-time task;WCET

2013-10-12;

2013-12-20

國家自然科學(xué)基金資助項(xiàng)目(61272097)；上海市教委科研創(chuàng)新重點(diǎn)基礎(chǔ)研究項(xiàng)目(12ZZ182)

1007-130X(2014)03-0393-06

TP303

A

10.3969/j.issn.1007-130X.2014.03.003

陳芳園(1982-),女,湖北鐘祥人，博士，工程師，研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)和實(shí)時(shí)系統(tǒng)。E-mail:fychen@nudt.edu.cn

通信地址：214083 江蘇省無錫市江南計(jì)算技術(shù)研究所

Address:Jiangnan Institute of Computing Technology,Wuxi 214083,Jiangsu,P.R.China