高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)第3章2

1、15 5、CacheCache一致性協(xié)議一致性協(xié)議(1)(1)一致性協(xié)議一致性協(xié)議 * *原理：原理：各各CacheCache中的塊均設(shè)有狀態(tài)位，某中的塊均設(shè)有狀態(tài)位，某CacheCache中塊的數(shù)據(jù)中塊的數(shù)據(jù)被改變時(shí)，其它被改變時(shí)，其它CacheCache相應(yīng)改變相應(yīng)改變?cè)搲K的該塊的狀態(tài)或數(shù)據(jù)狀態(tài)或數(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)不同

2、，獲得塊改變信息的有效途徑不同，互連結(jié)構(gòu)不同，獲得塊改變信息的有效途徑不同， 共有共有總線總線監(jiān)聽法監(jiān)聽法或或目錄法目錄法兩種兩種途徑途徑(3)(3)一致性協(xié)議的性能參數(shù)一致性協(xié)議的性能參數(shù) * *性能參數(shù)性能參數(shù)：總線流量、撲空總線流量、撲空率率、更新速率等、更新速率等 * *影響因素：影響因素：CacheCache參數(shù)、一致性粒度等參數(shù)、一致性粒度等轉(zhuǎn)上頁2四、并行計(jì)算機(jī)四、并行計(jì)算機(jī)通信機(jī)構(gòu)通信機(jī)構(gòu)1 1、通信操作、通信操作 * *通信過程通信過程： P P通知通信開始通知通信開始 拷貝到緩沖區(qū)拷貝到緩沖區(qū)打包打包 NICNIC啟動(dòng)包傳輸啟動(dòng)包傳輸網(wǎng)絡(luò)網(wǎng)絡(luò)傳輸傳輸 NICNIC接收數(shù)據(jù)包

3、接收數(shù)據(jù)包通知信息到達(dá)通知信息到達(dá)拆包拆包( (含保護(hù)檢查含保護(hù)檢查) ) 通知通知通信請(qǐng)求到達(dá)通信請(qǐng)求到達(dá)處理通信操作處理通信操作發(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回下頁3 *

4、 *性能指標(biāo)：性能指標(biāo)：時(shí)延、帶寬、時(shí)延、帶寬、代價(jià)代價(jià) 通信時(shí)間通信時(shí)間(n)=(n)=開銷開銷數(shù)據(jù)時(shí)延數(shù)據(jù)時(shí)延網(wǎng)絡(luò)延遲網(wǎng)絡(luò)延遲占用度占用度 =t=t0 0n/Bn/Bt tl lt tc c 其中：其中： t t0 0-P-P通知通信開始通知通信開始NICNIC啟動(dòng)傳輸?shù)膯?dòng)傳輸?shù)难舆t延遲 t tc c數(shù)據(jù)包數(shù)據(jù)包占用網(wǎng)絡(luò)資源導(dǎo)致沖突而等待的占用網(wǎng)絡(luò)資源導(dǎo)致沖突而等待的延遲延遲 t tl l數(shù)據(jù)包數(shù)據(jù)包穿過網(wǎng)絡(luò)穿過網(wǎng)絡(luò)( (無沖突無沖突) )的的延遲延遲 * *影響性能的因素：影響性能的因素： 通信通信硬件硬件指指NICNIC等功能的延遲等功能的延遲 通信軟件通信軟件指多次接口抽象、緩沖區(qū)

5、拷貝等的指多次接口抽象、緩沖區(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/Bn/Bt tc ct tl lt toverlapoverlap) ) 注：通信重疊有通信注：通信重疊有通信- -計(jì)算、通信計(jì)算、通信- -通信重疊兩種通信重疊兩種42 2、通信操作與編程模型、通信操作與編程模型 * *( (并行并行) )

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

7、、異步非互同步、異步互鎖、異步非互鎖鎖3 3種種 * *通信模式通信模式要求：要求：有一對(duì)一有一對(duì)一( (如點(diǎn)點(diǎn)如點(diǎn)點(diǎn)) )、一對(duì)多、一對(duì)多( (如廣播如廣播) )、多對(duì)一、多對(duì)一( (如聚集如聚集) )、多對(duì)多、多對(duì)多( (如置換如置換) )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 35(2)(2)數(shù)據(jù)并行數(shù)據(jù)并行模型的通信操作模型的通信操作 * *特點(diǎn)：特點(diǎn)：?jiǎn)尉€程單線程、松散同步、松散同步( (語句級(jí)語句級(jí)) )并行、單地址空間、數(shù)并行、單地址空間、數(shù)據(jù)并行、據(jù)并行

8、、隱隱式分配式分配( (屏蔽方式屏蔽方式) ) * *通信操作：通信操作：PUPU間通信間通信ININ、OUTOUT，顯式完成，顯式完成 PUPU間同步間同步無無( (松散同步自動(dòng)實(shí)現(xiàn)松散同步自動(dòng)實(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)消息傳遞消息傳遞模型的通信操作模

9、型的通信操作 * *特點(diǎn)：特點(diǎn)：多線程多線程、異步并行、異步并行、多地址空間多地址空間、操作并行、操作并行、顯顯式分配式分配 * *通信通信操作：操作：P P間通信間通信SendSend、RecvRecv，顯式顯式完成完成 P P間同步間同步進(jìn)程進(jìn)程創(chuàng)建創(chuàng)建( (操作操作) )、撤消、撤消/ /同步同步( (通信通信) )回33頁63 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)研究?jī)?nèi)容：內(nèi)容： 定義定義通信操作、通信原語、硬件原語通信操作、通信原語、硬件原語 ( (用戶用戶/ /系統(tǒng)層系統(tǒng)層) () (軟件軟件/ /硬件層硬件層)

10、) 確定確定高效高效地實(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ù)并行 編程模型編程模型通信抽象通信抽象74 4、通信機(jī)構(gòu)的實(shí)現(xiàn)通信機(jī)構(gòu)的實(shí)現(xiàn)

11、 * *通信抽象通信抽象( (通信通信操作操作) )： 共享變量共享變量模型模型ReadRead、WriteWrite指令指令，高級(jí)同步，高級(jí)同步結(jié)構(gòu)結(jié)構(gòu) 消息消息傳遞模型傳遞模型SendSend、RecvRecv函數(shù)函數(shù)，高級(jí)同步，高級(jí)同步結(jié)構(gòu)結(jié)構(gòu) * *用戶用戶/ /系統(tǒng)通信系統(tǒng)通信邊界邊界( (通信原語通信原語) )： 共享變量共享變量模型模型ReadRead、WriteWrite操作操作，低級(jí)同步，低級(jí)同步原語原語 消息消息傳遞模型傳遞模型SendSend、RecvRecv操作操作，低級(jí)同步，低級(jí)同步原語原語共享變量共享變量消息傳遞消息傳遞UMAUMA訪存模型訪存模型地址映射地址映射

12、NICNIC實(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) * *軟件軟件/ /硬件通信邊界硬件通信邊界：轉(zhuǎn)31頁OSOS組織并實(shí)現(xiàn)組織并實(shí)現(xiàn)各種通信操作各種通信操作8 * *通信模型的可擴(kuò)展性：通信模型的可擴(kuò)展性： 取決于取決

13、于結(jié)構(gòu)模型結(jié)構(gòu)模型及及互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的可的可擴(kuò)展性擴(kuò)展性5 5、通信機(jī)構(gòu)的通信機(jī)構(gòu)的性能性能 * *通信抽象的性能：通信抽象的性能： 性能參數(shù)性能參數(shù)通信操作的通信操作的使用效率使用效率 影響因素影響因素對(duì)對(duì)應(yīng)用程序應(yīng)用程序的支持程度的支持程度 對(duì)對(duì)編譯器編譯器/ /運(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ì)算、通信- -通信間的通信間的重疊重疊程度程

14、度轉(zhuǎn)32頁轉(zhuǎn)29頁9五、并行計(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 請(qǐng)求請(qǐng)求請(qǐng)求請(qǐng)求請(qǐng)求請(qǐng)求獲得獲得釋放釋放等待等待等待等待II1313 等待等待II3333 II2222 獲得獲得II2323 II1111 II2121 II3131 各進(jìn)程競(jìng)爭(zhēng)同步權(quán)各進(jìn)程競(jìng)爭(zhēng)同步權(quán)獲得獲得釋放釋放II3232 釋放釋放 * *組成組成：獲得方法、等待算法、釋放獲得方法

15、、等待算法、釋放方法方法回下頁同步同步原子操作原子操作控制同步控制同步數(shù)據(jù)同步數(shù)據(jù)同步互斥互斥路障路障找到找到信號(hào)燈和鎖信號(hào)燈和鎖產(chǎn)產(chǎn)- -銷銷池和隊(duì)列池和隊(duì)列102 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)用于互斥用于互斥 * *硬件原語硬件原語： 具有具有讀讀- -改改

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

17、編譯器對(duì)應(yīng)用程序、編譯器/ /運(yùn)行庫的運(yùn)行庫的支持支持程度程度 * *同步實(shí)現(xiàn)的性能：同步實(shí)現(xiàn)的性能： 性能性能參數(shù)參數(shù)延遲、通信量、公正性、可擴(kuò)放延遲、通信量、公正性、可擴(kuò)放性性 影響因素影響因素同步同步權(quán)的獲得方法、等待算法、釋放權(quán)的獲得方法、等待算法、釋放方法方法 （主要（主要反映為低級(jí)同步原語的反映為低級(jí)同步原語的性能）性能）12六、并行計(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)(MBus)分布式分布式(

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

19、類型定制定制交叉交叉開關(guān)開關(guān)總線或總線或交叉開關(guān)交叉開關(guān)定制定制定制定制 商用商用回下頁 * *相互影響：相互影響：結(jié)構(gòu)與訪存模型，通信結(jié)構(gòu)與訪存模型，通信/ /同步機(jī)構(gòu)與編程模型，同步機(jī)構(gòu)與編程模型， 一致性模型與程序性能及系統(tǒng)性能一致性模型與程序性能及系統(tǒng)性能132 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)多為緊耦合、共享現(xiàn)多為緊耦合、共享

20、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)共享存儲(chǔ)器共享存儲(chǔ)器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的自然的自然結(jié)合：結(jié)合：NUMANUM

21、A利于系統(tǒng)的可擴(kuò)展性利于系統(tǒng)的可擴(kuò)展性14(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)不同編程模型不同編程模型 單地址空間機(jī)器的消息傳遞單地址空間

22、機(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)程組可有有頁級(jí)頁級(jí)共享地址空間共享地址空間，利用缺頁異常，利用缺頁異常OSOS遠(yuǎn)程遠(yuǎn)程調(diào)調(diào)頁實(shí)現(xiàn)頁實(shí)現(xiàn)轉(zhuǎn)上頁15(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采用采用蟲孔尋徑蟲孔尋徑傳輸方式，對(duì)傳輸方式，對(duì)ININ拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)的要求降低的要求降低 使延遲主要在使延遲

23、主要在P P及及NICNIC上上 +NIC+NIC的的DMADMA傳輸傳輸不阻塞不阻塞CPUCPU，對(duì)，對(duì)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à)格較高較高163 3、并行體系結(jié)構(gòu)設(shè)計(jì)的相關(guān)問題、并行體系結(jié)構(gòu)設(shè)計(jì)的相關(guān)問題 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)是軟硬件系統(tǒng)結(jié)構(gòu)

24、設(shè)計(jì)是軟硬件交互設(shè)計(jì)、反復(fù)設(shè)計(jì)與評(píng)價(jià)的交互設(shè)計(jì)、反復(fù)設(shè)計(jì)與評(píng)價(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一致性，存儲(chǔ)一致性一致性，存儲(chǔ)一致性模型模型(3)(3)確定系統(tǒng)的確定系統(tǒng)的通信機(jī)構(gòu)及同步機(jī)構(gòu)通信機(jī)構(gòu)及同步機(jī)構(gòu) 確定軟件確定軟件/ /硬件邊界的硬件邊界的通信原語、同步通信原語、同步原語原語(4)(4)確定殼結(jié)構(gòu)及其參數(shù)確定殼結(jié)構(gòu)及

25、其參數(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ì)等等17第三節(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ù)量) )、存儲(chǔ)部件存儲(chǔ)部件規(guī)模規(guī)模及及軟件軟件規(guī)模規(guī)模等時(shí)，等時(shí)，系統(tǒng)系統(tǒng)應(yīng)具有應(yīng)具有更更高的性能高的性能或或功能功

26、能 * *規(guī)?？蓴U(kuò)展性規(guī)?？蓴U(kuò)展性：指系統(tǒng)指系統(tǒng)最多允許增加最多允許增加的的P P數(shù)量，增加應(yīng)包括數(shù)量，增加應(yīng)包括 IN IN、NICNIC等；等； * *資源可擴(kuò)展性資源可擴(kuò)展性：指系統(tǒng)指系統(tǒng)最多允許增加的最多允許增加的MEMMEM容量，增加應(yīng)容量，增加應(yīng)包包 括括CacheCache和磁盤等；和磁盤等； * *軟件可擴(kuò)展性軟件可擴(kuò)展性：指系統(tǒng)指系統(tǒng)是否是否允許擴(kuò)展允許擴(kuò)展OSOS、編譯器、編譯器、數(shù)學(xué)庫數(shù)學(xué)庫 和和工程庫、應(yīng)用軟件和編程環(huán)境工程庫、應(yīng)用軟件和編程環(huán)境等等回46頁回49頁182 2、應(yīng)用可擴(kuò)展性、應(yīng)用可擴(kuò)展性 指指機(jī)器規(guī)模擴(kuò)大機(jī)器規(guī)模擴(kuò)大( (問題規(guī)模不變問題規(guī)模不變) )時(shí)

27、，系統(tǒng)性能時(shí)，系統(tǒng)性能應(yīng)成應(yīng)成比例比例提高提高；問題規(guī)模擴(kuò)大問題規(guī)模擴(kuò)大( (機(jī)器規(guī)模不變機(jī)器規(guī)模不變) )時(shí)，系統(tǒng)性能時(shí)，系統(tǒng)性能應(yīng)應(yīng)不會(huì)明顯不會(huì)明顯下降下降 * *機(jī)器規(guī)模可擴(kuò)展性：機(jī)器規(guī)?？蓴U(kuò)展性：指隨著資源指隨著資源( (P P、MEMMEM、I/OI/O) )的增加，的增加， 系統(tǒng)性能可提高系統(tǒng)性能可提高的的程度程度 例例處理處理某問題時(shí)某問題時(shí)T T32P32P=100h=100h，若，若T T64P64P50h50h，則，則 * *問題規(guī)?？蓴U(kuò)展性：?jiǎn)栴}規(guī)?？蓴U(kuò)展性：指隨著問題指隨著問題規(guī)模的增加，規(guī)模的增加， 系統(tǒng)性能系統(tǒng)性能下降的下降的程度程度應(yīng)應(yīng)不會(huì)不會(huì)失衡失衡 例例矩陣矩

28、陣加加運(yùn)算時(shí)運(yùn)算時(shí)T Tmnmnmnmn=kT=kTn nn n，若，若k=ck=cm m2 2，則，則 機(jī)器規(guī)模及問題規(guī)模應(yīng)與機(jī)器規(guī)模及問題規(guī)模應(yīng)與程序處理方法程序處理方法相相對(duì)應(yīng)對(duì)應(yīng) 反例反例若程序并行度若程序并行度為為3232，則，則P P3232時(shí)時(shí)性能永遠(yuǎn)性能永遠(yuǎn)不變不變回49頁193 3、技術(shù)可擴(kuò)展性、技術(shù)可擴(kuò)展性 指系統(tǒng)指系統(tǒng)適應(yīng)技術(shù)改變適應(yīng)技術(shù)改變的程度，有代的程度，有代可擴(kuò)展性、空間可擴(kuò)展性可擴(kuò)展性、空間可擴(kuò)展性和異構(gòu)可和異構(gòu)可擴(kuò)展性擴(kuò)展性3 3個(gè)方面?zhèn)€方面 * *代可擴(kuò)展性：代可擴(kuò)展性：系統(tǒng)對(duì)使用下一代部件或系統(tǒng)對(duì)使用下一代部件或軟件的軟件的支持支持程度程度 例例更換處理器

29、，應(yīng)不需要更換主板等更換處理器，應(yīng)不需要更換主板等 * *空間可擴(kuò)展性：空間可擴(kuò)展性：系統(tǒng)對(duì)地理位置擴(kuò)展的支持系統(tǒng)對(duì)地理位置擴(kuò)展的支持程度程度 例例SMPSMP、MPPMPP空間可擴(kuò)展性有限空間可擴(kuò)展性有限， Internet Internet網(wǎng)網(wǎng)空間可擴(kuò)展性空間可擴(kuò)展性最好最好 * *異構(gòu)可擴(kuò)展性：異構(gòu)可擴(kuò)展性：系統(tǒng)對(duì)不同設(shè)計(jì)者和系統(tǒng)對(duì)不同設(shè)計(jì)者和廠商軟硬件廠商軟硬件的支持的支持程度程度 例例硬件是否具有標(biāo)準(zhǔn)接口、開放系統(tǒng)結(jié)構(gòu)硬件是否具有標(biāo)準(zhǔn)接口、開放系統(tǒng)結(jié)構(gòu)， 軟件是否可軟件是否可移植移植等等回下頁20二、可擴(kuò)展設(shè)計(jì)原理二、可擴(kuò)展設(shè)計(jì)原理 包括獨(dú)立原理、平衡設(shè)計(jì)原理、可擴(kuò)展設(shè)計(jì)原理和包括獨(dú)

30、立原理、平衡設(shè)計(jì)原理、可擴(kuò)展設(shè)計(jì)原理和時(shí)延包時(shí)延包容原理容原理4 4個(gè)個(gè)方面方面1 1、獨(dú)立原理、獨(dú)立原理 應(yīng)應(yīng)努力使努力使系統(tǒng)的系統(tǒng)的各組成部分各組成部分( (軟件及硬件軟件及硬件) )相互相互獨(dú)立獨(dú)立 原理特點(diǎn)：原理特點(diǎn)：便于實(shí)現(xiàn)資源、軟件、代及便于實(shí)現(xiàn)資源、軟件、代及異構(gòu)可擴(kuò)展性異構(gòu)可擴(kuò)展性 示例示例算法算法應(yīng)獨(dú)立于體系結(jié)構(gòu)應(yīng)獨(dú)立于體系結(jié)構(gòu)( (如如InternetInternet) )， 程序設(shè)計(jì)語言應(yīng)獨(dú)立于機(jī)器硬件程序設(shè)計(jì)語言應(yīng)獨(dú)立于機(jī)器硬件( (如如C C語言語言) )， 節(jié)點(diǎn)節(jié)點(diǎn)應(yīng)獨(dú)立于網(wǎng)絡(luò)、應(yīng)獨(dú)立于網(wǎng)絡(luò)、NICNIC獨(dú)立于網(wǎng)絡(luò)拓?fù)洫?dú)立于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)結(jié)構(gòu) * *獨(dú)立的實(shí)現(xiàn)：獨(dú)立的

31、實(shí)現(xiàn)：體系結(jié)構(gòu)與實(shí)現(xiàn)體系結(jié)構(gòu)與實(shí)現(xiàn)分離分離 使用標(biāo)準(zhǔn)使用標(biāo)準(zhǔn)組件組件轉(zhuǎn)43頁轉(zhuǎn)上頁212 2、平衡設(shè)計(jì)原理、平衡設(shè)計(jì)原理 應(yīng)應(yīng)努力努力最小最小化性化性能瓶頸能瓶頸和和避免單點(diǎn)避免單點(diǎn)失效失效(1)Amdaha(1)Amdaha定律定律 系統(tǒng)性能系統(tǒng)性能改善程度改善程度(S)(S)取決于取決于改進(jìn)部分被使用的改進(jìn)部分被使用的頻率頻率(2)Amdaha(2)Amdaha法則法則 系統(tǒng)系統(tǒng)處理速度應(yīng)處理速度應(yīng)與與MEMMEM容量和容量和I/OI/O速度速度相平衡相平衡 * *常用平衡點(diǎn)：常用平衡點(diǎn)：1MIPS1MIPS1MB1MB1Mb/s1Mb/s 注注此此結(jié)果不結(jié)果不包含非包含非計(jì)算需求計(jì)算需求

32、( (如檢查點(diǎn)如檢查點(diǎn)) )eeeerffTTPS/)1(10改進(jìn)后運(yùn)行時(shí)間改進(jìn)前運(yùn)行時(shí)間 * *平衡的實(shí)現(xiàn)平衡的實(shí)現(xiàn)：優(yōu)先處理高頻優(yōu)先處理高頻使用使用部件，避免部件，避免性能性能瓶頸產(chǎn)生瓶頸產(chǎn)生22(3)50%(3)50%法則法則 平衡理解平衡理解、t tp p、t t0 0及及t tc c等相加項(xiàng)均相近時(shí)等相加項(xiàng)均相近時(shí) * *50%50%法則法則：若程序性能各相加項(xiàng)的若程序性能各相加項(xiàng)的每項(xiàng)使系統(tǒng)性能衰減均不每項(xiàng)使系統(tǒng)性能衰減均不大于大于50%50%時(shí)，認(rèn)為該系統(tǒng)是平衡的時(shí)，認(rèn)為該系統(tǒng)是平衡的 程序性能程序性能若工作若工作負(fù)載負(fù)載= =nwnw，則則n n個(gè)個(gè)節(jié)點(diǎn)的并行執(zhí)行時(shí)間節(jié)點(diǎn)的并行

33、執(zhí)行時(shí)間)()()()log2( 0parallelecommunicatcomputentntwnttnwTTTTpcfn其中：其中：t tf f -一個(gè)浮點(diǎn)操作時(shí)間；一個(gè)浮點(diǎn)操作時(shí)間；-負(fù)載不平衡開銷；負(fù)載不平衡開銷； t t0 0 -通信啟動(dòng)開銷；通信啟動(dòng)開銷；t tc c-每字節(jié)通信開銷；每字節(jié)通信開銷； -通信通信- -計(jì)算比；計(jì)算比； t tp p-并行化開銷并行化開銷 * *平衡的平衡的實(shí)現(xiàn)：實(shí)現(xiàn)：平衡平衡w w、t tf f、t t0 0、t tc c、t tp p之間關(guān)系，之間關(guān)系，使程序性能的各相加項(xiàng)使程序性能的各相加項(xiàng)基本基本相等相等23轉(zhuǎn)43頁轉(zhuǎn)44頁顆粒度顆粒度w w

34、 (flop) (flop)節(jié)點(diǎn)速度節(jié)點(diǎn)速度1/1/t tf f ( (MflopMflop/s)/s)啟動(dòng)開銷啟動(dòng)開銷t t0 0 ( (ss) )100(100(細(xì)細(xì)) )4 425252020551000(1000(中中) )101010010050502020 例例1 1根據(jù)給定的根據(jù)給定的w及及1/tf，估算平衡的通信啟動(dòng)開銷估算平衡的通信啟動(dòng)開銷t0 0 解解平衡時(shí)通信啟動(dòng)開銷平衡時(shí)通信啟動(dòng)開銷t0 0wtf，即，即 例例2 2根據(jù)給定的根據(jù)給定的及及1/tf，估算平衡的通信帶寬估算平衡的通信帶寬1/1/tc c 解解平衡時(shí)通信帶寬平衡時(shí)通信帶寬1/1/tc ctf，即，即通信通信

35、/ /計(jì)算計(jì)算(B/flop)(B/flop)節(jié)點(diǎn)速度節(jié)點(diǎn)速度1/1/t tf f( (MflopMflop/s)/s)通信帶寬通信帶寬1/1/t tc c(MB/s)(MB/s)0.010.014 40.040.0420200.20.20.10.1101011505055 原理特點(diǎn)：原理特點(diǎn)：便于實(shí)現(xiàn)規(guī)模、資源及應(yīng)用可便于實(shí)現(xiàn)規(guī)模、資源及應(yīng)用可擴(kuò)展性擴(kuò)展性243 3、可擴(kuò)展設(shè)計(jì)原理、可擴(kuò)展設(shè)計(jì)原理 系統(tǒng)設(shè)計(jì)時(shí)增加一些特性，以滿足可擴(kuò)展性需要，包括系統(tǒng)設(shè)計(jì)時(shí)增加一些特性，以滿足可擴(kuò)展性需要，包括過度過度設(shè)計(jì)設(shè)計(jì)和和向后兼容性向后兼容性設(shè)計(jì)設(shè)計(jì)2 2個(gè)方面?zhèn)€方面 * *過度設(shè)計(jì)過度設(shè)計(jì)：設(shè)計(jì)時(shí)增加一些特性設(shè)計(jì)時(shí)增加一些特性，以兼顧將來擴(kuò)展的需求以兼顧將來擴(kuò)展的需求 例例PCIPCI總線的總線的AD63:32AD