第七章 PIPELINING.

Slides:



Advertisements
Similar presentations
高考英语阅读分析 —— 七选五. 题型解读: 试题模式: 给出一篇缺少 5 个句子的文章, 对应有七个选项,要求同学们根据文章结构、 内容,选出正确的句子,填入相应的空白处。 考查重点: 主要考查考生对文章的整体内容 和结构以及上下文逻辑意义的理解和掌握。 (考试说明) 选项特点: 主旨概括句(文章整体内容)
Advertisements

智慧老伯的一席話 原稿 : 溫 Sir 中譯 : 老柳 A man of 92 years, short, very well- presented, who takes great care in his appearance, is moving into an old people’s.
第七课:电脑和网络. 生词 上网 vs. 网上 我上网看天气预报。 今天早上看了网上的天气预报。 正式 zhèngshì (报告,会议,纪录) 他被这所学校正式录取 大桥已经落成,日内就可以正式通车 落伍 luòw ǔ 迟到 chídào 他怕迟到,六点就起床了.
程序的执行 程序执行和指令执行概述 数据通路基本结构和工作原理 流水线方式下指令的执行
第 2 章 中央處理單元.
Chapter 10 效能測量與分析.
-CHINESE TIME (中文时间): Free Response idea: 你周末做了什么?
:sisu Password:
完形填空技巧 CET4.
How can we become good leamers
广德二中2006届高考 英语专题复习 单项填空 答题指导.
Performance Evaluation
最新計算機概論 第3章 計算機組織.
摘要的开头: The passage mainly tells us sth.
Leftmost Longest Regular Expression Matching in Reconfigurable Logic
Unit 7 Protect the Earth (Story time) 觅渡教育集团 王 珏 标题 课时 教师姓名 日期 1.
Operating System CPU Scheduing - 3 Monday, August 11, 2008.
Minimum Spanning Trees
Lecture on High Performance Processor Architecture (CS05162)
主題五 CPU Learning Lab.
第 2 章 中央處理單元.
Excellence in Manufacturing 卓 越 制 造
臺北市立大學 資訊科學系(含碩士班) 賴阿福 CS TEAM
Quiz 3 假设各种分支占所有指令数的百分比如下表所示:
CPU資料處理 醫務管理暨醫療資訊學系 陳以德 副教授: 濟世CS 轉
Lecture on High Performance Processor Architecture (CS05162)
初二英语写作课 课件 福建省闽清县第一中 王国豪
第4章 处理器(CPU) 4.1 引言 4.2 逻辑设计的一般方法 4.3 建立数据通路 4.4 一个简单的实现机制 4.5 多周期实现机制.
指令集架構 計算機也跟人類一樣,需要提供一套完整的語言讓人們跟它充分溝通,以完成正確的計算工作。
5 Computer Organization (計算機組織).
Lecture on High Performance Processor Architecture (CS05162)
The Processor: Datapath and Control
Retail Customer Online Registration 零售顧客線上註冊教學
第4章 网络互联与广域网 4.1 网络互联概述 4.2 网络互联设备 4.3 广域网 4.4 ISDN 4.5 DDN
微程序控制器 刘鹏 Dept. ISEE Zhejiang University
创建型设计模式.
預官考試輔導 計算機概論提要 91年12月4日.
The Wise Old Man 智慧老伯的一席話 原稿: 溫Sir 中譯 : 老柳 中譯潤稿:風刀雨箭
子博弈完美Nash均衡 我们知道,一个博弈可以有多于一个的Nash均衡。在某些情况下,我们可以按照“子博弈完美”的要求,把不符合这个要求的均衡去掉。 扩展型博弈G的一部分g叫做一个子博弈,如果g包含某个节点和它所有的后继点,并且一个G的信息集或者和g不相交,或者整个含于g。 一个Nash均衡称为子博弈完美的,如果它在每.
JTAG INTERFACE SRAM TESTER WITH C-LCM
Fundamentals of Physics 8/e 28 - Magnetic Force
Lesson 44:Popular Sayings
第十五课:在医院看病.
計算機概論 第3章 計算機組織與結構概觀.
成品检查报告 Inspection Report
Guide to a successful PowerPoint design – simple is best
BORROWING SUBTRACTION WITHIN 20
Architecture and Systems 研究群 報 告 人:單智君 陳昌居 鍾崇斌 中華民國95年11月30日
The Processor: Datapath and Control (Multi-cycle implementation)
中国科学技术大学计算机系 陈香兰 2013Fall 第七讲 存储器管理 中国科学技术大学计算机系 陈香兰 2013Fall.
中国科学技术大学计算机系 陈香兰 Fall 2013 第三讲 线程 中国科学技术大学计算机系 陈香兰 Fall 2013.
The Wise Old Man 智慧老伯的一席話 原稿: 溫Sir 中譯 : 老柳
中央社新聞— <LTTC:台灣學生英語聽說提升 讀寫相對下降>
计算机系统结构(2012年春) ----存储层次: Cache基本概念
高考应试作文写作训练 5. 正反观点对比.
第10章 存储器接口 罗文坚 中国科大 计算机学院
计算机问题求解 – 论题1-5 - 数据与数据结构 2018年10月16日.
Chapter 10 Mobile IP TCP/IP Protocol Suite
Remember the five simple rules to be happy 快樂的五個簡單常規
严肃游戏设计—— Lab-Adventure
名词从句(2).
何正斌 博士 國立屏東科技大學工業管理研究所 教授
The Wise Old Man 智慧老伯的一席話 原稿: 溫Sir 中譯 : 老柳
常州市教育学会学业水平监测 九年级英语试卷分析 常州市第二十四中学 许喆 2012年2月.
怎樣把同一評估 給與在不同班級的學生 How to administer the Same assessment to students from Different classes and groups.
Race Conditions and Semaphore
MATLAB 結構化財務程式之撰寫 MATLAB財務程式實作應用研習 主題五 資管所 陳竑廷
Climbing a Rock Wall 攀岩 选自《多维阅读第10级》.
陳情表之外     with 三仁 三樂 歐陽宜璋製於 /10/23.
When using opening and closing presentation slides, use the masterbrand logo at the correct size and in the right position. This slide meets both needs.
Presentation transcript:

第七章 PIPELINING

Outline What is pipelining? The basic pipeline for a RISC instruction set The major hurdle of pipelining – pipeline hazards Data hazards Control hazards Performance

What is pipelining? Pipelining is an implementation technique whereby multiple instructions are overlapped in execution. Not visible to the programmer Each step in the pipeline completes a part of an instruction. Each step is completing different parts of different instructions in parallel Each of these steps is called a pipe stage or a pipe segment.

What is pipelining? Like Assembly line in the factory The time required between moving an instruction one step down the pipeline is a machine cycle. All the stages must be ready to proceed at the same time Slowest pipe stage dominates Machine cycle is usually one clock cycle (sometimes two, rarely more) The pipeline designer’s goal is to balance the length of each pipeline stage.

(a) 循序執行 (b) 硬體組織 (c) 利用管線處理的執行 圖 8.1 管線處理指令的基本觀念 時間 I I I F E F E F E 2 3 F E F E F E 1 1 2 2 3 3 (a) 循序執行 中間階段緩衝器 B1 指令提取 單元 執行單元 (b) 硬體組織 時間 時脈週期 1 2 3 4 指令 I F E 1 1 1 I F E 2 2 2 I F E 3 3 3 (c) 利用管線處理的執行 圖 8.1 管線處理指令的基本觀念

Pipeline Stages Every stage is completed within one cpu clock F (Fetch) D (Decode) E (Execute) W (Write)

(a) 指令的執行被分成四個步驟 (b) 硬體組織 圖 8.2 管線的4 階段 時間 時脈週期 1 2 3 4 5 6 7 指令 I F D E W 1 1 1 1 1 I F D E W 2 2 2 2 2 I F D E W 3 3 3 3 3 I F D E W 4 4 4 4 4 (a) 指令的執行被分成四個步驟 中間階段緩衝器 D : 解碼指令 與 提取運算元 F : 提取指令 E: 執行運作 W : 寫入結果 B1 B2 B3 (b) 硬體組織 圖 8.2 管線的4 階段

How about the clock of IF Because all the stages must be completed at the same time, we can not expect IF to access main memory Thus IF must access L1 cache When cache is built in CPU, the access time of cache is almost the same as the time to execute other operations within CPU Slowest pipe stage dominates

Performance of Pipeline If the stages are perfectly balanced, then the time per instruction on the pipelined machine – assuming ideal conditions--is equal to

Pipeline Hazards Structural hazards Data hazards Control hazards Caused by resource conflict Possible to avoid by adding resources – but may be too costly Data hazards Instruction depends on the results of a previous instruction in a way that is exposed by the overlapping of instructions in the pipeline Can be mitigated somewhat by a smart compiler Control hazards When the PC does not get just incremented Branches and jumps - not too bad

管線可能遇到的問題(data hazard) 時間 時脈週期 1 2 3 4 5 6 7 8 9 指令 I F D E W 1 1 1 1 1 Stall (拖延) 除法 I F D E W 2 2 2 2 2 I F D E W 3 3 3 3 3 I F D E W 4 4 4 4 4 I F D E 5 5 5 5 圖 8.3 執行作業耗費一個以上的時序週期所造成的影響 I3 waits I2’s result to do ALU

管線可能遇到的問題(control hazard or instrction hazard) 時間 時脈週期 1 2 3 4 5 6 7 8 9 指令 I 1 F 1 D 1 E 1 W 1 I F D E W 2 2 2 2 2 I F D E W 3 3 3 3 3 (a) 在連續時序週期中的指令執行步驟 時間 時脈週期c 1 2 3 4 5 6 7 8 9 階段 Bubble(氣泡), stall(間隔) F: 提取 F 1 F 2 F 2 F 2 F 2 F 3 D: 解碼 D idle idle idle D D 1 2 3 E: 執行 E idle idle idle E E 1 2 3 W: 寫入 W idle idle idle W W 1 2 3 (b) 在連續時序週期中,每一個處理器階段所執行的功能 圖 8.4 在快取中,F2的失誤所造成的管線拖延

管線可能遇到的問題(structural hazard) 時間 時脈週期 1 2 3 4 5 6 7 指令 I F D E W 1 1 1 1 1 I (載入) F D E M W 2 2 2 2 2 2 I F D E W 3 3 3 3 3 I F D E 4 4 4 4 I F D 5 5 5 圖 8.5 位於管線時序上的 Load 指令所造成的影響

But pipeline will promote productivity Pipeline can not accelerate the execution time of instructions, actually it will prolong the instruction execution time due to the latch added between stages But pipeline will promote productivity Shorten the completion time of one instruction

Data Hazard Add R2,R3,R4 Sub R5,R4,R6 One instruction’s source registers is the destination register of previous one

圖 8.6 由於 D2 與 W1 之間的資料相關性所造成的管線間隔 Data Hazard 時間 時脈週期 1 2 3 4 5 6 7 8 9 指令 I (Add) F D E W 1 1 1 1 1 I (Sub) F D D E W 2 2 2 2A 2 2 I F D E W 3 3 3 3 3 I F D E W 4 4 4 4 4 圖 8.6 由於 D2 與 W1 之間的資料相關性所造成的管線間隔

D2 與 W1 之間的資料相關性利用forwarding解除間隔(stall) Forwarding also called bypassing, shorting, short-circuiting 時間 時脈週期 1 2 3 4 5 6 7 8 9 指令 I (Add) F D E W 1 1 1 1 1 I (Sub) F D E W 2 2 2 2 2 E I F D W 3 3 3 3 3 F 4 D E W I 4 D2 與 W1 之間的資料相關性利用forwarding解除間隔(stall)

Forwarding(轉交) How do we handle this in general? Key is to keep the ALU result around Add R2,R3,R4 Sub R5,R4,R6 How do we handle this in general? Forwarded value can be at ALU output or Mem stage output ADD produces R4 value at ALU output SUB needs it again at the ALU input

(b) 在處理器管線中之來源與結果暫存器的位置 來源 1 來源 2 SRC1 SRC2 暫存器檔 ALU RSL T 目的 (a) 資料路徑 SRC1,SRC2 RSL T E:執行 (ALU) E: Ex ecute W : 寫入 (ALU) (暫存器檔) 轉交路徑 (b) 在處理器管線中之來源與結果暫存器的位置 (b) P osition of the source and result registers in the processor pipeline 圖 8.7 利用管線處理的處理器中的運算元轉交處理

Instruction side effect An implicit data hazard Auto inc/dec addressing mode (push, pop) Carry flag Add R1,R3 AddwithCarry R2,R4 R4  [R2] + [R4] + carry

Control hazards (instruction hazard) 時間 時脈週期 1 2 3 4 5 6 指令 I F E 1 1 1 I (分支) F E 執行單元閒置 2 2 2 Branch penalty I F X 3 3 I F E k k k I F E k +1 k+ 1 k+ 1 圖 8.8 分支指令所造成的閒置週期

(a) 在 Execute 階段中計算分支位址 時間 時脈週期 1 2 3 4 5 6 7 8 I F 1 D 1 E W 1 1 1 I 2 (分支) F 2 D 2 E 2 I F 3 3 D 3 X I 4 F 4 X I F k D k E k W k k I F k+ 1 k+ 1 D k+ 1 E k+ 1 (a) 在 Execute 階段中計算分支位址 時間 時脈週期 1 2 3 4 5 6 7 I F 1 D 1 E 1 W 1 1 I 2 (分支) F 2 D 2 I F 3 3 X I F k D k E k W k k I F k+ 1 D k+ 1 E k+ 1 k+ 1 (b) 在 Decode 階段中計算分支位址(減少branch penalty) 圖 8.9 分支時序

圖 8.10 在圖 8.2b 的硬體組織中,使用指令佇列(預先提取) The instruction queue is used mainly for detecting and dealing with branches 指令提取單元 指令佇列 F : 提取指令 D : 分派/ 解碼單元 E : 執行 單元 W : 寫入 結果 圖 8.10 在圖 8.2b 的硬體組織中,使用指令佇列(預先提取)

Branch Instructions 20% of Dynamic execution is branch instructions, that is, every 5 instructions been executed has one branch Branch has huge impact on pipeline, thus modern CPU has various strategies to handle this control hazard such as delay branch, branch prediction, branch folding

Delayed branch (make the stall cycle useful) Branch delay slot Compiler has to find instructions to fill in the slot(85% complex compiler technique can handle one delay slot) Maybe more than one slot, but it is hard for compiler to locate suitable instructions to fill in. Compiler need to find an instruction which is always executed to fill in the slot whether the branch is taken or not

(a) 原來的程式迴圈 (b) 重新排序過的指令 圖 8.12 為延遲分支重新排序的指令 LOOP Shift_left R1 Decrement R2 Branch=0 LOOP NEXT Add R1,R3 (a) 原來的程式迴圈 LOOP Decrement R2 Branch=0 LOOP Branch delay slot Shift_left R1 NEXT Add R1,R3 (b) 重新排序過的指令 圖 8.12 為延遲分支重新排序的指令

圖 8.13 在圖 8.12b 的迴圈中,在最後兩回期間 說明填入延遲槽的執行時序 時間 時脈週期 1 2 3 4 5 6 7 8 指令 遞減 F E 分支 F E Shift (延遲槽) F E 遞減(發生分支) F E 分支 F E Shift (延遲槽) F E Add (Branch not tak en) F E 圖 8.13 在圖 8.12b 的迴圈中,在最後兩回期間 說明填入延遲槽的執行時序

Branch prediction (Speculative execution) Static branch prediction Fixed prediction for every branch Branch taken Branch not taken Dynamic branch prediction branch-prediction buffer Branch target buffer (BTB)

Branch-prediction buffer this buffer contains a bit as to whether the branch was last taken or not (1 time history) upon fetching the instruction, we also fetch the prediction bit (from a special cache) if the bit is set, we predict that the branch is taken if the bit is not set, we predict that the branch is not taken

(b) 4-狀態演算法 (2 bit history) 發生分支 (BT) BNT LNT LT BT 沒有發生分支(BNT) (a) 2-狀態演算法(1 bit history) BT BNT SNT LNT BNT BNT BT ST: strongly taken LT: likely taken LNT: likely not taken SNT: strongly not taken BT LT ST BT BNT (b) 4-狀態演算法 (2 bit history) Better Approach 圖 8.15 分支預測演算法的狀態機表示法

Branch target buffer (BTB) we need to know both the branch condition outcome and the branch address by the end of the IF stage we need to know where we are branching to before we have even decode the instruction as a branch! doesn’t seem possible, but we will use a prediction buffer like before but enhanced: We will use a branch-target buffer This will store for a given branch prediction of the branch outcome and if the branch is taken, the predicted branch target

The Target Buffer Send PC of current instruction to target buffer in IF stage If we get a hit (PC is in the table) then look up the predicted PC and branch prediction If predict taken, then update the PC with the predicted PC in the buffer otherwise increment PC as usual Thus, we predict the branch location before we have even decoded the current instruction to see if it is a branch! On a branch miss or misprediction, update the buffer by moving missing PC into buffer, or updating predicted PC/branch prediction bit

Branch Folding Notice that by using the branch target buffer we are fetching the new PC value (or the offset for the PC) from the buffer and then updating the PC and then fetching the branch target location instruction Instead, why not just fetch the next instruction? In Branch folding, the buffer stores the instruction at the predicted location If we use this scheme for unconditional branches, we wind up with a penalty of –1 (we are in essence removing the unconditional branch) Note: for this to work, we must also update the PC, so we must store both the target location and the target instruction this approach won’t work well for conditional branches

PowerPC 601 architecture

Branch folding The instruction queue is used mainly for detecting and dealing with branches. The 601's branch unit scans the bottom four entries of the queue, identifying branch instructions and determining what type they are (conditional, unconditional, etc.). In cases where the branch unit has enough information to resolve the branch right then and there (e.g. in the case of an unconditional branch, or a conditional branch whose condition is dependent on information that's already in the condition register) then the branch instruction is simply deleted from the instruction queue and replaced with the instruction located at the branch target. This branch-elimination technique, called branch folding, speeds performance in two ways. First, it eliminates an instruction (the branch) from the code stream, which frees up dispatch bandwidth for other instructions. Second, it eliminates the single-cycle pipeline bubble that usually occurs immediately after a branch.

Pipeline and addressing mode Complex addressing mode doesn’t save any clock cycle than simple addressing mode Load (X(R1)),R2  complex addressing mode Add #X,R1,R2 Load (R2),R2  simple addressing mode Load (R2),R2

(a) 複雜定址模式 (b) 簡單定址模式 圖 8.16 使用複雜與簡單定址模式的等價作業 時脈週期 1 2 3 4 5 6 7 Load 時間 時脈週期 1 2 3 4 5 6 7 Load F D X + [R1] [X + [R1]] [[X + [R1]]] W F 轉交 下一個指令 F D E W (a) 複雜定址模式 Add F D X + [R1] W Load F D [X + [R1]] W Load F D [[X + [R1]]] W 下一個指令 F D E W (b) 簡單定址模式 圖 8.16 使用複雜與簡單定址模式的等價作業

現代處理器的定址模式特色 (RISC優先強調的部分) 存取運算元時不需要存取記憶體一次以上 只有載入(load)與儲存(store)指令存取記憶體運算元 使用的定址模式沒有副作用 暫存器定址模式(不須計算EA) 暫存器間接定址模式(不須計算EA) 索引定址模式(只須一個clock計算EA)

Add Compare Branch=0 R1,R2 R3,R4 . . . (a) 程式片段 (b) 重新排序過的指令 圖 8.17 指令的重新排序 條件碼旗標所導入的相關性會降低compiler替指令重新排序的彈性

Pipeline Datapath 圖 8.18 針對管線執行,以位於 ALU 的輸入與輸出中的中間階段緩衝器來修改之資料路徑 暫存器檔 匯流排 A A 匯流排 B ALU R B 匯流排 C PC 控制訊號管線 遞增器 指令解碼器 IMAR 記憶體位址 (指令提取) 指令佇列 MDR/Write DMAR MDR/Read 指令快取 記憶體位址 (資料存取) 資料快取 圖 8.18 針對管線執行,以位於 ALU 的輸入與輸出中的中間階段緩衝器來修改之資料路徑 Figure 8.18. Datapath modified for pipelined e x ecution, with interstage b uf fers at the input and output of the ALU.

超純量作業 (superscalar) Multiple-issue Multiple pipeline Wide bus to cache Separate Integer’s Execute Unit and Floating’s Execute Unit Usually multiple IEUs, FEUs

F : 指令提取 單元 指令佇列 浮點數單元 分派單元 W : 寫入 結果 整數單元 圖 8.19 包含兩個執行單元的處理器

圖 8.20 在圖 8.19 的處理器中的指令執行流程範例,假定沒有遇到危障 時間 時脈週期 1 2 3 4 5 6 7 I (F add) 1 F D E E E W 1 1 1A 1B 1C 1 I (Add) F D E W 2 2 2 2 2 I (Fsub) 3 F D E E E W 3 3 3 3 3 3 I (Sub) F D E W 4 4 4 4 4 圖 8.20 在圖 8.19 的處理器中的指令執行流程範例,假定沒有遇到危障

Out of order execution (脫序的執行) In order issue To avoid dead lock Out of order execution Reorder buffer In order retire Register renaming Temporary registers for commitment Imprecise exception Allow instructions completion after exception instruction Precise exception instructions completion after exception instruction are aborted

圖 8.23 UltraSPARC II 處理器的主要構成要素 系統交互連接匯流排 外部快取 單元 指令 資料 載入佇列 儲存佇列 預先提取 與分派單元 記憶體管理 單元 D-Cache I-Cache iTLB dTLB 指令緩衝區 浮點 暫存器 浮點單元 整數 暫存器 整數執行 單元 圖 8.23 UltraSPARC II 處理器的主要構成要素

      圖 8.24 UltraSPARC II 處理器的管線組織 兩條整數管線處理 解碼 快取 延遲 寫入 提取 群組 執行 延遲 檢查  E C N1 N2 N3 W  E C N1 N2 N3 W  執行 執行 寫入 F D G 暫存器 執行 檢查  R X1 X2 X3 N3 W  R X1 X2 X3 N3 W  兩條浮點管線處理 指令緩衝區 圖 8.24 UltraSPARC II 處理器的管線組織

效能考量 T=(N x S)/R Instruction throughput Only one L1 cache L1,L2 cache Ps = R/S = N/T  一秒所能執行的指令數 Only one L1 cache Dmiss = ((1-hi) + d(1-hd)) x Mp Dmiss = (0.05 + 0.03) x 17 = 1.36 cycles L1,L2 cache Dmiss = ((1-hi) + d(1-hd)) x (hs x Ms + (1-hs) x Mp) = 0.46 cycles

管線階段的數目 較遠的指令在管線中形成相關性 管線變長,分支的損失更嚴重 成本增加 UltraSPARC II  9 stages Intel Pentium pro  12 stages Pentium 4  12 stages

結論 管線設計的考量 處理器的指令集 管線硬體的設計 編譯程式的設計 三者之間互動強烈