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