【正文】 處理器 處理器 處理器 處理器 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 在內(nèi)存分 層中又引 入一層 處理器能 迅速訪問 自己的局 部內(nèi)存 非均勻內(nèi)存訪問的機器和消息傳 遞的機器；為獲得良好的性能 軟件都必須有很好局部性 并行性和數(shù)據(jù)局部性優(yōu)化概述 應(yīng)用中的并行性 ? 并行應(yīng)用性能衡量的兩種標(biāo)準(zhǔn) – 并行覆蓋：整個計算中并行運行部分的百分比 – 并行粒度：處理器上無需和其它處理器同步或通信的計算量 循環(huán)對并行化來說特別有吸引力 ， 循環(huán)可以有許 多次迭代計算 ， 如果這些計算相互獨立 ， 則它們是 并行計算的主要來源 許多控制結(jié)構(gòu)簡單 、 數(shù)據(jù)量大并且耗時長的科學(xué) 和工程應(yīng)用 ， 很容易以較細(xì)粒度被并行化 并行性和數(shù)據(jù)局部性優(yōu)化概述 循環(huán)級并行 耗時的應(yīng)用一般都使用大數(shù)組 ， 導(dǎo)致程序中出現(xiàn) 有許多次迭代的循環(huán) ， 這些迭代經(jīng)常相互獨立 ， 可 以把這類循環(huán)的大量迭代分到各處理器上 并行性和數(shù)據(jù)局部性優(yōu)化概述 循環(huán)級并行 for (i = 0。 i n。 i++) { Z[i] = X[i] ? Y[i]。 Z[i] = Z[i] ? Z[i]。 } // 變換成如下代碼 b = ceil (n/M)。 // M個處理器 , p = 0, 1, …, M ?1 for (i = b?p。 i min(n, b?(p+1))。 i++) { Z[i] = X[i] ? Y[i]。 Z[i] = Z[i] ? Z[i]。 } // 數(shù)據(jù)并行的例子 并行性和數(shù)據(jù)局部性優(yōu)化概述 循環(huán)級并行 – 對并行化來說 ， 任務(wù)級不像循環(huán)級那樣有吸引力 – 對一個程序而言 ， 獨立的任務(wù)數(shù)是一個常數(shù) ， 它不像典型的循環(huán)那樣 ， 獨立的計算單元隨迭代次數(shù)增加而增加 – 任務(wù)通常不是等規(guī)模的 ， 因此很難保證所有的處理器在所有時間都處于忙碌 并行性和數(shù)據(jù)局部性優(yōu)化概述 數(shù)據(jù)局部性 ? 程序局部性 – 大多數(shù)程序的大部分時間在執(zhí)行一小部分代碼 ，并且僅涉及一小部分?jǐn)?shù)據(jù) ? 時間局部性 – 程序訪問的內(nèi)存單元在很短的時間內(nèi)可能再次被程序訪問 ? 空間局部性 – 毗鄰被訪問單元的內(nèi)存單元在很短的時間內(nèi)可能被訪問 并行性和數(shù)據(jù)局部性優(yōu)化概述 數(shù)據(jù)局部性 – 同一個緩存行上的元素一起被使用的情況是空間局部性的一種重要形式 – 這種空間局部性將緩存未命中降到最低 ， 因此使得程度獲得明顯的加速 并行性和數(shù)據(jù)局部性優(yōu)化概述 數(shù)據(jù)局部性 for (i = 0。 i n。 i++) { // 該程序段對向量機來 Z[i] = X[i] ? Y[i]。 // 說是一種優(yōu)化形式 } for (i = 0。 i n。 i++) { Z[i] = Z[i] ? Z[i]。 } for (i = 0。 i n。 i++) { // 有較好的數(shù)據(jù)局部性 Z[i] = X[i] ? Y[i]。 Z[i] = Z[i] ? Z[i]。 } 并行性和數(shù)據(jù)局部性優(yōu)化概述 數(shù)據(jù)局部性 – 對行為主的數(shù)組 Z，根據(jù)空間局部性，顯然更愿意逐行地給該數(shù)組元素置零 for (j = 0。 j n。 j++) for (i = 0。 i n。 i++) for (i = 0。 i n。 i++) for (j = 0。 j n。 j++) Z[i, j] = 0。 Z[i, j] = 0。 – 為了獲得最好的性能，應(yīng)該并行化外循環(huán) b = ceil (n/M)。 for (i = b?p。 i min(n, b?(p+1))。 i++) for (j = 0。 j n。 j++) Z[i, j] = 0。 并行性和數(shù)據(jù)局部性優(yōu)化概述 數(shù)據(jù)局部性 ? 操作在數(shù)組上的數(shù)值應(yīng)用的幾個重要特征 – 數(shù)組代碼經(jīng)常有許多可以并行化的循環(huán) – 當(dāng)循環(huán)有并行性時，它們的迭代可按任意次序執(zhí)行，因而可重新安排計算次序以徹底改進數(shù)據(jù)局部性 – 在創(chuàng)建相互獨立的并行計算大單元時，串行執(zhí)行這些單元往往會產(chǎn)生較好的數(shù)據(jù)局部性 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法 – 該算法是計算密集型的 ， 原則上內(nèi)存訪問不應(yīng)該構(gòu)成瓶頸 – 假定矩陣的布局是行為主 – 假定正好 c個數(shù)組 元素能夠放滿一個 緩存行 ， X的一行僅 散布在 n/c個緩存行上 – 假定緩存足以放下 X所 有的緩存行 ， 讀入 X出 現(xiàn) n2/c次緩存未命中 for (i = 0。 i n。 i++) for (j = 0。 j n。 j++) { Z[i, j] = 。 for (k = 0。 k n。 k++) Z[i, j] = Z[i, j] + X[i, k] ? Y[k, j]。 } 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法 ? 先考慮在單處理器上順序執(zhí)行 j = 0 1 … n ?1 i = 0 X Y 完成 Z一行元 素的計算， 取 Y出現(xiàn)的緩 存未命中次數(shù) 在 n2/c和 n2之間 完成整個 Z， Y未命中次數(shù) 在 n2/c和 n3之間 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法 ? 再考慮在 p個處理器上并行計算 – 把 Z不同行的計算指派到不同處理器 ， 每個處理器計算 Z的連續(xù) n/p行 – 每個處理器訪問矩陣 X和 Z的 n/p行以及整個 Y， 用n3/p次乘加運算來完成對 Z的 n2/p個元素的計算 – 雖然計算時間與 p成比例減少 ， 但通信代價卻與 p成比例增加 ， 因為交付給 p個處理器之緩存的總緩存行是 n2/c + pn2/c – p逼近 n時 ， 計算時間為 O(n2)， 通信代價為 O(n3) 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法的優(yōu)化 – 復(fù)用在緩存的數(shù)據(jù)才代表數(shù)據(jù)局部性好 – 復(fù)用應(yīng)該很快發(fā)生 ， 數(shù)據(jù)才可能還在緩存 – 在上述算法中 ， n2個乘加操作隔開了矩陣 Y中同一個數(shù)據(jù)的復(fù)用 ， n個乘加操作隔開了 Y中同一個緩存行的復(fù)用 – 分塊是重排循環(huán)中迭代次序的一種方法 ， 它能夠極大地改進程序的局部性 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法的優(yōu)化 – 從第 4到 7行的程序計算左上角為 X[ii, kk]和 Y[kk, jj]的兩塊對左上角為 Z[ii, jj]的塊的貢獻 for (ii = 0。 ii n。 ii = ii + b) for (jj = 0。 jj n。 jj = jj + b) for (kk = 0。 kk n。 kk = kk + b) for (i = ii。 i ii + b。 i++) for (j = jj。 j jj + b。 j++) for (k = kk。 k kk + b。 k++) Z[i, j] = Z[i, j] + X[i, k] ? Y[k, j]。 b n 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法的優(yōu)化 – 適當(dāng)選擇 b， 使 3個矩陣都有一個塊可以裝到緩存 – 把 X或 Y一塊取到緩存 ， 會出現(xiàn) b2/c次緩存未命中 – 對于 X和 Y的一對塊 ， 第 4到 7行的程序完成 b3次乘加計算 – 由于整個矩陣乘法需要 n3次乘加計算 ， 則取一對塊到緩存的總次數(shù)是 n3/b3 – 對于 X和 Y的一對塊會有 2b2/c次緩存未命中 ， 因此緩存未命中的總次數(shù)是 2n3/bc – 和 O(n3/c)， 甚至 O(n3)次緩存未命中相比 ， 在 b較大時 ， 2n3/bc能體現(xiàn)出分開方法的好處 習(xí) 題 ? 第一次： , ? 第二次： ,