PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

及仇
5 years ago
Views:

1 并行计算 Parallel Computing 主讲人孙广中 Spring, / 41

2 Overview Course Administration Course Style and Structure Intro to Parallel Computing 国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 2 / 41

3 Course Administration Instructor: 孙广中计算机学院国家高性能计算中心 ( 合肥 ) gzsun@ustc.edu.cn TA: 待定 Textbook: 并行计算 - 结构算法编程, 陈国良编著, 北京 : 高等教育出版社,2011 国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 3 / 41

4 Course Administration Reference Book: Kai Hwang,Zhiwei Xu,"Scalable Parallel Computing",McGraw-Hill,1998 J.JaJa,"Introduction to Parallel Algorithms",Addison Wesley,1992 V.Kumar etal, Intro to Parallel Computing, Benjamin/Cummings, 1994 陈国良, 并行算法的设计与分析 ( 第 3 版 ), 高等教育出版社, 2009 陈国良等, 并行计算机体系结构, 高等教育出版社,2002 陈国良等, 并行算法实践, 高等教育出版社,2003 J.Dongarra etal, Sourcebook of Parallel Computing ( 莫则尧等译 ), 电子工业出版社, 2005 Shameem Akhter, et. al. 著, 李宝峰等译. 多核程序设计技术, 电子工业出版社,2007 Richard Gerber, et. al. 著, 王涛等译. 软件优化技术, 电子工业出版社, / 41

5 Grading Grade breakdown Final Exam 60% Homework Assignments 20% Experiments 15% Class Participation and Activity 5% 国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 5 / 41

6 Overview Course Administration Course Style and Structure Intro to Parallel Computing 国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 6 / 41

7 About the Textbook Authors: 陈国良教授, 中科院院士, 国家高性能中心 ( 合肥 ) 主任, 第一届全国高等学校国家级教学名师奖 2009 年国家教学成果二等奖获主并行算法学科体系 : 并行算法的设计与分析并行计算机体系结构并行算法实践并行计算并行计算模型 : 三层并行计算模型 Textbook: 2003 年度国家精品课程教材并行算法学科体系中面向计算机专业及其相关专业的本科生教材国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 7 / 41

8 算法理论可计算性与计算复杂性算法研究的数学基础专业博士生面向计算算法设计与分析并行排序和选择算法 VLSI 计算理论与并行算法并行图论算法分布式算法面向计算并行算法类课程教学网站并行算法的设计与分析并行算法类课程实践算法实现并行算法实践并行计算机体系结构算法应用基础并行计算 : 结构. 算法. 编程面向计或计算科学高性能计算导论国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 8 / 41

9 Parallel Computing Parallel Architectures Parallel Algorithms Parallel Programming Parallel Applications 9 / 41

10 Abstract Generally speaking, parallel computing deals with the parallel computer architectures, parallel algorithms and parallel programming. In this lecture we will discuss briefly them separately. In part I, we will discuss the contemporary parallel computer system architectures and memory access models, parallel system interconnections and parallel system performance evaluation. In part II, we will discuss the parallel computational models, the design methods, techniques and methodology of parallel algorithms, as well as some parallel numerical algorithms. In part III, we will discuss the parallel programming models,sharedmemory, message-passing and dataparallel programming, as well as parallel programming environment and tools. In part III, we will discuss 10 / 41

11 Part I : Parallel Hardware System Hardware Platform for Parallel Computing: System Architectures and Models System Interconnections Performance Evaluation 11 / 41

12 Part I : Parallel Architectures - System Architectures and Models Parallel Computer System Architectures PVP : Parallel Vector Processors SMP : Symmetric Multiprocessors MPP : Massively Parallel Processors DSM : Distributed Shared Memory COW : Cluster Of Workstations Parallel Computer Memory Access Models UMA : Uniform Memory Access NUMA : Non-Uniform Memory Access COMA : Cache-Only Memory Access NORMA : NO-Remote Memory Access 12 / 41

13 Part I : Parallel Architectures - System Interconnections Network Environments Inter-node Interconnections( Buses, Switches ) Inter-node Interconnections( SAN ) Inter-system Interconnections( LAN, MAN, WAN ) Interconnection Topologies Static-Connection Networks( LA,RC,MC,TC,HC,CCC) Dynamic-Connection Networks (Buses, Crossbar, MIN) Wide-Band Networks FDDI( Fiber Distributed Data Interface ) FE/GE( Fast Ethernet / Gigabit Ethernet ) ATM( Asynchronous Transfer Mode ) SCI( Scalable Coherence Interface ) 13 / 41

14 Part I : Parallel Architectures - Performance Evaluation Speed up of Systems Amdahl s Law Gustafson s Law Sun and Ni s Law Scalability of Systems Iso-efficiency Iso-speed Average Latency Performance of Systems : Benchmarks LINPACK SPEC PARKBENCH NAS etc 14 / 41

15 Part II : Parallel Algorithms Theoretical Base for Parallel Computing: Computational Models Design Policy Design Methodology Design Techniques Parallel Numerical Algorithms 15 / 41

16 Part II : Parallel Algorithms - Computational Models PRAM : Parallel Random Access Machines APRAM : Asynchronous PRAM BSP : Bulk Synchronous Parallel LogP : Latency, Overhead, Gap, Processors 16 / 41

17 Part II : Parallel Algorithms - Design Policy Parallelizing a Sequential Algorithm Designing a new Parallel Algorithm Borrowing Other Well-known Algorithm 17 / 41

18 Part II : Parallel Algorithms - Design Methodology PCAM : Partitioning PCAM : Communication PCAM : Agglomeration PCAM : Mapping 18 / 41

19 Part II : Parallel Algorithms - Design Techniques Balanced Trees Doubling Technique Partitioning Strategy Divide and Conquer Pipelining 19 / 41

20 Part II : Parallel Algorithms - Parallel Numerical Algorithms Dense Matrix Algorithms Solving Systems of Linear Equations Fast Fourier Transform 20 / 41

21 Part III : Parallel Programming Software Support for Parallel Computing: Programming Models Shared-Memory Programming Message-Passing Programming Data-Parallel Programming Programming Environment and Tools 21 / 41

22 Part IV : Parallel Applications Applications for Parallel Computing: Application Backgrounds Parallel Computing for Atmospheric Model Software Packages of Numerical Computing Others: 3D Fourier Transform, Image Feature extraction, Seepage Computing, 22 / 41

23 Overview Course Administration Course Style and Structure Intro to Parallel Computing 国家高性能计算中心 ( 合肥 ) 并行计算, 孙广中 ( 中国科学技术大学, 计算机学院 ) 2018/3/19 23 / 41

24 什么是并行计算? A parallel computer is a collection of processing elements that communicate and cooperate to solve large problem fast. David E. Culler Or all processors cooperate to solve a single problem Daily life examples: House construction // 综合 : 并发分布流水 Car manufacturing // 流水线 Grocery store operation // 分布 24 / 41

25 为什么需要并行计算? Interest in parallelism since the very ancient era of computers(e.g. ILLIAC IV of 1967 had 64 processors) Parallel Processing is an effective answer for the tremendous future computing requirements. applications impulses: Data-intensive applications: videoconferencing, virtual reality, large database and data mining, speech recognition, biology, image and signal processing, etc Computing-intensive applications: numerical simulation(e.g. forecasting, manufacturing, chemistry, aerodynamics) Network-intensive applications Multicore and manycore and cloud computing 25 / 41

26 为什么需要并行计算? Grand challenges: Science today: experimentation, theory, simulation(or computation) Simulation relies heavily on parallel processing America HPCC project, ASCI project In one words: Parallel processing promises increase of Performance(e.g. large, fast, cost) Reliability Large set of computational problems are inherently parallel in nature. But their existing applications are designed for uniprocessor systems. Their parallelization is required. 26 / 41

27 应用需求 Cite from CRAY Inc. 27 / 41

28 加速战略计算实施 ASCI 美国能源部 10 年投资 10 亿美元模拟核实验及核武器储备管理问题 TFLOPS TFLOPS PFLOPS EFLOPS, 高性能计算的发展符合千倍定律 28 / 41

29 并行计算的粒度 Coarse-grained( 粗粒度 ):Level of jobs Middle-grained( 中等粒度 ):Level of processes Fine-grained( 细粒度 ):Level of machine instructions(or lower) 29 / 41

30 并行计算的研究领域 Design of parallel computers: How to the number of processors, communication throughput, data sharing, etc. Design of parallel algorithms: Parallel algorithms may be quite different from their sequential counterparts. Design of parallel software: Operating systems Compiles Libraries Tools: debuggers, performance analyzers Applications of parallel computing 30 / 41

31 31 / 41

32 32 / 41

33 33 / 41

34 34 / 41

35 超级计算机的增长速度超过摩尔定律 100 倍 Cite from CRAY Inc. 35 / 41

36 Trends?- 动物食物链 36 / 41

37 Trends? 计算机食物链 Mainframe Mini Computer Workstation PC Vector Supercomputer 37 / 41

38 Trends? 计算机食物链 (hitting wall soon) Mini Computer (future is bleak) Mainframe Workstation PC Vector Supercomputer MPP 38 / 41

39 Trends?- 计算机食物链 ( 现在和将来 ) 39 / 41

40 40 / 41

41 思考题 01 问题 1: 谈谈你所知道的高性能计算与云计算的区别?? 问题 2: 并行程序的描述应如何? 与串行程序有什么不同? 问题 3: 如何并行地尽快求解 n 个元素的最大值或排序? 41 / 41

并行计算

并行计算 Parallel Computing 主讲人孙广中 Spring, 2016 Overview Course Administration Course Style and Structure Intro to Parallel Computing 2 Course Administration(1) Instructor: 孙广中计算机学院 Email:gzsun@ustc.edu.cn