并行算法第一章并行計算性能測評

1、23教材、參考書主要內容5第一章并行計算機系統(tǒng)及結構模型1.1 并行計算概論671.1.1并行處理的含義8并行性的含義9并行性的含義),.,(211nxxxv ),.,(212nyyyv nnyxyxyxvvR.22112110并行性的含義11并行性的含義niyxzzizRiiii, 2 , 10010121,.,xxxxnn121,.,yyyynn121.1.2 并行處理的應用13并行處理的應用14氣象數(shù)值預報15海洋學、天體物理16遙測地球資源數(shù)據(jù)處理17石油開采及管理18石油開采及管理19工程計算20社會經濟學及政府部門21國防、人工智能、基礎研究22國防、人工智能、基礎研究23當代科學

2、與工程問題的計算需求24當代科學與工程問題的計算需求25HPCC應用領域26科學計算的需要27當代科學與工程問題的計算需求28美國美國ASCI計劃計劃29并行處理中的幾個難題30并行處理中的幾個難題傳統(tǒng)傳統(tǒng)Von Neumann結構及其存在問題結構及其存在問題31存儲器指令寄存器、計數(shù)器存儲器指令數(shù)據(jù)指令流驅動32研究并行處理應考慮的幾個問題33并行處理機系統(tǒng)的優(yōu)點341.1.3 并行處理機的分類35Flynn分類法36SISD37SIMD38MIMD39Handler分類法,)(WWDDKKcT40按體系結構分類41現(xiàn)代并行機結構分類42對稱多處理機SMP43大規(guī)模并行處理機MPP44分布式

3、共享存儲多處理機DSM45工作站機群COW461.2 并行計算機系統(tǒng)互連47靜態(tài)互連網(wǎng)絡48動態(tài)連接49網(wǎng)絡性能指標50網(wǎng)絡性能指標51靜態(tài)互連網(wǎng)絡（1）52一維線性陣列一維線性陣列201)(111)(11nPPPLCnPPPLC右連接：左連接：53一維線性陣列2/N54二維網(wǎng)孔二維網(wǎng)孔55二維網(wǎng)孔二維網(wǎng)孔56二維網(wǎng)孔二維網(wǎng)孔57二維網(wǎng)孔二維網(wǎng)孔) 1(2NN1NN22/2NN2(a)2-D網(wǎng)孔(b)Illiac網(wǎng)孔(c)2-D環(huán)繞58網(wǎng)孔連接)()()()(222121PMCPMCPMCPMCNNNNPmod)1(NNNPmod)(NNPmod)1(NNNPmod)(59網(wǎng)孔連接)15,11

4、, 7 , 3)(14,10, 6 , 2)(13, 9 , 5 , 1)(12, 8 , 4 , 0()()0 , 4 , 8 ,12)(1 , 5 , 9 ,13)(2 , 6 ,10,14)(3 , 7 ,11,15()()15,14,.,1 , 0()()0 , 1,.,14,15()(2162162121PMCPMCPMCPMC網(wǎng)孔連接1N61樹形連接62樹形連接311log22N樹形連接的典型用法64超立方體連接nN22/N65超立方體連接66立方環(huán)連接（環(huán)型嵌入超立方體）67立方環(huán)連接68二進制碼與格雷碼1 , 2,.11mibbgbgiiimm1 , 2,.11migbbgbi

5、iimm69二進制編碼與格雷編碼70立方環(huán)連接71立方環(huán)連接72立方環(huán)連接73NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/( kN1NN)(2NN N2N21N1N2/nN2/3N靜態(tài)互連網(wǎng)絡特性比較74洗牌交換網(wǎng)絡75交換網(wǎng)絡洗牌交換網(wǎng)絡77逆洗牌交換網(wǎng)絡78逆洗牌交換網(wǎng)絡動態(tài)互連網(wǎng)絡7980公共總線81交叉開關（Croosbar）82交叉開關（Croosbar）83多級互連網(wǎng)絡84多級互連網(wǎng)絡85多級互連網(wǎng)絡86多級互連網(wǎng)絡-交換開關87多級互連網(wǎng)絡-拓撲結構88多級互連網(wǎng)絡-控制方式89多級互連網(wǎng)絡90

6、多級互連網(wǎng)絡91多級互連網(wǎng)絡思考題931.3 并行處理機的系統(tǒng)結構941.3.1并行向量處理機PVP95對稱多處理機SMP96大規(guī)模并行處理機MPP97分布共享存儲多處理機DSM工作站機群COW99公用結構100shell結構101公用結構 102公用結構 103小結 1041.3.2 并行計算機訪存模型105均勻存儲訪問模型UMA106非均勻存儲訪問模型NUMA107全高速緩存存儲訪問模型COMA108全高速緩存存儲訪問模型COMA高速緩存一致性非均勻存儲訪問模型110高速緩存一致性非均勻存儲訪問模型111高速緩存一致性非均勻存儲訪問模型112非遠程存儲訪問模型NORMA非遠程存儲訪問模型NORMA小結114115小結屬性屬性PVPSMPMPPDSMCOW結構類型結構類型處理器類型處理器類型互連網(wǎng)絡互連網(wǎng)絡通信機制通信機制地址空間地址空間系統(tǒng)存儲器系統(tǒng)存儲器訪存模型訪存模型MIMDMIMDMIMDMIMDMIMD專用定制專用定制商用商用商用商用商用商用商用商用定制交叉定制交叉 開關開關總線交總線交叉開關叉開關定制網(wǎng)絡定制網(wǎng)絡定制網(wǎng)絡定制網(wǎng)絡商用網(wǎng)絡商用網(wǎng)絡共享變量共享變量共享變量共享變量共享變量共享變量消息傳遞消息傳遞消息傳遞消息傳遞單地址單地址單地址單地址單地址單地址多地址多地址多地址多地址集中共享集中共享集中共享集中共享分布不共享分布不共享分布不共享分布不