計算機(jī)系統(tǒng)結(jié)構(gòu)第7章-多處理機(jī)(編輯修改稿)
2024-09-12 01:40 本頁面
【文章內(nèi)容簡介】 點(diǎn)都是一個交叉點(diǎn)。每個節(jié)點(diǎn)可以處于打開和關(guān)閉狀態(tài)。 ? 交叉開關(guān)網(wǎng)絡(luò)是一種無阻塞的網(wǎng)絡(luò)， CPU不會因?yàn)槟承┙徊纥c(diǎn)或者線路被占用無法與內(nèi)存模塊建立連接（假設(shè)內(nèi)存模塊是可用的）。而且，建立連接時不需要事先規(guī)劃。即使已經(jīng)建立了多個任意的連接，仍然有可能在剩下的 CPU和剩下的內(nèi)存之間建立連接 ? 交叉網(wǎng)絡(luò)的缺點(diǎn)是節(jié)點(diǎn)需要 n2個，當(dāng)節(jié)點(diǎn)數(shù)量比較大（ n1000）時候不可能實(shí)現(xiàn)的。 3. 多級互連網(wǎng)絡(luò) 為了實(shí)現(xiàn)任意處理機(jī)間的互連，引入了多級互連網(wǎng)絡(luò)的概念。所謂多級互連網(wǎng)絡(luò)，就是指由多級開關(guān)按照一定的方式進(jìn)行互連，組合而成的一個復(fù)雜的網(wǎng)絡(luò)系統(tǒng) 級 1 級 2 級 N開 關(guān)開 關(guān)開 關(guān)…級 間互 連 1開 關(guān)開 關(guān)開 關(guān)…級 間互 連 2?開 關(guān)開 關(guān)開 關(guān)…級 間互 連N 1 決定多級互連網(wǎng)絡(luò)特性的主要因素有三個方面：交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式。 ? 交換開關(guān)是組成互連網(wǎng)絡(luò)的基本單元。通常一個a b交換開關(guān)代表有 a個輸入和 b個輸出。每個輸入可與一個或多個輸出相連。最常用的是二元開關(guān)，具有直通和交換功能。四元開關(guān)則在此基礎(chǔ)上，增加了上播和下播功能。 ? 拓?fù)浣Y(jié)構(gòu)指前一級交換開關(guān)的輸出端與后一級交換開關(guān)的輸入端之間的連接模式。通常，可以采用互連函數(shù)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)。 ? 控制方式是對各個交換開關(guān)進(jìn)行控制，通常分如下三種控制方式：級控制，即同一級交換開關(guān)通過同一個控制信號控制；單元控制，即對每個交換開關(guān)進(jìn)行單獨(dú)控制；部分級控制，對不同的級采用不同數(shù)量的控制信號。例如，第 i級使用 i＋ 1個控制信號控制（ 0≤i≤n— 1）。顯然，部分級控制是前兩種方式的折中。 同一個多級網(wǎng)絡(luò)分別采用不用的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò) 多級互連網(wǎng)絡(luò)實(shí)例 多級立方體網(wǎng)絡(luò)通常是由三種互連函數(shù)的 3個 單級立方體網(wǎng)串接起來形成的，它的開關(guān)全部采 用二功能開關(guān)。對一個 N N的 n級立方體網(wǎng)絡(luò)， 其級數(shù) n＝㏒ 2N，每級有 N/2個開關(guān)，全部開關(guān) 數(shù)為 nN/2。采用交換函數(shù)構(gòu)成拓?fù)浣Y(jié)構(gòu)，各級分 別采用 E0、 E …En 交換函數(shù)。當(dāng)所有開關(guān)都 直通時，實(shí)現(xiàn)恒等變換。 采用三種不同的控制方式，可以構(gòu)成三種不同 的互連網(wǎng)絡(luò)：采用級控制可以構(gòu)成 STARAN交換 網(wǎng)；采用部分級控制，可以構(gòu)成 STARAN移數(shù) 網(wǎng)；采用單元控制可以構(gòu)成間接二進(jìn)制 n方體網(wǎng)。 以 N=8為例， n＝㏒ 2N＝ 3，即分三級，開關(guān)總數(shù)為 3 8/2＝ 12個，如圖 714所示。當(dāng)采用級控方式時，具有交換功能。例如當(dāng) 0— 2三級級控信號為 101時，即第 0級和第 2級中所有開關(guān)狀態(tài)處于交換狀態(tài)，第 1級中開關(guān)處于直通狀態(tài)，輸入和輸出的對應(yīng)關(guān)系為 05,14,27,36,41,50,63,72。對于其它幾種級控信號，也將會形成不同的輸入和輸出的交換連接。當(dāng)采用部分級控時，網(wǎng)絡(luò)實(shí)現(xiàn)移位功能。比如第 0級用級控信號“ 0”，第 1級中的開關(guān)均使用部分級控信號“ 1”，第 2級中的開關(guān) I、 J信號用信號“ 1”，開關(guān) K、 L用信號“ 0”，則實(shí)現(xiàn)移 2（ mod 8）的功能。當(dāng)采用單元控制時，對各個開關(guān)進(jìn)行單獨(dú)控制，可以實(shí)現(xiàn)包括交換置換、移數(shù)置換在內(nèi)的常用函數(shù)置換。 ABCDEFGHIJKL0123456701234567k = 0 k = 1 k = 2第三節(jié) 多處理機(jī)系統(tǒng)的系統(tǒng)控制 多處理機(jī)系統(tǒng)中，每臺處理機(jī)都能夠獨(dú)立執(zhí)行自己的程序和指令流，但是，一個進(jìn)程應(yīng)該分配到哪個處理機(jī)上運(yùn)行是由什么決定的呢，運(yùn)行不同進(jìn)程的處理機(jī)間又是怎樣進(jìn)行通信的呢？ 1. 多處理機(jī)系統(tǒng)的調(diào)度 調(diào)度算法的一般目標(biāo)是：使用最少的處理機(jī)、在最短的時間內(nèi)完成并行程序的執(zhí)行任務(wù) 下圖是 3個處理機(jī) P P P3上執(zhí)行 5個任務(wù) T1～ T5的任務(wù)時空圖，各個任務(wù)執(zhí)行時間分別為 、 2。結(jié)合該圖來說明關(guān)于任務(wù)調(diào)度的參數(shù) 0 1 65432 7P 1P 3P 2T 1 T 2T 2 T 1T 3 T 4 T 5（ 1）調(diào)度參數(shù) ? 任務(wù)流時間 完成任務(wù)所需要的時間定義為任務(wù)流時間，例如完成任務(wù) T1共需要 5+2 = 7 時間單位 ? 調(diào)度流時間 一個調(diào)度流時間是調(diào)度中所有任務(wù)流的時間。圖中的調(diào)度流時間 = T1流 +T2流 +T3流 +T4流+T5流時間 = 7++2+2+2 = (時間單位 )。 ? 平均流 平均流等于調(diào)度流時間除以任務(wù)數(shù)。最小平均流時間表示任務(wù)占用處理機(jī)與存儲器等資源的時間很短，不但使任務(wù)的機(jī)時費(fèi)用降低，還使系統(tǒng)有更充裕的時間處理其他任務(wù)。這樣，最少平均流時間就是系統(tǒng)吞吐率的一個間接度量參數(shù)。 ? 處理機(jī)的利用率 處理機(jī)的利用率等于該處理機(jī)上任務(wù)流之和除以最大有效時間單位 (本例為 )。 P P P3的利用率分別為 、 ，空閑的時間分別為 、 ，忙的時間分別為 、 、 。處理機(jī)平均利用率 = ++)/3 = 。 （ 2）調(diào)度算法模型 調(diào)度模型一般分為靜態(tài)的確定性模型和動態(tài)的隨機(jī)型模型 ? 靜態(tài)確定型模型 要求在求解問題前就已知每個任務(wù)執(zhí)行所需的時間以及系統(tǒng)中各任務(wù)間的關(guān)系。這種調(diào)度算法的設(shè)計比較簡單，但如果事先不能準(zhǔn)確估計每個任務(wù)的執(zhí)行時間及任務(wù)間的關(guān)系，該調(diào)度算法的效率就不高 ? 動態(tài)隨機(jī)型模型 在運(yùn)行過程中對資源進(jìn)行動態(tài)分配，一般用隨機(jī)分配方式或巡回方式，將當(dāng)前任務(wù)分配給空閑的處理機(jī)執(zhí)行 （ 3）常見調(diào)度策略 ? 輪轉(zhuǎn)法 ? 多級輪轉(zhuǎn)法 ? 組調(diào)法 ? 隨機(jī)函數(shù)法 2. 多處理機(jī)的進(jìn)程通信 多處理機(jī)進(jìn)程間通信一般是通過共享內(nèi)存的方式進(jìn)行通信。其中最關(guān)鍵的就是不同處理機(jī)之間 cache的不一致問題。由此引入 cache一致性協(xié)議 （ 1）監(jiān)聽協(xié)議 每個含有物理存儲器中數(shù)據(jù)塊副本的 Cache還要保留該數(shù)據(jù)塊共享狀態(tài)的副本，但是不集中地保存狀態(tài)。 Cache通?？梢酝ㄟ^廣播媒介（總線或交換機(jī)訪問），所有的 Cache控制器對總線進(jìn)行監(jiān)聽，來確定它們是否含有總線或交換機(jī)上請求的數(shù)據(jù)塊的副本。任何可以向所有處理器廣播 Cache缺失的通信媒介都可以用來實(shí)現(xiàn)基于監(jiān)聽的一致性。 ?寫無效協(xié)議 在執(zhí)行寫操作時使其它 cache副本無效，處理器寫數(shù)據(jù)項(xiàng)之前保證該處理機(jī)能獨(dú)占地訪問數(shù)據(jù)項(xiàng) 處理器活動 總線 活動 處理器 A的Cache內(nèi)容 處理器不 B的Cache內(nèi)容 存儲器 X位置Cache的內(nèi)容 0 處理器 A讀 X Cache 缺失于
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1