单击此处编辑母版标题样式,,2003.3.1,计算机系统结构,*,第九章,MIMD,计算机(,P499),,MIMD,计算机与,SIMD,计算机的主要区别，在于,SIMD,只能在,同一时刻,做,多件相同,的事情，而,MIMD,却可以,在,同一时刻,做,多件相同,或,不同,的事情（多指令流所致），所以求解同一个问题时采用,MIMD,将能实现更大比例的并行操作，即处理效率更高从并行处理的级别看，,SIMD,是,数据级并行处理,，,流水线,是,指令级并行处理,，,MIMD,是,任务级并行处理,由于技术上的原因，目前实现的,MIMD,计算机都是,多处理机系统,，包括,多计算机系统,多处理机系统由多台处理机连接而成，它们能够并行执行独立的程序模块，并且相互通信和同步，以实现作业、任务级的并行2003.3.1,1,,计算机系统结构,CU2,CU1,CUn,PUn,PU2,PU1,MMn,MM2,MM1,IS1,IS1,IS2,IS2,ISn,DS1,ISn,DS2,DSn,多,指令流,多数据流,MIMD,2003.3.1,2,,计算机系统结构,9.1,MIMD,的典型结构(,P500),多处理机系统通常包含多个处理机模块、多个存储器模块、多个,I/O,通道，这些设备与单处理机系统中的设备没有本质不同，,最大的差别是互连网络和多机操作系统,。
由于多处理机系统是在作业、任务级并行，处理机之间的通信不像,SIMD,系统那样频繁和急迫，所以,互连网络可以采用通用网实现,，以便在满足流量需要的前提下降低成本1)共享存储器方案（紧耦合型）,,,P500,图9.1(,a),存储器和,I/O,设备是独立的子系统，通过互连网络为所有的处理机共享2)分布存储器方案（松耦合型）,,,P500,图9.1(,b),每台处理机有自己的存储器和,I/O,设备处理机之间的信息交换通过互连网络2003.3.1,3,,计算机系统结构,2003.3.1,4,,计算机系统结构,它有多个控制器，至少有多个指令部件，用以对各个,PE,实现单独的控制，而又相互协调配合多处理机的外围设备要能够被多个,PE,分别调用，因而要,通过互连网络,转接，而不像并行处理机的外围设备那样统一访问主存储器并行处理机由于主要完成数组向量运算，它的,PE,和,MM,之间的数据交往比较有规则，互连网络的作用主要放在数据对准上，功能简单；,多处理机的互连网络必须满足各个,PE,随机地访问主存储器的要求,，连接模式、频带和路径选择等问题都要复杂多处理机属,任务级并行,，,SIMD,属于数据级并行。
多处理机与并行处理机（,SIMD,）,的主要区别,2003.3.1,5,,计算机系统结构,•,结构灵活性,,并行处理机是针对数组、向量处理而设计的而多处理机不限于数组向量的处理，力图把能并行处理的任务、数组，以至标量都进行并行处理•,程序并行性的识别,,并行处理机实现操作一级的并行，其并行性存在于指令内部多处理机中，因为不限于解决数组向量处理问题，并行性存在于指令外部，即表现在多个任务之间再加上系统通用性的要求，就使程序并行性的识别难度较大因此，它必须利用多种途径，如算法、程序语言、编译、操作系统、以至指令、硬件等，尽量挖掘各种潜在的并行性多处理机的特点,2003.3.1,6,,计算机系统结构,•,并行任务的派生,,并行处理机依靠单指令流对多数据流实现并行操作，这种并行操作是通过各条单独的指令加以反映和控制的，指令本身就可以启动多个处理部件并行多处理机,是处于多指令流操作方式，一个程序当中就,存在多个并发的程序段,，需要专门的指令来表示它们的并发关系以控制它们的并发执行，以便一个任务开始被执行时就能派生出可与它并行执行的另一些任务该过程称为,并行任务派生,可能达到较高的效率,9.2,MIMD,的并行程序控制(,P608),2003.3.1,7,,计算机系统结构,•,进程同步,,并行处理机是操作级的并行，所有处于活动状态的处理单元同时执行共同的指令，受同一个控制器控制，工作自然同步。
多处理机所实现的是指令、任务、程序级的并行在同一时刻，不同的处理机执行着不同的指令要区分进程之间的多种不同的依赖关系要求多处理机采取特殊的同步措施，使并发进程之间保持程序所要求的正确顺序•,资源分配和进程调度,,处理机执行并发任务，需用处理机的数目没有固定要求，各个处理机进入或退出任务的时刻互不相同，所需共享资源的品种、数量又随时变化，情况十分复杂，需要好的资源分配和进程调度策略9.2,MIMD,的并行程序控制(,P608),2003.3.1,8,,计算机系统结构,(1)任务派生语句 ───,当前运行的进程向操作系统申请创建一个新进程，并试图用一个空闲处理机来运行它如果操作系统没有找到空闲处理机资源，则让新进程排队等待格式：,FORX <,进程名>,,(2)任务汇合语句 ───,检查包括当前进程在内的各先期并发进程是否完成，如未完成则停止当前进程，释放其处理机资源，如已完成则让当前进程继续执行，通常是转入后继进程汇合语句的每次执行会对一个计数器加1（该计数器初值为0），直至达到语句所要求的汇合进程数格式：,JOIN <,汇合进程数>，,9.2,MIMD,的并行程序控制(,P608),2003.3.1,9,,计算机系统结构,实例：,x = ( a + b )×( a - c ),,,我们设想用3个进程来完成上式中3个运算，则它们之间的相关关系可用数据相关图来描述（右图）。
并行程序可用,Fork/Join,语句写成如下形式：,,k: Fork k+3,,k+1: Add A,B,T1,,k+2:,Goto,k+4,,k+3: Sub A,C,T2,,k+4: Join 2,1,,k+5:,Mul,T1,T2,X,,,该程序在2台处理机的,MIMD,系统上运行的时空关系可用资源时间图表示（假设进程,k,执行时间大于进程,k+3）2003.3.1,10,,计算机系统结构,9.,4 MIMD,的加速性能模型(,P502～P512),(1)两个处理机的并行模型（,P504,）；,,,,总处理时间 =,R×max{ M-K，K } + C×( M-K )×K,,,其中：,M ──,任务总数；,,,K ──,分配给处理机1的任务数；,,,R ──,执行1个任务所需时间；,,,C ──,进行1次通信所需时间最优解：,P505,第1～3行2),N,个处理机的并行模型（,P505,）总处理时间 =,R×max{,K,i,} + (C/2)×Σ[K,i,×( M-,K,i,)],,= R×max{,K,i,} + (C/2)×( M,2,-ΣK,i,2,),,2003.3.1,11,,计算机系统结构,2003.3.1,12,,计算机系统结构,9.,5,多处理机实例（,P521,）,9.,5.1,MPP（,P521,）,,大规模并行处理系统,MPP,───,,几百台以上处理机通过专用互连网络构成的高性能,MIMD,系统。
造价高，性能也高9.,5.2 SMP（P528）,,,共享存储型多处理机系统,SM,P,───,,所有处理机共享统一编址的内存空间，由硬件协调访存冲突，并行程序设计者感觉特别方便9.,5,.3,CLUSTER（,机群系统，,P541,）,,,机群系统,CLUSTER,───,,几台至十几台微机或工作站通过通用网络构成的低成本并行处理,MIMD,系统，与,MPP,特点相反2003.3.1,13,,计算机系统结构,机群系统的具体知识,9.,5.3.1,什么是机群系统,,利用,高速通用网络,将一组高性能工作站或,高档,PC,机,，按某种结构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度胁调处理，实现高效并行处理的系统从结构和结点间的通信方式来看，它,属于分布存储,系统，主要利用,消息传递方式,实现各主机之间的通信，由建立在一般操作系统之上的并行编程环境完成系统的资源管理及相互协作，同时也屏蔽工作站及网络的异构性，对程序员和用户来说，机群系统是,一个整体,的并行系统机群系统中的,主机和网络可以是同构的，也可以是异构的,目前已实现和正研究中的机群系统大多采用现有商用工作站和通用,LAN,网络，既可缩短开发周期又可利用最新微处理器技术。
大多机群系统的并行编程环境是建立在,Unix,操作系统之上，尽量利用商用系统的研究成果，减少系统开发与维护费用2003.3.1,14,,计算机系统结构,•,机群系统出现的原因（有利条件）：,,,(1),微处理器性能机价格比迅速提高,，可充当机 群系统的运算节点；,,,,(2),网络技术进步使得松散耦合系统的通信瓶颈得到缓解,例,：,ATM155M/620 M,；以太网,1000 M,；甚至有的产品已接近了多处理机专用互联网（如交叉开关网络、多机网络）性能例如,MyriCom,公司的,Myrinet,1.28G,，开关延迟只有,1us,3),并行编程环境,的开发使得编制并行程序或改写串行程序更加容易2003.3.1,15,,计算机系统结构,Computer Food Chain,2003.3.1,16,,计算机系统结构,与传统的并行处理机相比，机群系统有下列特点：,,（,1,）开发周期短,,,·,结点,——,商用工作站,,,,·,网络,——,通用网络，例如,,ATM,,·,操作系统,——Unix/LINUX,,·,并行程序设计语言,——,在,C,、,Fortran,上扩充2,）用户投资风险小,,购置巨型机或多处理机系统，投资大，但很可能用不起来。
9.,5.3.2,机群系统的特点（,P541,） P542 (1)-(6),2003.3.1,17,,计算机系统结构,（,3,） 系统价格低,,（,4,）充分利用系统资源,,某计算机系,100,多台工作站，一般单机系统的使用率不到,10%,而组成机群系统后，可达到,80%,左右机群系统可分批更新5,）系统扩展性好,,（,6,）用户编程方便,,并行程序设计语言一般是在,C,、,C++,或,Fortran,中加入,",通信原语,",扩展出来的2003.3.1,18,,计算机系统结构,机群系统的关键技术主要包括：,,（,1,）高效通信系统,,机群系统一般采用通用局域网，目前局域网技术大体分两类,,,·,共享介质网络 例：,Ethernet,,·,开关网络例：,ATM,Myrinet,和,100M,交换式,Ethernet,三、机群系统的关键技术,,人们希望机群系统具有以下特点：,,·,较高的节点运算速度；,,·,系统加速比性能接近线性增长；,,·,并行应用程序的开发要高效、方便2003.3.1,19,,计算机系统结构,网络性能的性能描述：,,,·,带宽速度：,10-100-1000Mbps,,往返延迟：,1,字节的数据包的往返传输时间。
新网络技术大幅提高了传输速度，但延迟时间还没多大变化（如下表）,,,,,,,,,,所以机群系统中局域网研究方向主要是：减少往返延迟和提高带宽利用率目前网络带宽利用率较低例如,640Mbps,的,Myrinet,,,应用程序可见带宽才,38Mpbs,提高带宽利用率途径之一： 精减协议， 例,TCP/IP,层次太多2003.3.1,20,,计算机系统结构,（,2,）并行程序设计语言和环境,,一般都是基于消息传递,(Message Passing ),现在的实现方法一般是：使用原有顺序编译器连接并行程序库研究方向：,1,）扩展原有顺序语言,,,2,）开发全新的并行语言,,,3,）研究自动化并行编译器，直接将顺,,序程序编译成并行代码并行程序设计环境（,P551,）,,,是介于分布式操作系统与并行应用程序之间的支撑软件组，提供并行运算所需的各种软件模块和管理功能，以此提升操作系统功能来全面支持并行计算最著名的并行程序设计环境是,PVM,2003.3.1,21,,计算机系统结构,（,3,）全局资源管理及利用,,有效的利用资源是机群系统的重要目标当前的方法：在一般的操作系统（,Unix,、,NT,等）上建立一个全局,Unix,。
共享资源,——,例如各节点的内存，在,155M,的,ATM,网络上，读取其它节点内存的时间仅为读取本地硬盘的五分之一据统计，对需经常访问硬盘的的应用程序，使用这种方法可以比使用本地磁盘快,5~10,倍2003.3.1,22,,计算机系统结构,对比,,多组织,可以多个组织（复用）,一个组织,一个组织,中等,高或者容错,低,低或中,多,多,单一,多,/,单地址空间,(,分布式共享内存,),同类,OS,或异构,OS,N,个同类,OS,独立的完整的,OS,一个主要的内核和多个微内核,目前不支持,某一层次支持,支持完全的,SSI,部分支持,独立运行队列,多队列协同运行,单一运行队列,主机单一队列,跨地区或国家,楼区范围,一个机箱,一个房间,10,～,1000,以上数量级,100,左右的数量级,10,～,100,数量级,100~1000,数量级,归属单位,系统可用性,地址空间,结点操作系统,单一系统映像,任务调度,连接距离,结点个数,分布式系统,集群,SMP,MPP,特征,2003.3.1,23,,计算机系统结构,本章小结,(1),MIMD,的2种典型结构,,,(2),MIMD,的并行程序控制,,,(3),MIMD,的加速性能模型,,,,,,,,,,,习题：,P561,，题6，题18（参看,P,346,题18,(3)和,P321,倒2段）。
2003.3.1,24,,计算机系统结构,。
