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

(1.國家高性能計算中心(合肥)，合肥 230027;2.中國科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，合肥 230027)

1 概述

并行化計算已經(jīng)成為提高計算性能的主流方向，多種并行計算平臺也應(yīng)運而生。傳統(tǒng)并行計算平臺有多核CPU、大規(guī)模并行處理機和工作站機群等［1］。為滿足不同行業(yè)的計算需求，多種專用并行平臺也迅速發(fā)展，如現(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)和通用圖形處理器(General Purpose Computing on GPU，GPGPU)［2-3］。然而，由于并行程序的行為模式比傳統(tǒng)的串行程序更為復(fù)雜，使得并行程序的編寫、調(diào)試和優(yōu)化都更加困難。同時，并行計算平臺的多樣化和硬件的升級，對程序的可移植性提出了嚴峻挑戰(zhàn)。

為了解決以上問題，人們嘗試從不同平臺上并行程序的行為模式中抽象出并行編程模型，并將其表達成易理解、易操作的編程框架。并行編程框架是將并行編程模型以API、編程規(guī)范等形式表達出來，并提供相應(yīng)的函數(shù)庫、編譯系統(tǒng)等底層支持的編程庫或工具集(toolkit)，其目的在于對程序員隱藏底層細節(jié)，降低并行程序開發(fā)的難度。傳統(tǒng)的并行編程框架如OpenMP［4］、MPICH［5］等已不能適應(yīng)硬件的發(fā)展和多樣化的計算需求。并行編程框架的研究，向著專業(yè)性、可移植性、混合編程等多種方向發(fā)展。

為了實現(xiàn)并行程序的可移植性，簡化上層并行程序的開發(fā)，并能靈活適用于不同計算需求和硬件變化，本文設(shè)計并實現(xiàn)了一種跨平臺、分層次、可擴展的并行編程框架OpenCH?？蚣芤圆⑿泻瘮?shù)庫的形式和層次化的API 設(shè)計對上層應(yīng)用程序的開發(fā)隱藏了底層計算平臺的差異和并行化細節(jié)，使得沒有經(jīng)過并行編程訓(xùn)練的開發(fā)人員可以按照串行程序開發(fā)的模式快速開發(fā)并行程序。基于該框架開發(fā)的并行程序可以不加修改地運行于共享存儲平臺、分布式存儲平臺和GPGPU。為了進一步簡化函數(shù)庫的開發(fā)，本文給出一種填充式并行編程工具。

2 相關(guān)研究

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

(1)基于并行函數(shù)庫的編程框架。提供一套并行函數(shù)庫，通過相應(yīng)的API 接口對上層開發(fā)人員隱藏程序的并行化細節(jié)。由北京應(yīng)用物理與計算數(shù)學(xué)研究所開發(fā)的并行自適應(yīng)結(jié)構(gòu)網(wǎng)格應(yīng)用支撐軟件框架(JASMIN［6］)是一套基于普適的數(shù)值計算函數(shù)庫和面向具體問題的物理模型函數(shù)庫的并行編程框架，適用于大型科學(xué)計算，尤其是物理過程模擬的高性能程序開發(fā)。

(2)針對特殊計算平臺、異構(gòu)平臺及混合編程的框架［7］。英偉達公司為其品牌下GPGPU 產(chǎn)品開發(fā)編程工具CUDA［8］，使開發(fā)人員可以用C/C++的語法規(guī)則編寫運行在設(shè)備上的程序，同時還為“主機-設(shè)備”異構(gòu)計算平臺上的程序開發(fā)提供了統(tǒng)一的編程環(huán)境。

(3)跨平臺、可移植的編程框架。蘋果公司于2008 年提出了一個適用于異構(gòu)計算平臺的并行編程語 言 OpenCL (Open Computing Language)［9］。OpenCL 對不同的運算平臺進行抽象，并建立一個通用的編程模型。開發(fā)者遵循OpenCL 標準編寫的程序，可以不加修改或稍作修改地運行于其他支持OpenCL 標準的硬件平臺上。

(4)面向具體應(yīng)用領(lǐng)域的編程框架。根據(jù)具體應(yīng)用問題的計算需求，提供更有針對性的并行編程工具。斯坦福大學(xué)設(shè)計實現(xiàn)的分子動力學(xué)模擬編程框架OpenMM［10］，不僅提供了專業(yè)的、跨平臺的并行函數(shù)庫，并且以面向?qū)ο蟮姆绞綄Ψ肿觿恿W(xué)系統(tǒng)做了直觀的描述。MapReduce 是適用于大數(shù)據(jù)處理的編程模型，該模型的具體實現(xiàn)有Google 公司的MapReduce 系統(tǒng)［11］和Apache 開源項目Hadoop 系統(tǒng)的MapReduce 模塊［12］。

(5)其他研究方向。如:可視化編程框架［13］，自動代碼轉(zhuǎn)換［14］，強調(diào)性能優(yōu)化的編程框架［15-16］。

以上列出的很多編程框架都結(jié)合了不止一種設(shè)計思想。例如OpenMM 即是面向分子動力學(xué)模擬領(lǐng)域的專業(yè)系統(tǒng)，又是一個跨平臺的，基于并行函數(shù)庫的編程框架。本文所介紹的編程框架OpenCH 是一個基于并行函數(shù)庫的，跨平臺、可移植的并行編程框架，可通過二次開發(fā)使其成為一個面向具體問題的專業(yè)編程工具;同時向函數(shù)庫開發(fā)人員提供了一種填充式并行開發(fā)工具。

3 OpenCH 并行編程框架的設(shè)計與實現(xiàn)

本文的并行編程框架有以下設(shè)計目標:

(1)降低并行編程的難度。上層應(yīng)用程序開發(fā)人員即使沒有經(jīng)過并行編程訓(xùn)練，也可以按照串行程序開發(fā)的模式快速開發(fā)并行程序。

(2)可移植性。當計算平臺發(fā)生變化時，應(yīng)用程序無需做任何修改即可在新的平臺上高效運行。

(3)編程框架是可擴展的。根據(jù)不同的應(yīng)用領(lǐng)域和計算需求，可對面向問題的函數(shù)庫進行擴展和定制。并且可擴展計算平臺支持以適應(yīng)計算平臺的升級和對新的計算平臺的需求。

(4)簡化并行函數(shù)庫的開發(fā)。

3.1 并行編程框架的層次模型

OpenCH 采用了層次化的結(jié)構(gòu)設(shè)計，分為平臺無關(guān)的上層API 和平臺相關(guān)的下層API，如圖1 所示。

圖1 編程框架的層次模型

上層API 是用戶在編寫應(yīng)用程序時調(diào)用的函數(shù)接口，是平臺無關(guān)的。下層API 由三層平臺相關(guān)的函數(shù)庫組成，包括面向問題的函數(shù)庫、通用函數(shù)庫、平臺支持功能庫。面向問題的函數(shù)庫是面向特殊應(yīng)用領(lǐng)域的并行函數(shù)庫。通用函數(shù)庫提供常用的數(shù)值計算和機器學(xué)習(xí)等算法的并行化實現(xiàn)，可以被面向問題的函數(shù)庫和上層應(yīng)用程序調(diào)用。平臺支持功能庫提供對計算平臺信息進行查詢和維護的接口，并向通用函數(shù)庫和面向問題的函數(shù)庫提供平臺相關(guān)的調(diào)度與優(yōu)化功能。

系統(tǒng)的函數(shù)庫架構(gòu)在現(xiàn)有的并行編程框架之上，橫向上分為OpenMP 庫、MPI 庫和CUDA 庫，可運行于共享存儲系統(tǒng)、分布存儲系統(tǒng)和GPGPU 等計算平臺。函數(shù)庫中每個函數(shù)在OpenMP、MPI 和CUDA子庫中都有相應(yīng)的實現(xiàn)。上層API 將運行于不同計算平臺的底層函數(shù)封裝在一個統(tǒng)一的接口下。例如，對于上層API 中的函數(shù)接口MatrixMul (A，B，C)，在下層API 中分別有以下3 種實現(xiàn):

(1)MatrixMul_OMP(A，B，C):OpenMP 實現(xiàn)，可運行于共享存儲計算平臺;

(2)MatrixMul_MPI(A，B，C):MPI 實現(xiàn)，可運行于分布式存儲計算平臺;

(3)MatrixMul_CUDA(A，B，C):CUDA 實現(xiàn)，可運行于GPGPU 計算平臺。

當上層API 被調(diào)用時，系統(tǒng)依據(jù)用戶對計算平臺設(shè)置，將用戶的調(diào)用自動映射到相應(yīng)的下層函數(shù)。這樣的層次化設(shè)計使得底層計算環(huán)境的差異對上層應(yīng)用程序完全透明，完全交由中間的函數(shù)映射策略處理。當程序運行環(huán)境發(fā)生變化時，不需要對程序做任何改動，只需通過系統(tǒng)設(shè)置接口修改平臺設(shè)置即可將函數(shù)調(diào)用映射到正確的底層庫中，使程序在新的計算平臺上運行。

3.2 并行函數(shù)庫的填充式開發(fā)

為了使并行函數(shù)庫的開發(fā)工作更加簡單和規(guī)范，本文設(shè)計并實現(xiàn)了一種填充式開發(fā)工具。

對于大多數(shù)數(shù)據(jù)并行程序來說，并行域中每個線程內(nèi)的邏輯是串行的。各線程只需要知道自己所處理的數(shù)據(jù)，即可串行地對數(shù)據(jù)執(zhí)行線程內(nèi)的操作;對于不同線程執(zhí)行不同操作的情況，各線程只需要依據(jù)自己的線程ID 決定相應(yīng)的操作，不受其他線程行為的影響。基于以上事實，本文設(shè)計一種填充式的并行程序開發(fā)方法。開發(fā)人員可以無需考慮多線程程序的整體行為，只需分別實現(xiàn)并行域線程內(nèi)串行程序和并行域外的串行程序，并設(shè)置數(shù)據(jù)的劃分與調(diào)度方式，即可完成并行程序的開發(fā)。系統(tǒng)將自動完成并行域的啟動終止和子過程間的同步，并負責向各線程傳遞線程編號和調(diào)度信息。

為實現(xiàn)以上方法，本文設(shè)計了如圖2 所示的樹形模板。

根模板是所有庫函數(shù)的共同基礎(chǔ)節(jié)點。根模板向下派生出針對各計算平臺的OpenMP 模板、MPI 模板和CUDA 模板。這一層模板中定義了相應(yīng)平臺上并行程序的抽象結(jié)構(gòu)，以及程序間的共同屬性和行為，包括:數(shù)據(jù)域，任務(wù)調(diào)度器，并行域的啟動與終止，子過程間的同步，線程編號和調(diào)度信息的傳遞。平臺基礎(chǔ)模板向下派生出函數(shù)的具體實現(xiàn)，開發(fā)人員在這一層以填充的方式定義函數(shù)的特殊屬性和行為，共性的部分自動從平臺基礎(chǔ)模板中繼承。

圖2 填充式編程的樹形模板

圖3 展示了OpenMP 模板和MPI 模板的結(jié)構(gòu)。一個OpenMP 程序可以抽象為一個或多個順序執(zhí)行或嵌套執(zhí)行的fork-join 子程序，每個子程序的結(jié)構(gòu)如圖3(a)所示。圖中所示的數(shù)據(jù)與變量被所有線程共享。Preprocess 過程包括變量聲明、內(nèi)存分配等預(yù)處理過程和其他前期計算;Fork 過程是并行區(qū)域每個線程所執(zhí)行的代碼;Join 過程是退出并行域后的后期計算和內(nèi)存回收等操作。主過程負責在各子過程之間進行并行域的啟動與退出，子過程之間的同步，和必要的參數(shù)傳遞。MPI 模板的結(jié)構(gòu)如圖3(b)所示。數(shù)據(jù)與變量存儲于各節(jié)點的本地內(nèi)存中。Preprocess 過程包括數(shù)據(jù)預(yù)處理、本地內(nèi)存分配和其他前期計算工作。這部分程序中各節(jié)點獨立運行，不需要進行交互，系統(tǒng)結(jié)構(gòu)對各節(jié)點透明。Cooperate 過程對應(yīng)于OpenMPI 程序中MPI_INIT 和MPI_FINALIZE 之間的部分。在此階段系統(tǒng)結(jié)構(gòu)對各節(jié)點是可見的，每個節(jié)點需要知道自己在整個系統(tǒng)中的位置和其他節(jié)點的位置，各節(jié)點間以消息傳遞的方式進行通信。Postprocess 過程中各節(jié)點獨立運行，主要包括本地內(nèi)存的回收等操作。主過程負責MPI 環(huán)境的啟動和終止、子過程間的同步和調(diào)度信息的傳遞等操作。

每個模板中都維護一個任務(wù)調(diào)度器。OpenMP和MPI 任務(wù)調(diào)度器主要實現(xiàn)以下功能:

(1)將數(shù)據(jù)、任務(wù)和線程表示成三維陣列的形式，提供三維索引和一維索引相互轉(zhuǎn)換的功能。

(2)按照用戶指令或依據(jù)平臺參數(shù)自動選擇或設(shè)置任務(wù)和線程的結(jié)構(gòu)。

(3)根據(jù)任務(wù)和線程結(jié)構(gòu)，將數(shù)據(jù)靜態(tài)地劃分為任務(wù)陣列，并將任務(wù)靜態(tài)地分配到各線程，為每個線程維護一個任務(wù)隊列，保證負載均衡。

(4)用戶和主動定義和更改每個線程的任務(wù)隊列。

(5)OpenMP 任務(wù)調(diào)度器可實現(xiàn)動態(tài)調(diào)度。任務(wù)調(diào)度器生成一個全局的任務(wù)隊列，并動態(tài)地將隊列中的任務(wù)分配給請求任務(wù)的空閑線程。

圖3 模板結(jié)構(gòu)

基于CUDA 的程序有著特殊的程序結(jié)構(gòu)，與host/device 混合編程模型相適應(yīng)。該系統(tǒng)保留了CUDA 程序的原始結(jié)構(gòu)。

這種填充式的開發(fā)方式適用于采用數(shù)據(jù)并行模式，各進程相對獨立，進程間數(shù)據(jù)依賴性小的并行程序開發(fā)。為兼顧函數(shù)設(shè)計的靈活性，用戶有權(quán)在函數(shù)實現(xiàn)時重載基礎(chǔ)模板中的某些屬性和行為。

4 OpenCH 的應(yīng)用

圖像處理的并行化是典型的數(shù)據(jù)并行問題，進程間沒有復(fù)雜的依賴關(guān)系。以基于k-means 算法的遙感影像非監(jiān)督分類為例，測試編程框架的有效性。

實驗中OpenMP 函數(shù)庫和MPI 函數(shù)庫運行的平臺為Intel CoreTM i5-2400 CPU(3.10 GHz，4 核);CUDA 函數(shù)庫運行平臺為NVIDIA GeForce GT 530 GPU。實驗所用數(shù)據(jù)為對地遙感衛(wèi)星Landsat-7 于2000 年6 月14 日獲取的長江三角洲地區(qū)的ETM +數(shù)據(jù)［17］。ETM+數(shù)據(jù)共有8 個波段。實驗選取藍、綠、紅、近紅外、中紅外(1.55～1.75)、中紅外(2.09～2.35)共6 個波段作為特征空間。本文按照系統(tǒng)規(guī)范分別建立了實驗所需的OpenMP，MPI 和CUDA 函數(shù)庫，并建立了統(tǒng)一的上層API 作為應(yīng)用程序調(diào)用庫函數(shù)的唯一接口。通過平臺設(shè)置接口改變計算平臺的設(shè)置，使程序運行于不同的計算平臺之上。實驗程序的實現(xiàn)包括以下4 個部分:

(1)應(yīng)用程序

Main()應(yīng)用程序主程序

(2)上層API

kmeans_RSclassification()公共函數(shù)接口

(3)下層API(面向問題的函數(shù)接口)

基于k-means 的遙感影像分算法，分別運行于OpenMP、MPI 和CUDA 計算平臺

(4)下層API(通用函數(shù)接口)

提供通用的k-means 聚類算法，分別運行于OpenMP、MPI 和CUDA 計算平臺。

圖4 為原始影像與分類結(jié)果。實驗分別比較了基于OpenCH 編程框架開發(fā)的程序與不使用OpenCH的OpenMP、MPI、CUDA 程序的運行時間，如圖5、圖6、表1 所示。所有實驗使用相同的參數(shù)和初始聚類中心，保證相同的迭代過程和計算結(jié)果。從實驗結(jié)果看出，基于該框架開發(fā)的程序成功運行于不同計算平臺之上，并且取得了與不使用框架的程序相近的性能和并行加速效果。使用編程框架本身造成的時間開銷在3.2%～13.6%之間，主要來自于多層函數(shù)間的映射和調(diào)用以及任務(wù)調(diào)度器的開銷等。

圖4 分類效果

圖5 OpenMP 程序時間性能比較

圖6 MPI 程序時間性能比較

表1 CUDA 程序性能比較

5 結(jié)束語

本文介紹一種新的并行編程框架OpenCH。該框架具有如下特點:上層應(yīng)用程序開發(fā)人員通過調(diào)用平臺無關(guān)的API 接口開發(fā)并行程序，無需關(guān)注并行化細節(jié)，降低了并行編程難度。通過層次化的API 設(shè)計，使得底層平臺的細節(jié)對上層應(yīng)用程序透明，程序可無需修改地運行于多種計算平臺。針對底層函數(shù)庫的開發(fā)，設(shè)計并實現(xiàn)了一種填充式的編程方法。該方法適用于線程間獨立性強的數(shù)據(jù)并行算法。并行函數(shù)庫和支持的計算平臺是可擴展的，能夠適應(yīng)新的計算需求和增加對新的計算平臺的支持。實驗結(jié)果證明該框架可有效簡化并行程序的開發(fā)，并獲得了良好的性能。

本文下一步的工作包括:(1)進一步豐富通用函數(shù)庫;(2)豐富任務(wù)調(diào)度器的功能，實現(xiàn)MPI 的動態(tài)調(diào)度功能;(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.