《多處理機(jī)》課件

一、多處理機(jī)的特點(diǎn)和主要技術(shù)指標(biāo),1、定義： 兩個(gè)或兩個(gè)以上處理機(jī)(包括PU和CU)，通過(guò)高速互連網(wǎng)絡(luò)連接起來(lái)，在統(tǒng)一的操作系統(tǒng)管理下，實(shí)現(xiàn)指令以上級(jí)（任務(wù)級(jí)、作業(yè)級(jí)）并行。 按照Flynn分類法，多處理機(jī)系統(tǒng)屬于MIMD計(jì)算機(jī)。 多處理機(jī)系統(tǒng)由多個(gè)獨(dú)立的處理機(jī)組成，每個(gè)處理機(jī)都能夠獨(dú)立執(zhí)行自己的程序。 存儲(chǔ)器操作并行并行存儲(chǔ)系統(tǒng)、相聯(lián)處理機(jī) 處理器操作步驟并行流水線處理機(jī) 處理器操作并行陣列處理機(jī) 任務(wù)、作業(yè)并行多處理機(jī),2、目的： 通過(guò)多個(gè)作業(yè)、任務(wù)的并行處理提高大而復(fù)雜問(wèn)題的解題速度 使用冗余的多個(gè)處理機(jī)，通過(guò)重新組織來(lái)提高系統(tǒng)的可靠性、適用性和可用性,（1）、結(jié)構(gòu)靈活性 并行處理機(jī)： 專用，PE數(shù)很多（幾千個(gè)），固定有限的通信 多處理機(jī)： 通用，幾十個(gè)，高速靈活的通信 （2）、程序并行性 并行處理機(jī) 并行性存在于指令內(nèi)部，識(shí)別比較容易 多處理機(jī) 并行性存在于指令外部，在多個(gè)任務(wù)之間，識(shí)別難度較大,3、特點(diǎn),（3）、并行任務(wù)派生并行處理機(jī)把同種操作集中在一起，由指令直接啟動(dòng)各PE同時(shí)工作。 多處理機(jī)用專門的指令來(lái)表示并發(fā)關(guān)系，一個(gè)任務(wù)開(kāi)始執(zhí)行時(shí)能夠派生出與它并行執(zhí)行的另一些任務(wù)，如果任務(wù)數(shù)多于處理機(jī)數(shù)，多余的任務(wù)進(jìn)入排隊(duì)器等待。 （4）、進(jìn)程同步并行處理機(jī)僅一個(gè)CU，自然是同步的 多處理機(jī)執(zhí)行不同的指令，工作進(jìn)度不會(huì)也不必保持相同,先做完的要停下來(lái)等待。有數(shù)據(jù)相關(guān)和控制相關(guān)也要停下來(lái)等待,要采取特殊的同步措施來(lái)保持程序所要求的正確順序。,（5）、資源分配和進(jìn)程調(diào)度并行處理機(jī)的PE是固定的，采用屏蔽手段改變實(shí)際參加操作的PE數(shù)目多處理機(jī)執(zhí)行并發(fā)任務(wù)，需用處理機(jī)的數(shù)目不固定，各個(gè)處理機(jī)進(jìn)入或退出任務(wù)的時(shí)刻不相同，所需共享資源的品種、數(shù)量又隨時(shí)變化 提出資源分配和進(jìn)程調(diào)度問(wèn)題，它對(duì)整個(gè)系統(tǒng)的效率有很大的影響。,多處理機(jī)為適應(yīng)多種算法，要求結(jié)構(gòu)能更靈活、變化要多，可以實(shí)現(xiàn)復(fù)雜的機(jī)間互連且避免爭(zhēng)用共享的硬件資源 多處理機(jī)的并行性主要體現(xiàn)于指令的外部，使得程序并行性的識(shí)別比較困難。它必須利用算法、程序語(yǔ)言、編譯、操作系統(tǒng)、指令及硬件等，從多種途徑去挖掘出各種潛在的并行性。 多處理機(jī)需要有專門的指令或語(yǔ)句來(lái)控制并行任務(wù)的派生。根據(jù)并發(fā)任務(wù)之間的數(shù)據(jù)相關(guān)或控制依賴等關(guān)系，使用專門的手段來(lái)進(jìn)行并行任務(wù)（進(jìn)程）的同步。,多處理機(jī)執(zhí)行并發(fā)任務(wù)所需的處理機(jī)的機(jī)數(shù)是不定的。各處理機(jī)進(jìn)入或退出任務(wù)所需資源的變化比較復(fù)雜，必須較好的解決動(dòng)態(tài)的資源分配和任務(wù)調(diào)度，讓各處理機(jī)的負(fù)荷盡可能均衡，防止死鎖。 多處理機(jī)中某個(gè)處理機(jī)發(fā)生故障后，應(yīng)知道如何重新組織系統(tǒng)，使系統(tǒng)不至于癱瘓。多處理機(jī)機(jī)數(shù)增多后，應(yīng)知道如何提供良好的編程環(huán)境。 因此，多處理機(jī)的結(jié)構(gòu)、機(jī)間互連、并行算法、并行語(yǔ)言、編譯、操作系統(tǒng)等都將會(huì)直接影響到系統(tǒng)的性能和效率的提高。,二、多處理機(jī)的硬件結(jié)構(gòu),1、多處理機(jī)的構(gòu)型 緊耦合多處理機(jī)通過(guò)共享主存實(shí)現(xiàn)機(jī)間通信 為了減少訪問(wèn)主存的沖突，主存采用模m多體交叉方式組織。如果處理機(jī)自帶局部存儲(chǔ)器或再加上Cache存儲(chǔ)器，可以大大提高系統(tǒng)的性能，降低對(duì)處理機(jī)存儲(chǔ)器互聯(lián)網(wǎng)絡(luò)的使用發(fā)生沖突的概率。 松耦合多處理機(jī)的每臺(tái)處理機(jī)有一個(gè)容量較大的存儲(chǔ)器，用于存放各處理機(jī)常用的指令和數(shù)據(jù)，減少訪主存的沖突。處理機(jī)之間通過(guò)通道或消息傳送系統(tǒng)MTS來(lái)進(jìn)行通信。,2、多處理機(jī)的機(jī)間互連形式 總線形式具有結(jié)構(gòu)簡(jiǎn)單、成本低、可擴(kuò)充性好的優(yōu)點(diǎn)。但性能和可靠性嚴(yán)重受物理因素的制約。總線形式需要使用相應(yīng)的總線控制機(jī)構(gòu)和總線仲裁算法，來(lái)解決總線的訪問(wèn)沖突。 令牌環(huán)網(wǎng)的互連形式采用點(diǎn)點(diǎn)連接，其物理參數(shù)容易得到控制，非常適合于有高通訊帶寬的光纖通信。 縱橫交叉開(kāi)關(guān)形式是多總線朝總線數(shù)增加方向發(fā)展的一種極端情況，它適影響系統(tǒng)性能的瓶頸不再是互聯(lián)網(wǎng)絡(luò)，而轉(zhuǎn)到了共享的主存。它適合處理機(jī)機(jī)數(shù)較多的情形，但也不宜超過(guò)32臺(tái)，否則將是系統(tǒng)造價(jià)過(guò)高。采用交叉開(kāi)關(guān)互連具有可擴(kuò)充性好，系統(tǒng)流量大的特點(diǎn)。,多端口存儲(chǔ)器互連是將分布于交叉開(kāi)關(guān)矩陣中的控制，轉(zhuǎn)移和優(yōu)先級(jí)仲裁邏輯放置到相應(yīng)存儲(chǔ)器模塊的接口中來(lái)。它對(duì)機(jī)數(shù)少的多處理機(jī)場(chǎng)合還是很適用的，但處理機(jī)機(jī)數(shù)固定了，不能隨意擴(kuò)充，整個(gè)系統(tǒng)性能不可能很高。 分布式結(jié)構(gòu)的開(kāi)關(guān)樞紐形式：將互連結(jié)構(gòu)的開(kāi)關(guān)設(shè)置在各處理機(jī)或接口內(nèi)部。在這種形式中，每臺(tái)處理機(jī)都經(jīng)過(guò)其開(kāi)關(guān)樞紐與其它多臺(tái)處理機(jī)連接，適合于用在處理機(jī)機(jī)數(shù)很多的分布式多處理機(jī)的場(chǎng)合。可擴(kuò)充性好，系統(tǒng)流量大。,3、存儲(chǔ)器組織 在多處理機(jī)上，如果各個(gè)處理機(jī)活躍的進(jìn)程是共享同一個(gè)集中連續(xù)的物理地址空間中的數(shù)據(jù)時(shí)，主存宜采用低位交叉編址；如果較少或基本不共享集中的數(shù)據(jù)時(shí)，主存宜用高位交叉編址。 采用Cache存儲(chǔ)器時(shí)，應(yīng)解決好多個(gè)Cache存儲(chǔ)器之間信息的一致性問(wèn)題。目前，主要采用以硬件為基礎(chǔ)的監(jiān)視Cache協(xié)議法。,三、多處理機(jī)的操作系統(tǒng),1、主從型：操作系統(tǒng)只在一個(gè)指定的主處理機(jī)上運(yùn)行，采用集中控制 硬件比較簡(jiǎn)單；但系統(tǒng)易癱瘓，如果主處理機(jī)工作負(fù)荷重，會(huì)影響整個(gè)系統(tǒng)的性能。適合于工作負(fù)荷固定，異構(gòu)型多處理機(jī) 2、各自獨(dú)立型：將控制功能分散到多臺(tái)處理機(jī)上，由他們共同來(lái)完成。 每臺(tái)處理機(jī)都有一個(gè)獨(dú)立的管理程序在運(yùn)行。某個(gè)處理機(jī)發(fā)生故障，不會(huì)引起整個(gè)系統(tǒng)的癱瘓。但是，實(shí)現(xiàn)較復(fù)雜，進(jìn)程調(diào)度的復(fù)雜性和開(kāi)銷加大，若某臺(tái)處理機(jī)發(fā)生故障，則難以恢復(fù)；各處理機(jī)負(fù)荷較難均衡。適合于地理位置分散的松耦合型多處理機(jī)。,3、浮動(dòng)型：操作系統(tǒng)的管理程序可在處理機(jī)之間浮動(dòng) 它可使各種資源有較好的負(fù)荷均衡；在硬件結(jié)構(gòu)和可靠性上有分布控制的優(yōu)點(diǎn)。在操作系統(tǒng)的復(fù)雜性和經(jīng)濟(jì)性上，它接近于主從型的，但操作系統(tǒng)的設(shè)計(jì)最為困難，適合于緊耦合的同構(gòu)型多處理機(jī)。,四、程序的并行性,1、并行算法： 它取決于計(jì)算機(jī)的結(jié)構(gòu)和題目，是提高多處理機(jī)并行性能的關(guān)鍵。 研究并行算法的一種思路是將大的程序分解成可由足夠多的處理機(jī)并行處理的并行過(guò)程。每個(gè)過(guò)程被看成是一個(gè)結(jié)點(diǎn)，將過(guò)程之間的關(guān)聯(lián)關(guān)系用結(jié)點(diǎn)組成的樹(shù)來(lái)描述。增大樹(shù)中每一層的結(jié)點(diǎn)數(shù)，即增大各處理機(jī)可并行運(yùn)行的過(guò)程數(shù)；降低樹(shù)的高度，即降低多處理機(jī)的運(yùn)算級(jí)數(shù)。,E = a + bx + cxx + dxxx,處理機(jī)的個(gè)數(shù)：P=3運(yùn)算的級(jí)數(shù)，樹(shù)高：T p =4 加速比，順序運(yùn)算的級(jí)數(shù)與并行運(yùn)算的級(jí)數(shù)比：S p = T1/T p =3/2 效率：E p = S p/p =1/2,E = a +x ( b + x( c + x (d),*,x,*,c,+,a,+,d,+,+,E = a ( b+c ( d+e ( f+gh ) ) ) E = ace ( f+gh )+a ( b+cd),g,h,f,e,d,c,b,a,+,*,g,h,f,e,a,c,*,+,*,*,*,*,+,a,b,c,d,處理機(jī)的個(gè)數(shù)：P=3 運(yùn)算的級(jí)數(shù)，樹(shù)高：T p =4 加速比，順序運(yùn)算的級(jí)數(shù)與并行運(yùn)算的級(jí)數(shù)比：S p = T1/T p =7/4 效率：E p = S p/p =7/12,2、編譯： 在多處理機(jī)上，程序的并行要求要設(shè)計(jì)出好的編譯程序，能將高級(jí)語(yǔ)言源程序盡可能編譯出并行度高的目標(biāo)程序，而不是生成指令間有著大量相關(guān)的串行程序。,3、程序段間的相關(guān)性分析 多個(gè)程序段、進(jìn)程、任務(wù)之間能否并行，依賴于程序的結(jié)構(gòu)。程序段間的數(shù)據(jù)關(guān)聯(lián)是限制程序并行的重要因素。 若有先寫后讀的數(shù)據(jù)相關(guān)，可以串行，不能并行。 若有先讀后寫的數(shù)據(jù)反相關(guān)，可以串行，不能交換串行?？梢圆⑿袌?zhí)行，但必須保證其寫入共享主存時(shí)的先讀后寫的次序。 若有（先）寫（后）寫的數(shù)據(jù)輸出相關(guān)，可以串行，在保證對(duì)相關(guān)單元寫入的先后次序的前提下，可以并行，但不能交換串行。,若同時(shí)有先寫后讀和先讀后寫兩種相關(guān)，以交換數(shù)據(jù)為目的時(shí)，則必須是并行，并要求讀與寫完全同步，不允許順序串性和交換串行。 若沒(méi)有任何相關(guān)，或僅有源數(shù)據(jù)相同時(shí)，可以并行，順序串行或交換串行 交換串行的目的是：如果程序段之間不能并行，也可以讓空閑的處理機(jī)提前去執(zhí)行后面的程序段，這可以從宏觀上增強(qiáng)各個(gè)程序段之間的并行度，加快作業(yè)完成的速度，改進(jìn)系統(tǒng)的運(yùn)行效率。,4、并行語(yǔ)言 為了增強(qiáng)程序并行性的識(shí)別能力，要求在程序語(yǔ)言中，能增設(shè)明確表示進(jìn)程并發(fā)和匯合的語(yǔ)句。 并行程序在多處理機(jī)上運(yùn)行需要用控制機(jī)構(gòu)管理并行任務(wù)的派生和匯合。 并行任務(wù)的派生和匯合通常使用軟件的手段來(lái)控制的。FORK派生 JOIN匯合 作為完整的并行語(yǔ)言，還要增加諸如程序分支、循環(huán)、并發(fā)進(jìn)程間的通訊和同步以及數(shù)組和進(jìn)程數(shù)組處理的描述。在多處理機(jī)上，處理機(jī)的機(jī)數(shù)多少是不會(huì)影響程序的編寫的，其所編寫的程序是可以在機(jī)數(shù)不同的多處理上通用的。,S1: U =A+B； S2: V=U/B； S3: W=A*U； S4: X=W-V ； S5: Y=W*U； S6: Z=X/Y,10 U=A+B FORK 30 20 V=U/B JOIN 2 GOTO 40 30 W=A*U JOIN 2 40 FORK 60 50 X=W-V JOIN 2 GOTO 70 60 Y=W*U JOIN 2 70 Z=X/Y,FORK 30,10+,20/,JOIN2,30*,GOTO 40,FORK 60,50-,60*,JOIN2,70/,FORK S2, S3, S4 S1 A1 = A1+ A2 JOIN 4 GOTO * S2 A3 = A3+ A4 JOIN 4 GOTO * S3 A5 = A5+ A6 JOIN 4 GOTO * S4 A7 = A7+ A8 JOIN 4 * FORK S6 S5 A1 = A1+ A3 JOIN 2 GOTO S7 S6 A5 = A5+ A7 JOIN 2 S7 A1 = A1+ A5,CPU 1,CPU2,t,CPU 1,CPU2,t,CPU3,FORK S2, S3, S4 S1 A1 = A1+ A2 JOIN 4 GOTO * S2 A3 = A3+ A4 JOIN 4 GOTO * S3 A5 = A5+ A6 JOIN 4 GOTO * S4 A7 = A7+ A8 JOIN 4,* FORK S6 S5 A1 = A1+ A3 JOIN 2 GOTO S7 S6 A5 = A5+ A7 JOIN 2 S7 A1 = A1+ A5,* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *,* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *,* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *,