并行算法第一章并行計(jì)算性能測評

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

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

3、共享存儲多處理機(jī)DSM45工作站機(jī)群COW461.2 并行計(jì)算機(jī)系統(tǒng)互連47靜態(tài)互連網(wǎng)絡(luò)48動態(tài)連接49網(wǎng)絡(luò)性能指標(biāo)50網(wǎng)絡(luò)性能指標(biāo)51靜態(tài)互連網(wǎng)絡(luò)（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二進(jìn)制碼與格雷碼1 , 2,.11mibbgbgiiimm1 , 2,.11migbbgbi

5、iimm69二進(jìn)制編碼與格雷編碼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)絡(luò)特性比較74洗牌交換網(wǎng)絡(luò)75交換網(wǎng)絡(luò)洗牌交換網(wǎng)絡(luò)77逆洗牌交換網(wǎng)絡(luò)78逆洗牌交換網(wǎng)絡(luò)動態(tài)互連網(wǎng)絡(luò)7980公共總線81交叉開關(guān)（Croosbar）82交叉開關(guān)（Croosbar）83多級互連網(wǎng)絡(luò)84多級互連網(wǎng)絡(luò)85多級互連網(wǎng)絡(luò)86多級互連網(wǎng)絡(luò)-交換開關(guān)87多級互連網(wǎng)絡(luò)-拓?fù)浣Y(jié)構(gòu)88多級互連網(wǎng)絡(luò)-控制方式89多級互連網(wǎng)絡(luò)90

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