流水线结构.ppt

第四章流水线结构 内容简介 计算机系统结构是指机器语言一级的程序员所看到的计算机属性 本章详细介绍流水线技术 包括先行控制技术 流水线原理 流水线性能分析 相关和相关的处理方法 超标量处理机和超流水线处理机等 讨论系统结构中的并行性问题 单机和多机系统中并行处理的实现以及突破冯 诺依曼型结构的新型计算机系统结构 从而了解新一代计算机的发展动向 8 4新型计算机系统结构8 3多处理机8 2向量处理机8 1流水线技术 本章主要内容 流水线技术 提高计算机的处理速度就要提高处理机指令执行的速度 人们采取的办法通常有三种 1 提高处理机的工作主频 2 采用更好的算法和设计更好的功能部件 3 采用指令级并行技术 3是目前和将来提高处理机指令执行速度的一条主要途径 8 1 1先行控制技术 1 指令的重叠执行方式处理机在执行多条指令时 有多种执行控制方式 顺序方式 重叠方式 先行控制方式 流水线控制方式等 我们先从最简单的来讲 一条指令的执行过程可以分为多个阶段 通常 把 条指令的执行过程分为3个阶段 取指令分析指令执行指令 时间t 取指令阶段 按照指令计数器的内容访问主存储器 取出一条指令送到指令寄存器 分析指令阶段 对指令的操作码进行译码后 按照给定的寻址方式和地址字段中的内容形成操作数的地址 并用这个地址读取操作数 操作数可能在主存储器或寄存器中 指令阶段 是指根据操作码的要求 完成指令规定的功能 在此期间 要把运算结果写到寄存器或主存储器中 指令的几种执行方式 假设取指令 分析指令和执行指令的时间都相等 每段的时间都为t 执行一条指令的时间为T1 则T1 t取指令 t分析指令 t执行指令 3t 1 顺序执行方式如图8 2 a 所示 采用顺序执行方式执行n条指令所用时间为 Tn 3t n 3nt 2 一次重叠执行方式如图8 2 b 图所示 这是一种最简单的重叠方式 把执行第k条指令与取第k十1条指令同时进行 则执行n条指令所用的时间为 Tn 3 t 2t n 1 1 2n t 3 二次重叠执行方式 如图8 2 c 所示 我们如果把取第k十1条指令提前到与分析第k条指令同时进行 那么 分析第k十l条指令会与执行第k条指令同时进行 则执行n条指令所用的时间为 T 3 t t n 1 2 n t 采用一次重叠执行方式 指令的执行时间缩短了近二分之 而且各功能部件在并行工作 利用率明显提高 采用二次重叠执行方式能够将指令的执行时间缩短近三分之二 进 步提高了指令的执行速度 但是处理机中同时在取指令 分析和执行指令 因此 要把顺序执行方式中的一个集中的指令控制器分解为三个相对独立的控制器来同时发出三种控制信号 它们是主存储控制器 指令控制器 运算控制器 另外 在指令分析或指令执行过程中都要访问主存储器取指令 存在解决访问主存储器的冲突问题 现代计算机的指令系统非常复杂 我们前面假设的情况是一种理想状态 在实际当中 各种指令难以做到 分析 与 执行 时间始终相等 所以二次重叠执行方式是 种理想的指令执行方式 2 先行控制技术要解决二次重叠执行方式中存在的访问主存储器的冲突问题 方法有三种 第一 把主存储器分成两个独立编址的存储器 一个专门存放指令 称为指令存储器 另一个专门存放操作数 称为数据存储器 两个存储器同时独立访问 解决了取指令和读操作数的冲突 第二 指令和数据仍然混合存放在同一个主存作储器内 采用低位交叉存取方式 第三 解决访问存储器冲突的根本办法是处理机结构作较大的改变 采用先行控制技术 先行控制的基本思想是使分析部件和执行部件能分别连续不断地分析和执行指令 这种技术实际上是预处理技术和缓冲技术的结合 即通过对指令流和数据流的预处理和缓冲 能够尽量使指令分析器和指令执行部件独立地工作 并始终处于忙碌状态 这样 就能够使取指令 分析指令和执行指令重叠起来执行 使指令分析器和执行部件能尽量地连续工作 而且 在采用了缓冲技术和预处理技术之后 运算器能够专心干数据的运算 从而大幅度提高指令的执行速度 在正常情况下 处理机中同时有三条指令在执行 先行控制技术最早在IBM公司研制的机器中采用 目前 先行控制技术是现代计算机系统中被普遍采用的一项重要技术 许多处理机中都已经采用了这种技术 包括超流水线处理机和超标量处理机等 8 1 2流水线 流水处理技术是在重叠 先行控制方式的基础上发展起来的 它基于重叠的原理 但却是在更高程度上的重叠 流水线方式是把一个重复的过程分解为若干个子过程 每个子过程可以与其他子过程同时进行 由于这种工作方式与工厂中生产流水线十分相似 因此 把它称为流水线工作方式 1 流水线工作原理根据上面的重叠技术和先行控制技术 进一步发展应用就是标量流水技术 假如把一条指令的解释过程进一步细分成取指 译码 执行 访存 写回寄存器五个子过程 并用五个独立的功能部件分别处理每个子过程 那么就像工厂中的流水线 五个子部件可以同时对不同的五条指令中的相对应的子过程进行操作 在流水技术中有如下一些特点 1 一条流水线由多个流水段组成 2 每个流水段有专门的功能部件对指令进行某种加工 3 各流水段所需时间是一样的 4 在理想情况下 在流水线上 每隔 t时间将会有一个结果流出流水线 描述流水线常用的方法是用 时空图 在时空图中 横坐标表示时间 也就是输入到流水线中的各个任务在流水线中所经过的时间 当流水线中的各个功能部件的执行时间都相等时 横坐标被分割成相等长度的时间段 纵坐标表示空间 即流水线的各个子过程 在时空图中 流水线的一个子过程通常称为 功能段 前面的例子用时空图描述如图8 3所示 2 流水线的分类从不同的角度 按照不同的观点 可以把流水线分成多种不同的种类 从名称上能反映这种流水线在某一方面的特点或性能 1 按流水线结构分类如图8 4 a 所示 按照流水线的各个功能段之间是否有反馈信号 可以把流水线分为线性与非线性流水线两类 线性流水线中 输入数据从流水线的一端进入 另一端输出 各功能段逐个串接起来 如图8 4 a 所示 这种方式下 数据在流水线中的各个功能段仅仅流过一次 所以通常一条线性流水线只能完成 种固定的功能 非线性流水线中 除有串行连接通路外 还有反馈回路 在流水过程中 某些功能段要重复使用 如图8 4 b 所示 功能段S2的输出又被反馈回送给S2的输入端 因为 功能段S2可能要被多次调用 所以这时流水线中数据由输入端到输出端不再是经过原来的三个时钟周期 还要加上反馈回路多次调用的执行周期 非线性流水线中 除有串行连接通路外 还有反馈回路 在流水过程中 某些功能段要重复使用 如图8 4 b 所示 功能段S2的输出又被反馈回送给S2的输入端 因为 功能段S2可能要被多次调用 所以这时流水线中数据由输入端到输出端不再是经过原来的三个时钟周期 还要加上反馈回路多次调用的执行周期 图8 4线性与非线性流水线 在非线性流水线中 只用图8 4 b 这样一种连接图不能表示出一个任务在非线性流水线中的实际流动的过程 还要用一张 预约表 两者共同来表示流水线的工作情况 在预约表中可以很清楚地表示出反馈回路的使用次数 如图8 5所示 它表示图8 4 b 中S2在反馈回路仅重复使用 次的预约表 图中用 表示功能段在相应的这一段时间内有效 即任务经过了这一个功能段 条非线性流水线可以对应有很多张预约表 一张预约表表示非线性流水线的一种工作方式 图8 5非线性流水线预约表 3 流水线的性能衡量流水线性能的主要指标有吞吐率 加速比和效率 1 流水线吞吐率最大吞吐率指流水线达到稳定状态后 单位时间内处理的任务总数 实际吞吐率是指单位时间内能处理的任务数或输出结果的数量 它总是小于最大吞吐率 因为流水线有 装入时间 和 排空时间 以及其他因素也会影响流水线的连续流动 2 加速比 不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比 即采用流水方式后的工作速度与顺序串行方式的工作速度之比 3 流水线效率 指流水线中各功能部件的利用率 4 数据相关与控制相关由于流水线中同时要处理多条指令 所以各种各样的冲突几率就会很大 比如在执行一条指令的过程中 如果用到的指令 操作数 变址偏移量等正好是前面指令的执行结果 则必须等待前面的指令执行完成 并把结果写到主存或通用寄存器中之后 本条指令才能开始执行 当后继指令的操作数刚好是前一指令的运算结果的情况下 也会发生不协调的情况等等 类似这些冲突我们称之为相关 在流水线中相关分为两大类 类是数据相关 另一类是控制相关 流水线技术必须较好的解决解这些相关问题 1 数据相关在采用先行控制方式的处理机中 数据相关有四种情况 它们是指令相关 主存操作数相关 通用寄存器相关和变址相关等 解决数据相关的方法有两种 一种方法是推后分析法 即在遇到数据相关时 就停顿后继指令的执行 直到前面指令的结果已经生成后再继续 另一种方法是设置专用路 即旁路技术 就是使用专门设置的通路将产生的结果直接送往需要它的地方而不是通过寄存器再访问 这样就可使流水线不发生停顿 在按序流动的流水线中 只可能出现主操作数相关 可通过定向传送的方法解决 在非按序流动的流水线中 则各种相关都可能发生 在RISC机流水线中 还存在一种装入延迟 解决这种装入延迟的办法是采用硬件联锁或重排指令的优化编译方法 2 控制相关控制相关是指由条件分支指令 转子程序指令 中断等引起的相关 例如 在执行条件转移指令 前一条指令还没有生成条件码 当转移发生时 将使流水线的流动受到破坏 为了减少因转移引起的流水线性能损失 可采用下述方法 一种是同数据相关的推后法 另一种是猜测法 尽早判别转移是否发生 尽早生成转移目标地址 加快和提前形成条件码 推后法实现起来简单 但是由于等待而降低了流水线效率 其他解决相关的方法在控制上要复杂一些 8 1 3超标量处理机与超流水线处理机 一般的流水线处理机只有一条指令流水线 一个多功能的操作部件 每个时钟周期 取指令 和 分析 完成一条指令 另一种流水线处理机虽然也只有一条指令流水线 每个时钟周期 取指令 和 分析 完成一条指令 但是有多个独立的操作部件 可以同时并行工作 例如 定点算术逻辑部件 浮点加减法部件 乘除法部件 取数存数部件等 这种处理机通常称为多操作部件处理机 1 超标量处理机超标量处理机 一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机 超标量处理机最基本的要求是必须有两套或两条以上完整的指令执行部件 它是利用硬件资源重复来实现空间的并行操作 主要特点是 有多个性能不同的处理部件 将可并行执行的指令送往不同的执行部件 形成多条流水线并行处理 由于超标量处理机在一个时钟周期内能够发射多条指令 因此 它对指令序列的要求与单流水线的标量处理机不同 在单流水线的标量处理机中 只有连续出现相同操作的指令序列时 流水线才能不 断流 功能部件的效率才能得到充分发挥 2 超流水线处理机超流水线处理机的工作方式与超标量处理机不同 在一个时钟周期内能够分时发射多条指令的处理机称为超流水处理机 它只需要增加少量硬件 通过各部分硬件的充分重叠工作来提高处理机性能 而超流水线处理机采用的是时间并行性 为了进一步提高处理机的指令级并行度 可以把超标量技术与超流水线技术结合在一起 这就是超标量超流水线处理机 8 2 1向量流水的基本概念 1 向量数据向量数据是一组不相关数据的集合 向量元素之间的次序是固定的 而且所有的数据元素具有相同的结构 如数据类型 数据长度等属性相同 所谓不相关即对向量中任意一个数据元素的操作 结果不影响到其他向量元素 比如有一个数组 我们要使数组中的每一个元素Ai都乘以一个数b 它们的结果互不影响 各自独立 向量数据的参数有 起始地址 即第一个向量元素存放的地址 向量长度 即向量元素的数量 向量间距 即相邻两个向量元素之间的距离 2 向量流水的主要特点因为一个向量数据中 包含有N个数据元素 对这个向量数据处理一次 就是处理了N次数据 所以 一条向量指令就相当于多个标量数据的循环 而且向量指令所要访问的向量元素均相邻 可以依次访问它们 比一串标量指令操作快 并且消除了标量数据中由循环引起的控制相关 向量流水线由于无数据相关 无程序转移 流水线可以充满 从而获得较高的吞吐率和流水线效率 由于取一次指令便可以完成很长的向量运算 所以要求向量计算机的存储器系统能提供给运算器连续不断的数据流 以及接收来自运算器的连续不断的运算结果 这是设计存储器系统的困难之处 8 2 2向量处理机的结构与性能 1 向量处理机的结构系统结构设计中所面临的主要问题是 如何设计出一个能满足运算器带宽要求的存储器系统 目前向量计算机采用两种方法 1 利用几个独立的存储器完成对相互独立的数据的并发访问 从而达到所要求的存储器带宽 即存储器 存储器结构 2 构造一个具有所要求带宽的高速中间存储器 并能实现该高速中间存储器与主存储器之间的快速数据交换 即寄存器 寄存器结构 存储器 存储器结构的向量处理机的工作特点 是向量操作的源向量都取自内存 且操作生成的结果向量也存放到内存中 而寄存器 寄存器结构的向量处理机 则都取自或存放到向量寄存器中 在向量机中 为了加快向量操作 采用多个独立的功能部件 并使它们并行工作 因为这些部件都是独立的 所以只要符合下面的条件 它们就可以并行工作 1 不存在向量寄存器使用冲突 向量寄存器使用冲突就是指多条并行工作的向量指令中的源向量或结果向量使用相同的向量寄存器 2 不存在功能部件使用冲突 功能部件冲突是指多条向量指令都要使用同一个功能部件 如两条向量指令都是加法运算时 浮点加的功能部件就无法同时满足 而发生冲突 8 3多处理机系统 1 多处理机系统的组成多处理机系统的组成有以下几部分 1 两个或两个以上功能大致相同的处理器 2 由所有处理器共享的一个公共主存和I O通道 控制器和外设 3 在处理器和程序之间实现作业 任务 程序段 数组和数组元素等各级的全面并行 必须有统一控制的操作系统 2 多处理机系统的特点多处理机系统属于多指令流多数据流 MIMD 结构 与属于单指令流多数据流 SIMD 计算机有很大的不同 流水线机 并行处理机都属于SIMD计算机 多处理机实现的是任务作业一级的并行 SIMD计算机只能实现指令间的并行操作 所谓任务级是指比较独立的程序段 也就是同时并行执行多段程序 在结构上多处理机系统中的每个处理机都需要有各自的控制部件 以执行各自的程序 并用复杂的互连网络实现各个处理机间的通信 在算法上也不局限于某种算法 而是充分利用通用算法的各种并行性 在系统软件上要解决多处理机的资源的管理与进程调度等多种问题 因而 多处理机具有较强的通用性 适用于向量 标量 各种数据的不同处理 也适用于多种算法 结构灵活 可以实现多种机间连接 图8 8是一种多处理机结构 8 3 2多处理机结构 多处理机在系统结构上分为两类 紧耦合系统和松耦合系统 1 松耦合系统松耦合系统也称为间接耦合系统 通常通过通道或通信线路实现机间联系 通过消息传递方式来实现处理机间的相互通信 信息传送的速度较慢 而且每个处理机是一个独立性较强的计算机模块 8 3 2多处理机结构 2 紧耦合系统紧耦合系统也称为直接耦合系统 目前大多数多处理机系统都属于紧耦合系统 紧耦合是通过共享主存实现处理机间的互相通信 主存储器对所有的处理机有一个统一的地址编址 系统中的各台处理机既可以共同执行一个任务 也可以同时执行几个程序 各处理机通过一个公共的硬件资源连接在一起 处理机间的相互联系比较紧密 按所用处理机类型是否相同及对称 又可分为同构或异构及对称或非对称的形式 常见组合是同构对称式和异构非对称式多机系统 8 4 1计算机系统结构的新概念 各种不同的系统结构按照计算机内部的控制机制可分为控制驱动 数据驱动 需求驱动和模式匹配四种类型 1 控制驱动这是传统的冯 诺依曼系统结构使用的控制方式 计算机中有一个程序计数器PC 每执行一条指令 程序计数器就自动加 1 指向下一条指令的地址单元 可见程序的执行是在程序计数器的控制下进行的 当它指向某条指令时 才驱动该条指令的执行 我们把这种方式称为控制驱动 2 数据驱动数据驱动控制方式 与上面的控制驱动方式不同 它的指令不是在控制下顺序执行的 当且仅当指令所需要的数据可用时 指令就可执行 即任何指令只要它所需要的操作数全部齐备且可用时 这些指令就可以同时执行 不需要程序计数器 可见指令的执行不受其他控制条件的约束 这种方式中 不使用变量 不存在数据共享等 数据驱动的原理形成了两个优点 指令的执行是无序的 完全受数据流的驱动 与指令在程序中出现的先后顺序无关 直接支持函数语言 有利于开发程序中各级的并行性 而且有利于改善软件环境 缩短软件的研制时间 3 需求驱动在需求驱动的系统结构中 需要执行哪一条指令时 该指令就被驱动执行 我们举例说明 例如 求X Y Z 1 Y 用函数的形式可以表示成 求X f u f u h v g w h v Y z g w 1 y 需求驱动的执行过程是这样的 求X 就必须求f u 求f u 就必须求h v 和g w 4 模式匹配驱动模式驱动控制方式是 给定模式匹配符号串 搜索与该对象相匹配的对象 一旦匹配就驱动执行该指令 8 4 2新概念系统结构计算机 1 数据流计算机 1 驱动原理在数据流计算机中有两种驱动方式 种是数据驱动方式 只要某一个操作所要求的输入数据全部到齐而且可用时 该操作就可以立即执行 另一种是需求驱动驱动方式 只有当某一个函数需要某 个自变量时才驱动对该自变量的求值操作 在数据流计算机没有变量的概念 在指令之间直接传送数据 有纯函数的特点 数据流计算机中数据流运算具有异步性 并行性 函数性和局部性的特点 需求驱动方式与数据驱动方式相比可以减少许多不必要的操作 有助于提高处理机的工作效率 但需求驱动方式实现起来更为困难 目前的数据流计算机一般采用数据驱动方式 2 数据流计算机模型在数据流计算机中 信息项以操作包和数据 令牌 形式出现 操作包由操作码 操作数和其后继指令所在地组成 令牌实质是一种表示某一操作数或参数已准备就绪的标志数据 数据流机根据对数据令牌处理方式的不同 可以分为静态和动态两类结构 2 面向函数程序设计语言的归约机归约机和数据流机一样 都是基于数据流的计算