陈国良院士--并行计算模型研究方法：单一模型和分层模型

并行计算模型研究方法：单一模型和分层模型陈国良中国科技大学国家高性能计算中心（合肥）二零零九年十月ResearchingMethodologyofParallelComputationalModels:UnifiedModelandLayeredModel摘要并行计算模型是并行计算理论的重要研究内容。传统的并行计算模型实际上是专门为设计和分析并行算法的所谓单一计算模型。首先，我们根据并行计算机系统结构的发展演变提出了单一计算模型的分代研究方法：即第一代共享存储模型、第二代分布存储模型和第三代存储层次模型。然后，我们根据单一计算模型发展中所遇到的问题，提出了复合计算模型的分层研究方法：即并行计算模型应按并行算法设计、并行程序设计和并行程序执行等三个层次分开考虑，这样各个层次职能分工明确和目标单一，从而使模型易于操作和使用。我们认为：按照模型的功能和使用对象，将模型分层是势在必行，而分为三层是充分和必要的。其中并行算法设计模型和并行程序设计模型的研究已比较成熟，目前应集中力量研究和开发并行程序执行模型。目录1.引言1.1什么是并行计算模型1.2并行计算模型的发展历程2.单一计算模型的分代研究方法2.1第一代：共享存储模型2.2第二代：分布存储模型2.3第三代：存储层次模型3.单一模型的问题和分层模型的动机3.1单一计算模型遇到的问题3.2分层模型的基本出发点3.3分层计算模型的基本概念4.复合计算模型的分层研究方法4.1第一层：并行算法设计模型4.2第二层：并行程序设计模型4.3第三层：并行程序执行模型5.结论5.1观点、困难和设想5.2分层模型性能对照表2009-9-1131、引言1.1什么是并行计算模型•模型定义：是从计算的角度，呈献给算法设计者的一种不同结构并行机的虚拟抽象机是算法设计者和系统结构师之间的桥梁•模型三要素：一组反映计算性能的机器参数（CPM、存储器、I/O网路等）约束计算过程的计算行为（同步/异步等）一个计算算法复杂度的成本函数•计算三要素：数据的存储数据的计算数据的传输2009-9-1141.2并行计算模型的发展历程•模型为并行算法研究者所使用在某种模型上设计正确和最佳的并行算法依据模型，分析算法的复杂度（最坏和平均）•模型随主流并行机结构变化而演变共享存储的SIMD机器↔SIMD-SM模型不同互连结构的SIMD机器↔SIMD-IN模型共享存储的MIMD机器↔MIMD-SM模型分布存储的MIMD机器↔MIMD-DM模型分布共享存储的MIMD机器↔MIMD-DSM模型•模型沿着完善、强化单一模型功能的路线而发展起初，模型仅考虑了CPU参数（第一代模型）然后，模型要考虑了通信网络参数（第二代模型）最近，模型又考虑了存储访问特性（第三代模型）现在，在存储层次的基础上，又扩展到同时考虑层次并行特性2009-9-1152、单一计算模型的分代研究方法2.1第一代：共享存储模型•第一代计算模型的特点共享存储以“CPU计算为中心”计算、存储和通信合一锁步（自动同步）计算•代表性模型PRAM，包括EREW、CREW、CRCW和C-CRCW、P-CRCW、A-CRCWAPRAM，即异步PRAM模型•优缺点优点：适合于并行算法的表达和分析，理论计算机科学家使用缺点：高度抽象，不考虑细节，不实用2009-9-1162.2第二代：分布存储模型•第二代计算模型的特点分布式存储以“数据通信为中心”计算和通信分开考虑整体大同步和个体异步计算•代表性模型整体大同步模型BSP个体异步模型LogP非独占异构模型NHBL•优缺点优点：BSP模型大同步易于编程和确保计算的正确性LogP模型隐藏通信拓扑，只考虑点-点通信，易于分析缺点：BSP模型在一个超步内必须等待最慢计算者LogP模型设计和分析算法很困难2009-9-1172.3第三代：存储层次模型•第三代计算模型的特点分布共享存储以“数据访问为中心”计算和访存分开层次存储包括寄存器、高速缓存、主存和辅存等•代表性模型均匀存储层次模型UMH分布的RAM模型DRAM(h,k)（h级存储层次、k种并行方式）基于LogP的存储层次模型Memory-LogP同时考虑层次存储和层次并行模型HPM•优缺点优点：反映当代并行机体系结构多存储层次的特点和多级并行度的特点缺点：分析过于复杂，难以操作使用2009-9-1183、单一模型的问题和分层模型的动机3.1单一计算模型遇到的困境•模型本身一味追求单一模型的功能强和多目标，致使单一模型越来越复杂，最终导致模型不实用和不可操作性。单一模型中，反映机器不同特性的参数过多，致使单一模型描述越来越困难，最终导致成本函数过于复杂而无法求解。当在单一模型中又考虑到机器的底层特性和不同的硬件并行度时，致使该模型很难建立。•模型的使用：对算法设计者而言，单一模型太复杂，设计算法时考虑的因素过多，影响设计低时空开销的优秀算法；对程序设计者而言，编程模型要简洁，才能确保算法的正确编程实现；而对程序执行者而言，尽管单一模型似乎很精确，但对程序执行时性能的优化却又缺乏足够的制导信息。2009-9-1193.2分层计算模型的基本出发点•模型应按算法设计、算法实现和算法执行进行分层：算法设计应建立在并行算法设计模型上；算法实现应通过并行程序设计模型来完成；算法执行应由并行系统的软/硬件来支撑。•分层好处：分层计算模型可将单一模型中的功能按要求分配到模型不同的层次中，缓解了单一计算模型的精确性与可使用性之间的矛盾。分层后，各层次模型职能不同，目标单一，各负其责，易于设计与实现。2009-9-11103.3分层计算模型的基本概念•三层并行计算模型：并行算法设计模型，并行程序设计模型和并行程序执行模型。前者是面向并行算法研究者的，中者是面向并行程序设计者的，后者是面向程序运行者的。•三层并行计算模型从几何形状上看，呈现哑铃形状：从不同的并行计算机来(抽象计算参数建立模型)，经过不同的加工后，又回到不同的并行计算机中去(运行代码，求解问题)。三层并行计算模型的图示可如下页所示。2009-9-1111并行机k并行机1并行机n并行算法设计模型并行机k并行机1并行机n并行程序设计模型并行程序执行模型并行算法设计层(面向算法研究者)并行算法实现层(面向程序设计者)并行算法运行层(面向程序执行者)从不同的并行机中抽象出计算参数建立并行算法设计模型根据并行机的软/硬件接口利用并行程序语言编程实现具体并行算法在各并行机系统软/硬件支撑下编译运行目标代码优化程序的实际性能2009-9-1112•三层并行计算模型的功能划分并行算法设计模型：它是算法设计者和计算机体系结构家之间的桥梁，主要用来指导并行算法的设计与分析。并行程序设计模型：它是程序设计者与计算机软/硬件之间的接口，主要负责把算法转换成可在并行机上正确执行的程序。并行程序执行模型：它是编译设计者与系统实现者之间的接口，编程人员在并行机软/硬件支撑下，编译和运行机器目标代码，以优化程序的性能。2009-9-11134、复合计算模型的分层研究方法4.1第一层：并行算法设计模型•算法设计模型需要反映硬件关键特性同时又必须非常简单易于算法描述和表达，是算法设计者与机器结构家之间的桥梁，是面向算法研究者的。•算法设计模型重点关注算法的原理，确保设计出来的算法的正确性和较低的时间、空间复杂度。•算法设计模型三要素：机器参数：抽象的CPU，Memory，I/O网络参数执行行为：同步/异步成本函数：它是机器参数的函数2009-9-1114•算法复杂性度量单位：算法步数•算法设计模型支撑条件：硬件平台，软件环境，理论基础•现有的算法设计模型：共享存储的同步PRAM模型共享存储的异步APRAM模型分布式存储的BSP，LogP模型考虑存储层次的UMH，DRAM(h)模型等2009-9-11154.2第二层：并行程序设计模型•程序设计模型对程序员提供了一些计算机软/硬件的编程接口，隐藏了通信和任务调度的细节，在一定程度上简化了并行程序的编写，是面向程序设计者的。•程序设计模型主要确保并行算法使用某种程序语言可以正确的在并行计算机上编程实现。•程序设计模型三要素：任务/数据划分进程/线程分配通信与同步2009-9-1116•程序设计复杂性度量单位：高级语言条数•程序设计模型支撑条件高级语言标准的程序库编程接口框架•当今流行的并行程序设计模型：主要有大粒度的进程级的消息传递模型，如MPI中、细粒度的线程级的共享变量模型，如OpenMP细粒度进程级的数据并行模型，如HPF。2009-9-11174.3第三层：并行程序执行模型•程序执行模型是编译器设计人员与系统实现人员之间的接口编译器设计人员决定如何将一种高级语言程序按某种程序执行模型转换成一种目标机器语言程序；系统实现人员则决定该程序执行模型在具体目标机器上的有效实现。•程序执行三要素：机器性能参数运行时系统行为性能指标•程序执行复杂性度量单位：机器指令条数2009-9-1118•程序执行模型中的三种并行性：任务级并行：考虑任务划分，任务映射，任务调度数据级并行：考虑数据划分，迭代和循环分解指令级并行：主要考虑如何高效发挥向量流水线，多发射，执行预取的效率等。•程序执行模型中性能评价标准：执行时间加速和效率可扩展性•支撑条件：软件支持：操作系统，编译器，工具环境硬件支持：CPU系统，Memory系统，I/O系统•并行程序的性能是以下因素的综合体现：算法、实现、编译器、操作系统、处理器体系结构、网络互连技术，因此实际程序的执行行为相当复杂。2009-9-11195、结论5.1观点、困难和设想•我们的观点根据并行计算模型的发展和演变，现今对并行计算模型进行分层是势在必行的。按照并行计算模型的功能和使用的对象，模型分为三个层次，是充分和必要的。并行算法设计模型和并行程序设计模型，目前相对比较成熟，而并行程序执行模型尚处于酝酿阶段，有待进一步研究与开发。2009-9-1120•目前的困难研究并行程序执行模型，究竟应如何下手，其基本框架大体是什么样的？并行程序执行模型，可否比照并行算法设计模型和并行程序设计模型那样来定量描述？研究并行程序的性能优化应着眼于计算机的系统软件（比如OS与编译等）或计算机的底层硬件？•我们的设想研究并行程序的执行模型，仍应借鉴和参考“程序性能优化”的研究方法。先确定出并行程序执行模型的粗框架，哪怕是非常粗糙和不完整的。在此粗框架上，进行实例研究，总结经验，反复修正之。2009-9-11215.2分层模型性能对照表2009-9-1122名称并行算法设计模型并行程序设计模型并行程序执行模型面向对象算法设计者编程者程序运行者作用算法设计者和机器结构设计者之间桥梁程序设计者与计算机软/硬之间接口编译设计者与系统实现者之间接口关注点算法正确性低时、空开销确保算法正确语义正确编程实现优化程序执行性能要素机器计算参数计算行为计算复杂度函数程序结构(编程模式)数据结构(共享/分布)可扩展，通用泛化机器性能参数运行时系统行为性能指标5.2分层模型性能对照表（续）2009-9-1123名称并行算法设计模型并行程序设计模型并行程序执行模型方法学设计方法（划分，分治，流水线，平衡树，…）编程风范（SPMD,循环并行,主从法MPMD,Fork/Join,放牧法,流水线法,…）执行模式（线程/进程产生,管理与撤消;同步;通信)复杂度算法步数高级语言条数机器指令条数支撑条件硬件平台软件支撑算法理论并行语言工具环境应用编程接口API编译器OS运行时系统硬件结构(CPU,Memory,I/O)现有模型PRAM,APRAM,BSP,logP,NHBL,UMH,DRAM(h)OpenMP,MPI,HPF？2009-9-1124