多核cache親和性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、結(jié)構(gòu)和大規(guī)模的嵌套并行程序的執(zhí)行。我們的政策執(zhí)行的線程分配的最大化屬于同一線程接近平行 截面，并使用 NUMA勺了解工作負(fù)載時(shí)，竊取戰(zhàn)略平衡是必要的。它已發(fā)展為一個(gè)插件的FORESTGOMP OpenMj平臺(tái)TBG的07。我們證明具有高度不規(guī)則的遞歸的OpenMP從表面重建中的應(yīng)用程序的通用并行導(dǎo)致該方法的有效性。我們實(shí)現(xiàn)一個(gè)沒(méi)有應(yīng)用程序級(jí)優(yōu)化的16 芯機(jī) 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,