WilliamStallings

ComputerOrganization

andArchitecture

5thEdition

Chapter12

ReducedInstruction

SetComputers

精簡指令集計算機

Topics

MajorAdvancesinComputers計算機的主要改進

InstructionExecutionCharacteristics指令執行的特點

UseofLargeRegisterFile使用大的寄存器

Compiler-BasedRegisterOptimization

基于編譯器的寄存器優化

ReducedInstructionSetArchitecture

精簡指令集體系結構

RISCPipeliningRISC流水線

RISCvs,CISCControversyRISC和CISC的比較

2

Major^AdvancesinComputers(l)______

Thefamilyconcept系列概念

IBMSystem/3601964

DECPDP-8

Separatesarchitecturefromimplementation

將體系結構和它的實現分開

Microporgrammedcontrolunit微程序控制器

IdeabyWilkes1951

ProducedbyIBMS/3601964

CachememoryCache存儲器

IBMS/360model851969

MajorAdvancesinComputers(2)___

SolidStateRAM固態存儲器

(Seememorynotes)

Microprocessors微處理器

Intel40041971

Pipelining流水

Introducesparallelismintofetchexecutecycle

Multipleprocessors多處理器

4

TheNextStep:RISC

RISC-ReducedInstructionSetComputer

RISC精簡指令集計算機

Keyfeatures

Largenumberofgeneralpurposeregisters,oruseof

compilertechnologytooptimizeregisteruse

大量通用寄存器，使用編譯技術優化寄存器的使用

Limitedandsimpleinstructionset

一個有限簡單的指令集

Emphasisonoptimisingtheinstructionpipeline

強調指令流水的優化

Comparisonofprocessors

ComplexInslructionSetReducedInstructionSuperscjibr

(CISCiCompuIrrSrl<R.ISC>Computer

CharacterisficIBMVAXIntelSPARCMIPSPowerPCUltuiMIPS

370/L68U/78Q80486R4000SPARCRLQOQO

Yeardcxeloped197319781989L987L991199319%1996

2083032356994225

Unstrudiom^

-lngjmclionsite(2-62^7L-Ll44444

-Addressingmodes422ILL121L

^hiinberofgenerai^^1616840-520323240-52032

^purposeregisfef^^^

Controlnirmorv?size4-20480246———————

1Kbits>

Cachesize，KByte)64X83212816-323264

6

DrivingforceforCISC(1)

CISC-ComplexInstructionSetComputer

CISC一復雜指令集計算機

WhyCISC?

Softwarecostsfarexceedhardwarecosts

軟件成本高于硬件成本

Increasinglycomplexhighlevellanguages

越來越復雜的高級語言

Semanticgap:Differencebetweenoperations

providedinHLLsandthoseprovidedincomputer

architecture

語義間隙問題：

HLLs提供的操作和計算機體系結構提供的操作不同

DrivingforceforCISC(2)_________________

toclosethegap

Leadsto:

Largeinstructionsets指令集非常大

Moreaddressingmodes更多的尋址方式

HardwareimplementationsofHLLstatements

e.g.CASE(switch)onVAX

HLL描述的硬件的實現

IntentionofCISC復雜指令集體系結構的目的

-Easecompilerwriting使編譯器的編寫更容易

Improveexecutionefficiency提高執行效率

Complexoperationsinmicrocode

因為復雜操作能以微代碼實現

SupportmorecomplexHLLs

提供更復雜的HLL支持

Atotallydifferentapproach:Simplerarchitecture

簡化體系結構

ExecutionCharacteristics

DevelopmentsofRISCswerebasedonthe

studyofinstructionexecutioncharacteristics

RISC的開發是基于指令的執行特性

Operationsperformed完成的操作

determinefunctionstobeperformedandinteractionwith

memory

決定了CPU所要完成的功能及其與存儲器的相互作用

Operandsused(typesandfrequencies)

使用的操作數及其類型和頻率

determinememoryorganizationandaddressingmodes

決定了存儲器如何組織存儲它們和訪問它們用的尋址方式

Executionsequencing

determinesthecontrolandpipelineorganization

決定了控制和流水線的組織結構

10

ExecutionCharacteristics

Intheremainderofthissection,wesummarize

theresultsofanumberofstudiesofhigh-level-

languageprograms.Alloftheresultsarebased

ondynamicmeasurements.

Dynamicstudiesaremeasuredduringthe

executionoftheprogram.

程序的執行中進行的動態測量。

Staticmeasurementsmerelyperformthese

countsonthesourcetextofaprogram.

靜態測量只是在源程序文本上進行統計，這不能

給出很有用的性能信息。

11

Operations

Table4.9reveal:

Assignmentstatementspredominate

Movementofdataisofhighimportance數據的移動重

要性

PreponderanceofConditionalstatements(IF,

LOOP)條件語句

Sequencecontrolisimportant指令集的順序控制

12

RelativeDynamicFrequency

DynamicMachineInstructionMemoryReference

Occurrence(Weighted)(Weighted)

PascalCPascalCPascalC

Assign[453813131415

Loop5342323326

Call151231334445

29431121713

GoTo-3

Other613121

13

Operations

Procedurecall-returnisverytimeconsuming

程序的調用花費大量時間

SomeHLLinstructionleadtomanymachine

codeoperations

一些HLL指令導致執行大量機器代碼

14

Operands

Mainlylocalscalarvariables

王要是局部，標量變量

Optimisationshouldconcentrateonaccessing

localvariables

優化也應該集中在局部變量的訪問

PascalCAverage

Integerconstant162320

Scalarvariable5853[55]

Array/structure262425

15

ProcedureCalls

Verytimeconsuming

過程調用是編譯后的HLL程序中最耗時的操作

Toimplementefficiently,twoaspectsaresignificant:

Dependsonnumberofparameterspassed

依賴于傳遞的參數的數量

Dependsonlevelofnesting依賴于嵌套深度

Mostprogramsdonotdoalotofcallsfollowedbylotsof

returns

程序一般不作大量的調用返回

Mostvariablesarelocal大部分變量是局部的

16

Implications

MakinginstructionsetarchitectureclosetoHLL

使指令集與HLL相近

nnotmosteffective不是最有效的

Bestsupportisgivenbyoptimisingmostused

andmosttimeconsumingfeatures

通過優化最經常使用的和最花費時間的，是最好

的方案。

17

Implications

Generalizingfromtheworkofanumberof

researchers,threeelementsemergethat,by

andlarge,characterizeRISCarchitectures.

Largenumberofregisters大量寄存器

Operandreferencingoptimization+localityof

referencesnmemoryreferencesreduced減少存

儲器訪問

Carefuldesignofpipelines精心設計流水線

Conditionalbranchandprocedurecall

條件分支和過程調用

Simplified(reduced)instructionset精簡指令

集

18

UseofA.argeRegisterFile______

Fromtheanalysis

Largenumberofassignmentstatements

Mostaccessestolocalscalars

主要訪問本地標量

nHeavyrelianceonregisterstorage

依賴于寄存器存儲

nMinimizingmemoryaccess

最小化內存訪問

19

Softwaresolutiontomaximizeregisterusage軟件方法

Requirecompilertoallocateregisterstothosemost

usedvariablesinagiventime

依賴于編譯器，把寄存器分配給那些一定時間內使用

最多的變量

Requiressophisticatedprogramanalysis

需要復雜的程序分析

Hardwaresolution硬件方法

Havemoreregisters

大量寄存器

Thusmorevariableswillbeinregisters

寄存器中存放大量變量

20

RegistersforLocalVariables

Storelocalscalarvariablesinregisters

在寄存器中存放本地標量變量

=>Reducesmemoryaccess減少存儲器訪問

Someproblems

Everyprocedure(function)callchangeslocality

每一次過程調用都會改變局部性

Oneverycall,localvariablesmustbesavedto

memory每次調用變量必須被存儲到存儲器

Parametersmustbepassed必須傳遞參數

Onreturn,resultsmustbereturnedandvariables

fromcallingprogramsmustberestored

必須返回結果并且恢復調用程序的變量

21

RegisterWindows

Solution:Registerwindows

Organizationofregisterstorealizethegoal

為了實現解決前述問題的目標，而對寄存器采用的組織結構

Fromtheanalysis

Onlyfewparametersandlocalvariables

少量參數和本地變量

Limitedrangeofdepthofcall有限的調用深度

=>

Usemultiplesmallsetsofregisters

使用多個小的寄存器組

Callsswitchtoadifferentsetofregisters

過程調用時自動地切換來使用不同的寄存器組

Returnsswitchbacktoapreviouslyusedsetofregisters

返回時切換回以前使用的寄存器組

OverlappingRegisterWindows

ParameterLocalTemporary

Level.1

RegistersRegistersRegisters

Call/Return

LevelJ+1

Threeareaswithinaregisterset窗口分為3個域:

Parameterregisters參數寄存器域

Localregisters局部寄存器域

Temporaryregisters臨時寄存器域

23

RegisterWindowscont.

Temporaryregistersfromonesetoverlapparameter

registersfromthenext

臨時寄存器用于當前過程與下一級過程（被當前過程調用

的過程）交換參數和結果

Temporaryregistersatonelevelarephysicallythesame

astheparameterregistersatthenextlowerlevel.

當前層的臨時寄存器域和下一層的參數寄存器域物理上是

同一個域。

Thisallowsparameterpassingwithoutmovingdata

這種重疊準許不用實際移動數據就能傳遞參數

24

CircularBufferdiagram

Theactual

organizationofthe

registerfileisasa

circularbufferof

overlapping

windows.

寄存器集的實際組

織結構是一個由重

疊窗口組成的環形

緩沖器。

OperationofCircularBuffer

?Whenacallismade,acurrentwindowpointer(CWP)is

movedtoshowthecurrentlyactiveregisterwindow

當一個調用發生時，專訪窗口指有移動到當前活動寄存器

窗口

Ifallwindowsareinuse,aninterruptisgeneratedand

theoldestwindow(theonefurthestbackinthecall

nesting)issavedtomemory(only.inandJoeneedto

besaved)

當所有窗口都在使用就會產生中斷，最老的窗口會保存到

內存(只保存參數、局部窗口的數據)

Asavedwindowpointerindicateswherethenextsaved

windowsshouldrestoreto

保存窗口指f表明下一個保存窗口應該恢復的地方

26

OperationofCircularBtrffer(2)________

Studiesshow:8windowsareenoughtohandle

uptoofcall/returnwithoutsave/restore

8個窗口足夠處理99%的調用和返回

E.g.,BerkeleyRISCuses8windowsof16

registerseach

27

GlobalVariables二2Options

Allocatedbythecompilertomemory

由編譯器為全局變量指定存儲器位置

Straightforward直截了當

Inefficientforfrequentlyaccessedvariables

對經常訪問的全局變量效率低下

Haveasetofregistersforglobalvariables

CPU中有一組全局寄存器

eg,registers0-7:global

8-31:localtocurrentwindow

Increasedhardwareburden硬件負擔增力口

Compilermustdecidewhichglobalvariablesshouldbe

designedtoregisters

編譯器也必須裁定什么樣的全局變量應指派到寄存器。

28

RegistersvCache

LargeRegisterFileCache

AlllocalscalarsRecentlyusedlocalscalars

所有局部變量最近使用的局部標量

IndividualvariablesBlocksofmemory

個別變量_______________________存儲器塊__________________

CompilerassignedglobalvariablesRecentlyusedglobalvariables

編譯器指派全局變量最近使用的全局變量

Save/restorebasedonSave/restorebasedoncaching

procedurenestingalgorithm

保存「恢復基于過程的嵌套深度保存「灰復基于cache替換算法

RegisteraddressingMemoryaddressing

寄存器尋址存儲器尋址

29

RegistersvCache

鍛大寄存器

保留了所有的局部標量變量

空間利用率低（窗口大，參數少）

寄存器與存儲器之間的數據傳送不太頻繁

Cache

有選擇地保留局部標量變量

可以有效地利用空間（動態更新）

同時也存在空間利用率低的問題（成塊傳送，包含無

用數據）

寄存器與存儲器之間的數據傳送可能較頻繁（組關聯

映像）

30

RegistersvCache

寄存器優于Cache表現在：

為訪問基于窗口寄存器集中的一個局部標量，使用一個窗

口號和一個“虛擬的”寄存器號。這些通過一個相對簡單

的譯碼器來選擇某一個具體的寄存器。

為訪問cache存儲器中的一個位置，必須生成全寬度的地

址。這種操作的復雜性取決于尋址方式。在一個組關聯的

cache中，地址的一部分用于讀取等同于組長度的幾個字

和標記(tag),地址的另一部分用于與標記進行比較，以

選擇所讀的一個字。

這一點應是很清楚的，盡管cache能與寄存器集一樣地快

，但cache的存取時間肯定要長。于是，從性能觀點看，

基于窗口的寄存器集對于局部標量是優選的。通過加入只

由指令使用的cache,能進一步改善性能。

31

ReferencingaScalar-

WindowBasedRegisterFile

Instruction

Data

快

32

ReferencingaScalar-Cache

Instruction

33

CompilerBasedRegisterOptimization

Assumesmallnumberofregisters(16-32)

假設只有少量寄存器可用

優化寄存器的使用就是編譯器的責任

HLLprogramshavenoexplicitreferencestoregisters

用高級語言寫的程序沒有對寄存器的顯式引用

Theobjectiveofthecompileristokeeptheoperandsfor

asmanycomputationsaspossibleinregistersratherthan

mainmemory,andtominimizeload-and-storeoperations.

編譯器的目標就是，盡可能地在寄存器中而不是在主存中為

多數計算保持操作數，并且減少與內存的裝入和存儲操作。

34

CompilerBasedRegisterOptimizationcont.

Eachquantityisassignedtoasymbolicorvirtualregister

準備駐留在寄存器中的每個程序量先被指派到一個符號的

或虛擬的寄存器中

Map(unlimited)symbolicregisterstorealregisters

然后編譯器再將這些末限定數目的符號寄存器映射到固定

數目的實寄存器上

Symbolicregistersthatdonotoverlapcansharereal

registers

那些使用不重疊的符號寄存器能共享同一實寄存器

Ifyourunoutofrealregisters,somevariablesuse

memory

若在程序具體運行期間，需要打交道的量多于實寄存器數

目、則某些量要被指派到存儲器位置上

35

Optimization

Theessenceoftheoptimizationtaskistodecide

whichquantitiesaretobeassignedtoregisters

優化任務的本質：是判定程序中什么樣的量應指

派到寄存器中

Thetechniqueisknownasgraphcoloring

圖著色技術

UsedinRISCcompiler用在RISC編譯器

Borrowedfromthedisciplineoftopology

這是由拓撲學借用過來的技術

36

GraphColoring

Givenagraphofnodesandedges

對于一個由結點和邊組成的給定圖

Assignacolortoeachnode

為每個結點指定顏色

Adjacentnodeshavedifferentcolors

使相鄰節點不同色

Useminimumnumberofcolors

要使用顏色的數目最少

Nodesaresymbolicregisters

結點是符號寄存器

37

GraphColoringcont.

Tworegistersthatareliveinthesameprogram

fragmentarejoinedbyanedge

若兩個符號寄存器同時“存活”于同一程序段，

則相應的兩個結點用一條邊連接起來以指出它們

相關。

Trytocolorthegraphwithncolors,wherenis

thenumberofrealregisters

嘗試用n種顏色給圖上色，n為實寄存器的數目

Nodesthatcannotbecoloredareplacedin

memory

這些不能上色的結點必須放入存儲器中

38

GraphColoringApproach

Assumeaprogramwithsixsymbolicregisterstobe

compiledintothreeactualregisters

Parta:符號寄存器使用的時間順序

Partb:寄存器干涉圖

39

生Trade-Off

Atrade-offbetweenlargeregistersandregister

optimization

在使用大量的寄存器和寄存器優化之間有一個權衡考慮問題

Withevensimpleregisteroptimization,

thereislittlebenefittotheuseofmorethan64

registers

若只有相當簡單的寄存器優化，那么使用多于64個寄存器只

帶來很少的好處

Withreasonablysophisticatedregisteroptimization

techniques,thereisonlymarginalperformance

improvementwithmorethan32registers

使用相當精致的寄存器優化技術，也比他角多于32個的寄存

器帶來更多的臨界性能改善

Studiesshow

64registersareenoughwithsimpleregisteroptimization

32registersareenoughwithsophisticatedregisteroptimization

40

ReducedInstructionSetArchitecture

WhyCISC(1)?

WhyCISC?

Easecompilerwriting使編譯器的編寫更容易

Improveexecutionefficiency提高執行效率

Compilersimplification?

Disputed…爭論

Complexmachineinstructionshardertoexploit

難以使用，編譯器必須找到嚴格滿足限制的情況

Optimizationmoredifficult

E.g.Minimizecodesize,enhancepipelining減小代碼提高流

水都很難實現

41

WhyCISC(2)?

Smallerprograms?

Programtakesuplessmemory程序占用內存少

Butmemoryisnowcheap但是內存非常便宜

Fewerinstructionstobefetched,reducingpagefaults.

Maynotoccupylessbitsinsymbolicmachinelanguage

符號形式的機器語言，所占據的存儲器位數卻不見得小

Moreinstructionsrequirelongerop-codes

CISC指令多，需要的操作碼就長

RISCtendtoemphasizeregister,andregisterreferencesrequire

fewerbits

RISC指令使用的寄存器訪問要求較少位數

42

WhyCISC(1)?

CodeSizeRelativetoRISCI

11CPrograms

RISCI1.0

VAX-11/7800.8CISC

M680000.9

Z80021.2

PDP-11/700.9RISC

CISC比RISC節省很少甚至沒有節省

VAX比PDP-11減少很少，但VAX指令復雜的多

43

WhyCISC(3)?

Fasterprograms?

Morecomplexcontrolunit

更復雜的控制單元

Microprogramcontrolstorelarger

微程序控制存儲更大

thussimpleinstructionstakelongertoexecute

增加了簡單指令的執行時間

ItisfarfromclearthatCISCistheappropriate

solution

CISC是較合適的解決方法

44

RISCCharacteristics

Oneinstructionpercycle

每周期一條指令

Registertoregisteroperations

寄存器到寄存器操作

Few,simpleaddressingmodes

簡單尋址方式

Few,simpleinstructionformats

簡單指令格式

45

OneInstructionPerMachineCycle

Inamachinecycle在一個機器周期

fetchtwooperandsfromregisters

從寄存器取兩個操作數

PerformanALUoperation完成一個ALU操作

Storetheresultinaregister結果存寄存器

Thereislittleornotneedformicrocode

很少或沒有需要微代碼

Machineinstructionscanbehardwired

機器指令可以用硬布線的方式實現

Suchinstructionsshouldexecutefasterthan

comparablemachineinstructionsonother

machines,

46

Register-to-RegisterOperations

Mostoperationsisregister-to-register

大多數操作應是寄存器到寄存器的

OnlyLOADandSTOREaccessingmemory

只有簡單的LOAD和STORE操作訪問存儲器

Simplifyinstructionsetandcontrolunit

簡化指令集和控制器

RISCincludeonly1or2ADDinstructions

VAXhas25differentADDinstructions

Encouragestheoptimizationofregisteruse

更適合于寄存器的優化使用

Frequentlyaccessedoperandsremaininhigh-speed

storage頻繁存取的操作數保留在高速存儲裝置

47

SimpleAddressingModes

AlmostallRISCinstructionsusesimpleregister

addressing

幾乎全部RISC指令都使用寄存器尋址方式

Mayincludeseveraladditionalmodes

DisplacementandPC-relative

可能包括幾種其它尋址方式，如偏移和相對

Simplifyinstructionsetandcontrolunit

簡化指令集和控制器

48

SimpleInstructionFormats

Onlyoneorafewformatsareused

僅使用一種或少數幾種格式

Instructionlengthisfixedandalignedonwordboundaries

指令長度固定并且在字邊界上對齊

Asingleinstructiondoesnotcrosspageboundaries

單一指令不會跨越內存分頁的邊界

Fieldlocations,especiallytheopcode,arefixed

字段位置，特別是操作碼字段位置是固定的

Opcodedecodingandregisteroperandaccessingcan

occursimultaneously

操作碼的譯碼和寄存器操作數的訪問能同時出現

Simplifycontrolunit簡化控制器

49

CISCvRISC

TypicalofaRISC

Asingleinstructionsize(typically4bytes)

單一指令長度(典型4個字節)

Asmallnumberofdataaddressingmodes(typically

lessthanfive)

較少的尋址方式(典型小于5種)

Noindirectaddressing無間接尋址

Nooperationsthatcombineload/storewitharithmetic

裝入/存儲操作不會與算術操作混在一起

Nomorethanonememory-addressedoperandper

instruction

每條指令不會有多于一個的存儲器操作數

Doesnotsupportarbitraryalignmentofdatafor

load/storeoperations

對裝入/存儲操作.不支持數據的任意對齊

50

RISCdesignsmaybenefitfromtheinclusion

ofsomeCISCfeatures

RISC設計包括某些CISC特色會有好處

CISCdesignsmaybenefitfromtheinclusion

ofsomeRISCfeatures

CISC設計包括某些RISC特色也會有益

PowerPC不再是純RISC機

Pentium也結合了RISC的特征

51

RISCPipelining

RISC:Mostinstructionsareregistertoregister

大多數指令是寄存器到寄存器的

Twophasesofexecution指令周期分為兩個步驟：

I:Instructionfetch取指令

E:Execute(ALUoperationwithregisterinputandoutput)

執行指令(帶寄存器輸入和輸出，完成一個ALU操作)

Forloadandstore裝入和存儲操作需要三個步驟：

I:Instructionfetch取指令

E:Execute(Calculatememoryaddress)

執行指令(計算存儲器地址)

D:Memory(Registertomemoryormemorytoregisteroperation)

存儲器(寄存器到存儲器或反向操作)

52

EffectsofPipelining

Onlyonememoryaccessperphase

LoadA叵；；：；；LoadAM

Tiiiii

Load：[iMl3LoadBM

IlliIII

AddCA?門□函AddCA+

IlliIII

StoreC1EDStoreMC

BranchX；!(10BrunchX

12345678910111213NOOP

(a)Scqucinialexecution123456

Iwo-waypiju-linedliming

Permittingtwomemoryaccessperphase

LoadADWIi

Lo;id!11周二

IIIII

NOOP國33

AddA+HiDBjJ1

II]IJJI

Stare::11k同:

IlliIII

u!rrmi

Branch

IlliIII

N(X)P

12345678

(c)Ihree-waypipelinedtiming

(d)Four-waypipelinedtiming

53

EffectsofPipelining

LoadAM

LoadB

AddA

StoreC

BrunchX

(a)Sequentialexecution

54

EffectsofPipelining

Onlyonememoryaccessperphase

E

LoadBMD]

AddCA+

StoreMC

BranchX

4

567

(b)Two-waypipelinedtiming

55

EffectsofPipelining

PermittingtwomemoryaccessDerphase

亙回

:E0

OOP1;E

Store

ranchX

(e)Three-waypipelinedliming

56

EffectsofPipelining

LoadA

IIlliIIIII

LoadB

1^""IIIII

NOOPI/b㈣HIH

?IIII?????

AddCA+bI11BBlHH

IIIIIIIIII

StoreMII|1年也仙||

IIIIIIIIII

IIII[IIIII

BranchXUH11B間