【正文】 0＝101011。(3)最小的啟動(dòng)循環(huán)為 （1，7）和（3，5）,平均啟動(dòng)距離為4?？刂葡嚓P(guān)：因程序的執(zhí)行方向可能被改變而引起的相關(guān)，也稱為全局相關(guān)。（名詞解釋）有兩條或兩條以上能同時(shí)工作的指令流水線，超標(biāo)量處理機(jī)采用的是空間并行性。先行指令窗口的作用類似于先行指令緩沖棧，典型大小為2－8條指令。）超標(biāo)量超流水線處理機(jī)：一個(gè)時(shí)鐘周期發(fā)射m次，每次發(fā)射n條指令三種處理機(jī)的性能關(guān)系：超標(biāo)量處理機(jī)相對(duì)性能最高，其次超標(biāo)量超流水處理機(jī)，超流水線處理機(jī)的相對(duì)性能最低 多流水線的調(diào)度主要有三種方法：順序發(fā)射順序完成、順序發(fā)射亂序完成、亂序發(fā)射亂序完成 指令發(fā)射順序是按照程序中指令排列順序進(jìn)行的稱為順序發(fā)射。（1） 、使用該流水線執(zhí)行這個(gè)程序，并用流過(guò)延遲時(shí)間與其相等的一個(gè)等效非流水線處理機(jī)執(zhí)行同一程序。解：(1)等效非流水線處理機(jī)執(zhí)行一條指令需要5個(gè)時(shí)鐘周期，依照加速比的定義：S=n*k/(k+n1)=15000*5/(5+150001)=75000/15004=(2)流水線的效率：E=n*k/(k*(k+n1))=15000/15004=吞吐率：TP=n*f/(k+n1)=15000*25M/(k+n1)=一個(gè)5段流水線處理機(jī)的預(yù)約表如下：列出禁止向量和沖突向量畫(huà)出狀態(tài)轉(zhuǎn)移圖列出所有簡(jiǎn)單循環(huán)，指出最小啟動(dòng)循環(huán)及其啟動(dòng)距離計(jì)算該流水線的最大吞吐率指出最小恒定循環(huán)，計(jì)算相對(duì)應(yīng)的吞吐率解：(1)禁止向量（3，4，5），沖突向量（11100）(2)狀態(tài)轉(zhuǎn)移圖(3)簡(jiǎn)單循環(huán)(1,1,6),(),(6),(1,6),最小啟動(dòng)循環(huán)（1，1，6），(4)最大吞吐率:設(shè)該流水線時(shí)鐘周期為t，則Tp=3/8t(5)最小恒定循環(huán)為6，相對(duì)應(yīng)的吞吐率Tp=1/6t第七章（了解）特性：(1)網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù) (2)結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊數(shù)稱為結(jié)點(diǎn)度，進(jìn)入結(jié)點(diǎn)的邊數(shù)叫入度， 從結(jié)點(diǎn)出來(lái)的邊數(shù)則叫出度 (3)距離：兩個(gè)結(jié)點(diǎn)之間相連的最少邊數(shù) (4) 網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間距離的最大值。(3)飛行時(shí)間 (Time of flight)：第一位信息到達(dá)接收方所花費(fèi)的時(shí)間。(5)發(fā)送方開(kāi)銷 (Sender overhead)：處理器把消息放到互連網(wǎng)絡(luò)的時(shí)間。：1 靜態(tài)互連網(wǎng)絡(luò)2 循環(huán)互連網(wǎng)絡(luò)3 多級(jí)互連網(wǎng)絡(luò)4 全排列互連網(wǎng)絡(luò)5 全交叉開(kāi)關(guān)網(wǎng)絡(luò)（計(jì)算）書(shū)P395恒等置換I:輸入與輸出完全相同；交換置換E：第一位取反；方體置換C cube：Ci，弟i位取反；均勻洗牌置換S shuffle:循環(huán)左移1位；碟式置換B（butterfly）:最高位與最低位對(duì)調(diào)；位置顛倒置換R（reversal）:12344321?；ミB函數(shù)分別為：(1)Cube3(2)PM2+3(3)PM20(4)Shuffle(5)Butterfly (6)Reversal第12號(hào)處理機(jī)分別與哪一個(gè)處理機(jī)相連？解：(12)10下= (1100)2下1）1100最高位取反得0100，4號(hào)處理機(jī)2）(12 + 8) MOD 16 = 4，4號(hào)處理機(jī)3）12 –1 = 11，11號(hào)處理機(jī)4）1100循環(huán)左移1位得到1001, 9號(hào)處理機(jī)5）1100的最高最低位交換0101, 5號(hào)處理機(jī)6）1100的位序反過(guò)來(lái)為0011, 3號(hào)處理機(jī) 習(xí)題1： 有編號(hào)為0－31共32個(gè)處理機(jī)，分別計(jì)算下列互連函數(shù)（E：交換函數(shù)；S：混洗函數(shù)；B：蝶式函數(shù)；PM2I：移數(shù)函數(shù)；自變量為10進(jìn)制處理機(jī)編號(hào)）。(2)并發(fā)性并行Concurrency：兩個(gè)或兩個(gè)以上事件在 同一時(shí)間間隔內(nèi)發(fā)生。(2)時(shí)間重疊：流水線(3)資源共享：分時(shí)系統(tǒng)，分布式系統(tǒng)并行處理機(jī)（SMID）的定義：多個(gè)處理部件PU按照一定方式互連，在同一個(gè)控 制部件CU控制下，對(duì)各自的數(shù)據(jù)完成同一條指令規(guī)定 的操作。并行處理機(jī)也稱為陣列處理機(jī)，按照按照佛林分類法，它屬于SIMD處理機(jī)。多處理機(jī)系統(tǒng)的特點(diǎn)1. 結(jié)構(gòu)靈活并行處理機(jī)：專用，PE數(shù)多，固定有限通信多處理機(jī)： 通用，PE數(shù)少，高速靈活通信2. 程序并行性并行處理機(jī)的并行性存在于指令內(nèi)部，識(shí)別比較容易。一個(gè)簡(jiǎn)單的例子：Y = A+B*C*D/E+F，用兩個(gè)處理機(jī)計(jì)算：CPU1：B*C， A+F， A+B*C*D/E+FCPU2：D/E， B*C*D/E，3. 并行任務(wù)派生并行處理機(jī)把同種操作集中，由指令直接啟動(dòng)各PE同時(shí)工 作。如果沒(méi)有空閑處理機(jī)，任務(wù)進(jìn)入排隊(duì)器等待。多處理機(jī)中，各處理機(jī)執(zhí)行不同的指令，工作進(jìn)度不會(huì)也 不必保持相同。有數(shù)據(jù)相關(guān)和控制 相關(guān)也要停下等待。多處理機(jī)執(zhí)行并發(fā)任務(wù)，需用處理機(jī)的數(shù)目不固定， 各處理機(jī)進(jìn)出任務(wù)的時(shí)刻不相同，所需共享資源的品 種、數(shù)量隨時(shí)變化。粗粒度并行：R/C大，通信開(kāi)銷小,并行性高。假設(shè)：每個(gè)任務(wù)的執(zhí)行時(shí)間R；不在同一個(gè)處理機(jī)上的兩個(gè)任務(wù)需要相互通訊，每 次通訊時(shí)間為C。通信時(shí)間C(MK)K是一個(gè)開(kāi)口向下的二次函數(shù)，任務(wù)執(zhí)行時(shí)間是兩根相交的直線，最小值發(fā)生在中間即 K=M/2令：通訊時(shí)間＝執(zhí)行時(shí)間則 R*M/2=C*M/2*(MM/2)則 R/C=M/2當(dāng)通信時(shí)間比較大時(shí)(R/CM/2)，總時(shí)間的最小值發(fā)生在兩個(gè) 端點(diǎn)(K=0 K=M)；當(dāng)通信時(shí)間比較小時(shí)(R/CM/2)，總時(shí)間的最小值發(fā)生在中點(diǎn) (K=M/2)。N臺(tái)處理機(jī)系統(tǒng)的基本模型要解決的問(wèn)題：把M個(gè)任務(wù)分配給N臺(tái)處理機(jī)，求總處理時(shí)間的最小值。M不是N的整數(shù)倍，如何平均分配？？：例1：４個(gè)任務(wù)平均分給３臺(tái)處理機(jī)：例2： 11個(gè)任務(wù)平均分給５臺(tái)處理機(jī)：M個(gè)任務(wù)分配給N臺(tái)處理機(jī)的最佳分配方法： M是N的整數(shù)倍，平分 M是N的整數(shù)倍， 臺(tái)處理機(jī)， 每臺(tái) 個(gè)任務(wù)如果M/N≠0，則：另外有1臺(tái)處理機(jī)分得剩下的 個(gè)任務(wù)；剩下的 臺(tái)處理機(jī)不分配任何任務(wù)。假設(shè)Ki 個(gè)任務(wù)分給了第ｉ臺(tái)處理機(jī)：第一項(xiàng)求出N臺(tái)處理機(jī)中最大執(zhí)行時(shí)間；第二項(xiàng)計(jì)算出Ki 與（M－Ki ）任務(wù)之間兩兩通信的開(kāi)銷 時(shí)間，它是關(guān)于Ki 的二次函數(shù)?？偨Y(jié)上面幾個(gè)模型，可以得出如下結(jié)論：(1)多處理機(jī)系統(tǒng)結(jié)構(gòu)所需的額外開(kāi)銷，包括調(diào)度，對(duì)共享資源的競(jìng)爭(zhēng)、同步、處理機(jī)之間通信等。有時(shí)，額外開(kāi)銷的增加可能比處理機(jī)數(shù)目的線性增加更快。如果采用粗粒度，能夠獲得較大的R/C比值；但是并行程度將大為降低。多處理機(jī)Cache間不一致的原因、兩種協(xié)議、監(jiān)聽(tīng)協(xié)議的兩種方法、寫(xiě)一次協(xié)議的內(nèi)容出現(xiàn)不一致性問(wèn)題的原因有三個(gè)：共享可寫(xiě)的數(shù)據(jù)、進(jìn)程遷移、I/O傳輸有兩類解決Cache不一致性問(wèn)題的協(xié)議：在總線互連的多處理機(jī)系統(tǒng)中，通常采用監(jiān)聽(tīng)協(xié)議。使用監(jiān)聽(tīng)協(xié)議，有兩種方法：方法一：寫(xiě)無(wú)效（Write Invalidate）策略，在本地 Cache的數(shù)據(jù)塊修改時(shí)使遠(yuǎn)程數(shù)據(jù)塊都無(wú)效。?如果Cache采用寫(xiě)直達(dá)方式，在使遠(yuǎn)程數(shù)據(jù)塊無(wú)效或更 新其他Cache的同時(shí)，還要同時(shí)修改共享存儲(chǔ)器中的內(nèi)容。大部分多處理機(jī)系統(tǒng)使用寫(xiě)無(wú)效策略。為了區(qū)分第一次寫(xiě)，把“讀寫(xiě)”狀態(tài)分為：保留 (Reserved)和重寫(xiě)(Dirty)。(3)保留(Reserved)：數(shù)據(jù)從存儲(chǔ)器讀入Cache后只被 寫(xiě)過(guò)一次，Cache和存儲(chǔ)器中都正確。整個(gè)系統(tǒng)中只有一份正確的拷貝。缺點(diǎn)：當(dāng)主存儲(chǔ)器的內(nèi)容無(wú)效時(shí),讀缺失引起的總 線讀操作必須禁止訪問(wèn)主存儲(chǔ)器，而大多數(shù)總線不支持這種