王韋樺

摘要：近年來，隨著多核芯片的產(chǎn)生和現(xiàn)代科學(xué)計(jì)算需求的不斷增大，并行計(jì)算系統(tǒng)被廣泛研究和使用，旨在提高多核芯片的利用率，提升系統(tǒng)的計(jì)算執(zhí)行效率。該文針對多核平臺間的并行計(jì)算系統(tǒng)，首先，介紹了并行計(jì)算系統(tǒng)的硬件組成結(jié)構(gòu)，然后，針對系統(tǒng)的硬件結(jié)構(gòu)，提出了相應(yīng)的并行編程模型的基本編程接口和支持機(jī)制，并從3個(gè)角度，即并行性分解、任務(wù)劃分和任務(wù)調(diào)度介紹并行計(jì)算系統(tǒng)的設(shè)計(jì)原理；最后總結(jié)并展望了并行計(jì)算系統(tǒng)未來的研究方向。

關(guān)鍵詞：并行計(jì)算系統(tǒng)；并行編程模型；并行任務(wù)劃分；并行任務(wù)調(diào)度

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）05-0244-03

Abstract： In recent years， with the development of multi-core chips and the increasing demand of modern scientific computing， Parallel computing systems have been widely studied and used in order to improve the utilization of multi-core chips， and to improve the computational efficiency of the system. In this paper， a parallel computing system is aimed at the multi core platform， First， the hardware structure of parallel computing system is introduced；Then， the basic programming interface and supporting mechanism of the parallel programming model are put forward；The design principles of parallel computing system are introduced from 3 aspects， namely， parallel decomposition， task partitioning and task scheduling； Finally， the future research directions of parallel computing systems are summarized and discussed.

Key words： parallel computing system； parallel programming model； parallel task partitioning； parallel task scheduling

1 背景

隨著互聯(lián)網(wǎng)行業(yè)的蓬勃發(fā)展，針對不同行業(yè)各類應(yīng)用的數(shù)據(jù)處理性能要求也在不斷提升，直接推動(dòng)了并行計(jì)算系統(tǒng)和分布式處理系統(tǒng)的廣泛應(yīng)用。所謂并行計(jì)算系統(tǒng)，就是構(gòu)建一組并行處理單元，并建立各個(gè)處理單元間的交互與協(xié)同規(guī)則，將數(shù)據(jù)處理任務(wù)分解成多個(gè)子任務(wù)，并依據(jù)并行計(jì)算系統(tǒng)各個(gè)處理單位的處理能力和運(yùn)行狀態(tài)進(jìn)行任務(wù)分派，以達(dá)到提高系統(tǒng)數(shù)據(jù)處理能力、處理規(guī)模和處理效率的目的[1]。

如圖1所示，并行計(jì)算系統(tǒng)的構(gòu)建主要包含三個(gè)部分，即：系統(tǒng)的硬件組成、系統(tǒng)的軟件環(huán)境和系統(tǒng)的并行程序設(shè)計(jì)[2]。以下針對這三個(gè)部分分別展開描述。

2 并行計(jì)算系統(tǒng)硬件組成

本文所設(shè)計(jì)的并行計(jì)算系統(tǒng)的硬件設(shè)備，由三臺并行計(jì)算節(jié)點(diǎn)compute-0-0、compute-0-1 和 compute-0-2組成，如圖2所示。這三個(gè)計(jì)算節(jié)點(diǎn)無主次之分，采用對等通信方式，通過以太網(wǎng)交換機(jī)構(gòu)成局域網(wǎng)絡(luò)。其中各個(gè)并行計(jì)算節(jié)點(diǎn)CPU：選用不低于Intel Core i7二代運(yùn)算能力的處理器（四核八線程），支持同步多線程；內(nèi)存：容量為4G，支持大容量高速運(yùn)算。

該并行計(jì)算系統(tǒng)的存儲方式可以認(rèn)為是一種多層次分布式內(nèi)存共享并行結(jié)構(gòu)，它同時(shí)結(jié)合了結(jié)點(diǎn)間分布式存儲和結(jié)點(diǎn)內(nèi)共享內(nèi)存的層次結(jié)構(gòu)。在該結(jié)構(gòu)下每個(gè)計(jì)算節(jié)點(diǎn)內(nèi)的多核CPU間利用內(nèi)存共享的方式進(jìn)行并行計(jì)算，而各計(jì)算節(jié)點(diǎn)之間則可采用基于消息傳遞的方式實(shí)現(xiàn)并行處理，其結(jié)構(gòu)如圖3所示。

3 多層次的并行編程模型

鑒于并行計(jì)算系統(tǒng)的分布式共享內(nèi)存并行結(jié)構(gòu)特點(diǎn)，和并行處理節(jié)點(diǎn)操作系統(tǒng)所提供的軟件支持，可以采用MPI+POSIX接口（Portable Operating System Interface of Unix） 的混合編程模型進(jìn)行并行計(jì)算系統(tǒng)的設(shè)計(jì)與開發(fā)。

MPI由一組庫函數(shù)組成，提供了統(tǒng)一的編程接口，并行程序的各個(gè)進(jìn)程之間通過這些函數(shù)進(jìn)行通信。在標(biāo)準(zhǔn)串行程序設(shè)計(jì)語言（C、C++）的基礎(chǔ)上，再加入實(shí)現(xiàn)進(jìn)程間通信的MPI消息傳遞函數(shù)，就構(gòu)成了MPI并行程序設(shè)計(jì)所依賴的并行編程環(huán)境[2]。MPI是一個(gè)標(biāo)準(zhǔn)，它不屬于任何一個(gè)產(chǎn)商，不依賴與某個(gè)操作系統(tǒng)。MPI支持多種操作系統(tǒng)，包括絕大多數(shù)的類Unix、Windows系統(tǒng)和所有主流的并行機(jī)[3]。

POSIX接口也稱為Pthreads，它是C語言多線程編程接口標(biāo)準(zhǔn)的一種具體實(shí)現(xiàn)，主要提供線程管理（創(chuàng)建、連接等）、線程同步（互斥量的創(chuàng)建、銷毀和鎖定等）和線程間的通信（條件變量的創(chuàng)建、銷毀和等待等）。

使用 MPI+Pthreads的多層次并行編程模型可以充分利用分布式內(nèi)存共享結(jié)構(gòu)的特點(diǎn)。上層使用MPI實(shí)現(xiàn)并行計(jì)算系統(tǒng)節(jié)點(diǎn)間的并行處理，下層使用Pthreads實(shí)現(xiàn)并行計(jì)算系統(tǒng)節(jié)點(diǎn)內(nèi)的多線程并行計(jì)算，實(shí)現(xiàn)原理如圖4所示。

4 并行計(jì)算系統(tǒng)的并行程序設(shè)計(jì)

根據(jù)并行計(jì)算系統(tǒng)的硬件組成和編程模式，其程序并行設(shè)計(jì)應(yīng)包含以下二個(gè)層面：

1）單個(gè)并行平臺內(nèi)的程序并行設(shè)計(jì)

根據(jù)系統(tǒng)在各個(gè)節(jié)點(diǎn)上所執(zhí)行的功能任務(wù)，從數(shù)據(jù)/任務(wù)劃分、通信同步和任務(wù)分配的層面上，討論程序并行處理設(shè)計(jì)的實(shí)現(xiàn)手段。

2）多個(gè)并行節(jié)點(diǎn)間的程序并行設(shè)計(jì)

重點(diǎn)考慮系統(tǒng)多節(jié)點(diǎn)間并行處理的任務(wù)分解和任務(wù)調(diào)度方法，目的是根據(jù)系統(tǒng)硬件組成和軟件環(huán)境，對數(shù)據(jù)處理任務(wù)進(jìn)行有效分解，并通過各節(jié)點(diǎn)間的任務(wù)合理調(diào)度，提升系統(tǒng)數(shù)據(jù)處理能力。

4.1 單個(gè)并行平臺內(nèi)的程序并行設(shè)計(jì)

單個(gè)并行平臺內(nèi)的并行程序設(shè)計(jì)就是將一個(gè)串行程序并行化，分解成若干個(gè)子程序塊，再分別進(jìn)行調(diào)度，從而讓程序并發(fā)的在多個(gè)核上運(yùn)行。以構(gòu)建仿真系統(tǒng)為例，依據(jù)并行程序設(shè)計(jì)的基本思路和設(shè)計(jì)模式開展研究討論：

4.1.1 任務(wù)劃分

根據(jù)仿真系統(tǒng)在單個(gè)并行平臺內(nèi)執(zhí)行的功能任務(wù)流程，同時(shí)，按照軟件構(gòu)件化設(shè)計(jì)思想，遵循高內(nèi)聚低耦合的設(shè)計(jì)理念，可將單個(gè)節(jié)點(diǎn)所處理的仿真任務(wù)按照不同的處理粒度和執(zhí)行層次劃分為一系列階段分別實(shí)施，包括：場景模擬階段、仿真數(shù)據(jù)生成階段、信息處理階段和顯示及結(jié)果評估階段。各個(gè)數(shù)據(jù)處理階段在進(jìn)行任務(wù)處理時(shí)，可依據(jù)各階段任務(wù)處理流程，分時(shí)順序執(zhí)行。該階段劃分任務(wù)的特點(diǎn)表現(xiàn)為：

1）系統(tǒng)由多個(gè)階段的不同功能處理協(xié)作完成任務(wù)；

2）每個(gè)處理階段均對應(yīng)不同的處理任務(wù)，并且各個(gè)任務(wù)之間按照規(guī)定的流程分時(shí)順序執(zhí)行；

3）各個(gè)處理階段之間可以采用基于消息傳遞或者內(nèi)存共享的方式進(jìn)行參數(shù)傳遞和函數(shù)調(diào)用。

綜上所述，仿真系統(tǒng)在單個(gè)并行計(jì)算平臺內(nèi)處理時(shí)，可按不同任務(wù)階段，基于流水線的方式實(shí)現(xiàn)并行計(jì)算處理，如圖5所示。

4.1.2 任務(wù)間的通信、同步和調(diào)度

根據(jù)仿真系統(tǒng)處理各個(gè)階段相對獨(dú)立的特點(diǎn)，各個(gè)處理階段通過自主交互的方式進(jìn)行任務(wù)間的通信、同步和調(diào)度。

首先，并行處理模塊建立一個(gè)任務(wù)隊(duì)列，各處理階段建立屬于其自身的任務(wù)調(diào)度器，用于其內(nèi)部任務(wù)的調(diào)度和從任務(wù)隊(duì)列提取任務(wù)。各個(gè)處理階段進(jìn)程中的任務(wù)調(diào)度器都有一個(gè)標(biāo)識信息，在從任務(wù)隊(duì)列拿到任務(wù)數(shù)據(jù)后，利用數(shù)據(jù)中的標(biāo)志信息，與各個(gè)處理階段的標(biāo)識信息進(jìn)行匹配，匹配時(shí)就激活該處理階段，并在處理完成后更新處理數(shù)據(jù)中的標(biāo)志信息，繼而激活后續(xù)的處理階段。

同時(shí)，在各個(gè)任務(wù)階段（進(jìn)程）之間的通信和同步，可利用MPI系統(tǒng)實(shí)現(xiàn)基于消息傳遞的點(diǎn)對點(diǎn)通信、全局通信和同步處理；亦可通過共享內(nèi)存方式，通過參數(shù)傳遞實(shí)現(xiàn)通信和同步。

而對于大規(guī)模數(shù)據(jù)處理需求，即可能在某個(gè)時(shí)間點(diǎn)或時(shí)間范圍內(nèi)會出現(xiàn)大量的待處理數(shù)據(jù)，而如果單個(gè)并行處理模塊的計(jì)算能力不足，造成數(shù)據(jù)隊(duì)列的堵塞，就會使系統(tǒng)出現(xiàn)無法預(yù)測的問題。此時(shí)，可用考慮采用一定的調(diào)度算法將實(shí)時(shí)任務(wù)分派到不同的處理節(jié)點(diǎn)執(zhí)行，實(shí)現(xiàn)多個(gè)并行處理模塊間的任務(wù)并行處理，從而使系統(tǒng)處理能力得到最大程度優(yōu)化。

4.2 多個(gè)并行節(jié)點(diǎn)間的程序并行設(shè)計(jì)

實(shí)時(shí)應(yīng)用的日趨復(fù)雜、數(shù)據(jù)的快速增長和系統(tǒng)規(guī)模的不斷擴(kuò)大迫切需要高性能的計(jì)算和處理能力的增長。提高系統(tǒng)計(jì)算和處理能力的途徑主要有兩種，一種是依賴于硬件（如電子元器件）的性能；另一種是建立多節(jié)點(diǎn)并行處理系統(tǒng)，利用節(jié)點(diǎn)的并行計(jì)算提高系統(tǒng)的處理能力[4]。同樣以構(gòu)建仿真系統(tǒng)為例，研究討論多個(gè)并行節(jié)點(diǎn)間的任務(wù)分配和調(diào)度策略：

4.2.1 任務(wù)劃分

對于多個(gè)并行處理節(jié)點(diǎn)間的并行程序設(shè)計(jì)，應(yīng)根據(jù)并行系統(tǒng)的硬件組成和軟件環(huán)境，首先對處理任務(wù)進(jìn)行有效分解，并在實(shí)現(xiàn)處理能力提升的基礎(chǔ)上，滿足系統(tǒng)負(fù)載均衡需求。處理任務(wù)的劃分方法通?？蓮奶幚淼臄?shù)據(jù)和實(shí)現(xiàn)的功能兩方面進(jìn)行考慮。

1）基于處理數(shù)據(jù)分解的任務(wù)劃分

數(shù)據(jù)分解的對象可以是輸入數(shù)據(jù)，計(jì)算的輸出數(shù)據(jù)或計(jì)算的中間結(jié)果。其實(shí)現(xiàn)步驟是，首先分解與仿真處理相關(guān)的輸入數(shù)據(jù)，并盡可能對數(shù)據(jù)進(jìn)行等量劃分；其次再將每個(gè)計(jì)算關(guān)聯(lián)映射到相應(yīng)的操作節(jié)點(diǎn)；當(dāng)該操作需要?jiǎng)e的任務(wù)的數(shù)據(jù)時(shí)，就會產(chǎn)生通信要求。

2）基于計(jì)算功能分解的任務(wù)劃分

功能分解也叫計(jì)算分解，它主要關(guān)注所需執(zhí)行的計(jì)算，將整個(gè)計(jì)算任務(wù)分解成一些小的任務(wù)，即各個(gè)處理節(jié)點(diǎn)使用同一處理軟件的不同功能模塊，對相同的數(shù)據(jù)信息進(jìn)行處理。其目的是盡量開拓并行執(zhí)行的可能，并行結(jié)構(gòu)如圖7所示。

4.2.2 任務(wù)調(diào)度

1）在數(shù)據(jù)分解并行模式下，并行處理系統(tǒng)應(yīng)有一個(gè)任務(wù)調(diào)度中心，在盡量考慮負(fù)載均衡、存儲空間均衡使用以及較少并行節(jié)點(diǎn)間通信的基礎(chǔ)上，將分解的數(shù)據(jù)發(fā)送到各個(gè)處理節(jié)點(diǎn)并行執(zhí)行。各個(gè)節(jié)點(diǎn)接受到任務(wù)調(diào)度中心的數(shù)據(jù)后開始本節(jié)點(diǎn)的局部計(jì)算任務(wù)，并實(shí)施計(jì)算節(jié)點(diǎn)間的通信，通過流水線方式輸出計(jì)算結(jié)果。

2）在功能分解并行模式下，多個(gè)處理模塊的并行系統(tǒng)也應(yīng)有一個(gè)任務(wù)調(diào)度中心，任務(wù)調(diào)度中心可以根據(jù)各個(gè)處理節(jié)點(diǎn)的處理功能和處理狀態(tài)，在并行系統(tǒng)內(nèi)尋找任務(wù)執(zhí)行節(jié)點(diǎn)。各個(gè)節(jié)點(diǎn)在完成對數(shù)據(jù)的本地處理功能后，向任務(wù)調(diào)度中心提交任務(wù)并發(fā)出后續(xù)功能操作的執(zhí)行請求。

5 結(jié)束語

本文以單平臺并行程序設(shè)計(jì)和多并行節(jié)點(diǎn)間的并行程序設(shè)計(jì)兩種體系結(jié)構(gòu)為例，說明并行計(jì)算技術(shù)在多核平臺間的并行計(jì)算體系結(jié)構(gòu)中的必要性和可行性。提出了用并行處理流水線的方法來加速單個(gè)平臺內(nèi)的多核系統(tǒng)計(jì)算；對于多個(gè)并行處理節(jié)點(diǎn)，通過將數(shù)據(jù)處理隊(duì)列或功能處理隊(duì)列的劃分，同時(shí)通過保證不同隊(duì)列間的時(shí)間同步，在不損失精度的前提下實(shí)現(xiàn)多平臺間的并行處理功能。

綜上所述，隨著多核/眾核芯片的發(fā)展以及一系列互聯(lián)網(wǎng)新興應(yīng)用的涌現(xiàn)，并行計(jì)算系統(tǒng)正步入面向新處理器結(jié)構(gòu)和新興應(yīng)用的優(yōu)化階段，如何高效設(shè)計(jì)并行模型和如何支持各類數(shù)據(jù)并行處理應(yīng)用將是未來發(fā)展重要方向[5]。

參考文獻(xiàn)：

[1] 陳國棟. 基于網(wǎng)絡(luò)流模型的統(tǒng)計(jì)費(fèi)用流相位解纏并行算法研究[D]. 成都： 成都理工大學(xué)碩士論文， 2012.

[2] 李偉峰. FDTD與MPSTD并行算法在電磁散射中的應(yīng)用研究[D]. 長沙： 國防科學(xué)技術(shù)大學(xué)碩士論文，2010.

[3] 王金花. 工程化星載SAR/InSAR數(shù)據(jù)處理軟件設(shè)計(jì)與實(shí)現(xiàn)[D]. 西安： 西安電子科技大學(xué)碩士論文， 2014.

[4] 王磊. 雷達(dá)系統(tǒng)標(biāo)準(zhǔn)化建模與仿真關(guān)鍵技術(shù)研究[D]. 成都： 電子科技大學(xué)博士論文， 2012.

[5] 王蕾， 崔慧敏， 陳莉， 等. 任務(wù)并行編程模型研究與進(jìn)展[J]. 軟件學(xué)報(bào)， 2013， 24（1）： 77-90.