1、1,多核程序设计第二章 并行计算基础,2008年8月18日,1,2,并行处理技术,2.0.1并行性概念 一、并行技术定义开发计算过程中并行事件的处理方法事件的并行性结构的并行性二、并行性含义同时性：两个或两个以上事件在同一时刻发生并发性：两个或两个以上事件在同一时间间隔发生流水线：两个或两个以上事件在可能重叠的时间段内,2.0 并行处理技术概述,2,3,并行处理技术,2.0.2 并行性的层次 一、程序执行的并行性指令内部并行：微操作并行指令间并行：多条指令并行任务或进程间并行：任务作并行性分解作业或程序间并行：资源的并行性分配算法二、数据处理的并行性位串字串：一次只对一个字的一位进行处理无并行
2、 位并字串：一次对多个字的一位进行处理W=1，B1位串字并：一次对一个字的多位进行处理W1，B=1位并字并：一次对许多字的多位进行处理W 1，B 1三、操作并行性的层次存储器操作并行：在一个存贮周期内访问多个存贮单元处理器操作步骤并行：指令执行子操作重叠处理器操作并行：多处理单元(多核)，在同一控制器控制下按同一条指令对多个数据组同时操作（多SIMD核）,并行度增加通信与调度开销增加硬件实现的比例增加,3,4,并行处理技术,2.0.3 并行性措施及困难一、并行性措施时间重叠：时间上错开，轮流重叠使用硬件：如流水线资源重复：空间重叠，以量取胜资源共享：多用户按时间顺序轮流使用同一套资源：如分时系
3、统二、并行性困难任务分配非常困难可并行性：任务的并行性划分和分发算法对并行性的限制算法不仅与问题有关，还与硬件有关处理机之间的通信开销限制当通信开销大时并行处理技术得不偿失并行处理环境可编程性并行开发环境需要并行编译和并行操作系统支持并行规模的确定可扩展性,4,5,2.0.5 多处理器互联方式,通信网络是多处理机性能发挥的瓶颈主要方式：总线、交叉开关、多端口存贮器、开关枢纽网络参数节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（Network Diameter）：网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（Bisec
4、tion Width）：对分网络各半所必须移去的最少边数对剖带宽（Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称为对称的（Symmetry）,5,6,静态互连网络与动态互连网络,静态互连网络处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。,6,7,静态互连网络-一维线性阵
5、列,1-D Linear Array并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为N-1（单向环），对剖宽度为2,7,8,静态互连网络-二维网孔,NN二维网孔（2-D Mesh）每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为 2N-1，对剖宽度为N 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为N-1，而
6、对剖宽度为2N 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus），节点度恒为4，网络直径为2N/2，对剖宽度为2N,8,9,静态互连网络-二叉树,二叉树除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为 如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。,9,10,静态互连网络-超立方,超立方 一个n-立方由N=2n 个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径
7、也是n，而对剖宽度为N/2。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。,10,11,动态互连网络-总线,PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等,11,12,动态互连网络-交叉开关（Crossbar）,单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般
8、有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。,12,13,单级交叉开关级联构成多级互连网络,MIN（Multistage Interconnection Network）,13,14,2.1并行计算机体系结构,并行计算机组成的各个部分：节点（node）互联网络（interconnect network）内存（memory）,内存模块与节点分离,内存模块位于节点内部,14,15,2.1.0 并行处理机的结构,四种体系结构SISD(Single Instruction Single Data)-Uni
9、processorsMISD(Multiple Instruction Single Data)?;multiple processors on a single data streamSIMD(Single Instruction Multiple Data)Examples:connection machine 2：65535个 1bit processors;Illiac IV：64个 64bit processors;Ad:Simple programming model;Low overhead;Flexibility;All custom integrated circuits(P
10、hrase reused by Intel marketing for media instructions vector)MIMD(Multiple Instruction Multiple Data)Examples:Sun Enterprise 5000,Cray T3D,SGI OriginAd:Flexible;Use off-the-shelf micros;Multiprocessors,MulticomputersMIMD current winner:Concentrate on major design emphasis=128 processor MIMD machine
11、s,15,16,并行处理机的结构,多个处理节点通过互连网络联接,16,17,MIMD结构,Center on organization of main memoryShared vs.DistributedAppearance of memory to hardwareQ1:Memory access latency uniform?Shared(UMA):yes,doesnt matter where data goesDistributed(NUMA):no,makes a big differenceAppearance of memory to softwareQ2:Can proce
12、ssors communicate directly via memory?Shared(shared memory):yes,communicate via load/storeDistributed(message passing):no,communicate via messagesDimensions are orthogonale.g.DSM:(physically)distributed,(logically)shared memory,17,18,典型MIMD-集中共享存储多处理机系统,Centralized Shared-Memory Architecture,总线结构,SM
13、P,18,19,典型MIMD-分布存储多处理机系统,Structure of distributed-memory multiprocessor,互连网络,19,20,典型MIMD-片上多处理器系统,Intel Core Micro-architecture,CPU1,Memory,CPU2,Cache Line,Front Side Bus(FSB),L2 is shared:No need to ship cache line,20,21,Intel Core微架构,21,22,IBM PowerPC CEll,IBM 架构核心的3.2 GHz Cell处理器，包括8个协同处理器(SPE)
14、，除1个SPE保留用做其它用途，其余7个SPE均以3.2 GHz频率运做，内建512 KB二级缓存，浮点性能最高可达218 GFLOPS,22,23,二种常见的分布存储多处理机系统,Distributed shared memory（DSM or scalable shared memory)统一的逻辑地址空间，但物理空间是分布的每个处理器可以通过逻辑Shared memory means sharing the address space,which is different from centralized shared memory.multiple computers Address
15、space consists of multiple private address spaces。逻辑上不连续，远程处理器无法访问。每一结点（processor-memory）模块是一单独的计算机，故称为多计算机结构。NOW计划，每一结点实质上是一工作站或PC，由LAN连接而成。,23,24,UMA vs.NUMA,UMA:uniform memory accessFrom p0 same latency to m0-m3Data placement doesnt matterLatency worse as system scalesInterconnect contention rest
16、ricts bandwidthSmall multiprocessors onlyNUMA:non-uniform memory accessFrom p0 faster to m0 than m1-m3Low latency to local memory helps performanceData placement important(software!)Less contention=more scalableLarge multiprocessor systems,24,25,2.1.1 多级存储体系结构,为了解决处理器与内存之间的性能/成本瓶颈问题。理论依据：局部性原理目前有多级C
17、ache在节点内部的cache称为二级cache（L2 cache）。在处理器内部更小的cache成为一级cache（L1 cache）。,25,26,多级存储体系结构-2,Cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。直接映射策略（direct mapping strategy）每个内存块只能被唯一的映射到一条cache线中K路组关联映射策略（K-way set association mapping strategy）Cache被分解为若干个组，每个组由K个Block组成，组直接映射，组内映射到任意Block全关联映射策略（full association map
18、ping strategy）内存块可以被映射到Cache中的任意一个Block,26,27,多级存储体系结构-3,Cache hit时的写策略write-through写命中时同时修改主存（外层存储器）始终保证数据一致：存贮器或其它处理器始终有最新数据控制位：valid影响性能：可以用Write buffers 提高性能write-back cache 写命中时不修改主存（外层存储器），数据块退出Cache时一次修改数据存在不一致性：存贮器或其它处理器始终有最新数据控制位：valid、dirty 存储器带宽要求较低,27,28,多级存储体系结构-4,Cache miss时的写策略Write a
19、llocate 数据块调入Cache，再写大Block时影响性能，但可提高命中率与write-through结合Write around(no write allocate)数据块直接写入主存大Block时写性能较好下次访问还是miss与write-Back结合,28,29,程序结构与Cache效率-循环交换,每次访问间隔100个元素for(k=0;k 100;k=k+1)for(j=0;j 100;j=j+1)for(i=0;i 5000;i=i+1)xij=2*xij;连续访问100个元素for(k=0;k 100;k=k+1)for(i=0;i 5000;i=i+1)for(j=0;j
20、100;j=j+1)xij=2*xij;改善空间局部性提高命中率,j,i,29,30,程序结构与Cache效率-循环融合,访问a、c时2次missfor(i=0;i N;i=i+1)for(j=0;j N;j=j+1)aij=1/bij*cij;for(i=0;i N;i=i+1)for(j=0;j N;j=j+1)dij=aij+cij;访问a、c时1次missfor(i=0;i N;i=i+1)for(j=0;j N;j=j+1)aij=1/bij*cij;dij=aij+cij;改善空间局部性提高命中率,30,31,程序结构与Cache效率-数组融合,多个一维数组int valSIZE;
21、int keySIZE;一个结构数组struct merge int val;int key;struct merge merged_arraySIZE;改善空间局部性提高命中率,31,32,程序结构与Cache效率-矩阵分割,矩阵乘法for(i=0;i(assuming no conflict;otherwise)Idea:compute on BxB submatrix that fits,y1k,zkj,x1j,(N+N)N+N)N=2N3+N2Accessed For N3 operations,32,33,程序结构与Cache效率-矩阵分割-2,分块修改后for(jj=0;jj N;
22、jj=jj+B)for(kk=0;kk N;kk=kk+B)for(i=0;i N;i=i+1)for(j=jj;j min(jj+B-1,N);j=j+1)r=0;for(k=kk;k min(kk+B-1,N);k=k+1)r=r+yik*zkj;xij=xij+r;Y 改善空间局部性Z 改善时间局部性 减小容量Misses 2N3+N2 N3/B+2N2,(BN+BN)+B2)(N/B)2=2N3/B+N2Accessed For N3 operations,33,34,并行体系结构下的Cache一致性,34,35,写操作引起Cache不一致-Write back,35,36,写操作引起
23、Cache不一致-Write through,36,37,Cache一致性解决思想,No cachesNot likely Make shared data non-cacheableSimple software solutionlow performance if lots of shared dataSoftware flush at strategic timesRelatively simple,but could be costly(frequent syncs)Hardware cache coherenceMake memory and caches coherent/cons
24、istent witheach other,37,38,硬件Cache一致性协议,Snooping Solution(Snoopy Bus):Send all requests for data to all processorsProcessors snoop to see if they have a copy and respond accordingly Requires broadcast,since caching information is at processorsWorks well with bus(natural broadcast medium)Dominates f
25、or small scale machines(most of the market)Directory-Based Schemes(discuss later)Keep track of what is being shared in 1 centralized place(logically)Distributed memory=distributed directory for scalability(avoids bottlenecks)Send point-to-point requests to processors via networkScales better than Sn
26、oopingActually existed BEFORE Snooping-based schemes,38,39,硬件监听方案,39,40,基本监听协议,Write Invalidate Protocol:Multiple readers,single writerWrite to shared data:an invalidate is sent to all caches which snoop and invalidate any copiesRead Miss:Write-through:memory is always up-to-dateWrite-back:snoop in
27、caches to find most recent copyWrite Broadcast Protocol(typically write through):Write to shared data:broadcast on bus,processors snoop,and update any copiesRead miss:memory is always up-to-dateWrite serialization:bus serializes requests!Bus is single point of arbitration,40,41,写无效协议-write Back,大多数系
28、统常用的Broadcast address of cache line to invalidateAll processor snoop until they see it,then invalidate if in local cache,41,42,写更新协议(广播)-write Back,42,43,两种协议性能的定性对比,对同一字的多次写操作，多次写广播；（写更新）只要一次无效化操作；（写无效）(思考:为什么不是多次无效化操作?)Cache数据块由多字组成的话，对块中每一字进行写操作每次都要写广播；（写更新）(write merge)只在第一次写块中任一字时，需要产生一无效信号；（写无
29、效）从一个处理器写数到另一处理器读出写入的数的延时：写广播完成后，读命中；写无效化，读失配，stall直到得到返回值。,43,44,Snoopy ProtocolInvalidation protocol,write-back cache,Each block of memory is in one state:Clean in all caches and up-to-date in memory(Shared)OR Dirty in exactly one cache(Exclusive)OR Not in any cachesEach cache block is in one stat
30、e(track these):Shared:block can be readOR Exclusive:cache has only copy,its writeable,and dirtyOR Invalid:block contains no dataRead misses:cause all caches to snoop busWrites to clean line are treated as misses,44,45,一致性机制的请求和操作,45,46,监听无效协议-CPU请求 Block状态机,State machinefor CPU requestsfor each cach
31、e block,46,47,监听无效协议-总线请求 Block状态机,State machinefor bus requests for each cache block,47,48,监听无效协议状态机合并,48,49,Pentium-Pros cache coherence,Notes-Write Allocate-L1 can have data not in L2-HIT:someone has it clean-HITm:someone has it dirty,49,50,写无效化目录协议,Similar to Snoopy Protocol:Three statesShared:1
32、 processors have data,memory up-to-dateUncached(no processor hasit;not valid in any cache)Exclusive:1 processor(owner)has data;memory out-of-dateIn addition to cache state,must track which processors have data when in the shared state(usually bit vector,1 if processor has copy)Keep it simple(r):Writ
33、es to non-exclusive data=write missProcessor blocks until access completesAssume messages received and acted upon in order sent,50,51,无效化目录协议-2,没有总线，采用消息机制interconnect no longer single arbitration pointall messages have explicit responses3种节点Local node where a request originatesHome node where the memory location of an address residesRemote node has a copy of a cache block,whether exclusive or sha
