計算機系統(tǒng)結(jié)構(gòu)期末復(fù)習(xí)-資料下載頁
2025-06-07 22:16本頁面
【正文】 兩個以上事件在 同一時間間隔內(nèi)發(fā)生。三條技術(shù)途徑：(1)資源重復(fù)：重復(fù)設(shè)置多個部件來提高速度。(2)時間重疊：流水線(3)資源共享：分時系統(tǒng)，分布式系統(tǒng)并行處理機（SMID）的定義：多個處理部件PU按照一定方式互連，在同一個控 制部件CU控制下，對各自的數(shù)據(jù)完成同一條指令規(guī)定 的操作。從CU看，指令是串行執(zhí)行的，從PU看，數(shù)據(jù) 是并行處理的。并行處理機也稱為陣列處理機，按照按照佛林分類法，它屬于SIMD處理機。并行處理機的兩種分類及其結(jié)構(gòu)分類：分布存儲器并行處理機和共享存儲器并行處理機 ?分布式存儲器并行處理機的結(jié)構(gòu)框圖 ?共享存儲器并行處理機的結(jié)構(gòu)框圖第九章多處理機的定義與特點多處理機定義：兩個或兩個以上處理機(包括PU和CU)，通過高 速互連網(wǎng)絡(luò)連接起來，在統(tǒng)一的操作系統(tǒng)管理下， 實現(xiàn)指令以上級（任務(wù)級、作業(yè)級）并行。多處理機系統(tǒng)的特點1. 結(jié)構(gòu)靈活并行處理機：專用，PE數(shù)多，固定有限通信多處理機： 通用，PE數(shù)少，高速靈活通信2. 程序并行性并行處理機的并行性存在于指令內(nèi)部，識別比較容易。 多處理機的并行性存在于指令外部，在多個任務(wù)之間，識 別難度較大。一個簡單的例子：Y = A+B*C*D/E+F，用兩個處理機計算：CPU1：B*C， A+F， A+B*C*D/E+FCPU2：D/E， B*C*D/E，3. 并行任務(wù)派生并行處理機把同種操作集中，由指令直接啟動各PE同時工 作。多處理機用專門的指令來表示并發(fā)關(guān)系，一個任務(wù)執(zhí)行時 能夠派生出與它并行的另一些任務(wù)。如果沒有空閑處理機，任務(wù)進(jìn)入排隊器等待。4. 進(jìn)程同步并行處理機僅一個CU，自然是同步的。多處理機中，各處理機執(zhí)行不同的指令，工作進(jìn)度不會也 不必保持相同。先做完的要停下等待。有數(shù)據(jù)相關(guān)和控制 相關(guān)也要停下等待。要采取同步措施來保持程序要求的正確順序5. 資源分配和進(jìn)程調(diào)度并行處理機的PE是固定的，用屏蔽來改變實際參加操 作的PE數(shù)目。多處理機執(zhí)行并發(fā)任務(wù)，需用處理機的數(shù)目不固定， 各處理機進(jìn)出任務(wù)的時刻不相同，所需共享資源的品 種、數(shù)量隨時變化。多處理機基本模型及其結(jié)論粒度與并行的關(guān)系并行性在很大程度上依賴于R/C比值，R/C是衡量任務(wù)粒度(Granularity)的尺度，其中：R: 程序執(zhí)行時間，C: 通信開銷細(xì)粒度并行：R/C小，通信開銷大,并行度低。粗粒度并行：R/C大，通信開銷小,并行性高。多處理機運算的基本模型目標(biāo)：由M個任務(wù)組成的程序，在N臺處理機組成的系統(tǒng)上 運行，求最短執(zhí)行時間？基本模型僅考慮由兩臺處理機組成的系統(tǒng)。假設(shè)：每個任務(wù)的執(zhí)行時間R；不在同一個處理機上的兩個任務(wù)需要相互通訊，每 次通訊時間為C?？偺幚頃r間＝R*Max(M－K，K)＋C*(M－K)*K其中：R：每個任務(wù)的執(zhí)行時間，C：通信開銷，K：任 務(wù)分配參數(shù)。通信時間C(MK)K是一個開口向下的二次函數(shù)，任務(wù)執(zhí)行時間是兩根相交的直線，最小值發(fā)生在中間即 K=M/2令：通訊時間＝執(zhí)行時間則 R*M/2=C*M/2*(MM/2)則 R/C=M/2當(dāng)通信時間比較大時(R/CM/2)，總時間的最小值發(fā)生在兩個 端點(K=0 K=M)；當(dāng)通信時間比較小時(R/CM/2)，總時間的最小值發(fā)生在中點 (K=M/2)?？倳r間最短的結(jié)論：當(dāng)R/C＜M/2時，把所有任務(wù)分配給同一臺處理機，K＝0；當(dāng)R/C＞M/2時，把任務(wù)平均分配給兩臺處理機，K＝M/2。N臺處理機系統(tǒng)的基本模型要解決的問題：把M個任務(wù)分配給N臺處理機，求總處理時間的最小值。T=Rmax(Ki)+C/2ΣKi(MKi)與兩臺處理機的情況類似，實際的最小值發(fā)生在極端分配 情況下：或者將所有的任務(wù)集中在一臺處理機上，或者將任務(wù)平均分配給所有處理機。M不是N的整數(shù)倍，如何平均分配？？：例1：４個任務(wù)平均分給３臺處理機：例2： 11個任務(wù)平均分給５臺處理機：M個任務(wù)分配給N臺處理機的最佳分配方法： M是N的整數(shù)倍，平分 M是N的整數(shù)倍， 臺處理機， 每臺 個任務(wù)如果M/N≠0，則：另外有1臺處理機分得剩下的 個任務(wù)；剩下的 臺處理機不分配任何任務(wù)。例如：101個任務(wù)平均分給50臺處理機：有33臺處理機，每臺分給3個任務(wù)；另有１臺處理機分給２個任務(wù)；剩下的16臺處理機不分配任務(wù)。假設(shè)Ki 個任務(wù)分給了第ｉ臺處理機：第一項求出N臺處理機中最大執(zhí)行時間；第二項計算出Ki 與（M－Ki ）任務(wù)之間兩兩通信的開銷 時間，它是關(guān)于Ki 的二次函數(shù)。?Ki最多有3個取值： 、 和0?當(dāng)M 是N 的倍數(shù)時，?單臺處理機執(zhí)行全部M個任務(wù)的總時間：?總處理時間＝RM?使兩者差為0，得到R/C=M/2結(jié)論：?當(dāng)R/C＞M/2時采用平均分配方法， ?當(dāng)R/C＜M/2時采用集中分配方法。總結(jié)上面幾個模型，可以得出如下結(jié)論：(1)多處理機系統(tǒng)結(jié)構(gòu)所需的額外開銷，包括調(diào)度，對共享資源的競爭、同步、處理機之間通信等。(2)當(dāng)處理機臺數(shù)增加時，額外開銷時間也增加。有時，額外開銷的增加可能比處理機數(shù)目的線性增加更快。(3)R/C比值越大，越有利于計算過程。如果采用粗粒度，能夠獲得較大的R/C比值；但是并行程度將大為降低。 (4)為了使價格和性能都比較合理，處理機數(shù)目存在一個極大值，這個值主要依賴于機器的系統(tǒng)結(jié)構(gòu)、基本技術(shù)（尤其是通信技術(shù)）和具體的應(yīng)用問題。多處理機Cache間不一致的原因、兩種協(xié)議、監(jiān)聽協(xié)議的兩種方法、寫一次協(xié)議的內(nèi)容出現(xiàn)不一致性問題的原因有三個：共享可寫的數(shù)據(jù)、進(jìn)程遷移、I/O傳輸有兩類解決Cache不一致性問題的協(xié)議：在總線互連的多處理機系統(tǒng)中，通常采用監(jiān)聽協(xié)議。在其他多處理機系統(tǒng)中，通常采用基于目錄協(xié)議。使用監(jiān)聽協(xié)議，有兩種方法：方法一：寫無效（Write Invalidate）策略，在本地 Cache的數(shù)據(jù)塊修改時使遠(yuǎn)程數(shù)據(jù)塊都無效。方法二：寫更新（Write Update）策略，在本地Cache 數(shù)據(jù)塊修改時通過總線把新的數(shù)據(jù)塊廣播給含該塊的所 有其他Cache?采用寫無效或?qū)懜虏呗耘cCache采用寫回方式（Write Back）還是寫直達(dá)方式（Write Through）無關(guān)。?如果Cache采用寫直達(dá)方式，在使遠(yuǎn)程數(shù)據(jù)塊無效或更 新其他Cache的同時，還要同時修改共享存儲器中的內(nèi)容。由于寫更新策略在本地Cache修改時需要通過總線把 修改過的數(shù)據(jù)塊廣播給所有含該數(shù)據(jù)塊的其他 Cache，增加了總線的負(fù)擔(dān)。大部分多處理機系統(tǒng)使用寫無效策略。寫一次(WriteOnce)協(xié)議方法：第一次寫Cache采用寫直達(dá)方式，以后采用寫回方式。為了區(qū)分第一次寫，把“讀寫”狀態(tài)分為：保留 (Reserved)和重寫(Dirty)。共有4種狀態(tài)(1)有效(Valid, 相當(dāng)于寫回方式中的只讀：(2)無效(Invalid)：在Cache中找不到或數(shù)據(jù)塊已作 廢。(3)保留(Reserved)：數(shù)據(jù)從存儲器讀入Cache后只被 寫過一次，Cache和存儲器中都正確。(4)重寫(Dirty)：Cache中的數(shù)據(jù)塊被寫過多次，而 且是唯一正確的數(shù)據(jù)塊。整個系統(tǒng)中只有一份正確的拷貝。主要優(yōu)點：減少大量的無效操作，提高了總線效率。缺點：當(dāng)主存儲器的內(nèi)容無效時,讀缺失引起的總 線讀操作必須禁止訪問主存儲器，而大多數(shù)總線不支持這種操作
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1