計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(ch-2)

1、1v 計(jì)算機(jī)系統(tǒng)的性能評(píng)價(jià)計(jì)算機(jī)系統(tǒng)的性能評(píng)價(jià) T TCPUCPU = I = IN NCPICPITcTc MIPSMIPS和和MFLOPSMFLOPS 基準(zhǔn)測(cè)試程序基準(zhǔn)測(cè)試程序（benchmarkbenchmark） 算術(shù)平均值算術(shù)平均值A(chǔ)m 調(diào)和平均值調(diào)和平均值Hm 幾何平均值幾何平均值Gm11()niiniiiNiNIICPIICPICPII總時(shí)鐘周期數(shù)指令總條數(shù)CCPU11=CPUNCNfTICPITICPI性能661010CPIfTIMIPScCPUN結(jié)論與參結(jié)論與參照機(jī)無(wú)關(guān)照機(jī)無(wú)關(guān)2v2.1 2.1 數(shù)據(jù)表示數(shù)據(jù)表示v2.2 2.2 尋址方式與指令格式的優(yōu)化尋址方式與指令格式的優(yōu)

2、化v2.3 CISC2.3 CISCv2.4 RISC2.4 RISC3v2.1.1 數(shù)據(jù)類型、數(shù)據(jù)表示與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型、數(shù)據(jù)表示與數(shù)據(jù)結(jié)構(gòu)v2.1.2 高級(jí)數(shù)據(jù)表示高級(jí)數(shù)據(jù)表示 自定義數(shù)據(jù)表示自定義數(shù)據(jù)表示 帶標(biāo)志符的數(shù)據(jù)表示帶標(biāo)志符的數(shù)據(jù)表示 數(shù)據(jù)描述符表示數(shù)據(jù)描述符表示 向量數(shù)據(jù)表示向量數(shù)據(jù)表示 堆棧數(shù)據(jù)表示堆棧數(shù)據(jù)表示4v什么是數(shù)據(jù)類型？什么是數(shù)據(jù)類型？v與數(shù)據(jù)值有什么區(qū)別？與數(shù)據(jù)值有什么區(qū)別？v為什么要定義數(shù)據(jù)類型？為什么要定義數(shù)據(jù)類型？v如何實(shí)現(xiàn)不同的數(shù)據(jù)類型？如何實(shí)現(xiàn)不同的數(shù)據(jù)類型？5v 數(shù)據(jù)類型數(shù)據(jù)類型：數(shù)值集合數(shù)值集合+ +操作集合。操作集合。v 數(shù)據(jù)表示數(shù)據(jù)表示：計(jì)算機(jī)硬

3、件可直接識(shí)別和引用的數(shù)據(jù)類型。：計(jì)算機(jī)硬件可直接識(shí)別和引用的數(shù)據(jù)類型。v 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)數(shù)據(jù)類型的組織方式；由軟件識(shí)別的數(shù)據(jù)類型。：結(jié)構(gòu)數(shù)據(jù)類型的組織方式；由軟件識(shí)別的數(shù)據(jù)類型。v 不同的數(shù)據(jù)表示可以為數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)提供不同的支持不同的數(shù)據(jù)表示可以為數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)提供不同的支持, 因此因此數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示是軟、硬件界面軟、硬件界面。v 理論上只需理論上只需最基本的數(shù)據(jù)類型最基本的數(shù)據(jù)類型（定點(diǎn)），其它都可由軟件實(shí)現(xiàn)，（定點(diǎn)），其它都可由軟件實(shí)現(xiàn)，但效率差，相反，所有數(shù)據(jù)類型都由硬件實(shí)現(xiàn)，成本高。但效率差，相反，所有數(shù)據(jù)類型都由硬件實(shí)現(xiàn)，成本高。v 實(shí)驗(yàn)表明實(shí)驗(yàn)表明

4、：用定點(diǎn)數(shù)據(jù)表示實(shí)現(xiàn)浮點(diǎn)運(yùn)算，處理機(jī)速度降低兩：用定點(diǎn)數(shù)據(jù)表示實(shí)現(xiàn)浮點(diǎn)運(yùn)算，處理機(jī)速度降低兩個(gè)數(shù)量級(jí)。個(gè)數(shù)量級(jí)。何謂硬件能夠直接識(shí)別？何謂硬件能夠直接識(shí)別？能夠直接由硬件實(shí)現(xiàn)相應(yīng)數(shù)據(jù)的運(yùn)算，也就是系能夠直接由硬件實(shí)現(xiàn)相應(yīng)數(shù)據(jù)的運(yùn)算，也就是系統(tǒng)結(jié)構(gòu)中要有相應(yīng)的運(yùn)算指令和運(yùn)算部件來(lái)完成這統(tǒng)結(jié)構(gòu)中要有相應(yīng)的運(yùn)算指令和運(yùn)算部件來(lái)完成這項(xiàng)任務(wù)。項(xiàng)任務(wù)。數(shù)據(jù)表示數(shù)據(jù)表示+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)6v系統(tǒng)效率是否提高系統(tǒng)效率是否提高縮短運(yùn)行時(shí)間（減少縮短運(yùn)行時(shí)間（減少CPU與存儲(chǔ)器的通信量）與存儲(chǔ)器的通信量）減少所需存儲(chǔ)空間減少所需存儲(chǔ)空間v高通用性和高利用率高通用性和高利用率否則會(huì)因?yàn)橛布杀镜脑黾佣档托詢r(jià)比否

5、則會(huì)因?yàn)橛布杀镜脑黾佣档托詢r(jià)比7v 1 1）若）若無(wú)向量數(shù)據(jù)表示無(wú)向量數(shù)據(jù)表示，一般需，一般需6 6條指令，其中條指令，其中4 4條要條要循環(huán)循環(huán)4 4萬(wàn)次。萬(wàn)次。vCPUCPU與與M M的通信量為：的通信量為：取指令：取指令：2+42+44000040000條條讀、寫(xiě)數(shù)據(jù)：讀、寫(xiě)數(shù)據(jù)：3 34000040000個(gè)個(gè)共訪問(wèn)存儲(chǔ)器：共訪問(wèn)存儲(chǔ)器：2+72+74000040000次次循環(huán)次數(shù)初始化循環(huán)次數(shù)初始化變址寄存器初始化變址寄存器初始化Ai+BiAi變址值修改變址值修改循環(huán)次數(shù)修改循環(huán)次數(shù)修改判斷并循環(huán)判斷并循環(huán)8 2）若）若有向量數(shù)據(jù)表示有向量數(shù)據(jù)表示，則只需，則只需1條條向量加法指令

6、向量加法指令，即只需取即只需取1條指令，少取指令條指令，少取指令1+440000次，讀、寫(xiě)數(shù)次，讀、寫(xiě)數(shù)據(jù)次數(shù)不變，執(zhí)行時(shí)間（訪存次數(shù)）縮短一半以上。據(jù)次數(shù)不變，執(zhí)行時(shí)間（訪存次數(shù)）縮短一半以上。無(wú)向量表示無(wú)向量表示有向量表示有向量表示取指令：取指令：2+4400001讀寫(xiě)數(shù)據(jù)讀寫(xiě)數(shù)據(jù)340000340000總訪問(wèn)次數(shù)總訪問(wèn)次數(shù)2+7400001+3400009v數(shù)據(jù)表示數(shù)據(jù)表示不斷上移不斷上移。字符串、向量、堆棧等數(shù)據(jù)表示已很。字符串、向量、堆棧等數(shù)據(jù)表示已很普遍。圖、表等復(fù)雜數(shù)據(jù)表示也開(kāi)始在某些計(jì)算機(jī)上出現(xiàn)。普遍。圖、表等復(fù)雜數(shù)據(jù)表示也開(kāi)始在某些計(jì)算機(jī)上出現(xiàn)。v對(duì)于一些復(fù)雜數(shù)據(jù)類型，如果用

7、數(shù)據(jù)表示實(shí)現(xiàn)，硬件代價(jià)對(duì)于一些復(fù)雜數(shù)據(jù)類型，如果用數(shù)據(jù)表示實(shí)現(xiàn)，硬件代價(jià)可能非常大。但如果用硬件給以適當(dāng)?shù)闹С?，用軟、硬結(jié)合可能非常大。但如果用硬件給以適當(dāng)?shù)闹С?，用軟、硬結(jié)合的方法實(shí)現(xiàn)，效果會(huì)很好。如用的方法實(shí)現(xiàn)，效果會(huì)很好。如用變址尋址方式變址尋址方式支持向量表示。支持向量表示。v系統(tǒng)結(jié)構(gòu)設(shè)計(jì)者應(yīng)考慮系統(tǒng)結(jié)構(gòu)設(shè)計(jì)者應(yīng)考慮：哪些數(shù)據(jù)類型用硬件實(shí)現(xiàn)（數(shù)據(jù)：哪些數(shù)據(jù)類型用硬件實(shí)現(xiàn)（數(shù)據(jù)表示），哪些用軟件實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)），哪些用軟、硬結(jié)合表示），哪些用軟件實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)），哪些用軟、硬結(jié)合實(shí)現(xiàn)（給以適當(dāng)?shù)挠布С郑?。?shí)現(xiàn)（給以適當(dāng)?shù)挠布С郑?011一般處理機(jī)中的數(shù)據(jù)表示方法一般處理機(jī)中的數(shù)據(jù)表

8、示方法v數(shù)據(jù)存儲(chǔ)單元（寄存器、主存儲(chǔ)器、外存儲(chǔ)器等）只存放數(shù)據(jù)存儲(chǔ)單元（寄存器、主存儲(chǔ)器、外存儲(chǔ)器等）只存放純數(shù)純數(shù)據(jù)據(jù)v通過(guò)指令中的通過(guò)指令中的操作碼解釋：操作碼解釋： 數(shù)據(jù)的類型數(shù)據(jù)的類型（定點(diǎn)、浮點(diǎn)、字符、字符串、邏輯數(shù)、向量（定點(diǎn)、浮點(diǎn)、字符、字符串、邏輯數(shù)、向量等）等） 進(jìn)位制進(jìn)位制（2進(jìn)制、進(jìn)制、10進(jìn)制、進(jìn)制、16進(jìn)制等）進(jìn)制等） 數(shù)據(jù)字長(zhǎng)數(shù)據(jù)字長(zhǎng)（字、半字、雙字、字節(jié)等）（字、半字、雙字、字節(jié)等） 尋址方式尋址方式（直接尋址、間接尋址、相對(duì)尋址、寄存器尋址（直接尋址、間接尋址、相對(duì)尋址、寄存器尋址等）等） 數(shù)據(jù)的功能數(shù)據(jù)的功能（地址、數(shù)值、控制字、標(biāo)志等）（地址、數(shù)值、控制字、

9、標(biāo)志等）v同一種操作有很多條指令（如同一種操作有很多條指令（如IBM370 的加法的加法指令指令共有共有8條）條）1213v在高級(jí)語(yǔ)言和應(yīng)用軟件中，在高級(jí)語(yǔ)言和應(yīng)用軟件中，數(shù)據(jù)的屬性數(shù)據(jù)的屬性由數(shù)據(jù)自己定由數(shù)據(jù)自己定義，而機(jī)器語(yǔ)言中的數(shù)據(jù)屬性一般由指令區(qū)分。高級(jí)語(yǔ)義，而機(jī)器語(yǔ)言中的數(shù)據(jù)屬性一般由指令區(qū)分。高級(jí)語(yǔ)言與機(jī)器語(yǔ)言之間的這種言與機(jī)器語(yǔ)言之間的這種語(yǔ)義差距語(yǔ)義差距，要靠，要靠編譯器等填補(bǔ)編譯器等填補(bǔ)，這增加了編譯的負(fù)擔(dān)、降低效率。這增加了編譯的負(fù)擔(dān)、降低效率。v常用高級(jí)數(shù)據(jù)表示方法：常用高級(jí)數(shù)據(jù)表示方法：自定義（自定義（Self-defining）數(shù)據(jù)表示）數(shù)據(jù)表示帶標(biāo)志符的數(shù)據(jù)表示帶標(biāo)

10、志符的數(shù)據(jù)表示 數(shù)據(jù)描述符表示數(shù)據(jù)描述符表示向量數(shù)組數(shù)據(jù)表示向量數(shù)組數(shù)據(jù)表示 堆棧數(shù)據(jù)表示堆棧數(shù)據(jù)表示141）帶標(biāo)志符的數(shù)據(jù)表示）帶標(biāo)志符的數(shù)據(jù)表示 60年代開(kāi)始，年代開(kāi)始，Burroughs公司在大型機(jī)中引入帶公司在大型機(jī)中引入帶標(biāo)志符標(biāo)志符的數(shù)據(jù)表示方式和的數(shù)據(jù)表示方式和數(shù)據(jù)數(shù)據(jù)描述符描述符兩種自定義數(shù)據(jù)表示方式。兩種自定義數(shù)據(jù)表示方式。vB5000的類型標(biāo)志位為的類型標(biāo)志位為1位，用來(lái)區(qū)分是操作數(shù)還位，用來(lái)區(qū)分是操作數(shù)還 是描述符；是描述符；vB6500、B7500的類型標(biāo)志位為的類型標(biāo)志位為3位，用來(lái)區(qū)分位，用來(lái)區(qū)分8種數(shù)種數(shù)據(jù)；據(jù)；vR-2的類型標(biāo)志位為的類型標(biāo)志位為10位位數(shù)據(jù)值數(shù)

11、據(jù)值類型標(biāo)志類型標(biāo)志 帶標(biāo)志符的數(shù)據(jù)表示帶標(biāo)志符的數(shù)據(jù)表示15v功能：操作數(shù)、指令、地址、控制字功能：操作數(shù)、指令、地址、控制字v陷阱：可由軟件定義陷阱：可由軟件定義4種捕捉方式種捕捉方式v封寫(xiě)：只讀、讀寫(xiě)封寫(xiě)：只讀、讀寫(xiě)v類型：在功能的基礎(chǔ)上進(jìn)一步定義類型類型：在功能的基礎(chǔ)上進(jìn)一步定義類型v校驗(yàn)：奇偶校驗(yàn)校驗(yàn)：奇偶校驗(yàn)2位位2位位1位位4位位1位位功能功能陷阱陷阱封寫(xiě)封寫(xiě)類型類型校驗(yàn)校驗(yàn)數(shù)值數(shù)值16v 標(biāo)志符數(shù)據(jù)表示方法的標(biāo)志符數(shù)據(jù)表示方法的主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)： 簡(jiǎn)化了指令系統(tǒng)和程序設(shè)計(jì)，縮小了人與機(jī)器之間的語(yǔ)義簡(jiǎn)化了指令系統(tǒng)和程序設(shè)計(jì)，縮小了人與機(jī)器之間的語(yǔ)義差距。差距。標(biāo)志符對(duì)高級(jí)語(yǔ)言程序

12、員透明，由編譯程序建立。標(biāo)志符對(duì)高級(jí)語(yǔ)言程序員透明，由編譯程序建立。 簡(jiǎn)化編譯程序，使高級(jí)語(yǔ)言與機(jī)器語(yǔ)言之間的簡(jiǎn)化編譯程序，使高級(jí)語(yǔ)言與機(jī)器語(yǔ)言之間的語(yǔ)義差距語(yǔ)義差距大大大縮短。大縮短。 便于實(shí)現(xiàn)相容性和一致性檢查便于實(shí)現(xiàn)相容性和一致性檢查，可以由硬件自動(dòng)實(shí)現(xiàn)，可以由硬件自動(dòng)實(shí)現(xiàn)。 由硬件自動(dòng)實(shí)現(xiàn)由硬件自動(dòng)實(shí)現(xiàn)數(shù)據(jù)類型轉(zhuǎn)換數(shù)據(jù)類型轉(zhuǎn)換。 支持支持DBS的實(shí)現(xiàn)與數(shù)據(jù)類型無(wú)關(guān)的要求。的實(shí)現(xiàn)與數(shù)據(jù)類型無(wú)關(guān)的要求。 方便軟件調(diào)試。根據(jù)捕捉標(biāo)志設(shè)置斷點(diǎn)等。方便軟件調(diào)試。根據(jù)捕捉標(biāo)志設(shè)置斷點(diǎn)等。v 8087中就使用了標(biāo)志符數(shù)據(jù)表示方法中就使用了標(biāo)志符數(shù)據(jù)表示方法17v數(shù)據(jù)和指令的長(zhǎng)度可能不一致。數(shù)據(jù)和指令

13、的長(zhǎng)度可能不一致。 解決方法：解決方法： 數(shù)據(jù)和指令分存于不同的存儲(chǔ)器，即數(shù)據(jù)和指令分存于不同的存儲(chǔ)器，即多體存儲(chǔ)器多體存儲(chǔ)器 合理設(shè)計(jì)指令字長(zhǎng)和數(shù)據(jù)字長(zhǎng)，一般原則是指令字合理設(shè)計(jì)指令字長(zhǎng)和數(shù)據(jù)字長(zhǎng)，一般原則是指令字長(zhǎng)向數(shù)據(jù)字長(zhǎng)靠攏長(zhǎng)向數(shù)據(jù)字長(zhǎng)靠攏v指令的執(zhí)行速度（指令的執(zhí)行速度（微觀速度微觀速度）降低。）降低。 程序的設(shè)計(jì)時(shí)間、編譯時(shí)間和調(diào)試時(shí)間縮短（程序的設(shè)計(jì)時(shí)間、編譯時(shí)間和調(diào)試時(shí)間縮短（宏觀時(shí)間宏觀時(shí)間）v硬件復(fù)雜度增加。硬件復(fù)雜度增加。 隨隨VLSIVLSI的發(fā)展，已不是大問(wèn)題。的發(fā)展，已不是大問(wèn)題。v存儲(chǔ)容量的變化。存儲(chǔ)容量的變化。 數(shù)據(jù)占用的存儲(chǔ)容量增大數(shù)據(jù)占用的存儲(chǔ)容量增大 指令

14、所占用的存儲(chǔ)容量減小指令所占用的存儲(chǔ)容量減小192）數(shù)據(jù)描述符表示法）數(shù)據(jù)描述符表示法用于用于描述一組相同類型的數(shù)據(jù)描述一組相同類型的數(shù)據(jù)（向量、矩陣、記（向量、矩陣、記錄等）。錄等）。Burroughs公司生產(chǎn)的公司生產(chǎn)的B6700機(jī)中采用的數(shù)據(jù)描機(jī)中采用的數(shù)據(jù)描述符表示方法：述符表示方法：101（描述符標(biāo)志位）（描述符標(biāo)志位） 特征標(biāo)記特征標(biāo)記 數(shù)據(jù)塊長(zhǎng)度數(shù)據(jù)塊長(zhǎng)度起始地址起始地址000/010（標(biāo)志符）（標(biāo)志符）數(shù)據(jù)數(shù)據(jù)38202048320yx塊長(zhǎng)度為塊長(zhǎng)度為3塊長(zhǎng)度為塊長(zhǎng)度為422v標(biāo)志符要與每個(gè)數(shù)據(jù)相連，兩者合用一存儲(chǔ)單元，而標(biāo)志符要與每個(gè)數(shù)據(jù)相連，兩者合用一存儲(chǔ)單元，而描述符則和

15、數(shù)據(jù)分開(kāi)存放描述符則和數(shù)據(jù)分開(kāi)存放v要訪問(wèn)數(shù)據(jù)集中的元素時(shí)，必須先訪問(wèn)描述符，增加要訪問(wèn)數(shù)據(jù)集中的元素時(shí)，必須先訪問(wèn)描述符，增加一級(jí)尋址一級(jí)尋址v描述符可看成是程序的一部分，而不是數(shù)據(jù)的一部分描述符可看成是程序的一部分，而不是數(shù)據(jù)的一部分23向量數(shù)據(jù)表示向量數(shù)據(jù)表示v C Ci i=A=Ai+5i+5+B+Bi i i=10 i=10 1000 1000v C C代碼代碼 for (i=10;i=1000;i+)for (i=10;i=1000;i+) Ci Ci=Ai+5+Bi;=Ai+5+Bi;v 標(biāo)量機(jī)上運(yùn)行時(shí)，編譯后需借助變址操作實(shí)現(xiàn)，標(biāo)量機(jī)上運(yùn)行時(shí)，編譯后需借助變址操作實(shí)現(xiàn)，各條指令

16、只能順序執(zhí)行。各條指令只能順序執(zhí)行。v 若有向量數(shù)據(jù)表示，可用一條向量指令實(shí)現(xiàn)若有向量數(shù)據(jù)表示，可用一條向量指令實(shí)現(xiàn)向量加（向量加（OP）A向量參數(shù)向量參數(shù)B向量參數(shù)向量參數(shù)C向量參數(shù)向量參數(shù)24基地址基地址向量長(zhǎng)度向量長(zhǎng)度 有效長(zhǎng)度有效長(zhǎng)度（向量長(zhǎng)度（向量長(zhǎng)度-位移量）位移量） 起始地址起始地址（基址（基址+位移）位移）位移量位移量向量參數(shù)：基地址、位移量、向量長(zhǎng)度、有效長(zhǎng)度、步距向量參數(shù)：基地址、位移量、向量長(zhǎng)度、有效長(zhǎng)度、步距向量數(shù)據(jù)表示向量數(shù)據(jù)表示Ci=Ai+5+Bi i=10 1000向量加（向量加（OP）A向量參數(shù)向量參數(shù)B向量參數(shù)向量參數(shù)C向量參數(shù)向量參數(shù)25L.D F0,a ;

17、load scalar aDADDIU R4,Rx,#512 ;last address to loadLoop: L.D F2,0(Rx) ;load X(i)MUL.D F2,F2,F0 ;a X(i)L.D F4,0(Ry) ;load Y(i)ADD.D F4,F4,F2 ;a X(i) + Y(i)S.D 0(Ry),F4 ;store into Y(i)DADDIU Rx,Rx,#8 ;increment index to XDADDIU Ry,Ry,#8 ;increment index to YDSUBU R20,R4,Rx ;compute boundBNEZ R20,Loo

18、p ;check if doneY=aX+Y26L.D F0,a ;load scalar aLV V1,Rx ;load vector XMULVS.D V2,V1,F0 ;vector-scalar multiplyLV V3,Ry ;load vector YADDV.D V4,V2,V3 ;addSV Ry,V4 ;store the result27A0A1（0）A2（0）A3A4A5（0）A6（0）A7稀疏向量稀疏向量A0A3A4A7壓縮向量壓縮向量01011001有序位向量有序位向量28v一般通用寄存器型機(jī)器對(duì)堆棧實(shí)現(xiàn)的支持較差：一般通用寄存器型機(jī)器對(duì)堆棧實(shí)現(xiàn)的支持較差：堆棧指令

19、少、功能單一（堆棧指令少、功能單一（Push、Pop） 堆棧位于存儲(chǔ)器內(nèi)，速度低，通常用于保存子程序調(diào)用時(shí)的堆棧位于存儲(chǔ)器內(nèi)，速度低，通常用于保存子程序調(diào)用時(shí)的返回地址及傳遞參數(shù)（返回地址及傳遞參數(shù)（軟堆棧軟堆棧）v具有堆棧數(shù)據(jù)表示和以堆棧尋址方式為主的計(jì)算機(jī)稱具有堆棧數(shù)據(jù)表示和以堆棧尋址方式為主的計(jì)算機(jī)稱堆棧型堆棧型計(jì)算機(jī)計(jì)算機(jī)。堆棧機(jī)器優(yōu)點(diǎn)：。堆棧機(jī)器優(yōu)點(diǎn)：寄存器硬堆棧寄存器硬堆棧與與主存軟堆棧主存軟堆棧聯(lián)為一體，速度同寄存器，容量聯(lián)為一體，速度同寄存器，容量同主存同主存豐富的堆棧指令，直接操作寄存器堆棧數(shù)據(jù)，無(wú)需訪問(wèn)主存豐富的堆棧指令，直接操作寄存器堆棧數(shù)據(jù)，無(wú)需訪問(wèn)主存支持高級(jí)語(yǔ)言的編

20、譯（逆波蘭表達(dá)式，支持高級(jí)語(yǔ)言的編譯（逆波蘭表達(dá)式，Reverse Polish Notation）F=AF=A* *B+C/(D-E)B+C/(D-E)用用逆波蘭表達(dá)式表示為逆波蘭表達(dá)式表示為ABAB* *CDE-/+CDE-/+只需要出、入棧兩種操作，就可以完成只需要出、入棧兩種操作，就可以完成任何普通表達(dá)式的運(yùn)算任何普通表達(dá)式的運(yùn)算支持支持嵌套嵌套與與遞歸遞歸30v尋找操作數(shù)及其他信息的地址的技術(shù)稱為尋址技術(shù)尋找操作數(shù)及其他信息的地址的技術(shù)稱為尋址技術(shù) 內(nèi)容：編址方式、尋址方式和定位方式內(nèi)容：編址方式、尋址方式和定位方式 對(duì)象：寄存器、主存儲(chǔ)器、堆棧和輸入輸出設(shè)備對(duì)象：寄存器、主存儲(chǔ)器、

21、堆棧和輸入輸出設(shè)備 重點(diǎn)：分析各尋址技術(shù)優(yōu)缺點(diǎn)，如何選擇和確定尋址技術(shù)重點(diǎn)：分析各尋址技術(shù)優(yōu)缺點(diǎn)，如何選擇和確定尋址技術(shù)311、 編址方式編址方式編址單位：字、字節(jié)、位編址單位：字、字節(jié)、位字節(jié)編址時(shí)信息在存儲(chǔ)器中按整數(shù)邊界存儲(chǔ)字節(jié)編址時(shí)信息在存儲(chǔ)器中按整數(shù)邊界存儲(chǔ) （清華（清華p72 圖圖2.12） IBM370 字節(jié)（字節(jié)（8位）、半字（位）、半字（16位）、單字（位）、單字（32 位）、雙位）、雙字（字（64位），主存儲(chǔ)器寬度為位），主存儲(chǔ)器寬度為(64位）位） （P61圖圖2.13）多字節(jié)信息編排方法：多字節(jié)信息編排方法：小端排序小端排序(LitterEndian) ：高地址為高位字節(jié)

22、：高地址為高位字節(jié)大端排序大端排序(BigEndian)：高地址為低位字節(jié)：高地址為低位字節(jié)零地址空間個(gè)數(shù)零地址空間個(gè)數(shù)3個(gè)：通用寄存器、主存儲(chǔ)器、輸入輸出個(gè)：通用寄存器、主存儲(chǔ)器、輸入輸出2個(gè)：通用寄存器、主存儲(chǔ)器和輸入輸出個(gè)：通用寄存器、主存儲(chǔ)器和輸入輸出1個(gè)：全部空間個(gè)：全部空間0個(gè)：隱含編址（堆棧計(jì)算機(jī)）個(gè)：隱含編址（堆棧計(jì)算機(jī)）32v 數(shù)據(jù)類型、數(shù)據(jù)表示與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型、數(shù)據(jù)表示與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型數(shù)據(jù)類型：數(shù)值數(shù)值+ +操作。數(shù)據(jù)表示操作。數(shù)據(jù)表示+ +數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)； 數(shù)據(jù)表示數(shù)據(jù)表示：計(jì)算機(jī)硬件可直接識(shí)別和引用的數(shù)據(jù)類型。：計(jì)算機(jī)硬件可直接識(shí)別和引用的數(shù)據(jù)類型。 數(shù)據(jù)結(jié)構(gòu)

23、數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)數(shù)據(jù)類型的組織方式；軟件識(shí)別的數(shù)據(jù)類：結(jié)構(gòu)數(shù)據(jù)類型的組織方式；軟件識(shí)別的數(shù)據(jù)類型。型。v 常用高級(jí)數(shù)據(jù)表示方法：常用高級(jí)數(shù)據(jù)表示方法： 自定義（自定義（Self-defining）數(shù)據(jù)表示）數(shù)據(jù)表示 標(biāo)志符標(biāo)志符數(shù)據(jù)表示數(shù)據(jù)表示 數(shù)據(jù)描述符數(shù)據(jù)描述符數(shù)據(jù)表示數(shù)據(jù)表示 向量向量數(shù)據(jù)表示數(shù)據(jù)表示 堆棧堆棧數(shù)據(jù)表示數(shù)據(jù)表示33v2.2.1 尋址方式尋址方式v2.2.2 程序定位技術(shù)程序定位技術(shù)v2.2.3 指令格式的優(yōu)化設(shè)計(jì)指令格式的優(yōu)化設(shè)計(jì)34v尋址方式在指令中的兩種尋址方式在指令中的兩種指明方式指明方式占用操作碼的某些位（如占用操作碼的某些位（如DJS 200系列）系列）在地址碼部

24、分專門設(shè)置尋址方式位字段（如在地址碼部分專門設(shè)置尋址方式位字段（如VAX-11）v3種面向的尋址方式種面向的尋址方式 面向寄存器的尋址方式面向寄存器的尋址方式面向堆棧的尋址方式面向堆棧的尋址方式面向主存的尋址方式面向主存的尋址方式35v程序的定位：程序的定位：把指令和數(shù)據(jù)中的把指令和數(shù)據(jù)中的邏輯地址邏輯地址（相對(duì)地址）轉(zhuǎn)換成主存儲(chǔ)（相對(duì)地址）轉(zhuǎn)換成主存儲(chǔ)器的器的物理地理物理地理（絕對(duì)地址）的過(guò)程。（絕對(duì)地址）的過(guò)程。v邏輯地址邏輯地址指相對(duì)于本程序或程序段的相對(duì)地址（編程時(shí)使用）指相對(duì)于本程序或程序段的相對(duì)地址（編程時(shí)使用）v物理地址物理地址指程序在主存儲(chǔ)器中使用的實(shí)際地址。指程序在主存儲(chǔ)器中

25、使用的實(shí)際地址。什么時(shí)間變換？如何變換？什么時(shí)間變換？如何變換？36v常用高級(jí)數(shù)據(jù)表示方法：常用高級(jí)數(shù)據(jù)表示方法：自定義（自定義（Self-defining）數(shù)據(jù)表示）數(shù)據(jù)表示標(biāo)志符標(biāo)志符數(shù)據(jù)表示數(shù)據(jù)表示數(shù)據(jù)描述符數(shù)據(jù)描述符數(shù)據(jù)表示數(shù)據(jù)表示 向量向量數(shù)據(jù)表示數(shù)據(jù)表示 堆棧堆棧數(shù)據(jù)表示數(shù)據(jù)表示v程序定位技術(shù)程序定位技術(shù)直接定位（無(wú)須重定位）直接定位（無(wú)須重定位）靜態(tài)重（再）定位靜態(tài)重（再）定位動(dòng)態(tài)重（再）定位動(dòng)態(tài)重（再）定位37v直接定位方式直接定位方式在在編寫(xiě)編寫(xiě)程序時(shí)或程序時(shí)或編譯編譯源程序（裝入主存前）時(shí)，程序中的指源程序（裝入主存前）時(shí)，程序中的指令和數(shù)據(jù)的地址就已經(jīng)確定。令和數(shù)據(jù)的地址

26、就已經(jīng)確定。（不重定位）（不重定位）v靜態(tài)重（再）定位靜態(tài)重（再）定位在程序運(yùn)行之前在程序運(yùn)行之前，裝入主存的過(guò)程中由，裝入主存的過(guò)程中由裝入程序裝入程序一次性完成一次性完成地址變換，把指令和數(shù)據(jù)的邏輯地址全部變換成物理地址。地址變換，把指令和數(shù)據(jù)的邏輯地址全部變換成物理地址。如圖所示如圖所示。如。如DOS系統(tǒng)中的系統(tǒng)中的LINK過(guò)程。過(guò)程。v動(dòng)態(tài)重（再）定位動(dòng)態(tài)重（再）定位在程序執(zhí)行過(guò)程中在程序執(zhí)行過(guò)程中，當(dāng)訪問(wèn)到相應(yīng)的指令和數(shù)據(jù)時(shí)才進(jìn)行地，當(dāng)訪問(wèn)到相應(yīng)的指令和數(shù)據(jù)時(shí)才進(jìn)行地址變換，確定其物理地址。址變換，確定其物理地址。如圖所示。如圖所示。3839v優(yōu)點(diǎn)優(yōu)點(diǎn)：1. 可在一般機(jī)器上全部用軟件

27、實(shí)現(xiàn)?？稍谝话銠C(jī)器上全部用軟件實(shí)現(xiàn)。2. 可以對(duì)多個(gè)程序段組成的程序靜態(tài)鏈接，而且實(shí)現(xiàn)簡(jiǎn)單?？梢詫?duì)多個(gè)程序段組成的程序靜態(tài)鏈接，而且實(shí)現(xiàn)簡(jiǎn)單。v缺點(diǎn)缺點(diǎn)：1. 因?yàn)槌绦蚴窃趫?zhí)行之前一次性裝入到主存儲(chǔ)器中的，執(zhí)行因?yàn)槌绦蚴窃趫?zhí)行之前一次性裝入到主存儲(chǔ)器中的，執(zhí)行期間不能在主存中移動(dòng)，所以期間不能在主存中移動(dòng)，所以不利于提高主存儲(chǔ)器的利用率不利于提高主存儲(chǔ)器的利用率。2. 若程序所要求的存儲(chǔ)容量超過(guò)了分配給它的物理空間，則若程序所要求的存儲(chǔ)容量超過(guò)了分配給它的物理空間，則程序員必須采用程序員必須采用覆蓋結(jié)構(gòu)。覆蓋結(jié)構(gòu)。3. 多個(gè)用戶多個(gè)用戶不能共享不能共享已經(jīng)在主存儲(chǔ)器中的同一個(gè)程序。已經(jīng)在主存儲(chǔ)

28、器中的同一個(gè)程序。4041v優(yōu)點(diǎn)優(yōu)點(diǎn)：1.1.可以使用較小的主存分配單位，以提高主存儲(chǔ)器的利用率?？梢允褂幂^小的主存分配單位，以提高主存儲(chǔ)器的利用率。2.2.幾個(gè)程序可以共享存放在主存的同一程序段。幾個(gè)程序可以共享存放在主存的同一程序段。3.3.支持虛擬存儲(chǔ)器?？梢詾橛脩籼峁┮粋€(gè)比實(shí)際主存儲(chǔ)器物支持虛擬存儲(chǔ)器?？梢詾橛脩籼峁┮粋€(gè)比實(shí)際主存儲(chǔ)器物理空間大得多的邏輯地址空間。（不需要使用覆蓋技術(shù)）理空間大得多的邏輯地址空間。（不需要使用覆蓋技術(shù)）v 缺點(diǎn)缺點(diǎn)：1.1.需要硬件支持（基址寄存器、地址加法器等）。需要硬件支持（基址寄存器、地址加法器等）。 2.2.在虛擬存儲(chǔ)器中實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比

29、較復(fù)雜在虛擬存儲(chǔ)器中實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較復(fù)雜。42v 由兩部分組成：由兩部分組成：操作碼操作碼和和地址碼地址碼。v 操作碼主要包括兩部分內(nèi)容：操作碼主要包括兩部分內(nèi)容：操作種類：操作種類：加、減、乘、除、數(shù)據(jù)傳送、移位、轉(zhuǎn)移、加、減、乘、除、數(shù)據(jù)傳送、移位、轉(zhuǎn)移、 輸入輸出輸入輸出操作數(shù)描述操作數(shù)描述：（假如沒(méi)采用自定義數(shù)據(jù)類型）（假如沒(méi)采用自定義數(shù)據(jù)類型）數(shù)據(jù)的類型：數(shù)據(jù)的類型：定點(diǎn)數(shù)、浮點(diǎn)數(shù)、復(fù)數(shù)、定點(diǎn)數(shù)、浮點(diǎn)數(shù)、復(fù)數(shù)、 字符、字符串、邏輯數(shù)、向量字符、字符串、邏輯數(shù)、向量 進(jìn)位制：進(jìn)位制：2進(jìn)制、進(jìn)制、10進(jìn)制、進(jìn)制、16進(jìn)制進(jìn)制數(shù)據(jù)字長(zhǎng)：數(shù)據(jù)字長(zhǎng)：字節(jié)、半字、字、雙字字節(jié)、半字、

30、字、雙字OPOA43v操作數(shù)的地址：操作數(shù)的地址：直接地址、間接地址、立即數(shù)、寄存器編號(hào)、變址寄存器直接地址、間接地址、立即數(shù)、寄存器編號(hào)、變址寄存器編號(hào)編號(hào)v地址的附加信息：地址的附加信息：偏移量、塊長(zhǎng)度、跳距偏移量、塊長(zhǎng)度、跳距v尋址方式：尋址方式：直接尋址、間接尋址、立即數(shù)尋址、變址尋址、相對(duì)尋址、直接尋址、間接尋址、立即數(shù)尋址、變址尋址、相對(duì)尋址、寄存器尋址寄存器尋址44指令指令操作碼操作碼地址碼地址碼操作種類操作種類操作數(shù)描述操作數(shù)描述操作數(shù)地址操作數(shù)地址地址附加信息地址附加信息尋址方式尋址方式45v 主要目標(biāo)：主要目標(biāo)： 節(jié)省程序存儲(chǔ)空間（平均指令字長(zhǎng)最短）節(jié)省程序存儲(chǔ)空間（平均指

31、令字長(zhǎng)最短） 提高執(zhí)行速度（指令格式盡量規(guī)整，便于譯碼）提高執(zhí)行速度（指令格式盡量規(guī)整，便于譯碼）v 研究?jī)?nèi)容：研究?jī)?nèi)容： 操作碼操作碼的優(yōu)化表示的優(yōu)化表示 地址碼地址碼的優(yōu)化表示的優(yōu)化表示46v操作碼的三種編碼方法：操作碼的三種編碼方法： 定（等）長(zhǎng)編碼定（等）長(zhǎng)編碼、Huffman編碼編碼、擴(kuò)展編碼擴(kuò)展編碼編碼方式編碼方式整個(gè)整個(gè)OS所用所用指令的操作碼總位數(shù)指令的操作碼總位數(shù)改進(jìn)的改進(jìn)的百分比百分比8位定長(zhǎng)編碼位定長(zhǎng)編碼4-6-10擴(kuò)展編碼擴(kuò)展編碼Huffman編碼編碼301,248184,966172,34603943B-1700B-1700操作碼編碼方式比較操作碼編碼方式比較v改進(jìn)操

32、作碼編碼方式能夠節(jié)省程序存儲(chǔ)空間。改進(jìn)操作碼編碼方式能夠節(jié)省程序存儲(chǔ)空間。47v操作碼的操作碼的信息冗余量信息冗余量= =（操作碼的實(shí)際平均長(zhǎng)度（操作碼的實(shí)際平均長(zhǎng)度H H）/ /操作碼實(shí)際平均長(zhǎng)度操作碼實(shí)際平均長(zhǎng)度v操作碼的操作碼的實(shí)際平均長(zhǎng)度實(shí)際平均長(zhǎng)度 L L表示操作碼的實(shí)際平均長(zhǎng)度表示操作碼的實(shí)際平均長(zhǎng)度 p pi i表示第表示第i i種操作碼出現(xiàn)的概率種操作碼出現(xiàn)的概率 l li i表示第表示第i i種操作碼的實(shí)際長(zhǎng)度種操作碼的實(shí)際長(zhǎng)度niiilpL121loginiiHpp v操作碼的操作碼的最短平均長(zhǎng)度最短平均長(zhǎng)度可通過(guò)下式計(jì)算（可通過(guò)下式計(jì)算（信息源熵信息源熵）：）：-其中：其

33、中：P Pi i表示第表示第i i種操作碼在程序中出現(xiàn)的概率種操作碼在程序中出現(xiàn)的概率P21表表2.1481、定（等）長(zhǎng)編碼、定（等）長(zhǎng)編碼v相對(duì)最短操作碼長(zhǎng)度的相對(duì)最短操作碼長(zhǎng)度的信息冗余量信息冗余量為：為：NHNR22loglog2logLNv對(duì)于對(duì)于N個(gè)操作，采用定長(zhǎng)編碼時(shí)，所需的最小二進(jìn)個(gè)操作，采用定長(zhǎng)編碼時(shí)，所需的最小二進(jìn)制位數(shù)為（即操作碼的平均實(shí)際長(zhǎng)度制位數(shù)為（即操作碼的平均實(shí)際長(zhǎng)度L）：）：2LNv特點(diǎn)特點(diǎn)規(guī)整統(tǒng)一，便于譯碼、冗余量大規(guī)整統(tǒng)一，便于譯碼、冗余量大491)把所有指令按照在程序中出現(xiàn)的概率排序。把所有指令按照在程序中出現(xiàn)的概率排序。2)選選兩個(gè)概率最小的結(jié)點(diǎn)兩個(gè)概率最

34、小的結(jié)點(diǎn)，將其概率值相加合并成一新結(jié)點(diǎn)，將其概率值相加合并成一新結(jié)點(diǎn)，把新結(jié)點(diǎn)與其它還沒(méi)有合并的結(jié)點(diǎn)一起形成新結(jié)點(diǎn)集。把新結(jié)點(diǎn)與其它還沒(méi)有合并的結(jié)點(diǎn)一起形成新結(jié)點(diǎn)集。3)在新結(jié)點(diǎn)集中選取兩個(gè)概率最小的結(jié)點(diǎn)進(jìn)行合并，如此繼續(xù)在新結(jié)點(diǎn)集中選取兩個(gè)概率最小的結(jié)點(diǎn)進(jìn)行合并，如此繼續(xù)進(jìn)行下去，直至全部結(jié)點(diǎn)合并完畢。（進(jìn)行下去，直至全部結(jié)點(diǎn)合并完畢。（根結(jié)點(diǎn)值應(yīng)為根結(jié)點(diǎn)值應(yīng)為1）。）。4)每個(gè)結(jié)點(diǎn)都有兩個(gè)分支，分別用一位代碼每個(gè)結(jié)點(diǎn)都有兩個(gè)分支，分別用一位代碼0 和和1表示（表示（可以可以任選任選）。）。5)從根結(jié)點(diǎn)開(kāi)始，沿箭頭所指方向，到達(dá)屬于該指令的概率結(jié)從根結(jié)點(diǎn)開(kāi)始，沿箭頭所指方向，到達(dá)屬于該指令的

35、概率結(jié)點(diǎn)，把沿線所經(jīng)過(guò)的代碼組合起來(lái)就得到這條指令的操作碼點(diǎn)，把沿線所經(jīng)過(guò)的代碼組合起來(lái)就得到這條指令的操作碼編碼。編碼。50 假設(shè)一臺(tái)模型計(jì)算機(jī)共有假設(shè)一臺(tái)模型計(jì)算機(jī)共有7種不同的操作碼，如果采種不同的操作碼，如果采用固定長(zhǎng)操作碼則需要用固定長(zhǎng)操作碼則需要3位。已知各種操作碼在程序中出位。已知各種操作碼在程序中出現(xiàn)的概率如下表所示，計(jì)算采用現(xiàn)的概率如下表所示，計(jì)算采用Huffman編碼法的操作編碼法的操作碼碼平均長(zhǎng)度平均長(zhǎng)度，并計(jì)算固定長(zhǎng)操作碼和，并計(jì)算固定長(zhǎng)操作碼和Huffman操作碼相操作碼相對(duì)于最短編碼的對(duì)于最短編碼的信息冗余量信息冗余量。指令指令I(lǐng)1概率概率0.45I20.30I30

36、.15I40.05I50.03I60.01I70.01510.450.300.150.050.030.010.011.000.550.250.100.050.0201010101010101011011101111011111011111152指令序號(hào)指令序號(hào)概率概率Huffman編碼法編碼法操作碼長(zhǎng)度操作碼長(zhǎng)度I10.4501位位I20.30102位位I30.151103位位I40.0511104位位I50.03111105位位I60.011111106位位I70.011111116位位采用采用Huffman編碼法所得到的操作碼的平均長(zhǎng)度編碼法所得到的操作碼的平均長(zhǎng)度0.4510.3020.

37、1530.0540.0350.0160.0161.97（位）（位）也可以采用將也可以采用將非葉子結(jié)點(diǎn)值相加非葉子結(jié)點(diǎn)值相加的方法求得的方法求得（補(bǔ)充）（補(bǔ)充）=1+0.55+0.25+0.10+0.05+0.02=1.97（位）（位）53操作碼的最短平均長(zhǎng)度操作碼的最短平均長(zhǎng)度0.451.1520.301.7370.152.7370.054.3220.035.0590.016.6440.016.6441.95（位）（位）采用采用3位等定長(zhǎng)操作碼的信息冗余量為：位等定長(zhǎng)操作碼的信息冗余量為： Huffman編碼法的信息冗余量?jī)H為：編碼法的信息冗余量?jī)H為：iippH2log%35395.117lo

38、g7log22HR%0.197.195.1197.195.197.1R冗余太多冗余太多54vHuffman編碼的編碼的特點(diǎn)：特點(diǎn)： 短碼不可能是長(zhǎng)碼的前綴，從而保證譯碼的唯一性和實(shí)時(shí)性。短碼不可能是長(zhǎng)碼的前綴，從而保證譯碼的唯一性和實(shí)時(shí)性。 Huffman編碼不唯一，其最長(zhǎng)編碼的長(zhǎng)度也可能不同，但操編碼不唯一，其最長(zhǎng)編碼的長(zhǎng)度也可能不同，但操作碼的平均碼長(zhǎng)肯定是唯一的。作碼的平均碼長(zhǎng)肯定是唯一的。 Huffman編碼中編碼中最長(zhǎng)編碼的長(zhǎng)度最長(zhǎng)編碼的長(zhǎng)度可能比使用定長(zhǎng)編碼的長(zhǎng)度可能比使用定長(zhǎng)編碼的長(zhǎng)度長(zhǎng)，但其長(zhǎng)，但其平均碼長(zhǎng)平均碼長(zhǎng)比定長(zhǎng)編碼平均碼長(zhǎng)短得多，比定長(zhǎng)編碼平均碼長(zhǎng)短得多，冗余少冗余少

39、。vHuffman操作碼的操作碼的主要缺點(diǎn)：主要缺點(diǎn)： 操作碼長(zhǎng)度很操作碼長(zhǎng)度很不規(guī)整不規(guī)整，硬件譯碼困難，硬件譯碼困難 與地址碼共同組成固定長(zhǎng)的指令比較困難與地址碼共同組成固定長(zhǎng)的指令比較困難55v 由定長(zhǎng)編碼法與由定長(zhǎng)編碼法與Huffman編碼法相編碼法相結(jié)合形成結(jié)合形成。操作。操作碼不定長(zhǎng)，但只有有限的幾種長(zhǎng)度。碼不定長(zhǎng)，但只有有限的幾種長(zhǎng)度。v 概率高的用短編碼，概率低的用長(zhǎng)編碼概率高的用短編碼，概率低的用長(zhǎng)編碼。其中某些。其中某些編碼組合（碼點(diǎn)）要留作編碼擴(kuò)展之用。編碼組合（碼點(diǎn)）要留作編碼擴(kuò)展之用。v 例如：將前例改例如：將前例改為為1-2-3-5不等長(zhǎng)擴(kuò)展編碼不等長(zhǎng)擴(kuò)展編碼法，和

40、法，和2-4等長(zhǎng)擴(kuò)展編碼等長(zhǎng)擴(kuò)展編碼法，可得到以下編碼方案：法，可得到以下編碼方案：56序號(hào)序號(hào)概率概率 1-2-3-5不等長(zhǎng)擴(kuò)展編碼不等長(zhǎng)擴(kuò)展編碼I10.450I20.3010I30.15110I40.0511100I50.0311101I60.0111110I70.01111112-4等長(zhǎng)擴(kuò)展編碼等長(zhǎng)擴(kuò)展編碼0001101100110111101111平均長(zhǎng)度平均長(zhǎng)度2.02.2信息冗余量信息冗余量2.5%11.4%7條指令的操作碼擴(kuò)展編碼法條指令的操作碼擴(kuò)展編碼法57v常用高級(jí)數(shù)據(jù)表示方法：常用高級(jí)數(shù)據(jù)表示方法：自定義（自定義（Self-defining）數(shù)據(jù)表示）數(shù)據(jù)表示標(biāo)志符標(biāo)志符數(shù)

41、據(jù)表示數(shù)據(jù)表示數(shù)據(jù)描述符數(shù)據(jù)描述符數(shù)據(jù)表示數(shù)據(jù)表示 向量向量數(shù)據(jù)表示數(shù)據(jù)表示 堆棧堆棧數(shù)據(jù)表示數(shù)據(jù)表示v程序定位技術(shù)程序定位技術(shù)直接定位（無(wú)須重定位）直接定位（無(wú)須重定位）靜態(tài)重（再）定位靜態(tài)重（再）定位動(dòng)態(tài)重（再）定位動(dòng)態(tài)重（再）定位58v1-2-3-5不等長(zhǎng)擴(kuò)展編碼不等長(zhǎng)擴(kuò)展編碼法，其操作碼最短平均長(zhǎng)度為：法，其操作碼最短平均長(zhǎng)度為：L=0.4510.3020.153 (0.050.030.010.01)5 = 2.00信息冗余量為：信息冗余量為：v2-4等長(zhǎng)擴(kuò)展編碼等長(zhǎng)擴(kuò)展編碼法，其操作碼最短平均長(zhǎng)度為法，其操作碼最短平均長(zhǎng)度為：L= (0.45+0.30+0.15) 2+ (0.05+

42、0.03+0.01+0.01) 4 = 2.20信息冗余量為：信息冗余量為：v注意注意：使用不同的擴(kuò)展方式，所能表示的指令條數(shù)是不同的。：使用不同的擴(kuò)展方式，所能表示的指令條數(shù)是不同的。 X-YX-Y擴(kuò)展法：擴(kuò)展法：X X、Y Y表示操作碼的位數(shù)表示操作碼的位數(shù) X/YX/Y擴(kuò)展法：擴(kuò)展法：X X、Y Y表示擴(kuò)展出的指令條數(shù)。表示擴(kuò)展出的指令條數(shù)。 例：例：4-8-124-8-12的的15/15/1515/15/15和和8/64/5128/64/512編碼法（編碼法（ P22P22 ）%5 . 200. 295. 11R%4 .1120. 295. 11R60編碼方法編碼方法各種不同長(zhǎng)度操作碼

43、的指令條數(shù)各種不同長(zhǎng)度操作碼的指令條數(shù)總指令條數(shù)總指令條數(shù)4位操作碼位操作碼6位操作碼位操作碼10位操作碼位操作碼15/3/1615316348/31/1683116558/30/3283032708/16/2568162562804/32/2564322562924-6-10不等長(zhǎng)擴(kuò)展編碼法舉例不等長(zhǎng)擴(kuò)展編碼法舉例61v某模型機(jī)的各條指令的使用頻率如下：某模型機(jī)的各條指令的使用頻率如下： ADD：43% SHR：1% SUB：13% CLL：2% JOM：6% CLA：22% STO：5% STP：1% JMP：7% 請(qǐng)分別用請(qǐng)分別用Huffman編碼法編碼法和和等長(zhǎng)擴(kuò)展編碼法等長(zhǎng)擴(kuò)展編碼法

44、為其設(shè)為其設(shè)計(jì)操作碼，并計(jì)算平均操作碼長(zhǎng)度。計(jì)操作碼，并計(jì)算平均操作碼長(zhǎng)度。62vHuffmanHuffman編碼法編碼法1.001.000.010.010.010.010.020.020.050.050.060.060.070.070.130.130.220.220.430.430.020.020.040.040.090.090.220.220.130.130.350.350.570.57111111100000000163指令指令指令使用指令使用頻度頻度piHuffman編碼編碼操作碼長(zhǎng)操作碼長(zhǎng)度度li2-4擴(kuò)展碼擴(kuò)展碼編碼編碼操作碼長(zhǎng)操作碼長(zhǎng)度度liADD0.4301002CLA0.22

45、1003012SUB0MP0.071100410014JOM0.061101410104STO0.051110410114CLL0.0211110511004SHR0.01111110611014STP0.0111111161110464vHuffman編碼平均碼長(zhǎng)編碼平均碼長(zhǎng):0.431+0.223+0.133+0.074+0.06 4+0.054 +0.025 +0.016+0.016 =2.42位位v2-4擴(kuò)展平均碼長(zhǎng)擴(kuò)展平均碼長(zhǎng):（0.43+0.22）2+（0.13+0.07+0.06+0.05+0.02 +0.01+0.01）4 =2.7位位請(qǐng)大家練習(xí)一下本

46、題用請(qǐng)大家練習(xí)一下本題用2-5不等長(zhǎng)擴(kuò)展法的結(jié)果不等長(zhǎng)擴(kuò)展法的結(jié)果65主存寬度主存寬度主存寬度主存寬度6667v指令格式的優(yōu)化設(shè)計(jì)指令格式的優(yōu)化設(shè)計(jì)主要目標(biāo)：主要目標(biāo)： 節(jié)省程序存儲(chǔ)空間（縮短指令的平均字長(zhǎng)）節(jié)省程序存儲(chǔ)空間（縮短指令的平均字長(zhǎng)） 提高執(zhí)行速度（指令格式盡量規(guī)整，便于譯碼）提高執(zhí)行速度（指令格式盡量規(guī)整，便于譯碼） 研究?jī)?nèi)容：研究?jī)?nèi)容： 操作碼操作碼的優(yōu)化表示的優(yōu)化表示 地址碼地址碼的優(yōu)化表示的優(yōu)化表示 操作碼的優(yōu)化：操作碼的優(yōu)化：最短編碼長(zhǎng)度（最短編碼長(zhǎng)度（信息源熵信息源熵公式）、信息冗余度公式）、信息冗余度等（定）長(zhǎng)編碼、等（定）長(zhǎng)編碼、HuffmanHuffman編碼、擴(kuò)

47、展編碼編碼、擴(kuò)展編碼68v操作碼的優(yōu)化表示操作碼的優(yōu)化表示等（定）長(zhǎng)編碼等（定）長(zhǎng)編碼 格式最規(guī)整、冗余最大格式最規(guī)整、冗余最大Huffman編碼編碼 最小概率合并法最小概率合并法 代碼平均長(zhǎng)度算法代碼平均長(zhǎng)度算法 冗余最小、格式最不規(guī)整冗余最小、格式最不規(guī)整擴(kuò)展編碼擴(kuò)展編碼 等長(zhǎng)擴(kuò)展、不等長(zhǎng)擴(kuò)展等長(zhǎng)擴(kuò)展、不等長(zhǎng)擴(kuò)展 X-Y-Z、X/Y/Z 冗余量和規(guī)整性居中冗余量和規(guī)整性居中Nn2log69指令字格式的優(yōu)化指令字格式的優(yōu)化v信息在存儲(chǔ)器中的存放方式信息在存儲(chǔ)器中的存放方式任意存放任意存放問(wèn)題：?jiǎn)栴}：信息跨存儲(chǔ)單元，降低訪問(wèn)速度信息跨存儲(chǔ)單元，降低訪問(wèn)速度00081018202870指令字格式

48、的優(yōu)化指令字格式的優(yōu)化按整數(shù)邊界存儲(chǔ)按整數(shù)邊界存儲(chǔ)（各類信息存儲(chǔ)的起始地址要求）（各類信息存儲(chǔ)的起始地址要求）字節(jié)（字節(jié)（1B）：）：半字（半字（2B） ：0單字（單字（4B） ： 0 0雙字（雙字（8B） ： 0 0 00008101871指令字格式的優(yōu)化指令字格式的優(yōu)化v可采用不同的尋址方式、地址制、地址形式和長(zhǎng)度以可采用不同的尋址方式、地址制、地址形式和長(zhǎng)度以及多種指令字長(zhǎng)與可變長(zhǎng)操作碼結(jié)合對(duì)指令字優(yōu)化。及多種指令字長(zhǎng)與可變長(zhǎng)操作碼結(jié)合對(duì)指令字優(yōu)化。v只優(yōu)化只優(yōu)化OP，不優(yōu)化，不優(yōu)化OA（如采用等長(zhǎng)地址碼），發(fā)揮（如采用等長(zhǎng)地址碼），發(fā)揮不了操作碼優(yōu)化帶來(lái)的好處不了操作碼優(yōu)化帶來(lái)的好處7

49、2定長(zhǎng)指令字內(nèi)實(shí)現(xiàn)多地址制定長(zhǎng)指令字內(nèi)實(shí)現(xiàn)多地址制73定長(zhǎng)指令字同地址制下的多種地址形式和長(zhǎng)度定長(zhǎng)指令字同地址制下的多種地址形式和長(zhǎng)度74IBM 370 IBM 370 指令的主要格式指令的主要格式( (多種指令字長(zhǎng)多種指令字長(zhǎng)) )75v某模型機(jī)共某模型機(jī)共7條指令，使用頻度分別為條指令，使用頻度分別為35%，25%，20%，10%，5%，3%，2%。該模型機(jī)有。該模型機(jī)有8位和位和16位兩位兩種指令字長(zhǎng)，采用種指令字長(zhǎng)，采用2-4擴(kuò)展操作碼擴(kuò)展操作碼。8位長(zhǎng)指令為位長(zhǎng)指令為R-R二二地址型，地址型，16位長(zhǎng)指令為位長(zhǎng)指令為R-M二地址變址尋址型，變址范二地址變址尋址型，變址范圍為（圍為（-

50、128127）。）。(1)設(shè)計(jì)該機(jī)的兩種指令格式，標(biāo)出各字段位數(shù)并給出操作設(shè)計(jì)該機(jī)的兩種指令格式，標(biāo)出各字段位數(shù)并給出操作碼編碼。碼編碼。(2)該機(jī)允許使用多少個(gè)可編址的通用寄存器，多少個(gè)變址該機(jī)允許使用多少個(gè)可編址的通用寄存器，多少個(gè)變址寄存器？寄存器？(3)計(jì)算操作碼的平均碼長(zhǎng)。計(jì)算操作碼的平均碼長(zhǎng)。76v2-4擴(kuò)展操作碼編碼擴(kuò)展操作碼編碼指令號(hào)指令號(hào)指令的使用頻指令的使用頻率率2-4擴(kuò)展操作碼編碼擴(kuò)展操作碼編碼135% 00225% 01320% 10410% 110055% 110163% 111072% 1111R-RR-M77v2）指令格式）指令格式R-RR-R型：型：操作碼操作碼

51、OP源寄存器源寄存器Rs目的寄存器目的寄存器Rd 2位位 3位位 3位位R-M型：型： 操作碼操作碼OP源寄存器源寄存器Rs變址寄存器變址寄存器Rx偏移地址偏移地址 4位位 3位位 1位位 8位位v3）平均長(zhǎng)度）平均長(zhǎng)度 0.352+0.252+0.22+0.14+0.054+ 0.034 +0.024 =2.4位位78v指令系統(tǒng)的功能設(shè)計(jì)有指令系統(tǒng)的功能設(shè)計(jì)有兩個(gè)截然相反的方向兩個(gè)截然相反的方向： 復(fù)雜指令系統(tǒng)復(fù)雜指令系統(tǒng)CISC(Complex Instruction Set Computer)增強(qiáng)指令功能，設(shè)置功能復(fù)雜的指令增強(qiáng)指令功能，設(shè)置功能復(fù)雜的指令 面向目標(biāo)代碼、面向高級(jí)語(yǔ)言、面

52、向操作系統(tǒng)優(yōu)化面向目標(biāo)代碼、面向高級(jí)語(yǔ)言、面向操作系統(tǒng)優(yōu)化 用一條指令代替一串指令。用一條指令代替一串指令。 精簡(jiǎn)指令系統(tǒng)精簡(jiǎn)指令系統(tǒng)RISC(Reduced Instruction Set Computer) vCISC特點(diǎn)：特點(diǎn)： 指令系統(tǒng)龐大，指令系統(tǒng)龐大，100條條 可變長(zhǎng)指令字格式可變長(zhǎng)指令字格式 ，如，如IBM370 多種尋址方式多種尋址方式 包括許多使用頻率不高的特殊功能指令包括許多使用頻率不高的特殊功能指令P25 表表2.579v指令系統(tǒng)龐大，相應(yīng)硬件復(fù)雜，增加研制時(shí)間和成本且易造指令系統(tǒng)龐大，相應(yīng)硬件復(fù)雜，增加研制時(shí)間和成本且易造成設(shè)計(jì)錯(cuò)誤。成設(shè)計(jì)錯(cuò)誤。v指令功能的不均衡，不

53、利于先進(jìn)體系結(jié)構(gòu)（如流水線）的實(shí)指令功能的不均衡，不利于先進(jìn)體系結(jié)構(gòu)（如流水線）的實(shí)現(xiàn)。現(xiàn)。v優(yōu)化編譯困難，難生成高效目標(biāo)程序，編譯程序本身龐大。優(yōu)化編譯困難，難生成高效目標(biāo)程序，編譯程序本身龐大。v多數(shù)指令的使用頻率不高，多數(shù)指令的使用頻率不高，80%20%規(guī)律規(guī)律。 如如VAX-11/780：304條指令、條指令、16種尋址方式、種尋址方式、7類類14種數(shù)種數(shù)據(jù)表示；據(jù)表示；IBM 360、370 、VAX8600、MC68020 控制部分控制部分占整個(gè)占整個(gè)CPU芯片面積芯片面積60%80IntelIntel80888088 處理機(jī)指令系統(tǒng)使用頻度和執(zhí)行時(shí)間統(tǒng)計(jì)處理機(jī)指令系統(tǒng)使用頻度和執(zhí)

54、行時(shí)間統(tǒng)計(jì) （C C 語(yǔ)言編譯程序和語(yǔ)言編譯程序和 PROLOGPROLOG 解釋程序）解釋程序） 使用頻度使用頻度 執(zhí)行時(shí)間執(zhí)行時(shí)間 序號(hào)序號(hào) 指令指令 累計(jì)累計(jì) 序號(hào)序號(hào) 指令指令 累累 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 1616 1717 1818 1919 2020 MOVMOV PUSHPUSH CMPCMP JMPccJMPcc ADDADD POPPOP RETRET CALLCALL JUMPJUMP SUBSUB INCINC LESLES REPNREPN IMULIMUL D

55、ECDEC XORXOR REPNZREPNZ CLDCLD LOOPccLOOPcc TESTTEST 24.8524.85 10.3610.36 10.2810.28 9.039.03 6.806.80 4.144.14 3.923.92 3.893.89 2.702.70 2.432.43 2.372.37 1.981.98 1.921.92 1.691.69 1.371.37 1.131.13 0.780.78 0.540.54 0.520.52 0.400.40 24.8524.85 35.2135.21 45.4945.49 54.5254.52 61.3261.32 65.466

56、5.46 69.3869.38 73.2773.27 75.9775.97 78.4078.40 80.7780.77 82.7582.75 84.6784.67 86.3686.36 87.7387.73 88.8688.86 89.6489.64 90.1890.18 90.7090.70 91.1091.10 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 1616 1717 1818 1919 2020 IMULIMUL MOVMOV PUSHPUSH JMPccJMPcc CMPCMP CALLCAL

57、L RETRET ADDADD JMPJMP LESLES POPPOP DECDEC SUBSUB XORXOR INCINC LOOPccLOOPcc LDSLDS CMPSCMPS MOVSMOVS JCXZJCXZ 19.5519.55 17.4417.44 11.1111.11 10.5510.55 7.807.80 7.277.27 4.854.85 3.273.27 3.263.26 2.832.83 2.612.61 1.491.49 1.181.18 1.041.04 0.990.99 0.640.64 0.640.64 0.440.44 0.390.39 0.370.37

58、19.5519.55 36.9936.99 48.1048.10 58.6558.65 66.4566.45 73.7273.72 78.5778.57 81.8481.84 85.1085.10 87.9387.93 90.5490.54 92.092.03 3 93.2193.21 94.2594.25 95.2495.24 95.8895.88 96.5296.52 96.9696.96 97.3597.35 97.7297.72 81vRISC特點(diǎn)：特點(diǎn)：減少指令（減少指令（100條）和尋址（條）和尋址（24種）的種類。種）的種類。 大多數(shù)指令在單周期內(nèi)完成。大多數(shù)指令在單周期內(nèi)完成。

59、CPI1采用采用LOAD/STORE結(jié)構(gòu)。僅此兩指令可訪問(wèn)存儲(chǔ)器結(jié)構(gòu)。僅此兩指令可訪問(wèn)存儲(chǔ)器硬聯(lián)控制為主、固件（微程序）實(shí)現(xiàn)為輔硬聯(lián)控制為主、固件（微程序）實(shí)現(xiàn)為輔。固定的指令字格式。固定的指令字格式。優(yōu)化編譯設(shè)計(jì)技術(shù)。優(yōu)化編譯設(shè)計(jì)技術(shù)。設(shè)置大量的通用寄存器，并采用設(shè)置大量的通用寄存器，并采用重疊寄存器窗口重疊寄存器窗口技術(shù)。技術(shù)。指令執(zhí)行采用流水線技術(shù)、延遲加載和延時(shí)轉(zhuǎn)移技術(shù)。指令執(zhí)行采用流水線技術(shù)、延遲加載和延時(shí)轉(zhuǎn)移技術(shù)。Cache結(jié)構(gòu)（結(jié)構(gòu)（2級(jí)級(jí)Cache、I-Cache 、 D-Cache ）v高效的流水線高效的流水線和和優(yōu)化編譯技術(shù)優(yōu)化編譯技術(shù)是現(xiàn)代是現(xiàn)代RISC系統(tǒng)特別注重的。系

60、統(tǒng)特別注重的。v如如RISC-I、 RISC-II?？刂撇糠挚刂撇糠终颊麄€(gè)占整個(gè)CPU芯片面積芯片面積10%82 TCPU=In CPI Tc 10ns2ns 1.11.4 1.31.4 RISC 33ns5ns 215 1 CISC TcCPIIn類型類型83 P31 表表2.6 請(qǐng)自學(xué)退偶（混合）請(qǐng)自學(xué)退偶（混合）CISC/RISC和后和后RISC84v指令系統(tǒng)功能設(shè)計(jì)指令系統(tǒng)功能設(shè)計(jì)要求要求：完整性（完整性（Completeness）：）：通用計(jì)算機(jī)所應(yīng)具備的基本指通用計(jì)算機(jī)所應(yīng)具備的基本指令種類。令種類。數(shù)據(jù)傳送類指令，運(yùn)算類指令，程序控制類指令、輸入輸數(shù)據(jù)傳送類指令，運(yùn)算類指令，程序