多核程序设计课件2并行计算基础.ppt

多核程序设计课件2并行计算基础.ppt

《多核程序设计课件2并行计算基础.ppt》由会员分享，可在线阅读，更多相关《多核程序设计课件2并行计算基础.ppt（134页珍藏版）》请在冰点文库上搜索。

1,多核程序设计第二章并行计算基础,2008年8月18日,1,2,并行处理技术,2.0.1并行性概念一、并行技术定义开发计算过程中并行事件的处理方法事件的并行性结构的并行性二、并行性含义同时性：

两个或两个以上事件在同一时刻发生并发性：

两个或两个以上事件在同一时间间隔发生流水线：

两个或两个以上事件在可能重叠的时间段内,2.0并行处理技术概述,2,3,并行处理技术,2.0.2并行性的层次一、程序执行的并行性指令内部并行：

微操作并行指令间并行：

多条指令并行任务或进程间并行：

任务作并行性分解作业或程序间并行：

资源的并行性分配算法二、数据处理的并行性位串字串：

一次只对一个字的一位进行处理无并行位并字串：

一次对多个字的一位进行处理W=1，B1位串字并：

一次对一个字的多位进行处理W1，B=1位并字并：

一次对许多字的多位进行处理W1，B1三、操作并行性的层次存储器操作并行：

在一个存贮周期内访问多个存贮单元处理器操作步骤并行：

指令执行子操作重叠处理器操作并行：

多处理单元（多核），在同一控制器控制下按同一条指令对多个数据组同时操作（多SIMD核）,并行度增加通信与调度开销增加硬件实现的比例增加,3,4,并行处理技术,2.0.3并行性措施及困难一、并行性措施时间重叠：

时间上错开，轮流重叠使用硬件：

如流水线资源重复：

空间重叠，以量取胜资源共享：

多用户按时间顺序轮流使用同一套资源：

如分时系统二、并行性困难任务分配非常困难可并行性：

任务的并行性划分和分发算法对并行性的限制算法不仅与问题有关，还与硬件有关处理机之间的通信开销限制当通信开销大时并行处理技术得不偿失并行处理环境可编程性并行开发环境需要并行编译和并行操作系统支持并行规模的确定可扩展性,4,5,2.0.5多处理器互联方式,通信网络是多处理机性能发挥的瓶颈主要方式：

总线、交叉开关、多端口存贮器、开关枢纽网络参数节点度（NodeDegree）：

射入或射出一个节点的边数。

在单向网络中，入射和出射边之和称为节点度。

网络直径（NetworkDiameter）：

网络中任何两个节点之间的最长距离，即最大路径数。

对剖宽度（BisectionWidth）：

对分网络各半所必须移去的最少边数对剖带宽（BisectionBandwidth）:

每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称为对称的（Symmetry）,5,6,静态互连网络与动态互连网络,静态互连网络处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：

用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。

6,7,静态互连网络-一维线性阵列,1-DLinearArray并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为N-1（单向环），对剖宽度为2,7,8,静态互连网络-二维网孔,NN二维网孔（2-DMesh）每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为2N-1，对剖宽度为N在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为N-1，而对剖宽度为2N垂直和水平方向均带环绕，则变成了2-D环绕（2-DTorus），节点度恒为4，网络直径为2N/2，对剖宽度为2N,8,9,静态互连网络-二叉树,二叉树除了根、叶节点，每个内节点只与其父节点和两个子节点相连。

节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。

胖树节点间的通路自叶向根逐渐变宽。

9,10,静态互连网络-超立方,超立方一个n-立方由N=2n个顶点组成，3-立方如图（a）所示；4-立方如图（b）所示，由两个3-立方的对应顶点连接而成。

n-立方的节点度为n，网络直径也是n，而对剖宽度为N/2。

如果将3-立方的每个顶点代之以一个环就构成了如图（d）所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。

10,11,动态互连网络-总线,PCI、VME、Multics、Sbus、MicroChannel多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等,11,12,动态互连网络-交叉开关（Crossbar）,单级交换网络，可为每个端口提供更高的带宽。

象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。

交叉开关一般有两种使用方式：

一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。

12,13,单级交叉开关级联构成多级互连网络,MIN（MultistageInterconnectionNetwork）,13,14,2.1并行计算机体系结构,并行计算机组成的各个部分：

节点（node）互联网络（interconnectnetwork）内存（memory）,内存模块与节点分离,内存模块位于节点内部,14,15,2.1.0并行处理机的结构,四种体系结构SISD（SingleInstructionSingleData）-UniprocessorsMISD（MultipleInstructionSingleData）?

;multipleprocessorsonasingledatastreamSIMD（SingleInstructionMultipleData）Examples:

connectionmachine2：

65535个1bitprocessors;IlliacIV：

64个64bitprocessors;Ad:

Simpleprogrammingmodel;Lowoverhead;Flexibility;Allcustomintegratedcircuits（PhrasereusedbyIntelmarketingformediainstructionsvector）MIMD（MultipleInstructionMultipleData）Examples:

SunEnterprise5000,CrayT3D,SGIOriginAd:

Flexible;Useoff-the-shelfmicros;Multiprocessors,MulticomputersMIMDcurrentwinner:

Concentrateonmajordesignemphasis=128processorMIMDmachines,15,16,并行处理机的结构,多个处理节点通过互连网络联接,16,17,MIMD结构,CenteronorganizationofmainmemorySharedvs.DistributedAppearanceofmemorytohardwareQ1:

Memoryaccesslatencyuniform?

Shared（UMA）:

yes,doesntmatterwheredatagoesDistributed（NUMA）:

no,makesabigdifferenceAppearanceofmemorytosoftwareQ2:

Canprocessorscommunicatedirectlyviamemory?

Shared（sharedmemory）:

yes,communicateviaload/storeDistributed（messagepassing）:

no,communicateviamessagesDimensionsareorthogonale.g.DSM:

（physically）distributed,（logically）sharedmemory,17,18,典型MIMD-集中共享存储多处理机系统,CentralizedShared-MemoryArchitecture,总线结构,SMP,18,19,典型MIMD-分布存储多处理机系统,Structureofdistributed-memorymultiprocessor,互连网络,19,20,典型MIMD-片上多处理器系统,IntelCoreMicro-architecture,CPU1,Memory,CPU2,CacheLine,FrontSideBus（FSB）,L2isshared:

Noneedtoshipcacheline,20,21,IntelCore微架构,21,22,IBMPowerPCCEll,IBM架构核心的3.2GHzCell处理器，包括8个协同处理器（SPE），除1个SPE保留用做其它用途，其余7个SPE均以3.2GHz频率运做，内建512KB二级缓存，浮点性能最高可达218GFLOPS,22,23,二种常见的分布存储多处理机系统,Distributedsharedmemory（DSMorscalablesharedmemory）统一的逻辑地址空间，但物理空间是分布的每个处理器可以通过逻辑Sharedmemorymeanssharingtheaddressspace,whichisdifferentfromcentralizedsharedmemory.multiplecomputersAddressspaceconsistsofmultipleprivateaddressspaces。

逻辑上不连续，远程处理器无法访问。

每一结点（processor-memory）模块是一单独的计算机，故称为多计算机结构。

NOW计划，每一结点实质上是一工作站或PC，由LAN连接而成。

23,24,UMAvs.NUMA,UMA:

uniformmemoryaccessFromp0samelatencytom0-m3DataplacementdoesntmatterLatencyworseassystemscalesInterconnectcontentionrestrictsbandwidthSmallmultiprocessorsonlyNUMA:

non-uniformmemoryaccessFromp0fastertom0thanm1-m3LowlatencytolocalmemoryhelpsperformanceDataplacementimportant（software!

）Lesscontention=morescalableLargemultiprocessorsystems,24,25,2.1.1多级存储体系结构,为了解决处理器与内存之间的性能/成本瓶颈问题。

理论依据：

局部性原理目前有多级Cache在节点内部的cache称为二级cache（L2cache）。

在处理器内部更小的cache成为一级cache（L1cache）。

25,26,多级存储体系结构-2,Cache的映射策略指的是内存块和cache线之间如何建立相互映射关系。

直接映射策略（directmappingstrategy）每个内存块只能被唯一的映射到一条cache线中K路组关联映射策略（K-waysetassociationmappingstrategy）Cache被分解为若干个组，每个组由K个Block组成，组直接映射，组内映射到任意Block全关联映射策略（fullassociationmappingstrategy）内存块可以被映射到Cache中的任意一个Block,26,27,多级存储体系结构-3,Cachehit时的写策略write-through写命中时同时修改主存（外层存储器）始终保证数据一致：

存贮器或其它处理器始终有最新数据控制位：

valid影响性能：

可以用Writebuffers提高性能write-backcache写命中时不修改主存（外层存储器），数据块退出Cache时一次修改数据存在不一致性：

存贮器或其它处理器始终有最新数据控制位：

valid、dirty存储器带宽要求较低,27,28,多级存储体系结构-4,Cachemiss时的写策略Writeallocate数据块调入Cache，再写大Block时影响性能，但可提高命中率与write-through结合Writearound（nowriteallocate）数据块直接写入主存大Block时写性能较好下次访问还是miss与write-Back结合,28,29,程序结构与Cache效率-循环交换,每次访问间隔100个元素for（k=0;k100;k=k+1）for（j=0;j100;j=j+1）for（i=0;i5000;i=i+1）xij=2*xij;连续访问100个元素for（k=0;k100;k=k+1）for（i=0;i5000;i=i+1）for（j=0;j100;j=j+1）xij=2*xij;改善空间局部性提高命中率,j,i,29,30,程序结构与Cache效率-循环融合,访问a、c时2次missfor（i=0;iN;i=i+1）for（j=0;jN;j=j+1）aij=1/bij*cij;for（i=0;iN;i=i+1）for（j=0;jN;j=j+1）dij=aij+cij;访问a、c时1次missfor（i=0;iN;i=i+1）for（j=0;jN;j=j+1）aij=1/bij*cij;dij=aij+cij;改善空间局部性提高命中率,30,31,程序结构与Cache效率-数组融合,多个一维数组intvalSIZE;intkeySIZE;一个结构数组structmergeintval;intkey;structmergemerged_arraySIZE;改善空间局部性提高命中率,31,32,程序结构与Cache效率-矩阵分割,矩阵乘法for（i=0;i（assumingnoconflict;otherwise）Idea:

computeonBxBsubmatrixthatfits,y1k,zkj,x1j,（N+N）N+N）N=2N3+N2AccessedForN3operations,32,33,程序结构与Cache效率-矩阵分割-2,分块修改后for（jj=0;jjN;jj=jj+B）for（kk=0;kkN;kk=kk+B）for（i=0;iN;i=i+1）for（j=jj;jmin（jj+B-1,N）;j=j+1）r=0;for（k=kk;kmin（kk+B-1,N）;k=k+1）r=r+yik*zkj;xij=xij+r;Y改善空间局部性Z改善时间局部性减小容量Misses2N3+N2N3/B+2N2,（BN+BN）+B2）（N/B）2=2N3/B+N2AccessedForN3operations,33,34,并行体系结构下的Cache一致性,34,35,写操作引起Cache不一致-Writeback,35,36,写操作引起Cache不一致-Writethrough,36,37,Cache一致性解决思想,NocachesNotlikelyMakeshareddatanon-cacheableSimplesoftwaresolutionlowperformanceiflotsofshareddataSoftwareflushatstrategictimesRelativelysimple,butcouldbecostly（frequentsyncs）HardwarecachecoherenceMakememoryandcachescoherent/consistentwitheachother,37,38,硬件Cache一致性协议,SnoopingSolution（SnoopyBus）:

SendallrequestsfordatatoallprocessorsProcessorssnooptoseeiftheyhaveacopyandrespondaccordinglyRequiresbroadcast,sincecachinginformationisatprocessorsWorkswellwithbus（naturalbroadcastmedium）Dominatesforsmallscalemachines（mostofthemarket）Directory-BasedSchemes（discusslater）Keeptrackofwhatisbeingsharedin1centralizedplace（logically）Distributedmemory=distributeddirectoryforscalability（avoidsbottlenecks）Sendpoint-to-pointrequeststoprocessorsvianetworkScalesbetterthanSnoopingActuallyexistedBEFORESnooping-basedschemes,38,39,硬件监听方案,39,40,基本监听协议,WriteInvalidateProtocol:

Multiplereaders,singlewriterWritetoshareddata:

aninvalidateissenttoallcacheswhichsnoopandinvalidateanycopiesReadMiss:

Write-through:

memoryisalwaysup-to-dateWrite-back:

snoopincachestofindmostrecentcopyWriteBroadcastProtocol（typicallywritethrough）:

Writetoshareddata:

broadcastonbus,processorssnoop,andupdateanycopiesReadmiss:

memoryisalwaysup-to-dateWriteserialization:

busserializesrequests!

Busissinglepointofarbitration,40,41,写无效协议-writeBack,大多数系统常用的BroadcastaddressofcachelinetoinvalidateAllprocessorsnoopuntiltheyseeit,theninvalidateifinlocalcache,41,42,写更新协议（广播）-writeBack,42,43,两种协议性能的定性对比,对同一字的多次写操作，多次写广播；（写更新）只要一次无效化操作；（写无效）（思考:

为什么不是多次无效化操作?

）Cache数据块由多字组成的话，对块中每一字进行写操作每次都要写广播；（写更新）（writemerge）只在第一次写块中任一字时，需要产生一无效信号；（写无效）从一个处理器写数到另一处理器读出写入的数的延时：

写广播完成后，读命中；写无效化，读失配，stall直到得到返回值。

43,44,SnoopyProtocolInvalidationprotocol,write-backcache,Eachblockofmemoryisinonestate:

Cleaninallcachesandup-to-dateinmemory（Shared）ORDirtyinexactlyonecache（Exclusive）ORNotinanycachesEachcacheblockisinonestate（trackthese）:

Shared:

blockcanbereadORExclusive:

cachehasonlycopy,itswriteable,anddirtyORInvalid:

blockcontainsnodataReadmisses:

causeallcachestosnoopbusWritestocleanlinearetreatedasmisses,44,45,一致性机制的请求和操作,45,46,监听无效协议-CPU请求Block状态机,StatemachineforCPUrequestsforeachcacheblock,46,47,监听无效协议-总线请求Block状态机,Statemachineforbusrequestsforeachcacheblock,47,48,监听无效协议状态机合并,48,49,Pentium-Proscachecoherence,Notes-WriteAllocate-L1canhavedatanotinL2-HIT:

someonehasitclean-HITm:

someonehasitdirty,49,50,写无效化目录协议,SimilartoSnoopyProtocol:

ThreestatesShared:

1processorshavedata,memoryup-to-dateUncached（noprocessorhasit;notvalidinanycache）Exclusive:

1processor（owner）hasdata;memoryout-of-dateInadditiontocachestate,musttrackwhichprocessorshavedatawheninthesharedstate（usuallybitvector,1ifprocessorhascopy）Keepitsimple（r）:

Writestonon-exclusivedata=writemissProcessorblocksuntilaccesscompletesAssumemessagesreceivedandacteduponinordersent,50,51,无效化目录协议-2,没有总线，采用消息机制interconnectnolongersinglearbitrationpointallmessageshaveexplicitresponses3种节点LocalnodewherearequestoriginatesHomenodewherethememorylocationofanaddressresidesRemotenodehasacopyofacacheblock,whetherexclusiveorsha