【正文】 支配 dst，被移動操作可利用空閑資源免費執(zhí)行，在控制流到達(dá) src時獲益 – 若 dst不支配 src， 需要插入被移動操作的拷貝 dst src 全局代碼調(diào)度 向下的代碼移動 從塊 src向下移動到塊 dst， 假定移動未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運行得較快 – 若 dst和 src等價 ， 則被移動操作應(yīng)該被執(zhí)行時 ， 它正好僅被執(zhí)行一次 src dst 全局代碼調(diào)度 向下的代碼移動 從塊 src向下移動到塊 dst， 假定移動未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運行得較快 – 若 dst和 src等價 ， 則被移動操作應(yīng)該被執(zhí)行時 ， 它正好僅被執(zhí)行一次 – src未后支配 dst, 向下移動的代碼經(jīng)常是存儲操作 , 復(fù)制從 src到 dst路徑上的各塊 ， 并把 被移動操作僅放置在 dst的新拷貝中 src dst 全局代碼調(diào)度 B1 B2 B3 B4 a = b + c B5 B6 B7 d = b + c B1 B2 B3 B4 t = b + c a = t B4? B5 d = t d = b + c B6 B6? B7 全局代碼調(diào)度 向下的代碼移動 從塊 src向下移動到塊 dst， 假定移動未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運行得較快 – 若 dst和 src等價 ， 則被移動操作應(yīng)該被執(zhí)行時 ， 它正好僅被執(zhí)行一次 – src未后支配 dst, 向下移動的代碼經(jīng)常是存儲操作 , 復(fù)制從 src到 dst路徑上的各塊 ， 并把 被移動操作僅放置在 dst的新拷貝中 – dst沒有后支配 src， 插入補償代碼以 保證被移動操作在不經(jīng) dst路徑上也執(zhí)行 src dst 全局代碼調(diào)度 更新數(shù)據(jù)相關(guān) 代碼移動會改變操作之間的數(shù)據(jù)相關(guān)關(guān)系 – 兩個對 x的賦值之一可以移動到最上面的基本塊 ，該變換能維持原來程序中的所有相關(guān)性 – 一旦一個對 x的賦值被上移 ， 另一個就不能移動了 – 移動使得 x在最上面塊的出口 由不活躍變成活躍 – 一個變量在某個程序點 活躍 ， 則就不能把對它的投機 定值移到該點的上面 x = 1 x = 2 全局代碼調(diào)度 全局調(diào)度的其他問題 – 程序調(diào)度應(yīng)該使經(jīng)常執(zhí)行的路徑運行得快一些 ， 不經(jīng)常執(zhí)行的路徑可能會因調(diào)度變得慢一些 – 編譯器可用來估計執(zhí)行頻率的技術(shù)有若干種 (1) 內(nèi)循環(huán)比外循環(huán)執(zhí)行得更頻繁 (2) 分支指令往回跳轉(zhuǎn)比不跳轉(zhuǎn)要更經(jīng)常 (3)看守程序出口或異常處理例程的分支語句很少被執(zhí)行 – 最好的頻率估計來自動態(tài)剖析 ， 程序被靜態(tài)插樁以用來運行時記錄條件分支每次的走向 全局代碼調(diào)度 全局調(diào)度的其他問題 ? 最簡單的全局調(diào)度算法也相當(dāng)復(fù)雜 ， 不介紹 ? 在一些全局調(diào)度算法中 ， 循環(huán)迭代的邊界是代碼移動的一種屏障 ， 需循環(huán)展開 for(i = 0。 可以通過把值存在不同的單元來刪除反相關(guān) – 輸出相關(guān) 如果對同一個單元先后寫兩次 。 i + 4 N。 i ++) { S(i)。 i n。 i N。 i ++) A[i] = B[i] + A[i ?2] 寫 A[i]和讀 A[i ?2]的依賴邊上標(biāo)記的迭代次數(shù)差是 2 并行性和數(shù)據(jù)局部性優(yōu)化概述 ? 并行編程模型 – 任務(wù)并行 – 數(shù)據(jù)并行 – 流水線并行 （ 前面幾節(jié)涉及較多 ） ? 本節(jié)內(nèi)容圍繞任務(wù)并行和數(shù)據(jù)并行 – 介紹并行計算機系統(tǒng)結(jié)構(gòu)的概況 – 給出并行化的基本概念 ， 程序循環(huán)的變換 ， 還有對并行化有用的概念 – 類似的考慮怎樣用于優(yōu)化數(shù)據(jù)局部性 – 以矩陣乘算法的優(yōu)化為例 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 對稱多處理器的體系結(jié)構(gòu) 二級 緩存 內(nèi)存 總線 二級 緩存 二級 緩存 二級 緩存 一級 緩存 一級 緩存 一級 緩存 一級 緩存 處理器 處理器 處理器 處理器 多個高性 能處理器 集成在一 塊芯片上 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 對稱多處理器的體系結(jié)構(gòu) 二級 緩存 內(nèi)存 總線 二級 緩存 二級 緩存 二級 緩存 一級 緩存 一級 緩存 一級 緩存 一級 緩存 處理器 處理器 處理器 處理器 多個高性 能處理器 集成在一 塊芯片上 通過共 享內(nèi)存來 進(jìn)行通信 必須在處理器的緩存中 找到它操作的大部分?jǐn)?shù) 據(jù)，以保證性能 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 分布式內(nèi)存機器 總線或其它互連 二級 緩存 二級 緩存 二級 緩存 二級 緩存 一級 緩存 一級 緩存 一級 緩存 一級 緩存 處理器 處理器 處理器 處理器 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 在內(nèi)存分 層中又引 入一層 處理器能 迅速訪問 自己的局 部內(nèi)存 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 分布式內(nèi)存機器 總線或其它互連 二級 緩存 二級 緩存 二級 緩存 二級 緩存 一級 緩存 一級 緩存 一級 緩存 一級 緩存 處理器 處理器 處理器 處理器 局部 內(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。 Z[i] = Z[i] ? Z[i]。 i n。 i n。 i++) for (j = 0。 for (k = 0。 kk n。 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í) 題 ? 第一次： , ? 第二次： ,