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