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

《多核程序设计课件2并行计算基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多核程序设计第二章并行计算基础2008年8月18日1§并行处理技术2.0.1并行性概念一、并行技术定义开发计算过程中并行事件的处理方法事件的并行性结构的并行性二、并行性含义同时性：两个或两个以上事件在同一时刻发生并发性：两个或两个以上事件在同一时间间隔发生流水线：两个或两个以上事件在可能重叠的时间段内2.0并行处理技术概述2§并行处理技术2.0.2并行性的层次一、程序执行的并行性指令内部并行：微操作并行指令间并行：多条指令并行任务或进程间并行：任务作并行性分解作业或程序间并行：资源的并行性分配算法二、数据处理的并行性位串字串：一次只对一个字的一位进行处理——无并行位并

2、字串：一次对多个字的一位进行处理——W=1，B＞1位串字并：一次对一个字的多位进行处理——W＞1，B=1位并字并：一次对许多字的多位进行处理——W＞1，B＞1三、操作并行性的层次存储器操作并行：在一个存贮周期内访问多个存贮单元处理器操作步骤并行：指令执行子操作重叠处理器操作并行：多处理单元(多核)，在同一控制器控制下按同一条指令对多个数据组同时操作（多SIMD核）并行度增加通信与调度开销增加硬件实现的比例增加3§并行处理技术2.0.3并行性措施及困难一、并行性措施时间重叠：时间上错开，轮流重叠使用硬件：如流水线资源重复：空间重叠，以量取胜资源共享：多用户按时间顺序轮流使

3、用同一套资源：如分时系统二、并行性困难任务分配非常困难可并行性：任务的并行性划分和分发算法对并行性的限制算法不仅与问题有关，还与硬件有关处理机之间的通信开销限制当通信开销大时并行处理技术得不偿失并行处理环境可编程性并行开发环境需要并行编译和并行操作系统支持并行规模的确定可扩展性42.0.5多处理器互联方式通信网络是多处理机性能发挥的瓶颈主要方式：总线、交叉开关、多端口存贮器、开关枢纽网络参数节点度（NodeDegree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（NetworkDiameter）：网络中任何两个节点之间的最长距离，即最

4、大路径数。对剖宽度（BisectionWidth）：对分网络各半所必须移去的最少边数对剖带宽（BisectionBandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称为对称的（Symmetry）5静态互连网络与动态互连网络静态互连网络处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网

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

6、iac网孔了，节点度恒为4，网络直径为N-1，而对剖宽度为2N垂直和水平方向均带环绕，则变成了2-D环绕（2-DTorus），节点度恒为4，网络直径为2[N/2]，对剖宽度为2N8静态互连网络----二叉树二叉树除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。9静态互连网络----超立方超立方一个n-立方由N=2n个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3

7、-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n，而对剖宽度为N/2。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。10动态互连网络---总线PCI、VME、Multics、Sbus、MicroChannel多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等11动态互连网络---交叉开关（Crossbar）单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程