4-HPC-trend-Intel-ICAF-zhangyunquan [Compatibility Mode]

Size: px

Start display at page:

Download "4-HPC-trend-Intel-ICAF-zhangyunquan [Compatibility Mode]"

简董
5 years ago
Views:

1 并行编程的现状及发展趋势张云泉中科院软件所并行软件与计算科学实验室计算机科学国家重点实验室 2010 年 8 月 20 日 ICAF 2010 成都香格里拉饭店

2 提纲无处不在的并行, 群核处理器普及并行程序设计语言现状并行程序设计语言发展趋势小结

3 MOORE S LAW The number of transistors incorporated in a chip will approximately double every 24 months. Gordon Moore Intel 1965

4 已经开始的计算革命 GHZ => MULTI-CORE 免费午餐没有了 : 软件面临着向并发的根本转变 The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software Herb Sutter in Dr. Dobb s Journal 30(3), March 2005

5 MANY-CORE: 群核与众核? Multi-Core: 多核 Many-Core: 许多核? 群核 : 异构核三五成群 : 几个人几个人在一起出处 : 明余继登典故纪闻卷十二 : 三五成群, 高谈嬉笑君字与羊字合起来群龙无首一群龙没有领头的比喻没有领头的, 无法统一行动群策群力群 : 大家, 集体 ; 策 : 谋划, 主意指发挥集体的作用, 大家一起来想办法, 贡献力量众核 : 同构核眾 : 一人为大, 二人为从, 三人则众人多势众众口一词众所共知众志成城出处 : 国语周语下 : 众心成城, 众口铄金不是处理器核的简单排列组合, 而是重新设计, 新的体系结构

6 四类群核处理器体系架构第一类 : 将重核集成在一起, 改动很少第二类 : 挖掘并行体系结构的设计空间, 寻找最优的芯片体系结构模型, 如 Cell, Cyclops64, Polaris, Larrabee 等第三类 : 全新的基于数据流的体系架构, 如 TRIPS( 数据流图的块执行 ), TFlex 体系结构 ( 组件化轻量处理器,CLP) 第四类 : 通用图形处理器 GPGPU, CPU+GPU, 如 Nvidia 公司的 Tesla,AMD 公司的 Firestream

7 多核和多线程异构四个体系结构创新片上 SMP, 或多线程机器, 程序模型是多线程大量增加处理器, 对传统并行应用带来巨大挑战性能受限于 : 管脚数, 存储墙, 处理器间协同提供多种计算模式, 如 Cell 处理器 gather-compute-scatter 存储模型和向量 / 标量计算模型选择一个合适的计算模型, 很有挑战性没有清晰的高效或可移植程序设计模型 GPGPU 加速器部件和可重构受限于 Amdahl 定律, 且数据传输也成为问题通常是体系结构里二等公民, 但 GPU 有取代之意就近存储 (near memory) 解决延迟问题 : 将计算资源靠近存储体 Processing-In-Memory 和 Processing Near-Memory(PNM)(3 维存储 ), 采用 PIM 技术的多核可比传统多核快 2-40 倍!

8 提纲无处不在的并行, 群核处理器普及并行程序设计语言的现状并行程序设计语言的发展趋势小结

9 并行计算的研究范围 3 算法设计 4 应用程序软件开发并行计算模型并行编程模型 2 并行计算系统软件 Interconnection Network 中间件 Memory Memory Memory Memory P P P P P P P P P P P P P P P P Multi-core processors Multi-core processors Multi-core processors Multi-core processors 1 体系结构设计

10 并行程序设计模型共享存储 : Automatic parallelization Pthreads(POSIX threads) Compiler directives: OpenMP 消息传递 : MPI: message passing interface PVM: parallel virtual machine HPF: high performance fortran 混合 SIMD( 指令级 )+CUDA( 核心级 )+OpenMP( 循环级 )+MPI( 进程级 ) PGAS CAF,UPC,Titanium HPCS 语言 ( 动态任务并行 ) X10,Chapel,Fortress

11 并行计算机设计程序的三种途径串行程序的自动并行化用户提供常规的串行程序, 编译器完成并行化由于编译器能力有限, 只对部分应用有效使用全新的并行语言 : 函数型数据流等已有应用程序需要全部改写新语言的实现效率有待进一步提高串行语言 + 并行化扩充增加支持并行性开发与通信同步的库调用增加新的语言成分, 如数组运算并行循环等 SPMD (Single Program Multiple Data) 编程模式

12 三代并行计算模型第一代并行计算模型 ( 针对共享存储器结构 ) 代表 :PRAM[Fortune&Wyllie78] 其他 :APRAM[Cole89] BPRAM 和 LPRAM[Aggarwal89] QSM[Gibbons97] 等第二代并行计算模型 ( 针对分布式存储结构 ) 代表 :BSP( 同步执行 )[Valiant90] LogP( 异步执行 )[Culler93] 其他 :LogGP[Alexandrov95] LogGPS[InoF01] LoGPC[Morirz98] BDM[Joesph96] C3[Hambrusch96] 等第三代并行计算模型 ( 考虑了访存层次 ) Memory LogP[Cameron03] LognP/Log3P [Cameron07] LogP- HMM[Li ZY95],DRAM(h,k)[ 张云泉 00],mLognP[ 涂碧波 08] 等

0 版标准发布,SC 94 1995 年 6 月,MPI 1.1 版标准发布 1997 年 4 月,MPI 2.

13 MPI 并行编程环境历史 1992 年 4 月, 由橡树岭国立实验室和 Rice 大学联合发起 ; William Gropp, Ewing Lusk 等人 1992 年 11 月,MPI 1.0 标准初稿发布 ; 1993 年 2 月, 修改稿发布,MPI 论坛成立 1994 年 6 月,MPI 1.0 版标准发布,SC 年 6 月,MPI 1.1 版标准发布 1997 年 4 月,MPI 2.0 版标准发布单边通信, 并行 I/O, 动态进程管理, 远程存储操作 2009 年 9 月,MPI 2.2 版标准发布 2011 年 9 月,MPI 3.0 版标准发布? 可扩展性 ( 性能和鲁棒性 ), 多核对机群和应用的支持混合编程动态任务并行

14 OPENMP Open specifications for Multi Processing An API for multi-threaded shared memory parallelism The OpenMP API specification for parallel programming started in 1997 October 1997: Fortran version 1.0 Late 1998: C/C++ version 1.0 June 2000: Fortran version 2.0 April 2002: C/C++ version : C/C++/Fortran version 2.5 May, 2008: Version 3.0: tasks and the task construct 指示语句 + 库函数 + 环境函数遵循 Fork-Join 模型, 不同区域的线程数可动态调整优势 : 已有串行程序的增量并行 #pragma omp directive-name [clause [, clause] ] newline

15 MPI+OPENMP 混合编程 MPI - 显式并行, 没有同步问题 - 适合粗粒度 OpenMP - 容易编程, 允许动态调度 - 只支持共享存储, 存在同步问题 MPI/OpenMP 混合 - 可以将 MPI 的数据分配与 OpenMP 的细粒度并行结合 - 适合 SMP 集群 (Clumps) - 可以实现层次并行模型前提条件 MPI 由于负载均衡问题, 可扩展性差 ;MPI 存在内存容量问题 ; MPI 数受限 ( 如 2 的幂次 ); MPI 实现的性能优化很弱, 而 OpenMP 实现效率很高 ;

16 中科院软件所并行计算实验室提纲无处不在的并行, 群核处理器普及并行程序设计语言的现状并行程序设计语言的发展趋势小结

17 新体系结构带来的挑战层次和混合并行 Clusters, SMPs, CMP ( 多核 ), SMT ( 同时多线程 ), 种类和范围更广泛的资源共享导致的潜在线程拥塞 ALU/FP 部件, cache, MCU, 数据通路, 存储带宽同构或异构显式的且更深的存储层次机器规模和扩展编译器不能自动挖掘多线程并行

18 并行编程模型的发展趋势

19 体系结构暴露的细节越来越多

20 20 可扩展并行编程概览当前的标准 :Fortran-77, Fortran-90 (2003), C, C++ 程序调用 MPI 和 OpenMP. 越来越多的使用 MPI-2, 特别是 I/O 消息传递模型和共享存储并行 PGAS 类语言 : UPC, Co-Array Fortran, 和 Titanium. 每个语言基于不同的基础语言 (C, Fortran-90, 和 Java ) 实现相似的编程模型固定数目进程, 全局数据视角, 但为性能显式的区分本地和远程数据 ; HPCS 类语言 : 无固定数目进程, 大量新的高级特点, 带局部性提示的全局数据视角 ;

21 发展历史 Fortran 95 Co-Array Fortran 由明尼苏达超级计算研究所和 NASA 的 Rober Numrich 对 Fortran 95 增加了并行扩展 Global Arrays 工具包发源于西北太平洋国家实验室提供 C, C++, Fortran, 和 Python 接口的库 ARMCI ( 单边通信库 ) 版本始于 1998 年. MPI, OpenMP, HPF 由加利福尼亚大学伯克利分校的 Yelick 教授领导 UPC (Unified parallel C) 由政府研究机构和 HPC 厂商组成的委员会由 GMU, IDA 和 NSA 协调 Titanium

22 GLOBAL ARRAYS 开发者 :Jarek Nieplocha, Robert Harrison and R. J. Littlefield 等 Pacific Northwest National Laboratory 年开源 ; May 版设计目标 : 弥补 MPI 的不足, 不是取代程序员可同时在程序里调用 MPI 和 GA; 是 PGAS 语言早期原型 ;

23 GLOBAL ARRAYS 的特点生成 / 管理全局数组结构的工具包物理上分布的数组可以通过共享存储风格的编程访问保留了数据局部性的挖掘不是语言的扩展, 而是库提供 Fortran, C, C++, Python 接口每个进程都有全局数组读写权访问数据不需要任务编号丰富的库函数调用 accumulate, scatter, gather, 外部线性代数接口 ScaLAPACK 等与 MPI 可互操作非阻塞通信影子单元库调用 (Ghost cell) 支持 SMP 节点的镜像数组

24 PGAS 语言分区的全局地址空间 Co-Array Fortran Titanium UPC 线程可直接读写远程数据数据有局部和全局的区分细节不同但内涵相似 SPMD 计算 ( 代码的本地视图 ) 用户提供数据和任务映射的细节通信和同步是显式的面向机群, 分布式存储 ; 可扩展性与 MPI 相当也许需要与 OpenMP 结合

25 UNIFIED PARALLEL C (UPC) v SPMD 显式并行全局地址空间语言 C 的扩展 (CAF 是对 Fortran 的扩展 ), 前身包括 AC, Split-C 和 Parallel C Preprocessor (PCP) An explicitly parallel execution model A shared address space Synchronization primitives and a memory consistency model Memory management primitives 共享存储被线程划分程序设计者分布数据通过读写共享变量进行单边通信, 显式同步全局地址空间 X[0] X[1] X[P] Shared Private

26 UPC 的优缺点全局地址空间容易编程通信通过表达式和赋值实现全局数据视角使得程序更容易阅读与串行 C 代码兼容通过调用 upc_forall( ) 共享存储编程风格程序员很容易参与性能优化缺点 : 并行度固定没有嵌套并行最好是一维并行划分!

CO-ARRAY 运行模型 Fortran 95 的扩展,2005 年成为正式标准 ; Numrich and Reid, Co-Array Fortran for Parallel Programming, ACM Fortran Forum, volume 17, no 2, pp 1-31,1998.

27 CO-ARRAY 运行模型 Fortran 95 的扩展,2005 年成为正式标准 ; Numrich and Reid, Co-Array Fortran for Parallel Programming, ACM Fortran Forum, volume 17, no 2, pp 1-31,1998. Numrich and Reid, Co-arrays in the next Fortran Standard, ACM Fortran Forum, volume 24, no 2, pp 4-17,2005. 固定数量的 images( 线程 ); (num_images(), this_image() ) 每份镜像独立执行相同的程序 ; 一个对象在每个镜像里的名字一样 ; 每份镜像操作自己的本地数据 ; 镜像只能通过显式的 co-array 语法将远程数据移动到本地 ; Cray T3E 和 Cray X1 Fortran 90 release 3.1

28 HPCS 语言高性能高生产率程序设计 Cray CHAPEL (Cascade High-Productivity Language) SUN Fortress IBM X10 研究型语言探索多种不同的新设计思想面向全局地址空间, 多线程平台高层次的可扩展全都解决局部性问题机器体系结构描述, 任务和计算到机器的映射试图降低同步开销原子块 / 事务

29 HPCS 语言 -X10 最根本目标 : 推动传统数值计算和商业计算高端计算机向可扩展高性能和高生产率的转变类型安全的现代并行分布式面向对象语言, 方便 Java 程序员使用目标机器未来基于多核 NUMA 存储层次的 SMP 节点和可扩展机群网络互联搭建的低端和高端计算系统属于 PGAS 家族通过 places 显式实现局部性控制 ; 通过 async, future, foreach 和 ateach 结构体现轻量级活动 ; 具有终止探测 (finish) 和分段计算 (clocks) 的结构 ; 可调用无锁同步 (atomic blocks); 可操纵全局数组和数据结构非分布式存储, 非共享存储, 分段式存储 Not Distributed Memory, Not Shared Memory,Fragmented Memory Model 全局异步, 本地同步 Globally Asynchronous, Locally Synchronous (GALS)

30 30 为何 MPI 如此难以超越? 制订过程的开放性全部邀请, 但需要艰苦工作所有的草案和代表全部开放第一个决定是不基于任何现存系统进行标准化可移植性没必要要求最小公倍数的方法 MPI 语义允许激进的实现无处不在 ; 可以在任何地方开发应用性能 MPI 可帮助管理存储层次集合操作可提供可扩展性可与优化编译器合作简单 MPI (i. e., MPI-2) 有 275 个函数 ; 也可以只用 6 个函数写出真正的应用

31 为何 MPI 如此难以超越 ( 续 )? 31 模块化 MPI 支持基于组件的带通信子的软件对库的支持意味着一些应用可以不进行任何 MPI 调用组件化 MPI 可以和其它工具一起工作 ( 编译器调试器和 profilers) 提供了与多线程程序的精确互动完整性可以编写任何并行算法在 MPI 里, 容易的事情未必总是容易但难得事情确实可能的透明性所见即所得厂商和开源社区的开发和研究在继续

32 未来十年甚至更长时间的展望从以处理器为中心转向以存储为中心 ; 开发和采用新的具有丰富并行性内置延迟隐藏机制内置可靠性管理低开销控制机制和自动负载均衡的计算模型 ; 符号计算超过数值计算 ; 传统处理器核被更细粒度的处理单元取代 ; 逻辑和存储单元的合并 ; 无需修理的计算机 : 系统自动重构降级 ; 几十亿到万亿级的并行度 ; 目标指导的自动程序设计计算机 ; 半导体技术之后的新技术

33 小结随着主频 Moor 定律接近极限, 采用多核并行的方式保持处理器性能的继续增长, 成为必由之路群核处理器的出现是否带来计算模式的根本变革? 群核处理器对程序设计模型提出了新的挑战, 需要思考如何解决和适应? 百花齐放众核处理器 GPGPU CPU+GPGPU 融合, 异构多核 ( 如 Cell), 数据流并行 TRIPS 处理器等都可能成为未来的主流处理器设计形式百家争鸣并发发掘细粒度同步和局部性描述将成为新一代并行程序设计模型研究的主要课题一些新的高生产率并行程序设计语言已经出现, 到底哪一个最后胜出, 目前尚不明朗库和框架, 如 TBB 和 MapReduce 等会成为过渡解决方案

34 谢谢! 本演讲部分内容参考了 HPCWPL 论文集和 BRIAN D. CARLSTROM,KARUSANKARALINGAM,AMD OWEN LIU, INTEL GANGSHAWU,WEN-MEIHWU, KATHY YELICK 等人的演讲材料

并行程序设计基础

并行程序设计基础 1800 1800 学计发软调术计术应软务 2 1. 论学 2. 实验学 3. 计学计学计学计动学计学计学计学计学计学计电学 3 4 ( 级计 ) CRAY, 银 I SMP( ) IBM p690 SUN MPP( 规 ) T3E 1000 HP ccnuma( 储 ) SGI Qrigin 统联腾 1800, IBM SP2