劉 超，祝永志

(曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照276826)

多核SMP集群混合并行編程技術(shù)的研究*

劉 超，祝永志

(曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照276826)

目前,高性能計(jì)算領(lǐng)域中大多數(shù)系統(tǒng)采用層次化硬件設(shè)計(jì)，具有若干多核CPU共享存儲(chǔ)的節(jié)點(diǎn)通過高速網(wǎng)絡(luò)互聯(lián)起來?；旌喜⑿芯幊碳夹g(shù)將節(jié)點(diǎn)間的分布式存儲(chǔ)與節(jié)點(diǎn)內(nèi)的共享存儲(chǔ)進(jìn)行了融合。針對(duì)多核SMP集群體系結(jié)構(gòu)的特點(diǎn)，進(jìn)一步研究了適用于多核SMP集群的層次化混合并行編程模型MPI/OpenMP，以及多核SMP節(jié)點(diǎn)間和節(jié)點(diǎn)內(nèi)多級(jí)并行的機(jī)制。充分利用消息傳遞編程模型和共享內(nèi)存編程模型各自的優(yōu)勢(shì)，在此基礎(chǔ)上研究了多粒度并行化編程方法。

多核SMP集群;混合編程；MPI/OpenMP

0 引言

隨著CMP技術(shù)的發(fā)展以及SMP集群體系結(jié)構(gòu)的推廣，融合SMP與MPP雙重特點(diǎn)的多核SMP集群成為高性能計(jì)算(HPC)領(lǐng)域廣泛采用的新型多核體系架構(gòu)與主流研發(fā)趨勢(shì)。這種分布式存儲(chǔ)與共享存儲(chǔ)相結(jié)合的體系架構(gòu)繼承了MPP在性能和可擴(kuò)展性上的優(yōu)勢(shì)，改善了SMP可擴(kuò)展性差的缺點(diǎn)，同時(shí)又具有集群高效通信的優(yōu)點(diǎn)[1]。這種節(jié)點(diǎn)間使用消息傳遞和節(jié)點(diǎn)內(nèi)利用共享內(nèi)存的多級(jí)混合并行編程模型，更好地匹配了多核SMP集群特點(diǎn)。

圖1 多核SMP集群體系架構(gòu)

圖1顯示了具有N個(gè)節(jié)點(diǎn)(每個(gè)節(jié)點(diǎn)為兩個(gè)四核CPU，圓形表示處理器內(nèi)核)的多核SMP集群體系結(jié)構(gòu)。處理器之間通過BUS/CROSSBAR互聯(lián)，并共享內(nèi)存區(qū)域與I/O設(shè)備。多核SMP節(jié)點(diǎn)通過高速通信網(wǎng)絡(luò)(如Myrinet、以太網(wǎng)等)連接，節(jié)點(diǎn)間利用消息傳遞進(jìn)行通信[2]。

1 混合平臺(tái)上的并行編程模型

嚴(yán)格來說，一個(gè)并行編程模型是計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的抽象[3]，它不依賴于任何特定的機(jī)器類型。但因CPU的組合方式不同，建立起的并行系統(tǒng)會(huì)產(chǎn)生許多可能的并行編程模型。圖2顯示了混合平臺(tái)上并行編程模型的分類。

圖2 混合架構(gòu)并行編程模型的分類

1.1 共享存儲(chǔ)編程模型 OpenMP

常見的共享內(nèi)存編程標(biāo)準(zhǔn)為OpenMP，它是為在多處理機(jī)上編寫并行程序而設(shè)計(jì)的API，其目的是易于共享存儲(chǔ)并行編程。通過在源程序代碼中加入指導(dǎo)性注釋(Compiler Directive)、編譯指導(dǎo)指令#pragma行來指定程序的并發(fā)性。在OpenMP中，線程并行已高度結(jié)構(gòu)化，常采用Fork-Join并行執(zhí)行模式[4]：首先由一個(gè)主線程串行運(yùn)行程序，當(dāng)需要并行計(jì)算時(shí)，派生的若干從線程與主線程共同并行執(zhí)行任務(wù)。在執(zhí)行結(jié)束后派生的從線程同步或中斷，控制流重回主線程中，如圖3所示。

圖3 Fork-Join并行執(zhí)行模式

OpenMP的特點(diǎn)為：隱式通信；高層次抽象；支持增量并行；可擴(kuò)展性高，移植性好;支持粗粒度和細(xì)粒度并行；面向應(yīng)用的同步原語，易于編并行程序；不僅能在共享存儲(chǔ)系統(tǒng)使用，也能在非共享存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，只是效率不同。

1.2 消息傳遞編程模型 MPI

常見的消息傳遞編程標(biāo)準(zhǔn)為MPI(Message Passing Interface)，它并不是一種編程語言，而是綁定在Fortran語言或C語言中的消息傳遞庫以及API接口，其目的是服務(wù)于進(jìn)程間通信。對(duì)于分布式存儲(chǔ)系統(tǒng)而言，MPI是一種自然的編程模型，而且能夠?qū)崿F(xiàn)SPMD并行模型，常采用Master-Woker工作模式：Master進(jìn)程把數(shù)據(jù)分配給Worker進(jìn)程；所有的Worker進(jìn)程接收相應(yīng)的數(shù)據(jù)；每個(gè)Worker進(jìn)程進(jìn)行數(shù)據(jù)計(jì)算；Worker進(jìn)程將結(jié)果發(fā)送給主進(jìn)程[5]。應(yīng)用程序的每次迭代都是重復(fù)這個(gè)邏輯，根據(jù)問題的性質(zhì)，Master進(jìn)程可能必須等待來自所有Worker進(jìn)程的結(jié)果之后才能發(fā)送新的數(shù)據(jù)，如圖4所示。

圖4 Master-Work工作模式

MPI特點(diǎn)是：顯式通信；效率高，移植性好；特別適用于粗粒度并行；多種優(yōu)化的組通信庫函數(shù)；通過在計(jì)算/通信的疊加，以提升并行性能。能在分布式存儲(chǔ)系統(tǒng)與共享存儲(chǔ)系統(tǒng)上運(yùn)行； 用戶控制對(duì)數(shù)據(jù)的劃分和進(jìn)程的同步。

OpenMP與MPI的主要特點(diǎn)對(duì)比如表1所示。

表1 OpenMP與MPI模型主要特點(diǎn)對(duì)比

1.3 OpenMP/MPI混合編程模型

結(jié)合多核SMP集群層次化存儲(chǔ)的結(jié)構(gòu)特點(diǎn)，充分利用上述兩種編程模型的優(yōu)勢(shì)：共享存儲(chǔ)模型的編程效率與分布式存儲(chǔ)模型的可擴(kuò)展性?；舅枷胧?(1)將問題規(guī)模進(jìn)行MPI劃分，形成通信不密集的若干子任務(wù)；(2)將每個(gè)子任務(wù)(即一個(gè)MPI進(jìn)程)分配到一個(gè)多核SMP節(jié)點(diǎn)上，節(jié)點(diǎn)之間依靠消息傳遞進(jìn)行通信；(3)在每個(gè)節(jié)點(diǎn)上使用OpenMP編譯制導(dǎo)語句將子任務(wù)再次劃分，并分配到節(jié)點(diǎn)的不同處理核心上由多線程并行執(zhí)行，節(jié)點(diǎn)內(nèi)利用共享變量進(jìn)行通信，如圖5所示。

圖5 Hybrid MPI/OpenMP編程模型

Hybrid MPI/OpenMP編程模型的優(yōu)勢(shì)：

(1)匹配當(dāng)前硬件的發(fā)展趨勢(shì)——多核和多處理器計(jì)算機(jī)；

(2)明確兩個(gè)并行層次：粗粒度(適用于MPI)和細(xì)粒度(適用于OpenMP)；

(3)某些應(yīng)用或系統(tǒng)特點(diǎn)可能會(huì)限制MPI進(jìn)程數(shù)量(可擴(kuò)展性問題)，因此OpenMP可以提供增量并行；

(4)有些應(yīng)用在MPI層工作負(fù)載不平衡，OpenMP通過分配不同數(shù)量的線程到MPI進(jìn)程以解決此問題；

(5)OpenMP避免了由MPI計(jì)算節(jié)點(diǎn)引起的額外通信開銷。

在現(xiàn)有MPI代碼中引入OpenMP意味著同時(shí)引入OpenMP的一些缺陷：

(1)控制任務(wù)分配與同步時(shí)的限制；

(2)線程創(chuàng)建和同步產(chǎn)生的開銷；

(3)對(duì)編譯器的依賴以及對(duì)OpenMP運(yùn)行時(shí)庫的支持；

(4)共享存儲(chǔ)問題；

(5)MPI與OpenMP運(yùn)行時(shí)庫相互作用可能對(duì)程序性能產(chǎn)生負(fù)面影響。

大部分的Hybrid代碼基于一個(gè)層次模型，這使得在MPI層利用大中型粒度并行和OpenMP層利用細(xì)粒度并行成為可能。在高層次，程序被顯示地構(gòu)造為若干MPI任務(wù)，其順序代碼中引入OpenMP制導(dǎo)指令，加入多線程以利用共享存儲(chǔ)的特點(diǎn)。這種編程模型根據(jù)通信與計(jì)算之間是否重疊分為兩類：

(1)無計(jì)算/通信重疊。這類又分為兩種方式：①只在并行域和主線程外調(diào)用MPI。優(yōu)點(diǎn)是SMP節(jié)點(diǎn)內(nèi)沒有消息傳遞。缺點(diǎn)是效率低，即在主線程進(jìn)行通信時(shí)，其他線程進(jìn)入休眠，沒有實(shí)現(xiàn)計(jì)算/通信的重疊。②應(yīng)用程序代碼在并行域外調(diào)用MPI，但MPI通信由多個(gè)CPU完成。MPI通信線程可由MPI庫自動(dòng)完成或由使用線程安全的MPI庫的應(yīng)用程序顯示完成。該方式示意圖如圖6所示。

圖6 無計(jì)算/重疊編程方式

(2)計(jì)算/通信重疊。為了避免MPI通信期間計(jì)算線程閑置而從OpenMP線程組中分離出一個(gè)或多個(gè)線程來處理與計(jì)算并行的通信，此時(shí)MPI函數(shù)的調(diào)用應(yīng)在Critical、Master 或 Single相應(yīng)的區(qū)域內(nèi)。有兩種方法：①當(dāng)通信由主線程(或幾個(gè)線程)執(zhí)行時(shí)，所有通信都注入到主線程，其他所有非通信線程執(zhí)行數(shù)據(jù)計(jì)算任務(wù)；②當(dāng)每個(gè)線程都有通信需求時(shí)，通信會(huì)注入到多個(gè)線程。計(jì)算/重疊編程方式示意圖如圖7所示。

圖7 計(jì)算/重疊編程方式

2 層次化混合編程的實(shí)現(xiàn)

解決混合并行編程所存在問題的核心策略就是標(biāo)準(zhǔn)，從這個(gè)角度來看，有分布式存儲(chǔ)編程MPI和共享式存儲(chǔ)OpenMP，這就構(gòu)成了開發(fā)混合編程的策略基礎(chǔ)。利用現(xiàn)有的MPI或OpenMP代碼構(gòu)建混合并行應(yīng)用程序，具體方法如下：

(1)使用OpenMP改良MPI。這是一種簡(jiǎn)單的混合編程實(shí)現(xiàn)方式，僅需將OpenMP編譯制導(dǎo)指令插入原循環(huán)代碼段外部。其性能取決于能被OpenMP并行求解的循環(huán)部分的計(jì)算量(通常是細(xì)粒度并行)。這種方式有利于通信綁定的應(yīng)用程序，因?yàn)槠錅p少了需要進(jìn)行通信的MPI進(jìn)程數(shù)。但是，如果程序中循環(huán)較多，使用的編譯指令也將隨之增多，創(chuàng)建并行域或線程同步的開銷將會(huì)增大[6]。因此，在進(jìn)行循環(huán)級(jí)并行化時(shí)，應(yīng)首選全局時(shí)間中計(jì)算時(shí)間占比較大的循環(huán)[7]。以下是細(xì)粒度偽混合程序代碼：

#include"mpi.h"

#include"omp.h"

......

//一些計(jì)算和MPI通信

#pragma omp paralle num_threads(...)

#pragam omp for private(...)

for(...)

{ //計(jì)算 }

//一些計(jì)算和MPI通信

......

MPI_Finalize();

(2)使用MPI改良OpenMP。這種方法(粗粒度并行)不同于前一個(gè)，需要考慮每個(gè)進(jìn)程如何與其他進(jìn)程通信，它可能需要完全重新設(shè)計(jì)并行性。編譯制導(dǎo)指令通常在程序的最外層，OpenMP線程緊隨MPI進(jìn)程而生成，生成的線程與SPMD模式中的進(jìn)程較為相似，即在不同的數(shù)據(jù)上執(zhí)行相同的代碼段。與SPMD的不同之處在于多核SMP節(jié)點(diǎn)內(nèi)各處理器共享存儲(chǔ)，無需預(yù)分配數(shù)據(jù)到各處理器上。此方法優(yōu)點(diǎn)是OpenMP編譯制導(dǎo)指令使用較少，調(diào)用與通信開銷較低。然而，OpenMP多線程的使用類似于MPI多進(jìn)程的使用，特別是當(dāng)使用混合模型中多級(jí)并行機(jī)制時(shí)，編程復(fù)雜性則會(huì)增大。以下是OpenMP部分偽混合代碼：

......

omp_set_num_threads(...)

#pragma omp paralle private(...)

th_id=omp_get_thread_num();

th_size=omp_get_num_threads();

......

for(...)

{..//計(jì)算}

#pargma omp barrier

#pargma omp master/single

{...//MPI通信}

......//MPI通信

......

3 實(shí)驗(yàn)

考慮到性能和易用性兩方面的因素，本文從整體上采用類似SMPD的模式：節(jié)點(diǎn)內(nèi)OpenMP細(xì)粒度并行與節(jié)點(diǎn)間MPI粗粒度并行，即Hybrid OpenMP/MPI層次化編程。選取矩陣乘法為案例，在矩陣規(guī)模和執(zhí)行內(nèi)核數(shù)量不同的情況下對(duì)比Non-hybirid混合編程所表現(xiàn)出的性能差異。

3.1 曙光TC5000高性能計(jì)算集群系統(tǒng)

曙光TC5000集群系統(tǒng)整體計(jì)算能力為5.7萬億次， 一臺(tái)A620r-H作為管理節(jié)點(diǎn)，6臺(tái)CB65作為計(jì)算節(jié)點(diǎn)，一套磁盤陣列提供存儲(chǔ)。每個(gè)刀片計(jì)算節(jié)點(diǎn)有兩顆AMD Opteron6128 2 GHz四核處理器，共計(jì)8核，整個(gè)集群配有144 GB內(nèi)存。

集群軟件環(huán)境：SUSE Linux Enterprise Server 10SP操作系統(tǒng)； 并行環(huán)境：MPI版本為MPICH2， GCC4.2.4編譯器；NFS文件共享服務(wù)；InfiniBand高速計(jì)算網(wǎng)絡(luò)管理并行通信等。

3.2 實(shí)驗(yàn)及結(jié)果分析

使用集群中6個(gè)雙路四核計(jì)算節(jié)點(diǎn)運(yùn)行MPI代碼與MPI/OpenMP代碼進(jìn)行對(duì)比測(cè)試。運(yùn)行混合MPI/OpenMP代碼時(shí)，每個(gè)計(jì)算節(jié)點(diǎn)分配一個(gè)MPI進(jìn)程和8個(gè)線程(節(jié)點(diǎn)內(nèi)的線程數(shù)不應(yīng)超過物理處理器個(gè)數(shù)[7])。應(yīng)當(dāng)注意到，在矩陣相乘計(jì)算的核心部分，可以認(rèn)為兩個(gè)循環(huán)都可以并行執(zhí)行。如果將內(nèi)部循環(huán)并行，程序在外部循環(huán)的每次迭代中都進(jìn)行線程的Fork-Join操作，這樣做的開銷可能高于將內(nèi)部循環(huán)在多線程間并行化所節(jié)省的時(shí)間；若對(duì)外層循環(huán)并行化，將使用一次Fork-Join操作，并可使程序有更大的粒度。程序中使用的矩陣規(guī)模分別為500×500,1 000×1 000，1 500×1 500。如表2所示，表中每個(gè)時(shí)間點(diǎn)對(duì)應(yīng)的值都是該程序運(yùn)行五次的平均值。從圖8可以清晰地看到在使用不同節(jié)點(diǎn)數(shù)時(shí)混合MPI/OpenMP程序與MPI程序的加速比。隨著節(jié)點(diǎn)數(shù)的增加，混合編程的加速比明顯高于純MPI的加速比。因?yàn)樵谶\(yùn)行MPI程序時(shí)CPU的利用率較低，并未充分利用處理器資源；而混合編程中CPU利用率較高，這進(jìn)一步驗(yàn)證了在多核處理器中使用OpenMP多線程對(duì)程序性能的影響(這些結(jié)果是在沒有任何優(yōu)化措施的情況下得到的)。

表2 執(zhí)行時(shí)間與加速比

圖8 MPI與MPI/OpenMP

4 結(jié)論

本文分析了多核SMP集群并行體系結(jié)構(gòu)的特點(diǎn)，研究適用于多核SMP集群的混合并行編程模型，針對(duì)MPI程序存在負(fù)載不平衡與可擴(kuò)展性差的問題，使用OpenMP改造MPI程序，這種細(xì)粒度并行化的MPI+OpenMP更容易實(shí)現(xiàn)且能提高程序性能。目前尚不清楚這種編程技術(shù)對(duì)多核SMP集群而言是否是最為有效的機(jī)制，還有很多問題尚待解決，這需要進(jìn)一步研究。

[1] 孫凝暉, 李凱, 陳明宇. HPP:一種支持高性能和效用計(jì)算的體系結(jié)構(gòu)[J]. 計(jì)算機(jī)學(xué)報(bào), 2008,31(9): 1503-1508.

[2] RABENSEIFNER R, HAGER G, JOST G. Hybrid MPI/OpenMP parallel programming on clusters of multi-core SMP nodes[C]. Proceedings of 17th Euromicro International Conference on Parallel, Distributed, and Network-based Processing. 2009:427-436.

[3] KOTOBI A, ABDUL H N A W, OTHMAN M, et al. Performance analysis of hybrid OpenMP/MPI based on multi-core cluster architecture[C]. 2014 International Conference on,Computational Science and Technology (ICCST). IEEE, 2015:1-6.

[4] MATTSON T G, SANDERS B A, MASSINGILL B. Patterns for parallel programming[M]. Addison-Wesley Professional, 2005.

[5] CASTELLANOS A, MORENO A, SORRIBES J, et al. Performance model for Master/Worker hybrid applications on multicore clusters[C]. IEEE International Conference on High Performance Computing and Communications, 2013:210-217.

[6] 祝永志. 多核SMP集群Hybrid并行編程模式的研究與分析[J]. 電子技術(shù), 2016(2):72-75.

[7] 陳勇, 陳國良, 李春生,等. SMP機(jī)群混合編程模型研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2004, 25(10):1763-1767.

Research on hybrid parallel programming technology on multi-core SMP cluster

Liu Chao，Zhu Yongzhi

(School of Information Science and Engineering, Qufu Normal University, Rizhao 276826,China)

Currently, the majority of high-performance computing systems use hierarchical hardware design. Nodes have a plurality of multi-core CPU shared memory interconnect by high-speed network. Hybrid parallel programming technology fuses inter-nodes of distributed memories and intra-nodes of sharing memories. Therefore, according to the characteristics of multi-core SMP cluster architecture, this paper further studies the hierarchy hybrid parallel programming model MPI/OpenMP applied to multi-core SMP cluster, and multi-core SMP inter-nodes and intra-nodes multi-level parallelism mechanisms. On the basis of making full use of respective advantages of message passing programming model and shared-memory programming model, this paper studies a multi-granularity parallel programming method.

multi-core SMP cluster; hybrid programming; MPI/OpenMP

山東省自然科學(xué)基金(ZR2013FL015)

TP301

A

10.19358/j.issn.1674- 7720.2017.04.006

劉超，祝永志.多核SMP集群混合并行編程技術(shù)的研究[J].微型機(jī)與應(yīng)用，2017,36(4)：18-21.

2016-08-31)

劉超(1984-)，男，碩士研究生，主要研究方向：并行計(jì)算。

祝永志(1964-)，男，碩士，教授，主要研究方向：分布式數(shù)據(jù)庫，并行與分布式計(jì)算。