并行計(jì)算機(jī)體系結(jié)構(gòu)第3章

1、1第三章第三章 并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)體系結(jié)構(gòu) 2第一節(jié)第一節(jié) 并行計(jì)算機(jī)系統(tǒng)簡介并行計(jì)算機(jī)系統(tǒng)簡介 一、并行一、并行向量處理機(jī)向量處理機(jī) 1 1、向量處理方式、向量處理方式 * *橫向處理：橫向處理：每次處理完向量的一個(gè)每次處理完向量的一個(gè)分量分量 如如D=AD=A(B+C)(B+C)，N N次處理次處理d di i= =a ai i( (b bi i+c+ci i) ) * *縱向處理：縱向處理：每次處理完向量的一個(gè)子操作；每次處理完向量的一個(gè)子操作； 如如兩次處理兩次處理E=B+CE=B+C及及D=AD=AE E 特征特征向量長度不受限制，宜于向量長度不受限制，宜于M-MM-M型向

2、量型向量處理機(jī)處理機(jī) * *縱橫處理：縱橫處理：對向量分組，組內(nèi)縱向?qū)ο蛄糠纸M，組內(nèi)縱向( (大小大小n n受硬件限制受硬件限制) )、組、組間橫向處理，宜于間橫向處理，宜于R-RR-R型向量型向量處理機(jī)處理機(jī)存儲系統(tǒng)存儲系統(tǒng)載入緩沖器載入緩沖器存儲緩沖器存儲緩沖器流水處理部件流水處理部件回下頁32 2、向量處理機(jī)結(jié)構(gòu)、向量處理機(jī)結(jié)構(gòu) 根據(jù)向量元素和結(jié)果存放根據(jù)向量元素和結(jié)果存放位置，可分為位置，可分為M-MM-M和和R-RR-R型型 * *向量功能部件：向量功能部件：向量的各分量采用流水操作方式；向量的各分量采用流水操作方式； * *向量存取部件：向量存取部件：采用特殊手段完成向量快速存?。?/p>

3、采用特殊手段完成向量快速存??； * *向量寄存器：向量寄存器： 由由V V、V VM M、V VL L組成組成主主存存標(biāo)量寄存器標(biāo)量寄存器標(biāo)量功能部件標(biāo)量功能部件向量功能部件向量功能部件向量寄存器向量寄存器/ /向量緩沖器向量緩沖器向量指令向量指令控制部件控制部件向量存取向量存取部件部件指令指令處理部件處理部件向量功能部件向量功能部件向量處理機(jī)向量處理機(jī)大容量大容量存儲器存儲器主計(jì)主計(jì)算機(jī)算機(jī)用戶用戶I/OI/O向量功能部件向量功能部件轉(zhuǎn)上頁43 3、提高向量處理性能的方法、提高向量處理性能的方法(1)(1)多個(gè)功能部件并行操作技術(shù)多個(gè)功能部件并行操作技術(shù) * *向量指令并行執(zhí)行的條件：向量指

4、令并行執(zhí)行的條件： a)a)不不存在向量寄存器使用存在向量寄存器使用沖突；沖突； b)b)不存在功能部件使用不存在功能部件使用沖突沖突(2)(2)鏈接技術(shù)鏈接技術(shù) 采用采用“旁旁路路”思想思想，解決指令，解決指令中向量寄存器的中向量寄存器的RAWRAW冒險(xiǎn)，冒險(xiǎn)，實(shí)現(xiàn)實(shí)現(xiàn)向量指令串向量指令串的的“并行并行”執(zhí)行執(zhí)行(3)(3)條件語句和稀疏矩陣的處理技術(shù)條件語句和稀疏矩陣的處理技術(shù) 利用向量屏蔽利用向量屏蔽控制技術(shù)，將控制技術(shù)，將標(biāo)量語句循環(huán)標(biāo)量語句循環(huán)向量語句；向量語句； 利用位向量利用位向量+ +壓縮向量壓縮向量技術(shù)實(shí)現(xiàn)技術(shù)實(shí)現(xiàn)稀疏矩陣，減少帶寬稀疏矩陣，減少帶寬需求需求(4)(4)向量規(guī)

5、約技術(shù)向量規(guī)約技術(shù) 對向量寄存器的分量計(jì)數(shù)器進(jìn)行對向量寄存器的分量計(jì)數(shù)器進(jìn)行控制，實(shí)現(xiàn)控制，實(shí)現(xiàn)復(fù)雜復(fù)雜功能功能54 4、并行向量處理機(jī)、并行向量處理機(jī)(PVP)(PVP) * *定義：定義：由多個(gè)由多個(gè)向量處理器向量處理器(VP)(VP)構(gòu)成的構(gòu)成的能夠并行處理多個(gè)向能夠并行處理多個(gè)向量的量的向量多處理機(jī)向量多處理機(jī)，又稱多向量，又稱多向量機(jī)機(jī)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)( (縱橫交叉開關(guān)縱橫交叉開關(guān)) )VPVPVPVPVPVPSMSMSMSMSMSM并行向量處理機(jī)并行向量處理機(jī)PVPPVP * *特點(diǎn)：特點(diǎn)：屬屬M(fèi)IMDMIMD類型機(jī)；類型機(jī)； 每個(gè)每個(gè)VPVP按地址可訪問所有按地址可訪問所有共享存

6、儲器共享存儲器 * *節(jié)點(diǎn)互連：節(jié)點(diǎn)互連： 能夠能夠同時(shí)同時(shí)實(shí)現(xiàn)實(shí)現(xiàn)任意任意節(jié)點(diǎn)間互連；節(jié)點(diǎn)間互連； 一般一般采用交叉開關(guān)實(shí)現(xiàn)采用交叉開關(guān)實(shí)現(xiàn)(n(n入到達(dá)任意入到達(dá)任意n n出出) )6二、二、SIMDSIMD計(jì)算機(jī)計(jì)算機(jī) 1 1、SIMDSIMD機(jī)結(jié)構(gòu)機(jī)結(jié)構(gòu) * *結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)：控制器控制器(CU)(CU)執(zhí)行標(biāo)量和程序流控制指令；執(zhí)行標(biāo)量和程序流控制指令； 所有所有PUPU操作操作相同，數(shù)據(jù)不同；相同，數(shù)據(jù)不同； 不同不同結(jié)構(gòu)時(shí)互連網(wǎng)絡(luò)的作用結(jié)構(gòu)時(shí)互連網(wǎng)絡(luò)的作用( (方向方向) )不同不同 * *節(jié)點(diǎn)互連：節(jié)點(diǎn)互連：要求能夠要求能夠同時(shí)同時(shí)實(shí)現(xiàn)實(shí)現(xiàn)多對多對( (非任意非任意) )節(jié)

7、點(diǎn)間節(jié)點(diǎn)間互連互連 基于互連基于互連硬件設(shè)計(jì)并行算法硬件設(shè)計(jì)并行算法集中式集中式SIMDSIMD互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)CUCUM M0 0M M1 1M Mm-1m-1PUPU0 0PUPU1 1PUPUn-1n-1M M0 0PUPU0 0PEPE0 0CUCU互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)M Mm-1m-1PUPUn-1n-1PEPEn-1n-1分布式分布式SIMDSIMD72 2、SIMDSIMD并行算法并行算法 * *常用算法：常用算法：有限差分、矩陣加、矩陣乘、累加求和有限差分、矩陣加、矩陣乘、累加求和等等 * *與與SIMDSIMD計(jì)算機(jī)關(guān)系：計(jì)算機(jī)關(guān)系： 不同不同SIMDSIMD計(jì)算機(jī)計(jì)算機(jī)( (互

8、連網(wǎng)絡(luò)可能不同互連網(wǎng)絡(luò)可能不同) )支持的并行算法不支持的并行算法不同及算法實(shí)現(xiàn)效率同及算法實(shí)現(xiàn)效率不同不同3 3、SIMDSIMD互連網(wǎng)絡(luò)互連網(wǎng)絡(luò) * *常用拓?fù)浣Y(jié)構(gòu)：常用拓?fù)浣Y(jié)構(gòu)：網(wǎng)格、環(huán)狀、超立方體網(wǎng)格、環(huán)狀、超立方體等等 * *控制方式：控制方式：集中式控制集中式控制( (外部、控制信號外部、控制信號) ) * *特征：特征：拓?fù)浣Y(jié)構(gòu)不同，實(shí)現(xiàn)的功能與性能不同，對并行算拓?fù)浣Y(jié)構(gòu)不同，實(shí)現(xiàn)的功能與性能不同，對并行算法的支持程度法的支持程度不同不同 并行算法與并行算法與SIMDSIMD互連網(wǎng)絡(luò)結(jié)構(gòu)有很大互連網(wǎng)絡(luò)結(jié)構(gòu)有很大關(guān)系關(guān)系回9頁8三、共享存儲多處理機(jī)三、共享存儲多處理機(jī) * *結(jié)構(gòu)特

9、點(diǎn)：結(jié)構(gòu)特點(diǎn)： 屬屬緊耦合緊耦合( (通過通過MEM BUSMEM BUS互連互連)MIMD)MIMD系統(tǒng)；系統(tǒng)； 所有所有存儲器構(gòu)成存儲器構(gòu)成單一單一地址空間地址空間 * *訪存特點(diǎn)：訪存特點(diǎn)： 處理機(jī)處理機(jī)可直接訪問所有存儲器，且訪問時(shí)間均相同；可直接訪問所有存儲器，且訪問時(shí)間均相同； 各各節(jié)點(diǎn)間通過節(jié)點(diǎn)間通過共享變量方式共享變量方式實(shí)現(xiàn)實(shí)現(xiàn)通信通信PMPM互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)P P1 1/C/C1 1注：注：P-P-處理機(jī)處理機(jī)( (帶帶CU)CU) PE PE處理單元處理單元( (不帶不帶CU)CU) C- C-高速緩存高速緩存 SM-SM-共享存儲器共享存儲器 D-I/OD-I/O設(shè)備設(shè)

10、備D D1 1P P2 2/C/C2 2P Pn n/C/Cn nSMSM1 1SMSM2 2SMSMm mPIOPIO互互連網(wǎng)絡(luò)連網(wǎng)絡(luò)D Dd d回11頁9 * *分類：分類： 根據(jù)根據(jù)P P的類型，可分為的類型，可分為同構(gòu)同構(gòu)/ /異構(gòu)型異構(gòu)型； 根據(jù)根據(jù)P P與與D D的連接特性，又可分為的連接特性，又可分為對稱對稱/ /不對稱不對稱型型 一般一般設(shè)計(jì)設(shè)計(jì)同構(gòu)對稱型、異構(gòu)不對稱同構(gòu)對稱型、異構(gòu)不對稱型型 * *節(jié)點(diǎn)互連：節(jié)點(diǎn)互連： 要求要求能夠?qū)崿F(xiàn)能夠?qū)崿F(xiàn)任意節(jié)點(diǎn)間任意節(jié)點(diǎn)間互連，但互連，但不要求不要求同時(shí)同時(shí) 控制控制方式方式分布式控制分布式控制( (內(nèi)部、消息目標(biāo)地址內(nèi)部、消息目標(biāo)地

11、址) )轉(zhuǎn)7頁10四、分布存儲多計(jì)算機(jī)四、分布存儲多計(jì)算機(jī) * *節(jié)點(diǎn)：節(jié)點(diǎn)：由處理器、存儲器和由處理器、存儲器和I/OI/O設(shè)備組成的設(shè)備組成的計(jì)算機(jī)計(jì)算機(jī) * *結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)： 可可分為緊耦合和松耦合分為緊耦合和松耦合( (通過通過I/O BUSI/O BUS互連互連)MIMD)MIMD系統(tǒng)；系統(tǒng)； 所有所有存儲器構(gòu)成存儲器構(gòu)成多個(gè)多個(gè)地址空間地址空間 * *訪存特點(diǎn)：訪存特點(diǎn)：處理機(jī)處理機(jī)只能直接訪問本地局部存儲器只能直接訪問本地局部存儲器； 各各節(jié)點(diǎn)間通過節(jié)點(diǎn)間通過消息傳遞方式消息傳遞方式實(shí)現(xiàn)實(shí)現(xiàn)通信通信 * *節(jié)點(diǎn)互連：節(jié)點(diǎn)互連：要求能實(shí)現(xiàn)要求能實(shí)現(xiàn)任意節(jié)點(diǎn)間任意節(jié)點(diǎn)間互連，但

12、互連，但不要求不要求同時(shí)同時(shí)回下頁互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)注：注：LM-LM-局部存儲器；局部存儲器；NIC-NIC-網(wǎng)絡(luò)接口電路網(wǎng)絡(luò)接口電路LMLM1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1節(jié)點(diǎn)節(jié)點(diǎn)n n互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)節(jié)點(diǎn)節(jié)點(diǎn)n nLMLM1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1BridgeBridge1 1IOBIOB11五、分布共享存儲多處理機(jī)五、分布共享存儲多處理機(jī) * *結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)： 根據(jù)根據(jù)互連方式，分為緊耦合和松耦合互連方式，分為緊耦合和松耦合MIMDMIMD系統(tǒng)；系統(tǒng)； 所有所有存儲器構(gòu)成存儲器構(gòu)成單一地址空間

13、單一地址空間( (硬件或軟件實(shí)現(xiàn)硬件或軟件實(shí)現(xiàn)) ) * *訪存特點(diǎn)：訪存特點(diǎn)： 處理機(jī)處理機(jī)可直接訪問所有存儲器，但訪問時(shí)間不相同；可直接訪問所有存儲器，但訪問時(shí)間不相同； 各各節(jié)點(diǎn)間通過節(jié)點(diǎn)間通過共享變量方式共享變量方式實(shí)現(xiàn)實(shí)現(xiàn)通信通信轉(zhuǎn)上頁轉(zhuǎn)8頁互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)注：注：M-M-硬件或軟件全局編址的存儲器硬件或軟件全局編址的存儲器M M1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1節(jié)點(diǎn)節(jié)點(diǎn)n n互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)節(jié)點(diǎn)節(jié)點(diǎn)n nM M1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1BridgeBridge1 1IOBIOB12 * *節(jié)點(diǎn)互

14、連：節(jié)點(diǎn)互連： 要求要求能夠?qū)崿F(xiàn)能夠?qū)崿F(xiàn)任意節(jié)點(diǎn)間任意節(jié)點(diǎn)間互連，但互連，但不要求不要求同時(shí)同時(shí) * *MIMDMIMD的可擴(kuò)展性比較：的可擴(kuò)展性比較： 共享共享存儲多處理機(jī)存儲多處理機(jī)不易擴(kuò)展不易擴(kuò)展( (互連網(wǎng)絡(luò)成為瓶頸互連網(wǎng)絡(luò)成為瓶頸) )； 分布分布存儲多計(jì)算機(jī)存儲多計(jì)算機(jī)易擴(kuò)展易擴(kuò)展( (訪問本地訪問本地MEMMEM概率高概率高) )； 分布分布共享存儲多處理機(jī)共享存儲多處理機(jī)易擴(kuò)展易擴(kuò)展( (訪問本地訪問本地MEMMEM概率高概率高) )13第二節(jié)第二節(jié) 并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)體系結(jié)構(gòu) 并行并行體系結(jié)構(gòu)研究內(nèi)容體系結(jié)構(gòu)研究內(nèi)容： 結(jié)構(gòu)模型結(jié)構(gòu)模型、訪存模型、一致性模型、訪存模

15、型、一致性模型、通信機(jī)構(gòu)、同步機(jī)通信機(jī)構(gòu)、同步機(jī)構(gòu)、互連網(wǎng)絡(luò)構(gòu)、互連網(wǎng)絡(luò)一、并行計(jì)算機(jī)結(jié)構(gòu)模型一、并行計(jì)算機(jī)結(jié)構(gòu)模型1 1、并行計(jì)算機(jī)結(jié)構(gòu)、并行計(jì)算機(jī)結(jié)構(gòu) * *種類：種類：單指令多數(shù)據(jù)流機(jī)單指令多數(shù)據(jù)流機(jī)(SIMD)(SIMD)， 并并行向量處理機(jī)行向量處理機(jī)(PVP)(PVP)，對稱多處理機(jī)，對稱多處理機(jī)(SMP)(SMP)， 大規(guī)模并行處理大規(guī)模并行處理機(jī)機(jī)(MPP)(MPP)，工作站機(jī)群，工作站機(jī)群(COW)(COW)， 分布共享存儲器多處理機(jī)分布共享存儲器多處理機(jī)(DSM)(DSM) * *同構(gòu)性：同構(gòu)性：SIMDSIMD單指令多數(shù)據(jù)流單指令多數(shù)據(jù)流機(jī)，數(shù)據(jù)并行；機(jī)，數(shù)據(jù)并行； MI

16、MDMIMDPVPPVP、SMPSMP、MPPMPP、COWCOW、DSMDSM，功能，功能并行并行回下頁14 * *結(jié)構(gòu)比較：結(jié)構(gòu)比較：轉(zhuǎn)上頁回下頁縱橫交叉開關(guān)縱橫交叉開關(guān)VPVP并行向量處理機(jī)并行向量處理機(jī)PVPPVPVPVPVPVPSMSMSMSMSMSM總線或縱橫交叉開關(guān)總線或縱橫交叉開關(guān)P/CP/C對稱多處理機(jī)對稱多處理機(jī)SMPSMPP/CP/CP/CP/CSMSMSMSMSMSM分布共享存儲器多處理機(jī)分布共享存儲器多處理機(jī)DSMDSM定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)MBMBP/CP/CLMLMNICNICDIRDIRMBMBP/CP/CLMLMNICNICDIRDIR大規(guī)模并行處理機(jī)大規(guī)模并行處理

17、機(jī)MPPMPPMBMBP/CP/CLMLMNICNIC定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)MBMBP/CP/CLMLMNICNIC工作站機(jī)群工作站機(jī)群COWCOW商品化網(wǎng)絡(luò)商品化網(wǎng)絡(luò)( (以太網(wǎng)、以太網(wǎng)、ATMATM等等) )MBMBP/CP/CLMLMNICNICBridgeBridgeLDLDIOBIOBMBMBP/CP/CLMLMNICNICBridgeBridgeLDLDIOBIOB回20頁152 2、并行計(jì)算機(jī)結(jié)構(gòu)模型比較、并行計(jì)算機(jī)結(jié)構(gòu)模型比較轉(zhuǎn)上頁屬性屬性SIMDSIMDPVPPVPSMPSMPDSMDSMMPPMPPCOWCOW同構(gòu)性同構(gòu)性SIMDSIMDMIMDMIMD同步性同步性指令級指令級同

18、步同步異步或松同步異步或松同步地址空間地址空間單地址單地址單地址單地址單地址單地址多地址多地址訪存模型訪存模型UMAUMAUMAUMANUMANUMANORMANORMA通信機(jī)制通信機(jī)制數(shù)據(jù)并行數(shù)據(jù)并行共享變量共享變量共享變量共享變量消息傳遞消息傳遞互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)定制定制交叉開關(guān)交叉開關(guān)總線或總線或交叉開關(guān)交叉開關(guān)定制定制定制定制商用商用其他不同其他不同P P類型類型、有、有/ /無無CacheCache耦合耦合程度、程度、OSOS駐留駐留 * *可擴(kuò)展性分析：可擴(kuò)展性分析： PVPPVP、SMPSMP相對較差，其他相對較差，其他較好較好 影響因素影響因素ININ可擴(kuò)展性、可擴(kuò)展性、訪問帶寬

19、與延遲訪問帶寬與延遲、組裝技術(shù)等、組裝技術(shù)等16二、并行計(jì)算機(jī)訪存模型二、并行計(jì)算機(jī)訪存模型1 1、UMA(Uniform Memory Access)UMA(Uniform Memory Access)模型模型 * *訪問特征：訪問特征：每個(gè)每個(gè)P P可訪問可訪問所有所有MEMMEM，且，且訪問訪問時(shí)間時(shí)間相同相同 所有所有MEMMEM構(gòu)成構(gòu)成單地址空間單地址空間 * *應(yīng)用：應(yīng)用：SIMDSIMD、PVPPVP、共享、共享存儲存儲多處理機(jī)多處理機(jī)(SMP)(SMP)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)P P1 1/C/C1 1注：注：P-P-處理機(jī)處理機(jī) C-C-高速緩存高速緩存 SM-SM-共享存儲器共享存

20、儲器P P2 2/C/C2 2P Pn n/C/Cn nSMSM1 1SMSM2 2SMSMm m回下頁 * *CacheCache一致性一致性特征：特征：支持支持 很很容易容易實(shí)現(xiàn)實(shí)現(xiàn)172 2、NUMA(Non-Uniform Memory Access)NUMA(Non-Uniform Memory Access)模型模型 * *訪問特征：訪問特征：各各P P可訪問可訪問所有所有MEMMEM，但訪問時(shí)間不但訪問時(shí)間不相同相同 所有所有MEMMEM構(gòu)成構(gòu)成單地址空間單地址空間 * *基于基于CacheCache一致性一致性的分類的分類：CC-NUMACC-NUMA(Cache (Cache

21、 Coherent NUMA)Coherent NUMA)； NCC-NUMANCC-NUMA(Non-Cache (Non-Cache Coherent NUMACoherent NUMA) ) * *NUMANUMA的應(yīng)用：的應(yīng)用：分布共享存儲多處理機(jī)分布共享存儲多處理機(jī)(DSM(DSM) )注：注：PP處理機(jī)；處理機(jī)；CCCacheCache；MM共享存儲器共享存儲器P P1 1/C/C1 1互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)M M1 1P P2 2/C/C2 2M M2 2P Pn n/C/Cn nM Mn n全局互連網(wǎng)絡(luò)全局互連網(wǎng)絡(luò)GSMGSM GSMGSMCINCINP P群群1 1P PCSMCS

22、MCSMCSMCINCINP P群群n nP PCSMCSMCSMCSMGSMGSM轉(zhuǎn)上頁回下頁回19頁 * *CacheCache一致性一致性特征：特征：支持或不支持或不支持支持183 3、COMA(Cache-Only Memory Access)COMA(Cache-Only Memory Access)模型模型 是是NUMANUMA模型模型的一種特例的一種特例，用各，用各節(jié)點(diǎn)節(jié)點(diǎn)CacheCache構(gòu)成構(gòu)成全局地址全局地址空間空間 * *訪問特征：訪問特征：各各P P可訪問可訪問所有所有CacheCache，但訪問時(shí)間不但訪問時(shí)間不相同相同 所有所有Cache(Cache(非主存非主存

23、) )構(gòu)成構(gòu)成單地址空間單地址空間 * *應(yīng)用：應(yīng)用：共享分布存儲多處理機(jī)共享分布存儲多處理機(jī)(DSM(DSM) )互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)注：注： P-P-處理機(jī)處理機(jī) C-C-高速緩存高速緩存 DIR-DIR-目錄目錄P PC CDIRDIRP PC CDIRDIRP PC CDIRDIR轉(zhuǎn)上頁 * *CacheCache一致性一致性特征：特征：支持支持194 4、NORMA(No-Remote Memory Access)NORMA(No-Remote Memory Access)模型模型 * *訪問特征：訪問特征：各各P P只能直接訪問只能直接訪問本地本地MEMMEM； 所有存儲器構(gòu)成多地址空

24、間所有存儲器構(gòu)成多地址空間 各各P P不能不能直接訪問直接訪問遠(yuǎn)程遠(yuǎn)程MEMMEM 需要通過消息傳遞實(shí)現(xiàn)間接訪問需要通過消息傳遞實(shí)現(xiàn)間接訪問 * *應(yīng)用：應(yīng)用：大規(guī)模并行處理機(jī)大規(guī)模并行處理機(jī)(MPP(MPP) )、工作站、工作站機(jī)群機(jī)群(COW(COW) )互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)( (消息傳遞消息傳遞) ) 注：注：LMLM局部存儲器局部存儲器LMLM1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1節(jié)點(diǎn)節(jié)點(diǎn)n n互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)( (消息傳遞消息傳遞) )節(jié)點(diǎn)節(jié)點(diǎn)n nLMLM1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1BridgeBridg

25、e1 1IOBIOB轉(zhuǎn)17頁 * *CacheCache一致性一致性特征：特征：不不支持支持205 5、并行計(jì)算機(jī)結(jié)構(gòu)模型與訪存模型、并行計(jì)算機(jī)結(jié)構(gòu)模型與訪存模型 訪存模型訪存模型 結(jié)構(gòu)模型結(jié)構(gòu)模型MIMDMIMD多處理機(jī)多處理機(jī)( (單地址空間單地址空間) )多計(jì)算機(jī)多計(jì)算機(jī)( (多地址空間多地址空間) )分布式存儲器分布式存儲器(NUMA)(NUMA)集中式存儲器集中式存儲器(UMA)(UMA)COMACOMACC-NUMACC-NUMANCC-NUMANCC-NUMA松耦合多計(jì)算機(jī)松耦合多計(jì)算機(jī)(NORMA)(NORMA)緊耦合多計(jì)算機(jī)緊耦合多計(jì)算機(jī)(NORMA)(NORMA)PVPPV

26、PSMPSMPDSMDSMCOWCOWMPPMPPSC-NUMASC-NUMASC-NUMASC-NUMA：software-coherent NUMAsoftware-coherent NUMA * *可擴(kuò)展性分析：可擴(kuò)展性分析： UMAUMA可擴(kuò)展性較差，其他可擴(kuò)展性較差，其他較好較好 影響因素影響因素互連網(wǎng)絡(luò)、組裝、訪問帶寬與延時(shí)互連網(wǎng)絡(luò)、組裝、訪問帶寬與延時(shí)等等轉(zhuǎn)14頁21三、并行計(jì)算機(jī)一致性模型三、并行計(jì)算機(jī)一致性模型1 1、存儲器層次結(jié)構(gòu)、存儲器層次結(jié)構(gòu) * *設(shè)計(jì)的相關(guān)參數(shù)：設(shè)計(jì)的相關(guān)參數(shù)： 存儲器容量存儲器容量、存儲粒度、存儲粒度( (交換粒度交換粒度) )、一致性粒度、關(guān)聯(lián)、

27、一致性粒度、關(guān)聯(lián)度、層次管理方法度、層次管理方法等等主存儲器主存儲器磁盤存儲器磁盤存儲器磁帶機(jī)磁帶機(jī)CacheCacheCPUCPU內(nèi)內(nèi)REGREG每位成本增加每位成本增加容量和存取時(shí)間增加容量和存取時(shí)間增加層層0 0層層1 1層層2 2層層3 3層層4 4容量容量按字交換，全相聯(lián)按字交換，全相聯(lián)按塊按塊( (多字多字) )交換，組相聯(lián)交換，組相聯(lián)按頁按頁( (多塊多塊) )交換，全相聯(lián)交換，全相聯(lián)按段按段( (多頁多頁) )交換，全相聯(lián)交換，全相聯(lián)222 2、一致性問題、一致性問題 包括包括CacheCache一致性一致性、存儲一致性兩個(gè)、存儲一致性兩個(gè)方面方面( (1)Cache1)Cac

28、he一致性一致性 指各指各P P的的CacheCache中數(shù)據(jù)副本中數(shù)據(jù)副本與與SMSM中中數(shù)據(jù)數(shù)據(jù)間間的的一致性一致性 * *CacheCache一致性策略：一致性策略： 禁止禁止法法-共享數(shù)據(jù)共享數(shù)據(jù)( (多多P P訪問訪問) )禁止進(jìn)入禁止進(jìn)入CacheCache； 刷新刷新法法用一致性協(xié)議用一致性協(xié)議提前刷新提前刷新CacheCache中數(shù)據(jù)中數(shù)據(jù)副本副本u:7u:7 u:5 u:5主存主存 Cache Cache u:5u:5P P1 1Cache Cache P P2 2Cache Cache P P3 3u:u:? ?u:u:? ?何時(shí)何時(shí)? ?u:5u:5P P1 1 P P2

29、 2 P P3 3 t回下頁 * *一致性目標(biāo)：一致性目標(biāo)：P P對對SMSM某單元某單元ReadRead的結(jié)果是最后的結(jié)果是最后WriteWrite所寫值所寫值 * *不一致原因：不一致原因：共享數(shù)據(jù)異步寫、繞過共享數(shù)據(jù)異步寫、繞過CacheCache的的I/OI/O操作操作23(2)(2)存儲一致性存儲一致性 指指各各P P中中程序次序程序次序與與執(zhí)行執(zhí)行次序次序之間的之間的一致性一致性 指指源程序的語義順序（此處指源程序的語義順序（此處指訪訪存操作存操作的語義次序的語義次序） 對不同存儲單元對不同存儲單元a. A=1;a. A=1;b. Flag=1;b. Flag=1;A A、flag

30、flag為共享變量為共享變量( (初值均為初值均為0)0)P1P1SMSM假設(shè)：假設(shè)：ININ的入的入出延遲相同；出延遲相同； SMSM按序完成按序完成請求請求各各P P按程序次序按程序次序執(zhí)行執(zhí)行： ( (程序語義程序語義) ) print Aprint A時(shí)輸出只可能為時(shí)輸出只可能為1 1；各各P P不按程序次序不按程序次序執(zhí)行：執(zhí)行： print Aprint A時(shí)輸出可能為時(shí)輸出可能為0 0或或1 1問題問題如何保證輸出只為如何保證輸出只為1 1？c. while (flag=0);c. while (flag=0);d. print A;d. print A;P2P2互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)

31、ININ轉(zhuǎn)上頁回下頁 * *一致性目標(biāo)：一致性目標(biāo)：P P中執(zhí)行次序與程序中執(zhí)行次序與程序次序的結(jié)果次序的結(jié)果一致一致 * *不一致原因：不一致原因：優(yōu)化編譯器或優(yōu)化編譯器或P P，導(dǎo)致程序，導(dǎo)致程序執(zhí)行執(zhí)行次序改變次序改變 如如異步異步流水流水24 * *存儲一致性模型：存儲一致性模型： -對執(zhí)行對執(zhí)行次序次序( (編譯及編譯及P)P)的限制的限制 順序一致性順序一致性執(zhí)行執(zhí)行次序次序程序次序、操作原子化程序次序、操作原子化 弱一致性弱一致性同步操作、訪存操作同步操作、訪存操作集滿足集滿足順序順序一致性一致性 處理器一致性處理器一致性P P內(nèi)內(nèi)W W遵循程序序、遵循程序序、WRWR的的R R

32、可可提前提前 釋放一致性釋放一致性基于獲得及釋放基于獲得及釋放同步操作的弱同步操作的弱一致性一致性轉(zhuǎn)上頁回下頁回26頁P(yáng) P0 0：P P1 1：R R4 4W W4 4R R4 4W W1 1W W2 2R R1 1R R2 2R R1 1W W3 3W W4 4共享共享MEMMEM按序完成按序完成P P0 0：P P1 1：R R2 2W W4 4R R1 1W W1 1W W2 2R R2 2R R3 3R R3 3W W3 3R R1 1W W2 2內(nèi)部可內(nèi)部可亂序亂序P P0 0：P P1 1：R R2 2W W4 4R R1 1W W1 1W W2 2S S2 2S S3 3S S

33、4 4W W3 3S S1 1W W2 2R R2 2253 3、單處理機(jī)的一致性模型、單處理機(jī)的一致性模型 * *CacheCache一致性策略：一致性策略： 僅僅CPUCPU控制數(shù)據(jù)控制數(shù)據(jù)寫策略可實(shí)現(xiàn)寫策略可實(shí)現(xiàn)(單單P P無共享數(shù)據(jù)無共享數(shù)據(jù)) ) DMADMA可控制數(shù)據(jù)可控制數(shù)據(jù)禁止法，所控?cái)?shù)據(jù)禁止法，所控?cái)?shù)據(jù)禁止進(jìn)入禁止進(jìn)入CacheCache * *存儲一致性模型：存儲一致性模型： 可可采用順序一致性、處理器一致性等采用順序一致性、處理器一致性等模型模型回下頁轉(zhuǎn)上頁CPUCPU內(nèi)內(nèi)REGREGL2 CacheL2 Cache主存儲器主存儲器磁盤存儲器磁盤存儲器MemBusMemB

34、usIOBusIOBus內(nèi)部內(nèi)部BusBusI/OI/O橋橋L1 CacheL1 CacheCacheCache一致性一致性CPUCPU控制控制相同單元相同單元存儲一致性存儲一致性DMADMA控制控制CPUCPU控制控制不同單元不同單元264 4、多處理機(jī)的一致性模型、多處理機(jī)的一致性模型 * *CacheCache一致性策略：一致性策略： 不不支持時(shí)支持時(shí)應(yīng)用程序應(yīng)用程序負(fù)責(zé)負(fù)責(zé)共享數(shù)據(jù)的共享數(shù)據(jù)的一致性一致性 支持時(shí)支持時(shí)刷新法刷新法，硬件硬件/OS/OS采用采用一致性協(xié)議一致性協(xié)議，使各使各P P的的ReadRead結(jié)果均為最新數(shù)據(jù)結(jié)果均為最新數(shù)據(jù) * *存儲一致性模型：存儲一致性模型：

35、 可采取可采取多種模型多種模型，編程語言編程語言( (編譯器編譯器) )、P P、程序須、程序須協(xié)調(diào)協(xié)調(diào) * *一致性模型研究內(nèi)容一致性模型研究內(nèi)容： 一致性一致性的定義及實(shí)現(xiàn)的定義及實(shí)現(xiàn)機(jī)理機(jī)理轉(zhuǎn)上頁轉(zhuǎn)24頁回下頁SM SM Cache Cache P P1 1NIC NIC 互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)IN IN MBMBMBMBSM SM Cache Cache P P2 2NIC NIC CacheCache一致性一致性存儲一致性存儲一致性相同單元相同單元不同單元不同單元275 5、CacheCache一致性協(xié)議一致性協(xié)議(1)(1)一致性協(xié)議一致性協(xié)議 * *原理：原理：各各CacheCache

36、中的塊均設(shè)有狀態(tài)位，某中的塊均設(shè)有狀態(tài)位，某CacheCache中塊的數(shù)據(jù)中塊的數(shù)據(jù)被改變時(shí)，其它被改變時(shí)，其它CacheCache相應(yīng)改變相應(yīng)改變該塊的該塊的狀態(tài)或狀態(tài)或數(shù)據(jù)數(shù)據(jù)； * *種類：種類：有有基于作廢基于作廢、基于更新基于更新兩種一致性兩種一致性協(xié)議協(xié)議(2)(2)一致性協(xié)議的實(shí)現(xiàn)一致性協(xié)議的實(shí)現(xiàn) * *方法方法：某某CacheCache產(chǎn)生產(chǎn)生事務(wù)事務(wù)( (通知改變通知改變) )，其余，其余CacheCache響應(yīng)響應(yīng)事務(wù)事務(wù) * *途徑途徑：互連結(jié)構(gòu)不同，獲得塊改變信息的有效途徑不同，互連結(jié)構(gòu)不同，獲得塊改變信息的有效途徑不同， 共有共有總線總線監(jiān)聽法監(jiān)聽法或或目錄法目錄法兩

37、種兩種途徑途徑(3)(3)一致性協(xié)議的性能參數(shù)一致性協(xié)議的性能參數(shù) * *性能參數(shù)：性能參數(shù)：主要主要有總線流量、撲空有總線流量、撲空率率、更新速率、更新速率； * *影響因素：影響因素：CacheCache參數(shù)、一致性粒度等參數(shù)、一致性粒度等轉(zhuǎn)上頁28四、并行計(jì)算機(jī)四、并行計(jì)算機(jī)通信機(jī)構(gòu)通信機(jī)構(gòu)1 1、通信操作、通信操作 * *通信過程通信過程： P P通知通信開始通知通信開始 拷貝到緩沖區(qū)拷貝到緩沖區(qū)打包打包 NICNIC啟動包傳輸啟動包傳輸網(wǎng)絡(luò)網(wǎng)絡(luò)傳輸傳輸 NICNIC接收數(shù)據(jù)包接收數(shù)據(jù)包通知信息到達(dá)通知信息到達(dá)拆包拆包( (含保護(hù)檢查含保護(hù)檢查) ) 通知通知通信請求到達(dá)通信請求到達(dá)處

38、理通信操作處理通信操作發(fā)送通信結(jié)果發(fā)送通信結(jié)果等等 * *實(shí)現(xiàn)分析：實(shí)現(xiàn)分析：整個(gè)過程整個(gè)過程由由P P、OSOS、NICNIC分工分工協(xié)作協(xié)作完成完成； 部分部分階段階段可可選擇選擇由硬件由硬件/ /軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)M M1 1NICNIC1 1P P1 1 /C/C1 1MBMB節(jié)點(diǎn)節(jié)點(diǎn)1 1BridgeBridge1 1IOBIOBM Mn nNICNICn nP Pn n /C/Cn nMBMB節(jié)點(diǎn)節(jié)點(diǎn)n nBridgeBridgen nIOBIOB回下頁29 * *性能指標(biāo)：性能指標(biāo)：時(shí)延、帶寬、代價(jià)；時(shí)延、帶寬、代價(jià)； 通信時(shí)間通信時(shí)間(n)=(n)=開銷開銷數(shù)據(jù)時(shí)

39、延數(shù)據(jù)時(shí)延網(wǎng)絡(luò)延遲網(wǎng)絡(luò)延遲占用度占用度 =t=t0 0n/n/B Bt tl lt tc c 其中：其中： t t0 0- - -為為P P通知通信開始通知通信開始NICNIC啟動傳輸?shù)难舆t；啟動傳輸?shù)难舆t； t tc c為數(shù)據(jù)包占用網(wǎng)絡(luò)資源導(dǎo)致沖突而等待的延遲；為數(shù)據(jù)包占用網(wǎng)絡(luò)資源導(dǎo)致沖突而等待的延遲； t tl l為數(shù)據(jù)包穿過網(wǎng)絡(luò)為數(shù)據(jù)包穿過網(wǎng)絡(luò)( (無沖突無沖突) )的的延遲延遲 * *影響性能的因素：影響性能的因素： 通信通信硬件硬件指通信操作實(shí)現(xiàn)過程中指通信操作實(shí)現(xiàn)過程中NICNIC等功能的延遲；等功能的延遲； 通信軟件通信軟件指多次接口抽象、緩沖區(qū)拷貝等的開銷；指多次接口抽象、緩沖

40、區(qū)拷貝等的開銷； 通信通信服務(wù)服務(wù)指服務(wù)質(zhì)量指服務(wù)質(zhì)量( (可靠傳輸可靠傳輸、流控、失效處理、流控、失效處理、按序傳輸、按序傳輸) )等的等的開銷開銷( (分?jǐn)傇诜謹(jǐn)傇贜ICNIC及通信軟件中及通信軟件中) )轉(zhuǎn)上頁回34頁 通信通信代價(jià)代價(jià)= =頻率頻率( (通信通信時(shí)間時(shí)間重疊重疊時(shí)間時(shí)間) ) =f=f(t(t0 0n/n/B Bt tc ct tl lt toverlapoverlap) ) 注：通信重疊有通信注：通信重疊有通信- -計(jì)算、通信計(jì)算、通信- -通信重疊兩種通信重疊兩種302 2、通信操作與編程模型、通信操作與編程模型 * *( (并行并行) )編程模型：編程模型：數(shù)據(jù)并

41、行、共享變量、消息數(shù)據(jù)并行、共享變量、消息傳輸傳輸3 3種種 * *通信操作通信操作- -編程模型：編程模型：不同編程模型不同編程模型的通信操作差距較大的通信操作差距較大(1(1) )通信通信操作的要求操作的要求 * *通信通信表示表示要求要求：隱隱式、顯式、顯式式方式方式2 2種，種，穿插穿插在程序中在程序中 * *通信定通信定序要求：序要求： 普通及通信操作普通及通信操作各各進(jìn)程按進(jìn)程按程序程序次序次序( (隱式隱式) )定定序序 特定通信操作特定通信操作全局按全局按同步操作同步操作( (顯式顯式) )定定序序 * *通信方式通信方式要求要求：有有同步、異步互鎖、異步非互同步、異步互鎖、異

42、步非互鎖鎖3 3種種 * *通信模式通信模式要求：要求：有一對一有一對一( (如點(diǎn)點(diǎn)如點(diǎn)點(diǎn)) )、一對多、一對多( (如廣播如廣播) )、多對一、多對一( (如聚集如聚集) )、多對多、多對多( (如置換如置換) )4 4種種P P0 0：P P1 1：R RW W1 1R R1 1W WW W2 2R R2 2W W2 2R R2 2R RW W3 3=0=0=1=1R R3 331(2)(2)數(shù)據(jù)并行數(shù)據(jù)并行模型的通信操作模型的通信操作 * *特點(diǎn)：特點(diǎn)：單線程單線程、松散同步、松散同步( (語句級語句級) )并行、單地址空間、數(shù)并行、單地址空間、數(shù)據(jù)并行、據(jù)并行、隱隱式分配式分配( (屏

43、蔽方式屏蔽方式) ) * *通信操作：通信操作：PUPU間通信間通信ININ、OUTOUT，顯式，顯式完成；完成； PUPU間同步間同步無無( (松散同步自動實(shí)現(xiàn)松散同步自動實(shí)現(xiàn)) )(3)(3)共享變量共享變量模型的通信操作模型的通信操作 * *特點(diǎn)：特點(diǎn)：多線程多線程、異步并行、異步并行、單地址空間單地址空間、操作并行、操作并行、顯顯式分配式分配 * *通信操作：通信操作：P P間通信間通信R R、W W，隱式完成；，隱式完成； P P間同步間同步進(jìn)程進(jìn)程創(chuàng)建創(chuàng)建( (操作操作) )、撤消、撤消/ /同步同步( (操作操作) )(4)(4)消息傳遞消息傳遞模型的通信操作模型的通信操作 *

44、*特點(diǎn)：特點(diǎn)：多線程多線程、異步并行、異步并行、多地址空間多地址空間、操作并行、操作并行、顯顯式分配式分配 * *通信通信操作：操作：P P間通信間通信SendSend、RecvRecv，顯式完成；顯式完成； P P間同步間同步進(jìn)程進(jìn)程創(chuàng)建創(chuàng)建( (操作操作) )、撤消、撤消/ /同步同步( (通信通信) )回33頁323 3、通信機(jī)構(gòu)的組成、通信機(jī)構(gòu)的組成 * *通信機(jī)構(gòu)層次結(jié)構(gòu)通信機(jī)構(gòu)層次結(jié)構(gòu)： * *通信機(jī)構(gòu)研究通信機(jī)構(gòu)研究內(nèi)容：內(nèi)容： 定義定義通信操作、通信原語、硬件原語；通信操作、通信原語、硬件原語； ( (用戶用戶/ /系統(tǒng)層系統(tǒng)層) () (軟件軟件/ /硬件層硬件層) ) 確定

45、確定高效高效地實(shí)現(xiàn)地實(shí)現(xiàn)這些原語的方法這些原語的方法回34頁無通信無通信操作操作注注：通信：通信抽象抽象用戶層實(shí)現(xiàn)編程模型的通信操作用戶層實(shí)現(xiàn)編程模型的通信操作( (或原語或原語) )用戶用戶/ /系統(tǒng)邊界系統(tǒng)邊界軟件軟件/ /硬件邊界硬件邊界操作系統(tǒng)層操作系統(tǒng)層通信硬件層通信硬件層( (如如NIC)NIC)物理通信介質(zhì)層物理通信介質(zhì)層( (如如IN)IN)編譯或庫層編譯或庫層 CADCAD 數(shù)據(jù)庫數(shù)據(jù)庫 科學(xué)科學(xué)建模等建模等 并行應(yīng)用并行應(yīng)用 多道程序多道程序 共享變量共享變量 消息傳遞消息傳遞 數(shù)據(jù)并行數(shù)據(jù)并行 編程模型編程模型通信抽象通信抽象334 4、通信機(jī)構(gòu)的實(shí)現(xiàn)通信機(jī)構(gòu)的實(shí)現(xiàn) *

46、*通信抽象通信抽象( (通信通信操作操作) )： 共享變量共享變量模型模型ReadRead、WriteWrite指令指令，高級同步，高級同步結(jié)構(gòu)結(jié)構(gòu) 消息消息傳遞模型傳遞模型SendSend、RecvRecv函數(shù)函數(shù)，高級同步，高級同步結(jié)構(gòu)結(jié)構(gòu) * *軟件軟件/ /硬件通信邊界硬件通信邊界( (硬件原語硬件原語) )： 共享變量共享變量模型模型ReadRead、WriteWrite操作操作，低級同步原語；，低級同步原語； 消息消息傳遞模型傳遞模型SendSend、RecvRecv操作操作，低級同步，低級同步原語原語共享變量共享變量消息傳遞消息傳遞UMAUMA訪存模型訪存模型地址映射地址映射 N

47、ICNIC實(shí)現(xiàn)虛實(shí)現(xiàn)虛- -實(shí)地址映射實(shí)地址映射傳輸實(shí)現(xiàn)傳輸實(shí)現(xiàn) NICNIC通過通過總線操作總線操作實(shí)現(xiàn)實(shí)現(xiàn)NUMANUMA訪存模型訪存模型地址映射地址映射 NICNIC或或OSOS實(shí)現(xiàn)地址映射實(shí)現(xiàn)地址映射傳輸實(shí)現(xiàn)傳輸實(shí)現(xiàn) NICNIC通過通過網(wǎng)絡(luò)事務(wù)網(wǎng)絡(luò)事務(wù)實(shí)現(xiàn)實(shí)現(xiàn)NORMANORMA訪存模型訪存模型地址映射地址映射OSOS實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)進(jìn)程- -節(jié)點(diǎn)映射節(jié)點(diǎn)映射傳輸實(shí)現(xiàn)傳輸實(shí)現(xiàn)NICNIC通過通過網(wǎng)絡(luò)事務(wù)網(wǎng)絡(luò)事務(wù)實(shí)現(xiàn)實(shí)現(xiàn) * *通信硬件通信硬件/ /通信介質(zhì)邊界：通信介質(zhì)邊界：轉(zhuǎn)31頁OSOS組織并實(shí)現(xiàn)組織并實(shí)現(xiàn)各種通信操作各種通信操作34 * *通信模型的可擴(kuò)展性：通信模型的可擴(kuò)展性：

48、取決于取決于結(jié)構(gòu)模型結(jié)構(gòu)模型及及互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的可的可擴(kuò)展性擴(kuò)展性5 5、通信機(jī)構(gòu)的通信機(jī)構(gòu)的性能性能 * *通信抽象的性能：通信抽象的性能： 性能參數(shù)性能參數(shù)通信操作的通信操作的使用效率使用效率 影響因素影響因素對對應(yīng)用程序應(yīng)用程序的支持程度；的支持程度； 對對編譯器編譯器/ /運(yùn)行庫運(yùn)行庫的支持程度的支持程度 * *通信通信實(shí)現(xiàn)的性能：實(shí)現(xiàn)的性能： 性能參數(shù)性能參數(shù)通信原語通信原語( (含硬件原語含硬件原語) )的的延遲延遲和和開銷開銷 影響因素影響因素實(shí)現(xiàn)過程的實(shí)現(xiàn)過程的軟硬件功能分配軟硬件功能分配； 互連網(wǎng)絡(luò)的互連網(wǎng)絡(luò)的性能性能； 通信通信- -計(jì)算、通信計(jì)算、通信- -通信間的通信

49、間的重疊重疊程度程度轉(zhuǎn)32頁轉(zhuǎn)29頁35五、并行計(jì)算機(jī)五、并行計(jì)算機(jī)同步機(jī)構(gòu)同步機(jī)構(gòu)1 1、同步操作、同步操作 用于實(shí)現(xiàn)用于實(shí)現(xiàn)兩個(gè)或多個(gè)進(jìn)程兩個(gè)或多個(gè)進(jìn)程間的同步間的同步 * *類型：類型：互斥、點(diǎn)點(diǎn)事件、柵障事件互斥、點(diǎn)點(diǎn)事件、柵障事件( (全局事件全局事件) )進(jìn)程進(jìn)程1 1：進(jìn)程進(jìn)程2 2：進(jìn)程進(jìn)程3 3：II1212 請求請求請求請求請求請求獲得獲得釋放釋放等待等待等待等待II1313 等待等待II3333 II2222 獲得獲得II2323 II1111 II2121 II3131 各進(jìn)程競爭同步權(quán)各進(jìn)程競爭同步權(quán)獲得獲得釋放釋放II3232 釋放釋放 * *組成組成：獲得方法、等

50、待算法、釋放獲得方法、等待算法、釋放方法方法回下頁同步同步原子操作原子操作控制同步控制同步數(shù)據(jù)同步數(shù)據(jù)同步互斥互斥路障路障找到找到信號燈和鎖信號燈和鎖產(chǎn)產(chǎn)- -銷銷池和隊(duì)列池和隊(duì)列362 2、同步機(jī)構(gòu)的實(shí)現(xiàn)同步機(jī)構(gòu)的實(shí)現(xiàn) * *同步結(jié)構(gòu)：同步結(jié)構(gòu)： 事件事件( (Signal/WaitSignal/Wait)用于點(diǎn)點(diǎn)事件同步；用于點(diǎn)點(diǎn)事件同步； 路障路障( (BarrierBarrier)用于柵障事件同步；用于柵障事件同步； 鎖鎖( (Lock/UnlockLock/Unlock) )和臨界區(qū)和臨界區(qū)( (E/L CriticalE/L Critical)用于互斥用于互斥 * *硬件原語硬件原

51、語： 具有具有讀讀- -改改- -寫功能寫功能的的原子操作指令原子操作指令 例例Test&SetTest&Set、Compare&SwapCompare&Swap、Fetch&AddFetch&Add等指令等指令 * *同步機(jī)構(gòu)研究同步機(jī)構(gòu)研究內(nèi)容：內(nèi)容： 定義定義編程模型的編程模型的同步結(jié)構(gòu)同步結(jié)構(gòu)、軟件軟件/ /硬件的硬件的硬件原語硬件原語 確定確定高效實(shí)現(xiàn)同步結(jié)構(gòu)的方法高效實(shí)現(xiàn)同步結(jié)構(gòu)的方法轉(zhuǎn)上頁派生派生373 3、同步模型的性能、同步模型的性能 * *接口抽象的性能：接口抽象的性能： 性能參數(shù)性能參數(shù)同步結(jié)構(gòu)的同步結(jié)構(gòu)的使用效率使用效率

52、影響因素影響因素對應(yīng)用程序、編譯器對應(yīng)用程序、編譯器/ /運(yùn)行庫的運(yùn)行庫的支持支持程度程度 * *同步實(shí)現(xiàn)的性能：同步實(shí)現(xiàn)的性能： 性能性能參數(shù)參數(shù)延遲、通信量、公正性、可擴(kuò)放延遲、通信量、公正性、可擴(kuò)放性性 影響因素影響因素同步同步權(quán)的獲得方法、等待算法、釋放權(quán)的獲得方法、等待算法、釋放方法方法 （主要（主要反映為低級同步原語的反映為低級同步原語的性能）性能）38六、并行計(jì)算機(jī)體系結(jié)構(gòu)發(fā)展六、并行計(jì)算機(jī)體系結(jié)構(gòu)發(fā)展1 1、并行體系結(jié)構(gòu)比較、并行體系結(jié)構(gòu)比較 * *結(jié)構(gòu)內(nèi)容比較：結(jié)構(gòu)內(nèi)容比較：并行類型并行類型SIMDSIMDMIMDMIMD結(jié)構(gòu)模型結(jié)構(gòu)模型SIMDSIMD集中式集中式(MBus

53、)(MBus)分布式分布式( (MbusMbus/ /IOBusIOBus) )PVPPVPSMPSMPDSMDSMMPPMPPCOWCOW訪存模型訪存模型UMAUMAUMAUMACOMACOMA、CC-NUMACC-NUMA NCC-NUMANCC-NUMANORMANORMA單地址單地址單地址單地址單地址單地址多地址多地址一致性一致性模型模型CacheCache無無無無支持支持支持支持不支持不支持無無存儲存儲順序順序順序順序 所有類型所有類型所有類型所有類型所有類型所有類型通信及同步通信及同步數(shù)據(jù)并行數(shù)據(jù)并行共享變量共享變量共享變量共享變量消息傳遞消息傳遞互連互連網(wǎng)絡(luò)網(wǎng)絡(luò)控制控制 集中控制

54、集中控制分布控制分布控制類型類型定制定制交叉交叉開關(guān)開關(guān)總線或總線或交叉開關(guān)交叉開關(guān)定制定制定制定制 商用商用回下頁 * *相互影響：相互影響：結(jié)構(gòu)與訪存模型，通信結(jié)構(gòu)與訪存模型，通信/ /同步機(jī)構(gòu)與編程模型，同步機(jī)構(gòu)與編程模型， 一致性模型與程序性能及系統(tǒng)性能一致性模型與程序性能及系統(tǒng)性能392 2、并行體系結(jié)構(gòu)發(fā)展、并行體系結(jié)構(gòu)發(fā)展(1)(1)機(jī)器組織的發(fā)展機(jī)器組織的發(fā)展向通用結(jié)構(gòu)向通用結(jié)構(gòu)發(fā)展發(fā)展 * *殼體系結(jié)構(gòu)殼體系結(jié)構(gòu)成為成為主流：主流：殼殼結(jié)構(gòu)結(jié)構(gòu)有利于有利于P P的代的代可可擴(kuò)展性擴(kuò)展性 * *MPPMPP與與COWCOW的界線越來越含糊：的界線越來越含糊：COWCOW現(xiàn)多為緊

55、耦合、共享現(xiàn)多為緊耦合、共享HDHD互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)NICNIC節(jié)點(diǎn)節(jié)點(diǎn)n n(a)(a)無共享無共享LMLMNICNIC節(jié)點(diǎn)節(jié)點(diǎn)1 1C CLDLDP PShellShellLMLMNICNIC節(jié)點(diǎn)節(jié)點(diǎn)1 1C CP PShellShell互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)(b)(b)共享磁盤共享磁盤NICNIC節(jié)點(diǎn)節(jié)點(diǎn)n nSDSD(c)(c)共享存儲器共享存儲器NICNIC節(jié)點(diǎn)節(jié)點(diǎn)1 1C CP PShellShell互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)NICNIC節(jié)點(diǎn)節(jié)點(diǎn)n nSDSDSMSM可擴(kuò)展并行計(jì)算機(jī)可擴(kuò)展并行計(jì)算機(jī)的常用的常用體系結(jié)構(gòu)體系結(jié)構(gòu)轉(zhuǎn)上頁回下頁 * *DSMDSM是是SMPSMP、MPPMPP的自然的自

56、然結(jié)合：結(jié)合：NUMANUMA利于系統(tǒng)的可擴(kuò)展性利于系統(tǒng)的可擴(kuò)展性40(2)(2)通信機(jī)制的發(fā)展通信機(jī)制的發(fā)展向混合模型發(fā)展向混合模型發(fā)展 * *通信通信的硬件實(shí)現(xiàn)方法趨于統(tǒng)一的硬件實(shí)現(xiàn)方法趨于統(tǒng)一 分布式結(jié)構(gòu)為主流結(jié)構(gòu)，分布式結(jié)構(gòu)為主流結(jié)構(gòu)， NIC NIC通過通過網(wǎng)絡(luò)事務(wù)網(wǎng)絡(luò)事務(wù)實(shí)現(xiàn)遠(yuǎn)程節(jié)點(diǎn)實(shí)現(xiàn)遠(yuǎn)程節(jié)點(diǎn)訪問，訪問， NICNIC或或OSOS轉(zhuǎn)換轉(zhuǎn)換成編程模型所需接口成編程模型所需接口( (R/WR/W操作和消息傳遞操作和消息傳遞) ) * *編程編程模型與機(jī)器組織逐步模型與機(jī)器組織逐步分離：分離： 同同一一機(jī)器機(jī)器可通過運(yùn)行庫或可通過運(yùn)行庫或OSOS實(shí)現(xiàn)實(shí)現(xiàn)不同編程模型不同編程模型 單地址

57、空間機(jī)器的消息傳遞單地址空間機(jī)器的消息傳遞可用可用共享的共享的緩沖區(qū)緩沖區(qū)實(shí)現(xiàn)；實(shí)現(xiàn)； 多地址空間機(jī)器的遠(yuǎn)程多地址空間機(jī)器的遠(yuǎn)程R/WR/W a)APPa)APP可構(gòu)成可構(gòu)成全局地址空間全局地址空間，利用，利用運(yùn)行庫運(yùn)行庫實(shí)現(xiàn)實(shí)現(xiàn)； b)b)進(jìn)程組可進(jìn)程組可有有頁級頁級共享地址空間共享地址空間，利用缺頁異常，利用缺頁異常OSOS遠(yuǎn)程遠(yuǎn)程調(diào)調(diào)頁實(shí)現(xiàn)頁實(shí)現(xiàn)轉(zhuǎn)上頁41(3)(3)互連網(wǎng)絡(luò)的發(fā)展互連網(wǎng)絡(luò)的發(fā)展向可向可擴(kuò)展及商品化擴(kuò)展及商品化發(fā)展發(fā)展 * *技術(shù)革新使技術(shù)革新使ININ可可擴(kuò)展性擴(kuò)展性較強(qiáng)：較強(qiáng)： +IN+IN采用采用蟲孔尋徑蟲孔尋徑傳輸方式，對傳輸方式，對ININ拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)的要求

58、降低的要求降低 使延遲使延遲主要在主要在P P及及NICNIC上上 +NIC+NIC的的DMADMA傳輸傳輸不阻塞不阻塞CPUCPU，對，對ININ拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)的要求的要求降低降低 通信通信- -計(jì)算可重疊計(jì)算可重疊 注：注：T T網(wǎng)絡(luò)網(wǎng)絡(luò)T T路由路由L L消息消息/B/B通道通道，T T路由路由主要由主要由拓?fù)浣Y(jié)構(gòu)決定拓?fù)浣Y(jié)構(gòu)決定 * *商品化商品化網(wǎng)絡(luò)基本可滿足網(wǎng)絡(luò)基本可滿足需求：需求： + +商品化網(wǎng)絡(luò)與專用商品化網(wǎng)絡(luò)與專用網(wǎng)絡(luò)的網(wǎng)絡(luò)的性能性能差距差距減小減小 + +商品化網(wǎng)絡(luò)的商品化網(wǎng)絡(luò)的性能性能/ /價(jià)格價(jià)格較高較高423 3、并行體系結(jié)構(gòu)設(shè)計(jì)的相關(guān)問題、并行體系結(jié)構(gòu)設(shè)計(jì)的相關(guān)

59、問題 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)是軟硬件系統(tǒng)結(jié)構(gòu)設(shè)計(jì)是軟硬件交互設(shè)計(jì)、反復(fù)設(shè)計(jì)與評價(jià)的交互設(shè)計(jì)、反復(fù)設(shè)計(jì)與評價(jià)的過程過程(1)(1)確定系統(tǒng)的結(jié)構(gòu)模型和訪存模型確定系統(tǒng)的結(jié)構(gòu)模型和訪存模型 SIMD/MIMDSIMD/MIMD，UMA/NUMA/NORMAUMA/NUMA/NORMA(2)(2)確定系統(tǒng)的一致性模型確定系統(tǒng)的一致性模型 是是/ /否支持、硬件否支持、硬件/ /軟件支持軟件支持CacheCache一致性，存儲一致性一致性，存儲一致性模型模型(3)(3)確定系統(tǒng)的確定系統(tǒng)的通信機(jī)構(gòu)及同步機(jī)構(gòu)通信機(jī)構(gòu)及同步機(jī)構(gòu) 確定軟件確定軟件/ /硬件邊界的硬件邊界的通信原語、同步通信原語、同步原語原語(4)(

60、4)確定殼結(jié)構(gòu)及其參數(shù)確定殼結(jié)構(gòu)及其參數(shù) MEMMEM及及CacheCache容量、交換粒度、一致性粒度、關(guān)聯(lián)度容量、交換粒度、一致性粒度、關(guān)聯(lián)度等等(5)(5)通信與互連設(shè)計(jì)通信與互連設(shè)計(jì) NICNIC設(shè)計(jì)、互連網(wǎng)絡(luò)設(shè)計(jì)設(shè)計(jì)、互連網(wǎng)絡(luò)設(shè)計(jì)等等43第三節(jié)第三節(jié) 可擴(kuò)展設(shè)計(jì)原理可擴(kuò)展設(shè)計(jì)原理 一、可擴(kuò)展性范圍一、可擴(kuò)展性范圍 * *可擴(kuò)展性：可擴(kuò)展性：包括包括資源可擴(kuò)展性、應(yīng)用可擴(kuò)展性、技術(shù)可資源可擴(kuò)展性、應(yīng)用可擴(kuò)展性、技術(shù)可擴(kuò)展性擴(kuò)展性1 1、資源可擴(kuò)展性、資源可擴(kuò)展性 指增加指增加機(jī)器規(guī)模機(jī)器規(guī)模( (P P數(shù)量數(shù)量) )、存儲部件存儲部件規(guī)模規(guī)模及及軟件軟件規(guī)模規(guī)模等時(shí)，等時(shí)，系統(tǒng)應(yīng)具有系統(tǒng)應(yīng)具有更更高的性能高的性能或或功能功能 *