并行计算结构算法编程Date1现代密码学理论与实践之五并行计算结构算法编程 第一篇 并行计算的基础 第一章 并行计算机系统及其结构模型 第二章 当代并行机系统：SMP、MPP和Cluster 第三章 并行计算性能评测 第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程Date2现代密码学理论与实践之五并行计算结构算法编程 第三篇 并行数值算法 第八章 基本通信操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 第四篇 并行程序设计 第十二章 并行程序设计基础 第十三章 并行程序设计模型和共享存储系统编程 第十四章 分布存储系统并行编程 第十五章 并行程序设计环境与工具Date3现代密码学理论与实践之五第一章并行计算机系统及结构模型 1.1 并行计算 1.1.1 并行计算与计算科学 1.1.2 当代科学与工程问题的计算需求 1.2 并行计算机系统互连 1.2.1 系统互连 1.2.2 静态互联网络 1.2.3 动态互连网络 1.2.4 标准互联网络 1.3 并行计算机系统结构 1.3.1 并行计算机结构模型 1.3.2 并行计算机访存模型Date4现代密码学理论与实践之五并行计算 并行计算：并行机上所作的计算，又称高性能 计算或超级计算。 计算科学：计算物理、计算化学、计算生物等 科学与工程问题的需求：气象预报、油藏模拟 、核武器数值模拟、航天器设计、基因测序等 。 需求类型：计算密集、数据密集、网络密集。 美国HPCC计划：重大挑战性课题，3T性能 美国Petaflops研究项目：Pflop/s。 美国ASCI计划：核武器数值模拟。Date5现代密码学理论与实践之五高性能计算机 Intel（Option Red)： 1Tflops,1997,Pentium Pro SGI(Option Blue Mountain): 3Tflops,1998,MIPS10000 IBM(Option White): 7Tflops,Top4,2001,Power3 日本Earth Simulator: 35Tflops,Top1,2002,VP Hewlett-Packard ASCI Q： 7Tflops ,Top2,3,2002, Alpha Server 中国联想： 1Tflops,Top43,2002Date6现代密码学理论与实践之五系统互连 不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WANDate7现代密码学理论与实践之五局部总线、I/O总线、SAN和LANDate8现代密码学理论与实践之五网络性能指标 节点度（Node Degree）：射入或射出一个节点的边 数。在单向网络中，入射和出射边之和称为节点度。 网络直径（Network Diameter）： 网络中任何两个 节点之间的最长距离，即最大路径数。 对剖宽度（Bisection Width） ：对分网络各半所必须 移去的最少边数对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对 剖平面上通过所有连线的最大信息位（或字节）数 如果从任一节点观看网络都一样，则称网络为对称的（ Symmetry） Date9现代密码学理论与实践之五静态互连网络 与动态互连网络 静态互连网络：处理单元间有着固定连接的一类网络， 在程序执行期间，这种点到点的链接保持不变；典型的 静态网络有一维线性阵列、二维网孔、树连接、超立方 网络、立方环、洗牌交换网、蝶形网络等 动态网络：用交换开关构成的，可按应用程序的要求动 态地改变连接组态；典型的动态网络包括总线、交叉开 关和多级互连网络等。Date10现代密码学理论与实践之五静态互连网络（1） 一维线性阵列（1-D Linear Array）： 并行机中最简单、最基本的互连方式， 每个节点只与其左、右近邻相连，也叫二近邻连接， N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖 宽度为1 当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于 环，环可以是单向的或双向的，其节点度恒为2，直径或为 （双向环）或为N-1（单向环），对剖宽度为2 Date11现代密码学理论与实践之五静态互连网络（2） 二维网孔（2-D Mesh）： 每个节点只与其上、下、左、右的近邻相连（边界节点除外） ，节点度为4，网络直径为 ，对剖宽度为 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了， 节点度恒为4，网络直径为 ，而对剖宽度为 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus） ，节点度恒为4，网络直径为 ，对剖宽度为 Date12现代密码学理论与实践之五静态互连网络（3） 二叉树： 除了根、叶节点，每个内节点只与其父节点和两个子节点相连 。 节点度为3，对剖宽度为1，而树的直径为 如果尽量增大节点度为，则直径缩小为2，此时就变成了星形 网络，其对剖宽度为 传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通 路自叶向根逐渐变宽。Date13现代密码学理论与实践之五静态互连网络（4） 超立方 ： 一个n-立方由 个顶点组成，3-立方如图(a)所示；4-立 方如图(b)所示，由两个3-立方的对应顶点连接而成。 n-立方的节点度为n，网络直径也是n ，而对剖宽度为 。 如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的 3-立方环，此时每个顶点的度为3，而不像超立方那样节点度 为n。Date14现代密码学理论与实践之五嵌入 将网络中的各节点映射到另一个网络中去 用膨胀（Dilation）系数来描述嵌入的质量，它是指被 嵌入网络中的一条链路在所要嵌入的网络中对应所需的 最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中 Date15现代密码学理论与实践之五嵌入Date16现代密码学理论与实践之五网络络名称网络规络规模节节点度网络络直径对对剖宽宽度对对称链链路数线线性阵阵列21非环环形2 （双 向）2是2-D网孔 4非Illiac网孔 4非2-D环绕环绕4是二叉树树31非星形2非超立方nn是立方环环3是静态互连网络特性比较Date17现代密码学理论与实践之五动态互连网络 (1)总线：PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、 快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等Date18现代密码学理论与实践之五动态互连网络 （2） 交叉开关（Crossbar）： 单级交换网络，可为每个端口提供更高的带宽。象电话交换机 一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态 ，而能提供所有（源、目的）对之间的动态连接。 交叉开关一般有两种使用方式：一种是用于对称的多处理机或 多计算机机群中的处理器间的通信；另一种是用于SMP服务器 或向量超级计算机中处理器和存储器之间的存取。Date19现代密码学理论与实践之五动态互联网络 （3） 单级交叉开关级联起来形成多级互连网络MIN（ Multistage Interconnection Network） Date20现代密码学理论与实践之五动态互连网络（4） 交换开关模块： 一个交换开关模块有n个输入和n个输出，每个输入可连接到任 意输出端口，但只允许一对一或一对多的映射，不允许多对一 的映射，因为这将发生输出冲突 级间互连（Interstage Connection ）： 均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接 n输入的网络需要 级 开关，在Ilinois大学的 Cedar2多处理机系统中采用了网络 Cray Y/MP多级网络，该网络用来支持8个向量处理器和256个 存储器模块之间的数据传输。网络能够避免8个处理器同时进 行存储器存取时的冲突。 Date21现代密码学理论与实践之五动态互连网络比较 n,节点规模 w，数据宽度动态动态 互连连网络络的复杂杂度和带宽带宽 性能一览览表网络络特性总线总线 系统统多级级互连连网络络交叉开关硬件复杂杂度每个处处理器带宽带宽 报报道的聚集带宽带宽SunFire服务务器 中的Gigaplane 总线总线 ： 2.67GB/sIBM SP2中的 512节节点的HPS ：10.24GB/sDigital的千兆开 关：3.4GB/sDate22现代密码学理论与实践之五标准互联网络（1） Myrinet: Myrinet是由Myricom公司设计的千兆位包交换网络，其目的 是为了构筑计算机机群，使系统互连成为一种商业产品。 Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及 在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任 意拓扑结构，不必限定为开关网孔或任何规则的结构。 Myrinet在数据链路层具有可变长的包格式，对每条链路施行 流控制和错误控制，并使用切通选路法以及定制的可编程的主 机接口。在物理层上，Myrinet网使用全双工SAN链路，最长 可达3米，峰值速率为（1.281.28）Gbps（目前有 2.56+2.56) Myrinet交换开关 :8,12,16端口 Myrinet主机接口 : 32位的称作LANai芯片的用户定制的VLSI 处理器，它带有Myrinet接口、包接口、DMA引擎和快速静态 随机存取存储器SRAM。 140 of the November 2002 TOP500 use Myrinet, including 15 of the top 100 Date23现代密码学理论与实践之五Myrinet连接的LAN/ClusterDate24现代密码学理论与实践之五标准互连网络（2) 高性能并行接口（HiPPI） Los Alamos国家实验室于1987年提出的一个标准，其目的是试 图统一来自不同产商生产的所有大型机和超级计算机的接口。 在大型机和超级计算机工业界，HiPPI作为短距离的系统到系 统以及系统到外设连接的高速I/O通道。 1993年，ANSI X3T9.3委员会认可了HiPPI标准，它覆盖了物 理和数据链路层，但在这两层之上的任何规定却取决于用户。 HiPPI是个单工的点到点的数据传输接口，其速率可达 800Mbps到1.6Gbps。 开发成功了一种能提供潜在的6.4Gbps速率，比HiPPI快8倍且 有很低时延的超级HiPPI技术， SGI公司和Los Alamos国家实验室都开发了用来构筑速率高达 25.6Gbps的HiPPI交换开关的HiPPI技术。 HiPPI通道和HiPPI交换开关被用在SGI Power Challenge服务 器、IBM 390主机、Cray Y/MP、C90和T3D/T3E等系统 Date25现代密码学理论与实践之五使用HiPPI通道和开关构筑的 LAN主干网 Date26现代密码学理论与实践之五标准互连网络（3） 光纤通道FC（Fiber Channel） : 通道和网络标准的集成 光纤通道既可以是