多核cache親和性

1、多核cache親和性綜述概述禾U用親和性這種特性可以降低進程轉(zhuǎn)移帶來的性能損失，提高cache命中率，同時利用該特性可以充分利用片上所有的cache來加速串行程序的執(zhí)行。但要利用該特性需要操作系統(tǒng)調(diào)度程序的支持，同時要求有一定的硬件的支持。經(jīng)過研究，cache親和性對單核多處理器的性能提升不大，但對于多核多處理器能帶來很大的性能提升。該文主要介紹了親和性的定義，親和性對性能的影響，最后怎樣利用操作系統(tǒng)及硬件支持 來充分利用該特性。引言芯片多處理器（CMP的已成為當(dāng)今高性能的多處理器主要形式之一。對 影響性能的關(guān)鍵因素之一便是高速緩存的利用率。傳統(tǒng)的對于高速緩存，每個 核心是有自己的私有L1高速

2、緩存，并在同一芯片上所有核心共享的較大二級緩 存。為了提高緩存利用率，我們需要考慮在緩存中的數(shù)據(jù)重用，在所有核心上 匚 共享緩存緩存訪問的爭奪，和私有緩存間的連貫性缺失率。親和性定義：親和性指進程在給定的cpu或cpu核上運行盡量長的時間而不被轉(zhuǎn)移到別的處理器的傾向性。在Linux里，內(nèi)核進程調(diào)度器天生就具有 軟親和性（soft affinity）的特性，這意味著進程通常不會在處理器或者內(nèi)核之間頻繁遷移。這種情況是我們希望的，因為進程遷移的頻率低意味著產(chǎn)生的負(fù)載小，具有更好的性能表現(xiàn)。在對稱多處理（SMP）上，操作系統(tǒng)的進程調(diào)度程序必須決定每個CPU上要運行哪些進程。這帶來兩項挑戰(zhàn)：調(diào)度程序必

3、須充分利用所有處理器，避免當(dāng)一個進程已就緒等待運行，卻 有一個CPU核心閑置一旁，這顯然會降低效率。然而一個進程一旦被安排在某個CPU核心上運行，進程調(diào)度程序也會將它安排在相同的CPU核心上運行。這會使性能更好，因為將一個進程從一個處理器遷移到另一個處理器是要付出性能代價的。一般進程會在相同的核或 CPU上運行，只會在負(fù)載極不均衡的情況下從一個核移往另一個核。這樣可以最小化緩存區(qū)遷移效應(yīng)，同時保證系統(tǒng)中處理器負(fù)載均衡。親和性程序性能的影響多核處理器的處理器與處理器之間的cache親和力是通過觀察緩存方面積累了一定的進程的狀態(tài)，即數(shù)據(jù)或指令后才進行考察的。利用高速緩存的親和力特性是由操作系統(tǒng)的調(diào)

4、度策略實現(xiàn)的：他們傾向于重新安排流程，使可能時盡量使程序運行在最近使用的處 理器。當(dāng)使用高親和度的處理器時，高速緩存的狀態(tài)都基本上已就緒，可以提高效率。在常規(guī)（unicore ）多處理器系統(tǒng)中，提高cache的親和力可以提高性能。類似的通過對多核處理器性能改進的觀察，是有效多核調(diào)度算法設(shè)計的關(guān)鍵。我們的研究分析了在多核處 理器的高速緩存親和性對性能的影響。我們發(fā)現(xiàn)，在多核單處理器的性能提升并不顯著。與此同時，在多核多處理器的性能提升則是是相當(dāng)明顯。我們評估了在多核處理器的cache親和力對性能的影響。我們研究了多核心單處理器和多核多處理器，無論是利用L1高速緩存的親和力和利用二級緩存親和力的影

5、響。我們假定該緩存的親和力不影響多核處理器的性能：對于多核單處理器-因為重裝的L1緩存狀態(tài)代價很低，在多核多處理器 -由于緩存的共享，處理器間二級緩存的親和力是普遍偏低的。我們的第一個假設(shè)得到了確認(rèn)。高速緩存的親和力對多核單處理器并沒有對程序性能產(chǎn)生影響，調(diào)度時間量小，二 級緩存保留量低，即使在 L1緩存是比較大的情況下也是這樣。盡管從利用高速緩存的親和 力對多核多處理器性能改善的上限值比unicore多處理器低，但仍然顯著：平均11%和最高27%。這種親和力對多核多處理器是值得考慮的。我們的結(jié)論是cache親和性在多核調(diào)度算法將不會對多核單處理器系統(tǒng)產(chǎn)生性能的 差異，但將改善多核多處理器的性

6、能。Torrellas等研究親和度感知調(diào)度對傳統(tǒng)（unicore ）多處理器性能的影響2。根據(jù)他們的研究，親和度感知調(diào)度算法降低緩存缺失多達7-36 %，同時10%更高的性能。Torrellas的研究，衡量一個特定的親和力感知的調(diào)度算法對性能的影響。Constantinou 等考察在多核處理器各核心間遷移的過程中性能的影響3。他們研究預(yù)先將核心L1指令和數(shù)據(jù)高速緩存進行處理，再將進程遷移到新的核心上的性能影響（而不是 直接轉(zhuǎn)移）。對數(shù)據(jù)cache進行預(yù)處理提高了緩存的核心和遷移過程中的親和力。因此，在Constantinou 的研究實驗，有效地測量L1緩存的親和力，在 Constantinou

7、 的研究更好的轉(zhuǎn)移友好的硬件體系結(jié)構(gòu)。利用操作系統(tǒng)對 cache親和性利用要利用cache親和性提高程序的性能要靠操作系統(tǒng)的調(diào)度實現(xiàn)。多核的設(shè)計使得多 線程的并行運行成為可能，但為了提高程序的性能，在如上圖所示的 CPU結(jié)構(gòu)中，6中建立了利用 cache親和性的實時系統(tǒng)調(diào)度算法。 多核架構(gòu)在一個芯片上放置多處理單元，大多數(shù)這樣的芯片核心共享部分或所有片上的 cache。針對之前的工作提出了改善軟實時調(diào)度時實時工作負(fù)載下緩存性能的方法，提出另 外兩個研究問題：（1）如何調(diào)度的實時任務(wù)時自動描述內(nèi)部緩存的行為；（二）如何有效地實施調(diào)度方法，使調(diào)度開銷不抵消任何緩存相關(guān)的獲得的性能提升。這篇論文解決

8、了一 個緩存感知的執(zhí)行 Linux軟實時調(diào)度中的這兩個問題，并表明該調(diào)度算法可以降低共享的 高速緩存缺失率使性能得到改善。在這個論文中，提出了一個緩存感知實時Linux內(nèi)核調(diào)度多核平臺的設(shè)計和實施。我們的重點具體是克服兩個主要障礙：在實踐中使用高速緩存感知的實時調(diào)度；自動緩存 分析和保證執(zhí)行效率。我們的研究結(jié)果表明，多線程任務(wù)可以在合理開銷下自動，準(zhǔn)確地 配置，來在運行時確定的每個作業(yè)集大小。此外，我們已經(jīng)表明，通過允許調(diào)度考慮到上 述的工作集大小配置信息，在實踐中就可以大大改善性能表現(xiàn)。為了使這些性能改進對廣泛的應(yīng)用能實現(xiàn)，芯片制造商必須提供必要的硬件支持。我們的 分析器所需的支持并不復(fù)雜：

9、我們只需要性能計數(shù)器，可用于精確計算共享緩存未命中次 數(shù)。正如前面所說，從英特爾酷睿2芯片轉(zhuǎn)移到新的i7處理器芯片，這些計數(shù)器的效率有所下降。我們認(rèn)為這是一個嚴(yán)重的錯誤。如果芯片制造商真正關(guān)心解決共享緩存的有效使 用問題，那么他們就需要重新考慮它們提供的性能監(jiān)視功能的特征，并確定支持的功能的 特征的集合，這一套標(biāo)準(zhǔn)的設(shè)置應(yīng)隨著定芯片架構(gòu)的發(fā)展保持穩(wěn)，（同樣更普遍可以說高 速緩存管理有關(guān)的硬件支持。）向多核技術(shù)的轉(zhuǎn)變是一個分水嶺，因為它從根本上改變在許多情況下計算平臺“標(biāo) 準(zhǔn)”稱為一個多處理器。在大多數(shù)多核平臺，不同的內(nèi)核共享的片上高速緩存。如果沒有有效的調(diào)度管理，使用緩存可能會導(dǎo)致抖動，嚴(yán)重降

10、低系統(tǒng)性能。事實上，關(guān)于多核平臺 一個最重要的問題是如果高效使用的高速緩存的問題。在本論文中，我們在一軟實時多核 心平臺上解決這個問題，即是對稱和共享最底層高速緩存的結(jié)構(gòu)，如上圖所示。圖中在所有核心共享一個二級緩存。這種架構(gòu)是相當(dāng)普遍的，Sun U1- traSPARC T1和T2處理器包含八個核心共享二級緩存，以及最近發(fā)布的英特爾酷睿i7芯片包含一個由四個核心共享的L3緩存（所有較高級別的緩存都是屬于每個核心的，因此不共享）。通過假設(shè)系統(tǒng)組織成多線程任務(wù)（ MTTs）,其中每個多線程任務(wù)由定期（順序）的 任務(wù)組成，可能有不同的執(zhí)行成本，但共用一個執(zhí)行區(qū)間。多線程任務(wù)可以指明引用相同數(shù)據(jù)集的任

11、務(wù)。（請注意，一個普通的周期性任務(wù)僅僅是一個“單線程”MTT 法）。抽象的多線程任務(wù)使通常只處理順序執(zhí)行的任務(wù)的任務(wù)模型允許并發(fā)執(zhí)行。這是重要的，因為 每個芯片核心數(shù)量的增加，個別核心的處理能力很可能保持不變，因此，多線程任務(wù)對實 現(xiàn)性能提升非常有用。在以前的工作，探討了通過調(diào)整聯(lián)合調(diào)度選擇來調(diào)度軟實時工作負(fù)載時來提升共享 內(nèi)存性能的方法。也就是說，聯(lián)合調(diào)度鼓勵在同一MTT的任務(wù)共同執(zhí)行，抵制會導(dǎo)致共享緩存抖動的任務(wù)。聯(lián)合調(diào)度，通過“任務(wù)推動“，即允許其中一個工作通過將其限期移動 到當(dāng)前的時間來獲得臨時的高優(yōu)先權(quán)。本文解決兩個問題的補充：（1 ）如何在調(diào)度器中自動描述實時任務(wù)緩存行為，而 不需

12、要離線分析工具（2）如何落實上述啟發(fā)式效率，使調(diào)度開銷不抵消任何緩存相關(guān)的性 能提升。7中提出了一個高速緩存感知的調(diào)度策略，通過考慮數(shù)據(jù)重用從而提高高速緩存性能， 聯(lián)合調(diào)度任務(wù)的內(nèi)存足跡，和共享缺失率。建議的調(diào)度策略是通過線程構(gòu)建模塊（TBB）實施的，這是一個由英特爾的多線程調(diào)度庫。實驗結(jié)果表明，該緩存感知任務(wù)調(diào)度策 略實現(xiàn)與原來相比減少高達 45%的執(zhí)行時間。在本文中，我們確定三個主要的高速緩存優(yōu)化中的因素，分別是數(shù)據(jù)重用，內(nèi) 存占用和緩存的一致性。一些以前的工作，考慮這些因素以改善的緩存的利用率。處 理器緩存的親和力調(diào)度旨在通過程根駐留在緩存中線程之間的數(shù)據(jù)重用調(diào)度線據(jù)數(shù)據(jù)。 構(gòu)建緩存共享

13、，利用的潛在的工作重疊，共同合作，預(yù)計線程設(shè)置，以減少內(nèi)存占用。 主題聚類通過聚類共享相同數(shù)據(jù)的線程到最近的核最大限度地減少了一致性的開銷。 實驗結(jié)果表明，CATS可以比只考慮內(nèi)存空間和數(shù)據(jù)的重用調(diào)度性能的提高實現(xiàn)高達 50 %，比只考慮緩存的一致性和數(shù)據(jù)的重用調(diào)度改善高達60%。具體的三大任務(wù)調(diào)度緩存性能方面的考慮：數(shù)據(jù)重用，內(nèi)存大小和連貫性。（1）數(shù)據(jù)重用：最大化的再利用任務(wù)間高速緩存中的數(shù)據(jù)是最簡單的減少高速緩存缺失 的方法。任務(wù)調(diào)度如果不考慮到可能的數(shù)據(jù)重用，緩存缺失可能招致很多冗余數(shù)據(jù)， 搬遷和重新載入數(shù)據(jù)。為了解決這個問題，安排共享相同的數(shù)據(jù)按的任務(wù)按順序執(zhí)行， 重復(fù)使用在緩存中的

14、數(shù)據(jù)。（2）內(nèi)存足跡當(dāng)協(xié)作任務(wù)內(nèi)存足跡占用量比共享緩存容量大，每個協(xié)作任務(wù)可能會取代其他人所需 要的數(shù)據(jù)，導(dǎo)致很多的緩存未命中。為了解決這個問題，調(diào)度程序可以安排共享相同 數(shù)據(jù)的任務(wù)同時更新他們重疊的共享緩存工作集，因此減少了總的工作集大小6。連貫性在CMP中，如果共享數(shù)據(jù)值改變，是在其他核心的私有緩存這些數(shù)據(jù)應(yīng)該是無效復(fù)印 件，并從其它內(nèi)核以下訪問無效的復(fù)制本將成為高速緩存的一致性錯過。可能有很多 高速緩存的一致性如果錯過了合作計劃的任務(wù)經(jīng)常寫寫共享相同的數(shù)據(jù)。為了解決這個問題，很少有共 享數(shù)據(jù)的任務(wù)分配給不同的內(nèi)核，以減少交通一致性。對于如上圖的CPU架構(gòu)，4中建議我們修改多核心處理器，以

15、便使執(zhí)行的程序可以從一個核心迅速遷移到另一個核心上，目的是允許采取順序執(zhí)行的應(yīng)用可以利用片上的L2 cache整體容量上的優(yōu)勢，可以利用全部的L2 cache。它使用了一種親和算法，自動將一個工作集進行分割。經(jīng)表明，該方法在4核CPU或?qū)?核心都適用，認(rèn)為它是可以適應(yīng)更多內(nèi)核。應(yīng)用程序要可以利用轉(zhuǎn)移的優(yōu)勢，要求其工作集具有稱之為"splittability“的性質(zhì)。已經(jīng)表明，“ splittability “是相當(dāng)普遍，如SPEC2000或舊的的基準(zhǔn)。這樣可以提高順序程序的性能同時很少影響其他程序的執(zhí)行效率。我們建議修改多核心處理器，這樣的執(zhí)行可以從一個核心迅速遷移到另一個。 我們的

16、目標(biāo)是允許采取序貫應(yīng)用的整體片上的L2容量上的優(yōu)勢。我們介紹了親和算法，自動分裂一個工作 set.We表明，該方法在4核配置的工程方法。然而, 工程還對2核心配置，我們認(rèn)為它是可以適應(yīng)它的內(nèi)核更大的數(shù)字。應(yīng)用程序 可以利用執(zhí)行移民的優(yōu)勢，如果其工作集展品屬性，我們稱之為“splittability ”。我們已經(jīng)表明，“ splittability”是相當(dāng)普遍，如規(guī)格CPU200C和奧爾登流行的基準(zhǔn)。這項研究表現(xiàn)出一定的順序上的應(yīng)用顯著提高 性能的潛力。但是，執(zhí)行的運移生存能力， 性仍需進一步確認(rèn)。雖然我們沒有考慮任何特定的遷移罰款脈沖氣保價值，一 個隱含的假設(shè)是，脈沖氣保不超過二級錯過了幾十。

17、最佳參數(shù)調(diào)整（的R -窗口的大小，轉(zhuǎn)換過濾器，工作集采樣率）取決于脈沖氣保。如果脈沖氣保小， 例如，脈沖氣保“10，有可能容忍 migrationfrequencies比表2日報道為高。此外，它可能是有用的區(qū)分低罰款和高罰款二級失誤。例如，在應(yīng)用中發(fā)現(xiàn)指 針負(fù)載使用鏈接的數(shù)據(jù)結(jié)構(gòu)通常具有較高的思念處罰。人們可以決定限制具備 了過渡過濾器只從指針負(fù)載要求來更新了觸發(fā)遷移應(yīng)用程序的類。需要進一步 研究，以更好地理解“ splittability ”和途徑揭露它。特別是，有一個與緩存 預(yù)取連接。執(zhí)行遷移并不是為了取代預(yù)取。未來的研究應(yīng)確定如何最好地結(jié)合 預(yù)取和執(zhí)行遷移。不過，目前尚不清楚在多大程度上

18、執(zhí)行遷移是正交的預(yù)取。 從理論上講，還有更多的“ splittability”比可預(yù)測性（如 HalfRandom）。然而，在實踐中，“splittability ”我們觀察到很多國家都從環(huán)形工作集的行 為來上預(yù)取是有可能成功。這可能是執(zhí)行遷移，以此來減少二級失誤，主要是 有趣的使用與數(shù)據(jù)結(jié)構(gòu)的應(yīng)用程序。然而，成“大”緩存預(yù)取留出更多的工作 集的不可預(yù)知的部分房間，可以執(zhí)行遷移以及其他應(yīng)用程序非常有用。至于落實執(zhí)行遷移的復(fù)雜性，最困難不在于遷移控制器，但在允許快速遷移的 硬件支持。特別是，更新的公共汽車直接的實現(xiàn)，在第2.3節(jié)所述，可能會產(chǎn)生一個重要的電力消耗。幾個方向是減少移民沒有過分增加罰

19、款的更新總線帶 寬成為可能。特別是最消耗帶寬寄存器更新。人們可以決定廣播寄存器更新時， 才過渡過濾絕對值低于某一閾值，因為它表明可能遷移。遷移后，有必要播出失蹤寄存器更新。人們可以同時過濾登記注冊一個小更新緩存更新。一個寄存器更新將被送往只有在驅(qū)逐從寄存器更新緩存項。遷移后， 登記冊的更新緩存內(nèi)容將灑在更新公共汽車。雖然執(zhí)行遷移提供了一種解決有 關(guān)工作集展示“ splittability ”緩存壁的問題，我們不認(rèn)為有理由實施單獨執(zhí) 行移民多核心。對于構(gòu)建的主要動機， 荷蘭國際集團一多核心仍然越來越多的工作量和并行應(yīng)用程序的執(zhí)行吞吐量。 然后，執(zhí)行移民來作為獎金。我們相信，執(zhí)行遷移的硬件成本將得

20、到更好的接 受，如果能找到其他優(yōu)勢，迅速遷移到另一個核心執(zhí)行。例如，有人建議，定 期活動遷移到芯片的不同部分允許較高的熱耗散 11 。 另一個有趣的方向，探討的是在執(zhí)行遷移來利用分支預(yù)測表。5 中，分層的多核機器接近理論的性能，要求各相關(guān)非均勻結(jié)構(gòu)的線程和數(shù)據(jù)分布非常小心，以減少高速緩存未命中和NUMA處罰。雖然人們認(rèn)為Ope nMF可以提高一個便攜式的方式對這種架構(gòu)的線程調(diào)度質(zhì)量和線程之間傳送有關(guān)的底層運行時系統(tǒng)數(shù)據(jù)的親和力珍貴的資料，最OpenMP運行時系統(tǒng)卻無法有效地支持極不規(guī)范，大規(guī)模并行應(yīng)用程序在NUMA機器。在本文中，我們提出了一個線程調(diào)度策略適合Ope nMP勺具有不規(guī)則的多層次

21、結(jié)構(gòu)和大規(guī)模的嵌套并行程序的執(zhí)行。我們的政策執(zhí)行的線程分配的最大化屬于同一線程接近平行 截面，并使用 NUMA勺了解工作負(fù)載時，竊取戰(zhàn)略平衡是必要的。它已發(fā)展為一個插件的FORESTGOMP OpenMj平臺TBG的07。我們證明具有高度不規(guī)則的遞歸的OpenMP從表面重建中的應(yīng)用程序的通用并行導(dǎo)致該方法的有效性。我們實現(xiàn)一個沒有應(yīng)用程序級優(yōu)化的16 芯機 14 加速。1 Vahid Kazempour,Alexandra Fedorova and Pouya Alagheband .PerformanceImplicati ons of Cache Affinity on Multicore Processors . Euro-Par 2008-Parallel Processing2 Josep Torrellas, A. Tucker, and A. Gupta. Evaluating the Performance of Cache-Affinity Scheduling in Shared-Memory Multiprocessors. Journal Of Parallel and Distributed Computing, 24):139-151, 19953 T. Constantinou, Y. Sazeides,