并行算法1 / Ch02024/8/18Parallel Algorithms Chapter 0 IntroductionSpring, 2016并行算法2 / Ch02024/8/18主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程介绍课程介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP100问题示例问题示例并行算法3 / Ch02024/8/180.1 任课教师和课程主页任课教师和课程主页n任课教师任课教师徐徐 云云 xuyunustc.edu.cnn我的研究方向我的研究方向大数据挖掘和生物信息学算法大数据挖掘和生物信息学算法并行编程模型及性能优化并行编程模型及性能优化n课程主页课程主页http:/staff.ustc.edu.cn/xuyun/pa.htm并行算法4 / Ch02024/8/18主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程介绍课程介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP50问题示例问题示例并行算法5 / Ch02024/8/180.2 课程介绍课程介绍: 内容、特点和学习方式内容、特点和学习方式n课程内容：课程内容：并行机结构模型、并行计算模型、并行算法基本知识；并行机结构模型、并行计算模型、并行算法基本知识；非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等；非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等；数值并行算法：矩阵运算、线性方程组求解、数值并行算法：矩阵运算、线性方程组求解、FFT算法等；算法等；并行计算理论。并行计算理论。新增内容：多核计算和新增内容：多核计算和GPU上的并行算法上的并行算法n课程特点：课程特点：追求算法上界最优追求算法上界最优(并行计算时间、并行成本、加速比并行计算时间、并行成本、加速比)；强调严密的理论分析；强调严密的理论分析；展现优秀的算法思想；展现优秀的算法思想；n学习方式：学习方式：课程讲授课程讲授、大作业大作业和和课堂讨论课堂讨论相结合相结合并行算法6 / Ch02024/8/180.2 课程简介课程简介: 教材和主要参考书目教材和主要参考书目n教材：教材：陈国良陈国良, 并行算法的设计与分析并行算法的设计与分析（第（第3 3版）版）, 高等教育出版社高等教育出版社, 2009.8 n主要参考书目：主要参考书目：Kai Hwang,Zhiwei Xu”,Scalable Parallel Computing”,McGraw-Hill,1998J.JaJa,”Introduction to Parallel Algorithms”, Addison Wesley,1992A.Gramma et al, ”Introduction to Parallel Computing”(Second Edition), 北京：机械工业出版社北京：机械工业出版社, 20032003陈国良陈国良, “并行计算：结构并行计算：结构算法算法编程编程” 北京：高等教育出版社，北京：高等教育出版社，20112011 并行算法7 / Ch02024/8/180.2 课程简介课程简介: 课程在并行计算技术中的地位课程在并行计算技术中的地位并行算法8 / Ch02024/8/18主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程介绍课程介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP100问题示例问题示例并行算法9 / Ch02024/8/180.3 课程考核和评分要求课程考核和评分要求nExamination and Grading -Lessons & Answer: 5% -Paper: 25% -Final written exam: 70%并行算法10 / Ch02024/8/18主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程内容介绍课程内容介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP100问题示例问题示例并行算法11 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 什么是并行计算？什么是并行计算？nA parallel computer is a “collection of processing elements that communicate and cooperate to solve large problem fast”. -David E. CullernOr all processors cooperate to solve a single problemnDaily life examples:House construction /综合：并发、分布、流水综合：并发、分布、流水Car manufacturing /流水线流水线Grocery store operation /分布分布并行算法12 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 为什么需要并行计算？为什么需要并行计算？(1)nInterest in parallelism since the very ancient era of computers(e.g. ILLIAC IV of 1967 had 64 processors)nParallel Processing is an effective answer for the tremendous future computing requirements.napplications impulses:Data-intensive applications: videoconferencing, virtual reality, large database and data mining, speech recognition, biology, image and signal processing, etcComputing-intensive applications: numerical simulation(e.g. forecasting, manufacturing, chemistry, aerodynamics) Network-intensive applicationMulticore and manycore and cloud computing并行算法13 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 为什么需要并行计算？为什么需要并行计算？(2)nGrand challenges:Science today: experimentation, theory, simulation (or computation)Simulation relies heavily on parallel processingnMulticore and ManycorenIn one words: Parallel processing promises increase ofPerformance(e.g. large, fast, cost)ReliabilityLarge set of computational problems are inherently parallel in nature. But their existing applications are designed for uniprocessor systems. Their parallelization is required.并行算法14 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 几种实现方案几种实现方案nMulti-Core PC, GPU (lowest cost)nCluster of workstations (lower cost)nMultiprocessor workstations ($60,000)DEC Firefly, Apollo DN 10000, SUN SPARCstation 20nShared memory multiprocessors ($200,000-400,000)Sequent Symmetry, Encore Multimax, SGI Challenge, SUN SPARCserver 2000nDistributed memory multicomputers ($200,000-400,000)Intel iPSC/860, NCUBE/2, MeikonMassively parallel processors ($5,000,000)Intel Paragon, TMC CM-5, CRAY T3D, IBM SP-2并行算法15 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 并行计算的粒度并行计算的粒度nCoarse-grained(粗粒度粗粒度)：Level of jobsnMiddle-grained(中等粒度中等粒度)：Level of processesnFine-grained(细粒度细粒度)：Level of machine instructions(or lower)并行算法16 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 并行计算无处不在并行计算无处不在n并并行行计算算时代已到代已到来来，将将普惠天下大普惠天下大众众多核多核PC国国家高性能家高性能计算中心算中心我校和中我校和中国国惠普惠普联手共建高性能手共建高性能计算算实验室室 2003-07-11http:/hpcjl.ustc.edu.cn/ n并并行行计算无算无处不在不在天天气气预报电影影电视制作制作搜索引擎：搜索引擎：www.google.com大型大型数数据据库医医药食品食品汽汽车、飞机机设计制造制造大大坝桥梁建造，防汛抗灾梁建造，防汛抗灾并行算法17 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 研究领域研究领域nDesign of parallel computers: How to the number of processors, communication throughput, data sharing, etc.nDesign of parallel algorithms: Parallel algorithms may be quite different from their sequential counterparts.nDesign of parallel software:Operating systemsCompilesLibrariesTools: debuggers, performance analyzersnApplication of parallel computing并行算法18 / Ch02024/8/180.4 并行计算介绍并行计算介绍: TOP500 http:/www.top500.org 并行算法19 / Ch02024/8/180.4 并行计算介绍并行计算介绍: TOP500 http:/www.top500.org Titan: ORNL Supercomputer n处理器理器及加速器及加速器: Per node：16-core AMD Opteron 6274 processor and an NVIDIA Tesla K20X GPU accelerator18,688 nodesn计算能力算能力: 理理论值: 27112.5 TFLOPS 实际值: 17590 TFLOPSn主存主存: 710TB并行算法20 / Ch02024/8/18中国高性能计算机性能中国高性能计算机性能TOP100排行榜排行榜张云泉张云泉 孙家昶孙家昶 袁国兴袁国兴 张林波张林波中国软件行业协会数学软件分会中国软件行业协会数学软件分会国家国家863863高性能计算机评测中心高性能计算机评测中心（http:/www.samss.org.cnhttp:/www.samss.org.cn）并行算法21 / Ch02024/8/18微微处理器中的理器中的并并行行计算算（1）n指令级并行(Instruction-level Parallelism ILP)：乱序(out of order)执行、分支预测、指令多发射、硬件预取等；n抢占式或时间片轮转的多任务OSn同时多线程技术(simultaneous Multi-Threading, SMT)：Intel公司实现的SMT技术就是超线程(Hyper-Threading, HT)技术，超线程技术实际上只有一个物理处理器，但从软件的角度来看，存在多个逻辑处理器。n多核处理器技术：采用单芯片多处理器(Chip Multiprocessor, CMP)的设计，多核多线程(有别于单核上的超线程)并行算法22 / Ch02024/8/18典型的多核典型的多核处理器（理器（2）n通用通用处理器：理器：IntelXeon 5300 (四核四核) IBMPOWER5(双双核核)SUNNIAGARA(8核核)、UltraSpac(双双核核) n网网络处理器理器IntelIXP2400MotorolaC-5n嵌入式系嵌入式系统TIOMAP，DavinciARMARM11MP图像处理图像处理图像处理图像处理 NvdiaNvdiaGF6800GF6800多媒体处理多媒体处理多媒体处理多媒体处理 IBMIBM，SonySony和和和和ToshibaToshibaCellCell处理器处理器处理器处理器 StanfordStanford大学大学大学大学ImagineImagine实验系统实验系统实验系统实验系统 AmbricAmbricAM2045(360AM2045(360核）核）核）核） Intel80Intel80个核的实验处理器个核的实验处理器个核的实验处理器个核的实验处理器 多核时代软件的挑战：在于并行算法和程序的并行化多核时代软件的挑战：在于并行算法和程序的并行化多核时代软件的挑战：在于并行算法和程序的并行化多核时代软件的挑战：在于并行算法和程序的并行化并行算法23 / Ch02024/8/18 虚虚拟化技化技术（3）n虚拟化技术：目前，计算的一个重要趋势就是虚拟化。创建一个虚拟计算环境，应用程序在该独立的环境或者虚拟机上执行，这些虚拟机能够运行完整、独立的OS并充分利用多线程技术。可分为两类：运行时虚拟化 这类虚拟机可以看作是OS之上的一种容器或者执行程序。如，Java虚拟机和微软的通用语言运行时环境(Common Language Runtime, CLR)。 系统虚拟化 这类虚拟机为应用软件重新创建了一个完整的执行环境，并且运行了一个属于自己的操作系统实例。n虚拟化技术和超线程的不同：前者使得应用程序在多个虚拟机上运行好像存在多个执行核，而后者没有虚拟核概念，只是物理核上分时运行。虚拟化的一个重要好处是剥离指令集结构与处理器的必然联系。并行算法24 / Ch02024/8/18并行算法25 / Ch02024/8/180.4 并行计算介绍并行计算介绍: 问题示例问题示例n问题问题1: 如何使如何使p个处理器中的多项数据，高效存储到共享存储器的个处理器中的多项数据，高效存储到共享存储器的一个数组中一个数组中? 问题问题2: 如何在一个分布式计算环境中对如何在一个分布式计算环境中对n个数进行排序个数进行排序? 问题问题3: 如何设计处理器的互联网络最优化矩阵乘法的计算时间？如何设计处理器的互联网络最优化矩阵乘法的计算时间？并行算法26 / Ch02024/8/18 End of Chapter 0