第七章 多处理机n多处理机具有两个以上的处理机，在操作系统控制下，通过共享的主存或输入/输出子系统或高速通信网络进行通信n多任务处理，协同求解，提高速度；n利用冗余，提高可靠性、适应性、可用性n分为：同构型、异构型、分布型 目录n多处理机的概念、问题和硬件结构n紧耦合多处理机多Cache的一致性问题n多处理机的并行和性能n多处理机的操作系统n多处理机的发展多处理机n属于多指令流、多数据流系统n多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序n实现更高一级的作业、任务之间的并行n结构上：要用多个指令部件分别控制，通过机间互联网络实现通信n算法上：不限于向量数组n系统管理上：依靠软件手段解决资源分配和管理，任务分配、处理机调度、进程同步和通讯多处理机与并行处理机的主要差别 方 面并行处理机多处理机结构灵活性针对向量、数组处理而设计的，有专用性，虽然处理单元数多16384个，但设置有限的、固定的机间互连通路实现作业、任务、程序段的并行，适应算法，结构灵活多变，实现复杂的机间互连，避免争用共享的硬件资源程序并行性实现操作级并行，并行性存在指令内部并行性还存在于指令外部，表现于多个任务间的并行并行任务派生通过指令来反映数据间是否并行计算，并由指令直接启动多个处理单元并行工作需要专门的指令或语句指明程序中各程序段的并发关系，并控制并发执行进程同步实现指令内部对数据操作的并行实现指令、任务作业级的并行资源分配和任务调度处理单元数目固定，利用屏蔽手段，改变数目处理机数目不固定，复杂多处理机存在的技术问题 n硬件结构上如何解决处理机、存储器模块及I/O子系统之间的互连n如何最大限度地开发系统的并行性，实现多处理机各级的全面并行；n如何分割任务的大小，任务的粒度大小；n如何协调好处理机中各并行执行的任务和进程间的同步问题；n如何将各个人物分配到一个或多个处理机上，解决好处理机调度、任务调度和资源分配问题，防止死锁；n系统发生故障，系统如何重新组织，正常工作 多处理机的硬件结构 n紧耦合和松耦合 n机间互连形式-性能的重要因素 n存储器的组织 紧耦合多处理机 n是通过共享主存来实现处理机间通讯，通信速率受限于主存的频率。
n减少主存冲突，采用模m多体交叉存取；n是否带专用Cache，有两种n各个处理机为同构型，同一类型、功能相同的多处理机；n处理机之间共享主存储器，通过高速总线或高速开关连接n主存储器有多个独立的存储模块n每个CPU能够访问任意一个存储器模块n通过映象部件MAP把全局逻辑地址变换成局部物理地址n通过互连网络寻找合适的路径，并分解访问存储器的冲突n多个输入输出处理机IOP也连接在互连网络上，I/O设备与CPU共享主存储器n处理机个数不能太多，几个到十几个n紧密偶合方式要求有很高通信频带可以采用如下措施：n采用高速互连网络n增加存储器模块个数，一般n?m，取12倍之间n每个存储器模块再分成多个小模块，并采用流水线方式工作n每个CPU都有自己的局部存储器LMn每个CPU设置一个CacheMAPMMCPU-MM-IOP互连网络紧密耦合多处理机模型CPUMAPCPUMAPCPUMMMMIOPIOPIOPIOPIOPCPUMAPCacheLMCPU-IOP互联网络CPU-MM互联网络MAPMAPCPUMAPCacheLMCPUMAPCacheLMIOPMAPMAPMAPMAP带二维共享存储器和、局部Cache及存储器的多处理机松耦合多处理机 n每一台处理都由容量较大的局部存储器，减少访存冲突，不同处理机间或者通过通道互连实现通信，或者通过消息传送系统（MTS）。
n可看成分布系统；n松耦合非层次型多处理机n层次型总线形式的多处理机LM0IOP0互连网络通过多输入输出输出口连接的多处理机CPU0LM0IOP0CPU0LM0IOP0CPU0LMIOP互连网络通过消息传送系统连接的松散耦合多处理机CPUCAS模块LMIOPCPUCAS模块n-1n处理机之间的连接频带比较低n通过输入输出接口连接,处理机间互为外围设备进行连接n例如，IBM公司的机器，都可以通过通道到通道的连接器CTC把两个不同计算机系统的IOP连接起来n通过并口或串口把多台计算机连接起来n例如，用串行口加一个MODEL拨号上网，也可以直接连接；多台计算机之间的连接需要有多个接口n通过Ethernet网络接口连接多台计算机 速度达10Mb、100Mb、1Gb，Mynet已经达到1.28Gb和2.56Gbn当通信速度要求更高时，可以通过一个通道和仲裁开关CAS（Channel and Arbiter Switch）直接在存储器总线之间建立连接CAS中有一个高速的通信缓冲存储器机间互联形式 n总线形式 n环形互连形式 n交叉开关形式 n多端口存储器形式n蠕虫穿洞寻径网络n开关枢纽结构形式 总线形式 n多个处理机、存储器模块和外围设备通过接口与公用总线相连，采用分时或多路转接技术传送。
n结构简单，成本低，增减模块方便，但对总线的失效敏感nIBM Stretch、UNIVAC Largn提高总线的系统效率：n采用优质高频同轴电缆，用光纤；n采用多总线方式减少冲突概率；总线仲裁算法n静态优先级算法：为每一个连到总线的部件分配一固定的优先级n固定时间片算法：把总线按固定大小时间片，轮流提供给部件使用n适合同步总线，时钟同步n动态优先级算法：让总线上各部件优先级可根据情况按一定规则动态地改变n先来先服务算法：按接受到访问总线请求先后顺序来响应环形互连形式 n总线形成环形互连n令牌（Token）n点点连接，物理参数容易控制n适合于高带宽的光纤；P6P7P5P4P0P1P3P2级间采用环形互连的多处理机交叉开关形式 n包含一组纵横开关阵列n是总线方式的极端n总线数=m+I+n,m：存储器模块数，n：处理机数，I：I/o设备数，一般：M=I+Nn交叉开关阵列复杂n例子：美国C.MMP、S-1 PnPnM1M2MmI/O1I/Oi交叉开关形式多端口存储器形式 n如果每个存储器模块有多各访问端口，且将分布在交叉开关矩阵中的控制、转换和优先级仲裁逻辑分别移到相应存储器模块的接口中I/O1I/O1M1M1M4M3M2P1P2四端口存储器形式的结构UNIVACCRAY_XMP开关枢纽结构形式 n把互连结构的开关设置在各个处理机或其接口内部，组成分布式结构。
n美国加州大学伯克利分校设计的树形多处理机X-TREE 存储器的组织 n并行存储器的构成 n多Cache的一致性问题 并行存储器的构成n有高位交叉和低位交叉 n低位交叉：按物理地址顺序轮流地分布在各个存储模块中n不连续，步距为mn向量、流水或阵列处理机中采用低位交叉n高位交叉：按物理地址顺序从模块0到模块m-1依次连续分布n连续n多处理机中采用高位交叉；(n-1)*mimm0(n-1)*m+1im+1m+11n*m-1(i+1)m-12m-1m-1模块0模块1模块m-1模块内部单元号模块号log2nlog2mm个模块的低位交叉编址n-1i102n-1n+in+1nM*n-1(m-1)n+i(m-1)*n+1(m-1)*n模块0模块1模块m-1模块内部单元号模块号log2nlog2mm个模块的高位交叉编址n本地存储器（HomeMemory）：处理机常用到的存储器模块；M0M1Mm-1Pp-1Pp-1Pp-1处理机存储器互连网络PMIN-本地存储器的概念2紧耦合多处理机多Cache的一致性问题n多Cache的一致性问题的产生n多Cache的一致性问题的解决办法多Cache的一致性问题 n每一个处理机都有自己专用的Cache，但主存中同一个信息块在多个Cache中都有时，会出现信息不一致情况；n写直达法-保证一个；n进程迁移-将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行；n对于进程迁移的Cache不一致性-禁止进程迁移写直达法缓存一致性问题的例子时间共享内存高速缓存C0 C1 C2 C3说明0bb -C0读入块b1bb b -b C1和C3读入块b2bb b -b3 处理器P3修改块b的副本。
现在系统处于不一致状态3b3b b -b3处理器P3执行写直达式因为C0和C1拥有不同的副本，系统处于不一致状态4b3b3 b3-b3共享内存控制器更新C0和C1现在系统处于一致性状态写回法缓存一致性问题的例子时间共享内存高速缓存C0 C1 C2 C3说明0bb -C0读入块b1bb b -b C1和C3读入块b2bb b -b3 处理器P3修改块b的副本现在系统处于不一致状态3Bb0 b1-b3处理器P0和P1各自修改块b的副本4B1b0 b1-b3P1执行写回式到内存5b1？b1 b1?哪个副本的值可以更新到内存和缓存中？多Cache的一致性问题的解决办法n解决进程迁移引起的多Cache不一致性n以硬件为基础实现多Cache的一致性n以软件为基础实现多Cache的一致性多Cache的一致性问题n两类方法：n硬件为基础-监视Cache协议（Snoopy Protocol）写作废法、写更新法n软件为基础-目录表法，全映像目录表法、有限目录表法、链式目录表法n硬件方法-通讯量大，处理机数多时复杂；n软件方法-减少复杂，降低通讯量，性能价格比高，适合于处理机数多实验系统 。