并行算法復(fù)習(xí)new

《并行算法復(fù)習(xí)new》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、1.并行算法:一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程相互作用和相互協(xié)調(diào)。2.并行與并發(fā)的關(guān)系：并行<并發(fā)并發(fā)是指兩個(gè)或者多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。在單處理機(jī)系統(tǒng)中，每一時(shí)刻僅能有一道程序執(zhí)行，宏觀上多道程序在同時(shí)運(yùn)行，微觀上這些程序是分時(shí)交替執(zhí)行。3.并行與分布式的關(guān)系：網(wǎng)絡(luò)；并行更注重性能，而分布式更注重透明共享。4.并行與網(wǎng)格計(jì)算（普適計(jì)算）的關(guān)系：網(wǎng)格通過(guò)網(wǎng)絡(luò)連接地理上分布的各類計(jì)算資源、存儲(chǔ)資源、通信資源、軟件資源、信息資源、知識(shí)資源等，形成對(duì)用戶相對(duì)透明的虛擬的高性能計(jì)算環(huán)境，讓人們透明地使用這些資源和功能。它們與并行計(jì)算存在規(guī)模上的差異。5.并行與云計(jì)算的關(guān)系：云計(jì)算以開放的

2、標(biāo)準(zhǔn)和服務(wù)為基礎(chǔ)，以互聯(lián)網(wǎng)為中心，提供安全、快速、便捷的數(shù)據(jù)存儲(chǔ)和網(wǎng)絡(luò)計(jì)算服務(wù)，讓互聯(lián)網(wǎng)這片“云”上的各種計(jì)算機(jī)共同組成數(shù)個(gè)龐大的數(shù)據(jù)中心及計(jì)算中心。云計(jì)算把計(jì)算及存儲(chǔ)以服務(wù)的形式提供給互聯(lián)網(wǎng)用戶，用戶所使用的數(shù)據(jù)、服務(wù)器、應(yīng)用軟件、開發(fā)平臺(tái)等資源都來(lái)自互聯(lián)網(wǎng)上的虛擬化計(jì)算中心，該數(shù)據(jù)中心負(fù)責(zé)對(duì)分布在互聯(lián)網(wǎng)上的各種資源進(jìn)行分配、負(fù)載的均衡、軟件的部署、安全的控制等。6.為什么要研究并行算法？（1）CPU的發(fā)展速度：MooreLaw。（2）“深藍(lán)”計(jì)算機(jī)以3.5:2.5戰(zhàn)勝卡斯帕羅夫。（3）需求：快速（天氣預(yù)報(bào)），提高計(jì)算精度，與理論、實(shí)驗(yàn)并重的科學(xué)方法（代替核武器實(shí)驗(yàn)）7.并行計(jì)算機(jī)分類1.

3、SISD,SingleInstructionStream&SingleDataStream:特征：串行的和確定的。指令系統(tǒng):CISC,RISC2.SIMD,SingleInstructionStream&MultipleDataStream:特征：同步的；確定的；適合于指令/操作級(jí)并行。1)陣列處理機(jī)（資源重復(fù)）;2)流水線處理機(jī)（時(shí)間重疊）.3.MISD,MultipleInstructionStream&SingleDataStream:4.MIMD,MultipleInstructionStream&MultipleDataStream共享存儲(chǔ)MIMD，也稱對(duì)稱多處理機(jī)（SMP，Sym

4、metryMultiProcessors），屬于緊密耦合的多處理機(jī)系統(tǒng)適合于小粒度并行分布式共享存儲(chǔ)MIMD，也稱為非一致內(nèi)存訪問(wèn)（NUMA,Non-UniformMemoryAccess），屬于松耦合的多處理機(jī)系統(tǒng)（共享虛擬存儲(chǔ)技術(shù)）,適合于中小粒度并行分布式存儲(chǔ)MIMD1).大規(guī)模并行系統(tǒng)MPP(MassivelyParallelProcessing)CM-5、曙光1000、神州-Ⅱ巨型機(jī)可以最大限度地增加處理機(jī)的數(shù)量，但結(jié)點(diǎn)間需要依賴消息傳遞進(jìn)行通信，適合于中小粒度并行2).群集系統(tǒng)Cluster特點(diǎn)：適合于粗粒度并行8.網(wǎng)絡(luò)直徑（networkdiameter）：網(wǎng)絡(luò)中最遠(yuǎn)的兩臺(tái)處理

5、機(jī)間的距離，即處理機(jī)間通信所需要跨越的網(wǎng)絡(luò)邊的條數(shù)的最大值。9.等分寬度（bisectionwidth）：網(wǎng)絡(luò)分成兩個(gè)相等部分（節(jié)點(diǎn)數(shù)相等或至多差1）所需要去掉的網(wǎng)絡(luò)邊的條數(shù)。10.并行計(jì)算機(jī)的處理機(jī)互連方式網(wǎng)絡(luò)直徑等分寬度網(wǎng)絡(luò)接口總線結(jié)構(gòu)一維陣列結(jié)構(gòu)n-112網(wǎng)格結(jié)構(gòu)2n-2n4超立方體結(jié)構(gòu)(q維)q2q-1q疊網(wǎng)結(jié)構(gòu)2q2q2q-1(q+1)行，每行有2q個(gè)節(jié)點(diǎn)11.并行計(jì)算模型，并行算法設(shè)計(jì)，并行計(jì)算機(jī)之間的關(guān)系如圖。表明，并行算法設(shè)計(jì)可以從兩個(gè)方面進(jìn)行（1）根據(jù)并行計(jì)算模型設(shè)計(jì)并行算法，然后將其映射到具體的并行計(jì)算機(jī)中（2）直接基于具體并行計(jì)算機(jī)進(jìn)行并行算法的設(shè)計(jì)與分析12.并行計(jì)算

6、模型的作用：（1）為并行算法的研究提供了一個(gè)基礎(chǔ)。（2）為并行算法的設(shè)計(jì)與分析提供了一種簡(jiǎn)單、方便的框架，避開了硬件上許多繁瑣的細(xì)節(jié)。（3）使得設(shè)計(jì)的并行算法具有一定的生命力，可以適用于多種具體的并行計(jì)算機(jī)。13.LogP模型：面向分布式存儲(chǔ)，點(diǎn)對(duì)點(diǎn)通信的多計(jì)算機(jī)系統(tǒng)的并行計(jì)算模型。參數(shù)說(shuō)明：（1）L（Latency）：源處理機(jī)與目標(biāo)處理機(jī)之間進(jìn)行消息通信所需等待延遲時(shí)間的上限。（2）o（overhead）：處理機(jī)用于發(fā)送或接收每個(gè)消息的時(shí)間開銷。（3）g（gap）：一臺(tái)處理機(jī)進(jìn)行連續(xù)發(fā)送或接收消息的最小時(shí)間間隔。（4）P（Processor）：處理機(jī)數(shù)量。特點(diǎn)：（1）只支持P2P通信，不關(guān)

7、心拓?fù)浣Y(jié)構(gòu)（2）消息的傳輸時(shí)間2o+L（3）只支持短消息（4）LogGP支持長(zhǎng)消息通信：tα+n*tβtα消息發(fā)送的啟動(dòng)時(shí)間，tβ是傳輸單位字節(jié)消息傳遞時(shí)間14.并行算法的目標(biāo):由串行的“深而窄”變?yōu)椤皽\而深”15.并行算法的分類1.流水線技術(shù)基本思想是把一個(gè)計(jì)算任務(wù)t，分成一系列子任務(wù)，使得一旦前一子任務(wù)完成下一個(gè)子任務(wù)就可以立即開始。eg:有多個(gè)實(shí)例需要執(zhí)行有一系列數(shù)據(jù)需要處理，并且每個(gè)數(shù)據(jù)需要多次進(jìn)行操