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

1多核程序设计第二章并行计算基础2008年8月18日浙江大学英特尔技术中心§并行处理技术2.0.1并行性概念一、并行技术定义开发计算过程中并行事件的处理方法事件的并行性结构的并行性二、并行性含义同时性：两个或两个以上事件在同一时刻发生并发性：两个或两个以上事件在同一时间间隔发生流水线：两个或两个以上事件在可能重叠的时间段内2.0并行处理技术概述浙江大学英特尔技术中心§并行处理技术2.0.2并行性的层次一、程序执行的并行性指令内部并行：微操作并行指令间并行：多条指令并行任务或进程间并行：任务作并行性分解作业或程序间并行：资源的并行性分配算法二、数据处理的并行性位串字串：一次只对一个字的一位进行处理——无并行位并字串：一次对多个字的一位进行处理——W=1，B＞1位串字并：一次对一个字的多位进行处理——W＞1，B=1位并字并：一次对许多字的多位进行处理——W＞1，B＞1三、操作并行性的层次存储器操作并行：在一个存贮周期内访问多个存贮单元处理器操作步骤并行：指令执行子操作重叠处理器操作并行：多处理单元(多核)，在同一控制器控制下按同一条指令对多个数据组同时操作（多SIMD核）并行度增加通信与调度开销增加硬件实现的比例增加浙江大学英特尔技术中心§并行处理技术2.0.3并行性措施及困难一、并行性措施时间重叠：时间上错开，轮流重叠使用硬件：如流水线资源重复：空间重叠，以量取胜资源共享：多用户按时间顺序轮流使用同一套资源：如分时系统二、并行性困难任务分配非常困难可并行性：任务的并行性划分和分发算法对并行性的限制算法不仅与问题有关，还与硬件有关处理机之间的通信开销限制当通信开销大时并行处理技术得不偿失并行处理环境可编程性并行开发环境需要并行编译和并行操作系统支持并行规模的确定可扩展性浙江大学英特尔技术中心多处理器互联方式通信网络是多处理机性能发挥的瓶颈主要方式：总线、交叉开关、多端口存贮器、开关枢纽网络参数节点度（NodeDegree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（NetworkDiameter）：网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（BisectionWidth）：对分网络各半所必须移去的最少边数对剖带宽（BisectionBandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称为对称的（Symmetry）浙江大学英特尔技术中心静态互连网络与动态互连网络静态互连网络处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。浙江大学英特尔技术中心静态互连网络----一维线性阵列1-DLinearArray并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为N-1（单向环），对剖宽度为2浙江大学英特尔技术中心静态互连网络----二维网孔N×N二维网孔（2-DMesh）每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为2N-1，对剖宽度为N在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为N-1，而对剖宽度为2N垂直和水平方向均带环绕，则变成了2-D环绕（2-DTorus），节点度恒为4，网络直径为2[N/2]，对剖宽度为2N(a)2-D网孔(b)Illiac网孔(c)2-D环绕浙江大学英特尔技术中心静态互连网络----二叉树二叉树除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。(a)二叉树(b)星形连接(c)二叉胖树浙江大学英特尔技术中心静态互连网络----超立方超立方一个n-立方由N=2n个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n，而对剖宽度为N/2。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。(b)4-立方(a)3-立方(c)顶点代之以环(d)3-立方环浙江大学英特尔技术中心动态互连网络---总线PCI、VME、Multics、Sbus、MicroChannel多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等LMIOC本地总线高速缓存CPUIFIFIF存储器总线存储器单元IFIFCPU板存储器板I/O板通信板系统总线(底板上)数据总线缓冲CCIOP数据总线网络(以太网等)磁盘和磁带部件打印机或绘图仪本地外围设备(SCSI总线)MCIF缓冲浙江大学英特尔技术中心动态互连网络---交叉开关（Crossbar）单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。浙江大学英特尔技术中心单级交叉开关级联构成多级互连网络MIN（MultistageInterconnectionNetwork）0101010101010101(a)4种可能的开关连接000001010011100101110111输入000001010011100101110111输出第0级第1级第2级(b)一种8输入的Omega网络浙江大学英特尔技术中心并行计算机体系结构并行计算机组成的各个部分：节点（node）互联网络（interconnectnetwork）内存（memory）内存模块与节点分离内存模块位于节点内部浙江大学英特尔技术中心并行处理机的结构四种体系结构SISD(SingleInstructionSingleData)--UniprocessorsMISD(MultipleInstructionSingleData)???;multipleprocessorsonasingledatastreamSIMD(SingleInstructionMultipleData)Examples:connectionmachine2：65535个1bitprocessors;IlliacIV：64个64bitprocessors;Ad:Simpleprogrammingmodel;Lowoverhead;Flexibility;Allcustomintegratedcircuits(PhrasereusedbyIntelmarketingformediainstructions~vector)MIMD(MultipleInstructionMultipleData)Examples:SunEnterprise5000,CrayT3D,SGIOriginAd:Flexible;Useoff-the-shelfmicros;Multiprocessors,MulticomputersMIMDcurrentwinner:Concentrateonmajordesignemphasis=128processorMIMDmachines浙江大学英特尔技术中心并行处理机的结构多个处理节点通过互连网络联接互连网络节点1节点2节点3节点4…………节点n节点i浙江大学英特尔技术中心结构CenteronorganizationofmainmemorySharedvs.DistributedAppearanceofmemorytohardwareQ1:Memoryaccesslatencyuniform?Shared(UMA):yes,doesn’tmatterwheredatagoesDistributed(NUMA):no,makesabigdifferenceAppearanceofmemorytosoftwareQ2:Canprocessorscommunicatedirectlyviamemory?Shared(sharedmemory):yes,communicateviaload/storeDistributed(messagepassing):no,communicateviamessagesDimensionsareorthogonale.g.DSM:(physically)distributed,(logically)sharedmemory浙江大学英特尔技术中心集中共享存储多处理机系统CentralizedShared-MemoryArchitectureMainmemoryI/O系统ProcessorOneormorelevelsofcacheProcessorOneormorelevelsofcacheProcessorOneormorelevelsofcacheProcessorOneormorelevelsofcache总线结构SMP浙江大学英特尔技术中心典型MIMD----分布存储多处理机系统Structureofdistributed-memorymultiprocessor互连网络浙江大学英特尔技术中心片上多处理器系统Intel®Core®Micro-architecture2M/4MsharedL2Cacheupto10.4