一种跨平台的并行编程框架设计与实现

李 婷，徐 云，聂鹏宇，潘玮华

(1.国家高性能计算中心(合肥)，合肥 230027;2.中国科学技术大学计算机科学与技术学院，合肥 230027)

1 概述

并行化计算已经成为提高计算性能的主流方向，多种并行计算平台也应运而生。传统并行计算平台有多核CPU、大规模并行处理机和工作站机群等［1］。为满足不同行业的计算需求，多种专用并行平台也迅速发展，如现场可编程门阵列(Field Programmable Gate Array，FPGA)和通用图形处理器(General Purpose Computing on GPU，GPGPU)［2-3］。然而，由于并行程序的行为模式比传统的串行程序更为复杂，使得并行程序的编写、调试和优化都更加困难。同时，并行计算平台的多样化和硬件的升级，对程序的可移植性提出了严峻挑战。

为了解决以上问题，人们尝试从不同平台上并行程序的行为模式中抽象出并行编程模型，并将其表达成易理解、易操作的编程框架。并行编程框架是将并行编程模型以API、编程规范等形式表达出来，并提供相应的函数库、编译系统等底层支持的编程库或工具集(toolkit)，其目的在于对程序员隐藏底层细节，降低并行程序开发的难度。传统的并行编程框架如OpenMP［4］、MPICH［5］等已不能适应硬件的发展和多样化的计算需求。并行编程框架的研究，向着专业性、可移植性、混合编程等多种方向发展。

为了实现并行程序的可移植性，简化上层并行程序的开发，并能灵活适用于不同计算需求和硬件变化，本文设计并实现了一种跨平台、分层次、可扩展的并行编程框架OpenCH。框架以并行函数库的形式和层次化的API 设计对上层应用程序的开发隐藏了底层计算平台的差异和并行化细节，使得没有经过并行编程训练的开发人员可以按照串行程序开发的模式快速开发并行程序。基于该框架开发的并行程序可以不加修改地运行于共享存储平台、分布式存储平台和GPGPU。为了进一步简化函数库的开发，本文给出一种填充式并行编程工具。

2 相关研究

目前并行编程框架的研究主要有:

(1)基于并行函数库的编程框架。提供一套并行函数库，通过相应的API 接口对上层开发人员隐藏程序的并行化细节。由北京应用物理与计算数学研究所开发的并行自适应结构网格应用支撑软件框架(JASMIN［6］)是一套基于普适的数值计算函数库和面向具体问题的物理模型函数库的并行编程框架，适用于大型科学计算，尤其是物理过程模拟的高性能程序开发。

(2)针对特殊计算平台、异构平台及混合编程的框架［7］。英伟达公司为其品牌下GPGPU 产品开发编程工具CUDA［8］，使开发人员可以用C/C++的语法规则编写运行在设备上的程序，同时还为“主机-设备”异构计算平台上的程序开发提供了统一的编程环境。

(3)跨平台、可移植的编程框架。苹果公司于2008 年提出了一个适用于异构计算平台的并行编程语 言 OpenCL (Open Computing Language)［9］。OpenCL 对不同的运算平台进行抽象，并建立一个通用的编程模型。开发者遵循OpenCL 标准编写的程序，可以不加修改或稍作修改地运行于其他支持OpenCL 标准的硬件平台上。

(4)面向具体应用领域的编程框架。根据具体应用问题的计算需求，提供更有针对性的并行编程工具。斯坦福大学设计实现的分子动力学模拟编程框架OpenMM［10］，不仅提供了专业的、跨平台的并行函数库，并且以面向对象的方式对分子动力学系统做了直观的描述。MapReduce 是适用于大数据处理的编程模型，该模型的具体实现有Google 公司的MapReduce 系统［11］和Apache 开源项目Hadoop 系统的MapReduce 模块［12］。

(5)其他研究方向。如:可视化编程框架［13］，自动代码转换［14］，强调性能优化的编程框架［15-16］。

以上列出的很多编程框架都结合了不止一种设计思想。例如OpenMM 即是面向分子动力学模拟领域的专业系统，又是一个跨平台的，基于并行函数库的编程框架。本文所介绍的编程框架OpenCH 是一个基于并行函数库的，跨平台、可移植的并行编程框架，可通过二次开发使其成为一个面向具体问题的专业编程工具;同时向函数库开发人员提供了一种填充式并行开发工具。

3 OpenCH 并行编程框架的设计与实现

本文的并行编程框架有以下设计目标:

(1)降低并行编程的难度。上层应用程序开发人员即使没有经过并行编程训练，也可以按照串行程序开发的模式快速开发并行程序。

(2)可移植性。当计算平台发生变化时，应用程序无需做任何修改即可在新的平台上高效运行。

(3)编程框架是可扩展的。根据不同的应用领域和计算需求，可对面向问题的函数库进行扩展和定制。并且可扩展计算平台支持以适应计算平台的升级和对新的计算平台的需求。

(4)简化并行函数库的开发。

3.1 并行编程框架的层次模型

OpenCH 采用了层次化的结构设计，分为平台无关的上层API 和平台相关的下层API，如图1 所示。

图1 编程框架的层次模型

上层API 是用户在编写应用程序时调用的函数接口，是平台无关的。下层API 由三层平台相关的函数库组成，包括面向问题的函数库、通用函数库、平台支持功能库。面向问题的函数库是面向特殊应用领域的并行函数库。通用函数库提供常用的数值计算和机器学习等算法的并行化实现，可以被面向问题的函数库和上层应用程序调用。平台支持功能库提供对计算平台信息进行查询和维护的接口，并向通用函数库和面向问题的函数库提供平台相关的调度与优化功能。

系统的函数库架构在现有的并行编程框架之上，横向上分为OpenMP 库、MPI 库和CUDA 库，可运行于共享存储系统、分布存储系统和GPGPU 等计算平台。函数库中每个函数在OpenMP、MPI 和CUDA子库中都有相应的实现。上层API 将运行于不同计算平台的底层函数封装在一个统一的接口下。例如，对于上层API 中的函数接口MatrixMul (A，B，C)，在下层API 中分别有以下3 种实现:

(1)MatrixMul_OMP(A，B，C):OpenMP 实现，可运行于共享存储计算平台;

(2)MatrixMul_MPI(A，B，C):MPI 实现，可运行于分布式存储计算平台;

(3)MatrixMul_CUDA(A，B，C):CUDA 实现，可运行于GPGPU 计算平台。

当上层API 被调用时，系统依据用户对计算平台设置，将用户的调用自动映射到相应的下层函数。这样的层次化设计使得底层计算环境的差异对上层应用程序完全透明，完全交由中间的函数映射策略处理。当程序运行环境发生变化时，不需要对程序做任何改动，只需通过系统设置接口修改平台设置即可将函数调用映射到正确的底层库中，使程序在新的计算平台上运行。

3.2 并行函数库的填充式开发

为了使并行函数库的开发工作更加简单和规范，本文设计并实现了一种填充式开发工具。

对于大多数数据并行程序来说，并行域中每个线程内的逻辑是串行的。各线程只需要知道自己所处理的数据，即可串行地对数据执行线程内的操作;对于不同线程执行不同操作的情况，各线程只需要依据自己的线程ID 决定相应的操作，不受其他线程行为的影响。基于以上事实，本文设计一种填充式的并行程序开发方法。开发人员可以无需考虑多线程程序的整体行为，只需分别实现并行域线程内串行程序和并行域外的串行程序，并设置数据的划分与调度方式，即可完成并行程序的开发。系统将自动完成并行域的启动终止和子过程间的同步，并负责向各线程传递线程编号和调度信息。

为实现以上方法，本文设计了如图2 所示的树形模板。

根模板是所有库函数的共同基础节点。根模板向下派生出针对各计算平台的OpenMP 模板、MPI 模板和CUDA 模板。这一层模板中定义了相应平台上并行程序的抽象结构，以及程序间的共同属性和行为，包括:数据域，任务调度器，并行域的启动与终止，子过程间的同步，线程编号和调度信息的传递。平台基础模板向下派生出函数的具体实现，开发人员在这一层以填充的方式定义函数的特殊属性和行为，共性的部分自动从平台基础模板中继承。

图2 填充式编程的树形模板

图3 展示了OpenMP 模板和MPI 模板的结构。一个OpenMP 程序可以抽象为一个或多个顺序执行或嵌套执行的fork-join 子程序，每个子程序的结构如图3(a)所示。图中所示的数据与变量被所有线程共享。Preprocess 过程包括变量声明、内存分配等预处理过程和其他前期计算;Fork 过程是并行区域每个线程所执行的代码;Join 过程是退出并行域后的后期计算和内存回收等操作。主过程负责在各子过程之间进行并行域的启动与退出，子过程之间的同步，和必要的参数传递。MPI 模板的结构如图3(b)所示。数据与变量存储于各节点的本地内存中。Preprocess 过程包括数据预处理、本地内存分配和其他前期计算工作。这部分程序中各节点独立运行，不需要进行交互，系统结构对各节点透明。Cooperate 过程对应于OpenMPI 程序中MPI_INIT 和MPI_FINALIZE 之间的部分。在此阶段系统结构对各节点是可见的，每个节点需要知道自己在整个系统中的位置和其他节点的位置，各节点间以消息传递的方式进行通信。Postprocess 过程中各节点独立运行，主要包括本地内存的回收等操作。主过程负责MPI 环境的启动和终止、子过程间的同步和调度信息的传递等操作。

每个模板中都维护一个任务调度器。OpenMP和MPI 任务调度器主要实现以下功能:

(1)将数据、任务和线程表示成三维阵列的形式，提供三维索引和一维索引相互转换的功能。

(2)按照用户指令或依据平台参数自动选择或设置任务和线程的结构。

(3)根据任务和线程结构，将数据静态地划分为任务阵列，并将任务静态地分配到各线程，为每个线程维护一个任务队列，保证负载均衡。

(4)用户和主动定义和更改每个线程的任务队列。

(5)OpenMP 任务调度器可实现动态调度。任务调度器生成一个全局的任务队列，并动态地将队列中的任务分配给请求任务的空闲线程。

图3 模板结构

基于CUDA 的程序有着特殊的程序结构，与host/device 混合编程模型相适应。该系统保留了CUDA 程序的原始结构。

这种填充式的开发方式适用于采用数据并行模式，各进程相对独立，进程间数据依赖性小的并行程序开发。为兼顾函数设计的灵活性，用户有权在函数实现时重载基础模板中的某些属性和行为。

4 OpenCH 的应用

图像处理的并行化是典型的数据并行问题，进程间没有复杂的依赖关系。以基于k-means 算法的遥感影像非监督分类为例，测试编程框架的有效性。

实验中OpenMP 函数库和MPI 函数库运行的平台为Intel CoreTM i5-2400 CPU(3.10 GHz，4 核);CUDA 函数库运行平台为NVIDIA GeForce GT 530 GPU。实验所用数据为对地遥感卫星Landsat-7 于2000 年6 月14 日获取的长江三角洲地区的ETM +数据［17］。ETM+数据共有8 个波段。实验选取蓝、绿、红、近红外、中红外(1.55～1.75)、中红外(2.09～2.35)共6 个波段作为特征空间。本文按照系统规范分别建立了实验所需的OpenMP，MPI 和CUDA 函数库，并建立了统一的上层API 作为应用程序调用库函数的唯一接口。通过平台设置接口改变计算平台的设置，使程序运行于不同的计算平台之上。实验程序的实现包括以下4 个部分:

(1)应用程序

Main()应用程序主程序

(2)上层API

kmeans_RSclassification()公共函数接口

(3)下层API(面向问题的函数接口)

基于k-means 的遥感影像分算法，分别运行于OpenMP、MPI 和CUDA 计算平台

(4)下层API(通用函数接口)

提供通用的k-means 聚类算法，分别运行于OpenMP、MPI 和CUDA 计算平台。

图4 为原始影像与分类结果。实验分别比较了基于OpenCH 编程框架开发的程序与不使用OpenCH的OpenMP、MPI、CUDA 程序的运行时间，如图5、图6、表1 所示。所有实验使用相同的参数和初始聚类中心，保证相同的迭代过程和计算结果。从实验结果看出，基于该框架开发的程序成功运行于不同计算平台之上，并且取得了与不使用框架的程序相近的性能和并行加速效果。使用编程框架本身造成的时间开销在3.2%～13.6%之间，主要来自于多层函数间的映射和调用以及任务调度器的开销等。

图4 分类效果

图5 OpenMP 程序时间性能比较

图6 MPI 程序时间性能比较

表1 CUDA 程序性能比较

5 结束语

本文介绍一种新的并行编程框架OpenCH。该框架具有如下特点:上层应用程序开发人员通过调用平台无关的API 接口开发并行程序，无需关注并行化细节，降低了并行编程难度。通过层次化的API 设计，使得底层平台的细节对上层应用程序透明，程序可无需修改地运行于多种计算平台。针对底层函数库的开发，设计并实现了一种填充式的编程方法。该方法适用于线程间独立性强的数据并行算法。并行函数库和支持的计算平台是可扩展的，能够适应新的计算需求和增加对新的计算平台的支持。实验结果证明该框架可有效简化并行程序的开发，并获得了良好的性能。

本文下一步的工作包括:(1)进一步丰富通用函数库;(2)丰富任务调度器的功能，实现MPI 的动态调度功能;(3)使该编程框架支持多个计算平台的混合编程。

［1］陈国良，安 虹，陈 峻，等.并行算法实践［M］.北京:高等教育出版社，2004.

［2］张 舒，褚艳利.GPU 高性能运算之CUDA［M］.北京:中国水利水电出版社，2009.

［3］Owens J D，Houston M，Luebke D，et al.GPU Computing［J］.Proceedings of the IEEE，2008，96(5):879-899.

［4］Dagum L，Menon R.OpenMP:An Industry Standard API for Shared-memory Programming ［J］.IEEE Computational Science and Engineering，1998，5(1):46-55.

［5］Gropp W.MPICH2:A New Start for MPI Implementations［C］//Proceedings of the 9th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface.London，UK:Springer-Verlag，2002:215-222.

［6］Mo Zeyao，Zhang Aiqing，Cao Xiaolin.JASMIN:A Parallel Software Infrastructure for Scientific Computing［J］.Frontiers of Computer Science in China，2010，4(4):480-488.

［7］Linderman M D，Collins J D，Wang Hong，et al.Merge:A Programming Model for Heterogeneous Multi-core Systems［C］//Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems.New York，USA:ACM Press，2008:521-531.

［8］NVIDIA Corporation.Cuda C Programming Guide［Z］.2012.

［9］Stone J E，Gohara D，Shi Guochun.OpenCL:A Parallel Programming Standard for Heterogeneous Computing Systems［J］.Computing in Science and Engineering，2010，12(3):66-73.

［10］Eastman P，Pande V S.OpenMM:A Hardwareindependent Framework for Molecular Simulations［J］.Computing in Science ＆ Engineering，2010，12 (4):34-39.

［11］Dean J，Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters［J］.Communications of the ACM，2008，51(1):107-113.

［12］White T.Hadoop:The Definitive Guide［M］.［S.1］:O'Reilly Media，Inc.，2012.

［13］Devin F，Boulet P，Dekeyser J L，et al.GASPARD:A Visual Parallel Programming Environment ［C］//Proceedings of International Conference on Parallel Computing in Electrical Engineering.Warsaw，Poland:IEEE Computer Society，2002:457-467.

［14］Acosta A，Almeida F，Peláez I.High-level Specifications for Automatically Generating Parallel Code ［J］.Concurrency and Computation Practice and Experience，2013，25(7):989-1012.

［15］Mariani G，Palermo G，Silvano C，et al.Arte:An Application-specific Run-time Management Framework for Multi-core Systems［C］//Proceedings of the 9th IEEE Symposium on Application Specific Processors.San Diego，USA:IEEE Computer Society，2011:326-334.

［16］Cole M.Bringing Skeletons Out of the Closet:A Pragmatic Manifesto for Skeletal Parallel Programming［J］.Parallel Computing，2004，30(3):389-406.

［17］USGC.Landsat Enhanced Thematic M apper Plus［EB/OL］.［2012-01-24］.https://lta.cr.usgs.gov/LETM P.