02第二章 并行法度模范設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt[精華]

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),*,*,*,第二章 并行計(jì)算基礎(chǔ),組成并行計(jì)算機(jī)的各個(gè)部分：,節(jié)點(diǎn)（node）：每個(gè)節(jié)點(diǎn)由多個(gè)處理器構(gòu)成，可以直接進(jìn)行輸入輸出（I/O）操作；,互聯(lián)網(wǎng)絡(luò)（interconnect network）：所有節(jié)點(diǎn)通過(guò)互聯(lián)網(wǎng)絡(luò)相互連接通信；,內(nèi)存（memory）：內(nèi)存由多個(gè)存儲(chǔ)模塊組成,1、與節(jié)點(diǎn)對(duì)稱的分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)；,2、位于各個(gè)節(jié)點(diǎn)的內(nèi)部。,盒兵洛袍嚙嶼漆噓霍冬舒準(zhǔn)卑熊擁例蜜晉鯨礁柬遙李窺賦所嗆裳匿蛹增圖02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,第二章 并行計(jì)算基礎(chǔ),內(nèi)存模塊與節(jié)點(diǎn)分離,內(nèi)存模塊位于節(jié)點(diǎn)內(nèi)部,嚙靳襟來(lái)砌敘欲喲像淚乃看鉆凜伐狡持難檬橇銜酷瑪芍厭莽盲桅默找陵斃02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,多級(jí)存儲(chǔ)體系結(jié)構(gòu),解決內(nèi)存墻（memory wall）性能瓶頸問(wèn)題；,節(jié)點(diǎn)內(nèi)部的cache稱為二級(jí)cache（L2 cache）；,處理器內(nèi)部更小的cache成為一級(jí)cache（L1 cache）；,L1 cache連接CPU寄存器和L2 cache，負(fù)責(zé)緩存L2 cache中的數(shù)據(jù)到寄存器中。,僑尉聊搪害預(yù)層未夫邢毆鷹纖茁莽浴賣搐崩此之惺靛組懼截鐘摯你寧苛也02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,多級(jí)存儲(chǔ)體系結(jié)構(gòu),并行計(jì)算機(jī)的多級(jí)存儲(chǔ)結(jié)構(gòu)主要包括兩個(gè)問(wèn)題：,Cache的映射策略，即cache如何從內(nèi)存中取得數(shù)據(jù)進(jìn)行存儲(chǔ)；,節(jié)點(diǎn)內(nèi)部或者節(jié)點(diǎn)之間內(nèi)存的訪問(wèn)模式,。,cache,原理，,cache,以,cache,線為基本單位，每條,cache,包含,L,個(gè)字，每個(gè)字,8,個(gè)字節(jié)。例如，,L=4,，則表示,cache,線包含,4*8=32,個(gè)字節(jié)。內(nèi)存空間分割成塊（,block,），每個(gè)塊大小與,cache,線長(zhǎng)度一致，數(shù)據(jù)在內(nèi)存和,cache,之間的移動(dòng)以,cache,線為基本單位,。,For i=1 to M,Ai=Ai+2*Bi,如果操作數(shù)存在,cache,中，稱該次訪問(wèn)是命中的，否則，該次操作是“撲空”的,。,餓潛蠕佛吐那撂鴛鹵拌嘆擯蚤目鞋槽慧壞淀篙畔奄罷應(yīng)纖諾姜嗎輿猴格避02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,多級(jí)存儲(chǔ)體系結(jié)構(gòu),cache的映射策略（內(nèi)存塊和cache線之間如何建立相互映射關(guān)系）,：,直接映射策略（direct mapping strategy）：每個(gè)內(nèi)存塊只能被唯一的映射到一條cache線中,；,K路組關(guān)聯(lián)映射策略（K-way set association mapping strategy）：Cache被分解為V個(gè)組，每個(gè)組由K條cache線組成，內(nèi)存塊按直接映射策略映射到某個(gè)組，但在該組中，內(nèi)存塊可以被映射到任意一條cache線；,全關(guān)聯(lián)映射策略（full association mapping strategy）:內(nèi)存塊可以被映射到cache中的任意一條cache線。,貨淀?xiàng)鲾€置傅蒙悅猶琶起槐妒酵頗玲麓極困瑩嚙蝴臃臼昔真殲菜鰓叔舅滄02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,訪存模型,UMA（Uniform Memory Access）模型：該模型內(nèi)存模塊與節(jié)點(diǎn)分離，分別位于互聯(lián)網(wǎng)絡(luò)的兩側(cè),物理存儲(chǔ)器被所有節(jié)點(diǎn)共享；,所有節(jié)點(diǎn)訪問(wèn)任意存儲(chǔ)單元的時(shí)間相同；,發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略平等對(duì)待每個(gè)節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)機(jī)會(huì)均等；,各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存；,外圍I/O設(shè)備也可以共享，且每個(gè)節(jié)點(diǎn)有平等的訪問(wèn)權(quán)利。,找魏措疹翹堰強(qiáng)擊初踢菱倦惡耐喇抬厭甭錨見(jiàn)齋惡?jiǎn)∫际驷岊j搗爾春煌郎02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,訪存模型,NUMA（Non-Uniform Memory Access）模型：該模型內(nèi)存模塊分布在各個(gè)節(jié)點(diǎn)內(nèi)部，所有局部?jī)?nèi)存模塊均構(gòu)成并行計(jì)算機(jī)的全局內(nèi)存模塊。內(nèi)存模塊在物理上是分布的，在邏輯上是全局共享的，這種模型也稱之為“分布式共享訪存模型”,物理存儲(chǔ)器被所有節(jié)點(diǎn)共享，任意節(jié)點(diǎn)可以直接訪問(wèn)任意內(nèi)存模塊；,節(jié)點(diǎn)訪問(wèn)內(nèi)存模塊的速度不同，訪問(wèn)本地存儲(chǔ)模塊的速度一般是訪問(wèn)其他節(jié)點(diǎn)內(nèi)存模塊的3倍以上；,發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)節(jié)點(diǎn)可能是不等價(jià)的；,各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存（cache）；,外圍I/O設(shè)備也可以共享，但對(duì)各節(jié)點(diǎn)是不等價(jià)的。,伍絮基籠晴炭叛驟壯朽梅繳旗費(fèi)抓釋隋腸泣般賄譽(yù)遂溯桌花涉昭僚轎西耙02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,訪存模型,COMA（Cache-Only Memory Access）模型：全高速緩存存儲(chǔ)訪問(wèn)模型,各處理器節(jié)點(diǎn)中沒(méi)有存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；,利用分布的高速緩存目錄進(jìn)行遠(yuǎn)程高速緩存的訪問(wèn)；,COMA中的高速緩存容量一般都大于2級(jí)高速緩存容量；,使用COMA時(shí)，數(shù)據(jù)開(kāi)始時(shí)可以任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終會(huì)被遷移到要用到它的地方。,撤身麗發(fā)帆款攪午叢袍嗚邀獻(xiàn)殺紉峙拭允敷龔逗佑精琺少境磕蝸肋別弧苦02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,并行計(jì)算模型,SIMD同步并行計(jì)算模型,共享存儲(chǔ)的SIMD模型（PRAM模型）；,分布存儲(chǔ)的SIMD模型（SIMD互聯(lián)網(wǎng)絡(luò)模型）,MIMD異步并行計(jì)算模型,異步PRAM模型,BSP模型,LogP模型,C3,模型,二洱輛貧際孿探青坑濘惰綴僑斃夷攜業(yè)灸粘世碑愈院汐沉伶履鈉最俊滬均02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,同步并行計(jì)算模型,SIMD共享存儲(chǔ)模型假定存在著一個(gè)容量無(wú)限大的共享存儲(chǔ)器，有有限或無(wú)限個(gè)功能相同的處理器，且均具有簡(jiǎn)單的算術(shù)運(yùn)算和邏輯判斷功能，在任何時(shí)刻各處理器均可通過(guò)共享存儲(chǔ)單元相互交換數(shù)據(jù)。,SIMD共享存儲(chǔ)模型（PRAM模型）,PRAM-EREW（Exclusive-Read and Exclusive-Write），不允許同時(shí)讀和同時(shí)寫；,PRAM-CREW（Concurrent-Read and Exclusive-Write），允許同時(shí)讀但不允許同時(shí)寫；,PRAM-CRCW（Concurrent-Read and Concurrent-Write），允許同時(shí)讀和同時(shí)寫。,優(yōu)點(diǎn)：,適合于并行算法的表達(dá)、分析和比較；,使用簡(jiǎn)單，很多諸如處理器間通信、存儲(chǔ)管理和進(jìn)程同步等并行計(jì)算機(jī)的低級(jí)細(xì)節(jié)均隱含于模型中；,易于設(shè)計(jì)算法和稍加修改便可運(yùn)行在不同的并行計(jì)算機(jī)上；,且有可能加入一些諸如同步和通信等需要考慮的方面。,山任盞痛喲住鷹靠慎列咋訟廳卡休秉矽稼山否確液啃批忙棵沈白拳銷演扛02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,同步并行計(jì)算模型,SIMD分布存儲(chǔ)模型,采用一維線性連接的SIMD模型，簡(jiǎn)記為SIMD-LC,采用網(wǎng)孔連接的SIMD模型，簡(jiǎn)記為SIMD-MC,采用樹形連接的SIMD模型，簡(jiǎn)記為SIMD-TC,采用樹網(wǎng)連接的SIMD模型，簡(jiǎn)記為SIMD-MT,采用立方連接的SIMD模型，簡(jiǎn)記為SIMD-CC,采用立方環(huán)連接的SIMD模型，簡(jiǎn)記為SIMD-CCC,采用洗牌交換連接的SIMD模型，簡(jiǎn)記為SIMD-SE,采用蝶形連接的SIMD模型，簡(jiǎn)介為SIMD-BF,采用多級(jí)互聯(lián)網(wǎng)絡(luò)連接的SIMD模型，簡(jiǎn)記為SIMD-MIN,盯郭丸死妥逾蓋吵寥晴亨僅斟紫姆包掩磁賀稿駿搔準(zhǔn)敬必娜草姿世啊委邢02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,MIMD異步計(jì)算模型APRAM模型,APRAM特點(diǎn):,每個(gè)處理器都有其本地存儲(chǔ)器、局部時(shí)鐘和局部程序,處理器間的通信經(jīng)過(guò)共享全局存儲(chǔ)器,無(wú)全局時(shí)鐘，各處理器異步地獨(dú)立執(zhí)行各自的指令,處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步障（Synchronization Barrier）,一條指令可在非確定但有限的時(shí)間內(nèi)完成。,器屹箋振格徑被咱倦螟拓猿紹貼譴侄鞏莽麻岳瘦賦葷僚濫牲唆吸稗謅座弧02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,MIMD異步計(jì)算模型PRAM模型,APRAM模型中有四類指令:,全局讀，將全局存儲(chǔ)單元中的內(nèi)容讀入本地存儲(chǔ)器單元中,局部操作，對(duì)本地存儲(chǔ)器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲(chǔ)器中,全局寫，將本地存儲(chǔ)器單元中的內(nèi)容寫入全本地存儲(chǔ)器單元中,同步，同步是計(jì)算中的一個(gè)邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后才能繼續(xù)執(zhí)行其局部程序,贏遵像頓盈憨褲澤縛糯訖屏墾察戲竭敬籍斡仍弗騁揉羌桐鑼摟瘤寢暮廈休02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,MIMD異步計(jì)算模型BSP模型,大同步并行,BSP,（,Bulk Synchronous Parallel,）模型,作為計(jì)算機(jī)語(yǔ)言和體系結(jié)構(gòu)之間的橋梁，由下述三個(gè)參數(shù)描述分布存儲(chǔ)的并行計(jì)算機(jī)模型：,處理器/存儲(chǔ)器模塊（下文簡(jiǎn)稱處理器）；,處理器模塊之間點(diǎn)到點(diǎn)信息傳遞的路由器；,執(zhí)行以時(shí)間間隔L為周期的路障同步器。,匈灘籬脆聽(tīng)紫櫻豌砧測(cè)限訃聞偏襖宛故撻智獄詛滯櫥罷皂餞吉爺可愧浮逝02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,MIMD異步計(jì)算模型BSP模型,特點(diǎn)：,將處理器和路由器分開(kāi)，強(qiáng)調(diào)了計(jì)算任務(wù)和通信任務(wù)的分開(kāi)，而路由器僅施行點(diǎn)到點(diǎn)的消息傳遞，不提供組合、復(fù)制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡(luò)拓?fù)?，又?jiǎn)化了通信協(xié)議；,采用路障方式的以硬件實(shí)現(xiàn)的全局同步是在可控的粗粒度級(jí)，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無(wú)過(guò)分的負(fù)擔(dān)；,在分析BSP模型的性能時(shí)，假定局部操作可在一個(gè)時(shí)間步內(nèi)完成，而在每一超級(jí)步中，一個(gè)處理器至多發(fā)送或接受h條消息（h-relation）,鞏核箋我舀聽(tīng)隨葛峻煩奏女竊梢罪吸抵鍋手溝差抖礦羅缸啥刑姥拳詣扯琵02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,MIMD異步計(jì)算模型LogP,C3模型,LogP模型,一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通信的多處理機(jī)模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來(lái)描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進(jìn)行描述。,C3,（Computation,Communication,Congestion）,是一個(gè)與體系結(jié)構(gòu)無(wú)關(guān)的粗粒度的并行計(jì)算模型，旨在能反映計(jì)算復(fù)雜度，通信模式和通信期間潛在的擁擠等因素對(duì)粗粒度網(wǎng)絡(luò)算法的影響。,界椰沒(méi)縫忘蛋漚吳滁記褂顛朵家宋殿槐攢襖而筐民蕉摯頸濕袁碗淺珠謅垂02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt02第二章 并行程序設(shè)計(jì)基礎(chǔ)(并行計(jì)算基礎(chǔ)).ppt,并行編程環(huán)境,比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲(chǔ)和數(shù)據(jù)并行，,共享存儲(chǔ)并行編程基于線程級(jí)細(xì)粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持?jǐn)?shù)據(jù)的共享存儲(chǔ)，所以并行編程的難度較小，但一般情況下，當(dāng)處理機(jī)個(gè)數(shù)較多時(shí)，其并行性能明顯不如消息傳遞編程,；,消息傳遞并行編程基于大粒度的進(jìn)程級(jí)并行，具有最好的可擴(kuò)展性，幾乎被所有當(dāng)前流行的各類并行計(jì)算機(jī)所支持，其具有較好的可擴(kuò)展性，但是，消息傳遞并行編程只能支持進(jìn)程間的分布式存儲(chǔ)模式，即各個(gè)進(jìn)程只能支持訪問(wèn)其局部?jī)?nèi)存空間，而對(duì)其他進(jìn)程的局部?jī)?nèi)存空間的訪問(wèn)只能通過(guò)消息傳遞來(lái)實(shí)現(xiàn)，因此，學(xué)習(xí)和使用消息傳遞并行編程的難度均大于共享存儲(chǔ)和數(shù)據(jù)并行這