付穎

（黔南民族職業(yè)技術(shù)學(xué)院大數(shù)據(jù)與電子商務(wù)系 貴州省黔南布依族苗族自治州 558022）

1 OpenMP技術(shù)概述

1.1 OpenMP技術(shù)

從計(jì)算機(jī)發(fā)明之初，到現(xiàn)如今的人工智能的出現(xiàn)，計(jì)算機(jī)的快速發(fā)展已成為很多領(lǐng)域的核心力量。在本世紀(jì)的頭10年，利用空氣冷卻技術(shù)制成的集成電路，其散熱能力已經(jīng)達(dá)到了該器件的極限。因此，通過不斷加快集成電路的速率來提升處理性能的方法已經(jīng)不再適用，既然計(jì)算方法對(duì)改善計(jì)算機(jī)處理性能有推動(dòng)作用，那么繼續(xù)發(fā)掘更強(qiáng)的計(jì)算機(jī)處理能力就是迫切且必要的，所以人們?cè)谘邪l(fā)新一代計(jì)算機(jī)的進(jìn)程中，并行技術(shù)起著關(guān)鍵性的作用。并行技術(shù)是指在同一時(shí)間內(nèi)，增添運(yùn)算量的處理技術(shù)。然而在目前的發(fā)展過程中，并行軟件的進(jìn)展，極大程度上地滯緩于并行技術(shù)體系結(jié)構(gòu)的進(jìn)展；并行技術(shù)的使用，也極大程度上地較滯緩于并行技術(shù)的發(fā)展[1]。

隨著并行技術(shù)的發(fā)展，市面上出現(xiàn)了形式不同的并行模型。比如基于程序構(gòu)建的模型（CSP、Linda 等），基于問題闡述的模型（GAMMA、UNITY 等），基于并行理論的模型（PRAM、BSP 等）和硬件結(jié)構(gòu)抽象模型(又稱為自然模型)。而硬件結(jié)構(gòu)的抽象模型又分為同享儲(chǔ)存的模型和語(yǔ)言（PVP,SMP 等）在 Pthreads、OpenMP等環(huán)境下進(jìn)行內(nèi)存同享編程，訊息傳送的模型和語(yǔ)言(適于MPP,Cluster 等)在MPI、PVM 等環(huán)境下進(jìn)行分布式內(nèi)存編程；數(shù)據(jù)并行的模型和語(yǔ)言(適合 MPP/Cluster上完成 SPMD 操作)在 Fortran、HPF 等環(huán)境下編程[2]。

OpenMP 技術(shù)是一種用于共享內(nèi)存并行系統(tǒng)的多線程程序設(shè)計(jì)方案，支持的編程語(yǔ)言含C、C++和Fortran[3]。OpenMP 技術(shù)提供對(duì)并行算法的高層抽象描述，特別適合在多核CPU 機(jī)器上的并行程序設(shè)計(jì)，程序員課通過在源代碼中添加專門的編譯指示來表明自己的編程意圖，由此編譯器可以自動(dòng)地將程序進(jìn)行并行化，并在必要之處加入同步互斥以及通信。當(dāng)選擇忽略這些編譯指示時(shí)，或者編譯器不支持OpenMP 技術(shù)時(shí)，程序又可退化為通常的程序（一般為串行），代碼仍然可以正常運(yùn)作，只是不能利用多線程來加速程序執(zhí)行[4-5]。

1.2 相關(guān)概念

串行計(jì)算：傳統(tǒng)意義上的編程計(jì)算，指計(jì)算過程只能夠按照計(jì)算機(jī)的執(zhí)行順序進(jìn)行的計(jì)算，在同一個(gè)時(shí)刻中計(jì)算機(jī)只能進(jìn)行一次運(yùn)算。

并行計(jì)算：是一種快速的計(jì)算方式，是相對(duì)串行計(jì)算而言的，我們又把這種計(jì)算方式稱為平行計(jì)算。傳統(tǒng)的串行計(jì)算由“指令”與“數(shù)據(jù)”兩部分構(gòu)成，在代碼施行時(shí)，內(nèi)存空間是采取“獨(dú)立應(yīng)用和占有”的方式，而且在代碼運(yùn)行期間所有的運(yùn)算都僅限于此。而并行計(jì)算，則是將計(jì)算相對(duì)獨(dú)立的分配給不同節(jié)點(diǎn)的進(jìn)程，通過它們自己獨(dú)立的操作進(jìn)行系統(tǒng)調(diào)度，享受獨(dú)立的CPU和內(nèi)存資源（即共享內(nèi)存），進(jìn)程中通過消息傳遞實(shí)現(xiàn)訊息的交換。它是一種一次能夠施行多個(gè)命令的算法，是一個(gè)能夠在同一時(shí)間內(nèi)利用各種不同的計(jì)算方式求解計(jì)算問題的歷程，是一種有效的提高計(jì)算速率和處理能力的運(yùn)算方法。其根本思想是使用多個(gè)處理器來解決同樣的問題。換言之，就是將問題分成幾個(gè)部分，每個(gè)部分由一個(gè)單獨(dú)的處理器進(jìn)行解決的運(yùn)算歷程[6-7]。

進(jìn)程：一個(gè)具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)，是CPU 資源分配的最小單位。

線程：建立在進(jìn)程的基礎(chǔ)上的一次程序運(yùn)行單位，被包含在進(jìn)程之中，是CPU 調(diào)度的最小單位，也是進(jìn)程中的實(shí)際運(yùn)作單位。

并行體：并行計(jì)算的數(shù)據(jù)規(guī)模。

并行數(shù)目：并行計(jì)算的次數(shù)。

加速比：同一個(gè)任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間的比率，用來衡量并行系統(tǒng)或程序并行化的性能和效果。

1.3 編譯環(huán)境

在本文中所以涉及到的計(jì)算的軟件環(huán)境是：64 位windows7 操作系統(tǒng)和CodeBlocks（版本13.12.0.0）編譯器，編程語(yǔ)言：C、C++和OpenMP，硬件環(huán)境是：Intel（R）Core（TM）i3_2375M 的雙核CPU（1.50GHz，1.50GHz），4G 內(nèi)存，AMD Radeon HD 7450M 與Intel（R）HD Graphics 3000 雙顯卡（基本上已經(jīng)是很落后的硬件環(huán)境，這種設(shè)備的機(jī)器能夠在跳蚤市場(chǎng)以十分低廉的價(jià)錢獲得），編譯優(yōu)化參數(shù)為-O2。

2 基于OpenMP技術(shù)探究并行體對(duì)運(yùn)行效率的影響

本節(jié)在保持并行數(shù)目不變的情況下，改變數(shù)據(jù)規(guī)模的大小，基于OpenMP技術(shù)探究并行體對(duì)運(yùn)行效率的影響。

以歐拉計(jì)劃[8]145 題為例。歐拉計(jì)劃是由Colin Hughes 發(fā)起的一個(gè)解題網(wǎng)站，目前這個(gè)網(wǎng)站包含了400多道難度不同的數(shù)學(xué)題，題目序號(hào)的增加與難度呈正相關(guān)，每一個(gè)問題都有相應(yīng)的討論社區(qū)，而且每個(gè)問題都可以在 1 分鐘內(nèi)通過計(jì)算機(jī)程序獲得。

145 題的題目?jī)?nèi)容為：某些正整數(shù)n 有這種特殊的特征：N 和N 取“相反”相加以后的全部的位都是奇數(shù)。例如：36+63=99 或者409+904=1313，我們把這些特殊的數(shù)字作為可反數(shù)，因此36，63 等這些數(shù)都是可反數(shù)。但是在N 和N 取“相反”的最前端都不能有0，一千以內(nèi)共含120 個(gè)可反數(shù)，問10 億（即109）以內(nèi)共含幾個(gè)可反數(shù)？

利用計(jì)算機(jī)進(jìn)行編程計(jì)算，可得到上述問題的正確答案為：60872。求解的串行計(jì)算偽代碼為：

通過實(shí)際計(jì)算，改變并形體的大小，取三次平均耗時(shí)，得到串行計(jì)算的運(yùn)算時(shí)間如表1所示。

接下來，采用并行（并行數(shù)目為2 次）編譯方式，對(duì)上述歐拉145 題進(jìn)行求解。將上述的串行偽代碼改寫為基于OpenMP 技術(shù)的并行偽代碼：

在測(cè)試環(huán)境近似相同且保證運(yùn)算結(jié)果相同的情況下，改變并形體的大小，取三次平均耗時(shí)，可得到并行計(jì)算（并行數(shù)目為2 次）的運(yùn)算時(shí)間如表2所示。

表2：歐拉計(jì)劃145 題并行計(jì)算所耗時(shí)長(zhǎng)

表3給出了歐拉計(jì)劃145題串行計(jì)算與并行計(jì)算（并行數(shù)目為2 次）的加速比。顯然，隨著并形體的變化，即數(shù)據(jù)規(guī)模的不斷增加，只有極少數(shù)情況下規(guī)模越大加速比越小，絕大部分情況下加速比與并形體規(guī)模大小呈正相關(guān)。

表3：串行計(jì)算與并行計(jì)算的加速比

通過表1 和表2 以及表3 的結(jié)果對(duì)比，直觀地顯示出了基于OpenMP 技術(shù)并行計(jì)算的優(yōu)越性。在保持并行數(shù)目不變的情況下，隨著并行體的規(guī)模逐步增大，并行計(jì)算對(duì)運(yùn)行效率的影響越大，并行計(jì)算的優(yōu)勢(shì)體現(xiàn)得越明顯。

3 基于OpenMP技術(shù)探究并行數(shù)目對(duì)運(yùn)行效率的影響

本節(jié)在保持并行體不變的情況下，即設(shè)置并行體中的數(shù)據(jù)規(guī)模相同，改變并行數(shù)目的次數(shù)，基于OpenMP技術(shù)探究并行數(shù)目對(duì)運(yùn)行效率的影響。

以蒙特·卡洛法[9]（Monte Carlo）求解π值為例。蒙特·卡洛法也稱為計(jì)算機(jī)的模擬方法，在20所示40年代由烏拉姆和J.馮·諾伊曼提出的一種基于“隨機(jī)數(shù)”的計(jì)算方式。其根本思想是，當(dāng)一個(gè)問題是某個(gè)事件發(fā)生的概率，或某個(gè)隨機(jī)變量的數(shù)學(xué)期望時(shí)，它們能夠通過一些“測(cè)試”，求出該事件的概率或者這個(gè)隨機(jī)數(shù)的平均值，并以此來作為該問題的解。

利用蒙特·卡洛法求解π 值的串行偽代碼如下：

通過該方法進(jìn)行編程計(jì)算，得到的最大隨機(jī)數(shù)為：32767。由蒙特·卡洛算法模擬出的半徑為1 的1/4 圓的面積為：0.785428，計(jì)算出的pi 值為：3.14171。

在測(cè)試環(huán)境近似相同的情況下，分別在并行數(shù)目取1次（即串行計(jì)算）、取2次一直取到183次進(jìn)行計(jì)算測(cè)試，其運(yùn)算結(jié)果如表4所示。

表4：蒙特·卡洛法求解π 值計(jì)算所耗時(shí)長(zhǎng)

由表4 的結(jié)果，得到并行數(shù)目與計(jì)算耗時(shí)關(guān)系如圖1所示。

圖1：并行數(shù)目與計(jì)算耗時(shí)的關(guān)系

通過表4 和圖1 結(jié)果顯示了，在保持并行體規(guī)模不變的情況下，且在CPU 物理極限范圍內(nèi)，并行數(shù)次數(shù)越高，并行計(jì)算對(duì)運(yùn)行效率的影響越大，所需耗時(shí)越短，優(yōu)勢(shì)越顯著，較好地體現(xiàn)了基于OpenMP 技術(shù)并行計(jì)算的優(yōu)越性。

4 結(jié)語(yǔ)

本文基于OpenMP 技術(shù)進(jìn)行并行計(jì)算，采用控制變量法的思想，以歐拉計(jì)劃145 題為例，探究了并行體對(duì)運(yùn)行效率的影響；以蒙特·卡洛法求解π 值為例，探究了并行數(shù)目對(duì)運(yùn)行效率的影響。通過實(shí)際算例與原有串行方法相比較，驗(yàn)證了基于OpenMP 并行計(jì)算的優(yōu)越性。但是，本文給出的兩個(gè)計(jì)算實(shí)例，測(cè)試時(shí)運(yùn)行環(huán)境只是相近，而非完全一致，系統(tǒng)中其他程序?qū)y(cè)試結(jié)果還是造成了一定程度的干擾，且計(jì)算規(guī)模都稍偏小，大規(guī)模的并形體對(duì)運(yùn)行效率的影響還需要進(jìn)一步的研究。其次，測(cè)試的計(jì)算機(jī)（雙核四線程）CPU 線程有限，并行數(shù)目也比較受限，多線程的并行數(shù)目對(duì)運(yùn)行效率的影響還需要進(jìn)一步的研究。