計算機系統(tǒng)結構電子教案

計算機系統(tǒng)結構

主講：華中科技大學計算機學院林安

教學計劃

4。

?教材：?總學時善

An-14

《計算機系統(tǒng)結構》（第二版）-.氧

升24

鄭緯民等-杼

A3$:W

清華大學出版社-mr血

o"44

.n普

左56

?參考書：-弓6:2

左

量

《計算機系統(tǒng)結構-杼76

復習與考試指導》-"8第2

鄭緯民等-呂

9Oe2

高等教育出版社-VI早

2001.9.1計算機系統(tǒng)結構2

第一章基本概念(P1)

本章介紹計算機系統(tǒng)結構的一些基本知識。包括定性知識和定

量知識兩大組內容。為了便于學習，本章各節(jié)重新編號，與教材編

號不同。

定性知識：本課程經常使用的一些名詞概念，以及對計算機的

定性認識、分析方法。

定量知識：對計算機性能進行定量評價的幾個重要公式。

2001.9.1計算機系統(tǒng)結構3

1.1定性知識幾個基本概念

上1、.1什么是計算機系統(tǒng)結構？（P4）

英文名稱：ComputerArchitectrue

計算機系統(tǒng)結構（也叫“計算機體系結構”）￡：傳授計算機整

機（硬軟件統(tǒng)一條件下）設計的重大技術知識。

Architectrue的英文原義是“建筑學”。

“計算機系統(tǒng)結構”作為事物名稱:使用者必須了解的機器外部特

性知識（廣義定義）。在本課程中“使用者”目前特指最低級語言的程

序員，“外部特性”特指整個硬件的外部特性（狹義定義）。

透明透概念:使用者可以不了解的知識。

2001.9.1計算機系統(tǒng)結構4

“計算機系統(tǒng)結構”狹義定義包含的內容（P4）

1.數(shù)據(jù)表示（硬件能夠直接識別和處理的數(shù)據(jù)類型和格式等）；

2.尋址方式（包括最小尋址單位、尋址方式的種類、表示和地址計算等）；

3.寄存器組織（包括各種寄存器的配置數(shù)目和功能定義）；

4.指令系統(tǒng)（包括機器指令的操作類型和格式、指令間的排序方式和控制機

構等）；

5.存儲系統(tǒng)（包括編址方式、存儲容量、最大編址空間等）；

6.中斷機構（中斷源的分類管理和中斷服務功能設計）；

7.機器工作狀態(tài)（如管態(tài)、目態(tài)等）的定義和切換；

8.輸入/輸出子系統(tǒng)結構與管理；

9.信息保護手段及其實現(xiàn)。

2001.9.1計算機系統(tǒng)結構5

1.1.2計算機系統(tǒng)的多級層次模型（P3）

第5級占用應用語用機需一特定應用用戶（使用特定應用語言）

|（經應用程序翻譯成高級語言）

第4級|逋用高級語用機寤—高級語言程序員（使用通用高級語言）

|（經編譯逑序翻譯成匯編語言）

第3級|匯編語;機器一修匚編語言程序員（使用匯編語言）

|（經超牌序翻譯成機器語言、操作系統(tǒng)原語）

第2級|操作系統(tǒng)語言嗝一操作系統(tǒng)用戶（使用操作系統(tǒng)原語）

|（經原語解釋子程序翻譯成機器語言）

第1級|傳統(tǒng)機器語占—傳統(tǒng)機器程序員（使用二進制機器語言）

|（由微程■解釋成微指令序列）

第0級|微指令」；i機N□一微指令程序員（使用微指令語言）

|（由硬件譯碼器解釋成控制信號序列）

圖1.1計算機系統(tǒng)的多級層次模型

2001.9.1計算機系統(tǒng)結構6

1.1.3其他重要名詞概念(自學)

［計灣機組成］計算機系統(tǒng)結構的邏輯實現(xiàn)。(P5)

［計算機實現(xiàn)］計算機組成的物理實現(xiàn)。(P5)

［計算機系統(tǒng)設計的3種主要方法］:“由下往上”、“由上往下”、

“由中間開始“。(P14)

［系列機］(P23)

［兼容性］(P24)

［模擬］(P24)

［仿真］(P24)

［虛擬機］(P24)

［宿主機］(P24)

［并行］求解一個問題的若干操作在時間安排上的可重疊性。

2001.9.1計算機系統(tǒng)結構7

1.1.4馮.諾依曼(VonNeumann)型機器的特點(P22)

傳統(tǒng)計算機又稱為馮.諾依曼型機器，它由運算器、控制器、存

儲器、輸入設備和輸出設備5部分組成，并具有如下特點：

1.以運算器為數(shù)據(jù)流動中樞，以控制器為控制命令中樞；

2.存儲程序并且執(zhí)行，程序象數(shù)據(jù)一樣可以修改；

3.存儲器按地址訪問，線性順序編址；

4.程序順序執(zhí)行；

5.指令由操作碼與操作數(shù)兩部分組成；

6.數(shù)據(jù)用二進制編碼；

7.機器由硬件與軟件組成，硬件功能不能改變。

2001.9.1計算機系統(tǒng)結構8

1.1.5現(xiàn)代計算機系統(tǒng)的分類（Flynn分類法，P6）

按照指令流和數(shù)據(jù)流的多倍性狀況把計算機分為：

1.單指令流單數(shù)據(jù)流(SISD--SingleInstructionStreamSingle

DataStream)

2.單指令流多數(shù)據(jù)流(SIMD--SingleInstructionStream

MultipleDataStream)

3.多指令流單數(shù)據(jù)流(MISD--MultipleInstructionStream

SingleDataStream)

4.多指令流多數(shù)據(jù)流(MIMD--MultipleInstructionStream

MultipleDataStream)

例題：P32,題7,題8,題9。

2001.9.1計算機系統(tǒng)結構9

1.2定量知識3個性能公式

1.2.1Amdahl定律(加快經常性事件原理，P9)

T1

S——=----------------

nTF

n(1-^)+-7

Se

其中：Sn全局加速比；

To原執(zhí)行時間(old)；

Tn新執(zhí)行時間(new)；

Se被改進部分的局部加速比；

Fe被改進部分原執(zhí)行時間占原來總時間的百分比。

2001.9.1計算機系統(tǒng)結構10

Amdah1定律的推導

改進之前程序運行總時間可寫為：T=T(1-Fe+Fe),

改進之后由于其中部分操作加快，總時間降為：

F

Tn=Tova-Fe+上c,)

Je

根據(jù)加速比定義，有：s.=〃=-----1—―

。(1-T---

2001.9.1計算機系統(tǒng)結構11

Amdahl定律的圖形

從圖1.2可以看出，增大Se和Fe對Sn都有提升作用；但當Fe固定時

,一味增大Se對Sn的作用會越來越不顯著。

圖1.2Amdahl定律的圖形

2001.9.1計算機系統(tǒng)結構12

1.2.2CPI與程序執(zhí)行時間Te(Pll)

CPI是衡量CPU執(zhí)行指令效率的重要指標。讓我們先考慮一個標準測

速程序的全部執(zhí)行時間Te和其中所有第i種指令的累計時間Ti,易知

T=ICxCPIxCYCLE

T=lCixCPLxCYCLE

1n

其中：CYCLE=—,IC=￡lC]

fZ=1

另一方面，我們又可以寫

nnn

Te=￡Ti=￡gXCPLXCYCLE}=^(/CxCP/)XCYCLE

i=\z=li=\_

比較上面第一式與最后一式，可以得到CPI與CPIi的關系

n

ICXCPI=XCP/)

Z=1

或者寫為CPI=Z(—Lxcm,它表明CP/為所有C/V,.的加權平均值。

Z=1ic1

2001.9.1計算機系統(tǒng)結構13

1.2.3每秒百萬指令數(shù)MIPS與每秒百萬浮點數(shù)MFLOPS

(P11)

ICf

MIPS=—xl0-6=----------------x10-6=，二x10-6,主要用于標量計算機；

TeICxCPIxCYCLECPI

MIPS

MFLOPS=,主要用于向量計算機。

每次浮點運算所需指令條數(shù)

例題：P10,例1.1?例1.5。

P33,題12，題13,題14o

2001.9.1計算機系統(tǒng)結構14

例題選講（1）

?例1.1（P10）

Amdahl定律公式,已知：Fe=0.4,Se=10,求Sn。

它說明局部（40%）的大幅度改進（10倍）對全局的作用要小得

多（1.56倍）。

?例1.2（P10）

Amdahl定律公式，已知方案1：Fei=0.2,Sei=10,求Sm；

已知方案2：Fe2=0.5,Se2=2,求S112。

它說明大范圍的小幅度改進（方案2）效果可能更好。

2001.9.1計算機系統(tǒng)結構15

例題選講(2)

?例1.3(P11)

CPI公式，注意該公式中的指令數(shù)百分比不同于Amdahl定律

中的時間百分比Fe,避免用錯。

已知：ICFP/IC=25%,IC非FP/IC=75%；

ICFPSQR/IC=2%,IC非FPSQR/IC=98%。

改進前：CPIFP=4.0,CPI非FP=1.33；

CPIFPSQR=20,CPI非FPSQR=?

改進后：CPIFP=2.0,CPI非FP=老值；

CPIFPSQR=2.0,CPI非FPSQR=老值。

求：兩種方案改進后的CPI。

分析：方案2缺一個條件CPI非FPSQR，但改進前用兩種方法算出

的CPI應該是相同的，所以由

CPI老=CPIFPXICFP/IC+CPI非FPXIC非FP/IC

=CPIFPSQRxICFPSQR/IC+CPI非FPSQRXIC非FPSQR/IC

2001.9.1計算機系統(tǒng)結構16

例題選講（3）

解出CPI非FPSQR=80/49

現(xiàn)在分別用兩種方案改進后的參數(shù)代入公式，算出新的CPI為

1.64和1.5,顯然CPI值較小的方案2較好。

教材的解法中有兩個小公式值得注意，一個是：

IC

CPI..-=CPI.-（CPI.-CPI）

新老丁「r'，老I新，

IC

它的實質就是

時鐘周期數(shù)總改變量=（GP/浙一C7VQ/C=（C7V,新一C7V-）/￡

另一個公式較容易理解：

2001.9.1計算機系統(tǒng)結構17

例題選講(4)

?例1.4(P12)

Te公式，其中CPI用相應的公式代換

nic

q=匯(CP//xi-ICXCYCLE

z=lIC

對A機器，已知CPI轉=2,IC轉/ICA=20%,CPI非轉=1,IC非轉/ICA=80%,

Te_A=l.2XICAxCYCLEA；

對B機器，從題義可知，IC比轉=IC轉，ICB=ICAX80%,CYCLEB

義比轉比轉轉/

=1.25CYCLEA，CPI=2,所以IC/ICB=IC(ICAX80%)

=25%,CPI非比轉=1,IC非比轉/ICB=75%,

Te_B=1.25XICBxCYCLEB

=1.25X80%XICAX1.25XCYCLEA

=1.25XICAXCYCLEA>Te_A

顯然A機器快一些。

2001.9.1計算機系統(tǒng)結構18

例題選講(5)

?例1.5(P12)

Te公式，改動上題中CYCLEB=1.1XCYCLEA,則最后

Te_B=1.25XICBxCYCLEB

=1.25X80%XICAX1.1XCYCLEA

=1.1XICAxCYCLEA<Te_A

這時B機器快一些。

Sn.

?題12(P33)20------------------------

zI

Amdahl定律公式，代入已知量/\

?/{

Se=20變成一元函數(shù)10.5/

Z/

Sn=20/(20-19Fe)/1/]

用三點作圖法作出關系曲線。L8/'J:

1------------1_

00.51Fe

2001.9.1計算機系統(tǒng)結構19

例題選講（6）

?題13(P33)

Amdahl定律公式,代入已知量Se=20,Sn=2,解出Fe=10/19

?題14(P33)

Amdahl定律公式,代入已知量Se=20,Sn=10,解出Fe=18/19

2001.9.1計算機系統(tǒng)結構20

本章小結

本章從定性知識和定量知識兩個方面介紹計算機系統(tǒng)結構的基本概

念。有關重點如下：

(1)計算機系統(tǒng)結構的廣義定義與狹義定義(9項內容)，計算機系統(tǒng)結

構與計算機組成的主要分工；

(2)計算機系統(tǒng)的多級層次模型(6級)，以及基于該模型的透明性判斷

方法；

(3)計算機實現(xiàn)、計算機系統(tǒng)設計的主要思路、模擬、仿真、虛擬機、

宿主機、系列機、兼容性、并行性等重要名詞的含義；

(4)馮.諾依曼型機器的7個特點；

(5)現(xiàn)代計算機系統(tǒng)分類的Flynn法(4類)；

(6)Amdahl定律；

(7)平均周期數(shù)CPI公式，程序執(zhí)行時間Te公式；

(8)每秒百萬指令數(shù)MIPS公式，每秒百萬浮點數(shù)MFLOPS公式。

習題：P33,題15,題19；P392,題10,題11,題12。

2001.9.1計算機系統(tǒng)結構21

第二章指令系統(tǒng)（P36）

本章介紹指令系統(tǒng)設計中2個最基本的內容：數(shù)據(jù)表示、操作碼優(yōu)

化。

2.1數(shù)據(jù)表示

［數(shù)據(jù)表示］就是計算機硬件能夠直接辨認與處理的數(shù)據(jù)類型。

人們通常使用的數(shù)據(jù)類型有整數(shù)、實數(shù)、邏輯數(shù)（布爾數(shù)）、字符串、

隊列、堆棧、鏈表、文件等，它們的運算方法各不相同。

所謂“硬件能夠直接辨認與處理”，指的是對該數(shù)據(jù)類型的各種運

算操作都有相應的實現(xiàn)硬件電路。

硬件不能直接辨認與處理的數(shù)據(jù)類型就要根據(jù)數(shù)據(jù)結構的知識編制

軟件轉化為硬件能處理的數(shù)據(jù)類型。

下面介紹通用型計算機數(shù)據(jù)表示集合中的一個基本成員——浮點

數(shù)據(jù)的分析與設計。

2001.9.1計算機系統(tǒng)結構22

2.1.1浮點數(shù)據(jù)表示(P38,P39)

浮點數(shù)據(jù)就是高級語言課程中所說的“實型數(shù)”。

2.1.1.1浮點數(shù)的組成

浮點數(shù)的組成與人們通常所說的“科學記數(shù)法”非常相似，唯一不同的是各部分

均為有限位數(shù)，如下所示

N=mxr^

它的主要參數(shù)有8個：

m——尾數(shù)，一般為純小數(shù)，符合規(guī)格化原則（即最高位的絕對值不為0）,

用泵碼或補碼表示；

e——階碼，整數(shù)，常用移口表示（見下文解釋）；

rm——尾數(shù)的基值，簡稱尾基，常見的有2進制、8進制、16進制、10進制等，

選定以后不變；

re——階碼的基值，簡稱階基，目前都采用2,也是選定以后不變；

P—尾數(shù)的位數(shù)，未將符號位計入；

q—階碼的位數(shù)，未將符號位計入。

mf——尾數(shù)的符號，表示數(shù)的正負，簡稱數(shù)符；

ef——階碼的符號，表示階碼的正負，簡稱階符。但對移碼表示來說，這僅僅

是額外的1位2進制數(shù)，不決定正負。

2001.9.1計算機系統(tǒng)結構23

移碼(P41)

移碼是一種2進制記數(shù)方法，它的真值等?「相同編碼的無符號數(shù)加1

危d。例如，同樣是2進制編碼000000?111111,看作6位無符號數(shù)時的取值范圍是0

?63,而看作6位移-10碼的取值范圍就是-10?53O如下圖所示。

圖2.1移碼與無符號數(shù)的比較實例

移碼是一種有符號數(shù)，但它的最高位通常不決定數(shù)的正負，不應稱為符號位。它的

獨特之處在于其最小取值的2進制編碼是全0,這給機器零的判斷和處理電路設計帶來

很大方便。

2001.9.1計算機系統(tǒng)結構24

2.1.1.2浮點數(shù)的機內格式（P39）

一種浮點數(shù)中每個數(shù)據(jù)的尾基:、階基心都是相同的，在設計運

算電路已經作為默認值來使用，各個具體數(shù)據(jù)在存儲時只需要存入

如下參數(shù)即可：

各字段位數(shù)：1位1位階碼q位尾數(shù)P位

e

mff?q-1.........e0??m[??????nip

對應位的權：....r°4%一1.........r-p

VzDe1111m11

隱含小數(shù)點

圖2.2浮點數(shù)的機內格式

2001.9.1計算機系統(tǒng)結構25

2.1.1.3浮點數(shù)的性能(P38)

浮點數(shù)的性能主要用表數(shù)范圍、表數(shù)精度和表數(shù)效率來刻畫,下面分別進行分析。

(1)表數(shù)范圍(P39)

表數(shù)范圍由這樣一些參數(shù)構成：最小負數(shù)、最大負數(shù)、最小正數(shù)、最大正數(shù)、

最小絕對值|用品、o它們幾何意義可以在數(shù)軸上表示，如下圖。

最小負數(shù)最大負數(shù)0最小正數(shù)最大正數(shù)

圖2.3數(shù)軸上的表數(shù)范圍示意圖

圖中陰影部分為浮點數(shù)的表數(shù)范圍。

根據(jù)浮點數(shù)的組成表達式可知，圖2.3中4個邊界值分別由尾數(shù)小階碼e各自的

邊界值兩兩組合而成，如下所示。

最大支數(shù)一最大正尾數(shù)/最大階碼；

最小正數(shù)----最小正尾數(shù)/最小階碼；

最大負數(shù)一最大負尾數(shù)/最小階碼；

最小負數(shù)一最小負尾數(shù)/最大階碼。

2001.9.1計算機系統(tǒng)結構26

?例2.1

對規(guī)格化浮點數(shù)，尾數(shù)為原碼，階碼為移-琮碼，寫出表數(shù)范圍。（P40）

解：由于原碼在數(shù)軸的零點兩邊對稱分布，即最大正數(shù)與最小負數(shù)的絕對值相

等、最小正數(shù)與最大負數(shù)的絕對值相等，所以可以用最小、最大絕對值來描述

它的分布。

首先根據(jù)圖2.2和式2.1以及移碼的基本定義，可以確定絕對值的極值表達式：

又?儲=(1一北p),e=2r^-1-d,/.\N\=(1_%.).琮

maxm1THXeIImaxmm

寫在一起就是:

]dp2re

rm.r~m<N<v(\—rm~)-rm

再用階碼的偏移量代換式中的-d得:

1?L

mmII、m7m

2001.9.1計算機系統(tǒng)結構27

可以代入具體數(shù)字來幫助理解:

設心=10,2=4,r=10,q=3。

按此題約定,-d=-IO',于是有:

m=101,e.=—d=—103,=101-1010,如下圖所示。

minmnIlimn

1位1位階碼3位尾數(shù)4位

X0000..1000

m=(l-10-4),e=2-103-l-6Z=2-103-l-103=103-l,

irax/m3*

N=(1-10—4).如下圖所示。

max

1位1位階碼3位尾數(shù)4位

X1999..9999

2001.9.1計算機系統(tǒng)結構28

（2）表數(shù)精度（P42）

表數(shù)精度用最大表數(shù)誤差表示（指數(shù)軸

相對誤差）；—I---------------?---------------1——I

最大絕對誤差是真實值與可表示值Nk真實值xNk+i

之間的可能最大距離，也就是相鄰兩

個可表示值間距的1/2,如圖2.4所示

0根據(jù)浮點數(shù)的組成式有其定義：圖2.4最大絕對誤差示意圖

5——(N1,,—TV,)=—(m,,,—m,)xr￡=—xr~pxre

1mxCvk+14/C'k+\mCmm

顯然它隨著階碼e增大而增大，不是一個定數(shù)。

2001.9.1計算機系統(tǒng)結構29

最大相對誤差與階碼e無關，但與尾數(shù)m的值有關。它的定義是

1—pe

—xrxr

5cmm1\xL

max=-x

幾X

NmX琮2m

上式中，當分母加取最小值時分式值達到最大。

1

由于二和富，所以最大相對誤差上限為口，"產。

2001.9.1計算機系統(tǒng)結構30

(3)表數(shù)效率(P45)

定義：

,、其中規(guī)格化浮點數(shù)個數(shù)2.(r-l).rf-1-2-^+1r-l1

77(r)=----------------------------------=------7---------------------------、m---=1

m

可以生成的浮點數(shù)個數(shù)2?r：2-r；rmr

此式說明效率之所以低于100%,是因為規(guī)格化的尾數(shù)最高位叫只能有

%T種取值的緣故?？梢钥闯?，〃的極小值與極大值分別是

2-1

7(2)=——=50%,lim77(%)=100%

［隱藏位技術］是一種提高表數(shù)效率的方法，但僅適用于r:2的情況:

尾數(shù)最高位叫在二進制條件下只有0和1兩種可能，按照規(guī)格化要求,

叫可由其它位推出，?！半[藏”了叫之后，尾數(shù)只存儲后面pT位，

它們中的任一位都有1m種取值，所以表數(shù)效率幾=100%。

2001.9.1計算機系統(tǒng)結構31

2.3指令格式的優(yōu)化(P90)

2.3.2操作碼優(yōu)化

目前常用的編碼方法有3種：定長編碼，Huffman編碼，擴展編碼。

2.3.2.1定長編碼就是所有指令使用相同的代碼位數(shù)，其最小碼長等于

L=L=[Log2n]

式中了是平均碼長，/,是第i種指令的碼長，n是指令總數(shù)。

?例2.2

已知n=15,求定長編碼的最小平均碼長。

解：_

L=[Log215~]=4

2001.9.1計算機系統(tǒng)結構32

2.2.1.1Huffman壓縮編碼(P91)

（1）Huffman壓縮概念（最佳編碼定理）：當用n個長度不等的代碼分別代表n種

發(fā)生概率不等的事件時，按照短代碼給高概率事件、把長代碼給低概率事

件的原則分配，可使平均碼長達到最低。

（2）Huffman編碼方法

這種編碼方法由兩個過程組成。

頻度合并：將全部n個事件（在此即為n條指令）的頻度值排序，選取

其中最小的2個頻度合并，然后將剩下的nT個頻度再次排序，再合并最小

的2個頻度，如此重復，直至剩下1個頻度為止。記錄所有的合并關系，形

成一棵二叉樹----Huffman樹，所有原始頻度值充當樹葉，而最后剩下的

總頻度1為樹根；

碼元分配：從樹根開始，對每個中間結點的左右2個分支邊各賦予一

位代碼“0”和“1”（“0”在哪一側不限）。讀出從根結點到任一片樹葉

的路徑上依次出現(xiàn)的代碼位就排成了這個事件（即指令）的完整編碼。由

于頻度高的事件較晚被合并，它的編碼位數(shù)也就較少，符合Huffman壓縮原

則。

上面所說的頻度值就是各事件實際出現(xiàn)次數(shù)的百分比，它是理論出現(xiàn)概率

的dfi似值。計算機系統(tǒng)結構33

(3)編碼方法性能指標(P91-P93)

信息量：根據(jù)信息論的基本知識，在n種可能發(fā)生的事件集合中，報告第i

種事件發(fā)生的消息中包含的信息量為

4T0ga(')=-10ga4

其中Pi是第i種事件發(fā)生的先驗概率，a是編碼基值。信息量的單位是表示位

數(shù)(最少所需位數(shù))。

這個定義式表明事件的發(fā)生概率越低，關于它的消息中的信息量越大

O

?嫡(entropy)----平均信息量：一個消息源對n種事件發(fā)布的消息的信息

量平均值，記為

nn

■=—?，)=—匯[4?bg〃(4)]

i=li=l

2001.9.1計算機系統(tǒng)結構34

?平均碼長：各事件編碼長度的數(shù)學期望。

Z=￡（K）

Z=1

?信息冗余昌：它表明消息編碼中“無用成分”所占的百分比。

L-H

RxlOO%

L

從減少存儲與傳輸量的角度看，編碼方法的平均碼長越短越好。但是平

均碼長不可能無限制縮短，它的下限就是嫡（即R二0時）。如果短于燧就一

定會丟失有用信息（即混淆不同指令），這是不允許的。

2001.9.1計算機系統(tǒng)結構35

2.2.1.2擴展編碼方法（等長擴展法，P93）

?用碼長表示：例如4-8-12法。這并不能說明具體編碼方法，例如

下面兩種編碼方法都是4-8-12法。

?用碼點數(shù)表示：例如15/15/15法，8/64/512法

-15/15/15法，每一種碼長都有4位可編碼位（前頭可以有相同

的擴展標識前綴），可產生16個碼點（即編碼組合），但是

至多只能使用其中15個來表示事件，留下1個或多個碼點組合

作為更長代碼的擴展標識前綴。已經用來表示事件的碼點組

合不能再作為其它更長代碼的前導部分，否則接收者會混淆。

這就是“非前綴原則”。

-8/64/512法，每一種碼長按4位分段，每一段中至少要留下1

位或多位作為擴展標識。各段剩下的可編碼位一起編碼，所

產生的碼點用來對應被編碼事件。每一段中的標識位指出后

面還有沒有后續(xù)段。

2001.9.1計算機系統(tǒng)結構36

?例2.3

已知頻度序列為0.00.1,0,15,0.15,0.2,0.3,求Huffman編碼、等

長擴展3/3/3碼、定長編碼、三者的平均碼長、信息冗余量以及嫡。

解：

燧H=

-(2X0.1Xlog20.1+2X0.15Xlog20.15+0.2Xlog20.2+0.3Xlog20.3)

=2.47

根據(jù)Huffman編碼方法作Huffman樹如圖2.5所示，三種編碼方法的結果列于

表2.1中。

2001.9.1計算機系統(tǒng)結構37

表2.1Huffman編碼、等長擴展3/3/3碼及定長編碼

指令14：5

I1121316

頻度0.1。10.15。15。20.3

Huffman碼0000011001010111

平均碼長￡=2.5,信息冗余量R—1.2%

3/3/3碼111011011100100100

平均碼長/=2.7,信息冗余量R—7.5%

定長編碼000001010011100101

平均碼長￡=3.0,信息冗余量RQ17.7%

2001.9.1計算機系統(tǒng)結構38

2.2.2操作數(shù)優(yōu)化尋址方式比較（P95）

指令中操作數(shù)占用的位數(shù)由操作數(shù)的個數(shù)與尋址方式決定。

按操作數(shù)的個數(shù)劃分，有零操作數(shù)指令、一操作數(shù)指令、二操作

數(shù)指令、三操作數(shù)指令共四種形式。應該按機器用途來選擇（P99,

表2.20）o

縮短操作數(shù)長度的常用方法是間址和變址（P99頁末）。

2001.9.1計算機系統(tǒng)結構39

本章小結

本章主要內容有數(shù)據(jù)表小和操作碼優(yōu)化兩個部分。具體細節(jié)如下：

(1)浮點數(shù)的表數(shù)范圍(在數(shù)軸上的4個端點)、表數(shù)精度3、表數(shù)效率中

(2)Huffinan編碼方法；

(3)等長擴展編碼方法(15/15/15法，8/64/512法)；

(4)編碼方法性能指標(嫡H,平均碼長匚，信息冗余量R)。

習題：P124,題3(忽略P124倒1行?P125第8行文字)，題13。

2001.9.1計算機系統(tǒng)結構40

第三章存儲系統(tǒng)(P130)

長期存在的問題：在合理的總價格限制下，單純性主存設備的速

度跟不上CPU的發(fā)展，容量不能滿足軟件尺寸擴大。

本章學習兩種提高主存系統(tǒng)性能/價格比的結構化方法：

器與存儲層次技術。后者為主。

2001.9.1計算機系統(tǒng)結構41

3.1并行存儲器(P136)

并行存儲器技術可以提高主存系統(tǒng)的整體等效速度，實際應用中,

常將它與存儲層次技術組合使用，可以互為補充，獲得很高的性能。

并行存儲器技術的基本思想是用多個獨立的存儲部件組成土存系

統(tǒng)，讓它們并行工作，在一個存儲周期內可以訪問到多個數(shù)據(jù)，從

而實現(xiàn)較高的存取流3。

并行存儲器包括多種類型，我們僅介紹提高訪問速度效果最顯著

的低位交叉訪問這一種。

2001.9.1計算機系統(tǒng)結構42

低位交叉訪問并行存儲器的結構:

它由n個存儲體組成（一般n為2的整次塞），每個體均有獨立的地址譯

碼器和數(shù)據(jù)緩沖器，以主存地址低位字段（最低的logm位）作為體選譯

碼信號，而剩下的高位字段則是體內地址。如圖所示（設n=4）o

地址總線

數(shù)據(jù)總線

2001.9.1計算機系統(tǒng)結構43

主存地址與結構參數(shù)的換算（P139）：

求主存地址：A=nxj+k

求結構參數(shù)：j=一，k=Amodn

其中：n——存儲體個數(shù)，A——主存地址，

j---體內地址，k-----體序號（k=0,1,2,n-1）

?例3.1

已知n=4,問主存地址13是在幾號體的幾號單元？

解：

由于n=4,體選譯碼信號使用主存地址的最低log2n=2位，所以地

址13（其二進制為1101B）對應的體號k=1（即01B）、體內地址j=3（

即11B）,也就是說，地址13位于1號體的3號單元（參看前一頁插圖）。

根據(jù)上式，所有k值（即體號）相同的地址之間均相差n的整倍數(shù)

,稱之為“模n同余”。

2001.9.1計算機系統(tǒng)結構44

低位交叉訪問并行存儲器的加速機理:

我們衡量存儲器件速度的常用指標是存儲周期Tm,它是同一存儲單元連續(xù)兩

次啟動的最小時間間隔，數(shù)值越小表明存儲器件速度越快。

傳統(tǒng)存儲系統(tǒng)只有一套地址譯碼器和數(shù)據(jù)緩沖器，所以各單元必須串行工作

,也就是說每個Tm周期內至多只能完成一次訪問。

由多個存儲體構成的并行存儲器中，各個存儲體都有獨立的地址譯碼器和數(shù)

據(jù)緩沖器，它們可以并行工作，使得一個Tm周期內可完成多次訪問，相當于加

速了多倍。最好情況下一個Tm周期內可完成n次訪問。

當前Tm周期中只要發(fā)現(xiàn)有一個新的訪問地址與前面地址屬于同一個存儲體，

該地址及其后面的地址就會被阻塞（稱為訪存沖突），留到下一個Tm周期訪問。

機器地址序列常常具有順序性，按照低位交叉的規(guī)律分配地址可使相繼出現(xiàn)

的地址落在相同存儲體的概率降到最低（參見上圖）。

考慮到地址總線與數(shù)據(jù)總線的擁擠問題，一個Tm周期里發(fā)送的多個訪問請求

最好彼此錯開Tm/n時間，如P140圖3.11所示，否則實現(xiàn)的復雜度會增加。

2001.9.1計算機系統(tǒng)結構45

計算平均加速倍數(shù)（P141）：

1.只考慮取指地址序列（假設地址順序

遞增，直至出現(xiàn)一條轉移指令）：

冗J二（1二g）一（n41倒數(shù)第一行）

g

其中g是指令序列中出現(xiàn)轉移指令的概

率。此公式在右圖中用綠線表示。

2.只考慮取數(shù)地址序列（假設地址完全

隨機）

K—」nx/r/2—0.28

此公式在右圖中用表示。

2001.9.1計算機系統(tǒng)結構46

例題：P203,題5

解：已知冗=匕支出，其中g=0.1,依題意有

g

——l-(l-g)z?+1——1—(1—g)"

K「—-―2—>K+0.2=―-—―+0.2

九十1n

gg

得0.9”>0.2,角星出〃〈思《15.28

1g0.9

向下取整，得15。取〃+1=16也對(文字理解差異)。

2001.9.1計算機系統(tǒng)結構47

3.2存儲層次原理及性能指標

3.2.1基本原理

?定義：（參見P131第二段）

由2種或多種存儲部件構成的復合存儲系統(tǒng)，通

過內部管理機構的自動更換機制,能夠不斷將大容r

量低速存儲部件中的活躍內容復制到小容量高速存

儲部件中（后者作為前者的局部副本）。

它既能滿足CPU的快速存取需要，又有很大的存

儲容量，平均單位價格也很低，等效于同時滿足3

方面要求的理想單一存儲部件。

Mn

?依據(jù)：程序訪問的局部化原理（時間局部化，空

圖3.3存儲層次模型

間局部化）。

?模型：如右圖所示，存儲層次由n層組成，

滿足3個不等式：Ti<Ti+1,Si<Si+1,Ci>ci+1o

2001.9.1計算機系統(tǒng)結構48

3.2.2性能指標(P132-P134)

(1)容量：s=s2(理論上)

(2)單價：(美分/bit)

5

,G+

G?S]+?S2S

c=------------------=―:2

S[+邑

S?

它的最小值是lim。=02

色一。

S]

2001.9.1計算機系統(tǒng)結構49

(3)速度：表現(xiàn)訪問速度的參數(shù)很多

?命中率：反映被訪問數(shù)據(jù)事先已在此的發(fā)生概率

H=-----1—，O<H<1

N'+N?

?等效訪問時間：命中時的訪問時間為不命中時的訪問時間為丁2,等效

訪問時間則是它們的概率均值

T=H?T]+Q_H)T2

lim7=不

“fl00%

2001.9.1計算機系統(tǒng)結構50

?訪問效率：這是一個相對值，便于不同系統(tǒng)之間的比較。

e=一

T

1

1

r+(l-r)-7f

H和r對e的作用

（廠是鄰級速度比）。

其中04e<Lr^>1

T\

訪問效率e受H和r的影響（參見右圖）：

rT->eO

2001.9.1計算機系統(tǒng)結構51

?Cache預取技術對命中率的提高作用（P134）：

這里所說的“預取”技術，并不是根據(jù)對程序執(zhí)行的未來趨勢進行

猜測以提前調入數(shù)據(jù)，而僅僅是在發(fā)生不命中情況時把調入1個數(shù)據(jù)

字改為調入1個數(shù)據(jù)塊的策略。根據(jù)程序的局部化原理，在當前使用

數(shù)據(jù)周圍的其它數(shù)據(jù)未來被使用的幾率大于遠處數(shù)據(jù)，所以該數(shù)據(jù)塊

中被提前調入的鄰近數(shù)據(jù)很可能成為未來的命中點，從而提高命中率

O

采用這種預取技術后新的命中率為

其中：H——原命中率（即按照不命中時取入1字的策略）；

出——新命中率（即按照不命中時取入1塊的策略）；

n——每塊數(shù)據(jù)平均被訪問次數(shù)。

2001.9.1計算機系統(tǒng)結構52

H，的推導:

N.

按照定義，原不命中率1—H=——--,新不命中率

N、+N2

N，

T—H'=-----------，并且有No

Ni'+N：1212

由于預取使得每塊數(shù)據(jù)中的不命中次數(shù)由n次降低到1次，所以有

入丁N.1-H

N2——N20此式可改寫為n=-----=---------

nN：\—H'

整理得H，=Ho

n

2001.9.1計算機系統(tǒng)結構53

?加速比(P193)

Cache-主存層次的主要作用是提高訪問速度，系統(tǒng)的等效速度應

高于主存(即M2)的原有速度，兩個速度之比稱為加速比。

§—等效速度—時間%

P~河2速度一等效時間一T

H工"一切工

1

Q—H)+H/r

2001.9.1計算機系統(tǒng)結構54

?增加中間層對e的影響

?例3.2

有一個109字節(jié)的程序被裝

入右圖所示的M3準備運行。

假定指令字長二1字節(jié)，程序

中無轉移指令和內存讀/寫指

令。

(b)

(1)按圖(a)求T和e；

⑵按圖(b)推導三層體系的T公式;

(3)按圖(b)求T和e；

(4)比較(1)(3)結果,有何結論?

2001.9.1計算機系統(tǒng)結構55

解:

103-11

(1)=——,\-H=-

IO3YIO3

T=HM+Q-H)TB3

1O3-11103+102-l

=---------------xlOOzzs1=-----------usx(1+10%)-7]

103103103

Ty

T

Q)T=H\T[+Q-H\).T2

T?—H2,TB2+(1—H〉TB3

由上面2式有

T=H-7]+(1——H2)?圖3〕

=H]11+Q_H)H2.TB2+Q_H)Q_H2)?TB3

2001.9.1計算機系統(tǒng)結構56

103-11

(3)H=——1-H=

210392103

103-11-103-11

T=------xljUS+—rXxlO/ZS,H------x100//5

103103io3103

106+104-103+102-10

跖。(i+i%)N

106

?99%

T

(4)結論：插入中間層后，層間速度差減少，訪問效率提高。

習題：P202,題3。

2001.9.1計算機系統(tǒng)結構57

存儲層次的管理方式(P148)

根據(jù)程序的局部化性質，存儲層次機構對用戶文件的管理應該劃分成較小

的基本調度單位來進行。依劃分標準不同，存在3種存儲層次管理方式。

⑴段式管ai(pi48)。段是程序中的一個邏輯單位，可以是一個程序模塊，

或者是一個數(shù)據(jù)結構。段的長度不一，但段內所有數(shù)據(jù)的信息屬性一般是相

同的，便于統(tǒng)一進行信息保護。

每段使用獨立的邏輯地址空間，即都從0開始計算地址。

段式管理方法的主要缺點是各段長短不一，調進調出之后容易形成大量不

規(guī)則的零碎空間。

段式管理方法的虛實變換算法是查段表(P150)。

2001.9.1計算機系統(tǒng)結構58

(2)頁式管理(P151)。頁是系統(tǒng)規(guī)定的固定長度單位。按頁劃分用戶文件可

以避免上述零碎空間浪費。

我們把用戶文件劃分得到的一個長度單位稱為“虛頁”，因為它的頁號

是在虛地址空間中編排的；實地址空間按頁的大小劃分得到的一個長度單

位稱為“實頁”。

頁式管理方法的主要缺點是按固定長度分出來的同一頁內常有不同屬性

的信息，不便于信息保護的實現(xiàn)。

頁式管理方法的虛實變換算法是查頁表(P152)。

⑶段頁式管理(P153)。它把上述兩種管理方式結合起來，首先將整個文件

分段，然后在各段內分頁，所以有一個段表和若干個頁表。其虛實變換算

法是先查段表，查出該段的頁表起始地址再查相應的頁表(P154)O

段頁式管理的主要缺點是多查一次表，虛實變換費時較多，占用空間也

較大。

由于段頁式管理方法的最小調度單位仍是頁，或者說它是分段之后的分

頁管理，為了敘述簡單，下面的分析還是