計算機系統(tǒng)結構第2章指令系統(tǒng).ppt

1 2 第二章指令系統(tǒng) 指令系統(tǒng)是硬件和軟件之間的接口 它會表明一臺計算機具有哪些硬件功能 是硬件邏輯設計的基礎 指令系統(tǒng)也需要為編譯器提供明確的編譯目標 使編譯結果具有規(guī)律性和完整性 指令系統(tǒng)是計算機系統(tǒng)軟硬件功能分配的界面 也是計算機系統(tǒng)結構設計的核心 其功能對計算機系統(tǒng)的性能有直接的影響 3 本章內容 2 1數據表示2 2尋址技術2 3指令格式的設計與優(yōu)化2 4CISC與RISC 4 2 1數據表示 計算機系統(tǒng)中所處理的數據類型各種各樣如 文件 圖 表 樹 隊列 鏈表 棧 向量 串 實數 整數 布爾數和字符等 計算機系統(tǒng)結構要解決的問題是如何在硬件和軟件之間合理分配這些數據類型 即 系統(tǒng)所有的這些數據類型 哪些由硬件實現(xiàn) 哪些用軟件來實現(xiàn) 5 數據表示指的是能由硬件直接識別的數據類型 也就是由指令系統(tǒng)處理的數據類型 例如 PentiumII的數據表示包括 8位 16位和32位帶符號和無符號整數 二 十進制數 32位和64位浮點數 串數據 例如 UltraSPARCII的數據表示有 8位 16位 32位和64位帶符號和無符號整數 32位 64位和128位浮點數 UltraSPARCII沒有提供硬件指令支持二 十進制數和串數據表示 但是它的浮點運算精度可以更高 6 數據表示是數據類型中最常用的 相對比較簡單的 易于硬件實現(xiàn)的那些數據類型 相對較復雜的數據類型 如表 樹 隊列 鏈表等則是由軟件來處理 它們是數據結構研究的對象 由于基本的數據表示在前導課程已有詳細闡述 本節(jié)主要更深入地討論浮點數表示涉及到的一些問題 以及自定義數據表示 7 2 1 1浮點數表示 現(xiàn)代大部分計算機都引入了浮點數據表示 典型的長度有32位和64位 浮點數表示的關鍵問題是 在數據字長確定的情況下 能設計出一種具有最佳表示范圍 表示精度和表示效率的浮點數表示方式 一 浮點數的表示范圍計算機中 典型的浮點數機器字格式如圖2 1所示 8 上圖中 浮點數機器字代碼由兩部分組成 階碼部分e和尾數部分m 階碼部分包含了階符和階碼值兩部分 尾數部分包括數符和尾數值 浮點數的值可表示為 其中 9 浮點數表示需要確定以下6個參數 尾數的基rm尾數表示可以采用用二進制 四進制 八進制 十六進制和十進制等 即尾數的基rm可分別取值為2 4 8 16 10等 尾數的值m尾數m可以采用原碼或補碼表示 數值可以采用小數或整數表示 10 尾數長度n尾數占用的二進制位數稱為尾數長度 不包括符號位 尾數的基為rm 尾數長度為n可表示的rm進制數的位數為當尾數采用二進制即rm 2時 尾數長度就是n 當尾數采用十六進制 則需要4位二進制數表示1位十六進制數 這時十六進制尾數的實際位數為 n 4 階碼的基re 階碼一般采用二進制表示 即階碼的基re 2 階碼的值e 一般采用移碼或補碼表示 值采用整數表示 階碼長度q由于階碼采用二進制 因此 階碼長度q的值就是階碼部分的二進制數位數 注意q不包括階碼符號位 11 由于機器字長的限制 任何一種浮點數的表示范圍和可表示的浮點數個數是有限的 浮點數只能表示出數軸上分散于正 負兩個區(qū)間上的部分離散值 如圖2 2所示 12 在尾數采用原碼 純小數 階碼采用移碼 整數的浮點數表示方式中 規(guī)格化浮點數的表示范圍N正和N負為 13 例2 1浮點數長度32位 數符1位和階符1位 階碼長度q 6 尾數長度n 24 尾數和階碼采用二進制 即rm re 2 尾數采用原碼 純小數 階碼采用移碼 整數 其規(guī)格化浮點數表示范圍為 即 14 例2 2浮點數長度32位 數符1位和階符1位 階碼長度q 6 尾數長度n 24 尾數采用十六進制和階碼采用二進制 即rm 16 re 2 尾數采用原碼 純小數 階碼采用移碼 整數 給出其規(guī)格化浮點數表示范圍 解 由于尾數采用十六進制 24位二進制表示6位十六進制數 故浮點數表示范圍為 即 15 上述兩個例子表明 當浮點數階碼尾數的二進制位數 碼制 小數點位置都相同時 則浮點數表示范圍由基值rm決定 基值rm越大表示范圍越大 但是 基值rm越大 浮點數在數軸上的分布越稀 二 規(guī)格化浮點數的表數個數由于字長限制 浮點數表示方式所能表示的浮點數個數是有限的 不連續(xù)的 可表示的規(guī)格化浮點數的個數為 可表示的階碼的個數與可表示的尾數的個數的乘積 如果階碼的基re 2 則q位長的階碼可表示的階碼的個數為2q個 16 尾數的基為rm n位長的尾數可表示的rm進制數的位數為 每個rm進制數的數位均可以有共有rm個取值 所以 尾數的總個數為 但應去掉小數點后第1個進制數位是0的那些非規(guī)格數 顯然 非規(guī)格化尾數的個數占了全部尾數總個數的的比例 因此 可表示的浮點數規(guī)格化尾數的總個數就為 由此推出可表示的規(guī)格化浮點數的個數為 可以推出 rm越大 在與rm 2的浮點數相重疊的范圍內 所表示數的個數要少得多 即數的密度分布會更稀 17 三 規(guī)格化浮點數的表示精度浮點數表示方式所能表示的浮點數個數是不連續(xù)的 有限的 只能表示出實數中很少的一部分 是實數的一個子集 稱為浮點數集 浮點數集的表示誤差指的是浮點數集中兩個最接近的浮點數之間的誤差 在浮點運算中 會出現(xiàn)運算中間結果或最后結果的尾數不在浮點集中的情況 不是溢出 這時必須用最接近這個結果的浮點數表示 例如 浮點加法運算過程中 對階操作需要對一個浮點數進行右規(guī)時 就要對尾數的最低位進行舍入 通常采用四舍五入來確定最低位的值 這時就產生了誤差 18 表示誤差也稱為表示精度 規(guī)格化浮點數的表示精度直接與尾數基rm的取值和rm進制的尾數位數有關 規(guī)格化浮點數運算中 如果需要對尾數的最低位進行處理 通常采用四舍五入的規(guī)則 因此 可以認為表數誤差是尾數的最后一位的值的一半 由此可以得出規(guī)格化浮點數的表數精度為 2 3 19 根據式 2 3 可以得出例2 1和例2 2中兩種不同尾數基值浮點數的表示精度分別為 比較以上的兩個浮點數的表示精度 可以看出尾數基值rm 16時 其表示精度與rm 2相比將損失23倍 顯然 如果浮點數尾數的二進制位數長度相同時 尾數基值rm為2具有最高的表示精度 20 四 浮點數機器字的格式設計定義一種浮點數機器字的格式需要確定浮點數表示的6個參數 具體原則如下 確定尾數m的數制和碼制 目前多數機器尾數m采用小數 原碼表示 確定階碼e的數制和碼制 目前一般機器階碼e都采用整數 移碼表示 確定尾數的基rm 目前多數機器尾數基值rm取2 確定階碼的基re 在一般通用計算機中 都取re 2 21 在浮點數表示方式中 尾數長度n主要影響表示精度 階碼長度q主要影響示數范圍 可根據要求的示數范圍和表數精度確定n和q的值 按照目前多數實際機器的情況 假設 浮點數尾數m用原碼 小數表示 階碼e用移碼 整數表示 尾數基值rm 2 階碼基值re 2 要求浮點數表示范圍不小于N N為可表示的最大正數 表示精度不低于 確定q和n的值的方法如下 22 根據浮點數表示范圍的要求 可得下式 解這個不等式 得到階碼長度q為 2 4 23 根據浮點數表示精度要求 可得下式 故得出尾數長度n為 2 5 由 2 4 和 2 5 兩個不等式得出的階碼長度q和尾數長度n 再加上一個尾數符號位mf和一個階碼符號位ef 就組成了一種滿足以上假設浮點數表示范圍和表數精度的浮點數機器字格式 一般為了使浮點數機器字字長滿足整數邊界的要求 還需要適當調整q和n的值 24 例2 3設浮點數尾數m用原碼 小數表示 階碼e用移碼 整數表示 尾數基值rm 2 階碼基值re 2 要求規(guī)格化浮點數的表示范圍N為 要求浮點數表數精度不低于 試設計一種浮點數的格式 根據浮點數表示范圍的要求 用式 2 4 計算階碼的長度q 25 考慮到要滿足整數邊界 可取階碼長度q 7位 根據浮點數表數精度要求 用式 2 5 計算尾數長度n 考慮到要滿足整數邊界 可取尾數長度n 54位 26 此例中 階碼長度q 7位 尾數長度n 54位 再加上1位尾數符號位和1位階碼符號位 則浮點數機器字字長為2 q n 63位 距離機器字字長的整數邊界要求還差1位 如果將這1位加到尾數長度上 則設計的64位浮點數機器字格式如下圖所示 27 在數據表示上 高級語言與機器語言一直存在語義差距 高級語言中 在引用數據之前必須用類型說明語句定義數據類型 其運算符不反映數據類型 是通用的 如在C語言程序中 有以下語句 inti jfloatx yi i jx x yi j是整型數據 x y是實型數據 運算符 可用于整型也可用于實型數據相加 2 1 2自定義數據表示 28 然而 一般的機器語言程序則完全不同 指令中是由操作碼定義操作數據的類型 如浮點數加法機器指令 以上指令中 操作碼是浮點加 指定對操作數X和Y進行浮點加法運算 無論X和Y是否是浮點數 都是按浮點數對待 因此 編譯時需要把高級語言程序中的數據類型說明語句和運算符轉換成機器語言中不同類型指令的操作碼 并要驗證指令中操作數的類型是否與運算符所要求的一致 若不一致 還需用進行處理 從而增加了編譯程序的復雜性 29 為了在數據表示上縮小高級語言與機器語言的語義差距 有人提出在機器語言級實現(xiàn)自定義數據表示 即由數據本身定義自己的類型 同時也簡化了指令系統(tǒng)和編譯器 自定義數據表示主要有帶標志符的數據表示和數據描述符數據表示 一 帶標志符的數據表示帶標志符的數據表示是指在數據中采用若干位來表示數據的類型 30 例如 早期的B7500大型機中 每個數據用三位標志符來區(qū)分8種數據類型 如下圖所示 標志符雖然主要用于指明數據類型 也可用于指明所用信息類型 例如 R 2計算機中 采用帶標志符的數據表示的數據字格式如下圖所示 31 上圖中 共有10位標志 2位功能位用于區(qū)別數據是操作數 指令 地址還是控制字 2位陷阱位用于軟件定義4種捕捉方式 為程序員對程序進行跟蹤控制提供方便 1位讀寫位用于指定數據是只讀的還是可讀可寫的 4位類型位可在功能位定義的基礎上進一步定義數據的類型 1位標志位是奇偶校驗位 32 標志符數據表示縮小了高級語言和機器語言語義差距 但是數據字因增設標志符 會增加程序所占的主存空間 而且按標志符確定數據屬性及判斷操作數之間是否相容等操作 會增加硬件復雜性 降低單條指令的執(zhí)行速度 二 數據描述符數據表示對于一組具有相同類型而且是連續(xù)存放的數據 如向量 矩陣和多維數組 沒有必要讓每個數據都帶有相同的標志符 因此 可以采用數據描述符 33 數據描述符與標志符的主要區(qū)別是 標志符只作用于一個數據 而描述符要作用于一組數據 因此 標志符通常與數值一起存放在同一個數據單元中 而描述符一般單獨占用一個存儲單元 描述符在描述一組數據的屬性中 還包括整個數據塊的訪問地址 長度及其他特征或信息 34 a 數據描述符 圖2 6B6700機中數據描述符表示 b 數據 B6700計算機的描述符如下圖所示 前三位為 000 表示該字為數據 前三位為 101 表示該字為數據描述符 如果該字是數據描述符 則進一步用8位標志位描述數據特性 如果描述的是整塊數據時 地址 字段用于指明首元素的地址 長度 字段用于指明塊內的元素個數 35 可以將描述符按樹型連接以描述多維數組表示 例如 有一個3 4二維陣列A 下圖表示了用數據描述符描述A陣列的情況 具體使用了兩級描述符 一級描述符一個 二級描述符是連續(xù)存放的三個描述符 描述符的前三位都為101 36 37 一級描述符的 長度 位為3 指向有3個元素的二級描述符的首址 每個二級描述符的 長度 位都為4 分別指向對應的有4個元素的數據 圖中 二維陣列A是一條指令的一個操作數 指令中的一個地址X指向描述A陣列的一級描述符 OP表示操作碼 38 從指令系統(tǒng)層來看 程序所處理的數據通常存放在主存儲器 寄存器 堆棧 I O接口中 尋址技術就是指如何從這些存儲部件中獲得數據的技術 尋址技術主要討論存儲部件的編址方式 尋址方式和定位方式 在 計算機組成原理 課程中對指令的各種尋址方式有詳細的介紹 在本節(jié)我們更注重于分析和比較它們的特點 2 2尋址技術 39 要訪問存放在主存儲器 寄存器 堆棧 I O接口中的數據 必須對這些存儲部件的空間進行編址 編址方式主要涉及編址單位和編址空間 一 編址單位存儲空間常用的編址單位有 字編址 字節(jié)編址和位編址 多數機器按字節(jié)編址 但是通常主存儲器的字長是4個字節(jié)以上 而且多數機器允許按字節(jié) 單字 雙字訪問存儲器 因此編址單位與訪問存儲器的信息寬度不一致 從而產生數據如何在存儲器中存放的問題 2 2 1編址方式 40 例如 某臺機器 按字節(jié)編址 數據有字節(jié) 8位 半字 雙字節(jié) 單字 4字節(jié) 和雙字 8字節(jié) 不同寬度 主存數據寬度64位 即一個存儲周期可訪問8個字節(jié) 采用按字節(jié)編址 大于字節(jié)寬度的數據是用該數據的首字節(jié)地址來尋址的 一種存放數據的方法是 在主存中允許數據從任意字節(jié)地址單元存放 如圖2 8 a 所示 這種方法很容易出現(xiàn)一個數據跨主存寬度邊界存儲的情況 對于跨界存放的數據 即使數據寬度小于或等于主存寬度 也需要兩個存儲周期才能訪問到 導致訪問速度顯著下降 41 a 數據按任意字節(jié)地址存放 圖2 8數據在主存中的存放方式 42 另一種數據存放方法是 要求數據在主存中存放的地址必須是該數據寬度 字節(jié)數 的整數倍 即雙字地址的最低3個二進制位必須為000 單字地址最低2位必須為00 半字地址最低1位必須為0 如圖2 8 b 所示 這種存放方法也稱為按整數邊界存儲方式 它可以使訪問任意寬度的數據都只用一個存儲周期 雖然浪費了一些存儲空間 但是速度比上一種方法有顯著提高 43 b 數據按整數邊界存放 圖2 8數據在主存中的存放方式 44 二 編址空間的組織計算機中需要編址的存儲部件主要有 通用寄存器 主存儲器和I O接口 它們的編址空間可以有以下3種組織方式 1 三個地址空間由于通用寄存器 主存儲器和I O接口的工作速度和容量等性能差別較大 很多機器中對這3個地址空間進行獨立編址 也就是說 每個地址空間都從0開始編地址碼 CPU中的通用寄存器數量有限 訪問速度很快 其容量比主存儲器小得多 所需要的地址碼長度短 一般只有單一的直接尋址方式 45 主存儲器的容量大 所需要的地址碼長度很長 采用的尋址方式最復雜 一般有間接尋址和變址尋址等多種尋址方式 以避免在指令中直接表示主存單元的地址碼 I O接口中的寄存器的數量一般比通用寄存器多 其地址碼長度介于寄存器和主存之間 因此多采用直接尋址方式 也有機器采用寄存器間址方式 三個地址空間獨立編址 由于每個地址空間都從0開始編碼 因此三個空間會有重疊 但是指令的操作碼和尋址方式會明確指出所訪問的是哪個地址空間 訪問I O地址空間則需要設置專用的I O指令 如Intel80 x86系列就采用三個地址空間獨立編址 46 2 二個地址空間CPU的通用寄存器獨立編址 I O接口寄存器和主存儲器統(tǒng)一編址 統(tǒng)一編址空間的高端地址一般用于I O接口寄存器地址 二個地址空間方式中 訪問主存的指令就能訪問I O寄存器 可以減少指令條數 但其問題是主存的地址空間會減小 如VAX 11系列機就采用二個地址空間的組織方式 3 一個地址空間所有數據存儲單位統(tǒng)一編址 地址空間的低端地址是CPU的通用寄存器地址 高端地址是I O接口寄存器地址 在單片機中 片內存儲器容量不大 一般采用一個地址空間 以減少指令種數 47 計算機中的一些專用寄存器或寄存器堆 如預取指令和數據的緩沖器 是不需要編址的 Cache存儲器映射的是相聯(lián)的主存內容 因此不需要編址 在堆棧型計算機中 數據的存取完全按照先進后出的方式進行 其存儲部件是不需要編址的 48 一條指令包括操作碼和地址碼 指令的功能就是根據操作碼對地址碼提供的操作數完成指定的操作 指令中以什么方式提供操作數或操作數地址 稱為尋址方式 CPU根據指令約定的尋址方式對地址字段的有關信息作出解釋 以找到操作數 每種機器的指令系統(tǒng)都有一套自己的尋址方式 不同計算機的尋址方式的分類和名稱并不統(tǒng)一 但大多數可以歸結為以下幾種類型 2 2 2尋址方式 49 1 立即尋址 2 寄存器尋址 3 主存尋址 直接尋址方式 間接尋址方式 變址類尋址方式 4 堆棧尋址 一臺機器的指令系統(tǒng)可以采用多種尋址方式 那么在指令中如何區(qū)分它們呢 常見的方法有兩種 一種方法是由操作碼決定其尋址方式 即由操作碼含義隱含約定采用何種尋址方式 另一種方法是在指令中設置尋址方式字段 由字段不同的編碼組合來指定操作數的尋址方式 50 2 2 3程序在主存中的定位方法 在多數計算機中 編譯器在對一個源程序或源程序段進行編譯時 是不能確定程序在主存中的實際位置 因此 編譯后的目標程序通常是從零地址開始分配地址空間 這種地址稱為邏輯地址 邏輯地址的集合稱為邏輯地址空間 計算機中的主存儲器 是一維線性編址的 這種地址稱為主存物理地址 其地址的集合稱為主存物理空間 對于多道程序 各目標程序的邏輯地址空間與物理地址空間是不一致的 當程序裝入主存時 就需要進行邏輯地址空間到物理地址空間的轉換 即對程序進行重定位 51 靜態(tài)重定位方法 要求對程序中那些需要修改地址的指令和數據加上某種標識 在程序運行之前 由專門的裝入程序一次將目標程序的帶標識指令和數據的邏輯地址變換成物理地址 程序一旦裝入主存其物理地址不再改變 如圖2 9所示 當目標程序A裝入主存從a地址開始的物理空間中時 為了正確運行程序 指令的地址碼應必須根據不同的尋址方式作相應的變換 如用直接尋址 間接尋址和變址尋址訪存時都應將指令中的邏輯地址加一個a值 而對立即數和相對地址 則不加a值 52 圖2 9靜態(tài)定位方式 53 靜態(tài)定位方式在程序運行時位置不能再改變 主存利用率低 如果程序需要的容量超過分配給它的物理空間 就必須采用覆蓋結構 此外 多個用戶不能共享存放在主存中的同一個程序 而程序的動態(tài)定位方式則可以避免這些問題 程序動態(tài)定位方式 程序在裝入主存時不修改指令的地址碼 而是在程序執(zhí)行時 通過硬件支持的基址尋址方式將操作數的邏輯地址轉換為主存的物理地址 54 如圖2 10所示 將目標程序A在主存中的起始地址a存入對應的基址寄存器中 程序執(zhí)行時 由地址加法器將指令操作數的邏輯地址加上基址寄存器中程序的起始地址 就形成了操作數的物理地址 實際上 并不是所有指令的地址碼都需要修改 如立即尋址和相對尋址是不需要修改的 為此需要在指令中標識本指令的主存地址碼是否需要加上基址 55 圖2 10動態(tài)定位方式 56 動態(tài)定位方式允許為一個程序分配不連續(xù)的主存空間 并且也允許多個程序共享存放在主存中的同一個程序段 有效地提高了主存的利用率 它還可以支持虛擬存儲器 從而大大擴展了邏輯地址空間 但實現(xiàn)動態(tài)定位方式需要有硬件支持且實現(xiàn)存儲管理的軟件算法較復雜 57 2 3指令格式的設計和優(yōu)化 設計者在選擇指令格式時 必須考慮許多因素 包括擴展新指令和利用在指令系統(tǒng)的使用周期中出現(xiàn)的新技術都是相當重要的 具體的設計原則主要有三條 一般情況下 短指令要優(yōu)于長指令 占內存少 減少內存帶寬 可以加快取指令 使指令長度達到最小 可能會使譯碼和重疊執(zhí)行變得困難 增加指令執(zhí)行時間 在指令格式中必須有足夠的空間來表示所有的操作類型 還要考慮留下富余的空間給以后的擴展指令使用 58 關于地址碼的個數與每個地址碼中位的數量 例如 典型RISC機器MIPS的指令長度固定為32位 操作碼6位 訪存指令設計有3個地址碼 2個5位的寄存器地址與1個16位的主存地址偏移量 采用基址尋址方式訪問主存 本節(jié)先描述與分析指令操作碼的三種編碼方式和地址碼的優(yōu)化 然后討論典型的CISC處理器PentiumII與RISC處理器SPARC的指令格式 59 一條指令是由操作碼和地址碼兩部分組成的 指令操作碼的優(yōu)化 就是指如何用最短的二進制位數來表示指令的操作信息 使程序中指令的平均操作碼長度最短 操作碼的編碼方式主要有三種 定長操作碼 哈夫曼 Huffman 編碼和擴展編碼 2 3 1指令操作碼的優(yōu)化 60 一 定長操作碼定長編碼是指所有指令的操作碼長度都是相等的 如果需要編碼的操作碼有n個 那么 定長操作碼的位數最少需要位 例如用指令字中第一個字節(jié) 8位 表示操作碼 這種方式有利于簡化硬件設計和減少指令譯碼時間 但是浪費了信息量 RISC 精簡指令系統(tǒng)計算機 采用這種編碼方法 61 二 哈夫曼編碼哈夫曼 Huffman 編碼法的基本思想 當各種事件發(fā)生的概率不均等時 對發(fā)生概率最高的事件用最短的編碼來表示 而對出現(xiàn)概率較低的事件用較長的編碼來表示 以使事件編碼的平均位數縮短 從而減少處理時間 哈夫曼編碼法可以用于信息壓縮的場合 如存儲空間的壓縮和時間的壓縮 使用哈夫曼編碼對操作碼進行優(yōu)化表示 就需要知道每種指令在程序中出現(xiàn)的概率 使用頻度 這是通過對大量已有的典型程序進行統(tǒng)計后得出的 62 編碼優(yōu)化的程度用平均碼長來評價 平均碼長定義為 2 6 其中 pi表示第i種操作碼在程序中的出現(xiàn)概率或使用頻度 共有n種操作碼 li是第i種操作碼的編碼長度 63 也可以用位冗余量來衡量編碼優(yōu)化的程度 位冗余量為其中 2 7 2 8 H稱為信息熵 Entropy 表示用二進制編碼表示n個碼點時 理論上的最短平均編碼長度 因此 對實際編碼的平均碼長l 都有 故有0 R 1 64 例2 4假設某模型機共有n 10種不同的指令 經統(tǒng)計各指令在程序中的使用頻度如表2 1所示 若操作碼用定長碼表示需要 4位 表2 1某模型機指令使用頻度舉例 65 根據式 2 8 計算操作碼的最短平均編碼長度為 這表明模型機10種指令的操作碼平均只需2 96位即可 如果用4位定長碼表示 l 4 根據式 2 7 計算信息冗余量為 66 利用哈夫曼算法 構造哈夫曼樹 將10條指令的使用頻度從小到大排序構成一個結點集 每次從結點集中選擇頻度最小的兩個結點合并成頻度為這兩個頻度之和的父結點 若結點集不為空集 就將生成的新結點放到結點集中 繼續(xù)從這個新的結點集中選擇出2個頻度最小的結點生成其父結點 直至結點集成為一個空集 就生成了一棵哈夫曼樹 從根節(jié)點開始 對每個結點的兩個分支分別用 0 和 1 標識 下面對此例使用哈夫曼編碼 如圖2 11所示 67 圖2 11哈夫曼樹舉例 68 如果要得到指令Ii的操作碼編碼 則根據圖2 11的哈夫曼樹 從根結點到Ii葉結點的路徑上 將沿線所經過的0或1代碼依次組合起來就形成了Ii指令的哈夫曼編碼 如表2 2左部分所示 69 表2 2操作碼哈夫曼編碼和擴展操作碼編碼 70 根據式 2 6 計算操作碼哈夫曼編碼的平均碼長為 平均碼長2 99位 非常接近于H 這種哈夫曼編碼的信息冗余量為 與4位定長碼的26 信息冗余量相比要小得多 71 需要指出的是哈夫曼編碼并非是惟一的 只要將哈夫曼樹各分支的 0 與 1 互換 就可以得到一組新的編碼 如果存在多個相同的最小頻度 由于頻度合并的次序不同 會導致生成不同的哈夫曼樹 得到的編碼也不相同 但是 計算的哈夫曼編碼平均碼長l是惟一的 而且是可用二進制位編碼平均碼長最短的編碼 因此哈夫曼編碼是最優(yōu)化的編碼 72 三 操作碼擴展編碼哈夫曼編碼具有最優(yōu)化的平均碼長 信息冗余量也接近理想值 但是 哈夫曼編碼形成的操作碼一般不規(guī)整 碼長種類多 不利于實現(xiàn)硬件譯碼和軟件編譯 實際機器中采用將定長操作碼與哈夫曼編碼結合形成的一種編碼方式 稱為操作碼擴展編碼 這種編碼方式的操作碼長度不是定長的 但只限于幾種碼長 較規(guī)整 具體編碼規(guī)則是 根據要求確定編碼的幾種長度 然后從最短碼開始 一種長度的編碼通常要剩下一個或多個碼點用作擴展標志 為后續(xù)較長的編碼使用 與哈夫曼編碼類似 擴展操作碼中的短碼不能是長碼的前綴 73 例2 4中的10條指令 采用2 4擴展操作碼編碼如表2 2右部分所示 將使用頻度高的I1 I2用兩位操作碼的00 01表示 剩下二個碼點10 11作為擴展為4位編碼的標志 根據式 2 6 計算這種擴展操作碼編碼的平均碼長為 74 表2 2操作碼哈夫曼編碼和擴展操作碼編碼 75 這種表示法的平均長度和信息冗余量 雖比哈夾曼編碼的大 但比定長4位碼小得多 而且編碼較規(guī)整 是一種實際可用的優(yōu)化編碼 為了便于硬件分級譯碼 一般采用等長擴展 如4 8 12擴展法表示操作碼位數按4位 8位和12位 每級加長4位擴展 類似還有3 6 9擴展法等 實際機器中 也有根據需要采用每級擴展位數不等的不等長擴展法 76 2 3 2地址碼的優(yōu)化表示 指令由操作碼和地址碼組成 由于下一條指令地址由程序計數器給出 因此地址碼只需要給出操作數和結果的地址 地址碼長度主要取決于地址碼個數 尋址方式 存儲設備 通用寄存器 主存和堆棧等 的編址方式和尋址空間大小等 一 地址碼個數指令的地址碼個數常見的有三個地址 二個地址 一個地址及零地址 77 1 三地址指令格式為 這種格式可以使操作后兩個操作數均不被破壞 可供再次使用 間接減少了程序的長度 如典型的RISC處理器都設置有三地址指令 2 二地址指令格式為 由A2提供源操作數源地址 由A1提供目的操作數地址 在運算后不再保留 該地址改為存放運算結果 只是A1或A2應盡量采用通用寄存器 以減少訪存次數 這種格式減少了指令給出的顯地址數 可以縮短指令長度 Intel80 x86主要采用這種指令格式 78 3 一地址指令格式為 一地址指令有兩種常見的形態(tài) 由操作碼定義它屬于哪一種 只有目的操作數的單操作數指令 指令中只給出一個目的地址A A既是操作數的地址 又是操作結果的存放地址 隱含約定目的地址的雙操作數指令 在某些機器中 雙操作數指令也可采用一地址指令格式 源操作數按指令給出的源地址A讀取 另一個操作數 目的操作數 隱含在CPU的累加器AC中 運算結果也將存放在AC中 如Intel8x86的乘法 除法指令就采用該格式 可見 一地址指令不僅可用來處理單操作數運算 也可用來處理雙操作數運算 這是使用隱地址以簡化地址結構的典型例子 79 4 零地址指令格式為 指令中只有操作碼 不含操作數 這種指令有兩種可能 不需要操作數的指令 例如空操作指令 停機指令等 所需操作數是隱含指定的 如計算機中對堆棧操作的運算指令 所需的操作數事先約定在堆棧中 由堆棧指針SP隱含指出 操作結果仍送回堆棧中 又如Intel80 x86的串操作處理指令 其操作數是隱含指定的 80 從上述討論可知 指令格式中采用隱含指定操作數地址 即隱地址 能夠有效地減少地址數 實際上縮短了指令碼的長度 但是會增加指令譯碼的復雜性 上述幾種指令格式只是一般情況 并非每臺計算機都具有 例如在Intel80 x86的指令系統(tǒng)中 指令地址格式有零地址 一地址和二地址3種形式 三地址地址指令具有功能強 便于編程等特點 如RISC處理器以三地址指令為主 也設置少量二地址 一地址和零地址指令 81 二 縮短地址碼的方法當前大多數計算機系統(tǒng)都采用虛擬存儲器系統(tǒng) 為程序提供更大的地址空間 這就要求指令中的訪存操作數地址是一個邏輯地址 虛擬地址 其長度一般遠超過實際主存的所需地址長度 因此 需要考慮如何用較短的地址碼來表示一個較大的邏輯地址空間 下面討論幾種常用的縮短地址碼的方法 82 采用寄存器直接尋址 或寄存器間接尋址都可以有效地縮短地址碼長度 例如 某機器有32個寄存器 每個寄存器長度是32位 一個寄存器地址只需要5位 如果采用寄存器間址 5位地址碼就可以間接給出32位的存儲器邏輯地址 采用基址或變址尋址方式縮短地址碼長度 由基址寄存器提供全字長的地址碼 足以指向整個邏輯地址空間 運行時可以用基址寄存器裝入某個主存區(qū)間或是程序段的首址 指令中的位移量只是相對于首址的偏移量 位移量可以比較短 例如Intel80 x86實模式的位移量通常為8位或16位 83 采用存儲器間接尋址方式縮短地址長度 例如 主存儲器按字節(jié)編址 將主存低1KB區(qū)域專門用來存放地址 如果邏輯地址需要32位 則用連續(xù)4個字節(jié)單元就可以存放32位地址 即1KB主存空間可以存放256個地址 在指令中用8位長度就可以表示32位地址 84 2 3 3指令格式設計實例 設計指令格式時 需要考慮指令的長度是采用固定的長度 還是采用可變長度 由于不同指令表示的信息量差異很大 可變長度指令就可以滿足這樣的需求 但是讀取變長指令的時間會延長 而且指令越復雜執(zhí)行時間也越長 實現(xiàn)也就更復雜 反之 指令長度固定 格式簡單 則讀取與執(zhí)行時間短 實現(xiàn)相對容易 目前多數復雜指令系統(tǒng)集計算機CISC都采用可變長度指令 如Intel80 x86系列 而精簡指令系統(tǒng)計算機RISC則一般采用固定長度指令 如SPARC MIPS 下面以典型的CISC的處理器PentiumII與RISC處理器SPARC為例討論其指令格式 85 一 PentiumII指令格式Pentium 的指令格式相當復雜 一是要與Intel80 x86兼容 而80 x86的指令格式就比較復雜 二是Pentium 對地址和數據的32位擴展 以及增加了尋址方式的靈活性 圖2 14給出了Pentium 的指令格式 最多具有6個變長域 只有操作碼字段是必須出現(xiàn)的 指令前綴一般根據需要選用 并放在指令前面 在Pentium機器碼程序中 大部分指令并無前綴 它們使用默認的條件進行操作 86 圖2 14Pentium 指令格式 87 1 指令前綴部分 指令前綴有4種 第1種包括4條前綴指令 LOCK REP REPE REPNE 第2種段指定 顯式地指定該指令使用哪個寄存器 第3種操作數長度指定 用于寄存器數據寬度切換 第4種地址長度指定 用于存儲器地址寬度切換 88 2 指令部分 指令本身包括以下字段 1 OPCODE 定義指令類型 寄存器數據寬度 及操作結果存入寄存器還是存儲器 2 MOD RM 分3個字段MOD REG RM REG 3位 定義一個寄存器尋址的操作數 MOD 2位 與RM 3位 定義另一個操作數的尋址方式 包括8個寄存器尋址和24種存儲器尋址 89 3 SIB當MOD RM 00 100時 使用SIB以說明比例變址尋址方式 4 DISP如果MOD RM定義的尋址方式需要位移量 即形式地址 由DISP字段給出 可以是8位 16位或32位 5 IMME如果指令有立即數 由IMME給出 可以是8位 16位或32位 可見 PentiumII的指令格式很復雜 這一是因為要與80X86兼容 二是它的地址和數據擴展到32位 90 Pentium 指令地址格式包括二地址 一地址和零地址3種形式 在早期的80 x86體系結構中 所有指令的操作碼長度都是一個字節(jié)的長度 前綴字節(jié)作為額外的操作碼附加在指令的最前面用于改變指令的操作 然而 在80 x86體系結構發(fā)展的過程中 所有的操作碼已經用完 因此操作碼0 xFF作為出口碼 escapecode 以表示本條指令的操作碼是兩字節(jié)的 PentiumII的操作碼通常需要完全譯碼后才能確定執(zhí)行哪一類操作 同樣 指令的長度也只有在操作碼譯碼后才能知道 也就是譯碼后才能確定下一條指令的起始地址 這就使實現(xiàn)更高的性能如多條指令重疊或同時執(zhí)行變得更為困難 這也是可變長度指令都存在的問題 91 二 SPARC指令格式SPARC ScalableProcessorArchitecture 是指由Sun公司定義的一種RISC處理器結構 92 SPARC所有指令的長度固定為32位 其基本指令格式如下圖 指令最高兩位操作碼 op 定義指令格式 基本指令格式只有3種 格式1專為CALL指令而設 格式2為SETHI 置高位 和BRANCH 轉移 指令而設 常用算術邏輯指令 LOAD STORE指令及其他指令均使用格式3 93 第2個操作碼op2用于區(qū)分BRANCH SETH等指令 第3個操作碼op3是定義指令操作的 每條指令只定義一個單獨的操作 opc是協(xié)處理機指令操作碼 opf是浮點處理機指令操作碼 指令格式3中 大多數指令的第1個源操作數rs1是寄存器操作數 第2個可能是寄存器rs2 也可能是立即數simm13 而目的地址一般均是寄存器rd 除了store和轉移指令外 整數算術邏輯運算指令是將rs1與rs2的內容 或simm13 按操作碼op3規(guī)定的操作運算后把結果送往rd 其功能可以描述為 當格式第13位i 0時 rs1 op3 rs2 rd當i 1時 rs1 op3simm13 rd 94 LOAD指令將存儲器中的數據取出送到rd中 而STORE指令將rd中的數據存到存儲器中 存儲器地址的計算方法如下 寄存器間接尋址方式 當i 0時 存儲器地址 rs1 rs2 當i 1時 存儲器地址 rs1 simm13 95 由于指令長度是32位 因此不能在指令中包括32位常量 SETHI指令只能設置22位常量 而把剩下的10位留給其他指令去實現(xiàn) 非預取的條件轉移指令使用格式2 由cond字段決定測試哪種條件 a位用于延遲轉移控制 當a 0時 跟在轉移指令下面的指令總是被執(zhí)行 當a 1時 只在條件轉移指令轉移成功時 跟在轉移指令下面的指令才被執(zhí)行 格式1用于執(zhí)行過程調CALL指令 這條指令很特別 其操作碼只有兩位 其余30位都用于定義地址 96 隨著技術的發(fā)展 新的指令格式被添加進來 新格式是通過把原來的一個字段分成不同的字段得到的 例如 最初的轉移指令使用格式2 有22位的偏移量 當加入分支預取指令時 22位中的3位被移作他用 其中1位用于預測 預測 不預測 其他兩位用于定義使用的條件碼位集合 只剩下19位的偏移量 SPARC的指令格式 指令類型和尋址方式相對簡單 可以認為是RISC體系結構的代表 97 2 4指令系統(tǒng)的改進 精簡指令系統(tǒng)計算機RISC是20世紀80年代提出的一種新的設計思想 目前市場上很多處理機都采用了RISC體系結構 如SUN公司的SPARC SuperSPARC UtraSPARC SGI公司的R4000 RS000 R10000 IBM公司的Power PowerPC Intel公司的80860 80960 DEC公司的Alpha Motorola公司的88100等 此外 一些典型的復雜指令系統(tǒng)計算機CISC的處理機設計時也吸收一些RISC的設計思想 如Intel公司的80486和Pentium系列 本節(jié)先介紹CISC RISC的特點 然后以兩個典型的RISC處理器MIPSR4000與SPARC為例 討論其指令系統(tǒng) 98 計算機的發(fā)展 使指令系統(tǒng)越來越龐大 復雜 這屬于CISC 復雜指令系統(tǒng)計算機 如 P6指令系統(tǒng)比8086除了在基本指令上有較大的增強外 還增加了57條MMX Multi MediaeXtension 指令及70條流式SIMD擴展指令 隨著Intel的PC機的不斷升級 考慮與以前指令系統(tǒng)的兼容性 其指令系統(tǒng)必將不斷擴張 一 從CISC到RISC 99 CISC指令系統(tǒng)存在的問題 20 與80 規(guī)律CISC中 大約20 的指令占據了80 的處理機時間 8088處理機的指令種類約100種 前11種 11 指令的使用頻度已經超過80 前8種 8 指令的運行時間已經超過80 前20種 20 指令 使用頻度達到91 1 運行時間達到97 72 其余80 指令 使用頻度只有8 9 只占2 28 的處理機運行時間 100 VLSI技術的發(fā)展引起的問題CISC處理器有大量的復雜指令 控制邏輯不規(guī)整 VLSI要求規(guī)整 而RISC控制簡單 符合VLSI要求 CISC要求微程序實現(xiàn)復雜指令系統(tǒng) 而RISC使用簡單指令 可以不用微程序實現(xiàn) 101 軟 硬件的功能分配問題CISC支持目標程序優(yōu)化 支持高級語言和編譯程序 增加了復雜指令 使硬件復雜化 使執(zhí)行時間加長 CISC增加了指令系統(tǒng)功能 簡化了軟件 增加了硬件復雜度 102 70年代 指令系統(tǒng)已非常龐大 指令功能相當復雜 1975年 IBM公司率先組織力量開始研究指令系統(tǒng)的合理性問題1979年研制出世界上第一臺采用RISC思想的計算機IBM8011986年 IBM正式推出采用RISC體系結構的工作站IBMRTPC 103 二 RISC的特點 大多數指令在一個周期內完成 采用LOAD STORE結構 較少的指令數和尋址方式 固定的指令格式 面向寄存器的結構 硬布線控制邏輯 注重編譯的優(yōu)化 104 1981年加州伯克利分校的DavidPatterson等人研制出了32位RISCI微處理器 其指令系統(tǒng)的31種指令包括 12種算術邏輯指令 8種訪問存儲器的指令 7種程序控制指令和4種其他指令 指令字長度固定為32位 以三地址指令為主 有少量二地址和一地址指令 可識別三種數據類型 只有變址尋址和相對尋址兩種尋址方式 按字節(jié)編址 只有LOAD STORE指令可以訪問存儲器 其他指令的操作都在通用寄存器之間進行 時鐘頻率為8MHz 所有指令都在一個機器周期 500ns 完成 78個通用寄存器 將它們分為多個寄存器窗口提供給相應過程使用 即采用重疊寄存器窗口技術 控制器占CPU面積的6 其余用于寄存器 當時CISC的MC68000的控制器占芯片的50 故無法安排數量眾多的寄存器 只能更多地訪問存儲器 105 隨著計算機技術的不斷發(fā)展 RISC的設計思想也有了一些發(fā)展變化 更強調所設計的指令系統(tǒng)支持流水線的高效率執(zhí)行 并支持編譯器生成優(yōu)化代碼 RISC為了使流水線高效率執(zhí)行 應具有以下特征 簡單而統(tǒng)一的指令格式 加快指令譯碼 大部分指令在單周期完成 只有LOAD STORE指令能夠訪問主存 簡單的尋址方式 采用延遲轉移技術 LOAD延遲技術 RISC為了支持編譯器生成優(yōu)化代碼 應具有以下特征 三地址指令格式 較多的寄存器 對稱的指令格式 106 三 減少CPI是RISC思想的精華程序執(zhí)行時間的計算公式 P I CPI T其中 P 執(zhí)行這個程序所使用的總的時間 I 這個程序所需執(zhí)行的總的指令條數 CPI CyclesPerInstruction 每條指令執(zhí)行的平均周期數T是一個周期的時間長度 107 RISC的速度要比CISC快3倍左右 關鍵是RISC的CPI減小了 108 RISC的出現(xiàn)是計算機系統(tǒng)結構發(fā)展最重要的變革之一 一方面CISC通過吸收RISC設計思想提高了傳統(tǒng)機器的性能 例如 Intel公司的80 x86處理機的指令平均周期數在不斷縮小 8086的CPI約為20 80286的CPI約為5 5 80386的CPI約為4 80486的CPI接近2 另一方面 RISC指令系統(tǒng)也開始采用一些復雜而必要的指令 使RISC計算機結構也日益復雜 部分RISC的邏輯實現(xiàn)采用硬聯(lián)和微程序相結合 讓大多數簡單指令用硬聯(lián)方式實現(xiàn) 功能較復雜的指令允許用微程序解釋實現(xiàn) 從目前的發(fā)展趨勢來看 RISC與CISC的優(yōu)勢互補和技術交融將會持續(xù)下去 109 2 4 2RISC指令系統(tǒng)實例 一 MIPSR4000指令系統(tǒng)MIPSTechnology公司推出MIPSR2000 R3000和R6000微處理器芯片 具有相同的32位系統(tǒng)結構和指令系統(tǒng) MIPSR4000與之前芯片不同 它所有內部和外部數據路徑和地址 寄存器以及ALU都是64位的 其指令系統(tǒng)是保持兼容的 64位的結構提供更大的地址空間 允許操作系統(tǒng)將大于1012字節(jié)的文件直接映射到虛擬存儲器 由于目前普遍使用磁盤空間達到或超過100GB 32位機器的4G地址空間變成了限制 此外 64位使得R4000能夠處理更高精度的浮點數如IEEE單精度浮點數 以及能夠一次處理字符串數據中的8個字符 110 R4000處理器包括兩個部分 CPU 存儲管理協(xié)處理器 R4000設置了32個64位通用寄存器 0 31 0寄存器的值固定為0 是一個特殊寄存器 因此 存放數據的寄存器只有31個 R4000包括 64KB指令Cache 64KB的數據Cache 相對較大的Cache允許系統(tǒng)保持更多的程序代碼和局部數據 從而減少了訪存沖突和提高了指令速度 111 1 MIPS的指令格式MIPS的指令采用32位固定長度 支持三地址指令 指令格式有3種 包括立即數型 轉移型和寄存器型 如圖2 16所示 MIPS的尋址方式只有3種 立即數尋址方式 寄存器尋址方式 以及基址加16位偏移量的訪存尋址方式 112 圖2 16MIPS的指令格式 113 2 MIPS指令集MIPSR系列處理器的基本指令集如表2 4所示 MIPS基本指令集有8類指令 具體包括 LOAD STORE指令 算術指令 含立即數 算術指令 三地址 寄存器尋址 移位指令 乘 除指令 跳轉和分支指令 協(xié)處理器指令以及專門指令 所有運算操作都基于寄存器 只有LOAD STORE指令能夠訪問主存儲器 R4000沒有存放條件碼的專用寄存器 如果一條指令產生某個條件 其相應的標志存于一個通用寄存器中 這可以避免采用專門處理條件代碼的邏輯 因為它們影響流水線的執(zhí)行和編譯器對指令的重排序 而且 采用了處理寄存器值相關性的邏輯 以保證流水線的高效率 114 表2 4MIPSR系列基本指令集 115 表2 4MIPSR系列基本指令集 116 表2 4MIPSR系列基本指令集 117 表2 4MIPSR系列基本指令集 118 表2 5R4000附加的指令 R4000在MIPS基本指令集上增加了附加指令 新的指令類型只增加了異常處理指令 其余的是原有類型指令的擴充 119 120 MIPS實現(xiàn)的是最簡單常用的存儲器尋址方式 基址尋址 即地