并行计算

Size: px

Start display at page:

Download "并行计算"

壹扈
5 years ago
Views:

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

2 Overview Course Administration Course Style and Structure Intro to Parallel Computing 2

3 Course Administration(1) Instructor: 孙广中计算机学院 TA: 待定 Textbook: 并行计算 - 结构算法编程, 陈国良编著, 北京 : 高等教育出版社,2011 3

4 Course Administration(2) 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. 著, 王涛等译. 软件优化技术, 电子工业出版社,2007 4

5 Grading Grade breakdown Final Exam: 70% Homework Assignments 10% Experiments 15% Class Participation and Activity: 5% 5

6 Overview Course Administration Course Style and Structure Intro to Parallel Computing 6

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

8 算法理论算法设计与分析算法实现算法应用基础并行排序和选择算法并行算法类课程教学网站可计算性与计算复杂性并行算法实践 VLSI 计算理论与并行算法算法研究的数学基础并行图论算法并行算法的设计与分析并行计算 : 结构. 算法. 编程高性能计算导论并行计算机体系结构分布式算法并行算法类课程实践面向计算机专业博士生面向计算机专业硕士生面向计算机专业本科生或计算科学的研究生 8

9 Parallel Computing Parallel Architectures Parallel Algorithms Parallel Programming Parallel Applications 9

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,shared-memory, message-passing and dataparallel programming, as well as parallel programming environment and tools. In part III, we will discuss 10

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

12 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

13 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

14 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

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

16 Computational Models PRAM : Parallel Random Access Machines APRAM : Asynchronous PRAM BSP : Bulk Synchronous Parallel LogP : Latency, Overhead, Gap, Processors 16

17 Design Policy Parallelizing a Sequential Algorithm Designing a new Parallel Algorithm Borrowing Other Well-known Algorithm 17

18 Design Methodology PCAM : Partitioning PCAM : Communication PCAM : Agglomeration PCAM : Mapping 18

19 Design Techniques Balanced Trees Doubling Technique Partitioning Strategy Divide and Conquer Pipelining 19

20 Parallel Numerical Algorithms Dense Matrix Algorithms Solving Systems of Linear Equations Fast Fourier Transform 20

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

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

23 Overview Course Administration Course Style and Structure Intro to Parallel Computing 23

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

25 为什么需要并行计算?(1) 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

26 为什么需要并行计算?(2) 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

27 Cite from CRAY Inc. 应用需求 27

28 1000GB 100GB 存储器容量全球气候变化人类基因湍流飞行动力学海洋环流粘滞流体动力学超导建模半导体建模量子染色动力学视觉 10GB 1GB 物体特性分析 72 小时天气预报结构生物学药物设计 100MB 3 维等离子体建模 10MB 48 小时天气预报机翼设计油藏建模化学动力学年后 100Mflops 1Gflops 10Gflops 100Gflops 1Tflops 图 1-1 系统速度 28

29 计算问题与时间要求问题 : 科学和工程问题的数值模拟与仿真计算密集数据密集网络密集三种混合要求 : 在合理的时限内完成计算任务秒级制造业分钟级短时天气预报 ( 当天 ) 小时级中期天气预报 (3~10 日 ) 尽可能快长期天气预报 ( 气候 ) 可计算湍流模拟 29

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

31 IBM 的策略 Cite from IBM Inc. 31

32 几种并行实现方案 Multi core PC and GPU (lowest cost) Cluster of workstations (lower cost) Multiprocessor workstations ($60,000) DEC Firefly, Apollo DN 10000, SUN SPARCstation 20 Shared memory multiprocessors ($200, ,000) Sequent Symmetry, Encore Multimax, SGI Challenge, SUN SPARCserver 2000 Distributed memory multicomputers ($200, ,000) Intel ipsc/860, NCUBE/2, Meiko Massively parallel processors ($5,000,000) Intel Paragon, TMC CM-5, CRAY T3D, IBM SP-2 32

33 通用处理器 : 典型的多核处理器系统 Intel Xeon 5300 ( 四核 ) IBM POWER5( 双核 ) SUN NIAGARA(8 核 ) UltraSpac( 双核 ) 网络处理器 Intel IXP2400 Motorola C-5 嵌入式系统 TI OMAP,Davinci ARM ARM11MP 图像处理 Nvdia GF6800 多媒体处理 IBM,Sony 和 Toshiba Cell 处理器 Stanford 大学 Imagine 实验系统 Ambric AM2045(360 核 ) Intel 80 个核的实验处理器多核时代软件的挑战 : 在于并行算法和程序的并行化 33

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

35 并行计算的研究领域 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 35

36 36

37 37

38 TOP

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

40 动物食物链 Trends? 40

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

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

43 Trends? 计算机食物链 ( 现在和将来 ) 43

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

PowerPoint 演示文稿

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