如果這篇博客對您有用的話，可以給我點(diǎn)個(gè)贊嗎，這對我很重要，謝謝！??

文章目錄

• 2 基礎(chǔ)并行計(jì)算
• • 2.1 并行算法的基礎(chǔ)知識
  • • 2.1.1 并行算法的基本概念
    • 2.1.2 并行算法的表達(dá)
    • 2.1.3 并行算法的復(fù)雜性度量
    • • 2.1.3.1 概述
      • 2.1.3.2 串行和并行算法的復(fù)雜性度量
      • 2.1.3.3 Brent定理
    • 2.1.4 并行算法中的同步和通信
    • • 2.1.4.1 并行算法的同步
      • 2.1.4.2 并行算法的通信
  • 2.2 并行計(jì)算模型的回顧

2 基礎(chǔ)并行計(jì)算

2.1 并行算法的基礎(chǔ)知識

2.1.1 并行算法的基本概念

在開始這一小節(jié)之前，容我們先了解幾個(gè)概念：

術(shù)語解釋

算法	解題方法和步驟的精確描述
并行算法	一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動作從而達(dá)到給定問題的求解
數(shù)值算法	基于數(shù)值計(jì)算原理，使用代數(shù)運(yùn)算的一類算法
非數(shù)值算法	基于比較關(guān)系，使用符號運(yùn)算的一類算法
同步算法	一種隱含同步要求的諸進(jìn)程執(zhí)行必須相互等待的一類并行算法
異步算法	一種顯式同步要求的諸進(jìn)程執(zhí)行不必相互等待的一類并行算法
確定算法	算法的每一步都明確指定下一步如何進(jìn)行的一類算法
隨機(jī)算法	算法執(zhí)行時(shí)，隨機(jī)從指定范圍內(nèi)選擇某些參數(shù)，以此確定算法運(yùn)行過程的一類算法
分布算法	泛指由通信鏈路連接的多個(gè)場點(diǎn)或節(jié)點(diǎn)，協(xié)同完成計(jì)算的一類并行算法

其中算法我們提倡用形式描述，即用計(jì)算機(jī)的某種編程語言來描述。對于算法來說，算法可以簡單地范圍串行算法和并行算法。串行算法和并行算法是相對于物理設(shè)備來講的，如果一個(gè)算法運(yùn)行在單處理機(jī)上，那么我們說其為串行算法；如果一個(gè)算法是允許在并行機(jī)（不包含并行單處理機(jī)）或者多處理機(jī)上，那么該算法為并行算法。

對于一般算法來說還可以分為數(shù)值算法和非數(shù)值算法。對于數(shù)值算法來說，我們可以用矩陣等代數(shù)處理方法進(jìn)行計(jì)算；而對于非數(shù)值算法來說，我們一般用比較，如a>b，而非$\frac{3}{5}$這類具體數(shù)的計(jì)算過程。

還有一種是，我們可以分為同步算法和異步算法，同步算法可以用于銀行轉(zhuǎn)賬，此時(shí)關(guān)于轉(zhuǎn)賬的轉(zhuǎn)賬人進(jìn)程和被轉(zhuǎn)賬人進(jìn)程必須同步進(jìn)行；而對于進(jìn)程來說是具有異步性的，當(dāng)我們對于一件事要分成很多步驟來執(zhí)行時(shí)，就可以使用異步算法一步一步走下去，如同接力棒一般。當(dāng)然，對于大多數(shù)情況，同步算法相對于異步算法來說會比較慢，因?yàn)橥剿惴ㄒ髢蓚€(gè)進(jìn)程必須同步進(jìn)行，如果此時(shí)一個(gè)進(jìn)程較慢，那么較快的進(jìn)程需等待；而異步算法不要求一件事必須做完才能做下一件事，它可以錯開進(jìn)行，無需等待。

并行算法中實(shí)際上蘊(yùn)含著分布式算法，在一些場景中，并行算法有時(shí)候用的是多計(jì)算機(jī)，那么此時(shí)并行算法即為分布式算法；而當(dāng)并行算法用在多處理器單機(jī)上時(shí)，并行算法就不是分布式算法了。關(guān)于并行算法和分布式算法的區(qū)別，在1.1.4我們已經(jīng)談過了，這里就不過多介紹了。分布式算法有時(shí)候也叫網(wǎng)絡(luò)算法或者叫做分而治之方法，因?yàn)閷τ诜植际郊阂话闶峭ㄟ^網(wǎng)絡(luò)來連接的，故名為網(wǎng)絡(luò)算法。

最后談到的是確定算法和隨機(jī)算法，對于我們的這門學(xué)科來說，我們一般談?wù)摰亩际谴_定算法。

2.1.2 并行算法的表達(dá)

對于并行算法的表達(dá)，我們一般可以有兩種形式：物理描述和形式描述。

在前面我們曾經(jīng)提到過我們在這門課用的會是形式描述，即用編程語言來描述算法，但是卻不是一定要能運(yùn)行。類似于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法時(shí)用類C語言來描述算法一般，我們在并行算法中也引入了類Algol和類Pascal來描述算法。

還有一種描述是用物理描述，即直接用語義來描述，比如用文字指明哪里該并行哪里該串行。

在形式描述中，用類Algol和類Pascal來描述算法的時(shí)候，有的是串行語言，有的是并行語言，如果要在代碼中使其并行，我們可以假如并行語句。如下所示：

• par-do語句

for i = 1 to n par-do ... end for

• for all語句

for all Pi,where 0<=i<=k do...end for

對于第一個(gè)示例來說，其過程實(shí)際上是：我們給進(jìn)程編號1到n，其中計(jì)算內(nèi)容例如有$a_i+b_i$，那么進(jìn)程1做$a_1+b_1$,進(jìn)程2做$a_2+b_2$，以此類推，并且n個(gè)進(jìn)程是并行的在做這樣一件事。需要注意的是，一般以for開頭，就要以end for結(jié)尾，這是一個(gè)必須的工作。當(dāng)然，也不強(qiáng)制要求一定要用這種形式，你也可以用C++中學(xué)過的花括號括起也是可以的。

同時(shí)，在書寫的過程中一定要注意縮進(jìn)，雖然這不是一種強(qiáng)制要求，但這是一種好習(xí)慣，方便閱讀的層次。

對于第二個(gè)示例來說，$P_i$既可以表示進(jìn)程，也可以表示處理器，具體情況具體分析，而上面的代碼說明了對于編號i（0<=i<=k）的進(jìn)程，都做省略號部分代碼所做的事。其中i可以是以0為索引，n-1為結(jié)束；也可以是1開始，n結(jié)束，這看個(gè)人喜好。

2.1.3 并行算法的復(fù)雜性度量

2.1.3.1 概述

一個(gè)并行算法設(shè)計(jì)好了， 一定要度量其復(fù)雜性。在數(shù)據(jù)結(jié)構(gòu)與算法的課中我們曾經(jīng)談?wù)撘粋€(gè)算法的復(fù)雜度是用漸進(jìn)復(fù)雜度量衡量的，這里同樣地，我們也是用復(fù)雜度的漸進(jìn)表示，即n趨近于無窮大時(shí)。

設(shè)f(n)和g(n)是自然數(shù)集合上的兩個(gè)函數(shù)，其中$C，C_1,C_2$都是正整數(shù)。那么有上界：$f(n)=O(g(n)),f(n)<=Cg(n)$，也有下界：$f(n)=\Omega (g(n)),f(n)>=Cg(n)$。

其中緊致界為：$f(n)=\Theta (g(n)),C_{1}g(n)<=f(n)<=C_{2}g(n)$。其中緊致界也叫精確界。

上面的每次可能聽著很懵，但是如果我換一個(gè)術(shù)語你馬上就懂了，上界叫做最壞復(fù)雜度，下界叫做最好復(fù)雜度。最壞時(shí)間復(fù)雜度和最好時(shí)間復(fù)雜度時(shí)間相差的區(qū)域即為精確界。

2.1.3.2 串行和并行算法的復(fù)雜性度量

對于串行算法的復(fù)雜性度量一般分析兩種，即最壞情況下的復(fù)雜度和期望復(fù)雜度，其中期望復(fù)雜度也叫平均復(fù)雜度。這些在數(shù)據(jù)結(jié)構(gòu)中都已學(xué)過這里不細(xì)講。

而對于并行算法的復(fù)雜性度量一般有四種：運(yùn)行時(shí)間t(n)、處理器數(shù)p(n)、并行算法成本c(n)和總運(yùn)算量W(n)。其中c(n) = t(n)×p(n)，W(n)為并行算法求解問題時(shí)所完成的總的操作步數(shù)。

2.1.3.3 Brent定理

Brent定理衡量了W(n)和T(n)的關(guān)系。令W(n)是某并行算法A在運(yùn)行時(shí)間T(n)內(nèi)所執(zhí)行的運(yùn)算量，則A使用p臺處理器可在t(n) = O(W(n)/p+T(n))時(shí)間內(nèi)執(zhí)行完畢。

在上面的敘述中可以看出：

• W(n)和c(n)密切相關(guān)
• P = O(W(n)/T(n))時(shí)，W(n)和c(n)兩者是漸進(jìn)一致的
• 對于任意的p，c(n)>W(n)

2.1.4 并行算法中的同步和通信

2.1.4.1 并行算法的同步

同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待，這種方式可用軟件、硬件和固件的辦法來實(shí)現(xiàn)。

上面的同步概念可以用一個(gè)例子來說明，假如一個(gè)老師帶領(lǐng)一幫學(xué)生去公司實(shí)習(xí)，實(shí)習(xí)這件事就是并行算法需要干的事，而干這件事是需要所有學(xué)生都到達(dá)，而各學(xué)生相當(dāng)于進(jìn)程，每個(gè)進(jìn)程具有異步性，有的進(jìn)程執(zhí)行快有的進(jìn)程執(zhí)行慢，快的進(jìn)程則需要等待慢的進(jìn)程，而這個(gè)等待的方式可以用軟硬件和固件來調(diào)控。

如果拿共享存儲多處理器上進(jìn)行求和算法來演示同步語句的話，即如下所示：

輸入：A = $(a_0,...,a_{n?1})$，處理器p

輸出：S = $\sum a_i$

Begin(1)S = 0(2)for all Pi where 0<=i<=p-1 do //啟動多個(gè)處理器(2.1)for j = i to n step p do //把任務(wù)分配給每個(gè)處理器L = L+aj //求局部和end for(2,3)lock(S) //上鎖S = S+L //互斥提交(2.4)unlock(S) //解鎖end forEnd

以上這個(gè)例子我們曾經(jīng)在1.1.3講過，對于共享存儲多處理器做一個(gè)求和工作來說，它相當(dāng)于有多少個(gè)進(jìn)程，就把這個(gè)求和分成多少段，進(jìn)程分配的每段求和相當(dāng)于在求一個(gè)局部和，所有進(jìn)程求完和后，就需要求總和。由于每個(gè)進(jìn)程計(jì)算的速度可能不一，所以就需要進(jìn)程同步機(jī)制，在共享存儲多處理器上這種機(jī)制只用臨界區(qū)來體現(xiàn)的。

臨界區(qū)這個(gè)概念我們曾經(jīng)在操作系統(tǒng)提到過，臨界區(qū)是保存臨界資源的，而臨界資源指的是一個(gè)時(shí)間段只允許一個(gè)進(jìn)程使用的資源。各進(jìn)程需要互斥地訪問臨界資源。對于共享存儲多處理器來說，每個(gè)局部和求解完成后，各個(gè)進(jìn)程需要互斥地往臨界區(qū)中提交局部和，當(dāng)所有局部和提交完成后，才進(jìn)行求總和。

2.1.4.2 并行算法的通信

對于共享存儲多處理器來說，其通常采用global read(x,y)和global write(x,y)來傳遞消息。

在操作系統(tǒng)我們曾經(jīng)學(xué)到過共享存儲，使用共享存儲的方式進(jìn)行進(jìn)程通信的話，操作系統(tǒng)會在內(nèi)存中開辟一個(gè)共享空間，讓兩個(gè)進(jìn)程進(jìn)行通信。假如兩個(gè)進(jìn)程想要互相通信，則一個(gè)進(jìn)程將消息寫于共享存儲單元中，然后另外一個(gè)進(jìn)程去該單元讀該消息。

而對于分布存儲多計(jì)算機(jī)來說，其采用的為send(x,i)和receive(y,i)來傳遞消息。

同樣地，在操作系統(tǒng)中我們也曾經(jīng)學(xué)到過消息傳遞，這也是為什么分布存儲多計(jì)算機(jī)被稱為消息傳遞多計(jì)算機(jī)的原因。其使用消息傳遞，所謂消息傳遞，就是進(jìn)程間的數(shù)據(jù)交換以格式化的消息為單位。進(jìn)程通過操作系統(tǒng)提供的“發(fā)送消息/接受消息”兩個(gè)原語進(jìn)行數(shù)據(jù)交換。

下面我們給出通信語句示例：

算法：環(huán)連接的分布存儲多計(jì)算機(jī)上矩陣向量乘算法

輸入：處理器數(shù)p，A劃分為B = A[1…n,(i-1)r+1…ir],r = n/p，x劃分為w = w[(i-1)r+1;ir]

輸出：$P_1$保存乘積AX

begin(1)Compute z = Bw(2)if i = 1 then yi = 0 else receive(y,left) endif(3)y = y+z(4)send(y.right)(5)if i = 1 then receive(y,left) End

2.2 并行計(jì)算模型的回顧

在前面我們已經(jīng)提到了并行計(jì)算模型，并行計(jì)算模型是算法設(shè)計(jì)者與體系結(jié)構(gòu)家之間的一個(gè)橋梁，是并行算法設(shè)計(jì)和分析的基礎(chǔ)；它屏蔽掉并行機(jī)的差異，從并行機(jī)中抽取若干個(gè)能反映計(jì)算特性的可計(jì)算或可測量的參數(shù)；并按照模型所定義的計(jì)算行為為構(gòu)造成本函數(shù)以此進(jìn)行算法的復(fù)雜度分析。

我們對模型的基本要求是：計(jì)算模型應(yīng)提供反映并行機(jī)計(jì)算特性的一組時(shí)間參數(shù)，它包括cpu性能參數(shù)，多層存儲訪問時(shí)間和網(wǎng)絡(luò)通信特性參數(shù)等。在計(jì)算模型中，我們應(yīng)該定義計(jì)算過程行為，如同步式和異步式。也應(yīng)該給出計(jì)算并行算法時(shí)間復(fù)雜度的成本函數(shù)。

我們設(shè)計(jì)的算法除非是那些學(xué)純理論的人可以不用應(yīng)用，否則其都是要應(yīng)用在并行機(jī)上。應(yīng)用在并行機(jī)上有兩種情況，特別和普遍。特別指的是設(shè)計(jì)的算法只能用于某一種并行機(jī)上，而普遍則是大多數(shù)通用。從學(xué)術(shù)觀點(diǎn)來看，我們更希望設(shè)計(jì)的算法可以實(shí)現(xiàn)后者的情況。

按照模型所定義計(jì)算行為，我們在此基礎(chǔ)上進(jìn)行并行算法的設(shè)計(jì)。根據(jù)模型參數(shù)和計(jì)算行為，構(gòu)造成本函數(shù)。并且我們結(jié)合在具體并行機(jī)上所測量的模型參數(shù)，進(jìn)行并行算法運(yùn)行時(shí)間理論分析。

總結(jié)

以上是生活随笔為你收集整理的并行计算——基础并行计算的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。