多核平臺間的并行計算系統(tǒng)研究

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

2、ract： 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. I

3、n 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 c

4、omputing 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 par

5、titioning； parallel task scheduling1 背景隨著互聯(lián)網(wǎng)行業(yè)的蓬勃發(fā)展，針對不同行業(yè)各類應(yīng)用的數(shù)據(jù)處理性能要求也在不斷提升，直接推動了并行計算系統(tǒng)和分布式處理系統(tǒng)的廣泛應(yīng)用。所謂并行計算系統(tǒng)，就是構(gòu)建一組并行處理單元，并建立各個處理單元間的交互與協(xié)同規(guī)則，將數(shù)據(jù)處理任務(wù)分解成多個子任務(wù)，并依據(jù)并行計算系統(tǒng)各個處理單位的處理能力和運行狀態(tài)進(jìn)行任務(wù)分派，以達(dá)到提高系統(tǒng)數(shù)據(jù)處理能力、處理規(guī)模和處理效率的目的1。如圖1所示，并行計算系統(tǒng)的構(gòu)建主要包含三個部分，即：系統(tǒng)的硬件組成、系統(tǒng)的軟件環(huán)境和系統(tǒng)的并行程序設(shè)計2。以下針對這三個部分分別展開描述。2 并行計算系統(tǒng)硬件組

6、成本文所設(shè)計的并行計算系統(tǒng)的硬件設(shè)備，由三臺并行計算節(jié)點compute-0-0、compute-0-1 和 compute-0-2組成，如圖2所示。這三個計算節(jié)點無主次之分，采用對等通信方式，通過以太網(wǎng)交換機構(gòu)成局域網(wǎng)絡(luò)。其中各個并行計算節(jié)點CPU：選用不低于Intel Core i7二代運算能力的處理器（四核八線程），支持同步多線程；內(nèi)存：容量為4G，支持大容量高速運算。該并行計算系統(tǒng)的存儲方式可以認(rèn)為是一種多層次分布式內(nèi)存共享并行結(jié)構(gòu)，它同時結(jié)合了結(jié)點間分布式存儲和結(jié)點內(nèi)共享內(nèi)存的層次結(jié)構(gòu)。在該結(jié)構(gòu)下每個計算節(jié)點內(nèi)的多核CPU間利用內(nèi)存共享的方式進(jìn)行并行計算，而各計算節(jié)點之間則可采用基于消

7、息傳遞的方式實現(xiàn)并行處理，其結(jié)構(gòu)如圖3所示。3 多層次的并行編程模型鑒于并行計算系統(tǒng)的分布式共享內(nèi)存并行結(jié)構(gòu)特點，和并行處理節(jié)點操作系統(tǒng)所提供的軟件支持，可以采用MPI+POSIX接口（Portable Operating System Interface of Unix） 的混合編程模型進(jìn)行并行計算系統(tǒng)的設(shè)計與開發(fā)。MPI由一組庫函數(shù)組成，提供了統(tǒng)一的編程接口，并行程序的各個進(jìn)程之間通過這些函數(shù)進(jìn)行通信。在標(biāo)準(zhǔn)串行程序設(shè)計語言（C、C+）的基礎(chǔ)上，再加入實現(xiàn)進(jìn)程間通信的MPI消息傳遞函數(shù)，就構(gòu)成了MPI并行程序設(shè)計所依賴的并行編程環(huán)境2。MPI是一個標(biāo)準(zhǔn)，它不屬于任何一個產(chǎn)商，不依賴與某個操

8、作系統(tǒng)。MPI支持多種操作系統(tǒng)，包括絕大多數(shù)的類Unix、Windows系統(tǒng)和所有主流的并行機3。POSIX接口也稱為Pthreads，它是C語言多線程編程接口標(biāo)準(zhǔn)的一種具體實現(xiàn)，主要提供線程管理（創(chuàng)建、連接等）、線程同步（互斥量的創(chuàng)建、銷毀和鎖定等）和線程間的通信（條件變量的創(chuàng)建、銷毀和等待等）。使用 MPI+Pthreads的多層次并行編程模型可以充分利用分布式內(nèi)存共享結(jié)構(gòu)的特點。上層使用MPI實現(xiàn)并行計算系統(tǒng)節(jié)點間的并行處理，下層使用Pthreads實現(xiàn)并行計算系統(tǒng)節(jié)點內(nèi)的多線程并行計算，實現(xiàn)原理如圖4所示。 4 并行計算系統(tǒng)的并行程序設(shè)計根據(jù)并行計算系統(tǒng)的硬件組成和編程模式，其程序并行

9、設(shè)計應(yīng)包含以下二個層面：1）單個并行平臺內(nèi)的程序并行設(shè)計根據(jù)系統(tǒng)在各個節(jié)點上所執(zhí)行的功能任務(wù)，從數(shù)據(jù)/任務(wù)劃分、通信同步和任務(wù)分配的層面上，討論程序并行處理設(shè)計的實現(xiàn)手段。2）多個并行節(jié)點間的程序并行設(shè)計重點考慮系統(tǒng)多節(jié)點間并行處理的任務(wù)分解和任務(wù)調(diào)度方法，目的是根據(jù)系統(tǒng)硬件組成和軟件環(huán)境，對數(shù)據(jù)處理任務(wù)進(jìn)行有效分解，并通過各節(jié)點間的任務(wù)合理調(diào)度，提升系統(tǒng)數(shù)據(jù)處理能力。4.1 單個并行平臺內(nèi)的程序并行設(shè)計單個并行平臺內(nèi)的并行程序設(shè)計就是將一個串行程序并行化，分解成若干個子程序塊，再分別進(jìn)行調(diào)度，從而讓程序并發(fā)的在多個核上運行。以構(gòu)建仿真系統(tǒng)為例，依據(jù)并行程序設(shè)計的基本思路和設(shè)計模式開展研究討論

10、：4.1.1 任務(wù)劃分根據(jù)仿真系統(tǒng)在單個并行平臺內(nèi)執(zhí)行的功能任務(wù)流程，同時，按照軟件構(gòu)件化設(shè)計思想，遵循高內(nèi)聚低耦合的設(shè)計理念，可將單個節(jié)點所處理的仿真任務(wù)按照不同的處理粒度和執(zhí)行層次劃分為一系列階段分別實施，包括：場景模擬階段、仿真數(shù)據(jù)生成階段、信息處理階段和顯示及結(jié)果評估階段。各個數(shù)據(jù)處理階段在進(jìn)行任務(wù)處理時，可依據(jù)各階段任務(wù)處理流程，分時順序執(zhí)行。該階段劃分任務(wù)的特點表現(xiàn)為：1）系統(tǒng)由多個階段的不同功能處理協(xié)作完成任務(wù)；2）每個處理階段均對應(yīng)不同的處理任務(wù)，并且各個任務(wù)之間按照規(guī)定的流程分時順序執(zhí)行；3）各個處理階段之間可以采用基于消息傳遞或者內(nèi)存共享的方式進(jìn)行參數(shù)傳遞和函數(shù)調(diào)用。綜上所

11、述，仿真系統(tǒng)在單個并行計算平臺內(nèi)處理時，可按不同任務(wù)階段，基于流水線的方式實現(xiàn)并行計算處理，如圖5所示。4.1.2 任務(wù)間的通信、同步和調(diào)度根據(jù)仿真系統(tǒng)處理各個階段相對獨立的特點，各個處理階段通過自主交互的方式進(jìn)行任務(wù)間的通信、同步和調(diào)度。首先，并行處理模塊建立一個任務(wù)隊列，各處理階段建立屬于其自身的任務(wù)調(diào)度器，用于其內(nèi)部任務(wù)的調(diào)度和從任務(wù)隊列提取任務(wù)。各個處理階段進(jìn)程中的任務(wù)調(diào)度器都有一個標(biāo)識信息，在從任務(wù)隊列拿到任務(wù)數(shù)據(jù)后，利用數(shù)據(jù)中的標(biāo)志信息，與各個處理階段的標(biāo)識信息進(jìn)行匹配，匹配時就激活該處理階段，并在處理完成后更新處理數(shù)據(jù)中的標(biāo)志信息，繼而激活后續(xù)的處理階段。同時，在各個任務(wù)階段（進(jìn)

12、程）之間的通信和同步，可利用MPI系統(tǒng)實現(xiàn)基于消息傳遞的點對點通信、全局通信和同步處理；亦可通過共享內(nèi)存方式，通過參數(shù)傳遞實現(xiàn)通信和同步。而對于大規(guī)模數(shù)據(jù)處理需求，即可能在某個時間點或時間范圍內(nèi)會出現(xiàn)大量的待處理數(shù)據(jù)，而如果單個并行處理模塊的計算能力不足，造成數(shù)據(jù)隊列的堵塞，就會使系統(tǒng)出現(xiàn)無法預(yù)測的問題。此時，可用考慮采用一定的調(diào)度算法將實時任務(wù)分派到不同的處理節(jié)點執(zhí)行，實現(xiàn)多個并行處理模塊間的任務(wù)并行處理，從而使系統(tǒng)處理能力得到最大程度優(yōu)化。4.2 多個并行節(jié)點間的程序并行設(shè)計實時應(yīng)用的日趨復(fù)雜、數(shù)據(jù)的快速增長和系統(tǒng)規(guī)模的不斷擴(kuò)大迫切需要高性能的計算和處理能力的增長。提高系統(tǒng)計算和處理能力的

13、途徑主要有兩種，一種是依賴于硬件（如電子元器件）的性能；另一種是建立多節(jié)點并行處理系統(tǒng)，利用節(jié)點的并行計算提高系統(tǒng)的處理能力4。同樣以構(gòu)建仿真系統(tǒng)為例，研究討論多個并行節(jié)點間的任務(wù)分配和調(diào)度策略：4.2.1 任務(wù)劃分對于多個并行處理節(jié)點間的并行程序設(shè)計，應(yīng)根據(jù)并行系統(tǒng)的硬件組成和軟件環(huán)境，首先對處理任務(wù)進(jìn)行有效分解，并在實現(xiàn)處理能力提升的基礎(chǔ)上，滿足系統(tǒng)負(fù)載均衡需求。處理任務(wù)的劃分方法通?？蓮奶幚淼臄?shù)據(jù)和實現(xiàn)的功能兩方面進(jìn)行考慮。1）基于處理數(shù)據(jù)分解的任務(wù)劃分?jǐn)?shù)據(jù)分解的對象可以是輸入數(shù)據(jù)，計算的輸出數(shù)據(jù)或計算的中間結(jié)果。其實現(xiàn)步驟是，首先分解與仿真處理相關(guān)的輸入數(shù)據(jù)，并盡可能對數(shù)據(jù)進(jìn)行等量劃分

14、；其次再將每個計算關(guān)聯(lián)映射到相應(yīng)的操作節(jié)點；當(dāng)該操作需要別的任務(wù)的數(shù)據(jù)時，就會產(chǎn)生通信要求。2）基于計算功能分解的任務(wù)劃分功能分解也叫計算分解，它主要關(guān)注所需執(zhí)行的計算，將整個計算任務(wù)分解成一些小的任務(wù)，即各個處理節(jié)點使用同一處理軟件的不同功能模塊，對相同的數(shù)據(jù)信息進(jìn)行處理。其目的是盡量開拓并行執(zhí)行的可能，并行結(jié)構(gòu)如圖7所示。4.2.2 任務(wù)調(diào)度1）在數(shù)據(jù)分解并行模式下，并行處理系統(tǒng)應(yīng)有一個任務(wù)調(diào)度中心，在盡量考慮負(fù)載均衡、存儲空間均衡使用以及較少并行節(jié)點間通信的基礎(chǔ)上，將分解的數(shù)據(jù)發(fā)送到各個處理節(jié)點并行執(zhí)行。各個節(jié)點接受到任務(wù)調(diào)度中心的數(shù)據(jù)后開始本節(jié)點的局部計算任務(wù)，并實施計算節(jié)點間的通信，

15、通過流水線方式輸出計算結(jié)果。2）在功能分解并行模式下，多個處理模塊的并行系統(tǒng)也應(yīng)有一個任務(wù)調(diào)度中心，任務(wù)調(diào)度中心可以根據(jù)各個處理節(jié)點的處理功能和處理狀態(tài)，在并行系統(tǒng)內(nèi)尋找任務(wù)執(zhí)行節(jié)點。各個節(jié)點在完成對數(shù)據(jù)的本地處理功能后，向任務(wù)調(diào)度中心提交任務(wù)并發(fā)出后續(xù)功能操作的執(zhí)行請求。5 結(jié)束語本文以單平臺并行程序設(shè)計和多并行節(jié)點間的并行程序設(shè)計兩種體系結(jié)構(gòu)為例，說明并行計算技術(shù)在多核平臺間的并行計算體系結(jié)構(gòu)中的必要性和可行性。提出了用并行處理流水線的方法來加速單個平臺內(nèi)的多核系統(tǒng)計算；對于多個并行處理節(jié)點，通過將數(shù)據(jù)處理隊列或功能處理隊列的劃分，同時通過保證不同隊列間的時間同步，在不損失精度的前提下實現(xiàn)多平臺間的并行處理功能。綜上所述，隨著多核/眾核芯片的發(fā)展以及一系列互聯(lián)網(wǎng)新興應(yīng)用的涌現(xiàn)，并行計算系統(tǒng)正步入面向新處理器結(jié)構(gòu)和新興應(yīng)用的優(yōu)化階段，如何高效設(shè)計并行模型和如何支持各類數(shù)據(jù)并行處理應(yīng)用將是未來發(fā)展重要方向5。Reference：1 陳國棟. 基于網(wǎng)絡(luò)流模型的統(tǒng)計費用流相位解纏并行算法研究D. 成都： 成都理工大學(xué)碩士論文， 2012.2 李偉峰. FDTD與MPSTD并行算法在電磁散射中的應(yīng)用研究D. 長沙： 國防科學(xué)技術(shù)大學(xué)碩士論文，2010.3 王金花. 工程化星載SAR/InSAR數(shù)據(jù)處理軟件設(shè)計與實現(xiàn)D.