第7章.多指令流多数据流计算机

计算机系统结构教程武汉理工大学武汉理工大学计算机系统结构教程武汉理工大学目录第7章多指令流多数据流计算机7.1MIMD计算机结构模型与访存模型7.2对称多处理机系统7.3大规模并行处理机系统7.4机群系统7.5分布式共享存储系统7.6并行算法的性能评测计算机系统结构教程武汉理工大学第7章多指令流多数据流计算机计算机系统结构教程武汉理工大学7.1MIMD计算机结构模型与访存模型本节首先介绍各类MIMD计算机的结构，然后抽象出具有普遍意义的MIMD计算机体系结构模型，包括MIMD计算机的结构模型和访存模型。并行计算机体系结构一般可分为以下6类：单指令流多数据流（SIMD）计算机；并行向量处理机（PVP）；对称多处理机（SMP）；大规模并行处理机（MPP）；工作站机群（COW）和分布式共享存储系统（DSM）。其中后5种都属于多指令流多数据流（MIMD）计算机。计算机系统结构教程武汉理工大学7.1.1MIMD计算机结构模型5种MIMD并行计算机的结构如图7.1所示。其中，VP是向量处理机，SM是共享存储器，P/C是微处理器和高速缓存，LM是本地存储器，NIC是网络接口电路，MB是存储器总线，DIR是为解决高速缓存一致性问题而设置的高速缓存目录存储器，IOB是I/O总线，LD是本地磁盘，B是存储总线与I/O总线之间的接口。计算机系统结构教程武汉理工大学VPVPVP…交叉开关网络SMSMSM（a）PVPP/CP/CP/C…总线或交叉开关SMSMI/O（b）SMPP/CLMNICMBP/CLMNICMB定制网络（c）MPP…定制网络（d）DSM…P/CLMDIRMBNICP/CLMDIRMBNIC商品网络（以太网、ATM等）（e）COW…P/CMBMBNICLDIOBP/CMBMBNICLDIOB图7.15种MIMD计算机的结构模型计算机系统结构教程武汉理工大学五种MIMD计算和结构特征比较计算机系统结构教程武汉理工大学MIMD计算机体系结构合一的结构模型20世纪90年代以后，上述各种并行计算机的体系结构呈现渐趋一致的趋势。促使体系结构渐趋一致而最终合一的主要因素是：所有体系结构都要求快速的高质量的互连网络；都希望尽量避免或降低延迟；都希望能尽量隐藏通信代价；都必须支持不同的同步形式；等等。根据各种MIMD计算机的体系结构渐趋一致的发展趋势，当代并行计算机的公共结构模型如图7.2所示。计算机系统结构教程武汉理工大学可扩放并行计算机公共结构模型ShellPCMDNICNIC结点N互连网络结点1…ShellPCMNICNIC结点N互连网络结点1…共享磁盘（a）无共享（b）共享磁盘计算机系统结构教程武汉理工大学ShellPC互连网络共享存储器ShellPC共享磁盘（c）共享存储计算机系统结构教程武汉理工大学7.1.2MIMD计算机访存模型1.均匀存储访问模型P1P2…Pn系统互连（总线，交叉开关，多级网络）I/OSM1…SMm处理器共享存储器图7.3UMA多处理机模型计算机系统结构教程武汉理工大学UMA模型的特点①物理存储器（SM1~SMm）被所有处理器均匀共享。所谓均匀共享是指：所有处理器访问任何存储器所需的时间都相同。②每个处理器可带有私有高速缓存。③外围设备以一定的形式被共享。计算机系统结构教程武汉理工大学2.非均匀存储访问模型LM1LM2LMnP1P2Pn互连网络（a）共享本地存储器模型GSMPPPCINGSMGSMGSM群1PPPCINGSMGSMGSM群N全局互连网络（GIN）GSMGSM……（b）层次式机群模型图7.4NUMA多处理机模型计算机系统结构教程武汉理工大学NUMA模型的特点①被共享的存储器在物理上是分布在所有的处理器中，所有的本地存储器（LM1~LMn）的集合组成全局地址空间。②处理器访问存储器所需的时间不相等，访问本地存储器LM或通过群内互连网络（ClusterInterconnectionNetwork，CIN）访问群内共享存储器（ClusterSharedMemory，CSM）费时较少，访问非本地存储器或通过全局互连网络（GlobalInterconnectionNetwork，GIN）访问全局共享存储器（GlobalSharedMemory，GSM）费时较多，即所谓非均匀存储访问。③每个处理器可带有私有高速缓存，外设也可以以某种形式共享。计算机系统结构教程武汉理工大学3.全高速缓存存储访问模型全高速缓存存储访问（Cache-OnlyMemoryAccess，COMA）模型如图7.5所示，它是NUMA模型的一种特例。…互连网络DCPDCPDCP图7.5COMA多处理机模型计算机系统结构教程武汉理工大学COMA模型的特点①各处理器结点中没有存储层次结构，全部高速缓存组成全局地址空间。②利用分布的高速缓存目录D对远程高速缓存进行访问。③COMA中的高速缓存容量一般都大于二级高速缓存容量。④开始使用COMA时，数据可以任意分配到高速缓存C中，在运行过程中，数据将被迁移到使用该数据的处理器结点的高速缓存中。计算机系统结构教程武汉理工大学4.高速缓存一致性非均匀存储访问模型高速缓存一致性非均匀存储访问模型如图7.6所示，它的一个结点实际上是一个SMP机器，通过互连网络把若干个SMP机器连接而成的一个较大规模的多处理机系统。P/CP/CM总线或交叉开关I/ONIC,DIR,RC结点1…P/CP/CM总线或交叉开关I/ONIC,DIR,RC结点N……系统互连网络图7.6CC-NUMA多处理机模型（RC：远程高速缓存）计算机系统结构教程武汉理工大学CC-NUMA模型的特点①绝大多数商用CC-NUMA多处理机系统都使用基于目录的高速缓存一致性协议来维护Cache的一致性。②保留了SMP结构的易于编程的优点，同时也改善了常规SMP结构的可扩放性问题。③CC-NUMA模型实际上是一个分布共享存储（DSM）多处理机系统模型。④CC-NUMA模型最显著的优点是程序员无需明确地在结点上分配数据。计算机系统结构教程武汉理工大学5.非远程存储访问模型在一个分布存储的多处理机系统中，如果所有的存储器都是私有的，仅能由本地处理器访问，就称为非远程存储访问（NO-RemoteMemoryAccess，NORMA）。基于消息传递的NORMA多计算机一般模型如图7.7所示。MPMP…MP消息传递互连网络（网络、环网、超立方、立方环等）PMPM…PMMPMPPMPM图7.7消息传递的NORMA多计算机一般模型计算机系统结构教程武汉理工大学NORMA模型的特点①每个结点都是由处理器（P）、本地存储器（M）和（或）I/O设备组成的自治计算机。多个结点由基于消息传递的互连网络互连。②所有的存储器都是私有的。③绝大多数NORMA都不支持远程存储器的访问。计算机系统结构教程武汉理工大学MIMD计算机的结构模型与访存模型的相互关系MIMD多处理机（单地址空间共享存储器）NORMA（多地址空间非共享存储器）UMA（集中式存储器）PVPSMPNUMA（分布式存储器）COMACC-NUMANCC-NUMACOW（松散耦合）MPP（紧耦合）DSM计算机系统结构教程武汉理工大学7.2对称多处理机系统对称多处理机（SMP）结构在当前的并行服务器中被普遍采用，而且已经越来越多地出现在桌面上。同时，SMP机器也越来越多地作为一个构造模块，用来构造更大规模的系统。计算机系统结构教程武汉理工大学7.2.1对称多处理机的结构图7.9SMP的结构P/CP/C…P/C总线或交叉开关SMSMI/O计算机系统结构教程武汉理工大学1.SMP结构的特点①对称性。系统中任何处理器都可以访问共享存储器的任何存储单元和I/O设备，且具有相同的访存时间。因此，SMP结构也称为均匀存储访问（UMA）结构。②单一物理地址空间。共享存储器的所有存储单元都按单一地址空间编址。③高速缓存一致性。多级高速缓存支持数据局部性，而且用硬件自动实现高速缓存一致性。④低通信延迟。处理器之间的通信采取对共享存储单元使用简单的读/写指令来完成，因此，通信的时间延迟很低。计算机系统结构教程武汉理工大学2.SMP的扩展存储层次结构在SMP机器中，所有的通信和计算都将导致对存储器的读/写，为了提高存储器的性能，需要对SMP机器的存储器扩展为具有层次结构的存储系统。计算机系统结构教程武汉理工大学SMP机器的几种扩展的存储层次结构一级高速缓存（交叉编址）互连网络主存（交叉编址）P1Pn…（a）共享高速缓存结构高速缓存P1Pn…高速缓存内存I/O设备总线（b）基于总线的共享内存结构计算机系统结构教程武汉理工大学高速缓存P1Pn…高速缓存内存内存互连网络（c）舞厅结构高速缓存P1Pn…高速缓存内存内存互连网络（d）分布式内存结构（非SMP结构）计算机系统结构教程武汉理工大学7.2.2高速缓存一致性问题在多处理机中，不仅Cache同共享内存中同一数据拷贝可能不一致，而且由于多个处理机异步地相互独立操作，也使多个Cache中同一份拷贝块可能不一致，这就是多处理机的Cache一致性问题。出现不一致的原因有3个：共享可写的数据、进程迁移和I/O传输。计算机系统结构教程武汉理工大学1.共享可写数据引起的不一致性P1P2XXXP1P2X'XX'P1P2X'XX更新之前写通过写回总线共享存储器高速缓冲存储器处理机XXXX’XX’计算机系统结构教程武汉理工大学2.进程迁移引起的不一致性P1P2XXXP1P2XX'X'P1P2X'XX更新之前写通过写回总线共享存储器高速缓冲存储器处理机XX’XXXX’计算机系统结构教程武汉理工大学3.I/O传输引起的不一致性总线I/O处理机高速缓冲存储器处理机P1P2XX存储器XI/OP1P2XX存储器X'X'（输入）P1P2X'X存储器XX（输出）（写通过）（写回）XXXXXX’计算机系统结构教程武汉理工大学7.2.3侦听高速缓存一致性协议基于总线互连的SMP机器是通过高速共享总线将若干个商用的微处理器（包括高速缓存）与共享存储器连接起来，所有的高速缓存控制器都侦听总线上出现的事务，一旦发现与自己有关的事务，就执行相应的动作来保证高速缓存一致性。在侦听一致性协议的实现中，需要保证实现：①与内存操作有关的所有的必要事务都应出现在总线上。②高速缓存控制器能采取适当的措施（动作）来处理有关的事务。计算机系统结构教程武汉理工大学1.侦听协议的表示侦听协议是用有限状态机表示的分布式算法，它由以下3部分组成：①状态集合。表示高速缓存中块的状态的集合。②状态转换图。状态转换图中的结点表示状态，有向弧表示状态的转换，转换用记号A/B来标记，A表示引发该转换的条件，即处理器的请求或高速缓存控制器侦听到的事务；B表示该转换产生的动作。我们用实线有向弧表示由处理器发起的事务引发的转换，用虚线有向弧表示由总线侦听器发起的事务引发的转换。③动作集合。有限状态机的动作集合是总线、高速缓存和处理器与一致性有关的动作组成的集合。计算机系统结构教程武汉理工大学2.侦听协议的策略（1）写直达策略与写回策略写直达策略和写回策略是用于维护本地高速缓存中的块与相应内存块拷贝一致性的两种策略。写直达（Write-Through）策略规定：当处理器执行写操作时，无论对本地高速缓存是否写命中，都要同时对内存中的相应块进行改写。写回（Write-Back）策略规定：当处理器执行写操作时，若对本地高速缓存写命中，则无需对内存中的相应块进行改写，直至高速缓存的块被替换时，才用该块的内寄去更新内存中的相应块。计算机系统结构教程武汉理工大学（2）写无效策略与写更新策略写无效策略和写更新策略是用于维护本地高速缓存中的块与其他高速缓存中的相应块拷贝一致性的两种策略。写无效（Write-Invalidate）策略规定：当本地高速缓存中的块被改写后，使所有其他高速缓存中与该块内容相同的块拷贝都无效。写更新（Write-Update）策略规定：当本地高速缓存中的块被改写后，通过总线把改写后的块广播到含有该块的所有其他高速缓存来更新相应的块。计算机系统结构教程武