高性能計算機的體系結構與程序優(yōu)化(存儲版)
【正文】 可取入 cache的塊狀矩陣，避免全行或全列的讀寫，以增強時間局部性 數組合并的例子 /* Before: 2 sequential arrays */ int val[SIZE]。 improve spatial locality 循環(huán)交換的例子 /* Before */ for (k = 0。 k 100。 i = i+1) for (j = 0。 /* After */ for (i = 0。 i = i+1) for (j = 0。 }。 j min(jj+B1,N)。 B稱為 分塊因子 Blocking Factor ? 不命中數從 2N3 + N2 降到 2N3/B +N2 ? 但還存在因沖突導致的不命中 減少因分塊導致的沖突不命中 ? 需要對分塊后形成的子矩陣進行重新布置 B loc kin g Fa ct or Miss Rate00. 050. 10 50 100 150F ull y A ss oc i ative C ach e D ire ct M a pp ed Ca c he 分塊的性能提高 ? 矩陣乘法： N=500 ? 在 i860上 –分塊前 ， 運行時間為 –分塊后 ， 運行時間為 ， 加速比 ? 在 Pentium 166MMX上 –分塊前 ， 運行時間為 –分塊后 ， 運行時間為 ， 加速比 多體交叉并行存儲系統(tǒng) ? 提高主存帶寬的重要途徑 –多個獨立的存儲體，統(tǒng)一編址，同時工作 –訪問均勻地分布在所有體內時，帶寬線性提高 ? 地址分配方式： word interleave 000000 000001 000002 000003 000004 000005 000006 000007 FFFFFF FFFFFE FFFFFD FFFFFC M0 M1 M2 M3 并行存儲器中的訪問沖突 ? 基本條件：體數不小于訪存所需要的時鐘周期數，以保證順序訪問時不會有體沖突 ? 體數增大時，沖突的機會會少一些，但成本增加了 ? 體數正好等于訪存周期數時，有下面的結論 ? 考慮固定步長的訪問序列 A, A+S, A+2S, A+3S, ... ? 若一共有 N個存儲模塊，則該訪問序列集中在 ? 若 GCD(N, S) = 1, 則沖突訪問的概率最小 ? 因為 N一般是 2的冪次，所以 S最好不是 2的冪次 N GCD(N, S) 個體內 對數組元素的沖突訪問 ? 在 C語言中，數組元素按行存放，按列訪問時會產生沖突 ? 在 FORTRAN中，按列存放，按行訪問時會產生沖突 ? 其它導致沖突的情形 –矩陣中的一個長方形塊 – FFT算法中存取步長依次為 2i, i = 0, 1, 2, … ? 減少沖突的方法（與 cache優(yōu)化類似） –循環(huán)交換、數組加邊 并行處理概述 ? 利用多個部件完成同一個任務 ? 并行處理的好處 –提高性能：縮短解題時間，擴大解題規(guī)模 –降低成本：與同樣性能的單機相比 –容錯：更高的可用性 ? 并行處理的層次 –處理機內：指令級并行，多功能部件 –處理機間：多處理機，多計算機 多機并行的基本形式 ? 按指令流與數據流的數量來劃分 –單指令流多數據流（ SIMD） –多指令流多數據流（ MIMD） ? 按機間的互連方式來劃分 –總線結構、交叉開關、網格結構、超立方體 –樹型結構、星型結構 ? 按存儲器的組織方式來劃分 –集中式存儲，通常是為多個處理機共享 –分布式存儲，通常是各個處理機私有的 兩種基本的結構 互連網絡（總線、開關等） P1 Pn M1 Mn 分布存儲的結構 適合任務間并行 互連網絡（總線、開關等） P1 Pn M1 Mn 共享存儲的結構 適合任務間、任務內并行 并行處理的過程：矩陣乘法 ? A ? B = C的過程可分為四個獨立的部分： Ai ? B = Ci， i = 1, 2, 3, 4 ? 每部分包含的運算可由一臺處理機單獨完成 ? 在集中存儲的系統(tǒng)中，同時訪問 B會導致沖突 ? 在分布存儲的系統(tǒng)中， B的分散存儲會導致通信 A B C X = A1 A2 A3 A4 C1 C2 C3 C4 并行處理的性能 ? 加速比：串行計算時間除以并行計算時間 ? 加速比小于處理單元數目的原因： –存在不可并行成分： Speedup 1/s –負載不均衡：有些處理機沒事做 –通信開銷：包括傳遞消息、訪存沖突等 –同步開銷：為了步調一致，必須相互等待 ? 極端的情況：并行后的性能比單機還差 ? 也可能出現超線性的加速比 并行粒度：在哪個級別上并行？ ? 子任務級的并行（粗粒度） –例如：方位 FFT、距離 FFT、距離 IFFT、方位 IFFT各由一個處理機完成，形成宏觀流水 –子任務的運算量差別較大時，不易實現負載的平衡 ? 數據級的并行（中等粒度或細粒度） –對問題相關的數據場進行劃分，每個處理器負責整個數據場的一小部分 –各部分間耦合較多時，對存儲器及互連網絡的性能要求較高 并行算法設計 ? 并行算法設計的目標
教學課件相關推薦
鄂ICP備17016276號-1