并行算法概述課件

一并行算法的目標(biāo)和分類(lèi)

1并行算法的目標(biāo)由串行的“深而窄”變?yōu)椤皽\而深”2并行算法的分類(lèi)二并行算法設(shè)計(jì)方法

1.流水線(xiàn)技術(shù)下述三種類(lèi)型的問(wèn)題比較適合用流水線(xiàn)技術(shù)：有多個(gè)實(shí)例需要執(zhí)行有一系列數(shù)據(jù)需要處理，并且每個(gè)數(shù)據(jù)需要多次進(jìn)行操作

一個(gè)進(jìn)程在執(zhí)行完之前，能夠傳遞執(zhí)行下一個(gè)進(jìn)程的消息

2.分治策略：分而治之的原則是把一個(gè)問(wèn)題分裂為若干個(gè)較小的子問(wèn)題，這些問(wèn)題可彼此獨(dú)立地并行求解。數(shù)據(jù)分割：數(shù)據(jù)分割是指各結(jié)點(diǎn)基本執(zhí)行相同的任務(wù)，只是數(shù)據(jù)不同。此方法常用在計(jì)算的各數(shù)據(jù)之間具有對(duì)稱(chēng)性的情況。例如對(duì)于向量的加法，可以分割為各個(gè)分量的加法。任務(wù)分割：任務(wù)分割是指總?cè)蝿?wù)由自然的數(shù)個(gè)子任務(wù)組成，將其分?jǐn)傇诟鱾€(gè)結(jié)點(diǎn)上。例如對(duì)于連續(xù)的數(shù)據(jù)處理任務(wù)，可以將其分割成數(shù)據(jù)采集、數(shù)據(jù)計(jì)算和結(jié)果輸出三個(gè)子任務(wù)。

它是設(shè)計(jì)并行算法的根本準(zhǔn)則。例計(jì)算Y=(A+B(C+DEF))+G

串行計(jì)算：需6步；并行計(jì)算：Y=Y1+Y2Y1=A+G+BC,Y2=BDEF

如用兩臺(tái)計(jì)算機(jī)的系統(tǒng)，并行計(jì)算步為4；如用四臺(tái)計(jì)算機(jī)的系統(tǒng)，并行計(jì)算步為3。3.指針跳躍技術(shù)：每當(dāng)遞歸調(diào)用時(shí)，所要處理的數(shù)據(jù)之間的距離將逐步加倍，經(jīng)過(guò)步k后就可完成距離為2k的所有數(shù)據(jù)的計(jì)算。下面我們利用倍增技術(shù)來(lái)解決線(xiàn)性遞歸問(wèn)題的并行計(jì)算。

函數(shù)Q(s,t)有以下性質(zhì)：（1）Q（i，i）＝bii＝1，2，…，n；（2）當(dāng)s<t，對(duì)于任意非負(fù)整數(shù)l，s＋l<t，我們有

（3）Q（1，i）＝xi,i＝1，2，…，n。

例如取，的計(jì)算過(guò)程的遞推分解情況如下：

第一次分解：

第二次分解：

第三次分解：

使用臺(tái)處理機(jī)，計(jì)算個(gè)元素值

（），需步計(jì)算。

4.平衡樹(shù)方法：將輸入元素作為葉節(jié)點(diǎn)構(gòu)筑一棵平衡二叉樹(shù)，然后自葉向根往返遍歷。此法成功的部分原因是在樹(shù)中能快速地存取所需要的信息。5.加速級(jí)聯(lián)策略：為了獲得一個(gè)快速最優(yōu)的算法，我們可以將一個(gè)最優(yōu)但相對(duì)不快的算法與另一個(gè)非?？斓皇亲顑?yōu)的算法級(jí)聯(lián)（或串聯(lián)）起來(lái)，形成一個(gè)加速級(jí)聯(lián)算法。雙對(duì)數(shù)深度樹(shù)

當(dāng)用雙對(duì)數(shù)深度樹(shù)求最大值時(shí)，每一層的最大值可在O（1）時(shí)間內(nèi)計(jì)算完（在SIMD－CRCW模型上用枚舉法[6]），因此，求最大值的時(shí)間T（n）＝O（loglogn），可見(jiàn)，它比平衡二叉樹(shù)上求最大值要快指數(shù)倍。但總的運(yùn)算量W（n）＝O（nloglogn）

第一步：運(yùn)行對(duì)數(shù)深度的平衡二叉樹(shù)算法，從葉結(jié)點(diǎn)向上直到層。由于逐次向上每層將使候選的數(shù)目減少二分之一，所以在該算法結(jié)束時(shí)，最大數(shù)將處于個(gè)元素之中，并且至此所使用的運(yùn)算量為，相應(yīng)的時(shí)間為。第二步：對(duì)第一步所產(chǎn)生的個(gè)最大值的候選數(shù)，運(yùn)行雙對(duì)數(shù)深度樹(shù)算法。此步所使用的運(yùn)算量，相應(yīng)的時(shí)間為。因此，整個(gè)算法的運(yùn)行時(shí)間為而運(yùn)算量為。三并行算法性能度量

1.運(yùn)行時(shí)間：2.并行度：

并行度與任務(wù)粒度的關(guān)系：3.成本：4.加速比和效率：說(shuō)明：（1）線(xiàn)性加速比；（2）超線(xiàn)性加速比：一般情況下是不會(huì)發(fā)生的（額外開(kāi)銷(xiāo)），但某些情形下會(huì)發(fā)生。（3）實(shí)用的加速比定義：串行算法運(yùn)行時(shí)間/并行算法運(yùn)行時(shí)間。5.并行算法的可擴(kuò)展性分析：并行算法的可擴(kuò)展性是對(duì)并行算法有效利用增加的處理機(jī)數(shù)目能力的一種度量，與算法設(shè)計(jì)內(nèi)在并行性和通信需求有關(guān)。

對(duì)某些并行算法而言，在處理器數(shù)增加的情況下，只要適當(dāng)?shù)卦黾訂?wèn)題規(guī)模，可以保持算法的效率不變，此即并行算法可擴(kuò)展性的恒等效率度量方法。

四并行加速比模型

1.Amdahl加速比模型：2.Gustafson加速比模型：1988年2月美國(guó)Sandia國(guó)家