《数值并行算法矩阵运算课件》由会员分享，可在线阅读，更多相关《数值并行算法矩阵运算课件（28页珍藏版）》请在金锄头文库上搜索。
1、并行算法1 / Ch02022/6/3Parallel Algorithms Chapter 0 IntroductionSpring, 2018并行算法2 / Ch02022/6/3主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程介绍课程介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行
2、计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP100问题示例问题示例并行算法3 / Ch02022/6/30.1 任课教师和课程主页任课教师和课程主页n任课教师任课教师徐徐 云云 n我的研究方向我的研究方向大数据挖掘和生物信息学算法大数据挖掘和生物信息学算法并行编程模型及性能优化并行编程模型及性能优化n课程主页课程主页http:/ / Ch02022/6/3主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程介绍课程介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在
3、并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP50问题示例问题示例并行算法5 / Ch02022/6/30.2 课程介绍课程介绍: 内容、特点和学习方式内容、特点和学习方式n课程内容：课程内容：基础知识：并行机结构模型、并行计算模型、并行算法基本知识等；基础知识：并行机结构模型、并行计算模型、并行算法基本知识等；非数值并行算法：排序、选择、组合搜索、串匹
4、配、图论算法等；非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等；数值并行算法：矩阵运算、线性方程组求解、数值并行算法：矩阵运算、线性方程组求解、FFT算法等；算法等；GPU算法：算法：GPU上并行算法、多核并行算法；上并行算法、多核并行算法；热点技术：区块链、全文本索引等。热点技术：区块链、全文本索引等。n课程特点：课程特点：追求算法上界最优追求算法上界最优(并行计算时间、并行成本、加速比并行计算时间、并行成本、加速比)；强调严密的理论分析；强调严密的理论分析；展现优秀的算法思想。展现优秀的算法思想。n学习方式：学习方式：课程讲授课程讲授、大作业大作业和和课堂讨论课堂讨论相结合相结合
5、并行算法6 / Ch02022/6/30.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
6、 Parallel Computing”(Second Edition), 北京：机械工业出版社北京：机械工业出版社, 20032003陈国良陈国良, “并行计算：结构并行计算：结构算法算法编程编程” 北京：高等教育出版社，北京：高等教育出版社，20112011 Rajaraman, Ullman.大数据互联网大规模挖掘与分布式处理大数据互联网大规模挖掘与分布式处理(中中译本译本). 人民邮电出版社人民邮电出版社, 2015.7 并行算法7 / Ch02022/6/30.2 课程简介课程简介: 课程在并行计算技术中的地位课程在并行计算技术中的地位并行算法8 / Ch02022/6/3主要内容主
7、要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程介绍课程介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP100问题示例问题示例并行算法9 / Ch02022/6/30.3 课程考核和评分要求课程考核和评分要求nExam
8、ination and Grading -Lessons & Answer: 10% -Paper: 30% -Final written exam: 60%并行算法10 / Ch02022/6/3主要内容主要内容n0.1 任课教师和课程主页任课教师和课程主页n0.2 课程内容介绍课程内容介绍 课程内容、特点和授课方式课程内容、特点和授课方式教材和主要参考书目教材和主要参考书目课程在并行计算技术中的地位课程在并行计算技术中的地位n0.3 课程考核和评分要求课程考核和评分要求n0.4 并行计算介绍并行计算介绍什么是并行计算什么是并行计算?为什么需要并行计算为什么需要并行计算?几种实现方案几种实现
9、方案并行计算的粒度并行计算的粒度并行计算的研究领域并行计算的研究领域TOP500和和China TOP100问题示例问题示例并行算法11 / Ch02022/6/30.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
10、 problemnDaily life examples:House construction / /综合：并发、分布、流水综合：并发、分布、流水Car manufacturing / /流水线流水线Grocery store operation / /分布分布并行算法12 / Ch02022/6/30.4 并行计算介绍并行计算介绍: 为什么需要并行计算？为什么需要并行计算？(1)nInterest in parallelism since the very ancient era of computers(e.g. ILLIAC IV of 1967 had 64 processors)nP
11、arallel 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 applicat
12、ions: numerical simulation(e.g. forecasting, manufacturing, chemistry, aerodynamics) Network-intensive applicationMulticore and manycore and cloud computing并行算法13 / Ch02022/6/30.4 并行计算介绍并行计算介绍: 为什么需要并行计算？为什么需要并行计算？(2)nGrand challenges:Science today: experimentation, theory, simulation (or computatio
13、n)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 unipro
14、cessor systems. Their parallelization is required.并行算法14 / Ch02022/6/30.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-40
15、0,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 / Ch02022/6/30.4 并行计算介绍并行计算介绍: 并行计算的粒度并行计算的粒度nCo
16、arse-grained(粗粒度粗粒度)：Level of jobsnMiddle-grained(中等粒度中等粒度)：Level of processesnFine-grained(细粒度细粒度)：Level of machine instructions(or lower)并行算法16 / Ch02022/6/30.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 anal
