单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 并行计算机系统,第一节 并行计算机系统的分类,第二节 共享存储器系统,第三节 消息传递型系统,第一节 并行计算机系统分类,向量机系统,流水式向量机系统,阵列式向量机系统,多处理机系统,共享存储器型,消息传递型,并行性的层次,操作级,流水,数据并行,指令级,相关性分析,指令调度,循环级,展开,推测执行,路径调度,线程级,并行多线程、多核与多处理器,数据缓存的一致性,同步与互斥的有效性,系统结构分类,Flyn,分类,向量流水,部件级流水,一条指令完成大量计算,对应于一个循环,每个数据元素的计算与其他数据元素无关,适合于深度流水,访存按一定模式,一次访问大量数据,向量流水计算机,向量指令,向量-向量指令,ADDV V1,V2,V3,向量-标量指令,ADDV V1,F2,V3,向量-存储器指令,LV V1,R1,向量归约指令,MAX F0,V1,收集-扩展指令,（,Gather-Scatter）,屏蔽指令,SENSV F0,V1,向量流水计算机的例子,Cray-1,阵列并行计算机系统,基本结构,分布式存储器,集中式存储器,运行方式,用一条指令同时对许多运算单元中的数据进行运算,基本构成,控制单元,CU,执行串行指令，并行指令广播各个,PE；,处理单元,PE,以同步方式执行指令,存储器模块,互连网络,IN,集中式控制，并行电路交换,阵列并行指令,向量运算，数据寻径，屏蔽操作,阵列并行计算机系统,阵列并行计算机系统,特点,专用,应用算法相关,适合于规则数据运算,不适合于条件分支程序,发展缓慢的原因,指令广播瓶颈,数据归约相关性,存储器速度难以提高,阵列机的程序设计,例：64个,PE,的阵列机中进行64000个数据的累加。
第一步，64个子集数据分配，数据,A,分配后的每个子集为,A1第二步，求部分累加和：,sum=0;,for(i=0;i=half,if(Pn1);,/*exit with final sum */,多处理机系统结构,多处理机系统的结构分类,UMA,tightly coupled,SMP,symmetrical multiprocessor,non SMP,NUMA,DSM,MPP,loosely coupled,UMA,Uniform memory access,可编程性,兼容性,简单的程序设计模型,通信开销小,可扩展性,共享存储器结构使得存储器成为瓶颈,访存速度要求,每个数据都来自共享的存储器,UMA,的实现,集中式存储器,问题,访存冲突,网络带宽,解决方案,多体交叉,本地指令存储器,本地,cache,NUMA,DSM,distributed shared memory,用硬件机制将分布的存储器构成一个逻辑上统一的共享存储器,cache,及其一致性问题,CC-NUMA,cache coherent NUMA,COMA,cache only memory access,MPP,massively parallel processors,大规模并行处理机系统,消息传递,显式数据交换,程序设计较难,NUMA,的实现,分布式存储器,本地存储器延迟较小,扩展性较好,性价比高,数据一致性问题,编程复杂,DSM,的结点,CC-NUMA,本地,cache,失效时数据将根据地址从本地存储器中或者远程存储器访问,Cache,命中率低,COMA,增加每个数据块的命中标志信息和状态信息,数据块可迁移,多处理机系统的结构分类,按硬件层次,芯片级,芯片多处理器,CMP,板级,多,CPU,芯片主板,机架级,网络级,网格,Bus,2 MB L2 Cache,Core1,Core2,芯片级并行性,特点,独立的控制流,分离的内部状态,没有共享的功能部件,分类,同构多核,Core 2 Duo,异构多核,Cell,处理器,网络处理器,EXE Core,FP Unit,EXE Core,FP Unit,L2 Cache,L1 Cache,L1 Cache,System Bus,(667MHz,5333MB/s),Intel Core 2 Duo,Xeon,Core 2,Dual Core Server Processor Evolution,Core 2 Processor Block Diagram,系统总线,指令预取,/,预译码,指令队列,L2 Cache,和控制,指令译码,微码,ROM,寄存器更名分配,调度器,FPU,ROB,ALU,ALU,ALU,LD,ST,L1 D-cache,和,D-TLB,指令预取,/,预译码,指令队列,指令译码,微码,ROM,ROB,寄存器更名分配,调度器,ST,LD,ALU,ALU,ALU,FPU,L1 D-cache,和,D-TLB,Intel Quad-core,Intel Core 2 Extreme,Intel Flash,Intels,tera,-scale chip,Cell,Sony-IBM,网络处理器（,IXP2400,）,多处理机系统的性能,执行时间,串行执行时间,+,并行执行时间,+,通信时间,加速比,处理机数,例,8-1,1,个计算任务在单个核的计算机上运行的启动时间为,1,秒，运算时间为,10,秒，数据结果汇总的时间为,1,秒。
如果将该计算任务放在多核处理器的计算机上运行，将运算部分分解成多个线程并行执行1,）假如任务的启动和数据汇总操作不能并行执行，任务之间的通信量可以忽略，问在核的数量分别为,2,、,4,、,8,、,16,时的任务执行时间和加速比2,）上述情况下，假如每两个处理器核之间的通信时间为,0.1,秒，每对处理器核的通信串行进行，问在核的数量分别为,2,、,4,、,8,、,16,时的任务执行时间和加速比解,（,1,）,任务在单个核的计算机上运行时间为,12,秒；,在双核计算机上的运行时间为,1+10/2+1=7,秒，,加速比为,12/7=1.71,；,在,4,核计算机上的运行时间为,1+10/4+1=4.5,秒，,加速比为,12/4.5=2.67,；,在,8,核计算机上的运行时间为,1+10/8+1=3.25,秒，,加速比为,12/3.25=3.69,；,在,16,核计算机上的运行时间为,1+10/16+1=2.63,秒，,加速比为,12/2.63=4.56,解（,2,）,任务在单个核的计算机上没有通信时间，,运行时间为,12,秒；,在双核计算机上的通信时间为,1,0.1,，,运行时间为,1+10/2+1+0.1=7.1,秒，加速比为,12/7.1=1.69,；,在,4,核计算机上的通信时间为,6,0.1=0.6,，,运行时间为,1+10/4+1+0.6=5.1,秒，加速比为,12/5.1=2.35,；,在,8,核计算机上的通信时间为,28,0.1=2.8,，,运行时间为,1+10/8+1+2.8=6.05,秒，加速比为,12/6.05=1.98,；,在,16,核计算机上的通信时间为,120,0.1=12,，,运行时间为,1+10/16+1+12=14.63,秒，加速比为,12/14.63=0.82,，,即比单核计算机的计算时间更长,如果采用并行通信？,处理器芯片的性能障碍,访存,Memory wall,功耗,散热问题,移动计算机的电池问题,主频,长流水线,功耗,第二节 共享存储器多处理机系统,多核处理器系统,系统中包含一个多核的处理器芯片,每个处理器核能够独立运行程序,单核多处理器系统,多个单核的处理器构成的系统,处理器之间的通信延迟时间较长,多核多处理器系统,多个多核处理器构成的并行系统,两个并行处理的层次,多处理机系统的结构分类,按程序特征,MIMD,SPMD,代替,SIMD,按处理机特征,同构,homogenius,异构,heterogenius,核,独立的指令执行和控制单元,独立的功能部件,独立的控制器,完整的指令流水线,独立的或者共享的,cache,单线程或,SMT,多核处理器分类,单核多线程处理器,单核,CPU,构成,多核处理器,多核芯片构成,多核多线程处理器,每个核都是多线程的,多核处理器的分类,CU:CPU state+Interrupt logic,CU,Cache,EU,CU,Cache,EU,CU,CU,Cache,EU,CU,EU,Cache,CU,Cache,EU,CU,CU,EU,CU,Cache,单核单线程处理器,单核多线程处理器,多核处理器,多核多线程处理器,多核处理机,单芯片多处理器,CMP,均匀,cache,访问,UCA,非均匀,cache,访问,NUCA,CU,EU,CU,EU,Cache,CU,EU,CU,EU,共享存储器,单核多处理机系统,CU,Cache,EU,CU,Cache,EU,共享存储器,CU,Cache,EU,互连网络,多核多处理机系统,CU,EU,CU,EU,Cache,CU,EU,CU,EU,CU,EU,CU,EU,Cache,CU,EU,CU,EU,CU,EU,CU,EU,Cache,CU,EU,CU,EU,CU,EU,CU,EU,Cache,CU,EU,CU,EU,共享存储器,互连网络,多处理机系统的构成,多核,共享,cache,多芯片,共享存储器,多板卡,共享存储器,消息传递,多机架,消息传递,网络通信,网格,网络通信,Web,服务,核,核,核,核,多芯片多核处理机,一块主板上集成多个多核芯片,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,多板卡多处理机,多芯片板卡,多核芯片,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,多机架多处理机,多板卡机架,多芯片板卡,多核芯片,超级计算机,多核面临的挑战,片内互连网络,UCA,NUCA,大容量多端口的共享,cache,难以实现,UCA,访存瓶颈,高效同步机制,虚拟化,多核处理器的发展,多核处理器的发展,3,维堆叠芯片,多处理机中的虚拟机,应用级,操作系统级,硬件平台级,固件级,CU,Cache,EU,CU,CU,EU,CU,Cache,虚拟机,1,虚拟机,2,虚拟机,3,虚拟机,4,虚拟机,5,多处理机中的虚拟机,Intra Core,Inter Core,Inter Board,Inter Rack,Grid,Virtualization of distributed processors,共享存储器系统程序设计例子,8个处理机，单总线连接,sumPn=0;,for(i=8000*Pn;i8000*(Pn+1);i=i+1),sumPn=sumPn+Ai;,/*sum the assigned areas */,half=8;,/*8 processors in single-bus MIMD */,do,synch();/*wait for completion of partial sums */,half=half/2;,/*dividing line on two sums */,if(Pn1);/*exit with final sum in sum0 */,其中,synch(),函数是一个屏障同步函数。
练习：多线程程序设计,在,4,个处理器核的计算机中执行下列循环程序，试改写这个程序，将其分成多个线程以提高执行速度for(i=0;i,numPixels,;i+),pGrayScalBitmapi,=(unsigned BYTE),(,pRGBBitmapi.red,*0.299+,pRGBBitmapi.green,*0.587+,pRGBBitmapi.blue,*0.114);,线程的同步问题,共享数据的读写相关性,如上述例子中的部分和的读写操作,共享数据的写写相关性,数据竞争,同步,给线程执。
