并行计算-结构算法编程修订版高等教育出版社课件

1.陈国良等，《并行计算机体系结构》，北京：高教出版社，2002

2.陈国良，《并行算法的设计与分析》，北京：高教出版社，2002(修订版)

3.陈国良等，《并行算法实践》，北京：高教出版社，2003

4.BarryWilkinson等，陆鑫达等译，《并行程序设计》，北京：机械工业出版社，2001参考教材并行计算（机）的历史和发展方向并行计算机体系结构概况并行计算机完成计算要考虑的一些关键问题并行算法设计的一般思路一些常用的并行算法基于多核的并行编程（入门级）课程简介《并行计算》课程要讨论的内容了解当代并行计算机的发展现状了解并行计算相关的基本术语和技术了解并行计算的思维方式能够理解和设计简单的并行算法能够设计和实现简单的并行程序（基于多核）开阔分析和处理问题的思路课程简介《并行计算》课程的目的总目录第一章 并行计算机系统及其结构模型第二章当代并行计算机系统介绍第四章并行算法的设计基础第五章并行算法的一般设计策略第六章并行算法的基本设计技术第七章并行算法的一般设计过程第八章基本通信操作第九章多核编程技术介绍成绩评定出勤率作业讨论考试成绩“并行计算”的概念串行式计算传统上，一般的软件设计都是串行式计算：软件在一台只有一个CPU的电脑上运行；问题被分解成离散的指令序列；指令被一条接一条的执行；在任何时间CPU上最多只有一条指令在运行。问题指令序列串行式计算“并行计算”的概念在最简单的情形下，并行计算是使用多个计算资源去解决可计算问题。用多CPU来运行；问题被分解成离散的部分可以被同时解决；每一部分被细分成一系列指令；每一部分的指令可以在不同的CPU上同时的执行；“并行计算”的概念“并行计算”的概念问题指令序列计算资源可以包括：任意数量的CPU用网络连接起来;

多核CPU；或者以上两者结合；可计算问题的特性：能分解成可以同时解决的离散的工作块；同一时刻可以执行多条程序指令；通常用多个计算资源解决问题所花的时间要比单个计算资源要短；并行计算是使用多个计算资源去解决可计算问题并行计算的用途

在历史上，并行计算被认为是高端计算，并用于为复杂的科学计算和基于真实世界的工程问题建模。大气层、地球、环境物理学应用、核能、原子能、凝聚态、高压、溶解、光电子；生物科学、生物工程、基因学化学、分子科学地理和地震学机械工程、从弥补术到空间飞行器电气工程、电路设计、微电子学计算机科学、数学并行计算的用途计算机模拟并行计算的用途计算机模拟并行计算的用途今天，商务应用是推动快速计算机发展的更大的推动力。这些应用需要用复杂的方法处理大量数据。数据库、数据挖掘石油勘探网络搜索引擎、基于网络的商务服务医学成像和诊断，制药设计国有企业或跨国企业的管理金融经济建模高级制图和虚拟现实、特别实在娱乐事业上网络视频和多媒体技术，协同工作环境大气的模型：分解成多个三维的单元。天气变化模拟：重复计算这些三维单元的状态来模拟它们随着时间推移变化的情况模拟示例全球大气被分解成大小是：1英里1英里1英里的单元，布满10英里高的高度，估计需要5*108个单元假设每个单元每次计算需要200次浮点运算，则一个时间步必须完成1011次浮点运算.如果要预报10天以上的天气，使用的时间间隔为10分钟，则需要104个时间步，总计需要浮点运算1015次.如果是一个100Mflops(108浮点运算/s)的计算机，则需108秒超过100天.如果想要10分钟完成计算，则需运算速度1.7Tflops(1.71012浮点运算/s)的计算机.例1：数值天气预报（计算机模拟）为什么使用并行计算节省时间和成本：理论上，使用更多的资源会使一个任务提前完成，而且会节约潜在的成本。况且可以使用便宜的、甚至市面将要淘汰的CPU来构建并行聚簇。解决更大规模的问题：很多问题是相当庞大而复杂的，尤其是当计算机的内存受到限制的时候，用单个计算机来解决是不切实际或者根本不可能的。"GrandChallenge"(/wiki/Grand_Challenge)问题需要Peta级浮点运算能力和存储空间的计算资源。网络搜索引擎和网络数据库每秒钟要执行上百万次的处理。为什么使用并行计算支持并行：单一的计算资源在同一时刻只能做一件事情。多个计算资源能够同时做很多事情。例如：AccessGrid(/)提供一个全球的合作网络，在这里来自世界上不同国家的人们可以开会并“现场”指导工作。为什么使用并行计算

使用非本地资源：当缺少本地计算资源的时候可以使用广泛的网络或Internet计算资源。例如：SETI@home()使用超过330000个计算机来执行每秒超过528T次浮点运算；(August04,2008)Folding@home()使用超过340,000计算机来执行每秒4.2P次浮点运算(November4,2008)为什么使用并行计算例2.并行处理技术在信息安全领域的应用一、并行处理技术在传统密码学中的应用

1、提高加解密的速度

2、提高密钥生成的速度

3、加速密码分析mccmkkk密码系统机理例2.并行处理技术在信息安全领域的应用二、利用量子计算机对传统密码体制进行分析

量子计算机是一种传统意义上的极大规模并行计算系统

大数的因子分解是数学中的一个传统难题，这一结果在密码学中有重要应用，著名的RSA算法的安全性就基于大数因子分解。现在人们普遍相信，对于经典计算机，大数因子分解不存在有效的多项式时间算法。但Shor却证明，利用量子计算机，可以在多项式时间内将大数分解，这一结果向RSA公钥系统的安全性提出了严重挑战。目前：量子计算机的实验方案还很初步。现在的实验只制备出单个的量子逻辑门，远未达到实现计算所需要的逻辑门网络。如果：在不远的将来，量子计算机成为现实，各种密码算法都能够被轻易的破解出来串行计算的限制

理论上和实际上，想要轻易地制造更快的串行计算机存在着巨大的限制。传输速度——线性计算机的执行速度直接取决于数据在硬件中传输的速度。光速的绝对限制是每纳秒30cm，铜导线是每纳秒9cm。不断提升的执行速度更加靠近极限。微型化的极限——处理器技术使芯片集成了更多的晶体管。但是，即使使用分子或者原子级别的组件也会很快达到芯片集成晶体管的极限。经济上的限制——让单个芯片变得更快需要增加昂贵的投入。用多个一般的芯片来取代单个高性能的芯片或许性能会更好而且更便宜1.2.1系统互连不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN局部总线、I/O总线、SAN和LAN1.2.1系统互连静态互连网络与动态互连网络静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。定义1：网络中任意两节点间最短路径的最大值称为网络的直径(diameterofanetwork)。直径越小越好，说明网络中任意两节点间的通信时间越少。它被用来确定并行算法的通信下限。定义2：当网络被切为相等的两半时，切口处的最少边数称为等分宽度（bisectionwidth对剖宽度）。等分宽度越大，说明网络布线密度越大，通信的复杂性越小。它为消息传递量提供了下限值。平分宽度=2直径=4网络性能指标定义3：与节点连接的边数称为节点度(nodedegree)。网络中各节点的节点度最好为一个常量，而不依赖于网络的大小，这样是因为处理器组织规模更容易扩大。定义4：如果从任意节点看网络都一样，则称网络为对称的(Symmetry)。节点度=2该网络是对称的网络性能指标1.2.2静态互连网络（1）一维线性阵列（1-DLinearArray）：并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为（双向环）或为N-1（单向环），对剖宽度为21.2.2静态互连网络（2）

二维网孔（2-DMesh）：每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为，对剖宽度为在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为，而对剖宽度为垂直和水平方向均带环绕，则变成了2-D环绕（2-DTorus），节点度恒为4，网络直径为，对剖宽度为1.2.2静态互连网络（3）二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。1.2.2静态互连网络（4）超立方：一个n-立方由个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n，而对剖宽度为。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列21非环形2

（双向）2是2-D网孔

4非Illiac网孔

4非2-D环绕4是二叉树31非星形2非超立方

nn是立方环3是静态互连网络特性比较1.2.3动态互连网络(1)总线：PCI、VME、Multics、Sbus、MicroChannel

多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等交叉开关（Crossbar）：单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储`器之间的存取。1.2.3动态互连网络(2)单级交叉开关级联起来形成多级互连网络MIN（MultistageInterconnectionNetwork）1.2.3动态互连网络(3)交换开关模块：

一个交换开关模块有n个输入和n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突级间互连（InterstageConnection）：均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接n输入的Ω网络需要级开关，在Ilinois大学的Cedar[2]多处理机系统中采用了Ω网络CrayY/MP多级网络，该网络用来支持8个向量处理器和256个存储器模块之间的数据传输。网络能够避免8个处理器同时进行存储器存取时的冲突。1.2.3动态互连网络(4)动态互连网络比较n,节点规模w，数据宽度动态互连网络的复杂度和带宽性能一览表网络特性总线系统多级互连网络交叉开关硬件复杂度每个处理器带宽

～报道的聚集带宽SunFire服务器中的Gigaplane总线：2.67GB/sIBMSP2中的512节点的HPS：10.24GB/sDigital的千兆开关：3.4GB/s1.2.4标准互联网络（1）Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，Myrinet网使用全双工SAN链路，最长可达3米，峰值速率为（1.28＋1.28）Gbps（目前有2.56+2.56)Myrinet交换开关:8,12,16端口Myrinet主机接口:32位的称作LANai芯片的用户定制的VLSI处理器，它带有Myrinet接口、包接口、DMA引擎和快速静态随机存取存储器SRAM。140oftheNovember2002TOP500useMyrinet,including15ofthetop100Myrinet连接的LAN/Cluster(机群)高性能并行接口（HiPPI）LosAlamos国家实验室于1987年提出的一个标准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。在大型机和超级计算机工业界，HiPPI作为短距离的系统到系统以及系统到外设连接的高速I/O通道。1993年，ANSIX3T9.3委员会认可了HiPPI标准，它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。HiPPI是个单工的点到点的数据传输接口，其速率可达800Mbps到1.6Gbps。开发成功了一种能提供潜在的6.4Gbps速率，比HiPPI快8倍且有很低时延的超级HiPPI技术，SGI公司和LosAlamos国家实验室都开发了用来构筑速率高达25.6Gbps的HiPPI交换开关的HiPPI技术。HiPPI通道和HiPPI交换开关被用在SGIPowerChallenge服务器、IBM390主机、CrayY/MP、C90和T3D/T3E等系统

1.2.4标准互联网络（2）使用HiPPI通道和开关构筑的LAN主干网光纤通道FC（FiberChannel）:通道和网络标准的集成光纤通道既可以是共享介质，也可以是一种交换技术光纤通道操作速度范围可从100到133、200、400和800Mbps。FCSI厂商也正在推出未来具有更高速度（1、2或4Gbps）的光纤通道光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接FDDI:光纤分布式数据接口FDDI（FiberDistributedDataInterface）FDDI采用双向光纤令牌环可提供100-200Mbps数据传输速率FDDI具有互连大量设备的能力传统的FDDI仅以异步方式操作1.2.4标准互联网络（3）双向FDDI环作为主干网ATM（AsynchronousTransferMode）:由成立于1991年的ATM论坛和ITU标准定义。ATM是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为53字节的报元进行传输。这种技术是基于报元交换机制。ATM的目的是将实时和突发数据的传输合并成单一的网络技术。ATM网络支持从25到51、155和622Mbps不同的速率，其速率越低ATM交换器和使用的链路价格越低。1.2.4标准互联网络（4）香港大学开发的Pearl机群代别类型以太网10BaseT快速以太网100BaseT千兆位以太网1GB引入年代198219941997速度（带宽）10Mb/s100Mb/s1Gb/s最大距离UTR（非屏蔽双扭对）100m100m25－100mSTP（屏蔽双扭对）同轴电缆500m100m25－100m多模光纤2Km412m（半双工）2Km（全双工）500m单模光纤25Km20Km3Km主要应用领域文件共享，打印机共享COW计算，C/S结构，大型数据库存取等大型图像文件，多媒体，因特网，内部网，数据仓库等1.2.4标准互联网络（5）1.3.1并行计算机结构模型

多核处理器

（MulticoreProcessor）两个或多个独立运行的内核集成于同一个处理器上面同一处理器内部所封装的核心如果体系结构相同，且对存储、I/O等资源的访问具有同等的地位，则为对称多核处理器。IBM、SUN、Intel、AMD均有对称多核处理器产品同一处理器内部所封装的核心如果体系结构不同，或者角色不同，则为非对称多核处理器。IBM、东芝、索尼、索尼娱乐共同推出的CellBECore0Core1FrontSideBus并行计算机体系合一结构

SMP、MPP、DSM和COW并行结构渐趋一致。大量的节点通过高速网络互连起来节点遵循Shell结构：用专门定制的Shell电路将商用微处理器和节点的其它部分（包括板级Cache、局存、NIC和DISK）连接起来。优点是CPU升级只需要更换Shell。1.3.1并行计算机结构模型五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定制商用商用商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器CrayC-90，CrayT-90，银河1号IBMR50，SGIPowerChallenge，曙光1号IntelParagon，IBMSP2，曙光1000/2000StanfordDASH，CrayT3DBerkeleyNOW，AlphaFarm1.3.2并行计算机访存模型（1)UMA（UniformMemoryAccess）模型是均匀存储访问模型的简称。其特点是：物理存储器被所有处理器均匀共享；所有处理器访问任何存储字取相同的时间；每台处理器可带私有高速缓存；外围设备也可以一定形式共享。NUMA(NonuniformMemoryAccess)模型是非均匀存储访问模型的简称。特点是