面向計(jì)算機(jī)體系結(jié)構(gòu)的程序優(yōu)化計(jì)算機(jī)科學(xué)導(dǎo)論第七講-文庫吧
2025-07-17 14:46 本頁面
【正文】 – 分布式內(nèi)存機(jī)器 兩類機(jī)器：非均勻內(nèi)存訪問的 機(jī)器和消息傳遞的機(jī)器 為獲得良好的性能，軟件都必 須有很好局部性 基 本 知 識(shí) 總線或其它互連 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 處理器 處理器 處理 器 處理器 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 在內(nèi)存分 層中又引 入一層 處理器能 迅速訪問 自己的局 部?jī)?nèi)存 18 ? 并行計(jì)算的常見方式 – 任務(wù)并行：每個(gè)處理器執(zhí)行不同的任務(wù) – 數(shù)據(jù)并行：把大任務(wù)分別成若干個(gè)相同的子任務(wù) ? 并行應(yīng)用的性能衡量的兩種標(biāo)準(zhǔn) – 并行覆蓋：整個(gè)計(jì)算中并行執(zhí)行部分的百分比 – 并行粒度：處理器上無需和其它處理器同步或通信的計(jì)算量 循環(huán)級(jí)并行 19 ? 循環(huán)級(jí)并行 – 耗時(shí)的應(yīng)用一般都使用大數(shù)組 ， 導(dǎo)致程序中出現(xiàn)有許多次迭代的循環(huán) ， 每次迭代用于計(jì)算數(shù)組中的一個(gè)元素 。 這些迭代經(jīng)常相互獨(dú)立 ， 它們是并行計(jì)算的主要來源 – 可以把這類循環(huán)的大量迭代分到各處理器上 循環(huán)級(jí)并行 20 ? 循環(huán)級(jí)并行 for (i = 0。 i n。 i++) { //計(jì)算向量 X和 Y Z[i] = X[i] ? Y[i]。 //對(duì)應(yīng)元素差的平方 Z[i] = Z[i] ? Z[i]。 } 該循環(huán)可并行執(zhí)行，把它變換成如下代碼。由各 處理器都執(zhí)行這段代碼來完成計(jì)算 b = ceil (n/M)。 // M個(gè)處理器 , 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ù)并行的例子 循環(huán)級(jí)并行 21 ? 循環(huán)級(jí)并行 – 對(duì)并行化來說 ， 任務(wù)級(jí)不像循環(huán)級(jí)那樣有吸引力 – 對(duì)一個(gè)程序而言 ， 獨(dú)立的任務(wù)數(shù)是一個(gè)常數(shù) ， 它不像典型的循環(huán)那樣 ， 獨(dú)立的計(jì)算單元隨迭代次數(shù)增加而增加 – 任務(wù)通常不是等規(guī)模的 ， 因此很難保證所有的處理器在所有時(shí)間都處于忙碌 循環(huán)級(jí)并行 22 程序中的局部性 ? 局部性的表現(xiàn) 大多數(shù)程序的大部分時(shí)間在執(zhí)行一小部分代碼 ， 并且僅涉及一小部分?jǐn)?shù)據(jù) 。 傳統(tǒng) 的 說法 ： 程序 90％ 的時(shí)間消耗在執(zhí)行 10％ 的代碼上 （ 代碼的局部性 ） – 程序經(jīng)常包含許多決不會(huì)執(zhí)行的 代碼 ， 如 由組件和庫構(gòu)建的程序經(jīng)常僅用所提供功能的一小部分 – 程序 運(yùn)行時(shí) ， 通常 僅 一部分代碼被真正執(zhí)行 。 如處理非法輸入和 異常 情況的 代碼 ， 雖對(duì)程序的正確性至關(guān)重要 ， 但它們很少被執(zhí)行 – 程序的大部分時(shí)間消耗在程序中最內(nèi)層循環(huán)和深度遞歸的執(zhí)行上 23 程序中的局部性 ? 兩種局部性 – 時(shí)間局部性 程序運(yùn)行過程中被訪問的內(nèi)存單元 （ 存放代碼或數(shù)據(jù) ） 在很短的時(shí)間內(nèi)可能再次被程序訪問 – 空間局部性 毗鄰被訪問單元的內(nèi)存單元在很短的時(shí)間內(nèi)會(huì)被訪問 – 同一個(gè)緩存行上的元素一起被使用是空間局部性的一種重要形式 。 它能把緩存未命中次數(shù)降到最低 ， 因而使得程序獲得明顯的加速 24 程序中的局部性 ? 局部性與內(nèi)存分層 – 通常 ， 最快的緩存 沒有大到足以把 代碼和數(shù)據(jù) 同時(shí)放在其中 – 從 程序難以 看出哪部分代碼 和數(shù)據(jù) 會(huì)被頻繁使用 – 動(dòng)態(tài)調(diào)整最快緩存的內(nèi)容不可避免 – 把最近使用的指令保存在緩存是一種較好的最優(yōu)化利用內(nèi)存分層的策略 – 改變數(shù)據(jù)布局或計(jì)算次序也可以改進(jìn)程序數(shù)據(jù)訪問的時(shí)間和空間局部性 25 ? 數(shù)據(jù)局部性 計(jì)算向量 X和 Y對(duì)應(yīng)元素差的平方 for (i = 0。 i n。 i++) { // 該程序段對(duì)向量機(jī)來 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]。 } 程序中的局部性 26 ? 數(shù)據(jù)局部性 – 對(duì)行為主的數(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)并行執(zhí)行 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。 程序中的局部性 27 程序中的局部性 例： 一個(gè)結(jié)構(gòu)體大數(shù)組 分拆成若干個(gè)數(shù)組 struct student { int num[10000]。 int num。 char name[10000][20]。 char name[20]。 … … … … } struct student st[10000]。 //非矩陣運(yùn)算的例子 ? 若是順序處理每個(gè)結(jié)構(gòu)體的多個(gè)域 ， 左邊方式的數(shù)據(jù)局部性較好 ? 若是先順序處理每個(gè)結(jié)構(gòu)的 num域 ， 再處理每個(gè)結(jié)構(gòu)的 name域 ， … ， 則右邊方式的數(shù)據(jù)局部性較好 ? 最好是按左邊方式編程 ， 由編譯器決定是否需要把數(shù)據(jù)按右邊方式布局 28 ? 矩陣乘算法 – 計(jì)算 Z = X ? Y， 它們都是 n?n的矩陣 （ 數(shù)組 ） – 矩陣數(shù)據(jù)的布局是行為主 根據(jù)下面公式 ， 當(dāng)使用 X的一行時(shí) ， 需逐列訪問 Y的所有元素 矩陣乘算法及其優(yōu)化 29 Zi,j = Xi,1*Y1,j + ... + Xi,n*Yn,j j = 0, 1, … , n ?1 i = 0 X Y i=n1 ? 矩陣乘算法 – 計(jì)算 Z = X ? Y， 它們都是 n?n的矩陣 （ 數(shù)組 ） – 矩陣數(shù)據(jù)的布局是行為主 矩陣乘算法及其優(yōu)化 30 Zi,j = Xi,1*Y1,j + ... + Xi,n*Yn,j 根據(jù)下面公式 ， 當(dāng)使用 X的一行時(shí) ， 需逐列訪問 Y的所有元素 j = 0, 1, … , n ?1 i = 0 X Y i=n1 ? 矩陣乘算法 – 計(jì)算 Z = X ? Y， 它們都是 n?n的矩陣 （ 數(shù)組 ） – 矩陣數(shù)據(jù)的布局是行為主 矩陣乘算法及其優(yōu)化 31 Zi,j = Xi,1*Y1,j + ... + Xi,n*Yn,j 根據(jù)下面公式 ， 當(dāng)使用 X的一行時(shí) ， 需逐列訪問 Y的所有元素
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1