體系結(jié)構(gòu)大題

Amdahl定律加快某部件執(zhí)行速度所能獲得的系統(tǒng)性能加速比，受限于該部件的執(zhí)行時(shí)間占系統(tǒng)中總執(zhí)行時(shí)間的百分比。系統(tǒng)性能加速比：加速比＝系統(tǒng)性能改進(jìn)后系統(tǒng)性能改進(jìn)前總執(zhí)行時(shí)間改進(jìn)前總執(zhí)行時(shí)間改進(jìn)后＝加速比依賴于兩個(gè)因素可改進(jìn)比例（Fe）：在改進(jìn)前的系統(tǒng)中，可改進(jìn)部分的執(zhí)行時(shí)間在總的執(zhí)行時(shí)間中所占的比例。它總是小于等于1。例如：一個(gè)需運(yùn)行60秒的程序中有20秒的運(yùn)算可以加速，那么這個(gè)比例就是20/60。部件加速比（Se）：可改進(jìn)部分改進(jìn)以后性能提高的倍數(shù)。它是改進(jìn)前所需的執(zhí)行時(shí)間與改進(jìn)后執(zhí)行時(shí)間的比。一般情況下部件加速比是大于1的。例如：若系統(tǒng)改進(jìn)后，可改進(jìn)部分的執(zhí)行時(shí)間是2秒，而改進(jìn)前其執(zhí)行時(shí)間為5秒，則部件加速比為5/2。

例1.1將計(jì)算機(jī)系統(tǒng)中某一功能的處理速度加快15倍，但該功能的處理時(shí)間僅占整個(gè)系統(tǒng)運(yùn)行時(shí)間的40%，則采用此增強(qiáng)功能方法后，能使整個(gè)系統(tǒng)的性能提高多少？解由題可知：Fe=40%=0.4Se=15根據(jù)Amdahl定律可知：

采用此增強(qiáng)功能方法后，能使整個(gè)系統(tǒng)的性能提高到原來(lái)的1.6倍。改進(jìn)后程序的總執(zhí)行時(shí)間TnT0：改進(jìn)前整個(gè)程序的執(zhí)行時(shí)間1－Fe：不可改進(jìn)比例

系統(tǒng)加速比Sn為改進(jìn)前與改進(jìn)后總執(zhí)行時(shí)間之比:例1.2某計(jì)算機(jī)系統(tǒng)采用浮點(diǎn)運(yùn)算部件后，使浮點(diǎn)運(yùn)算速度提高到原來(lái)的25倍，而系統(tǒng)運(yùn)行某一程序的整體性能提高到原來(lái)的4倍，試計(jì)算該程序中浮點(diǎn)操作所占的比例。解由題可知：Se=25Sn=4根據(jù)Amdahl定律可知：

由此可得：Fe

=78.1%即程序中浮點(diǎn)操作所占的比例為78.1%。Amdahl定律：一種性能改進(jìn)的遞減規(guī)則如果僅僅對(duì)計(jì)算任務(wù)中的一部分做性能改進(jìn)，則改進(jìn)得越多，所得到的總體性能的提升就越有限。重要推論：如果只針對(duì)整個(gè)任務(wù)的一部分進(jìn)行改進(jìn)和優(yōu)化，那么所獲得的加速比不超過(guò)：1/（1－可改進(jìn)比例）哈夫曼編碼基本思想：當(dāng)各種事件發(fā)生的概率不均等時(shí)，可以對(duì)發(fā)生概率最高的事件用最短的位數(shù)（時(shí)間）來(lái)表示（處理），而對(duì)于出現(xiàn)概率較低的事件，則可以用較長(zhǎng)的位數(shù)（時(shí)間）來(lái)表示（處理），從而使總的平均位數(shù)（時(shí)間）縮短。構(gòu)造哈夫曼樹(shù)的方法將各事件按其使用頻度從小到大依次排列；每次從中選擇兩個(gè)頻度值最小的結(jié)點(diǎn)，將其合并成一個(gè)新的結(jié)點(diǎn)，并把新結(jié)點(diǎn)畫(huà)在所選結(jié)點(diǎn)的上面，然后用兩條邊把新結(jié)點(diǎn)分別與那兩個(gè)結(jié)點(diǎn)相連。新結(jié)點(diǎn)的頻度值是所選兩個(gè)結(jié)點(diǎn)的頻度值的和。把新結(jié)點(diǎn)與其他剩余未結(jié)合的結(jié)點(diǎn)一起，再以上面的步驟進(jìn)行處理，反復(fù)進(jìn)行，直到全部結(jié)點(diǎn)都結(jié)合完畢、形成根結(jié)點(diǎn)為止。操作碼優(yōu)化的程度可以用信息熵來(lái)衡量。表示用二進(jìn)制編碼表示n個(gè)碼點(diǎn)時(shí)，理論上的最短平均編碼長(zhǎng)度。例2.1假設(shè)某模型機(jī)有7條指令，這些指令的使用頻度如表左邊所示。(1)計(jì)算這7條指令的操作碼編碼的最短平均碼長(zhǎng)；(2)畫(huà)出哈夫曼樹(shù)，寫(xiě)出這7條指令的哈夫曼編碼，并計(jì)算該編碼的平均碼長(zhǎng)和信息冗余量。2.3指令系統(tǒng)的設(shè)計(jì)與優(yōu)化指令頻度pi

操作碼使用哈夫曼編碼操作碼長(zhǎng)度li

利用哈夫曼概念的擴(kuò)展操作碼操作碼長(zhǎng)度li

I1

0.4001002I2

0.30102012I3

0.151103102I4

0.0511100511004I5

0.0411101511014I6

0.0311110511104I70.03111115111142.3指令系統(tǒng)的設(shè)計(jì)與優(yōu)化

解（1）（2）其哈夫曼樹(shù)如圖所示，該樹(shù)的每個(gè)葉結(jié)點(diǎn)分別對(duì)應(yīng)于一條指令。在該樹(shù)中，對(duì)每個(gè)結(jié)點(diǎn)向下的兩個(gè)分支，分別用二進(jìn)制“1”和“0”來(lái)表示。從該哈夫曼樹(shù)可以很容易地寫(xiě)出哈夫曼編碼。

具體方法：對(duì)于任意一條指令I(lǐng)i

（i=1，2，…，7），從哈夫曼樹(shù)根結(jié)點(diǎn)出發(fā)、沿一條路徑連接到葉結(jié)點(diǎn)Ii，把途中所經(jīng)過(guò)的各分支的“0”和“1”按從左到右的順序記錄下來(lái)，便是該指令的哈夫曼編碼。上表中列出了所有指令的哈夫曼編碼。哈夫曼樹(shù)舉例2.3指令系統(tǒng)的設(shè)計(jì)與優(yōu)化該哈夫曼編碼的平均碼長(zhǎng)是：其信息冗余量為3.2流水線的性能指標(biāo)例3.1設(shè)在下圖所示的靜態(tài)流水線上計(jì)算：

流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中，試計(jì)算其吞吐率、加速比和效率。3.2.4流水線的性能分析舉例(每段的時(shí)間都為△t)3.2流水線的性能指標(biāo)解：（1）選擇適合于流水線工作的算法先計(jì)算A1+B1、A2+B2、A3+B3和A4+B4；再計(jì)算(A1+B1)×(A2+B2)和(A3+B3)×(A4+B4)；然后求總的乘積結(jié)果。（2）畫(huà)出時(shí)空?qǐng)D3.2流水線的性能指標(biāo)在18個(gè)△t時(shí)間中，給出了7個(gè)結(jié)果。吞吐率為：

不用流水線，由于一次求和需6△t，一次求積需4△t，則產(chǎn)生上述7個(gè)結(jié)果共需（4×6+3×4）△t=36△t

加速比為：（3）計(jì)算性能3.2流水線的性能指標(biāo)

流水線的效率可以看出，在求解此問(wèn)題時(shí)，該流水線的效率不高。

(原因)3.2流水線的性能指標(biāo)主要原因多功能流水線在做某一種運(yùn)算時(shí)，總有一些段是空閑的；靜態(tài)流水線在進(jìn)行功能切換時(shí)，要等前一種運(yùn)算全部流出流水線后才能進(jìn)行后面的運(yùn)算；運(yùn)算之間存在關(guān)聯(lián)，后面有些運(yùn)算要用到前面運(yùn)算的結(jié)果；流水線的工作過(guò)程有建立與排空部分。3.2流水線的性能指標(biāo)例3.2有一條動(dòng)態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第4段的時(shí)間為2△t，其余各段時(shí)間均為△t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中。若在該流水線上計(jì)算:

試計(jì)算其吞吐率、加速比和效率。3.2流水線的性能指標(biāo)解:(1)選擇適合于流水線工作的算法應(yīng)先計(jì)算A1×B1、A2×B2、A3×B3和A4×B4；再計(jì)算(A1×B1)＋(A2×B2)(A3×B3)＋(A4×B4)；然后求總的累加結(jié)果。(2)畫(huà)出時(shí)空?qǐng)D(3)計(jì)算性能3.2流水線的性能指標(biāo)3.2流水線的性能指標(biāo)

下面我們?cè)倏匆粋€(gè)例子：

例在靜態(tài)流水線上計(jì)算:

求：吞吐率，加速比，效率。解：(1)確定適合于流水處理的計(jì)算過(guò)程(2)畫(huà)時(shí)空?qǐng)D(3)計(jì)算性能

吞吐率TP＝7／(20△t)

加速比S＝(34△t)／(20△t)＝1.7效率E＝(4×4＋3×6)／(8×20)＝0.213.2流水線的性能指標(biāo)3.2流水線的性能指標(biāo)可以看出，在求解此問(wèn)題時(shí)，該流水線的效率不高。動(dòng)態(tài)流水線的時(shí)－空?qǐng)D舉例Ⅰ舉例Ⅱ:

這樣行不行？

正確答案在非線性流水線中，存在反饋回路，當(dāng)一個(gè)任務(wù)在流水線中流過(guò)時(shí)，可能要多次經(jīng)過(guò)某些段。流水線調(diào)度要解決的問(wèn)題：

應(yīng)按什么樣的時(shí)間間隔向流水線輸入新任務(wù)，才能既不發(fā)生功能段使用沖突，又能使流水線有較高的吞吐率和效率？3.3非線性流水線的調(diào)度向一條非線性流水線的輸入端連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔稱為非線性流水線的啟動(dòng)距離。會(huì)引起非線性流水線功能段使用沖突的啟動(dòng)距離則稱為禁用啟動(dòng)距離。啟動(dòng)距離和禁用啟動(dòng)距離一般都用時(shí)鐘周期數(shù)來(lái)表示，是一個(gè)正整數(shù)。預(yù)約表橫向（向右）：時(shí)間（一般用時(shí)鐘周期表示）縱向（向下）：流水線的段3.3.1單功能非線性流水線的最優(yōu)調(diào)度例：一個(gè)5功能段非線性流水線預(yù)約表

如果在第n個(gè)時(shí)鐘周期使用第k段，則在第k行和第n列的交叉處的格子里有一個(gè)√。如果在第k行和第n列的交叉處的格子里有一個(gè)√，則表示在第n個(gè)時(shí)鐘周期要使用第k段。

根據(jù)預(yù)約表寫(xiě)出禁止表F禁止表F：一個(gè)由禁用啟動(dòng)距離構(gòu)成的集合。

具體方法對(duì)于預(yù)約表的每一行的任何一對(duì)√，用它們所在的列號(hào)相減（大的減小的），列出各種可能的差值，然后刪除相同的，剩下的就是禁止表的元素。在上例中第一行的差值只有一個(gè)：8；第二行的差值有3個(gè)：1，5，6；第3行只有一個(gè)√，沒(méi)有差值；第4和第5行的差值都只有一個(gè)：1；其禁止表是：F={1，5，6，8}根據(jù)禁止表F寫(xiě)出初始沖突向量C0（進(jìn)行從一個(gè)集合到一個(gè)二進(jìn)制位串的變換）沖突向量C：一個(gè)N位的二進(jìn)制位串。設(shè)C0=（cNcN-1…ci…c2c1），則：ci=0：允許間隔i個(gè)時(shí)鐘周期后送入后續(xù)任務(wù)ci=1：不允許間隔i個(gè)時(shí)鐘周期后送入后續(xù)任務(wù)對(duì)于上面的例子F={1，5，6，8}

C0=（10110001）

根據(jù)初始沖突向量C0畫(huà)出狀態(tài)轉(zhuǎn)換圖當(dāng)?shù)谝粋€(gè)任務(wù)流入流水線后，初始沖突向量C0決定了下一個(gè)任務(wù)需間隔多少個(gè)時(shí)鐘周期才可以流入。在第二個(gè)任務(wù)流入后，新的沖突向量是怎樣的呢？假設(shè)第二個(gè)任務(wù)是在與第一個(gè)任務(wù)間隔j個(gè)時(shí)鐘周期流入，這時(shí)，由于第一個(gè)任務(wù)已經(jīng)在流水線中前進(jìn)了j個(gè)時(shí)鐘周期，其相應(yīng)的禁止表中各元素的值都應(yīng)該減去j，并丟棄小于等于0的值。對(duì)沖突向量來(lái)說(shuō)，就是邏輯右移j位（左邊補(bǔ)0）。

在沖突向量上，就是對(duì)它們的沖突向量進(jìn)行“或”運(yùn)算。SHR(j)（C0）∨C0其中:SHR(j)表示邏輯右移j位推廣到更一般的情況假設(shè):Ck：當(dāng)前的沖突向量j:允許的時(shí)間間隔則新的沖突向量為：SHR(j)（Ck）∨C0對(duì)于所有允許的時(shí)間間隔都按上述步驟求出其新的沖突向量，并且把新的沖突向量作為當(dāng)前沖突向量，反復(fù)使用上述步驟，直到不再產(chǎn)生新的沖突向量為止。從初始沖突向量C0出發(fā)，反復(fù)應(yīng)用上述步驟，可以求得所有的沖突向量以及產(chǎn)生這些向量所對(duì)應(yīng)的時(shí)間間隔。由此可以畫(huà)出用沖突向量表示的流水線狀態(tài)轉(zhuǎn)移圖。有向?。罕硎緺顟B(tài)轉(zhuǎn)移的方向弧上的數(shù)字：表示引入后續(xù)任務(wù)（從而產(chǎn)生新的沖突向量）所用的時(shí)間間隔（時(shí)鐘周期數(shù)）對(duì)于上面的例子（1）C0=（10110001）引入后續(xù)任務(wù)可用的時(shí)間間隔為：2、3、4、7個(gè)時(shí)鐘周期如果采用2，則新的沖突向量為：

（00101100）∨（10110001）=（10111101）如果采用3，則新的沖突向量為：

（00010110）∨（10110001）=（10110111）如果采用4，則新的沖突向量為：

（00001011）∨（10110001）=（10111011）如果采用7，則新的沖突向量為：

（00000001）∨（10110001）=（10110001）（2）對(duì)于新向量（10111101），其可用的時(shí)間間隔為2個(gè)和7個(gè)時(shí)鐘周期。用類似上面的方法，可以求出其后續(xù)的沖突向量分別為

（10111101）和（10110001）。（3）對(duì)于其他新向量，也照此處理。（4）在此基礎(chǔ)上，畫(huà)出狀態(tài)轉(zhuǎn)移示意圖。根據(jù)狀態(tài)轉(zhuǎn)換圖寫(xiě)出最優(yōu)調(diào)度方案根據(jù)流水線狀態(tài)圖，由初始狀態(tài)出發(fā)，任何一個(gè)閉合回路即為一種調(diào)度方案。列出所有可能的調(diào)度方案，計(jì)算出每種方案的平均時(shí)間間隔，從中找出其最小者即為最優(yōu)調(diào)度方案。上例中，各種調(diào)度方案及其平均間隔時(shí)間。最佳方案：（3，4）平均間隔時(shí)間：3.5個(gè)時(shí)鐘周期（吞吐率最高）方案（4，3）的平均間隔時(shí)間也是3.5，但它不是最佳方案，為什么？調(diào)度策略平均延遲拍數(shù)(2,7)(2,2,7)(3,7)(3,4)(3,4,3,7)(3,4,7)(4,3,7)(4,7)（7）4.53.6753.54.254.674.675.57各種調(diào)度策略及平均延遲拍數(shù)

方案（3，4）是一種不等時(shí)間間隔的調(diào)度方案，與等間隔的調(diào)度方案相比，在控制上要復(fù)雜得多。為了簡(jiǎn)化控制，也可以采用等間隔時(shí)間的調(diào)度方案，但吞吐率和效率往往會(huì)下降不少。在上述例子中，等時(shí)間間隔的方案只有一個(gè)：（7），其吞吐率下降了一半。8.5通道處理機(jī)通道流量一個(gè)通道在數(shù)據(jù)傳送期間，單位時(shí)間內(nèi)能夠傳送的數(shù)據(jù)量。所用單位一般為B/s。又稱為通道吞吐率、通道數(shù)據(jù)傳輸率等。通道最大流量

一個(gè)通道在滿負(fù)荷工作狀態(tài)下的流量。8.5.4通道流量分析8.5通道處理機(jī)參數(shù)的定義TS：設(shè)備選擇時(shí)間。從通道響應(yīng)設(shè)備發(fā)出的數(shù)據(jù)傳送請(qǐng)求開(kāi)始，到通道實(shí)際為這臺(tái)設(shè)備傳送數(shù)據(jù)所需要的時(shí)間。