計算機系統(tǒng)結(jié)構(gòu)清華大學出版社第5章.ppt

第五章標量處理機 2020 2 12 2020 2 12 2 本章主要內(nèi)容 5 1先行控制技術5 2流水線技術5 3相關性分析技術5 4超標量處理機5 5超流水線處理機5 6超標量超流水線處理機 2020 2 12 3 標量處理機 只有標量數(shù)據(jù)表示和標量指令系統(tǒng)的處理機稱為標量處理機 是最常用最普通的處理機 設計處理機的主要任務就是縮短解釋指令的時間 提高處理機指令的執(zhí)行速度 提高處理機的工作主頻 5 60年代主要采用這種技術 每3 4年處理機的速度要提高一個數(shù)量級 采用更好的算法和設計更好的功能部件 如采用RISC等 多條指令并行執(zhí)行 指令級的并行技術 流水線技術 處理機中設置多個獨立的功能部件 如浮點運算器 定點運算器 訪存部件等 超長指令技術 2020 2 12 4 5 1先行控制技術 先行控制技術的關鍵是采用緩沖技術和預處理技術 以及兩者都采用 通過對指令流和數(shù)據(jù)流的預處理和緩沖 能夠盡量使指令分析器和指令執(zhí)行部件獨立工作并始終處于忙碌狀態(tài) 5 1 1指令的重疊執(zhí)行方式5 1 2先行控制方式的原理5 1 3處理機結(jié)構(gòu)5 1 4指令執(zhí)行序列5 1 5先行緩沖棧5 1 6緩沖深度的設計方法 2020 2 12 5 指令的重疊執(zhí)行方式 一條指令的執(zhí)行可以分為多個階段 具體分法視處理機而定 一般可以分為三個階段 取指令是指按照指令計數(shù)器的內(nèi)容訪問主存 取出一條指令送到指令寄存器 分析指令是指對指令的操作碼進行譯碼 按照給定的尋址方式和地址字段內(nèi)容形成操作數(shù)地址 并用這個地址讀出操作數(shù) 操作數(shù)可以在主存也可以在寄存器 執(zhí)行指令是根據(jù)操作碼的要求 完成指令規(guī)定的功能 把結(jié)果寫到主存或者寄存器 指令分析或者指令執(zhí)行階段還得修改指令計數(shù)器的更新 為下一條指令作準備 2020 2 12 6 指令的重疊執(zhí)行方式 1 順序執(zhí)行方式執(zhí)行n條指令所用的時間為 如果每段時間都為t 則執(zhí)行n條指令所用的時間為 T 3nt主要優(yōu)點 控制簡單 節(jié)省設備 主要缺點 速度慢 功能部件的利用率低 2020 2 12 7 2 一次重疊執(zhí)行方式如果兩個過程的時間相等 則執(zhí)行n條指令的時間為 T 1 2n t主要優(yōu)點 指令的執(zhí)行時間縮短 功能部件的利用率明顯提高 主要缺點 需要增加一些硬件 控制過程稍復雜 指令的重疊執(zhí)行方式 續(xù) 2020 2 12 8 3 二次重疊執(zhí)行方式如果三個過程的時間相等 執(zhí)行n條指令的時間為 T 2 n t在理想情況下 處理機中同時有三條指令在執(zhí)行 處理機的結(jié)構(gòu)要作比較大的改變 需要采用先行控制技術 指令的重疊執(zhí)行方式 續(xù) 2020 2 12 9 先行控制方式的原理 1 采用二次重疊執(zhí)行方式必須解決兩個問題 1 有獨立的取指令部件 指令分析部件和指令執(zhí)行部件把一個集中的指令控制器 分解成三個獨立的控制器 存儲控制器 指令控制器 運算控制器 2 要解決訪問主存儲器的沖突問題取指令 分析指令 執(zhí)行指令都可能要訪問存儲器 2020 2 12 10 2 解決訪存沖突的方法 1 采用低位交叉存取方式 這種方法不能根本解決沖突問題 取指令 讀操作數(shù) 寫結(jié)果 2 主存分為兩個獨立的存儲器 獨立的指令存儲器和數(shù)據(jù)存儲器 如果再規(guī)定 執(zhí)行指令所需要的操作數(shù)和執(zhí)行結(jié)果只寫到通用寄存器 則取指令 分析指令和執(zhí)行指令就可以同時進行 在許多高性能處理機中 有獨立的指令Cache和數(shù)據(jù)Cache 這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu) 先行控制方式的原理 續(xù) 2020 2 12 11 3 采用先行控制技術采用先行控制技術的關鍵是緩沖技術和預處理技術 緩沖技術通常用在工作速度不固定的兩個功能部件之間 設置緩沖棧的目的是用來以平滑功能部件之間的工作速度 在采用了緩沖技術和預處理技術之后 運算器能夠?qū)Ｐ挠跀?shù)據(jù)的運算 從而大幅度提高程序的執(zhí)行速度 先行控制方式的原理 續(xù) 2020 2 12 12 處理機結(jié)構(gòu) 1 三個獨立的控制器 存儲控制器 指令控制器 運算控制器 2 四個緩沖棧 先行指令緩沖棧 先行讀數(shù)緩沖棧 先行操作棧 后行寫數(shù)棧 3 處理機組成 2020 2 12 13 4 先行指令緩沖棧的組成作用 只要指令緩沖棧沒有充滿 就自動發(fā)出取指令的請求 指令分析器每分析完一條指令 自動向指令緩沖棧發(fā)出取下一條指令的請求 指令取出后就把先行指令緩沖棧中的指令作廢 分析指令速度和從主存取指令的速度是隨機的 指令緩沖棧的指令數(shù)目是動態(tài)的 設置兩個程序計數(shù)器 先行程序計數(shù)器PC1 用來指示取指令 現(xiàn)行程序計數(shù)器PC 記錄指令分析器正在分析的指令地址 處理機結(jié)構(gòu) 續(xù) 2020 2 12 14 處理機結(jié)構(gòu) 續(xù) 先行緩沖站的組成 指令緩沖存儲器堆 采用先進先出的方式 保證指令的執(zhí)行順序不致混亂 2020 2 12 15 處理機結(jié)構(gòu) 續(xù) 先行控制方式中的一次重疊執(zhí)行 重疊部分 無論誰先結(jié)束 都不能提前執(zhí)行下一條指令 需要等待 無論任何時刻 在指令分析部件和指令執(zhí)行部件內(nèi)都只有相鄰的兩條指令重疊執(zhí)行 處理機只需要設置一套指令分析部件 指令控制器 一套指令執(zhí)行部件 運算控制器和運算器 控制方式簡單 所需要時間為T 1 n t 2020 2 12 16 處理機結(jié)構(gòu) 續(xù) 5 存在的主要問題 計算機指令系統(tǒng)復雜 各類指令 分析 和 執(zhí)行 的時間相差很大 分析指令和執(zhí)行指令常常相互等待 造成部件的浪費 分析k 1操作所需要的操作數(shù)正好是執(zhí)行k的結(jié)果 不能重疊執(zhí)行 發(fā)生數(shù)據(jù)相關 還有控制相關 變址相關 轉(zhuǎn)移或轉(zhuǎn)子程序指令時 程序的執(zhí)行過程不是順序的 先行指令緩沖棧中預取指令和分析的下一條指令都可能要作廢 2020 2 12 17 指令執(zhí)行時序 設置了指令緩沖棧 取指令的時間就可以忽略不計 一條指令的執(zhí)行可分為2個過程 1 分析指令和執(zhí)行指令時間不相等時的情況 等待 2020 2 12 18 指令執(zhí)行時序 2 采用先行緩沖棧的指令執(zhí)行過程先行讀數(shù)棧 先行操作棧 后行寫數(shù)棧 理想情況下 指令執(zhí)行部件應該一直忙碌 連續(xù)執(zhí)行n條指令的時間為 2020 2 12 19 先行緩沖棧 設置先行緩沖棧的目的 使指令分析器和指令執(zhí)行部件能夠獨立工作 1 先行指令緩沖棧 處于主存儲器與指令分析器之間 用它來平滑主存儲器取指令和指令分析器使用指令之間的速度差異 RR型指令 不必處理 直接送先行緩沖棧 RS型指令 主存有效地址送先行讀數(shù)棧 用該先行讀數(shù)棧的寄存器編號替換指令中的主存地址碼部分 形成RR 指令送先行緩沖棧 2020 2 12 20 RI型指令 指令中的立即數(shù)送先行讀數(shù)棧 用該先行讀數(shù)棧的寄存器編號替換指令中的立即數(shù)部分 形成RR 指令送先行緩沖棧 轉(zhuǎn)移指令 一般在指令分析器中直接執(zhí)行 2 先行操作棧處于指令分析器和運算控制器之間 使指令分析器和運算器能夠各自獨立工作 采用先進先出方式工作 由指令寄存器堆和控制邏輯組成 先行緩沖棧 續(xù) 2020 2 12 21 3 先行讀數(shù)棧處于主存儲器與運算器之間 平滑運算器與主存儲器的工作 每個緩沖寄存器由地址寄存器 操作數(shù)寄存器和標志三部分組成 也可以把地址寄存器和操作數(shù)寄存器合為一個 當收到從指令分析器中送來的有效地址時 就向主存申請讀操作數(shù) 讀出的操作數(shù)存放在操作數(shù)寄存器中或覆蓋掉地址寄存器中的地址 先行緩沖棧 續(xù) 2020 2 12 22 4 后行寫數(shù)棧每個后行緩沖寄存器由地址寄存器 數(shù)據(jù)寄存器和標志三部分組成 指令分析器遇到向主存寫結(jié)果的指令時 把形成的有效地址送入后行寫數(shù)棧的地址寄存器中 并用該地址寄存器的編號替換指令的目的地址部分 形成RR 指令送入先行操作棧 當運算器執(zhí)行這條RR 型寫數(shù)指令時 只要把寫到主存的數(shù)據(jù)送到后行寫數(shù)棧的數(shù)據(jù)寄存器中即可 先行緩沖棧 續(xù) 2020 2 12 23 先行緩沖棧 續(xù) 5 采用先行控制方式時一個程序的執(zhí)行情況 2020 2 12 24 緩沖深度的設計方法 以靜態(tài)分析為主 通過模擬來確定緩沖深度 1 先行指令緩沖棧的設計考慮兩種極端情況 假設緩沖深度為DI 1 先行指令緩沖棧已經(jīng)充滿指令流出的速度最快 例如連續(xù)分析RR型指令 設這種指令序列的最大長度為L1 平均分析一條這種指令的時間為t1 指令流入的速度最慢 設平均取一條指令的時間為t2 從主存儲器中取到先行指令緩沖棧中的指令條數(shù)是L1 DI條 2020 2 12 25 應該滿足如下關系 L1t1 LI DI t2計算出緩沖深度為 如果這種指令流的連續(xù)長度超過L1 則先行指令緩沖棧被取空 指令分析器沒有指令可分析 被迫處于等待狀態(tài) 緩沖棧失去作用 2 先行指令緩沖棧原來為空輸入端指令流入的速度最快 每次取指令的時間最短 設這種指令序列的最大長度為L2 平均取一條這種指令的時間為t2 緩沖深度的設計方法 續(xù) 2020 2 12 26 輸出端指令流出的速度最慢 指令分析器連續(xù)分析最難分析的指令 設平均分析一條指令的時間為t1 分析的指令條數(shù)是L2 DI條 應該滿足如下關系 L2 DI t1 LIt2 計算出緩沖深度為 如果這種指令流的連續(xù)長度超過L2 先行指令緩沖棧被完全充滿 失去緩沖作用 緩沖深度的設計方法 續(xù) 2020 2 12 27 2 設計舉例在一般處理機中連續(xù)執(zhí)行短指令的概率大 例 一個采用先行控制方式的處理機 指令分析器分析一條指令用一個周期 到主存儲器中取一條指令裝入先行指令緩沖棧平均用4個周期 如果這種指令的平均長度為9 即90 的指令是執(zhí)行時間短的指令 解 計算先行指令緩沖棧的緩沖深度為 緩沖深度的設計方法 續(xù) 2020 2 12 28 3 先行指令緩沖棧的工作時間關系第1個周期 取走指令k 1 請求取指令 第4個周期末尾 指令k 8取到先行指令緩沖棧 第8個周期末尾 指令k 9取到先行指令緩沖棧 第9個周期 分析指令k 9 先行指令緩沖棧空 第10個周期 指令分析器等待 緩沖深度的設計方法 續(xù) 2020 2 12 29 4 其余緩沖棧的設計原則一般有關系 DI DC DR DW其中 DI是先行指令緩沖棧的緩沖深度 DC是先行操作棧的緩沖深度 DR是先行讀數(shù)棧的緩沖深度 DW是后行寫數(shù)棧的緩沖深度 例如 IBM370 165機 DI 4 DC 3 DR 2 DW 1 我國研制的兩臺大型計算機 DI 8 DC DR 4 DW 2 DI 12 DC DR 6 DW 2 緩沖深度的設計方法 續(xù) 2020 2 12 30 數(shù)據(jù)相關 數(shù)據(jù)相關 在執(zhí)行本條指令的過程中 如果用到的指令 操作數(shù) 變址量等是前面指令的執(zhí)行結(jié)果 這種相關稱為數(shù)據(jù)相關 控制相關 由條件分支指令 轉(zhuǎn)子程序指令 中斷等引起的相關 解決數(shù)據(jù)相關的方法有兩種 推后分析法 遇到相關數(shù)據(jù) 推后本條指令的分析 直至所需要的數(shù)據(jù)寫入到相關的存儲單元 設置專用路徑 不必等到所需要的數(shù)據(jù)寫入到相關存儲單元 而是經(jīng)專門設置的數(shù)據(jù)通路讀取所需要的數(shù)據(jù) 2020 2 12 31 1 指令相關發(fā)生指令相關的情況 n STORER1 n 1n 1 滿足關系 結(jié)果地址 n 指令地址 n 1 當?shù)趎條指令還沒有把執(zhí)行結(jié)果寫到主存之前 取出的第n 1條指令顯然是錯誤的 在k個流水段的流水線處理機中 第n條指令要修改從第n 1到第n k指令中的任意一條指令 都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤 數(shù)據(jù)相關 續(xù) 2020 2 12 32 在采用先行控制方式的處理機中 如果執(zhí)行部件正在執(zhí)行第n條指令 與下述情況之一發(fā)生相關 都可能造成程序執(zhí)行結(jié)果發(fā)生錯誤 存放在先行操作棧中的指令正在指令分析器中分析的指令已經(jīng)預取到先行指令緩沖棧中的指令指令執(zhí)行結(jié)果還在后行緩沖棧中的指令更嚴重的是 有些分支指令 可能已經(jīng)在指令分析器中執(zhí)行完成 數(shù)據(jù)相關 續(xù) 2020 2 12 33 解決指令相關的根本辦法是 在程序執(zhí)行過程中不允許修改指令 現(xiàn)代程序設計方法要求程序具有再入性 可以被遞歸調(diào)用等 也要求不修改指令 在IBM370系列機中 用 執(zhí)行指令 來解決 在程序執(zhí)行過程中既能夠修改指令 程序又具有再入性 執(zhí)行指令 執(zhí)行由第二地址 X2 B2 D2 決定的主存數(shù)據(jù)區(qū)中的指令 數(shù)據(jù)相關 續(xù) 2020 2 12 34 2 主存操作數(shù)相關發(fā)生主存操作數(shù)相關的指令序列 n OPA1 A2 A3 A1 A2 OP A3 n 1 OPA4 A1 A5 A4 A1 OP A5 出現(xiàn)下列情況之一 A1 A2 A3是主存地址 就發(fā)生主存操作數(shù)相關 A1 n A2 n 1 A1 n A3 n 1 解決辦法 運算結(jié)果寫到通用寄存器 而不寫到主存對于訪問主存儲器的請求 寫結(jié)果的優(yōu)先級高于讀操作數(shù) 數(shù)據(jù)相關 續(xù) 2020 2 12 35 有先行操作棧處理機中 分析指令 已經(jīng)執(zhí)行指令需要進入后行寫數(shù)操作棧向主存寫回運算結(jié)果的指令之間可能相隔很多條指令 已經(jīng)進入先行操作棧的任何一條指令在向主存申請讀數(shù)時都可能與正在執(zhí)行部件中執(zhí)行的指令 正在后行寫數(shù)棧中等待寫結(jié)果到主存的指令 甚至還在先行操作棧中的指令發(fā)生主存操作數(shù)相關 解決辦法 對于剛進入先行操作棧中的指令在向主存讀數(shù)之前 首先把訪問主存的地址與后行寫數(shù)棧中的所有主存地址比較 如果發(fā)現(xiàn)有相等的 則先行棧的讀數(shù)操作緩行 等到相關寫操作數(shù)指令完成 并把結(jié)果寫到主存之后再讀數(shù) 數(shù)據(jù)相關 續(xù) 2020 2 12 36 數(shù)據(jù)相關 續(xù) 3 通用寄存器數(shù)據(jù)相關發(fā)生寄存器數(shù)據(jù)相關的可能性很大 影響面也很大n OPR1 A2 R1 R1 OP A2 n 1 OPR1 R2 R1 R1 OP R2 發(fā)生R1 n R1 n 1 稱為R1數(shù)據(jù)相關 發(fā)生R1 n R2 n 1 稱為R2數(shù)據(jù)相關 2020 2 12 37 解決通用寄存器數(shù)據(jù)相關的方法 方法一 把讀操作數(shù) 寫運算結(jié)果與指令執(zhí)行合在一個節(jié)拍 從數(shù)據(jù)從通用寄存器讀出 在運算器中完成運算 結(jié)果寫回通用寄存器的整個回路中 只有通用寄存器是時序邏輯 當發(fā)生下述情況時 不能采用這種方法 當寄存器個數(shù)多時 讀寫寄存器的時間長 當功能部件數(shù)量多時 寄存器的讀寫端口多 當功能部件的執(zhí)行時間比較長 或要求指令的執(zhí)行時間短時 數(shù)據(jù)相關 續(xù) 2020 2 12 38 方法二 建立相關專用通路 ByPass 由于發(fā)生寄存器數(shù)據(jù)相關的情況很普遍 一般計算機系統(tǒng)都采用專用數(shù)據(jù)通路 把讀通用寄存器 執(zhí)行操作和寫結(jié)果分為3個周期 或2個周期 采用專用數(shù)據(jù)通路能夠縮短1至2個周期 數(shù)據(jù)相關 續(xù) 2020 2 12 39 變址相關 在采用變址尋址方式的處理機中 由于變址量放在寄存器中 因此 可能發(fā)生與通用寄存器數(shù)據(jù)相關類似變址相關 4 LOAD相關LOAD操作的執(zhí)行時間可能比較長n LOADR1 A R1 A n 1 ADDR1 R2 R1 R1 OP R2 如果R1 n R2 n 1 或R1 n R1 n 1 則發(fā)生LOAD數(shù)據(jù)相關 數(shù)據(jù)相關 續(xù) 2020 2 12 40 解決方法 方法一 由編譯器在LOAD之后插入不發(fā)生數(shù)據(jù)相關的指令 由于LOAD的執(zhí)行時間不確定 不能根本解決問題 方法二 由硬件自動插入空操作 直到LOAD操作完成 在單條流水線處理機中 也可以停止節(jié)拍發(fā)生器 直到數(shù)據(jù)從存儲器中讀出為止 數(shù)據(jù)相關 續(xù) 2020 2 12 41 控制相關 因程序的執(zhí)行方向可能被改變而引起的相關 也稱為全局相關 主要包括 無條件轉(zhuǎn)移 一般條件轉(zhuǎn)移 復合條件轉(zhuǎn)移 中斷等 1 無條件轉(zhuǎn)移在流水線處理機中 無條件轉(zhuǎn)移指令不進入執(zhí)行流水段 一般在指令譯碼階段就實際執(zhí)行完成 如果在處理機中設置有指令先行緩沖棧 則要全部或部分作廢先行指令緩沖棧中的指令 2020 2 12 42 如果轉(zhuǎn)移目標指令L不在先行指令緩沖棧中 則要將先行指令緩沖棧中的所有指令全部作廢 并等待取出轉(zhuǎn)移目標指令L 如果轉(zhuǎn)移目標指令L在先行指令緩沖棧中 只要作廢先行指令緩沖棧中的部分指令 無條件轉(zhuǎn)移指令一般對指令執(zhí)行部件的工作不會造成影響 為進一步減少無條件轉(zhuǎn)移指令造成的影響 在先行指令緩沖棧的入口處增設一個專門處理無條件轉(zhuǎn)移指令的指令分析器 控制相關 續(xù) 2020 2 12 43 2 一般條件轉(zhuǎn)移k 置條件碼CCk 1 JMP CC L 如果CC為真轉(zhuǎn)向L L 當條件碼是上一條指令產(chǎn)生時 相關最嚴重 控制相關 續(xù) 2020 2 12 44 無論轉(zhuǎn)移是否成功 條轉(zhuǎn)移指令都在指令分析階段就已經(jīng)執(zhí)行完成 無論轉(zhuǎn)移不成功或不成功 指令分析器要停頓一段時間 等待條件碼產(chǎn)生 控制相關 續(xù) 2020 2 12 45 如果轉(zhuǎn)移成功 指令L已經(jīng)在先行指令緩沖棧 指令分析器接著 分析L 如果指令L不在先行指令緩沖棧 指令分析器要等待一個周期 轉(zhuǎn)移不成功 對程序執(zhí)行影響不大 當轉(zhuǎn)移成功時 不僅指令執(zhí)行過程變成完全串行 而且要作廢先行指令緩沖棧中的大量指令 在采用流水線方式的處理機中 要通過軟件與硬件的多種手段來近可能地降低轉(zhuǎn)移成功的概率 減少轉(zhuǎn)移成功造成的影響 控制相關 續(xù) 2020 2 12 46 3 復合條件轉(zhuǎn)移k OPL 產(chǎn)生條件碼 并決定是否轉(zhuǎn)向L L 如果轉(zhuǎn)移不成功 不造成任何影響 就象普通的運算型指令一樣如果轉(zhuǎn)移成功 造成的影響比一般條件轉(zhuǎn)移指令還要大得多 全部或部分作廢先行指令緩沖棧 先行操作棧 先行讀數(shù)棧和指令分析器中的指令 必須采取策略 減小轉(zhuǎn)移成功造成的影響 控制相關 續(xù) 2020 2 12 47 控制相關 續(xù) 2020 2 12 48 轉(zhuǎn)移預測技術 轉(zhuǎn)移預測技術包括 靜態(tài)分支預測 在程序執(zhí)行過程中轉(zhuǎn)移預測方向不能改變動態(tài)分支預測 在程序執(zhí)行過程中能夠改變轉(zhuǎn)移預測方向 2020 2 12 49 靜態(tài)分支預測技術 1 軟件 猜測法 目標 通過編譯器盡量降低轉(zhuǎn)移成功的概率 例如 對于循環(huán)程序 普通編譯器生成的目標代碼 轉(zhuǎn)移成功的概率很高 不成功的只有一次 這種編譯結(jié)果對流水線極為不利 優(yōu)點 不需要改變先行控制器的硬件結(jié)構(gòu) 只需適當修改編譯器就能夠大幅度降低條件轉(zhuǎn)移指令對先行控制器產(chǎn)生的影響 其最終目標是提高處理機執(zhí)行程序的速度 2020 2 12 50 靜態(tài)分支預測技術 續(xù) 軟件 猜測法 通過編譯器降低轉(zhuǎn)移成功的概率 2020 2 12 51 2 硬件 猜測法 方法 通過改變硬件結(jié)構(gòu)來降低轉(zhuǎn)移指令對流水線的影響在先行指令緩沖棧的入口處設置一個簡單的指令分析器 當檢測到轉(zhuǎn)移指令時 就把轉(zhuǎn)移目標地址L送入先行程序計數(shù)器PC1中 同時保留當前PC1中的內(nèi)容到另一寄存器中 轉(zhuǎn)移成功 猜測正確 對轉(zhuǎn)移指令對流水線不造成影響 轉(zhuǎn)移不成功 用保存下來的地址恢復PC1和PC 軟硬件共同配合 都往同一個方向去猜測 靜態(tài)分支預測技術 續(xù) 2020 2 12 52 3 兩個先行指令緩沖棧向前條件轉(zhuǎn)移 轉(zhuǎn)移成功與不成功各50 在先行指令緩沖棧中增加一個先行目標緩沖棧按照轉(zhuǎn)移成功的方向預取指令到先行目標緩沖棧中 先行指令緩沖棧仍然按照轉(zhuǎn)移不成功的方向繼續(xù)預取指令 如果轉(zhuǎn)移不成功 則繼續(xù)分析原來先行指令緩沖棧中指令 如果轉(zhuǎn)移成功 則分析新增設的先行目標緩沖棧中的指令 靜態(tài)分支預測技術 續(xù) 2020 2 12 53 靜態(tài)分支預測技術 續(xù) AIB 新增先行指令緩沖棧 IB原先行指令緩沖棧 TR1 TR2 保存PC1和PC中的內(nèi)容 轉(zhuǎn)移不成功 恢復PC1和PC 2020 2 12 54 短循環(huán)程序的處理 在循環(huán)程序中存在大量的短循環(huán)程序 對于短循環(huán)程序 一般先行指令緩沖棧的效率很低 一種極端的情況是 當循環(huán)體只有一條指令 先行緩沖棧失效 指令分析器分析完該指令后就清除指令緩沖棧 重新到主存取指令 短循環(huán)程序的特點 循環(huán)體的長度小于等于先行指令緩沖棧的深度 使得在循環(huán)程序執(zhí)行過程中 整個循環(huán)體能夠始終存放在先行指令緩沖棧不被清除 循環(huán)程序可以多次重復使用減少訪問主存的次數(shù) 循環(huán)次數(shù)的控制采用計數(shù)轉(zhuǎn)移指令實現(xiàn) 因為計數(shù)轉(zhuǎn)移指令可以在指令分析器中直接執(zhí)行 指令分析器分析到這種特殊條件轉(zhuǎn)移指令時不必等到指令執(zhí)行部件形成條件碼 而在指令分析器中就可以判斷循環(huán)出口條件是否滿足 控制循環(huán)的條件轉(zhuǎn)移指令一般是向后轉(zhuǎn)移的指令 2020 2 12 55 短循環(huán)程序的處理 續(xù) 要在先行控制器中對短循環(huán)程序作特殊處理 必須解決好三個問題 指令分析器如何發(fā)現(xiàn)短循環(huán)程序 如何控制短循環(huán)程序在先行緩沖棧不被清除 如何控制循環(huán)體的執(zhí)行次數(shù) 即處理好循環(huán)體的出口 2020 2 12 56 短循環(huán)程序的處理 續(xù) 方法一 在指令系統(tǒng)中專門設置短循環(huán)程序的開門指令和關門指令 由編譯器在對源程序進行編譯時發(fā)現(xiàn)短循環(huán)程序 并在其開頭加上短循環(huán)開門指令 在末尾加上關門指令 在指令分析器中增加專門的硬件來處理短循環(huán)開關門指令 設置專門的短循環(huán)標志觸發(fā)器TL 當TL 1時表示先行指令緩沖棧內(nèi)是短循行程序而不被清除 2020 2 12 57 短循環(huán)程序的處理 續(xù) 執(zhí)行過程 指令分析器分析到開門指令表示循環(huán)開始 開門指令主要為循環(huán)做預處理 將短循環(huán)程序的循環(huán)次數(shù)送入指令分析器的循環(huán)次數(shù)計數(shù)器 設置短循環(huán)程序在先行指令緩沖棧的起始地址 即入口 置位短循環(huán)標志觸發(fā)器TL 表示短循環(huán)程序的開始 先從指令緩沖棧中取出一條指令進行分析 如果TL 1 每從指令緩沖棧取一條指令 都不清除該指令 執(zhí)行到關門指令 循環(huán)體結(jié)束 指令緩沖棧放置了全部該段循環(huán)體的指令 每次循環(huán)都執(zhí)行關門指令 關門指令控制循環(huán)體的次數(shù) 2020 2 12 58 短循環(huán)程序的處理 續(xù) 關門指令的工作 把循環(huán)計數(shù)器減1 若循環(huán)計數(shù)器值大于等于1 現(xiàn)行程序計數(shù)器指向短循環(huán)程序的入口 準備下一次循環(huán) 若等于1 還要把Tl清零 當Tl 0時 每分析一條指令就清除該指令 先行緩沖?；謴驼９δ?若循環(huán)計數(shù)器值為0 循環(huán)結(jié)束 順序執(zhí)行后續(xù)指令 2020 2 12 59 短循環(huán)程序的處理 續(xù) 優(yōu)缺點 優(yōu)點是硬件簡單 開關門指令確定循環(huán)體 指令操作馬即可識別此兩條指令 不需專門的硬件 缺點是增加了程序員的負擔 方法二 在有的機器中為使短循環(huán)程序處理對程序員透明 不采用專門的開關門指令 而是采用專門的硬件來識別短循環(huán)程序 IBM360 370在指令分析器中有一個向后檢測8條指令的功能 如果條件轉(zhuǎn)移指令的轉(zhuǎn)移目標地址和轉(zhuǎn)移指令本身地址相差小于0 大于 8 即認為遇到短循環(huán)程序 處理方法和開關方法相同 許多高性能處理機采用專門的一級指令Cache 把指令Cache和數(shù)據(jù)Cache分開 其中指令可以較長時間保存 有效提高循環(huán)程序的執(zhí)行速度 2020 2 12 60 5 2流水線處理機技術 空間并行性 設置多個獨立的操作部件時間并行性 分時使用同一個部件的不同部分5 2 1流水線工作原理5 2 2流水線的分類5 2 3線性流水線的性能分析5 2 4非線性流水線的調(diào)度 2020 2 12 61 流水線工作原理 1 流水寄存器流水線的每一個階段稱為流水步 流水步驟 流水段 流水線階段 流水功能段 功能段 流水級 流水節(jié)拍等 在每一個流水段的末尾或開頭必須設置一個寄存器 稱為流水寄存器 流水鎖存器 流水閘門寄存器等 加入流水寄存器 會增加指令的執(zhí)行時間 在一般流水線時空圖中不畫出流水寄存器 2020 2 12 62 2 一種指令流水線一般4至12個流水段 8個流水段的稱為超流水線處理機3 流水線時空圖 流水線工作原理 續(xù) 2020 2 12 63 流水線工作原理 續(xù) 一個浮點加法器流水線的時空圖 2020 2 12 64 4 流水線的主要特點只有連續(xù)提供同類任務才能發(fā)揮流水線效率盡量減少因條件分支造成的 斷流 通過編譯技術提供連續(xù)的相同類型操作每個流水線段都要設置一個流水寄存器時間開銷 流水線的執(zhí)行時間加長是流水線中需要增加的主要硬件各流水段的時間應盡量相等流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度 流水線需要有 裝入時間 和 排空時間 流水線工作原理 續(xù) 2020 2 12 65 流水線的分類 1 線性流水線與非線性流水線流水線的各個流水段之間是否有反饋信號線性流水線 LinearPipelining 每一個流水段都流過一次 而且僅流過一次非線性流水線 NonlinearPipelining 某些流水段之間有反饋回路或前饋回路 線性流水線能夠用流水線連接圖唯一表示 非線性流水線必須用流水線連接圖和流水線預約表共同表示 2020 2 12 66 流水線的分類 續(xù) 2 按照流水線的級別來分處理機級流水線 又稱為指令流水線 例如 在采用先行控制器的處理機中 各功能部件之間的流水線 2020 2 12 67 流水線的分類 續(xù) 部件級流水線 操作流水線 如浮點加法器流水線宏流水線 MacroPipelining 處理機之間的流水線稱 每個處理機對同一個數(shù)據(jù)流的不同部分分別進行處理 2020 2 12 68 流水線的分類 續(xù) 3 單功能流水線與多功能流水線單功能流水線 只能完成一種固定功能的流水線 Cray 1計算機種有12條 YH 1計算機有18條Pentium有一條5段定點和一條8段浮點流水線 Pentium 有兩條定點和一條浮點指令流水線 多功能流水線 流水線的各段通過不同連接實現(xiàn)不同功能Texas公司的ASC機 8段流水線 能夠?qū)崿F(xiàn) 定點加減法 定點乘法 浮點加法 浮點乘法 邏輯運算 移位操作 數(shù)據(jù)轉(zhuǎn)換 向量運算等 2020 2 12 69 流水線的分類 續(xù) 2020 2 12 70 4 靜態(tài)流水線與動態(tài)流水線靜態(tài)流水線 同一段時間內(nèi) 多功能流水線各個功能段只能按照一種方式連接 實現(xiàn)一種固定的功能 流水線的分類 續(xù) 2020 2 12 71 動態(tài)流水線 在同一段時間內(nèi) 多功能流水線各段可以按照不同的方式連接 同時執(zhí)行多種功能 流水線的分類 續(xù) 條件 流水線中各個功能部件之間不能發(fā)生沖突 2020 2 12 72 5 流水線的其他分類方法按照數(shù)據(jù)表示方式 標量流水線和向量流水線按照控制方式 同步流水線和異步流水線順序流水線與亂序流水線 按照流水線輸出端流出的任務和流水線輸入端流入的任務順序是否相同劃分 亂序流水線又稱為無序流水線 錯序流水線或異步流水線等 流水線的分類 續(xù) 2020 2 12 73 線性流水線的性能分析 主要指標 吞吐率 加速比和效率1 吞吐率 ThoughPut 單位時間內(nèi)流水線所完成的任務數(shù)量或輸出結(jié)果數(shù)量 流水線吞吐率的最基本公式 其中 n為任務數(shù) k為完成n個任務所用的時間 各段執(zhí)行時間相等 輸入連續(xù)任務情況下 完成n個任務需要的總時間為 Tk k n 1 t其中 k為流水線的段數(shù) t為時鐘周期 2020 2 12 74 線性流水線的性能分析 續(xù) 依據(jù) 從輸出端 用k個時鐘周期輸出第一個任務 其余n 1個周期 每個周期輸出一個任務 共n 1個任務 從輸入端 用n個周期輸入n個任務 另外還有k 1個周期等待流水線排空 2020 2 12 75 線性流水線的性能分析 續(xù) Tk k t n 1 t k n 1 t吞吐率為 最大吞吐率為 2020 2 12 76 線性流水線的性能分析 續(xù) 最大吞吐率和實際吞吐率的關系 流水線的實際吞吐率要小于最大吞吐率 實際吞吐率和 t 流水線短數(shù)k 輸入到流水線的任務數(shù)n相關 只有n k時 才有TP TPmax 2020 2 12 77 線性流水線的性能分析 續(xù) 各段時間不等 完成n個連續(xù)任務 吞吐率 最大吞吐率 流水線各段執(zhí)行時間不相等的解決辦法 2020 2 12 78 線性流水線的性能分析 續(xù) 1 將 瓶頸 部分再細分 如果可分的話 2020 2 12 79 線性流水線的性能分析 續(xù) 2020 2 12 80 線性流水線的性能分析 續(xù) 2 加速比 Speedup 計算加速比的基本公式 各段執(zhí)行時間相等 輸入連續(xù)任務情況下 加速比 最大加速比 各段時間不等 輸入連續(xù)任務情況下 實際加速比為 2020 2 12 81 線性流水線的性能分析 續(xù) 是否流水線的段數(shù)越多越好 當流水線段數(shù)增加時 需要連續(xù)輸入的任務數(shù)也必須增加 由于程序中存在數(shù)據(jù)相關 轉(zhuǎn)移 中斷等情況 任務數(shù)n受到很大限制 控制的復雜性 電路的實現(xiàn)及組裝技術 實現(xiàn)的成本等的限制 流水線不可能很多 2020 2 12 82 3 效率 Efficiency 流水線的設備利用率 計算流水線效率的一般公式 各流水段時間相等 輸入n個連續(xù)任務 流水線的效率為 最高效率為 各流水段時間不等 輸入n個連續(xù)任務 流水線效率為 線性流水線的性能分析 續(xù) 2020 2 12 83 各段設備量或價格不等時 流水線的效率為 即 其中 ai k 且 k 流水線的吞吐率 加速比與效率的關系 因為 因此 E TP t S k E 線性流水線的性能分析 續(xù) 2020 2 12 84 4 流水線最佳段數(shù)的選擇采用順序執(zhí)行方式完成一個任務的時間為t在同等速度的k段流水線上執(zhí)行一個任務的時間為 t k d d為流水鎖存器的延遲時間 流水線的最大吞吐率為 P 1 t k d 流水線的總價格估計為 C a bk 其中 a為功能段身的總價格 b為每個鎖存器的價格A G Larson把流水線的性能價格比PCR定義為 線性流水線的性能分析 續(xù) 2020 2 12 85 線性流水線的性能分析 續(xù) 求PCR的最大值為 2020 2 12 86 5 流水線性能分析舉例對于單功能線性流水線 輸入連續(xù)任務的情況 通過上面給出的公式很容易計算出流水線的吞吐率 加速比和效率 對于輸入不連續(xù)任務 或多功能流水線 通常采用基本公式計算 例 用一條4段浮點加法器流水線求8個浮點數(shù)的和 Z A B C D E F G H 線性流水線的性能分析 續(xù) 2020 2 12 87 解 Z A B C D E F G H 線性流水線的性能分析 續(xù) 2020 2 12 88 解 線性流水線的性能分析 續(xù) 2020 2 12 89 線性流水線的性能分析 續(xù) 例 多功能 線形流水線 輸入任務是不連續(xù)的情況 計算流水線的吞吐率 加速比和效率 利用Ti ASC多功能靜態(tài)流水線計算兩個向量的點積 Z AB CD EF GH 解 為減少數(shù)據(jù)相關性充分發(fā)揮流水線的作用 因該先做4個乘法 AB CD EF GH 然后坐兩個加法AB CD和EF GH 最后求總的結(jié)果Z 2020 2 12 90 線性流水線的性能分析 續(xù) 流水線的時空圖 2020 2 12 91 線性流水線的性能分析 續(xù) 20個周期完成7個運算 每個功能能段的延遲時間都為 t 則Tk 20 t n 7 則有流水線吞吐率TP為 如果采用順序執(zhí)行方式 完成一次乘法要用4個 t 完成一次加法要用6個 t 完成全部運算要用 t t t 流水線的加速比 為 整個流水線共有 段 流水線的效率 為 2020 2 12 92 線性流水線的性能分析 續(xù) 整個流水線效率很低 多功能流水線在做某一運算時 總有一些功能段是閑置的 靜態(tài)流水線必須等前一種運算運算全部排除流水線之后才能重新進行連接 計算本身存在數(shù)據(jù)相關 發(fā)生數(shù)據(jù)相關時必須等待前一個運算結(jié)果產(chǎn)生之后 下一個運算才能開始 流水線有裝入和排空部分 當輸入到流水線中的任務不多時 裝入與排空部分所占的比例比較大 2020 2 12 93 非線性流水線的調(diào)度 非線性流水線中存在反饋回路 當一個任務在流水線中流過時 在同一功能段中可能要多次經(jīng)過 不能在一個時鐘周期內(nèi)向流水線輸入一個任務 否則會發(fā)生在同一個時刻有幾個任務爭用同一個功能段的情況 稱為功能部件沖突或者流水線沖突 為避免沖突 采用延遲輸入新任務的方法 間隔幾個周期再輸入新任務 間隔的周期數(shù)不是一個常數(shù) 而是一串周期變化的數(shù)字 2020 2 12 94 非線性流水線的調(diào)度 續(xù) 非線性流水線調(diào)度的任務是要找出一個最小的循環(huán)周期 按照這周期向流水線輸入新任務 流水線的各個功能段都不會發(fā)生沖突 而且流水線的吞吐率和效率最高 1 非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對于非線形流水線 連接圖不能唯一表示工作流程 因此 引入流水線預約表 2020 2 12 95 非線性流水線的調(diào)度 續(xù) 例如 非線形流水線的連接圖和預約表 2020 2 12 96 非線性流水線的調(diào)度 續(xù) 四個功能段組成非線性流水線 與線性流水線相同地方 從第一個功能段S1到最后一個功能段S4的單方向傳輸線 不同的地方 有兩條反饋線和一條前饋線 輸出端經(jīng)常不在最后一個功能段 可能從中間的任意一個功能段輸出 2020 2 12 97 非線性流水線的調(diào)度 續(xù) 預約表 預約表的橫坐標表示流水線工作的時鐘周期 縱坐標表示流水線的功能段 中間的X表示該功能段在該時鐘周期處于工作狀態(tài) 即有任務在該時鐘段通過該功能段 空白表示該時鐘周期該功能段不工作 一行可以有多個X 表示一個任務在不同時鐘周期重復使用同一個功能段 一列可以有多個X 指同一個時鐘周期多個功能段被使用 預約表的行數(shù)是非線性流水線的段數(shù) 列數(shù)是指一個任務從進入流水線到從流水線輸出經(jīng)過的時鐘周期數(shù) 又稱為功能求值時間或裝入時間 2020 2 12 98 非線性流水線的調(diào)度 續(xù) 一張預約表可能與多個流水線連接圖相對應 原因 在預約表的同一列中可能有多個X 即該時鐘周期有多個功能段輸出 下一功能段的輸入有多個來源 從而應對有多個連接圖 2020 2 12 99 非線性流水線的調(diào)度 續(xù) 一個流水線連接圖對應與多張預約表 原因 非線性流水線的有些功能段可能有多個輸出端 也有些功能段有多個輸入端 輸出端和輸入端之間連接的先后次序形成多張預約表 2020 2 12 100 非線性流水線的調(diào)度 續(xù) 2 非線性流水線的沖突啟動距離 連續(xù)輸入兩個任務之間的時間間隔 又稱等待時間 流水線沖突 以某啟動距離連續(xù)向一條非線性流水線輸入任務 可能會存在幾個任務爭用同一個流水段 2020 2 12 101 非線性流水線的調(diào)度 續(xù) 2020 2 12 102 非線性流水線的調(diào)度 續(xù) 引起非線性流水線功能段沖突的啟動距離稱為禁止啟動距離 有些啟動距離在非線性流水線的所有功能段 在任何時間都不會發(fā)生沖突 如前表的 5 1 7 不發(fā)生沖突的啟動距離不一定僅僅是一個常數(shù) 在一般情況下是一個循環(huán)數(shù)列 稱為非線性流水線的啟動循環(huán) 只有一個啟動距離的啟動循環(huán)又稱為恒定循環(huán) 2020 2 12 103 非線性流水線的調(diào)度 續(xù) 要正確的調(diào)度一條非線性流水線 首先需要找到流水線的所有禁止啟動距離 把所有禁止啟動距離組合在一起形成數(shù)列 稱為非線性流水線的禁止向量 計算禁止向量 把預約表中每一行中任意兩個X之間的距離算出來 去掉重復的 這些數(shù)組成數(shù)列就是該非線性流水線的禁止向量 把一個啟動循環(huán)內(nèi)的所有啟動距離相加再除以這個啟動循環(huán)內(nèi)的啟動距離個數(shù)就得到該啟動循環(huán)的平均啟動距離 2020 2 12 104 3 無沖突調(diào)度方法主要目標 找出最小平均啟動距離的啟動循環(huán) 由E S Davidson及其學生于1971年提出禁止向量 預約表中每一行任意兩個 之間距離的集合 上例中為 3 4 6 沖突向量 用C CmCm 1 C2C1 表示 m位的二進制數(shù) 其中 m是禁止向量中的最大值 如果i在禁止向量中 則Ci 1 否則Ci 0 上例中C 101100 非線性流水線的調(diào)度 續(xù) 2020 2 12 105 非線性流水線的調(diào)度 續(xù) 由沖突向量可以構(gòu)造狀態(tài)圖 將沖突向量C作為初始沖突向量送入m位的右移邏輯移位器 移出為0 移位器內(nèi)的值和初始沖突向量做按位或運算 得到一個新的沖突向量 移出為1 不做任何處理 移位器繼續(xù)右移 中間形成的新的沖突向量 也按上述方法處理 在初始向量和新的沖突向量之間用箭頭連接 并標注右移次數(shù) 表示各種狀態(tài)之間的轉(zhuǎn)換關系 向量重復時合并到一起 2020 2 12 106 非線性流水線的調(diào)度 續(xù) 當初始沖突向量確定后 狀態(tài)圖就是唯一的 不同的預約表可能產(chǎn)生相同的初始沖突向量 因而不同的預約表也可能有相同的狀態(tài)圖 從預約表可以畫出狀態(tài)圖 沖狀態(tài)圖不能獲得預約表 當啟動距離大于或等于m 1時 流水線的任何一個功能段在任何時鐘周期都不會發(fā)生沖突 但流水線的吞吐率 加速比 效率都很差 2020 2 12 107 例 一條4功能段的非線性流水線 每個功能段的延遲時間都相等 它的預約表如下 1 寫出流水線的禁止向量和初始沖突向量 2 畫出調(diào)度流水線的狀態(tài)圖 3 求最小啟動循環(huán)和最小平均啟動距離 4 求平均啟動距離最小的恒定循環(huán) 非線性流水線的調(diào)度 續(xù) 2020 2 12 108 解 1 禁止向量為 2 4 6 初始沖突向量 S 101010 2 構(gòu)造狀態(tài)圖S邏輯右移2 4 6位時 不作任何處理 邏輯右移1 3 5和大于等于7時 S右移1位之后 010101 101010 111111 S右移3位之后 000101 101010 101111 S右移5位之后 000001 101010 101011 S右移7位或大于7位后 按位或就還原到它本身 非線性流水線的調(diào)度 續(xù) 2020 2 12 109 非線性流水線的調(diào)度 續(xù) 新沖突向量再處理 101111右移5位之后 000001 101010 101011 101011右移3位之后 000101 101010 101111 101011右移5位之后 000001 101010 101011 2020 2 12 110 簡單循環(huán) 狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán) 在一個狀態(tài)圖中 簡單循環(huán)的個數(shù)是有限的 3 最小的啟動循環(huán)為 1 7 和 3 5 平均啟動距離為4 4 啟動距離最小的恒定循環(huán)為 5 非線性流水線的調(diào)度 續(xù) 2020 2 12 111 非線性流水線的調(diào)度 續(xù) 2020 2 12 112 非線性流水線的調(diào)度 續(xù) 2020 2 12 113 4 優(yōu)化調(diào)度方法采用最小啟動循環(huán)啟動非線性流水線時 許多功能段還有空閑 即預約表中還有空白格子 最小啟動循環(huán)實際上不能使非線性流水線充分發(fā)揮效率 L E Shar于1972年提出流水線最小平均啟動距離的限制范圍 最小平均啟動距離的下限是預約表中任意一行里 的最多個數(shù) 即同一任務通過流水線中任意一個功能段的次數(shù) 最小平均啟動距離小于等于狀態(tài)圖中任意一個簡單循環(huán)的平均啟動距離 最小平均啟動距離的上限是沖突向量中1的個數(shù)再加上1 1992年 L E Shar又證明了上述限制范圍 最有用的是第1條 預約表中 最多的行一定是瓶頸流水段 要使整個流水線最大發(fā)揮作用 必須使瓶頸功能段不間斷工作 不得空閑 非線性流水線的調(diào)度 續(xù) 2020 2 12 114 非線性流水線的調(diào)度 續(xù) 采用預留算法來調(diào)度非線性流水線 可以達到最優(yōu)調(diào)度 確定流水線的最小平均距離 最小平均距離等于預約表中任意一行中X的最大個數(shù) 或者同一個任務流過任意功能段的最多次數(shù) 確定最小啟動循環(huán) 相對于同一個最小平均啟動距離可能有多個最小啟動循環(huán) 其中有一個且只有一個啟動距離都相等的恒定循環(huán) 選用該恒定循環(huán)為最小啟動循環(huán) 結(jié)合流水線預約表和連接圖 采用預留算法 通過插入非計算延遲功能段實現(xiàn)最小啟動循環(huán) 2020 2 12 115 對于前例的預約表 在同一行中 最多的為2個 因此 最小平均距離可以達到2 最小啟動循環(huán)可以是 2 1 3 1 1 4 1 2 3 現(xiàn)取恒定循環(huán) 2 每一行中與第1個 的距離為2的倍數(shù)的位置都要預留出來 S3行的第2個 從周期5延遲到周期6 為此 S2行的第2個 從周期6延遲到周期7 S1行的第2個 從周期7延遲到周期8 實際上 只要在流水段S4的輸出端到流水段S3的輸入端中間插入一個非計算延遲D1 非線性流水線的調(diào)度 續(xù) 2020 2 12 116 非線性流水線的調(diào)度 續(xù) 2020 2 12 117 非線性流水線的調(diào)度 續(xù) 2020 2 12 118 在非線性流水線中 最多的流水段一定是 瓶頸 流水段 實現(xiàn)最優(yōu)調(diào)度的目標是使 瓶頸 流水段處于忙碌狀態(tài) 沒有空閑周期 最優(yōu)調(diào)度方法能夠使非線性流水線的吞吐率 加速比和效率達到最優(yōu) 非線性流水線的調(diào)度 續(xù) 2020 2 12 119 局部相關 在流水線處理機中由于處理的指令條數(shù)很多 發(fā)生相關的可能性及其造成的影響將更嚴重 按照對程序執(zhí)行過程可能造成的影響劃分 可以把相關分為局部相關和全局相關兩類 如圖 程序中一條分支指令把程序劃分為三個部分 每部分內(nèi)部不再有分支操作 這種部分稱為基本塊 2020 2 12 120 局部相關 續(xù) 同一個基本塊內(nèi)部的相關稱為局部相關 lacalcorrelation 在基本塊之間的相關成為全局相關 globalcorrelation 引起全局相關的除了分支操作還有中斷 局部相關對程序執(zhí)行影響較小 僅限于相關指令臨近的幾條指令 全局相關影響很大 影響到整個程序的執(zhí)行方向 2020 2 12 121 局部相關 續(xù) 促使流水線充分發(fā)揮作用 需要軟硬件結(jié)合 軟件編譯的目標代碼要適合流水線結(jié)構(gòu) 盡量把相關數(shù)據(jù)和相關控制的指令安排得遠一些 把相同操作盡量安排在一起 在硬件方面解決好存儲系統(tǒng)的頻帶問題 能夠為流水線提高足夠的指令和數(shù)據(jù) 解決好流水線的局部相關和全局相關 局部相關包括 先寫后讀數(shù)據(jù)相關 先讀后寫數(shù)據(jù)相關 寫寫相關三種 2020 2 12 122 順序流動與亂序流動 1 順序流動方式 任務按順序流入流水線 也按順序流出流水線把如下一段程序輸入到這條流水線中 k R0 R1 k 1 k 2 R2 R0 R3 k 3 k 4 k 5 2020 2 12 123 指令k 2無法繼續(xù)執(zhí)行 要在功能段S2中等待 后續(xù)的指令k 4 k 5 等也不能進入流水線 功能段S3 S4 S5將逐漸空閑 缺點 吞吐率和效率降低優(yōu)點 流水線的控制邏輯比較簡單 順序流動與亂序流動 續(xù) 2020 2 12 124 順序流動與亂序流動 續(xù) 流水線 斷流 有些功能段 空閑 2020 2 12 125 2 亂序 Outoforder 流動方式 指令流出流水線的順序與流入流水線的順序不同 又稱為錯序流動方式 無序流動方式 異步流動方式等 順序流動與亂序流動 續(xù) 2020 2 12 126 亂序流動中的數(shù)據(jù)相關 在亂序流動方式中 可能發(fā)生三種數(shù)據(jù)相關寫寫相關k LOADF1 A F1 A 寫讀相關k 1 FADDF2 F1 F2 F2 F1 k 2 FMULF1 F3 F1 F1 F3 k 3 STOREF1 B B F1 讀寫相關 1 寫讀相關 指令k與指令k 1之間關于F1的相關 又稱為數(shù)據(jù)相關 先寫后讀相關 流相關 WR相關 RAW相關等 2020 2 12 127 2 讀寫相關 指令k 1與指令k 2之間關于F1的相關 變量名相關 先讀后寫相關 反相關 RW相關 WAR相關等 3 寫寫相關 指令k與指令k 2左邊的F1之間的相關關系稱為 輸出相關 寫寫相關 WW相關 WAW相關或?qū)懞笤賹懴嚓P等 有時把相關稱為 冒險 hazard 竟爭 competition 等 在程序執(zhí)行過程中 只有避免相關 執(zhí)行結(jié)果才是正確的 亂序流動中的數(shù)據(jù)相關 續(xù) 2020 2 12 128 亂序流動中的數(shù)據(jù)相關 續(xù) 測試先寫后讀數(shù)據(jù)相關的方法 在流水線的讀書操作功能段設置一個相聯(lián)比較器 在指令讀操作數(shù)之前 把源操作數(shù)地址和已經(jīng)在流水線中的從讀數(shù)功能段到寫結(jié)果功能段之間的所有指令的目標地址進行比較 發(fā)現(xiàn)地址相等 則表明發(fā)生了先寫后讀相關 測試先讀后寫 寫寫相關的方法 在流水線的寫功能段設置相聯(lián)比較器 把自己的目標操作數(shù)地址分別與已經(jīng)進入流水線的指令序號比自己小的源操作數(shù)地址和目標操作數(shù)地址進行比較 發(fā)現(xiàn)源操作數(shù)地址相等 發(fā)生先讀后寫相關 發(fā)現(xiàn)目標操作數(shù)地址相等 發(fā)生了寫寫相關 2020 2 12 129 亂序流動中的數(shù)據(jù)相關 續(xù) 三種數(shù)據(jù)相關可以用下列關系式來表示 對于寫讀相關D i S j 對于讀寫相關S i D j 對于寫寫相關D i D j 2020 2 12 130 亂序流動中的數(shù)據(jù)相關 續(xù) 在流水線中避免數(shù)據(jù)相關的方法分為兩類