【正文】 c和 d分別被分配了 R R R4和 R5 可用來將相鄰基本塊組合成一個(gè)更大基本塊 代碼調(diào)度的約束 一個(gè)基本的機(jī)器模型 ? 機(jī)器模型 M = (R, T) – T：操作類型集 ， 如讀取 、 存儲(chǔ)和算術(shù)運(yùn)算等 – R = [r1, r2, … ]：硬件資源向量集 ， 如內(nèi)存訪問部件 、 算術(shù)運(yùn)算部件和浮點(diǎn)功能部件 ri代表第 i類資源中可用的部件數(shù) – 每個(gè)操作有一組輸入操作數(shù) 、 一組輸出操作數(shù)和一個(gè)資源需求 – 和每個(gè)輸入操作數(shù)相關(guān)的是一個(gè)輸入延遲 – 和每個(gè)輸出操作數(shù)相關(guān)的是一個(gè)輸出延遲 代碼調(diào)度的約束 一個(gè)基本的機(jī)器模型 ? 機(jī)器模型 M = (R, T) – 對(duì)每種操作類型 t， 資源使用由一張二維資源預(yù)留表 RTt來建模 – 條目 RTt[i, j]是 t類型的一個(gè)操作在它被發(fā)射 i時(shí)鐘周期后 ， 使用第 j種資源的部件數(shù) – 對(duì)任何 t、 i和 j， RTt[i, j]必須小于或等于 R[j] 基 本 塊 調(diào) 度 數(shù)據(jù)依賴圖 ? 基本塊由數(shù)據(jù)依賴圖 G = (N, E)來表示 – 結(jié)點(diǎn)集合 N表示該塊的機(jī)器指令中的操作集合 – 有向邊集合 E表示這些操作之間的數(shù)據(jù)相關(guān)約束 ? G的結(jié)點(diǎn)集 N和邊集 E按如下兩步構(gòu)造 – N中的每個(gè)操作 n有一張資源預(yù)留表 RTn， 其值直接就是 n的操作類型的資源預(yù)留表 – 每條邊 e都標(biāo)示有延遲 de， 表示 e的目的結(jié)點(diǎn)必須在它源結(jié)點(diǎn)發(fā)射 de個(gè)時(shí)鐘周期之后才可以發(fā)射 基 本 塊 調(diào) 度 數(shù)據(jù)依賴圖 資源預(yù)留表 alu men LD R2, 0(R1) ST 4(R1), R2 LD R3, 8(R1) ADD R3, R3, R2 ADD R3, R3, R4 ST 0(R7), R7 ST 12(R1), R3 2 2 2 1 1 1 1 1 1 i1 i2 i3 i4 i5 i6 i7 灰色表 示 1 白色表 示 0 操作是全流水 的，只需顯示 在第 1行使用 的資源 基 本 塊 調(diào) 度 基本塊的表調(diào)度 – 關(guān)鍵路徑包括最后 5個(gè)結(jié)點(diǎn) ， 故第 3條指令先調(diào)度 – 再調(diào)度第 1條指令 ， 因?yàn)榈?4條指令還需等 1周期 – 第 4周期調(diào)度 2條 資源預(yù)留表 alu men 調(diào)度表 LD R3, 8(R1) ADD R3, R3, R2 ADD R3, R3, R4 ST 0(R7), R7 ST 12(R1), R3 ST 4(R1), R2 LD R2, 0(R1) 基 本 塊 調(diào) 度 基本塊的表調(diào)度 – 根據(jù)每個(gè)結(jié)點(diǎn)同先前已經(jīng)被調(diào)度的各結(jié)點(diǎn)之間的數(shù)據(jù)相關(guān)約束 ， 來計(jì)算一個(gè)結(jié)點(diǎn)可以執(zhí)行的最早時(shí)間槽 – 這個(gè)結(jié)點(diǎn)所需資源根據(jù)一張資源預(yù)留表來進(jìn)行檢查 ， 該資源預(yù)留表收集了所有到目前為止被占用資源 。 i + 4 N。 } S(i +2)。 i ++) { S(i)。A, amp。 i n。 for (i = 0。 i N。 i ++) { sum = sum + A[i]。 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ù)并行 – 介紹并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的概況 – 給出并行化的基本概念 ， 程序循環(huán)的變換 ， 還有對(duì)并行化有用的概念 – 類似的考慮怎樣用于優(yōu)化數(shù)據(jù)局部性 – 以矩陣乘算法的優(yōu)化為例 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 對(duì)稱多處理器的體系結(jié)構(gòu) 二級(jí) 緩存 內(nèi)存 總線 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 處理器 處理器 處理器 處理器 多個(gè)高性 能處理器 集成在一 塊芯片上 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 對(duì)稱多處理器的體系結(jié)構(gòu) 二級(jí) 緩存 內(nèi)存 總線 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 處理器 處理器 處理器 處理器 多個(gè)高性 能處理器 集成在一 塊芯片上 通過共 享內(nèi)存來 進(jìn)行通信 必須在處理器的緩存中 找到它操作的大部分?jǐn)?shù) 據(jù)，以保證性能 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 分布式內(nèi)存機(jī)器 總線或其它互連 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 處理器 處理器 處理器 處理器 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 在內(nèi)存分 層中又引 入一層 處理器能 迅速訪問 自己的局 部?jī)?nèi)存 并行性和數(shù)據(jù)局部性優(yōu)化概述 多處理器 ? 分布式內(nèi)存機(jī)器 總線或其它互連 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 二級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 一級(jí) 緩存 處理器 處理器 處理器 處理器 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 局部 內(nèi)存 在內(nèi)存分 層中又引 入一層 處理器能 迅速訪問 自己的局 部?jī)?nèi)存 非均勻內(nèi)存訪問的機(jī)器和消息傳 遞的機(jī)器；為獲得良好的性能 軟件都必須有很好局部性 并行性和數(shù)據(jù)局部性優(yōu)化概述 應(yīng)用中的并行性 ? 并行應(yīng)用性能衡量的兩種標(biāo)準(zhǔn) – 并行覆蓋：整個(gè)計(jì)算中并行運(yùn)行部分的百分比 – 并行粒度：處理器上無需和其它處理器同步或通信的計(jì)算量 循環(huán)對(duì)并行化來說特別有吸引力 ， 循環(huán)可以有許 多次迭代計(jì)算 ， 如果這些計(jì)算相互獨(dú)立 ， 則它們是 并行計(jì)算的主要來源 許多控制結(jié)構(gòu)簡(jiǎn)單 、 數(shù)據(jù)量大并且耗時(shí)長(zhǎng)的科學(xué) 和工程應(yīng)用 ， 很容易以較細(xì)粒度被并行化 并行性和數(shù)據(jù)局部性優(yōu)化概述 循環(huán)級(jí)并行 耗時(shí)的應(yīng)用一般都使用大數(shù)組 ， 導(dǎo)致程序中出現(xiàn) 有許多次迭代的循環(huán) ， 這些迭代經(jīng)常相互獨(dú)立 ， 可 以把這類循環(huán)的大量迭代分到各處理器上 并行性和數(shù)據(jù)局部性優(yōu)化概述 循環(huán)級(jí)并行 for (i = 0。 } // 變換成如下代碼 b = ceil (n/M)。 Z[i] = Z[i] ? Z[i]。 // 說是一種優(yōu)化形式 } for (i = 0。 i n。 j n。 i n。 Z[i, j] = 0。 i++) for (j = 0。 i n。 for (k = 0。 ii n。 kk n。 j jj + b。 b n 并行性和數(shù)據(jù)局部性優(yōu)化概述 矩陣乘法算法的優(yōu)化 – 適當(dāng)選擇 b， 使 3個(gè)矩陣都有一個(gè)塊可以裝到緩存 – 把 X或 Y一塊取到緩存 ， 會(huì)出現(xiàn) b2/c次緩存未命中 – 對(duì)于 X和 Y的一對(duì)塊 ， 第 4到 7行的程序完成 b3次乘加計(jì)算 – 由于整個(gè)矩陣乘法需要 n3次乘加計(jì)算 ， 則取一對(duì)塊到緩存的總次數(shù)是 n3/b3 – 對(duì)于 X和 Y的一對(duì)塊會(huì)有 2b2/c次緩存未命中 ， 因此緩存未命中的總次數(shù)是 2n3/bc – 和 O(n3/c)， 甚至 O(n3)次緩存未命中相比 ， 在 b較大時(shí) ， 2n3/bc能體現(xiàn)出分開方法的好處 習(xí) 題 ? 第一次： , ? 第二次： ,