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

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

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

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

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

由此可得：Fe

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

操作碼使用哈夫曼編碼操作碼長度li

利用哈夫曼概念的擴展操作碼操作碼長度li

I1

0.4001002I2

0.30102012I3

0.151103102I4

0.0511100511004I5

0.0411101511014I6

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

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

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

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

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

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

加速比為：（3）計算性能3.2流水線的性能指標

流水線的效率可以看出，在求解此問題時，該流水線的效率不高。

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

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

下面我們再看一個例子：

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

求：吞吐率，加速比，效率。解：(1)確定適合于流水處理的計算過程(2)畫時空圖(3)計算性能

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

加速比S＝(34△t)／(20△t)＝1.7效率E＝(4×4＋3×6)／(8×20)＝0.213.2流水線的性能指標3.2流水線的性能指標可以看出，在求解此問題時，該流水線的效率不高。動態(tài)流水線的時－空圖舉例Ⅰ舉例Ⅱ:

這樣行不行？

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

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

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

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

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

C0=（10110001）

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

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

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

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

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

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

（10111101）和（10110001）。（3）對于其他新向量，也照此處理。（4）在此基礎(chǔ)上，畫出狀態(tài)轉(zhuǎn)移示意圖。根據(jù)狀態(tài)轉(zhuǎn)換圖寫出最優(yōu)調(diào)度方案根據(jù)流水線狀態(tài)圖，由初始狀態(tài)出發(fā)，任何一個閉合回路即為一種調(diào)度方案。列出所有可能的調(diào)度方案，計算出每種方案的平均時間間隔，從中找出其最小者即為最優(yōu)調(diào)度方案。上例中，各種調(diào)度方案及其平均間隔時間。最佳方案：（3，4）平均間隔時間：3.5個時鐘周期（吞吐率最高）方案（4，3）的平均間隔時間也是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）是一種不等時間間隔的調(diào)度方案，與等間隔的調(diào)度方案相比，在控制上要復雜得多。為了簡化控制，也可以采用等間隔時間的調(diào)度方案，但吞吐率和效率往往會下降不少。在上述例子中，等時間間隔的方案只有一個：（7），其吞吐率下降了一半。8.5通道處理機通道流量一個通道在數(shù)據(jù)傳送期間，單位時間內(nèi)能夠傳送的數(shù)據(jù)量。所用單位一般為B/s。又稱為通道吞吐率、通道數(shù)據(jù)傳輸率等。通道最大流量

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