一種跨平臺的并行編程框架設計與實現

李 婷，徐 云，聶鵬宇，潘瑋華

(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.