(精品)浙江工商大学-计算机体系结构-第4章 多处理器和线程级并行.ppt

第4章 多处理器和线程级并行o简介o对称式共享存储器系统结构o对称式共享存储器多处理器的性能o分布式共享存储器o同步o存储器连贯性模型 4.1 简介o问题引出 尽管单处理器仍在发展，但多处理器自20世纪末开始显得越来越重要，由于开发ILP的空间正在减少，单处理器的发展速度正在逐步变慢，使得多处理器唱主角的时代到来。对多处理器的依赖还体现在以下方面：对服务器及其性能的关注不断增加、以数据为中心的应用不断增多、工业制造中批量复制比专门生产的方法更有优势，而多处理器正好有此优势4.1 简介o并行系统结构分类 根据数据流和指令流的并行度，将计算机分为四类 1、单指令流单数据流（SISD）:单处理器 2、单指令流多数据流（SIMD）同一条指令被多个使用不同数据流的多处理器执行。通过将相同的操作以并行的方式应用于数据的各个项来实现数据级的并行，每个处理器有自己的数据存储器，但系统中有唯一的指令存储器和控制处理器，用来获取和分配指令。4.1 简介o并行系统结构分类 根据数据流和指令流的并行度，将计算机分为四类 3、多指令流单数据流（MISD）至今无此类型的商用机 4、多指令流多数据流（MIMD）每个处理器取自己的指令并对自己的数据进行操作，多个线程按并行操作，计算机实现线程级并行，这种线程级并行比数据级并行更加灵活，用途也更为广泛。4.1 简介o并行系统结构分类 MIMD的优势 1、灵活性强 在必要的软件和硬件支持下，MIMD既能作为单用户多处理器为单一应用程序提供高性能，又可作为同时运行多个任务的多道程序多处理器系统使用，还可以提供结合这两种任务的应用。2、能够充分利用现有处理器的性价比优势 多核芯片通过复制方式可降低单处理器设计成本4.1 简介o几个概念 多核：又称为片内多处理器或单芯片多处理器，在一个单独的晶片上设计多个处理器，多个内核共享一些资源如二级缓存、存储器和I/O总线 进程：是可以独立运行的一段代码，进程的状态包含了处理器运行这个进程的所有必要信息。线程：指运行在不同处理器上的多个执行过程，允许不同的地址空间上多个进程同时执行，也允许共享的地址空间上多个线程同时执行。4.1 简介oMIMD分类 根据处理器个数分为两类，这两类机器的存储器组织方式和互联测量不相同，根据存储器组织方存储器组织方式式而不是处理器构成方式区分多处理器种类。1、集中式共享存储器系统结构（图4.1）最多拥有几十个处理器，但随着处理器数目的增多，共享单个集中式存储器方案前景不被看好.存储器对每个处理器都是对等的，顾也称为对称多处理器系统，该系统是目前最流行的系统结构.4.1 简介oMIMD分类 2、分布式存储器系统结构（图4.2）支持更多的处理器，存储器按照分布式组织。系统基本结构由多个独立节点构成，每个节点包含处理器、存储器、输入输出和互连网络接口，各个节点通过互连网络连接在一起。分布式存储器结构优点是缩短了本地存储器访问的时延，缺点是处理器间的数据通信变得更加复杂且时延也更大。4.1 简介o通信和存储器系统结构模型 根据处理器间传递数据的方法，有两种不同的系统结构：1、通过共享的地址空间进行通信 共享存储器指的是共享寻址空间，物理上分开的存储器能够作为逻辑上共享的地址空间进行寻址，只要有正确的访问权限，任何一个节点都能够通过引用地址的方式访问任意节点上的存储器。4.1 简介o通信和存储器系统结构模型 根据处理器间传递数据的方法，有两种不同的系统结构：2、通过私有的地址空间进行通信 私有的地址空间在逻辑上是分散的，不能被远程的处理器寻址，每个处理器-存储器模块本质上是一台独立的计算机。4.1 简介o并行处理遇到的挑战 有两个障碍使得并行处理遇到了挑战，第一个障碍是程序可获得的并行度是有限的；第二个障碍来自于通信相对较高的开销。这两个障碍使得并行处理器难以得到较高的性价比（见P138-139页例子）并行度低和远程通信时延太长是多处理器的最大挑战，后面集中讨论减少通信时延技术4.2 对称式共享存储器系统结构 对称式共享存储器系统支持共享和私有数据的缓存，私有数据被单个处理器使用，共享数据被多个处理器使用，基本上是通过读写共享数据完成处理器之间的通信。把私有数据缓存后，对该数据的访问可以在Cache中进行，共享数据可以在Cache中形成多个副本，这样可以减少访问时延和降低对存储器带宽的要求，但会产生Cache一致性问题。4.2 对称式共享存储器系统结构o处理器的Cache 一致性 缓存共享带来了新的问题，如果没有其他的防范措施，会导致两个处理器得到两个不同的值（见图4.3）.如果在一个存储器系统中读取任何一个数据项的返回结果总是最近写入的数值，那么就认为该存储器具有一致性。该定义包含了一致性和连贯性两个方面，一致性定义了读操作可以返回什么样的数值，连贯性定义了写入的数值什么时候才能被都操作返回4.2 对称式共享存储器系统结构o存储器一致性满足的条件 1、处理器P对地址X的写操作后面紧跟着P对X的读操作，而且这次读操作和写操作之间没有其他处理器对X的写操作，读操作总是返回P写入的数值。2、在其他处理器对X的写操作后，处理器P对X进行读操作，这两个操作之间有足够的间隔而且没有其他处理器对X进行写操作，读操作返回的是写入的数值。3、对同一个地址的写操作是串行执行的。4.2 对称式共享存储器系统结构o存储器一致性满足的条件 虽然上面三个性质可以保证一致性，但写入的数据什么时候可以读取也是至关重要的。如果某个处理器对X的写操作只领先其他处理器对X的读操作很小一段时间，那么就无法保证该读操作能返回写入的数值，因为这一刻写入的数据甚至可能还没有被处理器发送出去。存储器连贯性模型定义了写入的数值在什么时候才可以被读操作读出的问题，此问题后面讨论。4.2 对称式共享存储器系统结构o存储器一致性和连贯性 一致性和连贯性是互补的，一致性定义了对同一个存储器地址进行的读写操作行为，而连贯性定义了关于访问其他存储器地址的读写操作。有两个假设：一是直到所有处理器都看到了写操作的结果后一个写操作才算完成，并且后续的写操作才可以开始；二是处理器不会因为其他存储器操作而改变写操作的顺序。4.2 对称式共享存储器系统结构o实施一致性的基本方案 Cache在本地为那些被同时读取的共享数据做了备份，一致性的Cache要为这些数据提供副本，副本可以减少访问时延。为了维护Cache一致性，小规模多处理器是通过在硬件上引入一个协议解决的 这个协议称为Cache一致性协议，实现该协议的关键在于跟踪所有数据块的状态，目前广泛采用的有两类协议，目录式和监听式。4.2 对称式共享存储器系统结构o实施一致性的基本方案 目录式：把物理存储器的共享状态存放在一个地点，称之为目录。目录式一致性比监听式的实现开销略高，但是可以用来扩展更多的处理器。监听式：每个含有物理存储器中数据块副本的Cache还要保留该数据块共享状态的副本，但是并不集中地保存状态。Cache通常通过广播的方式访问，所有的Cache控制器对总线进行监听，来确定它们是否含有总线上请求的数据块的副本。4.2 对称式共享存储器系统结构o监听协议 写无效协议：在处理器写数据项之前保证该处理器能独占地访问数据项，在执行写操作时要使其他副本无效，该协议是目前在监听和目录方案中最常用的协议。写广播协议：写入数据项时更新该数据项所有的副本，该协议必须将所有的写操作广播给共享Cache，需要更大的带宽。4.2 对称式共享存储器系统结构o基本实现技术 写无效的基本思路 小规模多处理器中实现写无效协议可使用总线或广播的方式来完成无效操作。要实现无效操作，处理器只要取得总线控制权然后在总线上广播无效数据地址即可。所有的处理器都要不断地监听总线来监测地址。处理器要检查各自的Cache 中是否有总线上广播的地址，如果有，则Cache中相应的数据要置为无效。4.2 对称式共享存储器系统结构o基本实现技术 共享块的操作 当向一个共享块执行写操作时，写处理器必须获得对总线的访问权才能广播无效性操作。若两个处理器同时对一个共享块执行写操作，其广播无效的请求会通过总线的仲裁实现串行化。所有的一致性方案都要求通过某种方式来实现对同一Cache块的串行化访问，包括对通信媒介的访问和对其他共享结构的访问。4.2 对称式共享存储器系统结构o基本实现技术 Cache块中的标识位 利用Cache块中的标识位可以实现监听过程，其中数据块的有效位使得实现无效操作更加容易。任何读操作缺失都可以通过监听总线来直接解决；对于写操作，需要知道其他Cache中是否存有该数据块的副本，如果没有其他副本，则不用将写操作放到总线上，不发送写操作能够节省时间和带宽。4.2 对称式共享存储器系统结构o基本实现技术 Cache块中的标识位 要跟踪一个Cache数据块是否能被共享，需要为每一个数据块增加一个状态位。增加数据块是否被共享的状态位之后，执行写操作时就可以据此来判定是否需要发送无效操作。当对共享数据执行写操作时，Cache会在总线上发送一个无效操作并把该块标记为私有。拥有Cache块唯一一个副本的处理器称为该块的所有者。4.2 对称式共享存储器系统结构o基本实现技术 Cache块中的标识位 当发送无效操作时，所有者的Cache块从共享状态变成独占状态。稍后如果其他处理器请求这个Cache块，那么它会再次变成共享状态。因为Cache对总线的监听同样可以观测到缺失的现象，所以它能够发现其他处理器请求独占Cache块的情况，并且会把状态设置成共享。4.2 对称式共享存储器系统结构o监听协议的局限性 随着处理器数目的增加或是对存储器要求的增加，系统集中式资源会变成瓶颈。在最简单的基于总线的多处理器中，总线必须同时支持一致性通信和由于Cache导致的存储器通信。同样，对于只有一个存储器部件，就必须处理所有的处理器请求。随着处理器的飞速发展，单独一条总线或单独一个物理存储器所能支持的处理器数量正在下降。4.2 对称式共享存储器系统结构o监听协议的局限性 为了增加处理器和存储器之间的通信带宽，设计者使用多种总线以及各种互联网络，像交叉开关或小型点对点网络。在这样的设计中，存储器系统可以被配置成多个物理组，以便在保持均匀存储器访问时间的情况下增加存储器有效带宽，参照图4.8，它是共享式存储器和分布式存储器的结合。4.2 对称式共享存储器系统结构o实现监听Cache一致性 实现监听一致性协议的主要复杂性是在任何最新的多处理器中，写缺失或更新缺失都不是原子操作。监测写缺失或更新缺失、与其他处理器和存储器的通信、对于写缺失得到的最新值、保证每个无效操作都被处理以及更新Cache，这些步骤均无法在一个单循环中完成。4.2 对称式共享存储器系统结构o实现监听Cache一致性 在简单单总线系统中，可以通过首先竞争总线和直到操作完成才释放总线的方式将这些步骤变成有效的原子操作。在没有总线的系统中，必须找到发生缺失时将这些步骤变成原子操作的其他方法。在监听系统中，保证竞争只有一个胜利者的方法是对所有的缺失使用广播来实现，具体可参照附录H中的细节。4.3 对称共享存储器多处理器性能oCache缺失的影响因素 Cache的总体性能由单处理器的Cache缺失通信和由通信造成的数据传输共同决定，后者会造成无效的和随之而来的Cache缺失。改变处理器个数、Cache大小、块大小都会以不同方式影响缺失率。4.3 对称共享存储器多处理器性能o几个概念 由处理器间通信引起的缺失，称为一致性缺失，分为两种：1、真共享缺失 由Cache一致性机制下的数据通信产生。处理器对共享Cache块的第一次写操作引发无效事件，从而获得该块的独占权。除此之外，另一个处理器试图从该Cache块中读一个已修改的字时，会产生一个缺失，该缺失由处理器间共享数据引起，称为真共享缺失。4.3 对称共享存储器多处理器性能o几个概念 2、假共享 是由于使用基于无效的一致性算法引起的。该算法利用了数据块的有效位，而这个有效位每个数据块只有一个。对数据块的某些字执行写操作而导致该数据块被置为无效后，再对该块中的另一些字执行写操作时，就会发生假共享现象。在假共享缺失中，共享的是数据块，并没有共享单个值。4.3 对称共享存储器多处理器性能o几个概念 2、假共享 如果在写操作中将其他处理器中的数据副本置为无效之后，这些处理器再次使用已经写入的数据，那么该调用是一个真共享调用并会导致缺失，而缺失与块的大小或字的位置无关。然而，如果写入的值和读取的字不相同，那么无效并不会引发传输新数值的操作，而只是导致多余的Cache缺失，该缺失为假共享缺失。4.3 对称共享存储器多处理器性能 例子：假如字x1和x2处于同一块Cache中，这个Cache块在Cache P1和P2中均为共享状态。P1和P2两个Cache在这之前已经读入了x1和x2。假如有如下事件序列，请区分每个缺失究竟是真共享Cache还是假共享Cache，或是命中。如果数据块大小是一个字，任何能够发生的缺失就都是真共享缺失了。4.3 对称共享存储器多处理器性能 -时序 P1 P2 1 写x1 2 读x2 3 写x1 4 写x2 5 读x2 -答案：1真 2假 3假 4假 5真4.3 对称共享存储器多处理器性能o多道程序和操作系统负载 负载分为3个不同阶段：编译基本测试程序，包括子计算活动；在库里建立对象文件；移除对象文件。最后一个阶段完全由I/O控制而且只有两个活动的进程，每个负责一个运行。在中间阶段，主要是依靠I/O，处理器大部分时间是空闲的。多道程序负载至少对于操作系统来讲有明显的指令Cache性能损失。不论Cache的大小是多少，用户级指令Cache缺失大约为操作系统速率的1/6。4.3 对称共享存储器多处理器性能o多道程序和操作系统负载的性能 改变Cache容量和块大小对多道程序工作负载的Cache性能产生影响。操作系统的行为比用户进程会导致更多的Cache缺失，除了操作系统有更大的代码容量和局限性缺失原因外，还有两个原因：第一，内核把页分配给用户之前首先要初始化所有页，这极大地增加了内核的强制性缺失率；第二，内核实际上共享数据，因此不能忽视一致性缺失率。用户进程只有被调度到另一个处理器上才会引起缺失，这部分比例小。4.3 对称共享存储器多处理器性能o多道程序和操作系统负载的性能 图4.16给出了数据缺失率与数据Cache大小的比率。增加数据Cache的大小对用户缺失率的影响比内核缺失率的影响要大。增加数据块的大小对缺失率有好的效果，因为大部分缺失属于容量缺失，这种缺失可以通过增大数据块大小得到改进。4.3 对称共享存储器多处理器性能o多道程序和操作系统负载的性能 对于多道程序工作负载，操作系统对存储器系统的要求是非常苛刻的。如果工作负载中包含了更多的操作系统或类操作系统活动，那么要想构建一个能力足够大的存储器系统是非常困难的。要改善性能也许可以通过更好的编程环境或编程帮助，使得操作系统更加关注Cache的活动。例如，对于来自不同系统调用发出的请求，操作系统会重用存储器，这和过程调用中的堆栈位置重用情况类似。4.4 分布式存储器 通过分配存储器的方式可以增加存储器带宽和互连带宽，这种方式可以将本地存储器通信和远程存储器通信迅速分开，这就减少了对存储器系统和互连网络的带宽要求。4.4 分布式存储器o目录协议 目录协议是基于监听一致性协议的一种替代方式，该协议保存每个Cache数据块的状态。目录中的信息包括哪个Cache拥有该块的副本，是否处于脏状态等等，目录协议同样可以用于集中式共享存储器中减少带宽要求。4.4 分布式存储器o目录协议 最简单的目录协议的实现机制是在目录中给每个存储器数据块分配一个条目，在这样的设计中，信息个数与存储器中块的个数和处理器个数的乘积成正比。这对于处理器数目小于200的处理器系统来说不成问题，因为目录的开销还可以接受。4.4 分布式存储器o目录协议 为了防止目录成为瓶颈，需要使目录随存储器分布，这样访问不同的目录就要到不同的地点，正如要在不同的存储器上执行不同的存储器请求一样。分布目录使得数据块的共享状态总是位于一个已知的地点，正是这个特性避免了一致性协议中的广播。图4.19给出了每个节点上带有目录的分布式存储器多处理器系统。4.4 分布式存储器o基于目录的Cache一致性协议 目录协议必须实现两个基本操作：处理读缺失和处理共享未修改Cache块的写操作。为了实现这些操作，目录必须跟踪每个Cache块的状态，可能出现的状态如下：共享：一个或多个处理器拥有Cache数据块，并且存储器中的数值也是最新的。未缓存：没有任何一个处理器含有该数据块副本 修改：只有一个处理器拥有该Cache块的副本并且对该块执行写操作，存储器中的副本是无效的。4.4 分布式存储器o基于目录的Cache一致性协议 除了跟踪Cache中每个块的状态外，还必须跟踪拥有共享数据块副本的处理器，因为执行写操作后这些处理器中的副本要设置成无效状态。实现这一功能最简单的方法是为每个存储器保留一个位向量。当块处于共享状态时，向量的每一位表示所对应的处理器是否拥有该块的副本。当块处于独占状态时，可以利用位向量来跟踪块的所有者。4.4 分布式存储器o基于目录的Cache一致性协议 每个Cache上的状态及转换与监听协议中的相同，只是转换中执行的动作稍有不同。数据项的独占副本的无效化和定位过程是不同的，因为两者都包括请求节点和目录间以及目录和一个或多个远程节点间的通信。在监听协议中，这两步是通过向所有节点广播的方式结合在一起的。4.4 分布式存储器o基于目录的Cache一致性协议 几个概念：本地节点、主节点和远程节点 本地节点：是指产生请求的节点 主节点：是指存储地址和目录条目所在的节点 远程节点：是指拥有Cahce块副本的节点，该副本可能处于共享状态，也可能处于独占状态（这时是唯一的副本），远程节点可以和本地节点或主节点相同。4.4 分布式存储器o基于目录的Cache一致性协议 实际多处理器中使用的目录协议需要优化，发生对独占状态数据块的读缺失或写缺失时，该块首先被送到主节点的目录，在那里存入主存储器中并被送到发出请求的节点上，商用处理器系统中使用的许多协议把数据从所有者节点直接送到请求节点上，这增加了协议的复杂性，更多内容参照附录H。4.5 同步o概述 同步是通过用户层的软件例程来构造的，这些例程要使用硬件提供的同步指令，关键是要在硬件上支持一条不可中断的指令或指令序列，该指令或序列能以原子操作的方式取回数据并修改其值。本节关注锁和解锁同步操作的实现，锁和解锁可以被直接用来实现互斥机制，以及实现更加复杂的同步机制4.5 同步o基本硬件原语 原子互换：是一个典型的构建同步原语的操作，它将一个寄存器中的值和一个存储器中的值进行互换，互换是不可割裂的，且两个同时进行的互换将由写串行机制进行排序，这种方式使得两个试图设置同步变量的处理器不可能同时完成设置。4.5 同步o基本硬件原语 构造同步操作可以先构造一个简单的锁，其中0表示该锁可以占用，1表示不能占用。如果处理器想占用该锁，可以通过将寄存器中的1与该锁在存储器中的值互换来实现。如果有其他处理器占用了该锁，返回结果为1，否则为0。如果返回结果为0，锁的值被设置成1，在处理器将锁释放之前，其他处理器无法占用这个锁。4.5 同步o基本硬件原语 其他一些原子性原语也可实现同步 测试并置位：首先对值进行检测，如果该值通过了检测则执行设置，例如可以定义一个测试0和设置1的操作，其使用方法与原子互换类似。取并增加：返回存储器中的值，并以原子操作的方式使存储器中的值加1，如果用0表示同步变量未被使用，就可以像使用互换一样使用取并增加操作4.5 同步o用一致性实现锁 有了原子操作就可以利用多处理器的一致性机制来实现自旋锁（即处理器通过循环来不停尝试获得锁，直到成功为止）。有两种情况会用到自旋锁，1、程序员要求占用锁的时间很短；2、程序员要求锁在可用时，锁定过程的时延较低。自旋锁的代价是要阻塞处理器并一直循环等待锁被释放。4.5 同步o用一致性实现锁 若不存在Cache一致性问题，可用简单方法在存储器中保存锁变量。处理器可以不停地使用原子操作尝试占用锁，或者说互换，以及检测锁是否可用。要释放锁，处理器只要将0值存储到锁中即可。若多处理器支持Cache一致性，就可以利用一致性协议把锁放入Cache来保证其一致性。4.6 存储器连贯性模型 存储器连贯性是指一个被处理器修改过的值，在何时可以被另一个处理器访问，或者说一个处理器应该以何种次序来查看被别的处理器写过的数据值，才能保证连贯性。由于查看的方式是读操作，所以上述问题变为：在不同处理器对不同单元进行读操作和写操作时，应加上何种属性才能确保连贯性。4.6 存储器连贯性模型o顺序连贯性模型 该模型是存储器连贯性最直接的模型，它要求程序每次执行的结果都是一样的。实现顺序连贯性最简单的方法是让处理器将存储器访问操作的完成时延到由该访问操作引起的所有无效动作完成为止，或采用时延下一个存储器的访问操作直到前一个操作完成。但顺序连贯性模型降低了潜在的性能，尤其是在大量的多处理器中延时更明显。4.6 存储器连贯性模型o程序员视角 虽然顺序简单模型有性能上的不足，但从程序员角度来看，它具有简单性的优点。为了实现起来容易，假设程序是同步的，不使用同步操作对变量的更新进行排序的情况称为数据竞争，因为其运行结果和处理器的相对速度有关。同步程序的另一个名字就是无数据竞争程序。4.6 存储器连贯性模型o非严格连贯性模型 该模型允许读写操作打乱次序完成，但要用同步操作来保证排序原则，使得一个同步程序的表现和处理器使用顺序连贯性模型时的表现一样。通过放宽对读写次序的要求，处理器性能可能获得显著的提升，但描述非严格连贯性模型非常复杂非常复杂，具体可参阅Adve等。4.6 存储器连贯性模型 目前大部分多处理器都支持某种非严格连贯性，这些模型包括从处理器连贯性到宽松的一系列模型。由于同步机制和多处理器特性密切相关，且容易造成错误，因而大部分程序员都使用标准的同步库来构造同步程序，不需要考虑选择非严格连贯性模型就能获得较高的性能。4.7 结论 多处理器和线程级并行在整个计算领域起到了重要作用，以下几种因素加速了这一变化的发生：1、并行处理在某些领域的应用已经得到认可。这些领域最主要的就是科学计算及工程计算，其中某些计算具有天然的并行性。2、关于事务处理和Web服务的服务器应用和多道程序环境的增长很快，这些应用可以获得固有的和易于实行的并行机制。4.7 结论 3、性能经历了20年的快速提升，目前开发指令级并行的利润正在逐步减少，甚至已经能看到这一变化。电源问题、复杂性以及越来越明显的低效问题都迫使设计者考虑它的替代方法，因此开发线程级并行成了未来的选择。4、在过去的50年，时钟频率上的改进来自于晶体管速度的改进，由于技术上的限制和功耗的原因，这种改进正变得越来越困难，因此开发多处理器并行越来越受到关注。4.7 结论 在二十世纪八九十年代，随着指令级并行技术的诞生和发展，能够开发指令级并行是优化编译器软件成功的关键。类似地，线程级并行能否开发成功也依赖于配套软件系统的开发，就像依赖于计算机系统结构的共享一样。在过去的三十年并行软件的发展十分缓慢，所以广泛地开发线程级并行在未来几年仍然要面临很多挑战。