經(jīng)典：存儲墻問題的思考

1、存儲墻問題的思考存儲墻問題的思考楊學(xué)軍楊學(xué)軍12021/8/6HPCC 09主要內(nèi)容主要內(nèi)容 存儲墻存儲墻提升計算速度的第一難題提升計算速度的第一難題 結(jié)構(gòu)與優(yōu)化結(jié)構(gòu)與優(yōu)化緩解緩解“存儲墻存儲墻”的對策的對策 使能技術(shù)使能技術(shù)解決解決“存儲墻存儲墻”可能的出路可能的出路22021/8/6HPCC 09存儲墻仍然是提升計算速度的第一難題1. Insufficient memory bandwidth2. Ignore performance features3. Ignore Littles Law4. Hide faults in low level5. Over synchronizatio

2、n globally6. Over synchronize communication7. Choose bad algorithms8. Dont rethink algorithms9. Choose “hard” applications10.Use overly-general processors Kathy Yelick (UC Berkeley)ISCA 09 Keynote:Ten Ways to Waste a Parallel Computer32021/8/6HPCC 09存儲墻問題 處理器單個引腳的信號傳輸速度受限處理器單個引腳的信號傳輸速度受限 處理器的引腳數(shù)受限處理

3、器的引腳數(shù)受限IBM Zurich Research Laboratory 200942021/8/6HPCC 09 在結(jié)點(diǎn)內(nèi)部：存儲器讀寫速度遠(yuǎn)遠(yuǎn)低于在結(jié)點(diǎn)內(nèi)部：存儲器讀寫速度遠(yuǎn)遠(yuǎn)低于CPU處理速度，處理速度，90ns VS 0.3ns 在結(jié)點(diǎn)之間：處理器之間的通信速度遠(yuǎn)遠(yuǎn)在結(jié)點(diǎn)之間：處理器之間的通信速度遠(yuǎn)遠(yuǎn)低于本地存儲訪問速度，低于本地存儲訪問速度，2000ns VS 90ns并行計算效率下降，目前大規(guī)模并行計算機(jī)并行計算效率下降，目前大規(guī)模并行計算機(jī)在實(shí)際應(yīng)用中的并行效率在在實(shí)際應(yīng)用中的并行效率在5%左右左右52021/8/6HPCC 09存儲墻問題之存儲墻問題之可能的解決途徑可能的解決

4、途徑體系結(jié)構(gòu)技術(shù)的發(fā)展體系結(jié)構(gòu)技術(shù)的發(fā)展使能技術(shù)使能技術(shù)的的發(fā)展發(fā)展62021/8/6HPCC 09主要內(nèi)容主要內(nèi)容 存儲墻存儲墻提升計算速度的第一難題提升計算速度的第一難題 結(jié)構(gòu)與優(yōu)化結(jié)構(gòu)與優(yōu)化緩解緩解“存儲墻存儲墻”的對策的對策 使能技術(shù)使能技術(shù)解決解決“存儲墻存儲墻”可能的出路可能的出路72021/8/6HPCC 09Multicore puts us on the wrong side of the memory wall. Will CMP ultimately be asphyxiated by the memory wall?（多核將我們放在了存儲墻問題的錯誤一面。多多核將我們放

5、在了存儲墻問題的錯誤一面。多核處理器最終是否會因為存儲墻問題窒息而死？核處理器最終是否會因為存儲墻問題窒息而死？） Thomas Sterling82021/8/6HPCC 09 集中式集中式Cache 純硬件管理，難以實(shí)現(xiàn)大容量純硬件管理，難以實(shí)現(xiàn)大容量 AMD Opteron當(dāng)前主要的片上末級層次存儲器 分布式分布式Cache (Non-Uniform Cache Architecture) 需要軟硬件配合管理，管理復(fù)雜需要軟硬件配合管理，管理復(fù)雜 Texas大學(xué)大學(xué)Austin分校分校 TRIPS 便箋存儲器便箋存儲器 (Scratch-Pad Memory) 純軟件管理，管理復(fù)雜，開銷

6、大純軟件管理，管理復(fù)雜，開銷大 IBM Cyclops64 流寄存器文件流寄存器文件 純軟件管理，隨機(jī)訪問困難純軟件管理，隨機(jī)訪問困難 NUDT FT6492021/8/6HPCC 09馮諾依曼計算機(jī)的固有瓶頸CPUStoretubeVon Neumann bottleneck 數(shù)據(jù)在存儲器中編址數(shù)據(jù)在存儲器中編址存儲，使得數(shù)據(jù)訪問不得存儲，使得數(shù)據(jù)訪問不得不在不在tube中傳送數(shù)據(jù)地址中傳送數(shù)據(jù)地址等等“無用無用”信息。信息。 John Backus 1977 ACM Turing Award Lecture馮馮 諾依曼計算機(jī)簡單模型諾依曼計算機(jī)簡單模型102021/8/6HPCC 09我們

7、歸納了數(shù)據(jù)訪問的六種特性依賴性依賴性重用性重用性相似性相似性親和性親和性一致性一致性生存性生存性112021/8/6HPCC 09這六種數(shù)據(jù)訪問特性并不獨(dú)立，而是相互關(guān)聯(lián)、相這六種數(shù)據(jù)訪問特性并不獨(dú)立，而是相互關(guān)聯(lián)、相輔相成的，它們從不同側(cè)面反映了數(shù)據(jù)訪問的輔相成的，它們從不同側(cè)面反映了數(shù)據(jù)訪問的特征特征時間時間空間空間地址地址值值時間時間空間空間值值地址地址時間時間空間空間地址地址值值122021/8/6HPCC 09依賴性 描述了包含寫訪問的數(shù)據(jù)單元訪問之描述了包含寫訪問的數(shù)據(jù)單元訪問之間的相對順序關(guān)系，約束了程序執(zhí)行的正確性間的相對順序關(guān)系，約束了程序執(zhí)行的正確性a = = a流依賴流依

8、賴 = aa =反依賴反依賴a = a =輸出依賴輸出依賴如果程序某條執(zhí)行路徑上的兩個語句訪問了相同的數(shù)據(jù)單元，如果程序某條執(zhí)行路徑上的兩個語句訪問了相同的數(shù)據(jù)單元，并且至少有一個語句是對這個單元的寫操作，那么這兩個語并且至少有一個語句是對這個單元的寫操作，那么這兩個語句之間存在數(shù)據(jù)依賴。數(shù)據(jù)依賴的約束保證了數(shù)據(jù)按正確的句之間存在數(shù)據(jù)依賴。數(shù)據(jù)依賴的約束保證了數(shù)據(jù)按正確的順序生產(chǎn)和消費(fèi)，保證程序變換不改變用計算結(jié)果表示的程順序生產(chǎn)和消費(fèi)，保證程序變換不改變用計算結(jié)果表示的程序含義序含義讀讀依賴讀讀依賴= a = a132021/8/6HPCC 09依賴性的分析 依賴性的表示依賴性的表示 Wol

9、fe等提出了利用距離向量和方向向量來刻等提出了利用距離向量和方向向量來刻劃循環(huán)嵌套迭代空間中依賴的方法劃循環(huán)嵌套迭代空間中依賴的方法 從循環(huán)嵌套迭代從循環(huán)嵌套迭代i中語句中語句S1到迭代到迭代j中語句中語句S2有依賴有依賴 距離向量：距離向量：d(i,j)k=jk-ik 方向向量：方向向量： “0D(i,j)k= “=”,如果如果d(i,j)k=0 “”,如果如果d(i,j)k0 數(shù)據(jù)依賴圖也是常用的依賴分析和優(yōu)化的表示數(shù)據(jù)依賴圖也是常用的依賴分析和優(yōu)化的表示形式形式142021/8/6HPCC 09依賴性的分析 依賴測試依賴測試 根據(jù)數(shù)組下標(biāo)判斷循環(huán)中對數(shù)組的兩次引用之間根據(jù)數(shù)組下標(biāo)判斷循環(huán)

10、中對數(shù)組的兩次引用之間是否存在依賴是否存在依賴 單下標(biāo)測試單下標(biāo)測試 ZIV測試、測試、SIV 測試和測試和MIV 測試測試 耦合下標(biāo)測試耦合下標(biāo)測試 基于依賴的程序變換基于依賴的程序變換 循環(huán)變換循環(huán)變換 循環(huán)傾斜循環(huán)傾斜 并行化并行化 152021/8/6HPCC 09依賴性的優(yōu)化舉例 在依賴性指導(dǎo)的循環(huán)變換理論下，利用計在依賴性指導(dǎo)的循環(huán)變換理論下，利用計算重組，可以大幅降低算重組，可以大幅降低Cache的失效率的失效率 Chen Ding and Maksim Orlovich The Potential of Computation Regrouping for Improving

11、Locality 162021/8/6HPCC 09重用性 描述了對同一個數(shù)據(jù)單元或相鄰數(shù)據(jù)描述了對同一個數(shù)據(jù)單元或相鄰數(shù)據(jù)單元集合的多次訪問之間的關(guān)系，是數(shù)據(jù)訪單元集合的多次訪問之間的關(guān)系，是數(shù)據(jù)訪問在存儲層次中表現(xiàn)出局部性的前提問在存儲層次中表現(xiàn)出局部性的前提aaa訪存序列訪存序列abab訪存序列訪存序列時間重用性時間重用性空間重用性空間重用性如果兩次數(shù)據(jù)訪問的是同一個數(shù)據(jù)單元或相鄰的數(shù)據(jù)單元集如果兩次數(shù)據(jù)訪問的是同一個數(shù)據(jù)單元或相鄰的數(shù)據(jù)單元集合，那么這兩次數(shù)據(jù)訪問具有重用性。重用性是程序中數(shù)據(jù)合，那么這兩次數(shù)據(jù)訪問具有重用性。重用性是程序中數(shù)據(jù)訪問的固有屬性之一，而局部性是重用性在程序

12、運(yùn)行時在某訪問的固有屬性之一，而局部性是重用性在程序運(yùn)行時在某一級存儲層次中的具體體現(xiàn)一級存儲層次中的具體體現(xiàn)172021/8/6HPCC 09重用性的分析 Wolf等提出了基于矩陣的數(shù)據(jù)重用模型等提出了基于矩陣的數(shù)據(jù)重用模型 針對循環(huán)中的一致生成訪問給出了重用性的針對循環(huán)中的一致生成訪問給出了重用性的分類和求解方法分類和求解方法 區(qū)分了重用性和局部性的不同區(qū)分了重用性和局部性的不同 重用性是程序中數(shù)據(jù)訪問的固有屬性之一，而局重用性是程序中數(shù)據(jù)訪問的固有屬性之一，而局部性是重用性在程序運(yùn)行時在某一級存儲層次中部性是重用性在程序運(yùn)行時在某一級存儲層次中的具體體現(xiàn)的具體體現(xiàn)for (i1=0; i

13、1N1; i1+) for (i2=0; i2N2; i2+) A2i1i1+1 2010H0Hr 自時間重用的條件自時間重用的條件0ker1Hspan 訪問矩陣訪問矩陣自時間重用向量空間自時間重用向量空間182021/8/6HPCC 09重用性的分析 我們將重用性模型擴(kuò)展至了并行程序我們將重用性模型擴(kuò)展至了并行程序 證明了證明了OpenMP程序在程序在Static，chunk1調(diào)度調(diào)度模式下塊邊界定理模式下塊邊界定理 證明了證明了OpenMP程序在程序在Static，chunk=1調(diào)度調(diào)度模式下線程內(nèi)重用與線程間重用的互斥性模式下線程內(nèi)重用與線程間重用的互斥性 通過定義循環(huán)并行化矩陣，我們導(dǎo)

14、出了各種類通過定義循環(huán)并行化矩陣，我們導(dǎo)出了各種類別并行數(shù)據(jù)重用的求解方法別并行數(shù)據(jù)重用的求解方法 針對并行程序的特點(diǎn)，我們增加了重用的一維針對并行程序的特點(diǎn)，我們增加了重用的一維分類分類自自/ /組組時間時間/ /空間空間自自/ /組組時間時間/ /空間空間執(zhí)行體內(nèi)執(zhí)行體內(nèi)/ /執(zhí)行體間執(zhí)行體間#pragma omp parallel forfor (i1=0; i1N1; i1+) for (i2=0; i2N2; i2+) A2i1i1+1 1000LPM 0LPM r 迭代內(nèi)重用的條件迭代內(nèi)重用的條件0ker1LPMspan 循環(huán)并行化矩陣循環(huán)并行化矩陣迭代內(nèi)向量空間迭代內(nèi)向量空間19

15、2021/8/6HPCC 09重用性的優(yōu)化舉例 根據(jù)重用性指導(dǎo)循環(huán)根據(jù)重用性指導(dǎo)循環(huán)Tiling，優(yōu)化，優(yōu)化Cache 單機(jī)性能提高約單機(jī)性能提高約20% 性能隨處理器的增加接近線性性能隨處理器的增加接近線性 Michael E. Wolf and Monica S. LamA Data Locality Optimizing Algorithm202021/8/6HPCC 09相似性 描述了程序的多個執(zhí)行體中對應(yīng)的多個數(shù)據(jù)描述了程序的多個執(zhí)行體中對應(yīng)的多個數(shù)據(jù)單元內(nèi)容之間的關(guān)系，用于優(yōu)化多個執(zhí)行體對存儲單元內(nèi)容之間的關(guān)系，用于優(yōu)化多個執(zhí)行體對存儲器的占用量器的占用量MPI程序程序MPI_In

16、it();a = 1;進(jìn)程進(jìn)程0a = 1;進(jìn)程進(jìn)程1a = 1;相似性相似性當(dāng)同一個程序派生多個執(zhí)行體時，如果這些執(zhí)行體內(nèi)和程序當(dāng)同一個程序派生多個執(zhí)行體時，如果這些執(zhí)行體內(nèi)和程序中某個變量對應(yīng)的多個數(shù)據(jù)單元在同一段代碼的執(zhí)行過程中中某個變量對應(yīng)的多個數(shù)據(jù)單元在同一段代碼的執(zhí)行過程中擁有相同的值，那么對這些數(shù)據(jù)單元的訪問具有相似性。相擁有相同的值，那么對這些數(shù)據(jù)單元的訪問具有相似性。相似的數(shù)據(jù)單元只是在訪問時具有相同的值，而屬于不同的存似的數(shù)據(jù)單元只是在訪問時具有相同的值，而屬于不同的存儲地址儲地址212021/8/6HPCC 09相似性的分析 我們研究了與我們研究了與“相似相似”互補(bǔ)的另一

17、個概念互補(bǔ)的另一個概念“差異差異” 建立了程序中的差異傳播模型建立了程序中的差異傳播模型 根據(jù)差異在程序中的傳播類型對其進(jìn)行了根據(jù)差異在程序中的傳播類型對其進(jìn)行了分類分類差異的分類差異的分類原生差異原生差異繼生差異繼生差異數(shù)據(jù)流生差異數(shù)據(jù)流生差異控制流生差異控制流生差異222021/8/6HPCC 09相似性的分析 通過前向數(shù)據(jù)流分析的方法研究了數(shù)據(jù)流通過前向數(shù)據(jù)流分析的方法研究了數(shù)據(jù)流生差異的求解方法生差異的求解方法 通過后向數(shù)據(jù)流分析的方法研究了控制流通過后向數(shù)據(jù)流分析的方法研究了控制流生差異的求解方法生差異的求解方法 基于加權(quán)依賴圖研究了數(shù)組元素間的差異基于加權(quán)依賴圖研究了數(shù)組元素間的差

18、異傳播規(guī)律傳播規(guī)律232021/8/6HPCC 09相似性的優(yōu)化舉例 共享具有相似性的數(shù)據(jù)，緩解共享共享具有相似性的數(shù)據(jù)，緩解共享Cache和共享主存中的數(shù)據(jù)保存量和共享主存中的數(shù)據(jù)保存量 優(yōu)化共享優(yōu)化共享Cache時，加速比達(dá)到時，加速比達(dá)到1.2775 優(yōu)化共享主存時，加速比達(dá)到優(yōu)化共享主存時，加速比達(dá)到4.2126242021/8/6HPCC 09親和性 描述了數(shù)據(jù)單元在多個處理器中訪問頻度之描述了數(shù)據(jù)單元在多個處理器中訪問頻度之間的關(guān)系，決定了數(shù)據(jù)分布對處理器訪問性能的影響間的關(guān)系，決定了數(shù)據(jù)分布對處理器訪問性能的影響CPU 0CPU 1abaabbbaa對對CPU 0的親和性更強(qiáng)的親

19、和性更強(qiáng)b對對CPU 1的親和性更強(qiáng)的親和性更強(qiáng)給定多個處理器，一個數(shù)據(jù)單元被某個處理器訪問得越頻繁，給定多個處理器，一個數(shù)據(jù)單元被某個處理器訪問得越頻繁，該數(shù)據(jù)對這個處理器的親和性就越強(qiáng)。在分布存儲結(jié)構(gòu)中，該數(shù)據(jù)對這個處理器的親和性就越強(qiáng)。在分布存儲結(jié)構(gòu)中，這個數(shù)據(jù)單元越靠近這個處理器，系統(tǒng)對這個數(shù)據(jù)單元的訪這個數(shù)據(jù)單元越靠近這個處理器，系統(tǒng)對這個數(shù)據(jù)單元的訪問開銷就越小。同時，當(dāng)某個數(shù)據(jù)單元對多個處理器都表現(xiàn)問開銷就越小。同時，當(dāng)某個數(shù)據(jù)單元對多個處理器都表現(xiàn)出較強(qiáng)的親和性時，就容易發(fā)生數(shù)據(jù)在處理器間的抖動問題出較強(qiáng)的親和性時，就容易發(fā)生數(shù)據(jù)在處理器間的抖動問題252021/8/6HPCC

20、 09親和性的分析 我們定量分析了數(shù)據(jù)訪問的親和性我們定量分析了數(shù)據(jù)訪問的親和性 從單個處理器訪問數(shù)據(jù)的角度定義了縱直親和度從單個處理器訪問數(shù)據(jù)的角度定義了縱直親和度 從多個處理器競爭訪問數(shù)據(jù)的角度了水平親和度從多個處理器競爭訪問數(shù)據(jù)的角度了水平親和度262021/8/6HPCC 09親和性的分析 縱直親和度的計算縱直親和度的計算 證明了數(shù)組訪問縱直親和度與訪問元素個數(shù)之證明了數(shù)組訪問縱直親和度與訪問元素個數(shù)之間的關(guān)系間的關(guān)系 通過極大迭代點(diǎn)法子空間集合導(dǎo)出了縱直親和通過極大迭代點(diǎn)法子空間集合導(dǎo)出了縱直親和度的計算度的計算 水平親和度的計算水平親和度的計算 證明了水平親和度等于兩兩處理器的數(shù)據(jù)

21、訪問證明了水平親和度等于兩兩處理器的數(shù)據(jù)訪問次數(shù)的乘積之和，揭示了水平親和度的本質(zhì)次數(shù)的乘積之和，揭示了水平親和度的本質(zhì) 證明了水平親和度和縱直親和度的定量關(guān)系證明了水平親和度和縱直親和度的定量關(guān)系272021/8/6HPCC 09親和性的優(yōu)化舉例 我們面向親和性問題優(yōu)化分布我們面向親和性問題優(yōu)化分布Cache中的中的數(shù)據(jù)分布數(shù)據(jù)分布 系統(tǒng)性能平均增長系統(tǒng)性能平均增長6.24%282021/8/6HPCC 09一致性 描述了數(shù)據(jù)的單個或多個副本訪問的數(shù)據(jù)內(nèi)容描述了數(shù)據(jù)的單個或多個副本訪問的數(shù)據(jù)內(nèi)容之間的關(guān)系，影響著程序執(zhí)行的正確性之間的關(guān)系，影響著程序執(zhí)行的正確性CPU 0CPU 1Cache

22、Cache主存主存a一致性一致性aa如果系統(tǒng)中對數(shù)據(jù)單個或多個副本的多次訪問的值與程序的如果系統(tǒng)中對數(shù)據(jù)單個或多個副本的多次訪問的值與程序的行為不一致，那么它們就違反了數(shù)據(jù)訪問的一致性。行為不一致，那么它們就違反了數(shù)據(jù)訪問的一致性。Cache 一致性和存儲一致性是系統(tǒng)設(shè)計的重要方面，對軟件的編程一致性和存儲一致性是系統(tǒng)設(shè)計的重要方面，對軟件的編程正確性和硬件的運(yùn)行效率都有著重要的影響正確性和硬件的運(yùn)行效率都有著重要的影響292021/8/6HPCC 09一致性的分析 Cache一致性一致性決定了讀操作返回什么值，決定了讀操作返回什么值，使多個處理器看到的數(shù)據(jù)是一致的使多個處理器看到的數(shù)據(jù)是一致

23、的 最早的最早的Cache一致性協(xié)議是目錄協(xié)議，一致性協(xié)議是目錄協(xié)議，IBM 3081 Goodman 等最早描述了基于偵聽協(xié)議的等最早描述了基于偵聽協(xié)議的Cache Agarwal 等提出了分布目錄的思想，用于構(gòu)建可擴(kuò)等提出了分布目錄的思想，用于構(gòu)建可擴(kuò)展的展的Cache 一致性協(xié)議一致性協(xié)議302021/8/6HPCC 09一致性的分析 Dubois 等提出了弱一致性模型的思想等提出了弱一致性模型的思想 Gharachorloo 等提出了第一個釋放一致性模等提出了第一個釋放一致性模型型 為了提高性能，兩種模型都放松了對為了提高性能，兩種模型都放松了對RW 和和RR順序的要求順序的要求 存儲

24、一致性存儲一致性決定寫操作的數(shù)什么時候決定寫操作的數(shù)什么時候能夠被讀返回，使得多個處理器什么時候能夠被讀返回，使得多個處理器什么時候看到的數(shù)據(jù)是一致的看到的數(shù)據(jù)是一致的 Lamport 第一次介紹了順序一致性模型第一次介紹了順序一致性模型 嚴(yán)格保持嚴(yán)格保持RW, RR, WR, WW四種順序四種順序312021/8/6HPCC 09一致性的分析 首屆全國百篇優(yōu)秀博士論文獲得者胡偉武首屆全國百篇優(yōu)秀博士論文獲得者胡偉武關(guān)于存儲一致性的研究關(guān)于存儲一致性的研究利用集合論中序關(guān)系的一些基本概念和結(jié)果，利用集合論中序關(guān)系的一些基本概念和結(jié)果，研究了有關(guān)順序一致共享存儲系統(tǒng)中的亂序執(zhí)研究了有關(guān)順序一致共

25、享存儲系統(tǒng)中的亂序執(zhí)行技術(shù)的基本理論行技術(shù)的基本理論 給出了共享存儲系統(tǒng)中判斷一個執(zhí)行正確與否的充給出了共享存儲系統(tǒng)中判斷一個執(zhí)行正確與否的充要條件要條件 給出了在共享存儲系統(tǒng)中保證一個執(zhí)行正確的訪存給出了在共享存儲系統(tǒng)中保證一個執(zhí)行正確的訪存次序條件次序條件 在執(zhí)行正確性模型的基礎(chǔ)上，提出了一種亂序執(zhí)行在執(zhí)行正確性模型的基礎(chǔ)上，提出了一種亂序執(zhí)行的方案的方案322021/8/6HPCC 09一致性的優(yōu)化舉例 胡偉武的研究中，在順序一致共享存儲系統(tǒng)中胡偉武的研究中，在順序一致共享存儲系統(tǒng)中使用亂序執(zhí)行技術(shù)，系統(tǒng)效能提高使用亂序執(zhí)行技術(shù)，系統(tǒng)效能提高50%左右左右 胡偉武、夏培肅胡偉武、夏培肅順

26、序一致共享存儲系統(tǒng)中的順序一致共享存儲系統(tǒng)中的亂序執(zhí)行技術(shù)亂序執(zhí)行技術(shù)模擬實(shí)現(xiàn)模擬實(shí)現(xiàn)332021/8/6HPCC 09生存性 描述了多個數(shù)據(jù)訪問的活躍程度之間的關(guān)系，描述了多個數(shù)據(jù)訪問的活躍程度之間的關(guān)系，是資源分配類問題求解的重要約束是資源分配類問題求解的重要約束a =b = = a = ba = = a b = = ba與與b的活躍的活躍周期相交周期相交a與與b的活躍的活躍周期不相交周期不相交如果多個數(shù)據(jù)的生命周期重疊，那么它們在程序運(yùn)行過程中如果多個數(shù)據(jù)的生命周期重疊，那么它們在程序運(yùn)行過程中同時活躍，表現(xiàn)出對某些資源占用的互斥性。因此，生存性同時活躍，表現(xiàn)出對某些資源占用的互斥性。因

27、此，生存性是很多資源分配類問題的重要約束，如寄存器分配等是很多資源分配類問題的重要約束，如寄存器分配等342021/8/6HPCC 09生存性的描述 相干圖（相干圖（Interference Graph) 每個結(jié)點(diǎn)表示一個數(shù)據(jù)的生存期每個結(jié)點(diǎn)表示一個數(shù)據(jù)的生存期 結(jié)點(diǎn)的權(quán)值表示對應(yīng)數(shù)據(jù)對象的大小結(jié)點(diǎn)的權(quán)值表示對應(yīng)數(shù)據(jù)對象的大小 如果兩個生存期可能同時存活如果兩個生存期可能同時存活( (相干相干) )，用一條邊，用一條邊相連相連 運(yùn)用運(yùn)用 標(biāo)量寄存器分配：對應(yīng)到對相干圖的圖著色問題標(biāo)量寄存器分配：對應(yīng)到對相干圖的圖著色問題 聚合數(shù)據(jù)對象聚合數(shù)據(jù)對象( (數(shù)組，流數(shù)組，流) )存儲分配：對應(yīng)到對相

28、存儲分配：對應(yīng)到對相干圖的區(qū)間著色干圖的區(qū)間著色問題問題352021/8/6HPCC 09生存性的分析 我們研究了面向嵌入式應(yīng)用的便箋存儲器分配問題我們研究了面向嵌入式應(yīng)用的便箋存儲器分配問題 大部分嵌入式應(yīng)用的相干圖滿足包含相干性大部分嵌入式應(yīng)用的相干圖滿足包含相干性 我們首次證明了滿足包含相干性的相干圖為置換圖我們首次證明了滿足包含相干性的相干圖為置換圖(Permutation Graph) 首次提出了一個線性時間復(fù)雜性的，基于置換圖著色的首次提出了一個線性時間復(fù)雜性的，基于置換圖著色的便箋存儲器分配算法便箋存儲器分配算法 該算法在大部分嵌入式應(yīng)用相干圖上能取得最優(yōu)，相對該算法在大部分嵌入

29、式應(yīng)用相干圖上能取得最優(yōu)，相對國際最新的基于超完美圖國際最新的基于超完美圖(Superperfect Graph)的算法，的算法，復(fù)雜性更低，性能更好復(fù)雜性更低，性能更好362021/8/6HPCC 09生存性的分析 我們研究了面向流應(yīng)用的流寄存器文件分配問題我們研究了面向流應(yīng)用的流寄存器文件分配問題 首次提出了一個基于存儲器著色的流寄存器文件分配框架首次提出了一個基于存儲器著色的流寄存器文件分配框架 巧妙地將開發(fā)復(fù)用和并行整合到對相干圖的操作中巧妙地將開發(fā)復(fù)用和并行整合到對相干圖的操作中 首次證明了絕大部分流應(yīng)用的相干圖為可比圖首次證明了絕大部分流應(yīng)用的相干圖為可比圖(comparabili

30、ty graph)，或可以降解為多個可比子圖，或可以降解為多個可比子圖 首次將流寄存器文件分配問題建模為最佳有向路徑尋找問首次將流寄存器文件分配問題建模為最佳有向路徑尋找問題，提出了一個最優(yōu)或近似最優(yōu)的流寄存器文件分配算法題，提出了一個最優(yōu)或近似最優(yōu)的流寄存器文件分配算法 該算法相對國際上普遍采用的基于該算法相對國際上普遍采用的基于Bin-Packing的的First-Fit算法，具有更好的性能算法，具有更好的性能372021/8/6HPCC 09生存性的優(yōu)化舉例 我們算法的效果我們算法的效果 能能在除在除QMR外的所有已有實(shí)際流應(yīng)用相干圖上外的所有已有實(shí)際流應(yīng)用相干圖上取得最優(yōu)流寄存器文件分

31、配取得最優(yōu)流寄存器文件分配(用用C表示表示) 在在QMR上，能取得近似最優(yōu)分配上，能取得近似最優(yōu)分配(用用F表示表示)382021/8/6HPCC 09生存性的優(yōu)化舉例 在隨機(jī)產(chǎn)生的在隨機(jī)產(chǎn)生的1200個滿足流應(yīng)用特性的相干圖中，個滿足流應(yīng)用特性的相干圖中，我們的算法在我們的算法在98%以上的圖中能取得最優(yōu)，以上的圖中能取得最優(yōu)，而而First-Fit只在約只在約25%的圖中能取得最優(yōu)的圖中能取得最優(yōu)392021/8/6HPCC 09綜合考慮六種數(shù)據(jù)訪問特性傳統(tǒng)傳統(tǒng)優(yōu)化技術(shù)優(yōu)化技術(shù)往往只考慮往往只考慮單一單一數(shù)據(jù)訪問性質(zhì)數(shù)據(jù)訪問性質(zhì)被優(yōu)化的性質(zhì)其它性質(zhì)綜合度量六種綜合度量六種數(shù)據(jù)訪問特性數(shù)據(jù)訪

32、問特性和諧的和諧的優(yōu)化算法優(yōu)化算法新的軟硬件配新的軟硬件配合的體系結(jié)構(gòu)合的體系結(jié)構(gòu)402021/8/6HPCC 09主要內(nèi)容主要內(nèi)容 存儲墻存儲墻提升計算速度的第一難題提升計算速度的第一難題 結(jié)構(gòu)與優(yōu)化結(jié)構(gòu)與優(yōu)化緩解緩解“存儲墻存儲墻”的對策的對策 使能技術(shù)使能技術(shù)解決解決“存儲墻存儲墻”可能的出路可能的出路412021/8/6HPCC 09一則新聞 2009年年9月月1日英國工程和物理科學(xué)研究委日英國工程和物理科學(xué)研究委員會員會EPSRC出資出資6 million研制光計算機(jī)研制光計算機(jī) 研究單位：帝國理工學(xué)院研究單位：帝國理工學(xué)院 & 英國皇后大學(xué)英國皇后大學(xué) 關(guān)鍵部分：納米等離子

33、器件關(guān)鍵部分：納米等離子器件 應(yīng)用：未來超快計算機(jī)應(yīng)用：未來超快計算機(jī) 時間：為期時間：為期6年年該項目圍繞納米光源、納米光調(diào)制器、該項目圍繞納米光源、納米光調(diào)制器、納米光放大器等展開研究，第一階段納米光放大器等展開研究，第一階段旨在旨在芯片間光互連領(lǐng)域取得重要突破領(lǐng)域取得重要突破422021/8/6HPCC 09芯片間光互連是解決存儲墻問題芯片間光互連是解決存儲墻問題最具潛力的技術(shù)之一最具潛力的技術(shù)之一銅互連銅互連光互連光互連432021/8/6HPCC 09光互連的優(yōu)勢物理屬性物理屬性頻率高頻率高多維多重復(fù)用多維多重復(fù)用弱衰減弱衰減自由空間傳播自由空間傳播應(yīng)用潛力應(yīng)用潛力傳輸帶寬高傳輸帶寬

34、高并行通信并行通信遠(yuǎn)距離通信遠(yuǎn)距離通信動態(tài)互連動態(tài)互連/ /可重構(gòu)可重構(gòu)光互連的物理依據(jù)光互連的物理依據(jù)光互連光互連 V.S. 電互連電互連442021/8/6HPCC 09光互連在計算機(jī)系統(tǒng)中的應(yīng)用 機(jī)柜間光互連的應(yīng)用已經(jīng)非常廣泛機(jī)柜間光互連的應(yīng)用已經(jīng)非常廣泛 板間光互連的應(yīng)用正在逐漸興起板間光互連的應(yīng)用正在逐漸興起 芯片間光互連技術(shù)具備解決存儲墻問題的芯片間光互連技術(shù)具備解決存儲墻問題的巨大潛力，仍處于探索階段巨大潛力，仍處于探索階段機(jī)柜間機(jī)柜間板間板間芯片間芯片間452021/8/6HPCC 09芯片間光互連技術(shù)的難點(diǎn) 現(xiàn)有光互連器件主要基于現(xiàn)有光互連器件主要基于III-V、II-VI族

35、化合物族化合物 機(jī)柜間、板間光互連用到的光收發(fā)器與調(diào)制器等機(jī)柜間、板間光互連用到的光收發(fā)器與調(diào)制器等 這些技術(shù)應(yīng)用于芯片間光互連的問題這些技術(shù)應(yīng)用于芯片間光互連的問題 材料材料昂貴，不兼容昂貴，不兼容CMOS工藝工藝 器件尺寸較大器件尺寸較大 器件功耗器件功耗較大較大芯片間光互連研究的關(guān)鍵芯片間光互連研究的關(guān)鍵硅光器件技術(shù)硅光器件技術(shù)462021/8/6HPCC 09硅光器件技術(shù)取得一系列突破 2004年年 Intel 1GHz硅光硅光子調(diào)制器子調(diào)制器 Nature 此前的記錄為此前的記錄為20MHz 提高了提高了50倍倍 2005年年 Intel 硅基拉曼硅基拉曼激光源激光源Nature 單

36、模模式下，單模模式下，80MHz激激光線寬光線寬 光學(xué)性質(zhì)優(yōu)良光學(xué)性質(zhì)優(yōu)良472021/8/6HPCC 09硅光器件技術(shù)取得一系列突破 2006年年 美國美國Cornell大學(xué)大學(xué) 寬帶光放大器寬帶光放大器 Nature 極大地拓寬了光信號放大極大地拓寬了光信號放大和變換的波長范圍和變換的波長范圍 顯著提高了硅基光集成電路顯著提高了硅基光集成電路的信號處理的信號處理能力能力 2008年年 Intel 硅光子探測器硅光子探測器Nature 340GHz增益帶寬積增益帶寬積 性能與傳統(tǒng)的商業(yè)化光性能與傳統(tǒng)的商業(yè)化光探測器相當(dāng)探測器相當(dāng)482021/8/6HPCC 09硅光器件技術(shù)取得一系列突破 2

37、008年年 IBM 最小的光開關(guān)最小的光開關(guān)Nature Photonics 器件尺寸：器件尺寸：45um x 22um 吞吐率：吞吐率：1Tbps 開關(guān)延遲：開關(guān)延遲：2ns 誤碼率：誤碼率：10-12 交調(diào)失真：交調(diào)失真：-25dB492021/8/6HPCC 09國際上芯片間光互連的研究項目 自自1998年以來，美國年以來，美國DAPRA先后投入先后投入了了2億億6千多千多萬美元用于光互連相關(guān)的項目萬美元用于光互連相關(guān)的項目研究研究，其中，其中4500萬美萬美元用于元用于2003至至2007年的年的芯片間光互連研究芯片間光互連研究 502021/8/6HPCC 09國際上芯片間光互連的研

38、究項目 美國：美國：UNIC項目項目 2007-2012，美國，美國DAPAR & SUN 4700萬美元萬美元 高帶寬、低延遲、低功耗、高帶寬、低延遲、低功耗、CMOS兼容，片內(nèi)兼容，片內(nèi)及片間光互連技術(shù)及片間光互連技術(shù) 美國其它美國其它多所企業(yè)和高校研究機(jī)構(gòu)參與多所企業(yè)和高校研究機(jī)構(gòu)參與512021/8/6HPCC 09國際上芯片間光互連的研究項目 歐盟：歐盟：OPERA2015 合作計劃合作計劃 2005年啟動，歐盟多個國家參與年啟動，歐盟多個國家參與 旨在通過加強(qiáng)光學(xué)與光子學(xué)領(lǐng)域的合作，提高旨在通過加強(qiáng)光學(xué)與光子學(xué)領(lǐng)域的合作，提高歐洲在信息技術(shù)領(lǐng)域的綜合影響力歐洲在信息技術(shù)領(lǐng)域

39、的綜合影響力 數(shù)十個芯片間光互連相關(guān)項目在研或已完成數(shù)十個芯片間光互連相關(guān)項目在研或已完成 歐盟：歐盟：HELIOS項目項目 2008-2012，耗資，耗資1200萬歐元萬歐元 解決光器件的解決光器件的CMOS工藝制備與集成問題工藝制備與集成問題 40Gb/s調(diào)制器、調(diào)制器、10 x10Gb/s收發(fā)器收發(fā)器 等光器件等光器件522021/8/6HPCC 09 日本日本 ：Keisoku 10PFLOPS超級計算機(jī)超級計算機(jī)計劃計劃 NEC等預(yù)測到等預(yù)測到2010年年CPU的的處理能力將達(dá)到處理能力將達(dá)到100GFlops。CPU與存儲器之間需要至少與存儲器之間需要至少25000根數(shù)據(jù)傳輸線才能滿根數(shù)據(jù)傳輸線才能滿足足CPU的處理速度的處理速度 目標(biāo)是實(shí)現(xiàn)目標(biāo)是實(shí)現(xiàn)CPU和存儲器之和存儲器之間間1000個光通道，每個通道個光