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

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