多核共享cache確定性技術

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

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

0 引 言

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

1 國內外研究

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

圖1 多核共享cache沖突

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

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

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

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

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

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

2 基于路的共享cache分區

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

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

基于路的cache分區策略示意如圖2所示，在一個四路組相聯的共享cache結構中，將cache的第一路和第二路分配給Core0，第三路和第四路分配給Core1，兩個核分別占用每個cache組的兩路cache，達到兩個核各獨占50%共享cache容量的目的。這種cache分區策略需要操作系統提供配置界面，針對每種硬件平臺提供配置數據。用戶通過配置界面為每個核配置相應的cache路。

圖2 基于路的cache分區策略

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

圖3 基于路的Cache分區流程

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

3 基于組的共享cache染色

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

共享cache的組織結構如圖4所示，內存地址的Set index域索引至具體的cache組，而組內的cache路是全相聯。cache染色分區的目的是不同核訪問不同的cache組，其原理就是不同核訪問的物理地址的Set index域不同。所以操作系統的共享cache染色設計實現是對處理器核上運行分區的物理地址分配管理，按照對應的色域進行分區物理地址空間分配。

圖4 cache組織結構

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

圖5 確定性多核操作系統cache著色設計框架

共享cache確定性緩解技術與硬件平臺相關，操作系統在啟動過程中需要獲取硬件的cache信息，包括容量、組織結構、地址索引段等。將這些信息作為cache分區的輸入數據，操作系統根據這些數據給分區分配內存空間段、cache容量。

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

圖6 共享cache染色分組流程

4 實驗結果

4.1 實驗環境

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

圖7 硬件測試環境

4.2 實驗方法

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

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

4.3 結果分析

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

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

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

圖9 FT2000共享Cache確定性測試結果

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

5 結束語

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