第07章-并行处理与普适计算.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/5/31,#,第,7,章 并行处理与普适计算,7.1,并行计算机系统结构,7.2,单处理机系统中的并行机制,7.3,多处理机系统的组织结构,7.4,多处理机操作系统和算法,7.5,从计算机到,网络,7.6,普适计算和移动计算,习题,7,第,7,章 并行处理与普适计算,7.1.1,指令级并行和机器并行,7.1,并行计算机系统结构,1,并行性（,Parallelism,）,并行计算机系统最主要的特性就是并行性（,Parallelism,），并行性是指计算机系统具有的同时运算或同时操作的特性，它包括同时性与并发性两种含义。,同时性（,Simultaneity,）,：指两个或多个事件在同一时刻发生在多个资源中。,并发性（,Concurrency,）,：指两个或多个事件在同一时间间隔内发生在多个资源中。,一般来说，可以从两个方面来开发处理机内部的并行性。,空间并行性：,即在一个处理机内设置多个独立的操作部件并行工作，称为多操作部件处理机和超标量处理机,。,时间并行性：,就是采用流水线技术。,图,7.1,并行处理技术发展,多道程序,分时系统,虚拟存储器,多终端,远程终端,分布处理系统,局域计算机网,通信处理机,计算机网,多存储体,多操作部件,相联处理机,并行处理机,同构型多处理机系统,可重构,容错多处理机,紧密耦合系统,现行控制高速缓存,指令操作宏流水线,异构型多处理机系统,高级语言处理机,数据库,处理机,松散耦合系统,专用,外围处理机,多计算机系统,单处理机,资源共享,资源重复,时间重叠,多机互连,功能专用化,网络化,并行处理同样也满足Amdahl定律,：,并行处理,加速比,=,除了Amdahl定律外，反映并行程序性能还有一个重要的度量：计算与通信的比率，意即计算,/,通信比率随着处理数据规模的增大而增加，随着处理器数目的增加而减少。,2,单机,并行性,时间重叠,（,Time Interleaving,）：,即,时间并行,技术。,让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分,，如,指令流水线。,资源重复（,Resource Replication,）：,即,空间并行,技术。,通过重复设置的硬件资源来提高系统可靠性或性能。例如,，两,台或多,台计算机完,成同样的任务。,时间重叠,+,资源重复（,Time Interleaving&Resource Replication,）：,即,时间并行,+,空间并行技术，当前并行机制的主流。如多核,CPU,，每个,处理器核内部有多级指令流水线。,资源共享（,Resource Sharing,）：,是,一种软件,方式，利用软件让多个用户按一定时间顺序轮流地使用同一套资源，以提高其利用率，这样相应地提高整个系统的性能例如多道程序分时系统。,3,多,机并行性,对于,多机系统，提高计算机系统的并行性的技术途径，除了单机系统的方法外，还包括：功能专用化，机间互连，网络化技术途径发展成异构型多处理机，同构型多处理机，分布式处理机系统。,并行处理,机,(Parallel Computer System),是通过重复设置大量相同的处理单元,PE,（,Processing Element,），将它们按一定的方式互连，在统一的控制部件,CU,（,Control Unit,）控制下，对各自分配来的不同数据并行地完成同一条指令所规定的操作。它依靠操作一级的并行处理来提高系统的速度。,4,并行,的等级和分类,1,）从计算机信息加工步骤和阶段看，并行性等级可分为：,存储器,操作并行,并行存储器系统和以相联存储器为核心构成的相联处理机。,处理器操作步骤并行,可以是一条指令的取指、分析、执行等操作步骤，也可以是具体运算。,处理器操作并行,为支持向量、数组运算，可以通过重复设置处理单元进行，如并行处理机。,指令、任务、作业并行,称为较高级并行，属于多指令流多数据流计算机,。,多,个,CPU,或处理元件紧密相连，它们之间具有高带宽和低时延，而且是亲密计算，称它们为紧耦合（,Tightly Coupled,）。当它们距离较远，具有低带宽、高时延，而且是远程计算，称它们为松散耦合（,Loosely Coupled,）,。,2,程序划分和粒度,并行性,的开发还可以按程序大小划分不同粒度的开发方式,。,图,7.2,五种程序执行级别,作业级（程序）,任务级（过程或程序段）,子任务级（例行程序，或子程序）,指令或语句,循环或递归循环,级,5,级,4,级,3,级,2,级,1,通信需求与调度开销,并行程度,粗粒度,中粒度,细粒度,7.1.2,并行计算机系统,结构,图,7.3,并行计算机系统结构,向量计算机,/,向量处理机,(Vector Computer,，,VC/Vector Processor,，,VP),SIMD,的两个子类,之一。分为,两大类体系结构：,向量,-,寄存器,处理器,和,存储器,-,存储器,向量处理器,。阵列处理机,(Array Computer/Array Processor),SIMD,的两个子类之一，属于分布式内存,SIMD(DM-SIMD),系统，包括许多完成同样功能的、完全相同的处理器,，处理器,分布在不同数据集合上执行相同的指令序列,。,多处理器,MIMD,的两个子类之一,。,对称式共享存储器多处理机,(Symmetrical Multi-Processing,，,SMP),，,分布式共享存储器多处理机,(Distributed Shared-Memory,，,DSM,),。,多计算机,MIMD,的两个子类,之一,。,大规模并行处理机,(Massively Parallel Processing Computer,，,MPP),，,通信机制采用专门设计的高性能互连网络和消息传递,方式,。,7.2.1,超线程和同时多线程,SMT,线程,，有时被称为轻量级进程,(Lightweight Process,，,LWP,），是程序执行流的最小单元，是进程内的一个相对独立且可独立调度和指派的执行单元，它比进程要,“,轻巧,”,得多。,超线程技术,就是利用特殊的硬件指令，把一个物理内核模拟成两个逻辑内核，让单个处理器都能使用线程级并行计算，进而兼容多线程操作系统和软件，减少了,CPU,的闲置时间，提高的,CPU,的运行速度。,同时,多线程技术,（,Simultaneous MultiThreading,，简称,SMT,），一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技术，使用的是线程级并行性（,Thread Level Parallelism,，简称,TLP,）,。,7.2,单处理机系统中的并行机制,实现,多线程有两种主要的方法：,细粒度（,Fine-Grained,）多线程,粗粒度（,Coarse-Grained,）多线程,7.2.2,单片多核处理器,CMP,单,芯片多处理器,(Chip Multiprocessors,，,CMP),与同时多线程处理器,(,Simultaneous Multithreading,，,SMT),，这两种体系结构可以充分利用这些应用的指令级并行性和线程级,并行性。,对称多核处理器,(Symmetric Multiprocessing System,，,SMP,),采用大量相同的通用处理器,内核。,非对称多核处理器,(Asymmetric Multiprocessing System,，,AMP,),中通用处理器的数量相对较少，并与一系列专用加速器引擎结合使用，由后者专门运行计算强度较高、对时延敏感的任务。,7.2.3,协处理器,协处理器,（,coprocessor,）是为减轻主处理器负担、协助主处理器完成特定工作的专用处理器，通过主处理器和协处理器的并行工作使计算机的速度得到提高。,从,物理角度看，协处理器可以是单独的机柜（如,IBM 360,的,I/O,通道）、主板上的插接板（如网络处理器）、独立的芯片（如数学协处理器,80387,）、甚至可以内置于主处理器芯片中（如,Intel,从,80486,开始将数学协处理器置于,CPU,内）,。,7.2.4,超标量与超流水线,（,1,）超标量,SA,标量流水技术,将一条指令分成若干个周期，以便多条指令重叠处理，从而提高处理器部件利用率。超标量有时称为第二代,RISC,。,超标,量体系结构,(Superscalar Architectures)CPU,内一般能有多条流水线，这些流水线能够并行处理，能够在一个时钟周期执行多个指令。处理器或指令编译器能够判断指令能独立于其它顺序指令而执行，还是依赖于另一,指令必须,跟其按顺序执行。处理器然后使用多个执行单元同时执行两个或更多独立指令,。,（,2,）超流水线,SP,超流水线（,Superpiplined,）又叫做深度流水线，是指某型,CPU,内部的流水线超过通常的,56,步以上，通过细化的流水，提高工作效率。使得机器在一个周期内完成一个甚至多个操作，其实质是用空间换取时间,。,（,3,）超标量超流水线,SASP,现在,很多,CPU,都是将超标量和超流水线技术一起使用，例如,Pentium IV,，流水线达到,20,级，频率最快已经超过,3GHz,，,经典,MIPS,只有,5,级流水。超标量超流水线处理机，在一个基本时钟周期内能够分时发送多组指令，并且每组指令又可包涵一条或多条指令的处理机。,（,4,）超长指令字,VLIW,超长指令字,(Very Long Instruction Word,，,VLIW),一种非常长的指令组合，它把许多条指令连在一起，增加了运算的速度,。超长指令字,(VLIW),是,指令级并行，超,线程是,线程级并行，而多内核则是芯片级并行,。,7.3.1,系统拓扑结构,7.3,多处理机系统的组织结构,（,1,）共享存储型紧耦合系统,（,2,）点对点型松耦合系统,（,3,）共享存储型多处理机,（,4,）松散耦合多处理机系统,（,5,）机群（集群）系统,7.3.2,多处理机系统中的存储器管理,（,1,）集中共享（共享存储）的并行处理机,每个,PE,没有局部存触器，存储模块以集中形式为所有,PE,共享,。,图,7.15,集中共享存储器结构,ICN,PE0,PE1,PEN-1,MM0,MM1,MMN-1,CU,SC,I/O-CH,I/O,SM,图,7.16,分布共享存储器结构,PEM0,PE0,PEM1,PE1,PEM,N-1,PEM,N-1,ICN,CU,CUM,I/O,接口,D,SC,（,2,）分布共享（分布存储）的并行处理机,各个处理单元设有局部存储器存放分布式数据，只能被本处理单元直接访问。此种局部存储器称为处理单元存储器（,Processing Element Memory,）,PEM,。在控制部件,CU,内设有一个用来存放程序的主存储器,CUM,。,7.3.3,多处理机系统中的通信,同步,消息传递：是指请求处理器发送一个请求后一直要等到应答结果才继续运行。,异步,消息传递：是指发送方不先经请求就直接把数据送往数据接收方,。,大多数,消息传递系统都提供两个原语,(,通常是库函数调用,),：,send,和,receive,，但这两个原语可能有多种不同的语义,。,（,1,）共享地址空间,：,物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址。这类计算机被称为分布式共享存储器系统（,DSM),，,NUMA,机器等。,（,2,）通信机制,：,消息传递通信机制，多个独立地址空间的计算机采用，通过处理器间显式地传递消息来完成。这些消息请求进行某些操作或者传送数据。在共享存储器上支持消息传递相对简单。在消息传递的硬件上支持共享存储器就困难得多。,7.3.4,多处理机高速缓冲存储器一致性,导致,多处理机系统中,Cache,内容不一致的因素有三个：,进程迁移。在多处理器系统中，进程可以在处理器中相互迁移,。,输入输出活动。绕过,Cache,的,I/O,操作会引起,Cache,与共享内存的不一致性,。,可写数据的共享。一台处理机采用全写法或回写法修改某一个数据块时，引起其它处理机的,Cache,中同一副本的不一致,。,解决多处理机,Cache,一致性有以硬件、软件为基础的两种方法：监视,Cache,协议法（,Snoopy Cache Protocol,）、目录表法（,Directory Scheme,）、以软件为基础的办法。,1,监视,Cache,协议法（,Snoopy Cache Protocol,）,1,）采用两种方法来解决,Cache,一致性问题：,写直达协议（,Write-Invalidate,）,也,称作,写无效协议,或,写作废协议,，因为是把数据块作废的办法，在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。,写,回协议（,Write Back,）,又,称为,MESI Cache,一致性协议，,CPU,做写操作时，修改数据写入,Cache,块，但不立刻写入共享存储器，在,Cache,中设置状态以表示该,Cache,块中的数据是正确的、共享存储器中的数据是过时的。仅当需要替换该,Cache,块时，将该,Cache,块写回共享存储器,。,MESI,协议用,协议中用到的四种状态的首字母,(M,，,E,，,S,和,I),命名。,2,）写更新和写作废协议性能上的差别主要来自：,在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。,在对同一,Cache,块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。,写作废是针对,Cache,块进行操作，而写更新则是针对字（或字节）进行。,考虑从一个处理器,A,进行写操作后到另一个处理器,B,能读到该写入数据之间的延迟时间，写更新协议的延迟时间较小。,3,）监听协议的实现,监听协议的基本实现技术有,3,个方面：,处理器之间通过一个可以实现广播的互连机制相连，通常采用的是总线。,Cache,发送到总线上的消息主要有以下两种：,RdMiss,读不命中,WtMiss,写不命中,块的拥有者：拥有该数据块的唯一副本的处理器。,（,2,）目录表法（,Directory Scheme,）,在,目录协议中，存储块的状态有,3,种：,未缓冲：该块尚未被调入,Cache,。所有处理器的,Cache,中都没有这个块的副本。,共享：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同。,独占：仅有一个处理机有这个块的,副本。,有,三种目录表：,全幅目录表法（全映象目录）,有限目录表法（有限映象目录）,链接目录表法（链式目录）,链式目录有两种实现方法：单链法,、,双链法,（,3,）以软件为基础的办法,靠软件的作用来限制一些公用的可写数据存放到,Cache,中。在编译时，通过编译程序分析，把数据分为能用,Cache,的（,Cacheable,）和不能用,Cache,的（,nonCacheable,）两部分，不能用,Cache,的数据只能存在主存中。,7.3.5,多处理机的同步,1,基本硬件原语,原子,交换（,atomic exchange,），将一个存储单元的值和一个寄存器的值进行交换。,建立一个锁：锁值,0,表示开的（可用），锁值,1,表示已上锁（不可用）,。,测试并,置,数,（,test_and_set,）：先测试一个存储单元的值，如果符合条件则修改其值。,读取并加,1,（,fetch_and_increment,）：它返回存储单元的值并自动增加该值,。,使用指令对,LL(load linked,或,load locked),的取指令，,SC(store conditional),的特殊存指令。,指令顺序执行：,SC,将返回一个值来指出该指令操作是否成功：,“1”,：成功；,“0”,：不成功。,LL,则返回该存储单元初始值。,2,用一致性实现旋转锁,采用多处理机的一致性机制来实现旋转锁。所谓,旋转锁，处理器环绕一个锁不停地旋转而请求获得该锁,。,（,1,）无,Cache,一致性机制,在,存储器中保存锁变量，处理器可以不断地通过一个原子操作请求使用权。比如：利用原子交换操作，并通过测试返回值而知道锁的使用情况。释放锁的时候，处理器只需简单地将锁置为,0,。,（,2,）机器支持,Cache,一致性,基于访问锁时的局部性原理，即处理器最近使用过的锁在不久的将来又会再次被使用。本方法将锁调入,Cache,，采用一致性机制保持锁值，减少获锁耗费的时间。在请求占用锁时，环绕进程不用每次都访问一次全局存储器，而只操作本地,Cache,中的锁,(,副本,),。,改进旋转锁，只读取和检测本地,Cache,中锁的副本，直到该锁已被释放为止。之后该处理器进行原子交换，与其他处理器竞争该锁变量。,3,同步性能问题,简单旋转锁可扩展性较差，很少用于大规模多处理机中。因为若大量处理机同时争用同一个锁，争用和通信开销非常大,。,7.3.6,多处理机实例,1,超级计算与,Cray1,超级计算,（,Supercomputing,）是计算数学的重要概念，指超级计算机及有效应用的总称,。高性能,计算（,High Performance Computing,，,HPC,）也可从,1972,年有开创性意义的并行计算机,ILI_IAC N,问世算起，这一领域发展异常迅速,。,图,7.26 Cray 1,号,2,多核多处理器,SUN T1,2006,年,3,月，,Sun,宣布开源化其多核心,Ultra Sparc T1,的处理器设计，,每个,T1,处理器中有,8,个处理器核，每个核最多支持,4,个线程。每个处理器核中都有一条,6,段的单流出流水线，类似于前面介绍的,5,段流水线，只是增加了一个段，用于进行线程切换。,3,多处理机,Origin 2000,Origin,2000,系统的可扩放性体系结构最多可以扩展至,1024,个处理器，而且规模增加可使系统性能也呈线性增长，包括计算能力、主存容量和带宽、系统互连带宽、,I/O,带宽和网络连接能力。通过,CrayLink,，分布在所有处理器结点上的存储器在逻辑上形成单一寻址空间的共享存储器系统，但对本地和远程存储器访问的时间是不同的，是一个,NUMA,结构,。,4,中国的超级计算机,我国,的超级计算机研制起步于,60,年代,。经过,几十年不懈地努力，我国的超级计算机系统研制已取得了丰硕成果，“银河”、“曙光”、“神威”、“深腾”等一批国产高端计算机系统的出现，使我国成为继美国、日本之后，第三个具备研制高端计算机系统能力的国家。,7.4.1,多处理机操作系统,多处理机操作系统,的功能：,进程管理,存储器管理,文件管理,系统重构和迁移,多处理机操作系统的类型：,（,1,）主从型,Master-Slave Configuration,）,（,2,）独立监督式（,Separate Supervisor,）,（,3,）浮动监督式（,Floating Supervisor,）,7.4,多处理机操作系统和算法,7.4.2,并行处理机算法,（,1,）矩阵加,矩阵,加,(,配比加,),是最简单的情况。假定两个,8*8,的矩阵,A,，,B,，相加，所得结果矩阵,C,也是一个,8*8,的矩阵。设,A,，,B,的分量元素分别存在,PEM i,的,Z,，,Z+1,单元中，所得结果矩阵,C,各分量存在,PEM i,的,Z+2,单元中。,用,下面三条指令可一次完成,(64,个处理单元并行,),：,LDA,Z,；,全部（,Z,）由,PEMi,送到,PE,的累加器,RGAi,ADRN,Z+1,；,全部（,Z+1,）与（,RGAi,）进行,浮点,；,规,舍加结果送,RGAi,STA,Z+2,；,全部（,RGAi,）由,PE,送,到,；DEMi,的（,Z+2,）单元,这里,0 i 63,（,2,）矩阵乘,矩阵乘是涉及二维数组运算。它比矩阵加复杂的多。设,A,，,B,和,C,为,3,个,8*8,的二维矩阵。若给定,A,和,B,，则为计算,C=A*B,的,64,个分量，可用下列公式：,（,7.7,）,其中,0i7,，,0j7,。,7.5.1,计算机网络,7.5,从计算机到网络,1969,年，,美国国防部远景研究规划局,(Advanced,Research Projects,Agency,ARPA),创建,了第一个分组交换网,ARPAnet,。,1983,年，,TCP/IP,协议成为,ARPAnet,的标准协议。同年，,ARPAnet,分解成两个网络，科研网,ARPAnet,，军用网,MILnet,。,7.5.2,物联网,（,1,）,RFID,技术,（,2,）传感器技术,（,3,）人工智能,技术,一般来说，射频识别系统包含射频标签,(Tag),、读写器,(Reader),和数据管理系统三部分。,7.5.3,无线传感器网络,无线,传感器网络（,Wireless Sensor Networks,，,WSN,）是一种分布式传感网络，它的末梢是可以感知和检查外部世界的传感器,。,WSN,中的传感器通过无线方式通信，因此网络设置灵活，设备位置可以随时更改，还可以跟互联网进行有线或无线方式的连接。通过无线通信方式形成的一个,多跳自组织网络,。,7.5.4,网格计算,网格,计算（,Grid Computing,），网格计算即分布式计算，是一门计算机科学,。它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分。,7.5.5,云计算,云计算（,Cloud Computing,）是基于互联网的相关服务的增加、使用和交付模式，通常涉及通过互联网来提供动态易扩展且经常是虚拟化的资源。云计算可以认为包括以下几个层次的服务：基础设施即服务（,IaaS,），平台即服务（,PaaS,）和软件即服务（,SaaS,）。,7.6.1,普适计算,普适计算又称普存计算、普及计算（,Pervasive Computing,或者,Ubiquitous Computing,）强调和环境融为一体的计算，而计算机本身则从人们的视线里消失。,7.6,普适计算和移动计算,7.6.2,分布式计算,分布式处理,则是将不同地点的，或具有不同功能的，或拥有不同数据的多台计算机通过通信网络连接起来，在控制系统的统一管理控制下，协调地完成大规模信息处理任务的计算机系统,。,7.6.3,移动计算和超移动,计算,7.6.4,迅驰技术,迅驰移动是,Intel,于,2003,年,3,月,12,日，面向笔记本电脑推出的无线移动计算技术的品牌名称。迅驰（,Centrino,）：,Centre(,中心）与,Neutrino,（中微子）两个单词的缩写。它由三部分组成：移动式处理器（,CPU,）、相关芯片组以及,802.11,无线网络功能模块。,移动计算（,Mobile Computing,）是随着移动通信、互联网、数据库、分布式计算等技术的发展而兴起的新技术。移动计算技术将使计算机或其它信息智能终端设备在无线环境下实现数据传输及资源共享。,7.6.5,智能手机,智能手机硬件主要有三大部分组成：通信子系统、应用子系统和电源管理子系统。总体来讲是以应用子系统为核心，通信子系统主要管理语音与数据通信。电源管理子系统保证可靠供电。,7.6.6,笔记本电脑,/,平板电脑,笔记本电脑又被称为,“,便携式电脑,”,，其最大的特点就是机身小巧，相比,PC,携带方便。,平板电脑（,Tablet Personal Computer,，简称,Tablet PC,、,Flat PC,、,Tablet,、,Slates,），是一种小型、方便携带的个人电脑，以触摸屏作为基本的输入设备。,7.6.7 PDA,智能终端,PDA,智能终端又称为掌上电脑，可以帮助我们完成在移动中工作，学习，娱乐等。按使用来分类，分为工业级,PDA,和消费品,PDA,。,7.6.8,车载智能终端,智能车载终端（又称卫星定位智能车载终端）融合了,GPS,技术、里程定位技术及汽车黑匣技术，能用于对运输车辆的现代化管理。,习题,7,7.1，7.2，7.3，7.4，7.5，7.6,，,7.7,，7.8,Thank you!,