【文章內(nèi)容簡介】 ， 則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí) ， 它正好僅被執(zhí)行一次 – 若 src未后支配 dst， 被移動(dòng)操作可利用空閑資源免費(fèi)執(zhí)行 ， 在控制流到達(dá) src時(shí)獲益 dst src 全局代碼調(diào)度 向上的代碼移動(dòng) 從塊 src向上移動(dòng)到塊 dst， 假定移動(dòng)未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運(yùn)行得較快 – 若 dst和 src等價(jià) ， 則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí) ， 它正好僅被執(zhí)行一次 – 若 src未后支配 dst，被移動(dòng)操作可利用空閑資源免費(fèi)執(zhí)行，在控制流到達(dá) src時(shí)獲益 – 若 dst不支配 src， 需要插入被移動(dòng)操作的拷貝 dst src 全局代碼調(diào)度 向下的代碼移動(dòng) 從塊 src向下移動(dòng)到塊 dst， 假定移動(dòng)未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運(yùn)行得較快 – 若 dst和 src等價(jià) ， 則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí) ， 它正好僅被執(zhí)行一次 src dst 全局代碼調(diào)度 向下的代碼移動(dòng) 從塊 src向下移動(dòng)到塊 dst， 假定移動(dòng)未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運(yùn)行得較快 – 若 dst和 src等價(jià) ， 則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí) ， 它正好僅被執(zhí)行一次 – src未后支配 dst, 向下移動(dòng)的代碼經(jīng)常是存儲(chǔ)操作 , 復(fù)制從 src到 dst路徑上的各塊 ， 并把 被移動(dòng)操作僅放置在 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)度 向下的代碼移動(dòng) 從塊 src向下移動(dòng)到塊 dst， 假定移動(dòng)未違反數(shù)據(jù)相 關(guān) ， 并使得通過 dst到 src的路徑運(yùn)行得較快 – 若 dst和 src等價(jià) ， 則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí) ， 它正好僅被執(zhí)行一次 – src未后支配 dst, 向下移動(dòng)的代碼經(jīng)常是存儲(chǔ)操作 , 復(fù)制從 src到 dst路徑上的各塊 ， 并把 被移動(dòng)操作僅放置在 dst的新拷貝中 – dst沒有后支配 src， 插入補(bǔ)償代碼以 保證被移動(dòng)操作在不經(jīng) dst路徑上也執(zhí)行 src dst 全局代碼調(diào)度 更新數(shù)據(jù)相關(guān) 代碼移動(dòng)會(huì)改變操作之間的數(shù)據(jù)相關(guān)關(guān)系 – 兩個(gè)對 x的賦值之一可以移動(dòng)到最上面的基本塊 ，該變換能維持原來程序中的所有相關(guān)性 – 一旦一個(gè)對 x的賦值被上移 ， 另一個(gè)就不能移動(dòng)了 – 移動(dòng)使得 x在最上面塊的出口 由不活躍變成活躍 – 一個(gè)變量在某個(gè)程序點(diǎn) 活躍 ， 則就不能把對它的投機(jī) 定值移到該點(diǎn)的上面 x = 1 x = 2 全局代碼調(diào)度 全局調(diào)度的其他問題 – 程序調(diào)度應(yīng)該使經(jīng)常執(zhí)行的路徑運(yùn)行得快一些 ， 不經(jīng)常執(zhí)行的路徑可能會(huì)因調(diào)度變得慢一些 – 編譯器可用來估計(jì)執(zhí)行頻率的技術(shù)有若干種 (1) 內(nèi)循環(huán)比外循環(huán)執(zhí)行得更頻繁 (2) 分支指令往回跳轉(zhuǎn)比不跳轉(zhuǎn)要更經(jīng)常 (3)看守程序出口或異常處理例程的分支語句很少被執(zhí)行 – 最好的頻率估計(jì)來自動(dòng)態(tài)剖析 ， 程序被靜態(tài)插樁以用來運(yùn)行時(shí)記錄條件分支每次的走向 全局代碼調(diào)度 全局調(diào)度的其他問題 ? 最簡單的全局調(diào)度算法也相當(dāng)復(fù)雜 ， 不介紹 ? 在一些全局調(diào)度算法中 ， 循環(huán)迭代的邊界是代碼移動(dòng)的一種屏障 ， 需循環(huán)展開 for(i = 0。 i N。 i ++) { for ( i = 0。 i + 4 N。 i += 4) { S(i)。 S(i)。 S(i +1)。 } S(i +2)。 S(i +3)。 } for ( 。 i N。 i ++) { S(i)。 } 全局代碼調(diào)度 靜態(tài)調(diào)度器和動(dòng)態(tài)調(diào)度器的相互影響 動(dòng)態(tài)調(diào)度器的優(yōu)點(diǎn)是可以根據(jù)運(yùn)行時(shí)的情況建立新 的調(diào)度表 ， 無需事先編碼所有可能的調(diào)度表 全局代碼調(diào)度 靜態(tài)調(diào)度器和動(dòng)態(tài)調(diào)度器的相互影響 ? 存在動(dòng)態(tài)調(diào)度情況下 ， 靜態(tài)調(diào)度器的作用 – 保證盡早地取高延遲的指令 ， 使得動(dòng)態(tài)調(diào)度器能夠盡早發(fā)射它們 – 盡早安排預(yù)取指令 ， 使數(shù)據(jù)到要用時(shí)已經(jīng)在緩存 , 或盡早安排可能不命中緩存的操作 – 只需要給數(shù)據(jù)相關(guān)的操作安排正確的次序 ， 無需通過極小化延遲來分離每一對數(shù)據(jù)相關(guān)的操作 – 給分支預(yù)測指令較高優(yōu)先級 ， 以減少預(yù)測錯(cuò)誤的代價(jià) 軟 件 流 水 引言 軟件流水是一種調(diào)度算法 ， 它每次調(diào)度一個(gè) 完整的循環(huán) ， 以充分利用穿越迭代的并行性 – 單次迭代的操作中幾乎沒有什么并行性 – 軟件流水技術(shù)不斷地重疊一些相繼迭代 ， 直到所有迭代都填入流水線為止 – 能產(chǎn)生高效和緊湊的代碼 以一周期內(nèi)可以同時(shí)發(fā)射一個(gè)讀取 、 一個(gè)存儲(chǔ) 、 一個(gè)算術(shù)運(yùn)算 （ 全流水 ） 和一個(gè)分支操作的機(jī)器 來舉例 軟 件 流 水 ? 每次調(diào)度一個(gè)迭代的結(jié)果見右邊 for (i = 0。 i n。 i ++) // R1, R2, R3 = amp。A, amp。B, amp。D D[i] = A[i] ? B[i] + c。 // R4 = c // R10 = n ?1 L: LD R5, 0(R1++) LD R6, 0(R2++) MUL R7, R5, R6 NOP ADD R8, R7, R4 NOP ST 0(R3++),R8, BL R10, L 該計(jì)算大部分是 串行的，它需要 7周期，只有循 環(huán)回跳指令和迭 代中最后一條指 令重疊 軟 件 流 水 ? 循環(huán)展開 4次迭代的調(diào)度結(jié)果見右邊 for (i = 0。 i n。 i ++) L: LD D[i] = A[i] ? B[i] + c。 LD LD MUL LD MUL LD ADD LD ADD LD ST MUL LD ST MUL ADD ADD ST ST BL(L) 展開后每次迭 代的執(zhí)行用 13 周期，或者說 原來的每次迭 代僅需要 周期 忽略了寄存器 分配的細(xì)節(jié) 軟 件 流 水 周期 j = 1 j = 2 j = 3 j = 4 j = 5 (1) LD (2) LD (3) MUL LD (4) LD (5) MUL LD (6) ADD LD (7) MUL LD (8) ST ADD LD (9) MUL LD (10) ST ADD LD (11) MUL (12) ST ADD (13) (14) ST ADD (15) (16) ST 不考慮寄存器 分配 循環(huán)的 軟件流水 ? 右邊是展開 5 次的迭代 ? 調(diào)度滿足所有 的資源和數(shù)據(jù) 相關(guān)約束 ? 第 7和 8周期執(zhí) 行的操作同第 9 和 10周期執(zhí)行 的是一樣的 軟 件 流 水 (1) LD (2) LD (3) MUL LD (4