【计算机】计算机体系结构（全书9）
计算机系统结构,第一章 基本概念 第五章 标量处理机 第二章 指令系统 第六章 向量处理机 第三章 存储系统 第九章 多处理机 第四章 输入输出系统,第九章 多处理机,两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。 按照Flynn分类法，多处理机系统属于MIMD计算机。 9.1多处理机结构 9.2多处理机性能模型 9.3多处理机的Cache一致性 9.4多处理机实例,9.1 多处理机结构,9.1.1 两种多处理机结构 根据存储器的组织形式，多处理机系统有2种基本结构，分别是共享存储器多处理机结构和分布式存储器多处理机结构。 共享存储器多处理机的存储器是一个独立的子系统，为所有的处理机共享，任何两台处理机可以通过访问共享的存储器单元实现通信。 分布式存储器多处理机的存储器分布在各处理机中，处理机之间通过点对点的通信实现信息交换。,9.1.2 多处理机系统的特点 多处理机属于多指令流多数据流（MIMD）计算机，下面概括说明多多理机系统的特点： 1.结构灵活性 结构特点：处理单元很多，但只需设置有限和固定的机间互连通路，即可满足一批并行性很高的算法的需要。 2.程序并行性在多处理机中，不限于解决数组向量处理问题，并行性存在于指令外部，即表现在多个任务之间，再加上系统通用性的要求，就是程序并行性的识别难度较大。 3.并行任务派生 一个程序当中存在多个并发的程序段，需要专门的指令来表示它们的并发关系以控制它们的并发执行，以便一个任务开始被执行时就能派生出可与它并行执行的另一些任务。这个过程称为并行任务派生。,4.进程同步多处理机采取特殊的同步措施，才能使并发进程之间保持程序所需要的正确顺序。5.资源分配和进程调度多处理机执行并发任务，需用处理机的数目没有固定要求，各个处理机进入或退出任务的时刻互不相同，所需共享资源的品种、数量又随时变化。于是，就提出了一个资源分配和进程调度问题。,9.2 多处理机性能模型,引起峰值性能下降的原因是： (1) 因处理机间通信而产生的延迟 (2) 一台处理机与其它处理机同步所需的开销 (3) 当没有足够多任务时，一台或多台处理机处于空闲状态 (4) 由于一台或多台处理机执行无用的工作 (5) 系统控制和操作调度所需开销 研究多处理机的目的：提前5年得到速度高10倍的机器。或用1/10的价格获得一台高性能的机器。如果设计得好，在某些适合进行并行处理得应用领域，可以达到：提前10年得到速度高100倍的机器或用1/100的价格获得一台高性能的机器。,并行性在很大程度上依赖于R/C比值， 其中：R代表程序执行时间，C代表通信开销。 通常：R/C比值小，并行性低。 R/C比值大，并行性高。 如果把作业分解成较大的块，就能得到较大的R/C比值，但是所得到的并行性比最大可能的并行性要小得多。 R/C比值是衡量任务粒度(Granularity)大小的尺度在粗粒度（Coarsegrain）并行情况下，R/C比值比较大，通信开销小在细粒度（Finegrain）并行情况下，R/C比值比较小，通信开销大 细粒度并行性需要的处理机多，粗粒度并行性需要的处理机少。 细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务。在极端情况下，一个小任务只完成一个操作。,9.3 多处理机的Cache一致性,9.3.1问题由来 产生Cache一致性问题的原因有以下3个方面： 1.共享可写数据引起不一致 在多处理机中，若多个Cache中有同一个可写数据块，当任何一个处理机对本地Cache中的这个数据块改写后，都会使本地Cache的这个数据块与远程Cache中的同一个数据块不一致。 2.进程迁移引起不一致 一个程序中可能存在多个可并行执行的程序段，当一个程序在一个处理机上运行时，可将派生的并行任务分配到其他处理机上运行，这种进行迁移也会引起不一致。若某进程在处理机Pi上对本地Cache的一个数据块改写后迁移到另一个处理机Pj上，那么，该进程在Pj上访问本地Cache的同一个数据块时，将出现数据块不一致。 3.I/O传输引起不一致I/O传输产生在I/O处理机与共享主存之间，当I/O处理机将一个新的数据块写入主存以更新原来的数据块时，主存中的新数据块与Cache中的原数据块将不一致。,9.3.2 监听协议 1.监听协议概述 当多个处理机和共享存储器采用总线互连时，可以采用总线监听协议解决Cache一致性问题。监听协议通过总线监听机制来监听各处理机对数据块的读/写操作，然后采用有关策略来维护多个Cache以及共享主存的一致性。 监听协议有四种用来保持Cache一致性的方法：写无效（Write-Invalidate）策略和写更新（Write-Update）策略用于维护本地Cache与远程Cache的一致性；写回（Write-back）策略和写通过（Write-Through）策略用于维护本地Cache与共享主存的一致性。2.采用Write-Through策略的Cache 在使用Write-Through策略的Cache中，数据块有两种状态：有效和无效。有效表示该数据块内容正确，无效表示该数据块内容已“过时”或不在Cache。,3.采用Write-Back策略的Cache 在使用Write-Back策略的Cache中，数据块有两种状态：读-写状态和只读状态。只读状态表示整个系统不止一个数据块拷贝是正确的，读-写状态表示数据块至少被修改过一次，存储器中相应数据块还没有被修改，即在整个系统中只有一个数据块拷贝是正确的。4.写一次（Write-once）协议 处理机对本地Cache块第一次写操作时，采用写通过策略，对该块其后的写操作采用写回策略。,9.3.3基于目录的协议1.目录结构及使用 在用互联网互联的多处理机系统中，采用基于目录的协议来维护Cache的一致性。基于目录的协议使用目录表来维护Cache的一致性。根据目录表的结构特点，给予目录的协议有以下3种。2.全映射目录 若多处理机系统有N台处理机，那么，全映射目录协议的目录表的每一个目录项都有N个指针字段。全映射目录协议不具有可扩展性。,3.有限目录 有限目录协议的每一个目录项都有数目固定的若干指针字段，但是，指针字段与处理机并不是一一对应的关系，任何一个指针字段可为任何要求装入该数据块的处理机建立指针，指针通常就是把该数据块装入自己本地Cache的另一个处理机的编号。有限目录协议具有可扩展性。4.链式目录 链式目录协议的每一个目录项只需要一个指针字段，指向装有该数据块的远程Cache中的相应目录项；这个相应目录项的指针字段指向下一个装有该数据块的另一个远程Cache中的相应目录项。链式目录也具有可扩展性。,9.4多处理机实例,多处理机系统主要有四大类： (1) 多向量处理机系统： 如CRAY YMP-90, NEC SX-3和FUJITSU VP-2000 (2) SMP (Symmetry MultiProcessors)对称多处理机; SMP (Shared MemoryMulptiProcessors)共享存储多处理机如SGI ChallengeSun SparcCenter 2000 (3) MPP (massively parallel processing)大规模并行处理机如Intel Paragon, CM-5, Cray T3D (4) Cluster 机群系统（NOW或COM）,9.3.1 大规模并行处理机(MPP),科学计算中的重大课题要求提供3T性能： (1) 1 Teraflops计算能力 (2) 1 Terabyte主存储器 (3) 1 Terabyte/s 输入输出频带宽度目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大。科学计算中的重大课题： 全球气候预报, 基因工程,飞行动力学,海洋环流, 流体动力学, 超导建模, 半导体建模, 量子染色动力学, 视觉采用的关键技术： VLSI, 可扩展技术, 共享虚拟存储技术虚拟共享存储器(Shared Virtual Memory)也称为共享分布存储器(DistributedShared Memory)；物理上分布存储器， 逻辑上共享存储器。,虚拟共享存储器的优点： 编程容易, 系统结构灵活 可扩充性好, 有较好的软件移植性 与消息传递方式相比，程序运行效率高，主要原因： (1) 数据块缓存在本地(内存或Cache中),可以多次使用 (2) 通信时间分散，提高了并行性 (3) 扩大存储空间，减少换页操作 虚拟共享存储器实现途径： (1) 硬件实现, 利用Cache技术。需要增加专用硬件 (2) 操作系统和库实现，通过虚拟存储机制取得共享和一致性。在松耦合的分布存储多处理机上，不需要增加任何硬件 (3) 编译实现，自动将共享访问转换成同步和一致原语。大多数系统采用途径(1)和(2)，或这两种途径结合实现,9.3.2 对称多处理机(SMP) SMP称为共享存储多处理机(SharedMemory mulptiProcessors),也称为对称多处理机(Symmetry MultiProcessors) 有三种模型： (1) UMA多处理机均匀存储器存取模型(Uniform MemoryAccess)存储器被所有处理机均匀共享所有处理机对所有存储单元具有相同的存取时间每台处理机有局部Cache外围设备可以共享,(2) NUMA多处理机 非均匀存储器存取(Nonuniform Memory Access)模型存储器访问时间随存储单元的位置不同而变化。 共享存储器在物理上是分布在所有处理机中的本地存储器。所有局部存储器地址空间的集合就组成了全局地址空间。 处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟。,(3) COMA多处理机 只有Cache的存储器结构(Cache-Only Memory Architecture) 模型；COMA是一种只用Cache的多处理机系统实际上，COMA模型是NUMA模型的一种特例，后者分布存储器换成了Cache在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间远程Cache访问通过分布Cache目录进行共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。,9.3.4 机群系统(Cluster) 1、机群系统的组成 机群系统是利用高速网络将一组高性能工作站或高档PC机连接起来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。 Cluster、NOW、COW 从结构和结点间的通信方式来看，属于分布存储系统。机群系统中的主机和网络可以是同构的，也可以是异构的。 微处理机技术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式正成为当前研究的热点。 (1)微处理器的性能不断提高。 (2)网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解。 (3)并行编程环境的开发使得新编并行程序或改写串行程序更为容易。,2、机群系统的特点(1)系统开发周期短。 (2)用户投资风险小。 (3)系统价格低。 (4)节约系统资源。 UC Berkeley计算机系100多台工作站的使用情况调查表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右。 (5)系统扩展性好。 (6)用户编程方便。,3、机群系统的关键技术(1)高效的通信系统 在用户空间实现通信协议精简通信协议 Active Message通信机制 (2) 并行程序设计环境 PVM(Parallel Virtual Machine)开始于1989年夏天,美国橡树岭国家实验室(ORNL)；是一套并行计算工具软件，支持多用户及多任务运行；支持多种结构的计算机，工作站、并行机以及向量机等；支持C、C+和Fortran语言；自由软件，使用非常广泛；编程模型可以是SPMD或MPMD；具有容错功能，当发现一个结点出故障时，自动将之删除 MPI(Message Passing Interface)在1992年11月至1994年元月产生。能用于大多数并行计算机、计算机机群和异构网络环境，支持C和Fortran两 种语言,编程模型采用SPMD, Express 美国Parasoft公司推出；能在不同的硬件环境上运行；支持C和Fortran两 种程序设计语言。 Linda 美国Yale大学与科学计算协会共同研制；通过函数扩充现并行程序的设计；支持C-Linda、Fortran-Linda等,
