多处理机系统第二版.ppt

多处理机系统,一：多处理机二：多核,多处理机系统,多处理机概念多处理机的特点多处理机结构多处理机系统调度,多处理机的Cache一致性机间互连形式机群系统多处理机实例,目标,昨夜西风凋碧树。独上高楼，望尽天涯路。理解多处理机和多核的区别衣带渐宽终不悔，为伊消得人憔悴。理解Cache一致性及解决方案众里寻他千百度，蓦然回首，那人却在，灯火阑珊处。了解多处理机结构、调度，机间互联,多处理机概念1.1多处理机概念1.2计算机的分类1.3多处理机系统的分类,一个问题,图书馆将一批新书上架，可以有多种方式。假定将书按类上架，而将书架依据在书库中的位置分成一些组。若由一工人单独完成，不能在要求的时间内完成任务。多个工人完成，假定每次一人仅往书架上放一本书。可以采用两种不同的方式：（1）将所有的书籍平均分配给每个人去完成。（2）将所有书架分成一些组，且平均分配给各个工人负责，同时将所有图书平均分配给每个工人去上架。如果工人发现一本书属于自己所负责的书架上，则将其放入书架。否则，将这本书传给所在书架对应的工人。,结论,将一个任务划分成一些子任务，并分配给多个工人去完成，工人们相互合作，这种协调的工作方式可较快地完成任务。并行计算就是严格地按照上述原理来完成的。,1.1多处理机概念,并行计算机在未来将会发挥更大的作用。通过复杂度和硅技术的提高而得到的性能的提高正在减小；获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起；并行计算机应用软件已有缓慢但稳定的发展。,1.1多处理机概念,多个处理机或多个计算机组成一个并行计算机。多处理器系统是指拥有多个CPU或多态计算机的计算系统多处理机即具有多个处理机的计算机。两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。,1.2计算机的分类,Flynn分类法单指令流单数据流（SISD）单指令流多数据流（SIMD）多指令流单数据流（MISD）多指令流多数据流（MIMD）SISD：其实就是传统的顺序执行的单处理器计算机，SIMD：相同的一条指令由多个处理部件同时执行，使用不同的数据流MISD：一组相同的数据送给多个处理部件，每个处理部件执行不同的指令序列MIMD：每个处理器取自己的指令，对自己的数据进行操作多处理机系统属于MIMD计算机系统（1）：MIMD具有灵活性（2）：MIMD可以充分利用商品化微处理器在性能价格比方面的优势,1.3多处理机系统的分类,根据内存和互联策略将MIMD分类一：共享内存架构（紧耦合）二：分布式内存架构（松耦合）,处理器组织SISDSIMDMISDMIMD早期的单处理机向量机阵列机共享内存分布内存SMPNUMA机群,多处理机的特点2.1多处理机特点2.2SIMD和MIMD,2.1多处理机特点,1、结构灵活性2、程序并行性3、并行任务派生4、进程同步5、资源分配和进程调度,SIMD和MIMD,SIMD和MIMD,多处理机系统结构3.1共享内存架构3.1.1集中式共享内存3.1.2分布式共享内存3.2.分布式内存架构,3多处理机系统结构,多处理机结构共享内存（紧耦合）和分布式内存（松耦合）3.1共享内存架构共享内存架构：处理机之间共享主存储器。紧耦合多处理机是通过共享主存来实现处理机间通信的。分为集中式共享内存和分布式共享内存。多个处理器，高速缓存（cache）一般利用公共总线实现互连。这类机器是通过共享主存实现处理机间的相互通信.这类机器有时被称为UMA(uniformmemoryaccess)机器。支持对共享数据和私有数据的Cache缓存。,3.1共享内存架构,优点：（1）联系紧密（2）成本低缺点：（1）处理机数量增多时，访问主存的冲突概率会加大（2）受制于处理机与主存之间互联网络带宽,3.1.1集中式共享内存,3.1.2分布式共享内存,物理上独立的内存具有逻辑上统一的共享地址空间。,3.2.分布式内存架构,多个计算机模块组成，称之为结点每个结点包含：处理器存储器IO存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。分布式存储器结构需要高带宽的互连。,3.2分布式内存架构,CAS：ChannelandArbiterSwitch（通道和仲裁开关）具有一个高速的通信缓冲存储器,3.2分布式内存架构,分布式内存结构的优点(1)如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；(2)对局部存储器的访问延迟低。主要缺点处理器之间的通信较为复杂，且各处理器之间访问延迟较大。,4多处理机系统调度4.1多处理机系统与单机调度的区别4.2多处理机系统调度分配方式4.3多处理机系统调度算法,4.1多处理机系统与单机调度的区别,多处理机调度与单机调度的主要区别涉及两个资源分配问题一是存放程序或数据的存储器分配及如何访问他们的问题二是将等待执行的就绪进程分配到哪一个处理机上执行的问题多处理机系统的调度目标是：以最高的可靠性，使用最少的处理机在最短的时间内完成最多的可以并行完成的进程,4.2多处理机系统调度分配方式,静态分配为每个处理机维护一个专门的短程队列优点是调度的开销小缺点是一个处理机可能空闲，这时他的队列为空，而另一个处理器却积压了很多，为了防止这种情况发生，需要使用一个公共队列动态分配所有进程都进入一个全局队列，然后调度到任何一个可用的处理器中。这样，在一个进程的生命周期中，他可以在不同的时间在不同的处理器上执行,4.3多处理机系统调度算法,自调度算法（1）先来先服务（2）最少线程数优先自调度算法不足就绪线程队列将成为性能的瓶颈被抢占的线程很难再同一个处理器上恢复运行，会带来性能下降线程都被放在公共线程池中，所有线程获得处理器的机会相同。如果一个程序的线程希望获得较高优先级，进程切换将导致性能的折中,4.3多处理机系统调度算法,群组调度算法基本思想：把一组进程在同一时间一次性调度到一组处理器上运行。优点：当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，系统性能得到提高。由于一次性同时调度一组处理器，调度的代价也将减少方法一：面向应用进程平均分配方法二：面向所有进程平均分配方法三：统一时间匹配线程数加权调度算法（例子：两个应用程序，一个有4个线程，另一个有1个线程，则第一个应用程序分4/5的CPU时间，第二个程序分1/5的CPU时间）,4.3多处理机系统调度算法,专用处理器调度算法基本思想：给一个应用指派一组处理器，一旦一个应用被调度，它的每个线程被分配一个处理器并一直占有处理器运行直到整个应用运行结束采用这一算法，处理器将不使用多道程序设计，即该应用的一个线程阻塞后，线程对应的处理器不会被调度给其他线程，而处于空闲状态,Cache一致性问题5.1多处理机cache的一致性5.2产生cache不一致的原因5.3实现一致性的基本方案,一个问题,两个人要从北京到昆明，订到了同一个座位的票。多份相同的数据同时存在于不同的Cache中，如果允许CPU随意更新自己的那份数据，就产生了不一致的数据,多个处理器共享一个存储器，当处理器规模较小时，这种机器十分经济支持对共享数据和私有数据的cache缓存，私有数据供一个单独的处理器使用，而共享数据供多个处理器使用,共享数据进入cache，产生一个新的问题Cache一致性问题！,Cache的一致性如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的,需满足以下条件,处理器P对X进行一次写之后又对X进行读，读和写之间没有其它处理器对X进行写，则读的返回值总是写进的值。一个处理器对X进行写之后，另一处理器对X进行读，读和写之间无其它写，则读X的返回值应为写进的值。对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。,产生cache不一致的原因,产生cache不一致的原因,写共享数据引起的不一致性进程迁移引起的数据不一致性I/O造成的数据不一致性,写共享数据引起的不一致性,P1,P2,更新前,x,x,x,处理机,Cache,共享存储器,P1,P2,写通过,x,x,x,P1,P2,写回,x,x,x,总线,进程迁移引起的不一致性,产生cache不一致的原因,右图为：包含共享变量x的进程原来在P1上运行，并对x进行了修改（但采取写回策略，所以暂时没有修改Memory），由于某种原因迁移到P2，修改过的x仍在P1的Cache中，P2运行时从Memory中得到x，这个x其实是“过时”的，所以造成了不一致。中间图为：P2中运行的进程对x进行了修改，采取写通过策略，所以把Memory中的x也修改为x，由于某种原因该进程迁移到P1，但P1的Cache中仍为x，所以造成不一致。,I/O造成的不一致性,P1,P2,x,x,存储器,P1,P2,x,x,P1,P2,x,x,x,x,x,x,x,I/O,存储器,输入,存储器,输出,Cache,总线,处理机,产生cache不一致的原因,中间图为：当I/O处理机将一个新的数据x写入主存储器时，绕过采用写通过策略的cache，则C1和共享存储器之间产生了不一致。右图为：直接从主存储器输出数据时（绕过Cache），采用写回策略的高速缓存产生不一致性。,实现一致性的基本方案,软件方法硬件方法,软件Cache一致性方法依赖于编译器和操作系统解决数据的一致性，尽量避免使用硬件电路和硬件逻辑。最简单的方法就是防止共享数据进入Cache软件方法优缺点另一方面：编译时段的软件方法通常要进行保守的决策，导致Cache的利用率不高一方面：软件方法将检测潜在的数据一致性问题从运行时段转移到了编译时段，设计的复杂性从硬件转移到了软件,实现一致性的基本方案,以软件为基础的办法，靠软件的作用来限制一些公用的可写数据存放到cache中。在编译时，通过编译程序分析，把数据分为能用cache的（cacheable）和不能用cache的（noncacheable）两部分，不能用cache的数据只能存在主存中。为了尽量提高工作效率，并不是把所有要写入的数据都归入不能用cache的数据之列，编译程序在分析时，要看一下可写数据是否在哪一段时间里可以安全地存入cache，哪一段时间里不允许写到cache中。使它在安全的期间使用cache存放，等到这段安全时期终了时，再把这个可写数据在cache中的副本作废，并规定不能用cache。这种方法比较简单，实际是避开了在CACHE中实现可写数据的共享问题，影响系统性能。,实现一致性的基本方案,硬件方法基于硬件的方法在程序运行时，动态的识别潜在的不一致条件，只有当不一致问题出现时，才会去处理。相较于软件方法来说，性能有提高；Cache利用高效；对程序员透明。Cache一致性协议：对多个处理器维护一致性的协议关键：跟踪记录共享数据块的状态共享数据状态跟踪记录技术目录协议监视协议MESI协议,实现一致性的基本方案,目录协议目录协议由一个目录和一个集中控制器构成目录中存放共享数据的分布信息，存放在主存中，集中控制器是主存控制器的一部分当有数据请求时，集中控制器会检查目录，集中控制器强制共享数据的CPU对共享数据无效，批准数据请求，然后发出必要的数据传送命令，进行主存与Cache或Cache与Cache间的数据传送。,实现一致性的基本方案,监视协议每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。当某个处理器对其共享的数据进行更新时，必须以广播的方式通知其他所有的Cache。每个Cache控制器能够监视网络，当看到这些广播的通知后就会做出相应的反应写无效协议写更新协议,实现一致性的基本方案,写无效在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权。,实现一致性的基本方案,写更新当一个处理器写某数据项时，通过广播使其它Cache中所有对应的该数据项拷贝进行更新。,实现一致性的基本方案,写更新和写无效协议性能上的差别对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写无效写一下只需一次作废操作对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写无效协议下仅在对本块第一次写时进行写无效操作从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写无效协议中，需要一个新的拷贝,实现一致性的基本方案,MESI协议在Cache的标记位中扩展两位，用于标记每个Cache的状态修改状态（Modified）专有状态（Exclusive）共享状态（Shared）无效状态（Invalid）本质上就是写无效协议,机间互联形式6.1总线形式6.2交叉开关形式6.3多端口存储器形式6.4多级互连网络形式6.5开关枢纽形式,1.总线形式IBMStretch和UNIVACLarg多处理机采用的就是单总线方式,单总线的优点：单总线方式结构简单、成本低，系统上增减模块方便，缺点：对总线的失效敏感。而且，处理机数增加会增大访问总线冲突的概率而导致系统效率急剧下降。,环形互联形式,总线仲裁算法静态优先级算法：为每个连到总线的部件分配一个固定的优先级固定时间片算法：把总线按固定大小时间片，轮流提供给部件使用动态优先计算法：让总线上各部件优先级可根据情况按一定规则动态地改变，如LRU算法先来先服务算法：按访问总线请求先后顺序来响应,交叉开关形式,每个交叉点是一个可以打开或关闭的一元开关，提供源和目的之间点对点的连接通路。控制、仲裁、转换机构均在开关中交叉点开关网络中n对处理器可以同时传送数据交叉开关网络的带宽和互联性最好交叉开关方式不适宜连接过多的处理机。影响多处理机系统性能的瓶颈不再是互连网络，而是共享的存储器,多端口存储器形式,主要思想：将所有交叉点仲裁逻辑和跟每个存储器模块有关的开关功能移到存储器控制器中。多端口存储器结构是一个折中方案，它介于低成本性能的总线系统和高成本高带宽的交叉开关系统之间。缺点：十分昂贵，不能扩展，当系统配置很大时，需要大量的互联电缆和连接器,多级互连网络形式,是介于总线(N)与交叉开关(N2)中间的一种(Nlog2N)。适用于构造大型多处理机系统。,开关枢纽形式,将互连结构设置在PE或其接口内部，组成分布结构(松耦合)。开关枢纽：由仲裁单元和开关单元组成，端口数不能多。结构：由开关枢纽组成各种结构，如树形结构。开关枢纽网络适宜于PE数较多的系统。,X-TREE多处理机结构框图（美国加州大学伯克利分校设计的树形多处理机）,机群系统7.1机群系统的组成7.2机群的分类7.3机群的关键技术7.4机群的特点,机群系统的组成,机群系统：利用高速通用网络将一组高性能工作站或高档PC机，按某种结构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。原因：（1）微处理器的性能不断提高，价格在不断下降（2）网络传输速度的提高。（3）并行编程环境的开发使得新编并行程序或改写串行程序更为容易。,机群系统的组成,从结构和结点间的通信方式来看，属于分布存储系统。机群系统中的主机和网络可以是同构的，也可以是异构的目前大多数机群系统采用的是现有商用工作站和网络，编程环境是建立在操作系统之上由建立在一般操作系统上的并行编程环境完成系统的资源管理和协同操作，同时屏蔽了工作站及网络的异构性，对程序员和用户来说，是一个整体的并行计算机系统,机群的分类,机群有两种类型，一种是专用机群，另一种是企业机群专用机群是为代替传统的大中型机或巨型机而设计的。具有以下特点：（1）装置比较紧凑。（2）一般都是同构性配置（3）采用集中控制（4）内部通信对外界是屏蔽的,机群的分类,企业机群主要是为了充分利用各个结点的空闲资源而设计的，它有以下特点：（1）装置是松散的。（2）经常采用异构性配置。（3）采用分散控制。（4）内部通信对外界是暴露的。,机群系统的关键技术,(1)高效的通信系统精简通信协议(2)并行程序设计环境PVM(ParallelVirtualMachine)ExpressLinda,机群系统的关键技术,(3)并行程序设计语言在多处理机系统中，必须用并行程序设计语言编写程序。或者把已经用串行语言编写的程序转换成并行语言程序之后，才能在多处理机系统上运行。(4)负载平衡技术一个大任务可分解为多个子任务，把多个子任务分配到各个处理结点上并行执行的技术称为负载平衡技术(5)并行程序调试技术用并行程序设计语言编写程序，比用串行程序设计语言更容易出错，因此，在多处理机系统中，用并行程序设计语言编写程序更加依赖于并行调试工具。(6)可靠性技术,机群系统的特点,系统开发周期短。用户投资风险小。系统价格低。节约系统资源。系统扩展性好。用户编程方便,多处理机实例UMA系统NUMA系统COMA系统,多处理机实例,UMA系统均匀内存访问系统（UniformMemoryAccess）所有的处理器使用load/store指令可以访问主存的任一位置，不管访问主存的哪个区域，处理器的访问时间都是一样的，不同的处理器访问主存所经历的时间也是一样的,多处理机实例,NUMA系统非均匀内存访问系统（NonuniformMemoryAccess）所有的处理器使用load/store指令可以访问主存的任一位置，单处理器访问主存的时间会因访问区域不同而不同，,多处理机实例,COMA只有Cache存储器结构（Cache-onlyMemoryArchitecture）一种只用高速缓存的多处理机。COMA模型是NUMA机的一种特例,(1)多向量处理机系统：如CRAYYMP-90,NECSX-3和FUJITSUVP-2000(2)SMP(SymmetryMultiProcessors)对称多处