【文章內(nèi)容簡介】 址方式： 是指令按什么方式尋找（訪問）到所 需的操作數(shù)或信息。 ? 指令所訪問的數(shù)據(jù) 主存、寄存器、堆棧 ? 尋址能力的要求 多樣性、靈活性、尋址空間范圍大小、地址變換速度 ? 目標： 以最短的位描述給定的尋址方式 尋址方式分析 ? 尋址方式在指令中的指明方式 – 占用操作碼位： DJS200系列指令系統(tǒng)中 8位操作碼最高兩位：間接（ 11）和直接（ 01） – 地址碼設(shè)置尋址方式字段： VAX11指令中源和目的各有 4位尋址方式位字段 主存 —— 直接 、 間接 、 變址 、 基址 、 相對尋址 直接尋址 使指令字變長 間接尋址 使指令執(zhí)行速度變慢 相對尋址 用于條件轉(zhuǎn)移指令中定位轉(zhuǎn)向后代碼的位置 變址尋址 支持向量、數(shù)組，實現(xiàn)循環(huán) ，用寄存器做變址器，地址碼部分不會很長，訪問數(shù)據(jù)速度相當于一次訪問內(nèi)存的速度 基址尋址 支持邏輯地址到物理地址的變換， 用于程序的動態(tài)再定位； 寄存器 —— 直接、間接尋址 以寄存器尋址方式為主的計算機稱為通用寄存器型計算機 優(yōu)點： 指令字長短 執(zhí)行速度快 支持向量、矩陣運算 缺點： 不利于編譯程序的設(shè)計 不利于中斷和子程序的遞歸調(diào)用 增加了硬件的復(fù)雜度 ? 堆棧 —— 堆棧尋址（只對棧頂元素進行操作） 特點： 程序所占主存空間小，指令長度短 支持程序的嵌套和遞歸調(diào)用，支持中斷處理 支持高級語言編譯 ? 面向主存：主要訪問內(nèi)存，少量訪問寄存器 – op m1 m2 ? 面向通用寄存器：多數(shù)在寄存器，少量在內(nèi)存 – op r m 、 op r1 r2 ? 面向堆棧：主要在堆棧，可減輕編譯負擔(dān) – op、 op m 、 op r (2)尋址方式分類 大多數(shù)采用分類編址，有三類： ① 存儲效率 ： 堆棧型 〉 通用寄存器型 程序占用空間小 利于減輕對高級語言編譯的負擔(dān) 支持子程序嵌套 、 遞歸調(diào)用 省去大量地址碼字段 ， 省空間 ② 運算速度 ：堆棧型 〈 通用寄存器型 堆棧訪存次數(shù)過多 面向寄存器方式支持向量 、 矩陣 一般在系統(tǒng)中三類尋址方式都應(yīng)當采用 3. 比較： ? 尋址方式分析 – 多種尋址方式可以顯著減少程序的指令條數(shù)，但這同時也可能增加實現(xiàn)的復(fù)雜度和使用這些尋址方式的指令的執(zhí)行時鐘周期數(shù) (CPI)，故需對多種尋址方式進行分析 程序定位技術(shù) ? 邏輯地址：程序員編寫程序時使用的地址 ? 物理地址：程序在主存中的實際地址 ? 一般來講，邏輯地址的空間大于物理地址的空間。因此，映射實際上是壓縮。 ?程序定位技術(shù) – 直接定位 ：程序裝入前，編譯時就已確定了程序中的指令和數(shù)據(jù)的主存物理地址 – 靜態(tài)再定位 ：程序裝入時，由定位裝入程序把程序的邏輯地址變換成物理地址，而在程序的執(zhí)行過程中，物理地址不再改變。 – 動態(tài)再定位 ：在執(zhí)行每條指令時才形成訪存物理地址的方法。通過基址尋址來實現(xiàn) 基址寄存器 ＋ 內(nèi)存 邏輯地址 用戶程序 優(yōu)點： ? 提高了主存利用率 ? 主存中的同一個程序段可為多個程序共享 ? 支持虛擬存儲器 問題： ? 需要硬件支持，虛擬存儲器的軟件管理算法也較復(fù)雜 指令格式的優(yōu)化設(shè)計 ? 指令 = 操作碼 + 地址碼 ? 指令格式的優(yōu)化：如何用最短的位數(shù)來表示指令的操作信息和地址信息，使程序中指令的平均字長最短 ? 主要目標 – 節(jié)省程序的存儲空間 – 指令格式盡量規(guī)整，便于譯碼 1. 操作碼的優(yōu)化設(shè)計 ? 操作碼主要包括兩部分內(nèi)容 – 操作種類：加減乘除、數(shù)據(jù)傳送、移位、轉(zhuǎn)移、I/O – 操作數(shù)描述： ?數(shù)據(jù)類型：定點、浮點、字符（串）、邏輯數(shù)、向量 ?進位制： 16進制 ?數(shù)據(jù)字長：字、半字、雙字、字節(jié) ? 地址碼通常包括三部分內(nèi)容 – 地址 : 直接、間接地址、立即數(shù)、寄存器編號、變址寄存器編號 – 地址的附加信息 : 偏移量、塊長度、間距 – 尋址方式 : 直接、間接、立即數(shù)、變址、相對寄存器尋址 ? 操作碼的三種編碼方法 – 固定長度 : 規(guī)整性好 , 解碼簡單 , 占用空間大 – Huffman編碼 : 空間小 , 規(guī)整性不好 , 解碼復(fù)雜 – 擴展編碼 : 折衷方案 ? 哈夫曼 (Huffman)壓縮概念 – 當各種事件發(fā)生的概率不均等時 , 采用優(yōu)化技術(shù)對發(fā)生 概率較高 的事件用 較短 的位數(shù) (時間 )來表示 (處理 ), 而對出現(xiàn)概率較低的允許用較長的位數(shù) (時間 )來表示 (處理 ), 以達到平均位數(shù)最少的目的 用于代碼壓縮、程序壓縮、空間壓縮和時間壓縮 ? 操作碼的優(yōu)化表示 – 信息源熵 ：信息源包含的平均信息量 – 操作碼的優(yōu)化表示就是要使信息冗余量 R最小 H即為操作碼可以達到的最短平均碼長 – 信息冗余量 – 實際編碼的操作碼碼長為： 例 ，頻度如下 I1 I2 I3 I4 I5 I6 I7 信息源熵 H= 信息冗余量 R=()/3==28% （ 1）等長編碼 可用 000～ 110來分別表示 7種不同的指令 I1: 000 I2: 001 I3: 010 I4: 011 I5: 100 I6: 101 I7: 110 （ 2）哈夫曼編碼（操作碼設(shè)計） ?表示方法：哈夫曼樹 ?基本思想 （頻率相關(guān)思想）： 當事件發(fā)生的概率不均等時，對概率高的事件用較短的位數(shù)（或時間）來表示，對概率低的事件用較長的位數(shù)（或時間）來表示，導(dǎo)致平均位數(shù)（時間）最短。 ? (1)將事件的使用頻度值作為葉結(jié)點并按出現(xiàn)頻率次序排列； （排序） (2)將出現(xiàn)頻率最小的兩個事件合并（頻率相加）形成一個新結(jié)點； （合并） (3)在新組成的葉結(jié)點序列中繼續(xù)做 (2)，直至到根結(jié)點（頻率＝ 1，構(gòu)成一棵樹 )； (4)從樹根起沿左和右子樹分別分配其值為 1和 0，直至葉結(jié)點； （分配值 ） (5)事件的使用頻度值葉結(jié)點編碼為從根結(jié)點到葉結(jié)點的編碼組合。 （得到編碼） 構(gòu)建方法： 1 0 0 0 0 0 0 1 1 1 1 1 I7 I6 I5 I4 I3 I2 I1 I1 I2 I3 I4 I5 I6 I7 0 10 110 11100 11101 11110 11111 葉結(jié)點 根結(jié)點 合并結(jié)點 由此可得到哈夫曼編碼如下： I1: 0 I2: 10 I3: 110 I4: 11100 I5: 11101 I6: 11110 I7: 11111 信息冗余量 R=()/=% 指令長度個數(shù) =4 平均碼長 L=*1+*2+*3+*5 +*5+*5+*5 = ? Huffman特點 : 平均碼長最短 代碼不唯一 ：（ 0, 1 可對換） （ 3）哈夫曼擴展編碼 （操作碼優(yōu)化） —— 擴展編碼法 基本思想：對霍夫曼編碼，根據(jù)使用頻率宏觀分布，將編碼長度擴展成幾種長度的編碼。 實現(xiàn)目標：平均碼長接近全哈夫曼碼的碼長， 同時又保持了 定長碼的規(guī)整性。 ?Huffman操作碼的主要缺點 – 操作碼長度很不規(guī)整 , 硬件譯碼困難 – 與地址碼共同組成固定長的指令比較困難 ? 例 1: Huffman用四種長度 0, 10, 110, 11100, 11101, 11110, 11111 , , , ? 擴展哈夫曼編碼如下： I1, I2, I3 用兩位 : 00, 01, 10 I4, I5, I6, I7 用四位 : 1100,1101,1110,1111 L=(++)*2+(+++)*4 = 信息冗余量 =()/==% 4 1 1 1 1 5 1 1 1 1 1 I7 4 1 1 1 0 5 1 1 1 1 0 I6 4 1 1 0 1 5 1 1 1 0 1 I5 4 1 1 0 0 5 1 1 1 0 0 I4 2 1 0 3 1 1 0 I3 2 0 1 2 1 0 I2 2 0 0 1 0 I1 OP長度 li huffman擴展編碼 OP長度 li 操作碼 OP 使用哈夫曼編碼 頻 度 （ Pi） 指 令 操作碼的擴展（等長擴展） 平均碼長： 2. 2 擴展方法： 等長擴展 和 不等長擴展 兩種。 ?等長擴展 —— 每次擴展相同的位數(shù) 如 4812等長擴展方法（ 每次擴展 4位 ） ?不等長擴展 —— 每次擴展不同的位數(shù) 如 4610不等長擴展方法 (美國的 B1700) 擴展標志： 保留 碼點標志 —— 一組編碼作為擴展標志 保留 標志位 —— 一個標志位作為擴展標志 擴展編碼中選擇某些特征位用于擴展。 0001 0000 1110 15 0000 0001 . . . 1110 15 1111 . . . 1111 1111 . . . 0000 0001 1110 15 1111 . . . 1111 1111 . . . 1111 1111 1111 . . . 8 0 000 0 001 . . . 0 111 64 1 000 1 001 . . . 1 111 512 1 000 1 001 . . . 1 111 0 000 0 001 0 111 1 000 1 001 1 111 0 000 0 001 0 111 . . . . . . 15/15/15擴展法 8/64/512編碼法 碼點標志 碼點標志 保留標志位 保留標志位 4812等長擴展編碼 ? 采用保留特征碼（碼點標志）方法編碼簡單，但表示的指令總數(shù)少。 例如： 4812等長編碼， 151515每種長度指令數(shù)為15，共可編碼 45種 平均每條指令位數(shù) =(4＋ 8＋ 12) 15/45=8 ? 采用保留標志位方法編碼較為復(fù)雜，但表示的指令總數(shù)多。 例如： 4812等長編碼， 864512共有指令數(shù)為 584 平均每條指令位數(shù)＝ （ 8 4＋ 64 8＋ 512 12） /584= 例 2：指令系統(tǒng)共有 42種指令，前 15種使用頻率平均為 ，中間 13種使用頻率平均為 ，最后 14種使用頻率平均為 。如何編碼？ 0000 ： 15種 1110 1111 0000 ： ： 15種 1111 1110 1111 1111 0000 ： ： ： 15種 1111 1111 1110 解：因頻率分布有三種，故碼長可有三種； 因每段指令數(shù)基本相同，故可采用 等長擴展 (4812位)， 保留特征碼的每段指令數(shù)相同 (151515)方法。結(jié)果如圖所示； 結(jié)果：采用 151515擴展方法，最后一種編碼用于擴展，每段 0000～ 1110用于編碼， 1111用于擴展。 例 3：指令系統(tǒng)共有 74種指令，前 4種使用頻率平均為 ，中間 15種使用頻率平均為 ，最后 55種使用頻率平均為 。如何編碼？ 解：同上例方法， 碼長可有三種； 因每段指令數(shù)成比例(1： 4)，故可采用 等長擴展方法 (369位 )擴展 ，保留標志位方法，結(jié)果如圖所示； 結(jié)果：采用 41664擴展方法，編碼第一位用于擴展，每段 0XX用于編碼， 1XX用于擴展。 0xx