多核共享cache確定性技術(shù)

虞保忠，周 霆，李運喜，黃凡帆

(中航工業(yè)西安航空計算技術(shù)研究所 第三研究室，陜西 西安 710010)

0 引 言

多核共享cache確定性是多核應(yīng)用于嵌入式實時系統(tǒng)所需要解決的關(guān)鍵技術(shù)。所謂確定性是指在給定輸入條件下，計算機能夠在確定的時間輸出確定的結(jié)果，即時間和計算結(jié)果確定。多核系統(tǒng)由于多個處理器核心共享cache，在并行運行時會競爭cache，導致cache抖動，影響軟件運行時序，計算機不能在確定的時間完成計算任務(wù)，這就是多核共享cache確定性問題。通用領(lǐng)域?qū)r間確定性并不敏感，只需要能夠輸出正確的結(jié)果，時間不確定性并不是功能問題。然而在實時確定性要求較高的安全應(yīng)用領(lǐng)域，如工業(yè)控制、醫(yī)療、航空航天、汽車等，對計算機軟件運行時序非常敏感，時間上的不確定性可能引發(fā)災(zāi)難性后果，因此確定性是實時系統(tǒng)關(guān)鍵需求。共享cache競爭沖突，微觀上影響CPU取指和內(nèi)存讀寫時間的不確定性，宏觀上導致應(yīng)用執(zhí)行時間的波動，影響軟件服務(wù)質(zhì)量，在安全關(guān)鍵領(lǐng)域甚至降低了軟件實時性。在多核平臺構(gòu)建安全關(guān)鍵系統(tǒng)需要重點考慮共享cache沖突干擾問題。Tim Loveless提出了構(gòu)建安全多核系統(tǒng)需要面臨共享cache確定性關(guān)鍵技術(shù)挑戰(zhàn)[1]，美國聯(lián)邦航空局一直在研究多核應(yīng)用于航空領(lǐng)域，針對多核共享cache提出了一些確定性分析和緩解建議[2]。本研究為了解決嵌入式實時系統(tǒng)多核并行時競爭共享cache沖突問題，在實時操作性中設(shè)計并實現(xiàn)cache確定性緩解策略，減少共享cache沖突，降低多核之間互擾，保證軟件執(zhí)行時間的確定性，通過實驗對比分析，經(jīng)過確定性緩解后，程序運行時間確定。

1 國內(nèi)外研究

多核共享cache競爭沖突是普遍存在的問題，圖1是典型的多核共享cache結(jié)構(gòu)，核在訪問L2 cache會產(chǎn)生競爭沖突，導致cache抖動、訪問延遲等問題。國內(nèi)外安全關(guān)鍵系統(tǒng)領(lǐng)域研究者深入分析共享cache確定性問題引發(fā)的原因、影響因素及產(chǎn)生的后果，通過消除或降低影響因素的方式緩解共享cache確定性問題。

圖1 多核共享cache沖突

CAST32A[2]是軟件認證指南，提出了多核需要解決重點解決多核之間的互相干擾問題，特別是共享cache競爭沖突導致的確定性問題。安全認證過程應(yīng)當考慮共享cache的確定性影響因素，采用硬件或軟件方法緩解共享cache的確定性問題。歐洲航空安全委員會研究的航空系統(tǒng)應(yīng)用多核項目提出需要對多核共享cache進行確定性影響分析，明確影響邊界及危害等級，并需要采取緩解措施。這兩項研究明確提出了安全關(guān)鍵領(lǐng)域應(yīng)用多核技術(shù)所帶來的共享cache沖突問題。由于硬件平臺的通用性，并沒有針對安全關(guān)鍵領(lǐng)域提供硬件層的確定性技術(shù)支持，因此需要重點從軟件層面采取確定性緩解措施。國內(nèi)外學者意識到了共享cache確定性問題帶來的服務(wù)質(zhì)量、安全性、實時性等問題，分別從硬件和軟件層提出了共享cache緩解方法，包括cache分區(qū)、cache鎖等機制。Awan M A等提出動態(tài)資源調(diào)度機制解決混合安全關(guān)鍵系統(tǒng)中共享cache確定性問題[3]。

一些多核處理器，如T2080平臺在硬件層面提供共享cache分區(qū)能力，把共享cache按核分配。這種分配方式是按行分配原則，每個cache組有16行，根據(jù)讀、寫方式，可允許每個處理器核以讀或?qū)懛绞绞褂弥付ǖ腸ache行。因此一個處理器核能夠使用的共享cache容量是0/16、1/16、2/16…至16/16的總cache大小。操作系統(tǒng)在給核分配共享cache容量時，按比例分配，保證每個核占用獨立的cache空間，避免共享cache競爭沖突。這種cache分配屬于靜態(tài)分區(qū)能力，cache分配到核，而不能隨應(yīng)用分配。

Intel?Xeon?E5 2600 v3系列服務(wù)器處理器引入了Cache Allocation Technology(CAT)[4]和Cache Monitoring Technology(CMT)[5]能夠給應(yīng)用分配私有共享cache空間。在硬件層提供共享cache的分配能力，CAT為cache空間管理控制提供軟件可編程接口，由操作系統(tǒng)根據(jù)應(yīng)用實際需求分配資源ID、資源容量，并分配到指定處理器核上調(diào)度，能夠?qū)崿F(xiàn)對應(yīng)用程序進行共享cache分配管理。CPU提供一套寄存器和接口中監(jiān)控cache事件，CMT可在多核平臺上同時監(jiān)控多個應(yīng)用程序的cache使用情況。

硬件獨有的cache分區(qū)能力不具備通用性，很多貨架產(chǎn)品并不支持這種能力。Sparsh Mittal[6]意識到共享cache帶來的性能損失、缺乏公平性及較低服務(wù)質(zhì)量(QoS)等問題，因此研究了一些多核共享cache分區(qū)技術(shù)。Mehrzad Nejat等[7]為了提升多核共享cache效能，提出了多核平臺的動態(tài)調(diào)頻調(diào)壓及運行cache分區(qū)技術(shù)，在保證服務(wù)質(zhì)量前提下節(jié)約功耗。而Saad Zia Sheikh等[8]在多核實時平臺上提出了動態(tài)cache分區(qū)技術(shù)，滿足多核系統(tǒng)實時性和確定性需求。

共享cache運行時動態(tài)分區(qū)[8-13]技術(shù)能夠一定程序緩解共享cache確定性問題，但是它們依賴于硬件提供的cache分區(qū)能力[4,5]。由于多數(shù)貨架產(chǎn)品不具備這樣的能力，特別是嵌入式系統(tǒng)領(lǐng)域，這就極大限制了共享cache分區(qū)應(yīng)用場景。因此需要能夠不依賴于硬件，且能夠滿足實時性需求的cache確定性緩解技術(shù)。Zheng W等提出在任務(wù)調(diào)度和cache鎖方面進行優(yōu)化[14]，以實現(xiàn)cache的最大效能，這種方法針對特定的任務(wù)集合，不能滿足不同應(yīng)用的需求，且不能解決cache確定性問題。Elena Lucherini[15]和Holtryd NR等[16]研究通用計算系統(tǒng)中的內(nèi)存頁著色技術(shù)，通過頁著色實現(xiàn)共享cache的分區(qū)，基于Linux系統(tǒng)實現(xiàn)，修改內(nèi)存分配器以實現(xiàn)頁著色。這種頁著色技術(shù)的實現(xiàn)依賴Linux的內(nèi)存管理機制，不具備實時性，不能應(yīng)用于多核實時系統(tǒng)領(lǐng)域。

本文在國產(chǎn)實時653操作系統(tǒng)中實現(xiàn)共享cache分區(qū)和共享cache染色方法，通過這兩種方法達到緩解多核共享cache確定性問題。653操作系統(tǒng)是遵守航空653標準的實時分區(qū)操作系統(tǒng)，具備時空隔離能力、多核支持能力、分區(qū)與核親和設(shè)置能力，將處理器核的cache容量需求抽象成分區(qū)的cache容量需求，解決機載應(yīng)用多核共享cache確定性問題。

2 基于路的共享cache分區(qū)

基于路的共享cache分區(qū)是按cache路分配給處理器核。cache的組成結(jié)構(gòu)由路、組構(gòu)成，共享cache有N個組，每個組內(nèi)有M路(8路、16路)，按路分配的就是把每個組內(nèi)的各路cache分配給固定的核。

這種基于路cache分區(qū)策略(way-based)通常是通過利用硬件級支持來實現(xiàn)。Power PC T2080平臺支持共享L2 cache在路一級別的劃分，通過對一組共享cache控制寄存器的配置，能夠做到將L2 cache中指定的路分配給指定的處理器核心，同時能夠指定該處理器核心對所分配的cache 路的操作權(quán)限，如讀時分配、寫時分配。讀時分配是指處理器核在讀內(nèi)存操作時，允許其分配該路cache，將讀的內(nèi)存數(shù)據(jù)緩存在cache中，提升讀內(nèi)存性能；寫時分配是指處理器核在寫內(nèi)存時，允許其分配該路cache，將待寫數(shù)據(jù)緩存在cache中，不直接寫內(nèi)存，提升寫內(nèi)存性能。

基于路的cache分區(qū)策略示意如圖2所示，在一個四路組相聯(lián)的共享cache結(jié)構(gòu)中，將cache的第一路和第二路分配給Core0，第三路和第四路分配給Core1，兩個核分別占用每個cache組的兩路cache，達到兩個核各獨占50%共享cache容量的目的。這種cache分區(qū)策略需要操作系統(tǒng)提供配置界面，針對每種硬件平臺提供配置數(shù)據(jù)。用戶通過配置界面為每個核配置相應(yīng)的cache路。

圖2 基于路的cache分區(qū)策略

操作系統(tǒng)的基于路的共享cache分區(qū)設(shè)計實現(xiàn)如圖3所示。操作系統(tǒng)對外提供共享cache分配數(shù)據(jù)配置接口，在操作系統(tǒng)開發(fā)環(huán)境中進行配置，配置數(shù)據(jù)以XML數(shù)據(jù)形式傳遞給操作系統(tǒng)。用戶分別配置每個CPU核能夠使用的cache路，共享cache是16路組相聯(lián)，每一路都可獨立配置。每路配置數(shù)據(jù)包括能夠訪問的核集和訪問模式。核集是一個32位數(shù)，每一位表示一個核，為0表示該核能夠訪問此路cache，為0表示該核不能訪問此路cache。訪問模式是讀、寫操作，讀配置為1時表示該核讀內(nèi)存時能夠分配此路cache，為0時表示該核讀內(nèi)存時不能夠分配此路cache；寫配置為1時表示該核寫內(nèi)存時能夠分配此路cache，為0時表示該核寫內(nèi)存時不能夠分配此路cache。通過這種細粒度的配置控制，嚴格控制核訪問內(nèi)存時的cache操作行為，避免多核分配同一路cache時的競爭沖突。L2CachePartitionPolicy根據(jù)配置數(shù)據(jù)生成硬件能夠識別的分區(qū)策略，轉(zhuǎn)換成對應(yīng)的硬件參數(shù)，并且由L2CachePartition將策略寫入到硬件中，開啟平臺的L2 cache分區(qū)功能，每個CPU核只能使用分配的cache行，避免cache路競爭。多核之間的cache路隔離機制給用戶提供了一種可配置的cache私有化劃分方法，允許用戶根據(jù)實際應(yīng)用場景按需分配，是一種非常靈活的配置方法，具有硬件依賴性，同時也需要用戶能夠準確估算各處理器核需要的cache容量。

圖3 基于路的Cache分區(qū)流程

cache分區(qū)屬于靜態(tài)分配機制，在系統(tǒng)初始化階段根據(jù)配置數(shù)據(jù)為每個核分配相應(yīng)的共享cache路及訪問模式，分配方式與核相關(guān)，運行時無法動態(tài)修改，運行于該核上的所有應(yīng)用共享這些cache空間。因此這種cache分區(qū)策略屬于按核分配，無法根據(jù)核上應(yīng)用動態(tài)分配，能夠在一定程度上緩解多核共享cache確定性一，但是犧牲了共享cache利用率，且有一定的局限性。

3 基于組的共享cache染色

基于組的共享cache染色是一種硬件無關(guān)的共享cache分區(qū)方法。與基于路的共享cache分區(qū)不同，它是把共享cache中的N個組分成若干份，每個核一份，每個核使用獨立的cache組。操作系統(tǒng)將頁著色設(shè)計作為一項配置項向用戶提供，為用戶提供cache確定性的解決策略，根據(jù)處理器核數(shù)確定頁色數(shù)目，做到每個核一種頁色。

共享cache的組織結(jié)構(gòu)如圖4所示，內(nèi)存地址的Set index域索引至具體的cache組，而組內(nèi)的cache路是全相聯(lián)。cache染色分區(qū)的目的是不同核訪問不同的cache組，其原理就是不同核訪問的物理地址的Set index域不同。所以操作系統(tǒng)的共享cache染色設(shè)計實現(xiàn)是對處理器核上運行分區(qū)的物理地址分配管理，按照對應(yīng)的色域進行分區(qū)物理地址空間分配。

圖4 cache組織結(jié)構(gòu)

操作系統(tǒng)的頁著色分配對象為653分區(qū)，如圖5所示。每個分區(qū)綁定在固定核上運行，操作系統(tǒng)給分區(qū)分配固定顏色的內(nèi)存頁。操作系統(tǒng)重新設(shè)計內(nèi)存分配器，分區(qū)的內(nèi)存空間按頁分配，內(nèi)存空間按頁管理，且標識相應(yīng)的顏色，不同顏色的內(nèi)存映射到不同的共享cache組。在分區(qū)初始化階段分配若干個內(nèi)存頁。通過靜態(tài)分配方式給各分區(qū)分配對應(yīng)顏色的物理內(nèi)存。具體設(shè)計流程包括：操作系統(tǒng)配置項目根據(jù)具體的處理器平臺為用戶提供cache染色的具體信息，包括是否使能cache染色、操作系統(tǒng)可提供的顏色數(shù)目、cache大小、每種顏色的cache大小等信息，用戶依據(jù)配置信息為每個分區(qū)配置分區(qū)所需要的cache顏色，操作系統(tǒng)依據(jù)用戶的配置在啟動階段為每一個分區(qū)分配與該分區(qū)配置的cache顏色數(shù)量匹配的內(nèi)存地址，完成每一個分區(qū)的虛擬地址與物理地址的映射，保證不同分區(qū)的物理地址頁按照頁著色算法的映射關(guān)系被映射到不同的cache塊中，如圖5所示。

圖5 確定性多核操作系統(tǒng)cache著色設(shè)計框架

共享cache確定性緩解技術(shù)與硬件平臺相關(guān)，操作系統(tǒng)在啟動過程中需要獲取硬件的cache信息，包括容量、組織結(jié)構(gòu)、地址索引段等。將這些信息作為cache分區(qū)的輸入數(shù)據(jù)，操作系統(tǒng)根據(jù)這些數(shù)據(jù)給分區(qū)分配內(nèi)存空間段、cache容量。

用戶在配置項目中根據(jù)操作系統(tǒng)提供的具體處理器信息完成對各個應(yīng)用分區(qū)的cache顏色的劃分。操作系統(tǒng)中的cache染色分組設(shè)計如圖6所示，其主要涉及操作系統(tǒng)的空間管理和任務(wù)調(diào)度。根據(jù)平臺的共享cache配置信息獲取接口獲取共享cache的一些配置參數(shù)，同時獲取平臺的CPU核數(shù)。將共享cache按照核數(shù)分成若干組，計算組大小及標識出內(nèi)存地址中的cache組標識位。空間管理模塊按組進行內(nèi)存分配管理，每一組內(nèi)存地址映射到對應(yīng)的cache組。在給任務(wù)分配內(nèi)存空間時，根據(jù)任務(wù)所屬的CPU核從對應(yīng)的內(nèi)存組中分配內(nèi)存。因此，最終結(jié)果是CPU核調(diào)度任務(wù)運行時，只能占用固定的cache組，不同核之間使用單獨的cache組。

圖6 共享cache染色分組流程

4 實驗結(jié)果

4.1 實驗環(huán)境

本文在國產(chǎn)實時653操作系統(tǒng)中實現(xiàn)并驗證共享cache分區(qū)和共享cache染色方法，硬件測試環(huán)境如圖7所示，1臺PC機、1臺Power PC T2080目標機、1臺國產(chǎn)FT2000A/HK目標機，通過1臺以太網(wǎng)交換機連接，用于加載待測試程序及調(diào)試控制；目標機的串口通過1臺N-port，經(jīng)以太網(wǎng)交換機連接到PC機，用于查看目標機程序的執(zhí)行輸出。

圖7 硬件測試環(huán)境

4.2 實驗方法

本實驗方法是在多核平臺中(2核和4核)，每個處理器核運行訪存密集型測試程序，連續(xù)多次運行，統(tǒng)計測試程序每次運行時間，通過程序運行時波動性驗證確定性效果，運行時間越穩(wěn)定，確定性越好，偶爾出現(xiàn)運行時間較大波動的，則確定性較差。

T2080是四核處理器平臺，2 MB共享cache，在國產(chǎn)操作系統(tǒng)中構(gòu)建4個應(yīng)用分區(qū)，每個核上一個應(yīng)用分區(qū)；FT2000AHK是雙核處理器平臺2 MB共享cache，構(gòu)建2個應(yīng)用分區(qū)。每個應(yīng)用分區(qū)內(nèi)執(zhí)行高頻次的內(nèi)存訪問，通過跨cache行的方式觸發(fā)共享cache不命中事件，引發(fā)多核并發(fā)訪問共享cache。針對基于路的共享cache分區(qū)方法，通過配置數(shù)據(jù)平均分配共享cache，測試每個核上測試程序執(zhí)行時間，測試單核情況下測試程序執(zhí)行時間，測試不開啟基于路的共享cache分區(qū)時每個核上測試程序執(zhí)行時間。針對基于組的共享cache染色方法，通過物理地址配置方式，使每個分區(qū)坐落在不同的cache組，測試每個核上程序執(zhí)行時間，測試單核情況下測試程序執(zhí)行時間及不開啟基于組的共享cache染色方法時每個核上測試程序執(zhí)行時間。FT2000AHK本身不支持共享cache分區(qū)，因此只測試驗證了基于組的共享cache染色方法。分別測試單核無沖突干擾、多核不開啟共享cache確定性緩解措施及開啟確定性緩解措施后每個測試程序執(zhí)行時間波動性。

4.3 結(jié)果分析

圖8是T2080平臺上的共享cache確定性緩解測試數(shù)據(jù)。該平臺四核共享二級cache，提供硬件層的cache分區(qū)能力及禁止二級cache的能力。因此分別測試了單核、多核基于組的cache染色分區(qū)、多核cache不分區(qū)、禁止二級cache及多核基于路的cache分區(qū)的配置下測試程序的性能。如該圖所示，橫軸是測試程序運行次數(shù)，縱軸是測試程序運行時間，在單核情況下，測試程序性能最優(yōu)，穩(wěn)定性也較好，這是由于單核獨占共享cache，沒有核間的競爭沖突；而多核不分區(qū)情況下，測試程序性能會出現(xiàn)多次抖動，這些抖動是由核間的共享cache競爭沖突產(chǎn)生；在關(guān)閉共享cache情況下，測試程序性能最差，但是穩(wěn)定性好；基于路的cache硬件分區(qū)配置下，性能稍優(yōu)于禁止共享cache的配置，且穩(wěn)定性較好；基于組的cache染色分區(qū)性能與不分區(qū)的配置相當，且穩(wěn)定性好。cache硬件分區(qū)和cache染色分區(qū)都能夠在一定程序上緩解確定性問題，但是硬件分區(qū)是針以核為對象分配cache行，多核不會共享同一cache行，共享數(shù)據(jù)也就需要每個核單獨加載；而cache染色分區(qū)是以任務(wù)為對象分配cache組，多核共享的數(shù)據(jù)只需要一個核加載，因此cache染色分區(qū)的性能稍優(yōu)于cache硬件分區(qū)。

圖8 T2080共享cache確定性緩解測試

圖9是FT2000平臺上的共享cache確定性緩解測試數(shù)據(jù)。由于該平臺硬件層不提供cache分區(qū)能力，因此使用平臺無關(guān)的cache染色技術(shù)進行cache分區(qū)。如該圖所示，橫軸是測試程序運行次數(shù)，縱軸是測試程序運行時間，在單核情況下，測試程序性能最優(yōu)，穩(wěn)定性也較好，這是由于單核獨占共享cache，沒有核間的競爭沖突；而雙核不分區(qū)情況下，測試程序性能會出現(xiàn)多次抖動，這些抖動是由核間的共享cache競爭沖突產(chǎn)生；在雙核分區(qū)情況下，測試程序性能較穩(wěn)定，沒有抖動現(xiàn)象。

圖9 FT2000共享Cache確定性測試結(jié)果

共享cache確定性緩解技術(shù)實驗結(jié)果表明，無緩解措施情況下，程序在T2080和FT2000平臺上運行時間會偶爾出現(xiàn)較大波動，而經(jīng)過緩解措施后，程序運行時間平穩(wěn)，平臺上能夠取得較好的確定性效果。

5 結(jié)束語

本文針對多核平臺的653操作系統(tǒng)設(shè)計實現(xiàn)共享cache分配管理，根據(jù)應(yīng)用分區(qū)的cache需求進行分配。這種cache分區(qū)策略能夠避免共享cache競爭沖突，確定性緩解機制作為操作系統(tǒng)的配置能力，無論多核處理器是否具備共享cache硬件級分區(qū)能力，都能夠在操作系統(tǒng)層實現(xiàn)共享cache分區(qū)。該方法不增加額外硬件開銷，對操作系統(tǒng)改動很少，只涉及到存儲空間管理的改造，在不影響系統(tǒng)性能前提下提升多核系統(tǒng)確定性。在注重安全性實時性的安全關(guān)鍵領(lǐng)域，確定性高于計算性能，操作系統(tǒng)通過設(shè)計cache分區(qū)方法緩解確定性問題。