第6章体系结构ppt课件.ppt

第六章 多处理器和线程级并行,6.1 简介6.2 对称式共享存储器系统结构6.3 对称式共享存储器多处理器的性能6.4 分布式共享存储器和基于目录的一致性6.5 同步6.6 存储器连贯性模型6.7 Sun T1多处理器,6.1 简介,单处理器已经运行在纳秒级了，必然要受到光速的限制，随着开发指令级并行空间的减少，未来必定是多处理器唱主角的时代本章主要讨论少量到中等数量的处理器(4-32)组成的多处理器技术MIMD并行系统结构通信和存储器系统结构模型并行处理遇到的挑战,MIMD模型能实现线程级并行，一般多处理器设计都选用这种体系结构MIMD优势：灵活性强，既能适应单用户单一应用，也能适应多任务多道程序环境。能充分利用现有微处理器性价比优势，利用微处理器作为内核，能有效降低设计成本我们常见集群和多核都是基于MIMD模型的。,MIMD并行系统结构,集群是一种流行的MIMD计算机类型，通常使用标准的组件和标准网络技术，这样就可以尽可能地支持多种通用技术集群一般可以分为2种：1 商业集群：依赖于第三方的处理器和互连技术，节点通常是刀片服务器或机架服务器，适用于吞吐量大而几乎没有线程级通信的应用，如Web和一些事务处理等2 客户集群：可以定制节点或互连网络，主要针对并行应用，即单个程序的并行，这种应用有大量的线程级交互，需要单独定制。IBM Blue Gene就是一个客户集群。,20世纪90年代，出现了多核处理器，即片内多处理器或单芯片多处理器，多个内核共享Cache、存储器和I/O总线，多核依靠复制而不是依靠超标量体系结构来提高性能和降低成本。IBM Power 5，Sun T1、Intel Pentium D和Xeon-MP都是基于多核的。对MIMD，进程可以运行在单个处理器之上，也可以运行在多个处理器之上，这时采用的是多线程的执行方式。线程由操作系统调度和管理，可以有不同的粒度大小，线程级并行与指令级并行不同的是，它可以在高层次上被软件系统识别，并且线程由几百至几百万条指令构成。,MIMD机器分为2类：1 集中式共享存储器系统结构到2006年，这种机器处理器个数少于100个，由于处理器数目较少，在使用大容量Cache的情况下，单一存储器的访问还是能够得到及时响应的。这种结构下的每个处理器是对等的，也称为对称多处理器(SMP)系统，这种系统结构称为均匀存储器访问(UMA)。2 分布式存储器系统结构：这种机器每个处理器有单独的存储器，彼此之间通过互连网络连接，这种方式解决了存储器带宽的瓶颈，但处理器间通信变得复杂，处理器数目越多，需要的互连网络带宽也越大。这种机器过去通常在处理器数目很大时使用，但现在这个数目在降低。,通信和存储器系统结构模型,分布式存储器系统有2种不同的系统结构：1 分布式共享存储器(DSM)系统这种体系结构通过共享的地址空间通信，即物理上分开的存储器作为逻辑上共享的地址空间进行寻址，通过引用地址的方式进行访问，2个不同的处理器中相同的物理地址代表存储器的同一位置DSM并没有单一的集中的存储器，与UMA相比，访问时间取决于数据在存储器中的位置，因此也称为非均匀存储器访问NUMADSM的机器，地址空间共享，通过load和store操作隐式地(implicitly)传递数据,2 多个寻址空间的存储器系统这种体系结构由多个私有空间构成，这些私有空间在逻辑上是分散的，不能被远程处理器寻址，2个不同的处理器中相同的物理地址代表2个不同存储器的不同位置。每个处理器-存储器模块本质上是一台独立的计算机，集群就属于这种类型的计算机，由不同的处理节点和专用的互连网络组成。这类机器的数据通信通过显式地(explicitly)在处理器间传递消息完成，因此常被称为消息传递多处理器系统(message-passing multiprocessors),并行处理遇到的挑战,有2个障碍使并行处理的应用遇到了挑战，第一个是程序可获得的并行度是有限的(并行度低)，第二个是通信相对较高的开销(通信时延长)。提高程序的并行度只能通过在软件中采用更好的并行算法实现，而通信的时延则可通过改进体系结构或软件降低。本章主要讨论减少通信时延的技术，如：确保存储器一致性的前提下，如何用Cache减少远程访问频率对潜在的性能瓶颈同步的讨论时延隐藏技术和共享存储器一致性模型,例：假设要用100个处理器获得80倍的加速比，那么原来计算机串行部分最多占多大比例解：并行部分所占比例=0.9975串行部分所占比例=1-0.9975=0.25%这个例题可以看到并行处理器性能对程序并行性有很高的要求,例：假设有一个应用程序在一台32个处理器的多处理器系统上运行，处理器访问一个远程存储器需要200ns。这个应用，除了涉及通信的存储器访问外，所有访问都命中本地存储器系统。执行远程访问会阻塞，处理器时钟频率为2GHz，基本CPI为0.5求：多处理器在没有远程访问时比只有0.2%的指令涉及远程访问快多少？,解：CPI=基本CPI+远程请求率远程请求开销周期数=0.5+0.2%远程请求开销周期数远程请求开销周期数=200ns时钟周期=(200ns1G)(12G)=400个周期CPI=0.5+0.002400=1.3所以要快1.3/0.5=2.6倍在实际应用中，非远程访问也可能在本地存储器中缺失，远程访问时间也不一定为固定值。这个例子告诉我们，远程通信时延影响巨大。,6.2 对称式共享存储器系统结构,对称式共享存储器系统结构发展历程多处理器的Cache一致性实施一致性的基本方案监听协议基本实现技术协议范例对称式共享存储器多处理器和监听协议的局限性实现监听Cache一致性,对称式共享存储器系统结构发展历程,大容量、多层次的Cache能够大量减少单个处理器对存储器带宽的需求，而由于这种需求的减少，多个处理器就能共享一个存储器。20世纪80年代，出现了小规模的多处理器系统，几个微处理器通过总线共享一个物理存储器，大容量Cache减少了对总线带宽的需求，在存储器带宽足够的条件下，性价比极高。设计者们把处理器和Cache放置在一块电路板上，然后再将这块电路板插在总线底板上。到20世纪90年代，每块电路板上放置了2个或4个处理器，并使用了多种总线和交叉存取。,这种体系结构的进一步的发展是多核处理器：2000年，IBM推出了第1个片内多处理器2005年AMD和Intel为服务器推出了双处理器版本2006年Sun公司推出了8处理器的多核的T1目前，高性能的处理器对存储器的需求已经超过了合理的总线能力，最新的设计已经开始使用小规模的交换机和受限的点对点网络。,多处理器的Cache一致性,对称式共享存储器系统中的数据分为私有数据和共享数据，私有数据的使用可以完全在Cache中进行，减少时延和带宽需求，就像单处理器一样共享数据则在多个Cache中形成多副本，虽然减少了时延和带宽需求，但带来Cache的一致性问题一致性定义了存储系统行为的2个不同方面：一致性(coherence)和连贯性(consistency)处理器的连贯性定义的是写入的数值必须什么时候才能被读操作返回，这个问题在6.6节讨论,存储系统具有一致性则要满足下面3个条件：1 处理器P对地址X的写操作后面紧跟P对X的读操作，读写之间没有其它处理器对X写，那么读操作总是返回P写入的数值。2 在其它处理器对X写以后，P读X，之间如果间隔足够且没有其它处理器对X写，读操作返回的是写入的值。3 对同一地址的写操作是串行执行的，任意2个处理器对同一地址的2个写在所有处理器看来有相同的顺序，这一特性称为写串行化。,实施一致性的基本方案,为了维护Cache的一致性，小规模多处理机系统不是通过软件而是通过硬件引入一个协议解决的，这个协议称为Cache一致性协议，主要有2种采用不同技术跟踪共享数据的协议：1 目录式：把物理存储器的共享状态存放在一个地点，称为目录2 监听式：每个含有物理存储器中数据块副本的Cache保留该数据块共享状态的副本，但并不集中保存状态，Cache通过广播媒介(总线或交换机)访问，所有Cache控制器对总线进行监听。目录式比监听式开销略高，但可扩展更多处理器，Sun公司的T1采用这种方式。,监听协议,有2种协议：1 写无效协议：执行写操作时使其它副本无效，其他副本再次使用时会发生缺失。2 写更新或写广播协议：写入数据项时更新该数据项的所有副本，这需要大量带宽。近期所有的多处理器都采用写无效协议,基本实现技术,实现写无效协议的关键是使用广播媒介来完成无效操作，而要实现无效操作，处理器只要取得总线控制权后广播无效数据的地址即可。所有处理器都要不断监听总线来监测地址，如果有无效数据地址，则Cache相应数据要置无效。如果2个处理器同时对一个共享块写的话，则需要通过总线的仲裁实现串行化，取得控制权的处理器会把另一个处理器的副本置无效。Cache缺失时则需要对数据项进行定位，写直达法能使最新值定位比较容易，可以简化Cache一致性的实现。,写回法定位新值比较困难，需要更大的代价，也更复杂，但带宽要求低，多处理器还是更多地使用这个方案。可以利用Cache已有的标志位实现监听过程，数据块的有效位可以使无效操作更简单。对于写操作，需要知道是否有其他副本，如果没有，写回法就不需要发送写操作到总线，节省时间和带宽。因为总线事务必须检查Cache地址的标识，可能干扰处理器对Cache的访问，这时要采取措施减少这种干扰，如备份标识或交2级Cache处理等。,协议范例,监听一致性协议通过每个节点的有限状态控制器来实现，这个控制器对每个来自总线或处理器的请求做出响应，然后改变选定Cache块的状态，并可以使用总线来访问数据或使之无效。逻辑上可以认为控制器和每个块是连在一起的，最简单的协议有3种状态：无效、共享和修改。共享状态是指块是有可能被共享的，修改状态是指块已被更新，代表被独占。这个协议假定是原子操作，是指不会被打断的操作，这种操作一旦开始，就一直运行到结束，非原子操作可能造成死锁。,无效,共享(只读),独占(读写),CPU读命中,CPU读缺失,替换,把读缺失挂在总线上,CPU读命中CPU写命中,CPU写缺失替换,写回Cache块把写缺失挂到总线上,CPU读把读缺失挂到总线上,CPU写把写缺失挂到总线上,CPU读缺失,替换,写回Cache块把读缺失挂到总线上,CPU写,把无效操作挂到总线上,CPU写缺失,替换,把写缺失挂到总线上,基于CPU请求的Cache状态转换,无效,共享(只读),独占(读写),该块写缺失,CPU读缺失,写回Cache块中断存储器访问,基于总线请求的Cache状态转换,写回Cache块中断存储器访问,该块读缺失,该块写缺失,该块无效,对称式共享存储器多处理器和监听协议的局限性,单一总线和单一存储器所能支持的处理器数量是有限的，可以使用互连网络而不是总线构建均匀的存储器访问AMD Opteron使用介于监听协议和目录协议之间的方法，它内部有4个双核处理器，共8个内核，处理器之间使用点对点连接，而处理器内部的连接则不是共享的。,实现监听Cache一致性,实现监听一致性协议的主要复杂性在于任何最新的多处理器中，写缺失或更新缺失都不是原子操作。在大多数基于总线的处理器中，都是通过独占总线，来实现原子操作的。在没有总线的系统中，对所有缺失使用广播或互连网络的一些基本特性，来保证竞争的胜利者只有一个。,6.3 对称式共享存储器多处理器的性能,两种一致性缺失商业负载商业负载的性能测试多道程序和操作系统负载多道程序和操作系统负载的性能,两种一致性缺失,由处理器间通信引起的缺失，称为一致性缺失，是前面讲过的4C中一个，它可以分为2种：1 真共享缺失：直接由处理器间共享数据引起的缺失，例如处理器对共享块的第一次操作引起的缺失，或由于读取其他处理器修改过的数据引起的缺失，这种缺失是无法避免的。2 假共享缺失：由于其他处理器修改数据，引起块失效，这时即使读块中没有修改过的数据也会引起缺失，这是由于使用基于无效的一致性算法引起的。如果Cache块的大小为一个字，那么将没有假共享缺失。,例：假定字X1和X2处于同一块Cache中，这个Cache块在Cache P1和P2种均为共享状态，且P1和P2中已经包含最新的X1和X2。假如发生下表所列的事件序列，请区分发生的缺失是真共享缺失还是假共享缺失,解：1 真共享缺失：因为P2已经读取了X1，需要P2中的X1设置为无效2 假共享缺失：因为X2是由于P1对X1的写而置成无效的，但P2并没有使用X13 假共享缺失：因为数据块是由于P2读X2标记为共享的，但P2并没有读X14 假共享缺失：理由同上5 真共享缺失：因为要读取的值刚被P2写过。,商业负载,本节研究4处理器共享存储器多处理器的存储器系统的行为，测试平台采用AlphaServer 4100。AlphaServer4100使用的处理器是Alpha 21164，每个时钟周期发射4条指令，主频为300MHz。Alpha 21164有3级Cache:一级Cache为1对8k Cache，块32字节，写直达法;二级Cache为96k三路组相联，块32字节，写回法;三级Cache为2M直接映射，块64字节，写回法二、三级及存储器时延为7、21、80个周期，由于其他处理器独占引起的缺失时延为125个周期4100平台主频比目前的处理器低，但在系统结构方面仍具有代表性，只是目前的系统比它有更低缺失率和更高缺失代价。,用于研究的商业负载有3中：1 仿照TPC-B的OLTP负载，使用Oracle 7.3.2作为底层数据库，负载由客户进程和服务器进程集合组成，服务器进程占85%，因其需要进行I/O操作，通常会在25000条指令后发生阻塞。2 基于TPC-D的决策支持系统(DSS)负载，也使用Oracle 7.3.2数据库，该负载使用6条有代表性的读查询，使用并行机制，平均1500000条指令发生一次阻塞。3 基于AltaVista数据库的Web索引查询基准测试程序，将查询映射到存储器，内循环进行了优化，线程间几乎不需要同步。,OLTP的I/O频率高，因而提高了内核时间和空闲时间的比例。DSS的I/O活动要少一些，但空闲时间还有9%AltaVista的查询在内存并进行了优化，因此内核和空闲时间最小，效果最为显著。,商业负载的性能测试,在上节的3个测试程序中，有效CPI各不相同，AltaVista网页搜索的CPI为1.3，DSS负载的平均CPI为1.6，OLTP负载CPI为7.0。从CPI上看，DSS和AltaVista性能尚可，但OLTP性能非常差，这是由于OLTP负载访问存储器最频繁，而存储体系性能不理想，有很多三级Cache缺失，具体数据可见三种测试执行时间的分布图。下面以OLTP为例，讨论影响Cache缺失的因素：三级Cache大小对缺失的影响处理器个数对缺失的影响三级Cache块大小对缺失的影响,三级Cache大小对缺失的影响,前面的图示使用了2路组相联方式的三级Cache，增加的三级Cache大大减少三级缺失，因此执行时间得到改进。令人惊讶的是，几乎所有的执行时间改进都是在容量从1M到2M时发生，继续增加容量不再有效。从存储器访问周期数来看，1M三级Cache存储器访问周期数主要来源于指令和容量/冲突缺失，而三级Cache容量增大会使这些因素不再重要。当容量超过2M时，真共享缺失成为主要部分，而三级Cache容量增加不会减少真共享缺失，本质是，增大三级Cache容量消除了绝大多数的单处理器缺失，但并未对多处理器缺失产生影响。,处理器个数对缺失的影响,处理器数目的增加，将导致真共享缺失的增加因每个处理器要处理的更多的强制缺失，强制缺失也稍有增加,三级Cache块大小对缺失的影响,把三级Cache块大小从32字节增加到256字节产生了以下影响：1 真共享缺失率降至不到原来的1/2，这说明真共享的局部性。2 强制缺失率显著降低3 冲突/容量缺失有一定减少，说明空间局部性在单处理器缺失中并不显著4 假共享缺失绝对值并不大，但几乎增加了一倍5 指令缺失没有受到显著影响结论：把块大小增加到128或256字节是合适的,多道程序和操作系统负载,本节研究由用户活动和操作系统活动构成的多道程序负载，负载由Andrew基准测试程序提供。负载在8处理器上运行5.24秒，产生203个进程，对3个不同文件系统进行了787次磁盘请求，负载使用128M存储器，且无页面调度活动发生。负载分为3个阶段：编译基准测试程序；在库里建立对象文件；移除对象文件。最后阶段完全由I/O控制，中间阶段也主要依靠I/O，处理器大都空闲，负载的I/O和操作系统活动比商业负载密集。,为测量负载，对存储器和I/O系统做如下设置：一级指令Cache：32k，2路组相联，块64字节，命中时间1个周期一级数据Cache：32k，2路组相联，块32字节，命中时间1个周期二级Cache：1M，指令数据共用，2路组相联，块128字节，命中时间10个周期存储器：挂在总线上，访问时间100个周期磁盘系统：时延为3ms,在多道程序中并行构造负载中执行程序的分配情况如下：,多道程序负载对操作系统活动有更多指令Cache性能损失。在操作系统中，64字节块、2路组相联指令Cache 32k时缺失率为1.7%，256k为0.2%，而对用户指令来说，仅为操作系统指令的1/6。这使得用户指令数为操作系统指令数的9倍，但执行时间仅为其4倍。,多道程序和操作系统负载的性能,这一节主要研究影响多道程序和操作系统工作负载的Cache性能的因素操作系统比用户进程有更高的缺失率，其原因除了操作系统的代码量更大和空间局部性差以外，还有2个原因一个是内核分配并初始化页，强制缺失率高，一个是共享数据引起的一致缺失率(用户程序只有调度到另一个处理器才有一致缺失)Cache容量的影响块大小的影响结论,Cache容量的影响,数据Cache的大小对用户缺失率的影响比内核缺失率的影响要大。,对内核来说，增大Cache容量只能减少单处理器的容量/冲突缺失,块大小的影响,增加数据块的大小对缺失率有好的效果，因为大部分强制缺失和容量缺失，都能随着数据块的增大而减少。一致缺失比例较小，所以块大小的负面影响是有限的，这说明假共享缺失是无关紧要的。内核调用具有较高的通信量，且随着块大小的增加而快速增长，当块从16字节增加到128字节时，缺失率降低了3.7倍，但每个缺失传输的字节数量提高了8倍，缺失通信量大约增加了2倍。用户通信与内核类似，但通信量很小,结论,对于多道程序工作负载，操作系统对于存储器系统的要求是苛刻的。如果负载中的操作系统活动过多，要构造能力足够的存储系统是非常困难的。要改善性能，操作系统应更加关注Cache的活动。,6.4 分布式共享存储器和基于目录的一致性,2006年，性能最高的集中式共享存储器16路多处理器的存储器带宽为每个处理器2.4GB/s，而使用分布式存储器模型的多处理器最大可用带宽为每个处理器为12GB/s。监听一致性协议对每个Cache缺失都要广播，带来过多的带宽需求，为解决这个问题，经常使用基于目录的一致性协议。带目录的分布式存储器多处理器系统基于目录的Cache一致性协议目录协议范例,带目录的分布式存储器多处理器系统,目录协议并不是分布式存储器系统专有，集中式存储器系统也可以使用，如Sun T1。目录协议保存每个Cache块的状态，目录中的信息包括哪个Cache拥有副本，是否脏块等。最简单的目录协议在目录中为每个块分配一个条目，信息个数等于存储器块数与处理器个数的乘积，存储开销适用于200个处理器以下的系统。如果处理器数目更多，就要进行改进，或减少目录条目数，或减少单个目录条目信息量。为防止目录成为通信瓶颈，目录要分布存放。,基于目录的Cache一致性协议,目录协议必须要实现2个基本操作：处理读缺失和共享未修改Cache块的写操作，写缺失则可由这2操作组合完成。协议中可能出现的状态包括：共享：一个或多个处理器拥有Cache块，并且存储器中的块与这些Cache块一样，都是最新的。未缓存：没有任何处理器包含该块的副本。修改：只有一个处理器拥有Cache块副本并进行过写操作，此时存储器中的块无效。块处于共享状态时，可以用向量表示其共享情况，向量的每一位对应一个处理器。目录协议和监听协议最大的不同在于后者是广播方式而前者不是。,目录协议范例,目录协议中的Cache块基本状态与监听协议一样，目录状态也与前面列出的类似，但它的实现不是通过广播完成的。单个Cache的状态转换是由读缺失、写缺失、无效和取数据引发的。单个Cache还会向主目录发送它所生成的读缺失消息、写缺失消息和无效消息。读和写缺失要求有数据值应答，而且这些事件的状态会等到接收到应答后才发生改变，确认无效操作何时完成是一个独立的问题，需单独处理。,无效,共享(只读),独占(读写),CPU读命中,CPU读缺失,读缺失,CPU读命中CPU写命中,CPU写缺失数据写回写缺失,CPU读发送读缺失消息,数据写回发送写缺失消息,CPU读缺失数据写回，读缺失取 数据写回,CPU写命中，发送无效消息,CPU写缺失，发送写缺失消息,基于目录的系统中单个Cache状态转换图,取无效,无效,CPU写,外节点请求 外节点动作 本地CPU请求 本地CPU动作,目录协议中，目录实现一致性协议的另一半工作发送到目录的消息引发2种不同操作：一种是更新目录状态，一种是发送其他消息来响应请求。目录状态代表了数据块的3个标准状态，但与监听方案不同，针对的是被缓存的存储器块。存储器块可以不被任何节点缓存，也可被一个节点独占，还可被多个节点共享(可通过向量表示)目录接收3种不同的请求：读缺失、写缺失和数据写回，所有的消息都来自外部。协议必须考虑原子性问题，实际使用时也需要优化。,不缓存,共享(只读),独占(读写),读缺失,数据值应答共享者=共享者+P,写缺失取/无效数据值应答共享者=P,数据值应答共享者=P读缺失,共享者=数据值应答,共享者=P,读缺失取；数据值应答；共享者=共享者+P写缺失,无效；共享者=P；数据值应答,与单个Cache状态转换图具有相同状态和结构的目录状态转换图,数据写回,写缺失,6.5 同步,一般来说，同步机制是通过用户层的软件构造的，但这些软件要使用硬件提供的同步指令。在小规模处理器系统或竞争较少的环境中，其关键是硬件上要支持一条不可中断的指令或指令序列，能以原子操作方式取回数据并修改其值。大规模处理器或竞争较多的环境，会造成额外的时延，使同步成为性能瓶颈。本节讨论基本的同步机制，关注锁和解锁同步操作的实现以及利用其实现互斥和更复杂的同步。基本硬件原语用一致性实现锁,基本硬件原语,在处理器中实现同步的关键，在于要有一个能以原子方式对存储器进行读写的硬件原语集合。原子互换是一个典型的构造同步原语的操作，它将一个寄存器中的值和一个存储器中的值互换。利用原子互换可构造一个简单的锁，该锁用0表示未被占用，用1表示已被占用，处理器使用时，用寄存器的值和该锁在存储器中的值互换，寄存器值为1表示锁已被占用，为0表示成功占用该锁。除了原子互换，还有测试并置位、取并增加操作也可以完成类似的功能。,实现存储器的原子操作很困难，因为它要求对存储器的读写在一个独立不可中断的指令中完成。另一种方法，是使用2条指令，其中第2条指令的反馈可以得知这对指令是否以原子方式执行。这对指令使用一个特殊的加载(称为链接加载)和一个特殊的存储(称为条件存储)。2条指令顺序执行，若链接加载所指地址的值在条件存储前改变了，或2条指令间有上下文切换，则条件存储失败。条件存储成功，则返回1，否则返回0。,try:MOV R3,R4;移动需要互换的值 LL R2,0(R1);链接加载 SC R3,0(R1);条件存储 BEQZ R3,try;存储转移失败 MOV R4,R2;把加载值放入R4上面这个程序完成了R4和R1指定地址中的值的原子交换，其中若LL和SC之间修改了存储器的值，SC会在R3中返回0。然后继续执行try。下面是取并增加原子操作的实现：try:LL R2,0(R1);链接加载 DADDUI R3,R2,#1;增加 SC R3,0(R1);条件存储 BEQZ R3,try;存储转移失败,用一致性实现锁,有了原子操作，就可以用多处理器的一致性机制实现自旋锁(通过循环不停尝试直到成功获得锁)程序员有2种情况会用到自旋锁：一是占用锁的时间很短，二是锁可用时锁定过程时延较低。这是因为自旋锁会阻塞处理器，很多情况并不适用不考虑Cache一致性问题，下面的代码使用原子互换来锁定R1指定的自旋锁：DADDUIR2,R0,#1lockit:EXCHR2,0(R1);原子锁定BNEZR2,lockbit;已经锁定,如果多处理器支持Cache一致性，就可以利用一致性协议把锁放入Cache来保证一致性，这样能使锁的自旋在本地Cache进行，而锁的访问具有局部性，同一处理器能减少获得锁需要的时间。lockit:LDR2,0(R1);锁的加载BNEZR2,lockbit;已经锁定DADDUIR2,R0,#1;不能获取EXCHR2,0(R1);原子锁定BNEZR2,lockbit;已经锁定上面程序前2条语句保证了在本地Cache中获得锁，然后多处理再试图占有锁，每个处理器都执行写操作，但大多写缺失，只有一个会独占它。,前面的代码也可以用链接加载/条件存储原语实现，这时写和读是显式分离的。lockit:LLR2,0(R1);锁的加载BNEZR2,lockbit;已经锁定DADDUIR2,R0,#1;不能获取SCR2,0(R1);原子锁定BNEZR2,lockbit;已经锁定虽然自旋锁方案简单且具有吸引力，但由于释放锁产生的通信量问题，还是难以扩展到多个处理器的情况。,6.6 存储器连贯性模型,存储器连贯性带来的问题程序员的视角非严格连贯性模型编译器优化和连贯性模型在严格连贯性模型中用推测来实现时延隐藏,存储器连贯性带来的问题,处理器之间是通过共享变量来进行通信的，所以要通过对共享变量的读和写操作来确保连贯性下面是进程P1和P2的两段代码：P1:A=0;P2:B=0;A=1;B=1;L1:if(B=0);L2:if(A=0);假设P1和P2在2个处理器上开始运行，同时执行到L1和L2处，如果写能立即生效，2个if语句都不被执行，但如果写无效被延迟或其中一个被延迟呢？该如何处理这种情况？,存储连贯性最直接的模型是顺序连贯性模型，它要求程序每次执行的结果是一样的，实现它最简单的方法是将存储器访问延迟到它引起的所有无效操作完成为止。这明显地降低了性能。在顺序模型下，前面的读操作A=0和B=0必须等到B=1和A=1完成之后进行。例：假设一个处理器的写缺失需要50个周期建立该缺失的拥有权，完成后每个无效信号的发送需要10个周期，从无效到收到应答还需要80个周期假设4个处理器共享一个Cache块，在顺序连贯性模型中，一个写缺失要对执行写操作的处理器造成的延迟=50+40+80=170个周期，这是相当大的性能损失。,程序员的视角,如果一个程序是同步的，意味着对共享变量的访问由同步操作来排序，与同步操作相对的情况称为数据竞争，其结果是无法预知的，而同步程序是无数据竞争程序。解锁和加锁就是一对同步操作，它可以隔离2个操作，比如2个写操作，让它们串行执行。大多数程序是同步的，如果不同步，程序的行为就难以确定，进而影响程序的结果。程序员可以自己编程完成同步机制，但一般情况下，他们会选择使用能保证正确性的同步库来实现同步。,非严格连贯性模型,非严格连贯性模型的关键在于允许读写操作打乱次序完成，但要用同步操作保证排序原则，使一个同步程序的表现和顺序连贯模型一样。顺序连贯性模型要求支持所有可能排序：RW，RR，WR，WW。非严格连贯性模型可以做一些放宽：1 放宽WR排序，称为完全存储排序模型(或处理器连贯性模型，)，这种排序维持了写顺序。2 放宽WW排序，称为部分存储排序的模型。3 放宽RW和WR排序，由此根据排序约束的细节和同步操作保证次序产生了多种模型。,放宽对次序的要求，处理器的性能可以得到显著提升，但相对来说也会变得非常复杂。目前大多数处理器都支持某种非严格连贯性，这些模型通常提供了相应的同步库，程序员通常使用库构造同步程序，而不需要考虑模型细节。,编译器优化和连贯性模型,为存储器连贯性定义模型的另一个原因，是要对编译器优化共享数据指定一个范围。在显式的并行程序中，除了同步点被清楚地定义出来且程序是同步的以外，编译器不能交换对2个不同共享数据项读操作和写操作顺序，因为这种操作可能改变程序的语义。不能交换读操作和写操作会限制一些优化技术的使用，如共享数据的寄存器分配技术。在隐式的并行程序中，程序必须是同步的，而且同步点已知，故不存在这些编译优化的问题。,在严格连贯性模型中用推测来实现时延隐藏,预测可以用来隐藏严格的连贯性模型引起的时延，使其具有非严格连贯性的优点。问题的关键在于处理器用动态调度来对存储器访问进行重排序，使其可乱序执行。借助推测处理器的时延提交特性，可以避免存储器乱序访问违反顺序连贯性而影响程序运行。假设一个连贯性协议建立在发送无效信号的基础上，如果在存储器访问被提交前收到无效信号，那么处理器会采用推测恢复来取消计算并从无效的地址重新开始。,如果重排存储器请求顺序会导致和顺序连贯不同的结果，处理器将会重新执行，如果推测正确，就不需要重新执行，实际上重新执行很少发生。Hill1998建议把顺序连贯性或处理器连贯性和推测执行结合起来，作为连贯性模型的一种选择。MIPS R1000在1990年就考虑了这一点，并利用R1000的乱序执行能力来支持顺序连贯性的实现。,6.7 Sun T1多处理器,T1是Sun公司2005年为服务器市场推出的多核处理器，是专为线程级并行开发的。T1处理器的结构T1的基本特征T1的性能运行SPEC基准测试程序的多核处理器的性能,T1的性能,1个线程和4个线程时缺失率及缺失延迟变化二级Cache容量和块大小对缺失率的影响二级Cache容量和块大小对缺失延迟的影响整体性能平均的线程状态分析线程未准备好的原因分析,1个线程和4个线程时缺失率及缺失延迟变化,二级Cache容量和块大小对缺失率的影响,二级Cache容量和块大小对缺失延迟的影响,整体性能,T1的有效吞吐量只有理想状况的56%-71%对于4.4-5.7的有效IPC，即使有更多晶体管、更高的电源功率和更大硅面积的Itanium 2也是无法比拟的。,平均的线程状态分析,线程未准备好的原因分析,运行SPEC基准测试程序的多核处理器的性能,T1与Power 5、Opteron和Pentium D相比：T1是以线程级并行为主，其他处理器则主要使用多发射和多核技术开发指令级并行。T1的浮点运算部件只有一个，浮点支持上要弱。可扩展性上，Power 5最好，Opteron和Pentium D提供了受限制的多处理器支持，T1则完全不适合扩展到大系统。实现技术迥异，晶片大小和电源功率很难比较。对存储系统及可用存储器带宽的假设也明显不同。,