程序的执行 程序执行和指令执行概述 数据通路基本结构和工作原理 流水线方式下指令的执行

Presentation on theme: "程序的执行 程序执行和指令执行概述 数据通路基本结构和工作原理 流水线方式下指令的执行"— Presentation transcript:

1 程序的执行 程序执行和指令执行概述 数据通路基本结构和工作原理 流水线方式下指令的执行
程序的执行 程序执行和指令执行概述 数据通路基本结构和工作原理 流水线方式下指令的执行

2 程序的执行机制 主要教学目标 理解CPU如何控制程序的执行流 了解一条指令的执行过程 了解CPU的主要功能和内部结构
了解数据通路的基本组成和定时方式 理解指令执行时数据通路中信息的流动过程 了解指令流水线的基本概念 了解内部异常和外部中断的基本概念

3 程序的执行机制 分以下三个部分介绍 第一讲：程序执行概述 程序及指令的执行过程 CPU的基本功能和基本组成
第二讲：数据通路基本结构和工作原理 数据通路基本结构 数据通路的时序控制 数据通路基本工作原理 第三讲：流水线方式下指令的执行 指令流水线的基本原理 适合流水线的指令集特征 CISC和RISC风格指令集 指令流水线的实现 高级流水线实现技术

4 一个日常生活中的例子—洗衣服 Pipelining: It’s Natural ! A B C D 如果让你来管理洗衣店，你会如何安排？
Laundry Example Ann, Brian, Cathy, Dave each have one load of clothes to wash, dry, and fold Washer takes 30 minutes Dryer takes 40 minutes “Folder” takes 20 minutes A B C D 如果让你来管理洗衣店，你会如何安排？ Pipelining: It’s Natural !

5 Sequential Laundry（串行方式）
6 PM 7 8 9 10 11 Midnight Time 30 40 20 30 40 20 30 40 20 30 40 20 T a s k O r d e A B C D 串行方式下 4 批衣服需花费 6 小时（4x( )=360分钟） N批衣服，需花费的时间为Nx( ) = 90N 如果用流水线方式洗衣服，则花多少时间呢?

6 Pipelined Laundry: (Start work ASAP)
6 PM 7 8 9 10 11 Midnight Time 30 40 20 T a s k O r d e A 串行为90分钟x4=6小时 N批则为90xN分钟 B 流水线方式下，需30+4x40+20 =210分 (3.5小时) 如果有N批衣服呢？ 30+Nx40+20分钟 假定每一步时间均衡，则比串行方式提高约3倍！ C D 流水方式下，所用时间主要与最长阶段的时间有关！

7 指令流水线的基本概念 五段流水线 取指令(IF)：根据PC的值从存储器取出指令。 指令译码(ID)：产生指令执行所需的控制信号。
取操作数(OF)：读取存储器操作数或寄存器操作数。 执行(EX)：对操作数完成指定操作。 写回(WB)：将操作结果写入存储器或寄存器。

8 单周期数据通路中指令的执行 假定：最复杂指令执行过程 ① 取指：200ps；②译码和读操作数：50ps；③ALU操作：100ps；④读存储器：200ps；⑤结果写寄存器：50ps。 =550 单周期：每条指令在单个时钟周期内完成，故CPI=1，时钟周期=600ps CPI=1，指令延时为600ps 指令吞吐率为1.67GIPS 每秒执行指令条数： 1/600ps=1/(600×10-15)=1.67×1012 指令串行执行，程序执行时间为：指令条数×600ps

9 流水线数据通路中指令的执行 最长段为200ps 取指令 译码/读数 ALU运算 读/写存储器 写结果 指令吞吐率为4GIPS
假定：最复杂指令执行过程 ① 取指：200ps；②译码和读操作数：50ps；③ALU操作：100ps；④读存储器：200ps；⑤结果写寄存器：50ps。 最长段为200ps 指令延时为：250ps×5=1.25ns 指令吞吐率为4GIPS 取指令 译码/读数 ALU运算 读/写存储器 写结果

10 流水线指令集的设计 具有什么特征的指令集有利于流水线执行呢？ 长度尽量一致，有利于简化取指令和指令译码操作
MIPS指令32位，下址计算方便: PC+4 X86指令从1字节到17字节不等，使取指部件极其复杂 格式少，且源寄存器位置相同，有利于在指令未知时就可取操作数 MIPS指令的rs和rt位置一定，在指令译码时就可读rs和rt的值 若位置随指令不同而不同，则需先确定指令类型才能取寄存器编号 load / Store指令才能访问存储器，有利于减少操作步骤，规整流水线 lw/sw指令的地址计算和运算指令的执行步骤规整在同一个周期 X86运算类指令操作数可为内存数据，需计算地址、访存、执行 内存中”对齐”存放，有利于减少访存次数和流水线的规整 总之，规整、简单和一致等特性有利于指令的流水线执行 op rs rt rd shamt func 6 11 16 21 26 31 6 bits 5 bits

11 按指令格式的复杂度来分 按指令格式的复杂度来分，有两种类型计算机：
复杂指令集计算机CISC (Complex Instruction Set Computer) 精简指令集计算机RISC (Reduce Instruction Set Computer) 早期CISC设计风格的主要特点 (1) 指令系统复杂 变长操作码 / 变长指令字 / 指令多 / 寻址方式多 / 指令格式多 (2) 指令周期长 绝大多数指令需要多个时钟周期才能完成 (3) 各种指令都能访问存储器 除了专门的存储器读写指令外，运算指令也能访问存储器 (4) 采用微程序控制 (5) 有专用寄存器 (6) 难以进行编译优化来生成高效目标代码 例如，VAX-11/780小型机 16种寻址方式；9种数据格式；303条指令；一条指令包括1～2个字节的操作码和下续N个操作数说明符。一个说明符的长度达1 ～10个字节。

12 复杂指令集计算机CISC CISC的缺陷 日趋庞大的指令系统不但使计算机的研制周期变长，而且难以保证设计的正确性，难以调试和维护，并且因指令操作复杂而增加机器周期，从而降低了系统性能。 1975年IBM公司开始研究指令系统的合理性问题，John Cocks提出精简指令系统计算机 RISC ( Reduce Instruction Set Computer )。 对CISC进行测试，发现一个事实： 在程序中各种指令出现的频率悬殊很大，最常使用的是一些简单指令，这些指令占程序的80%，但只占指令系统的20%。而且在微程序控制的计算机中，占指令总数20%的复杂指令占用了控制存储器容量的80%。 1982年美国加州伯克利大学的RISCⅠ，斯坦福大学的MIPS，IBM公司的IBM801相继宣告完成，这些机器被称为第一代RISC机。 SKIP

13 Top 10 80x86 Instructions ( 简单指令占主要部分，使用频率高！) MOV M to R Jcc CMP
MOV R to M BACK ( 简单指令占主要部分，使用频率高！)

14 RISC设计风格的主要特点 (1) 简化的指令系统 指令少 / 寻址方式少 / 指令格式少 / 指令长度一致 (2) 以RR方式工作
除Load/Store指令可访存外，其余指令都只访问寄存器 (3) 指令周期短 以流水线方式工作， 因而除Load/Store指令外，其他简单指令都只需一个或一个不到的时钟周期就可完成 (4) 采用大量通用寄存器，以减少访存次数 (5) 采用硬连线路控制器，不用或少用微程序控制 (6) 采用优化的编译系统，力求有效地支持高级语言程序 MIPS是典型的RISC处理器，82年以来新的指令集大多采用RISC体系结构 x86因为“兼容”的需要，保留了CISC的风格，同时也借鉴了RISC思想

15 指令流水线的实现 可以分5个流水段，最长阶段为200ps 取指令 IFetch 读数/译码 Reg/Dec ALU运算 Exec
假定：最复杂指令执行过程 ① 取指：200ps；②译码和读操作数：50ps；③ALU操作：100ps；④读存储器：200ps；⑤结果写寄存器：50ps。 可以分5个流水段，最长阶段为200ps 取指令 IFetch 读数/译码 Reg/Dec ALU运算 Exec 读/写存储器 Mem 写结果 Write

16 五段流水线数据通路 流水段寄存器：保存每个时钟周期执行的结果! Clk Ifetch (IF) Clock-to-Q delay
Reg/Dec (ID) Exec (Ex) Mem Wr 1 PC+4 PC+4 PC PC+4 Imm Imm Rs Zero busA Data Mem A Ra busB Rb Exec Unit RA Do IUnit IF/ID Register ID/Ex Register Ex/Mem Register Mem/Wr Register Mux 1 The pipelined datapath consists of combination logic blocks separated by pipeline registers. If you get rid of all these registers (not the PC), this pipelined datapath is reduced to the single-cycle datapath. This should give you extra incentive to do a good job on your single cycle processor design homework because you can build your pipeline design based on your single cycle design. Anyway, the registers mark the beginning and the end of a pipe stage. In the multiple clock cycle lecture, I recommended that the best way to think about a logic clock cycle is that it begins slightly after the clock tick and ends right at the next clock tick. For example here, the Reg/Decode stage begins slightly after this clock tick when the output of the IF/ID register has stabilized to its new value AND ends RIGHT at the next clock tick when the output of the register file is clocked into the ID/Exec register. At the end of the Reg/Decode stage, the register output that just clocked into the ID/Exec register has NOT yet propagate to the register output yet. It takes a Clk-to-Q delay. When the new value we just clocked in (points to the clock tick) has propagate to the register output, then we have reach the beginning of the Exec stage. Notice that the Wr stage of the pipeline starts here (last cycle) but there is no corresponding datapath underneath it because the Wr stage of the pipeline is handled by the same part of the pipeline that handles the Register Read stage. This part of the datapath (Reg File) is the only part that is used by more than one stage of the pipeline. This is OK because the register file has independent Read and Write ports. More specifically, the Reg/Decode stage of the pipeline uses the register file’s read port while the Write Back stage of the pipeline uses the register file’s write port. +3 = 32 min. (Y:12) Rt WA RFile Di Rw Di Rt I Rd 1 流水段寄存器：保存每个时钟周期执行的结果!

17 指令流水线的执行举例 考察以下几个点的情况：
Clock Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Ifetch Reg/Dec Exec Mem Wr 0: Load 4: R-type 8: Store 12: Beq End of Cycle 4 End of Cycle 5 End of Cycle 6 End of Cycle 7 考察以下几个点的情况： 周期4结束: Load 的 Mem, R-type 的 Exec, Store 的 Reg, Beq 的 Ifetch 周期5结束: Load 的 Wr, R-type 的 Mem, Store 的 Exec, Beq 的 Reg 周期6结束: R-type 的 Wr, Store 的 Mem, Beq 的 Exec 周期7结束: Store 的 Wr, Beq 的 Mem Well, let’s look at a more complex example so I can show you how different instructions at different stages of execution can be processed by our pipelined datapath simultaneously. Let’s consider the following instruction sequence: Load, R-type, Store, and then Branch on equal to target address 1000. In the next four slides, I will show you the state of the datapath at the end of Cycle 4, Cycle 5, Cycle 6 and Cycle 7. First let’s take a look at the end of Cycle 4 where: (a) The Load instruction has just finished its Mem stage. (b) The R-type instruction has just finished its Exec stage. (c) The Store instruction has just finished its Register Fetch slash Instruction Decode stage. (d) And finally, the Branch instruction has just finish fetching the instruction. Remember now, the next four pictures we will be looking at are at the end of a clock cycle. That is right at the clock tick. +2 = 59 min. (Y:39)

18 指令流水线的执行举例 lw指令与beq、sub、or指令关于$8数据相关 指令lw与beq是load-use数据相关
可通过转发解决数据相关 Load-use数据相关不能通过转发解决 可通过前半周期写后半周期读解决数据相关 beq指令条件满足时，应转200处执行，但在此之前已有3条指令正在执行，需从流水线中冲刷掉 延迟损失时间片C=3

19 流水线的冲突/冒险(hazard)情况 结构冒险 (hardware resource conflicts，硬件资源冲突):
Hazards：指流水线遇到无法正确执行后续指令或执行了不该执行的指令 结构冒险 (hardware resource conflicts，硬件资源冲突): 现象：同一个部件同时被不同指令所使用 一个部件每条指令只能使用1次，且只能在特定周期使用 设置多个部件，以避免冲突。如指令存储器IM 和数据存储器DM分开 数据冒险 (data dependencies，数据相关): 现象：后面指令用到前面指令结果数据时，前面指令的结果还没产生 转发(Forwarding/Bypassing旁路) 或 前半周期读后半周期写 Load-use冒险不能通过转发解决，需阻塞(stall)一个时钟周期 编译程序优化指令顺序 控制 (分支) 冒险 (changes in program flow，改变控制流): 现象：转移或异常改变执行流程，后继指令在目标地址产生前已被取出 采用静态或动态分支预测 编译程序优化指令顺序(分支延迟) 本PPT内容只需大概了解

20 编译器优化指令顺序解决数据冒险 编译器的优化很重要！ Fast code: lw $2, b lw $2, b
以下源程序可生成两种不同的代码，优化的代码可避免Load阻塞 a = b + c; d = e – f; 假定 a, b, c, d ,e, f 在内存 编译器的优化很重要！ Slow code: lw $2, b lw $3, c add $1, $2, $3 sw $1, a lw $5, e lw $6, f sub $4, $5, $6 sw $4, d Fast code: lw $2, b lw $3, c lw $5, e add $1, $2, $3 lw $6, f sw $1, a sub $4, $5, $6 sw $4, d 调整后 如果硬件不支持阻塞处理的话，则编译器可以将顺序调整和插入NOP指令结合起来，在找不到可插入的指令时，插入NOP指令！

21 编译器优化以避免阻塞的情况调查 由此可见，优化调度后load阻塞现象大约降低了1/2~1/3

22 编译器优化指令顺序解决控制冒险 如何对以下程序段进行分支延迟调度？（假定时间片为2） 若分支延迟时间片减少为1 lw $1, 0($2)
基本思想：把分支指令前面的与分支指令无关的指令调到分支指令后面执行，以填充延迟时间片（也称分支延迟槽Branch Delay slot），不够时用nop填充 如何对以下程序段进行分支延迟调度？（假定时间片为2） 若分支延迟时间片减少为1 lw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 add $3, $3,$2 sw $1, 0($2) …… lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) nop add $3, $3,$2 sw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) add $3, $3,$2 sw $1, 0($2) …… 调度后 调度后可能带来其他问题：产生新的load-use数据冒险 调度后，无需在硬件线路中阻塞branch指令后面指令的执行

23 提高性能措施—实现指令级并行 实现指令流内部的并行流水线称为指令级并行（ILP） 有两种指令级并行策略
超流水线（Super- pipelining） 级数更多的流水线 理想情况下，流水线的加速比与流水段的数目成正比 （即：理想情况下，流水段越多，时钟周期越短，指令吞吐率越高） 但是，它会增加开销，且是有极限的！可以怎样突破极限呢？ 多发射流水线（Multiple issue pipelining ） 多条指令(如整数、浮点、装入/存储等) 同时启动并独立运行 前提：有多个执行部件。如定点、浮点、乘/除、取数/存数部件等 结果：能达到小于1的CPI，定义CPI的倒数为IPC （例如：理想的四路多发射流水线的IPC为4） 两种实现方法 静态多发射：由编译器在编译时静态完成指令打包和冒险处理 动态多发射：由硬件在执行时动态完成指令打包和冒险处理 N段流水线说明一个时钟周期内最多有几条指令同时并行执行？ N条！故N越大并行度越高！ CPI =？ CPI =1

24 静态多发射处理器 静态打包时，一定要保证指令内部不会出现冒险！ 由编译器在编译时进行相关性分析和静态分支预测，以静态完成指令打包
指令打包（将同时发射的多条指令合并到一个长指令中） 将同一个时钟周期内发射的多个指令看成是一条多个操作的长指令，称为一个“发射包” “静态多发射”也被称为“超长指令字”（VLIW-Very Long Instruction Word），采用这种技术的处理器被称为VLIW处理器 在同一个周期内发射的指令类型是受限制的（举例:干洗/水洗） 例如，只能是一条ALU指令/分支指令、一条Load/Store指令 IA-64采用这种方法，Intel称其为EPIC（Explicitly Parallel Instruction Computer—显式并行指令计算机） 安腾、安腾2 静态打包时，一定要保证指令内部不会出现冒险！

25 动态多发射处理器 由硬件在执行时动态完成指令打包或冒险处理 通常被称为超标量处理器（Superscalar）
同一个时钟动态发射多条指令，一个周期内可执行一条以上指令 与VLIW处理器的不同点： VLIW处理器：与机器结构密切相关，在结构有差异机器上要重新编译 超标量处理器：编译器仅进行指令顺序调整（还是串行序列），不进行指令打包，而是由硬件根据机器结构决定同时发射哪几条指令。因此，编译后的代码能够被不同结构的机器正确执行 超标量多结合动态流水线调度（Dynamic pipeline scheduling）技术 通过指令相关性检测和动态分支预测等手段，投机性地不按指令顺序执行，当发生流水线阻塞时，可以到后面找指令来执行（乱序执行） 举例说明动态流水线调度技术： 左边指令序列中，哪条指令可以提前执行？ sub指令可提前到addu指令前执行 如果不将sub调到前面，则会影响slti指令的执行，而且还会发生load-use冒险

26 本章小结 CPU的基本功能是周而复始地执行指令，并处理异常和中断。 CPU最基本的部分是数据通路和控制单元
数据通路（datapath）中包含组合逻辑元件和存储信息的状态元件。 组合逻辑（如加法器、ALU、扩展器、多路选择器以及状态元件的读操作逻辑等）用于对数据进行处理； 状态元件包括触发器、寄存器和存储器等，用于对指令执行的中间状态或最终结果进行存储。 控制单元（control unit）：对取出的指令进行译码，与指令执行得到的条件标志或当前机器的状态、时序信号等组合，生成对数据通路进行控制的控制信号。 指令执行过程主要包括取指、译码、取数、运算、存结果。 通常把取出并执行一条指令的时间称为指令周期，它由机器周期或直接由时钟周期组成。现代计算机已经没有机器周期的概念。

27 本章小结 现代计算机的每个指令周期直接由时钟周期（节拍）组成。 时钟信号是CPU中用于控制同步的信号。
每条指令功能不同，因此每条指令执行时数据在数据通路中所经过的部件和路径也可能不同。但是，每条指令在取指令阶段都一样。 早期计算机中数据通路采用总线方式，通过CPU的内部总线把CPU中的通用寄存器、ALU、暂存器、指令寄存器等互连，有单总线、二总线和三总线结构数据通路。 现代计算机的数据通路都采用流水线方式实现，将每条指令的执行过程分解成功能段相同的几个流水段，每个流水段的执行时间也被设置成完全相同。 流水线方式下，同时有多条指令重叠执行，因此程序的执行时间比串行执行方式下缩短很多。在有些情况下会发生流水线冒险，包括结构冒险、数据冒险和控制冒险三类。 高级流水线：超流水、静态多发射（VLIW）、超标量、动态调度