计算机体系结构chapter07new

计算机体系结构周学海[e-mail]0551-63601556,63492271中国科学技术大学2019/12/16中国科学技术大学第7章多处理器及线程级并行7.1引言7.2集中式共享存储器体系结构7.3分布式共享存储器体系结构7.4存储同一性7.5同步与通信2019/12/16计算机体系结构27.1、引言单处理机的发展正在走向尽头？并行计算机在未来将会发挥更大的作用。1.获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起；2.自1985年以来，体系结构的改进使性能迅速提高，这种改进的速度能否持续下去还不清楚，但通过复杂度和硅技术的提高而得到的性能的提高正在减小；3.并行计算机应用软件已有缓慢但稳定的发展。2019/12/16计算机体系结构3并行计算机体系结构的分类1、按照Flynn分类法，可把计算机分成单指令流单数据流（SISD）单指令流多数据流（SIMD）多指令流单数据流（MISD）多指令流多数据流（MIMD）2019/12/16计算机体系结构42、MIMD已成为通用多处理机体系结构的选择，原因：(1)MIMD(2)MIMD可以充分利用商品化微处理器在性能价格3、根据多处理机系统中处理器个数的多少，可把现有的MIMD机器分为两类（每一类代表了一种存储器的结构和互连策略）(1)集中式共享存储器结构这类机器有时被称为UMA(uniformmemoryaccess)机2019/12/16计算机体系结构52019/12/16计算机体系结构6(2)分布式存储器结构每个结点包含：•处理器•存储器•I/O在许多情况下，分布式存储器结构优于采用集中式共享存储器结构。分布式存储器结构需要高带宽的互连。2019/12/16计算机体系结构72019/12/16计算机体系结构8分布式存储器结构的优点如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；对局部存储器的访问延迟低。主要缺点处理器之间的通信较为复杂，且各处理器之间访问延迟较大。簇：超结点2019/12/16计算机体系结构9通信模型和存储器的结构模型1.两种地址空间的组织方案(1)物理上分离的多个存储器可作为一个逻辑上共享的存储空间进行编址。这类机器的结构被称为分布式共享存储器(DSM)或可缩放共享存储器体系结构。DSM机器被称为NUMA(non-uniformmemoryaccess)机器。(2)整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。2019/12/16计算机体系结构10两种通信模型每一个处理器-存储器模块实际上是一个单独的计算机，这种机器也称为多计算机。2.两种通信模型(1)共享地址空间的机器利用Load和Store指令中的地址隐含地进行数据通讯。(2)多个地址空间的机器通过处理器间显式地传递消息完成这种2019/12/16计算机体系结构11通信模式消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。例如:一个处理器要对远程存储器上的数据进行访问或操作①发送消息，请求传递数据或对数据进行操作.远程进程调用(RPC,remoteprocesscall)②目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。2019/12/16计算机体系结构12通信模式同步消息传递请求处理器发送一个请求后一直要等到应答结果才继续运行。异步消息传递发送方发出消息后，立即继续执行原来的程序。发送方不先经请求就直接把数据送往数据接受方。2019/12/16计算机体系结构13通信机制的性能三①通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。②通信延迟理想状态下通信延迟应尽可能地小。通信延迟＝发送开销＋跨越时间＋传输延迟＋接收开销③通讯延迟的隐藏如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通讯延迟的隐藏。通常的原则是：只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。2019/12/16计算机体系结构14不同通信机制的优点1、共享存储器通信的主要优点①与常用的集中式多处理机使用的通信机制兼容②当处理器通信方式复杂或程序执行动态变化时易于编程，同时在简化编译器设计方面也占有优势。③当通信数据较小时，通信开销较低，带宽利用较好。④通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。2019/12/16计算机体系结构152.消息传递通信机制的主要优点①硬件较简单。②通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。在共享存储器上支持消息传递相对简单，但在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息2019/12/16计算机体系结构16并行处理面临的挑战并行处理面临着两个重要的挑战：程序中有限的并行性相对较高的通信开销1、有限的并行性使机器要达到好的加速比十分困难例7.1如果想用100个处理器达到80的加速比，求原计算程序中串行部分所占比例。2019/12/16计算机体系结构17例7.12019/12/16计算机体系结构1880＝1并行比例100＋（1－并行比例）1可加速部分比例理论加速比＋（1－可加速部分比例）解根据Amdahl定律加速比为：•得出：并行比例＝0.9975•可以看出要用100个处理器达到80的加速比，串行计算的部分只能占0.25%。2.面临的第二个挑战主要是指多处理机中远程访问的较大延迟。在现有的机器中，处理器之间的数据通信大约需要35～500个时钟周期。同一芯片中core之间的延迟35~50cycles不同芯片间core之间的延迟100~500cycles2019/12/16计算机体系结构19远程访问一个字的延迟时间2019/12/16计算机体系结构20机器通信机制互连网络处理机数量典型远程存储器访问时间SPARCCenter共享存储器总线≤201μsSGIChallenge共享存储器总线≤361μsCrayT3D共享存储器3维环网32－20481μsConvexExemplar共享存储器交叉开关＋环8－642μsKSR-1共享存储器多层次环32－2562-6μsCM-5消息传递胖树32－102410μsIntelParagon消息传递2维网格32－204810-30μsIBMSP-2消息传递多级开关2－51230-100μs例7.2一台32个处理器的计算机，对远程存储器访问时间为2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为10ns，如果指令基本的CPI为1.0(设所有访存均命中Cache)，求在没有远程访问的状态下与有0.5%的指令需要远程访问的状态下，前者比后者快多少?2019/12/16计算机体系结构21解有0.5%远程访问的机器的实际CPICPI＝基本CPI＋远程访问率×远程访问开销＝1.0＋0.5%×远程访问开销远程访问开销＝远程访问时间/时钟时间＝2000ns/10ns＝200∴CPI＝1.0＋0.5%×200＝2.0它为只有局部访问的机器的2.0／1.0＝2倍，因此在没有远程访问的状态下的机器速度是有0.5%远程访问的机器速度的2倍。2019/12/16计算机体系结构22问题的解决并行性不足：通过采用并行性更好的算法来解决远程访问延迟的降低：靠体系结构支持和编程技术2019/12/16计算机体系结构23并行程序的计算／通信比率反映并行程序性能的一个重要的度量计算与通信的比率计算/通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。2019/12/16计算机体系结构247.2集中式共享存储器体系结构多个处理器共享一个存储器。当处理器规模较小时，这种机器十分经济。支持对共享数据和私有数据的Cache缓存。私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。共享数据进入Cache产生了一个新的问题Cache的一致性问题2019/12/16计算机体系结构25多处理机的一致性(1)不一致产生的原因（Cache一致性问题）I／O操作Cache中的内容可能与由I／O子系统输入输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。2019/12/16计算机体系结构26例两个处理器Cache对应同一存储器单元产生出不同的值假设：初始条件下各个Cache无X值，X单元值为1；写直达方式的Cache2019/12/16计算机体系结构27时间事件CPUACache内容CPUBCache内容X单元存储器内容011CPUA读X112CPUB读X113CPUA将0存入X010（2）存储器是一致的（非正式地定义）如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面返回给读操作的是什么值(coherence)什么时候才能将已写入的值返回给读操作(consistency)如果存储系统行为满足条件①处理器P对X进行一次写之后又对X进行读，读和写之间没有其它处理器对X进行写，则2019/12/16计算机体系结构28②一个处理器对X进行写之后，另一处理器对X进行读，读和写之间无其它写，则读X的返回值应为写进的值。③对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。2点假设（1）直到所有的处理器均看到了写的结果，一次写操作才算完成；（2）允许处理器无序读，但必须以程序规定的顺2019/12/16计算机体系结构29实现一致性的基本方案在一致的多处理机中，Cache提供两种功能。共享数据的迁移降低了对远程共享数据的访问延迟。共享数据的复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。2019/12/16计算机体系结构30(1)Cache一致性协议:对多个处理器维护一致性的协议(2)关键：跟踪共享数据块的状态(3)共享数据状态跟踪技术目录物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。监听每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。2019/12/16计算机体系结构31Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。2019/12/16计算机体系结构323.(1)写作废协议在一个处理器写某个数据项之前保证它对该数据项有例在写回Cache的条件下，监听总线中写作废协议的实现。2019/12/16计算机体系结构33处理器行为总线行为CPUACache内容CPUBCache内容主存X单元内容0CPUA读XCache失效00CPUB读XCache失效000CPUA将X单元写1作废X单元10CPUB读XCache失效111(2)写更新协议当一个处理器写某数据项时，通过广播使其它Cache例在写回Cache的条件下，监听总线中写更新协议的实现。2019/12/16计算机体系结构34处理器行为总线行为CPUACache内容CPUBCache内容主存X单元内容0CPUA读XCach失效00CPUB读XCach失效000CPUA将X单元写1广播写X单元111CPUB读X111(3)写更新和写作废协议性能上的差别对同一数据的多个写而中间无读操作的情况,写更新协议需进行多次写广播操作，而在写作废协对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝