计算机体系结构chapter7-1

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 多,处理机,多处理机具有两个以上的处理机，在操作系统控制下，通过共享的主存或输入,/,输出子系统或高速通信网络进行通信。,多任务处理，协同求解，提高速度；,利用冗余，提高可靠性、适应性、可用性。,分为：同构型、异构型、分布型,目录,多处理机的概念、问题和硬件结构,紧耦合多处理机多,Cache,的一致性问题,多处理机的并行和性能,多处理机的操作系统,多处理机的发展,多处理机,属于多指令流、多数据流系统,多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。,实现更高一级的作业、任务之间的并行,结构上：要用多个指令部件分别控制，通过机间互联网络实现通信,算法上：不限于向量数组,系统管理上：依靠软件手段解决资源分配和管理，任务分配、处理机调度、进程同步和通讯,多处理机与并行处理机的主要差别,方,面,并行处理机,多处理机,结构灵活性,针对向量、数组处理而设计的，有专用性，虽然处理单元数多,16384,个，但设置有限的、固定的机间互连通路,实现作业、任务、程序段的并行，适应算法，结构灵活多变，实现复杂的机间互连，避免争用共享的硬件资源,程序并行性,实现操作级并行，并行性存在指令内部,并行性还存在于指令外部，表现于多个任务间的并行,并行任务派生,通过指令来反映数据间是否并行计算，并由指令直接启动多个处理单元并行工作,需要专门的指令或语句指明程序中各程序段的并发关系，并控制并发执行,进程同步,实现指令内部对数据操作的并行,实现指令、任务作业级的并行,资源分配和任务调度,处理单元数目固定，利用屏蔽手段，改变数目,处理机数目不固定，复杂,多处理机存在的技术问题,硬件结构上如何解决处理机、存储器模块及,I/O,子系统之间的互连,如何最大限度地开发系统的并行性，实现多处理机各级的全面并行；,如何分割任务的大小，任务的粒度大小；,如何协调好处理机中各并行执行的任务和进程间的同步问题；,如何将各个人物分配到一个或多个处理机上，解决好处理机调度、任务调度和资源分配问题，防止死锁；,系统发生故障，系统如何重新组织，正常工作,多处理机的硬件结构,紧耦合和松耦合,机间互连形式,-,性能的重要因素,存储器的组织,紧耦合多处理机,是通过共享主存来实现处理机间通讯，通信速率受限于主存的频率。,减少主存冲突，采用模,m,多体交叉存取；,是否带专用,Cache,，,有两种,各个处理机为同构型，同一类型、功能相同的多处理机；,处理机之间共享主存储器，通过高速总线或高速开关连接。,主存储器有多个独立的存储模块,每个,CPU,能够访问任意一个存储器模块,通过映象部件,MAP,把全局逻辑地址变换成局部物理地址,通过互连网络寻找合适的路径，并分解访问存储器的冲突,多个输入输出处理机,IOP,也连接在互连网络上，,I/O,设备与,CPU,共享主存储器。,处理机个数不能太多，几个到十几个,紧密偶合方式要求有很高通信频带。可以采用如下措施：,采用高速互连网络,增加存储器模块个数，一般,n?m,，,取,1,2,倍之间。,每个存储器模块再分成多个小模块，并采用流水线方式工作。,每个,CPU,都有自己的局部存储器,LM,。,每个,CPU,设置一个,Cache,。,MAP,MM,CPU-MM-IOP,互连网络,紧密耦合多处理机模型,CPU,MAP,CPU,MAP,CPU,MM,MM,IOP,IOP,IOP,IOP,IOP,CPU,MAP,Cache,LM,CPU-IOP,互联网络,CPU-MM,互联网络,MAP,MAP,CPU,MAP,Cache,LM,CPU,MAP,Cache,LM,IOP,MAP,MAP,MAP,MAP,带二维共享存储器和、局部,Cache,及存储器的多处理机,松耦合多处理机,每一台处理都由容量较大的局部存储器，减少访存冲突，不同处理机间或者通过通道互连实现通信，或者通过消息传送系统（,MTS,）。,可看成分布系统；,松耦合非层次型多处理机,层次型总线形式的多处理机,LM,0,IOP,0,互连网络,通过多输入输出输出口连接的多处理机,CPU,0,LM,0,IOP,0,CPU,0,LM,0,IOP,0,CPU,0,LM,IOP,互连网络,通过消息传送系统连接的松散耦合多处理机,CPU,CAS,模块,LM,IOP,CPU,CAS,模块,n-1,处理机之间的连接频带比较低,通过输入输出接口连接,处理机间互为外围设备进行连接,例如，,IBM,公司的机器，都可以通过通道到通道的连接器,CTC,把两个不同计算机系统的,IOP,连接起来。,通过并口或串口把多台计算机连接起来,例如，用串行口加一个,MODEL,拨号上网，也可以直接连接；多台计算机之间的连接需要有多个接口。,通过,Ethernet,网络接口连接多台计算机,速度达,10Mb,、,100Mb,、,1Gb,，,Mynet,已经达到,1.28Gb,和,2.56Gb,。,当通信速度要求更高时，可以通过一个通道和仲裁开关,CAS,（,Channel and Arbiter Switch,）,直接在存储器总线之间建立连接。,CAS,中有一个高速的通信缓冲存储器。,机间互联形式,总线形式,环形互连形式,交叉开关形式,多端口存储器形式,蠕虫穿洞寻径网络,开关枢纽结构形式,总线形式,多个处理机、存储器模块和外围设备通过接口与公用总线相连，采用分时或多路转接技术传送。,结构简单，成本低，增减模块方便，但对总线的失效敏感。,IBM Stretch,、,UNIVAC,Larg,提高总线的系统效率：,采用优质高频同轴电缆，用光纤；,采用多总线方式减少冲突概率；,总线仲裁算法,静态优先级算法,：为每一个连到总线的部件分配一固定的优先级,固定时间片算法,：把总线按固定大小时间片，轮流提供给部件使用,适合同步总线，时钟同步,动态优先级算法,：让总线上各部件优先级可根据情况按一定规则动态地改变,先来先服务算法,：按接受到访问总线请求先后顺序来响应,环形互连形式,总线形成环形互连。,令牌（,Token,）,点点连接，物理参数容易控制,适合于高带宽的光纤；,P6,P7,P5,P4,P0,P1,P3,P2,级间采用环形互连的多处理机,交叉开关形式,包含一组纵横开关阵列。,是总线方式的极端。,总线数,=m+I+n,m,：,存储器模块数，,n,：,处理机数，,I,：,I/o,设备数，一般：,M=I+N,交叉开关阵列复杂,例子：美国。,C.MMP,、,S-1,Pn,Pn,M1,M2,Mm,I/O1,I/,Oi,交叉开关形式,多端口存储器形式,如果每个存储器模块有多各访问端口，且将分布在交叉开关矩阵中的控制、转换和优先级仲裁逻辑分别移到相应存储器模块的接口中。,I/O1,I/O1,M1,M1,M4,M3,M2,P1,P2,四端口存储器形式的结构,UNIVAC,CRAY_XMP,蠕虫穿洞寻径网络,Wormhole,。,Dally,于,1986,年提出。,机间采用小容量缓冲存储器，实现消息分组寻径存储转发之用,曙光,1000,多处理机,虫蚀寻径,(wormhole),把包分成更小的片。每个结点的寻径器中有片缓冲区。,用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”。,当消息的头片到达一个结点,A,的寻径器后，寻径器根据头片的寻径消息立即做出路由选择,特点,每个结点的缓冲器的需求量小，易于用,VLSI,实现。,较低的网络传输延迟。所有的片以流水方式向前传送，时间并行性。而在存储转发中，消息是整个的从一个结点“跳”向另一个结点，通道的使用时串行的。所以它的传输延迟基本上正比于消息在网络中传输的距离。,Wormhole,与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）。,通道共享性好、利用率高。对通道的预约和释放是结合在一起的一个完整的过程：占有一段新的通道后将立即放弃用过的一段旧通道。,易于实现,Multicast,和,Broadcast,。允许寻径器复制消息包的片并把它们从多个输出通道输出。,Wormhole,方式中，同一个包中所有的片象不可分离的同伴一样以流水方式顺序的传送。包可看作是一列火车，由火车头（头片）和被牵引的车厢（数据片）组成。,线路交换,Wormhole,存储转发,开关枢纽结构形式,把互连结构的开关设置在各个处理机或其接口内部，组成分布式结构。,美国加州大学伯克利分校设计的树形多处理机,X-TREE,存储器的组织,并行存储器的构成,多,Cache,的一致性问题,并行存储器的构成,有高位交叉和低位交叉,低位交叉：按物理地址顺序轮流地分布在各个存储模块中。,不连续，步距为,m,向量、流水或阵列处理机中采用低位交叉,高位交叉：按物理地址顺序从模块,0,到模块,m-1,依次连续分布。,连续,多处理机中采用高位交叉；,(n-1)*m,im,m,0,(n-1)*m+1,im+1,m+1,1,n*m-1,(i+1)m-1,2m-1,m-1,模块,0,模块,1,模块,m-1,模块内部单元号,模块号,log,2,n,log,2,m,m,个模块的低位交叉编址,n-1,i,1,0,2n-1,n+i,n+1,n,M*n-1,(m-1)n+i,(m-1)*n+1,(m-1)*n,模块,0,模块,1,模块,m-1,模块内部单元号,模块号,log,2,n,log,2,m,m,个模块的高位交叉编址,本地存储器（,HomeMemory,）：,处理机常用到的存储器模块；,M0,M1,Mm-1,P,p-1,P,p-1,P,p-1,处理机存储器互连网络,PMIN-,本地存储器的概念,2,紧耦合多处理机多,Cache,的一致性问题,多,Cache,的一致性问题的产生,多,Cache,的一致性问题的解决办法,多,Cache,的一致性问题,每一个处理机都有自己专用的,Cache,，,但主存中同一个信息块在多个,Cache,中都有时，会出现信息不一致情况；,写直达法,-,保证一个；,进程迁移,-,将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行；,对于进程迁移的,Cache,不一致性,-,禁止进程迁移,多,Cache,的一致性问题的解决办法,解决进程迁移引起的多,Cache,不一致性,以硬件为基础实现多,Cache,的一致性,以软件为基础实现多,Cache,的一致性,多,Cache,的一致性问题,两类方法：,硬件为基础,-,监视,Cache,协议（,Snoopy Protocol,）,写作废法、写更新法,软件为基础,-,目录表法，全映像目录表法、有限目录表法、链式目录表法,硬件方法,-,通讯量大，处理机数多时复杂；,软件方法,-,减少复杂，降低通讯量，性能价格比高，适合于处理机数多。实验系统,