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