本科系統(tǒng)結(jié)構(gòu)課件 chapter2-3

§3指令系統(tǒng)的設(shè)計和優(yōu)化

指令系統(tǒng)是從程序設(shè)計者看到的機器的主要屬性，是軟、硬件的主要界面指令系統(tǒng)是計算機系統(tǒng)結(jié)構(gòu)的主要組成部分指令系統(tǒng)是軟件與硬件分界面的一個主要標志指令系統(tǒng)是軟件與硬件之間互相溝通的橋梁指令系統(tǒng)與軟件之間的語義差距越來越大指令系統(tǒng)的設(shè)計主要包括指令的功能（操作類型、具體操作內(nèi)容）和指令格式的設(shè)計.內(nèi)容指令系統(tǒng)設(shè)計的基本原則指令操作碼的優(yōu)化指令字格式的優(yōu)化

指令設(shè)計的步驟根據(jù)應(yīng)用，初擬出指令的分類和具體的指令；試編出用該指令系統(tǒng)設(shè)計的各種高級語言的編譯程序；對各種算法用哪些大量測試程序進行模擬測試，看指令系統(tǒng)的操作碼和尋址方式效能是否都比較高；將程序中高頻出現(xiàn)的指令串復(fù)合改成一條強功能新指令，即改用硬件方式實現(xiàn)；而將頻度很低的指令的操作改成基本的指令組成的指令串來完成，即用軟件方式實現(xiàn)；指令類型非特權(quán)型：主要供應(yīng)應(yīng)用程序員使用，也可供系統(tǒng)程序員使用，包括算術(shù)邏輯運算、數(shù)據(jù)傳送、浮點運算、字符串、十進制運算、控制轉(zhuǎn)移及系統(tǒng)控制等；特權(quán)型：系統(tǒng)程序員使用，用戶無權(quán)使用，有啟動I/O（多用戶環(huán)境下）、停機等待、存儲管理保護、控制系統(tǒng)狀態(tài)、診斷等；指令系統(tǒng)的設(shè)計設(shè)計的原則：如何支持編譯系統(tǒng)能高效、簡易地將源程序翻譯成目標代碼。規(guī)整性對稱性獨立性和全能性正交性可組合性可擴充性系統(tǒng)設(shè)計人員希望指令碼密度適中高密度指令：強功能符合指令優(yōu)點：減少程序長度、訪存次數(shù)、Cache、虛存訪問調(diào)度次數(shù)、程序運行時間；缺點：指令系統(tǒng)復(fù)雜，硬件實現(xiàn)困難；兼容性適應(yīng)性指令系統(tǒng)的設(shè)計包含的內(nèi)容指令的格式指令的類型操作功能操作數(shù)的訪問方式---尋址方式指令的組成一般的指令主要由兩部分組成：操作碼和地址碼操作碼主要包括兩部分內(nèi)容：操作種類：加、減、乘、除、數(shù)據(jù)傳送、移位、轉(zhuǎn)移、輸入輸出操作數(shù)描述數(shù)據(jù)的類型：定點數(shù)、浮點數(shù)、復(fù)數(shù)、字符、字符串、邏輯數(shù)、向量進位制：2進制、10進制、16進制數(shù)據(jù)字長：字、半字、雙字、字節(jié)地址碼通常包括三部分內(nèi)容：地址：直接地址、間接地址、立即數(shù)、寄存器編號、變址寄存器編號地址的附加信息：偏移量、塊長度、跳距尋址方式：直接尋址、間接尋址、立即數(shù)尋址、變址尋址、相對尋址、寄存器尋址指令設(shè)計要考慮的問題操作數(shù)的存儲形式存儲器CPU內(nèi)什么地方每條指令中顯式說明的操作數(shù)個數(shù)操作數(shù)的位置操作類型操作數(shù)的類型和長短指令格式的優(yōu)化

指令=操作碼+地址碼指令格式的優(yōu)化：如何用最短的位數(shù)來表示指令的操作信息和地址信息，使程序中指令的平均字長最短。主要目標：節(jié)省程序的存儲空間指令格式盡量規(guī)整，便于譯碼操作碼的優(yōu)化表示

操作碼的三種編碼方法：固定長度：規(guī)整性好，解碼簡單，空間大。Huffman編碼：空間小，規(guī)整性不好，解碼復(fù)雜。擴展編碼：折衷方案。固定長度4Huffman編碼2.12擴展編碼3.12信息源熵2.09改進操作碼編碼方式能夠節(jié)省程序存儲空間例如：Burroughs公司的B-1700機操作碼編碼方式整個操作系統(tǒng)所用指令的操作碼總位數(shù)改進的百分比8位定長編碼4-6-10擴展編碼Huffman編碼301,248184,966172,346039％43％哈夫曼（Huffman）壓縮當各種事件發(fā)生的概率不均等時，采用優(yōu)化技術(shù)對發(fā)生概率最高的事件用最短的位數(shù)（時間）來表示（處理），而對出現(xiàn)概率較低的允許用較長的位數(shù)（時間）來表示（處理），以達到平均位數(shù)減少的目的。用于代碼壓縮、程序壓縮、空間壓縮和時間壓縮

操作碼的優(yōu)化表示

信息源熵：信息源包含的平均信息量。

信息冗余量：

舉例

七條指令，頻度如下

I1I2I3I4I5I6I70.40.30.150.050.040.030.03

信息源熵H=2.17

信息冗余量=0.28=28%1.000.600.300.150.060.030.030.040.050.150.300.400.0911111100000(11111)(11110)(11101)(11100)(110)(10)(0)I7I6I1I2I3I4I50擴展編碼

Huffman操作碼的主要缺點：操作碼長度很不規(guī)整，硬件譯碼困難與地址碼共同組成固定長的指令比較困難擴展編碼法：由固定長操作碼與Huffman編碼法相結(jié)合形成減少平均長度方便譯碼上例：Huffman用四種長度

0，10，110，11100，11101，11110，11111I1、I2、I3用兩位：00、01、10I4、I5、I6、I7用四位：

1100、1101、1110、1111

平均碼長=2.30

信息冗余量=0.0565=5.65%Huffman編碼方法

寫出每個事件出現(xiàn)頻度找出兩個時間出現(xiàn)頻度最低的數(shù)字，相加形成新的頻度重復(fù)（2），直到出現(xiàn)頻度為1，建立Huffman樹確定Huffman代碼表

說明目的：平均碼長減少。Huffma代碼不唯一0，1對換合并次序

假設(shè)一臺模型計算機共有7種不同的操作碼，如果采用固定長操作碼需要3位。已知各種操作碼在程序中出現(xiàn)的概率如下表，計算采用Huffman編碼法的操作碼平均長度，并計算固定長操作碼和Huffman操作碼的信息冗余量。

利用Huffman樹進行操作碼編碼的方法，又稱為最小概率合并法。指令I(lǐng)1概率0.45I20.30I30.15I40.05I50.03I60.01I70.01舉例1把所有指令按照操作碼在程序中出現(xiàn)的概率，自左向右從排列好。選取兩個概率最小的結(jié)點合并成一個概率值是二者之和的新結(jié)點，并把這個新結(jié)點與其它還沒有合并的結(jié)點一起形成新結(jié)點集合。在新結(jié)點集合中選取兩個概率最小的結(jié)點進行合并，如此繼續(xù)進行下去，直至全部結(jié)點合并完畢。最后得到的根結(jié)點的概率值為1。每個結(jié)點都有兩個分支，分別用一位代碼“0”

和“1”表示。從根結(jié)點開始，沿尖頭所指方向，到達屬于該指令的概率結(jié)點，把沿線所經(jīng)過的代碼組合起來得到這條指令的操作碼編碼。解：采用Huffman編碼法所得到的操作碼的平均長度

＝0.45×1＋0.30×2＋0.15×3＋0.05×4

＋0.03×5＋0.01×6＋0.01×6＝1.97（位）熵H＝0.45×1.152＋0.30×1.737＋0.15×2.737

＋0.05×4.322＋0.03×5.059＋0.01×6.644

＋0.01×6.644＝1.95（位）0.450.300.150.050.030.010.011.000.550.250.100.050.02010101010101指令序號概率Huffman編碼法操作碼長度I10.4501位I20.30102位I30.151103位I40.0511104位I50.03111105位I60.011111106位I70.0111111116位采用3位固定長操作碼的信息冗余量為： 例如：把上例改為1-2-3-5擴展編碼法，其操作碼最短平均長度為：

H = 0.45×1＋0.30×2＋0.15×3＋

(0.05＋0.03＋0.01＋0.01)×5

= 2.00

信息冗余量為：

又例如：把上例改為2-4等長擴展編碼法，其操作碼最短平均長度為：

H = (0.45+0.30+0.15)×2+

(0.05+0.03+0.01+0.01)×4

= 2.20

信息冗余量為：序號概率1-2-3-5擴展編碼I10.450I20.3010I30.15110I40.0511100I50.0311101I60.0111110I70.01111112-4等長擴展編碼0001101100110111101111平均長度2.02.2信息冗余量2.5%11.4%7條指令的操作碼擴展編碼法

舉例2：二~十進制代碼壓縮

2位二~十進制代碼可表示0~99abcdefgh00000000000100010010001000110011010001000101010101100110011101111000100010011001寫出概率表ae=00,g=0.8*0.8=0.64ae=01,g=0.2*0.8=0.16ae=10,g=0.8*0.2=0.16ae=11,g=0.2*0.2=0.04畫出Huffman代碼樹，寫出代碼表ae狀態(tài)概率Huffman代碼000.640100.1611010.16100110.04101寫出壓縮代碼表ae=000bcdfghae=10b=c=011xdfghae=01f=g=0100dbchae=11b=c=f=g=0101dxxh15/15/15與8/64/512編碼

0000

：15種111011110000

：：15種11111110111111110000

：：：15種111111111110111111110111100010000001100010000000111101111000000110000000011100010000………………………………864512指令字格式的優(yōu)化

為了不降低訪存取指令的速度，按整數(shù)邊界存儲。操作數(shù)地址的位數(shù)從尋址范圍看：越大越好用各種方法，壓縮操作碼的位數(shù)通過采用多種不同的尋址方式、地址制、地址形式和地址碼長度以及多種指令字長，將它們與可變長操作碼的優(yōu)化表示相結(jié)合，可構(gòu)成冗余度盡可能少的指令字。等長地址碼發(fā)揮不出操作碼優(yōu)化表示的作用limax地