計算機組織與體系結構

1、COA 大連交通大學軟件學院交通工程+軟件工程10級2班 zsc計算機組織與體系結構 大連交通大學軟件學院交通工程2班 張帥超 2011-11-6 辛卯年Chapter 1 Introduction1.1 Architecture & Organization計算機組織與體系結構Organization is how features are implementedArchitecture is those attributes visible to the programmer1.2 Structure & FunctionStructure is the way in which comp

2、onents relate to each other 部件之間相互連接的方式Function is the operation of individual components as part of the structure各個部件的操作* All computer functions are:1.Data processing 數據處理 2. Data storage 數據存儲3. Data movement數據移動或傳送 4. Control控制* As a computer system 系統(tǒng)級 CPU Control operation of the computer and pe

3、rforms its data processing function Often simply referred to as processor Main memory Stores data I/O Moves data between computer and its external environment System interconnection Some mechanism that provides for communication among CPU, Memory, and I/O * As a component (CPU) 部件級 Control unit Cont

4、rol operation of CPU and computer Arithmetic and logic unit(ALU) 算術邏輯單元 Performs the computers data processing functions Registers 寄存器組 Provides storage internal to the CPU CPU interconnection Some mechanism that provides for communication among control unit, ALU, and registers * As a element (CU) 元

5、件級 Sequencing Login 順序邏輯 Control Unit Registers and Decoders 控制器的寄存器和譯碼器 Control Memory 控制存儲器Function Structure Data storage - - Main memory Data movement - - I/O Data processing - - ALU Control - - CUChapter 2 Computer Evolution and Performance2.1 A Brief History of Computers 計算機簡史G1: vacuum tubes

6、真空管 1.ENIAC 電子數字積分計算機 The major drawback : programmed manually by setting switches and plugging and unplugging cables2.The von Neumann Machine馮諾依曼 Stored-program concept程序存儲概念 Be developed by von Neumann and Turing Program(steps of operating) can be coded and stored in main memory like data IAS comp

7、uter consists of the following:Main memory ALU Control unit I/O3.Commercial Computers 商用計算機G2: transistors 晶體管G3: Integrated Circuits(IC) 集成電路 Fabricate(制造 ) an entire circuit in a tiny piece of silicon rather than assemble discrete components把生產計算機的元件放在一個半導體芯片上1.Microelectronics 微電子學 Function of co

8、mputer elements (a) Gates 門 (b) Memory cell 存儲元 Four basic functions as follow sData storage By memory cells(Main memory) Data processing By gates(ALU) Data movement Memory-gates-memory(I/O) Control Read/Write(CU)2.Moores law 摩爾定律 The number of transistors that could be put on single chip was doubli

9、ng every year. The pace slowed to a doubling every 18 months in the 1970sE.g. Growth in CPU transistor count3.DEC PDP-8 Digital Equipment Corporation 數字設備公司 Original Equipment Manufacturers (OEM) 原始設備制造商 BUS 總線 Data bus Address bus Control bus GL：Later generations Semiconductor Memory半導體存儲 Microproc

10、essors 微處理器 Set of registers (storage in CPU) Memory Buffer Register(MBR) 存儲器緩沖寄存器 Memory Address Register (MAR) 存儲器地址寄存器 Instruction Register (IR) 指令寄存器 Instruction Buffer Register (IBR) 指令緩沖寄存器 Program Counter (PC) 程序計數器 Accumulator (AC) 累加器 Multiplier Quotient (MQ) 乘商寄存器IAS operationInstruction c

11、ycle指令周期 Fetch cycle 取指周期 Execution cycle 執(zhí)行周期2.1 Designing for performance 性能設計Categories of computer Desktop 桌面體 (臺式機、筆記本) Server 服務器 (要求存儲能力和傳輸能力強) Workstation 工作站 (復雜工程、科學應用、計算能力強) We pay attention to things Microprocessor speed 微處理的速度（快） Memory size 存儲容量（大）Performance Mismatch性能不匹配Processor spe

12、ed increased Memory capacity increasedMemory speed lags behind processor speed存儲器速度滯后于處理器速度Solutions解決方案 Increase number of bits retrieved at one time 增加每次取出的位數 Make DRAM “wider” rather than “deeper” Change DRAM interface Cache Reduce frequency of memory accessMore complex cache and cache on chip In

13、crease interconnection bandwidth High speed buses Hierarchy of buses補充知識（1）二進制（2）邏輯運算補充一：B/KB/MB/GB 單位換算 1 byte (B) = 8 bits (b) 字節(jié)=8個二進制位 1Kilobyte(K/KB)=210 bytes=1,024 bytes 千字節(jié) 1Megabyte(M/MB)=220 bytes=1,048,576 bytes 兆字節(jié) 1Gigabyte(G/GB)=230bytes=1,073,741,824bytes 千兆字節(jié) 補充（二）：邏輯運算（AND、OR、NOR、XO

14、R） AND 與 兩者都是“真”則結果必“真”，有一個為“假”則結果必“假”O(jiān)R 或 兩者都是“假”則結果必“假”，有一個為“真”則結果必“真”NOR 非或反 “真”變“假” ， “假”變“真”XOR 異或 相同為0，相異為1 NOTE：多位二進制數時，各對應位分別進行運算 Chapter 3 A Top-Level View of Computer Function and Interconnection 頂層計算機的功能和互連 系統(tǒng)總線3.1 Computer components The Control Unit and the Arithmetic and Logic Unit con

15、stitute the Central Processing Unit控制器和運算器構成CPU Data and instructions need to get into the system and results out Input/output系統(tǒng)要輸入數據和指令，輸出結果 Temporary storage of code and results is needed Main memory需要暫時存儲(數據的和指令的)編碼和結果3.2 Computer FunctionExecute (or deal with) instruction1. An instruction cycle

16、(simplest) Fetch(取指令)& Execute (執(zhí)行指令)Instruction formatOpcode:0001=Load AC from Memory 0010=Store AC to Memory 0101=Add to AC from Memory 0001 1001 0100 0000 =1 940H (940H)=AC Means Load data to AC from 940H of Memory 0101 1001 0100 0001 =5 941H (941H) +(AC)=AC Means Add to AC with data from 941H 00

17、10 1001 0100 0001 = 2 941H (AC) =(941H) Means Store data in AC to 942H2.Interrupts 中斷Mechanism by which other modules (e.g. I/O) may interrupt normal sequence of processingsuspending 掛起 branching 分支processing 處理resuming 恢復3.Interrupt Cycle 中斷周期 Added to instruction cycle Processor checks for interru

18、pt Indicated by an interrupt signal If no interrupt, fetch next instruction If interrupt pending（未處理）:-Suspend execution of current program -Save context -Set PC to start address of interrupt handler routine -Process interrupt interrupt handler program -Restore context and continue interrupted progr

19、am4.Multiple Interrupts Define priorities(優(yōu)先級)-Low priority interrupts can be interrupted by higher priority interrupts-When higher priority interrupt has been processed, processor returns to previous interrupt (in nest as they occur)3.3 Connecting Structures3.4 Bus Interconnection Single and multip

20、le BUS structures are most common1.What is a Bus?A communication pathway connecting two or more devicesUsually broadcast 廣 播 Often grouped Power lines may not be shown2.system Bus A bus that connects major computer components(CPU, Memory, I/O) Three main functional groups Data bus 數據總線 -Address bus

21、地址總線 Control bus 控制總線(1)Data Bus Carries data Remember that there is no difference between “data” and “instruction” at this level “Width” is a key determinant of performance -8, 16, 32, 64 bit(2)Address bus Designate the source or destination of data e.g. CPU needs to read an instruction from a give

22、n location in memory Bus width determines maximum memory capacity of system e.g. 8080 has 16 bit address bus giving 64k address spaceInsertion 可以推出N位十進制整數表示范圍為0至10N-1，共10N個數 繼續(xù)：則N位二進制整數表示范圍為0至2N-1，共2N個數 例如：四位b3b2b1b0可表示0000至1111共24=16個數 N位的二進制地址編碼可以在2N個存儲“字”中確定一個“字”-尋址范圍(addressing range)或稱為存儲空間(mem

23、ory space)(3)Control Bus Control and timing information Memory read/write signal Interrupt request Clock signals時鐘信號，用于同步操作3.Single Bus Problems Lots of devices on one bus leads to: Propagation delays 傳播延遲 Long data paths mean that co-ordination of bus use can adversely affect performance If aggrega

24、te data transfer approaches bus capacity Most systems use multiple buses to overcome these problems4.Elements of Bus Design type總線類型 Method of arbitration總線仲裁方法 Timing定時 Bus width數據寬度 Data transfer type數據傳輸類型(1)Bus Types Dedicated Separate data & address lines Multiplexed Shared lines (data & addres

25、s共用，時間分前后，再加控制信號) Address valid or data valid control line Advantage - fewer lines Disadvantages More complex control Reduce in performance(2)Bus Arbitration 仲裁 More than one module controlling the bus e.g. CPU and DMA controller Only one module may control bus at one time 集中式 Arbitration may be cen

26、tralised or distributed 分散式(3)Timing定時Co-ordination of events on bus (協(xié)調)Synchronous(同步)Asynchronous (異步)(4)Bus width The number of lines being referred to width of bus Width of data bus impacts on system performance性能 Width of address bus impacts on system capacity容量（5）.Data transfer type Write/rea

27、d operation（multiplexed） Write/read operation（no multiplexed） Write-modify-read operation(不能分開,馬上進行) Read -after-write operation Block data transfer成塊傳輸Chapter 4Cache Memory 高速緩沖存儲器4.1 Computer Memory System Overview1.Characteristics of memory Systems (1)LocationCPU (registers, cache) Internal (main

28、 memory, cache) External (disk, tape)(2)Capacity容量=字數x字長 Word size word length (字長) The natural unit of organisation 8,16,32bits Number of words (字數) or Bytes注意：字（word）在不同的機器上位數不同，它不是一個公認的單位，而字節(jié)是標準單位：1Byte=8bits(3)Unit of Transfer傳輸單位 Internal “word” Usually governed by data bus width Be equal to th

29、e word length (size) (or xx bits) External “block” Usually a block which is much larger than a word(e.g.4,8,16) 1block=2n words(4)Access Methods Sequential access 順序存取 e.g. tape Start at the beginning and read through in order Access time depends on location of data and previous locationDirect acces

30、s 直接存取 e.g. disk Individual blocks have unique address Access time depends on location of data and previous locationRandom access 隨機存取 e.g. RAM(Main memory) Individual addresses identify locations exactly Access time is independent of location or previous accessAssociative access 關聯(lián)存取 e.g. cache Dat

31、a is located by a comparison with contents of a portion of the store Access time is independent of location or previous access(5)Performance(6)Physical Types Semiconductor 半導體 RAM （DRAM & SRAM) Magnetic 磁 Disk & Tape Optical 光 CD & DVD Magnetic Optical 磁-光 MO(用的少)(7)Physical Characteristics物理特性 Vola

32、tile/nonvolatile 易失性 非易失性 Erasable/nonerasable 可擦除 不可擦除（可讀可寫 ） （只讀）2.Memory Hierarchy 存儲器分層結構 Registers In CPU Internal or Main memory May include one or more levels of cache “RAM” External memory Backing store 將存儲備份寄存器組 高速緩沖存儲器 主存儲器 磁盤 CD光盤 DVD光盤 磁帶-光-磁盤 一寫多讀光盤 （刻錄盤）1.每位價格降低 2.容量大 3.存儲時間長（速度慢 Hhit

33、on radio (x%) , Taverage Access time T1access time to L1, T2access time to L2 T=HT1+(1-H)(T1+T2)=T1+(1-H)T2 Suppose H=95, then T=T1+(1-0.95)T2=0.015us Result: Speed=L1 Access time Capacity=L2 capacity4.2 CacheCache operation - overviewCPU requests contents of memory location Check cache for this dat

34、a If present, get from cache (fast) If not present, read required block from main memory to cache Then deliver from cache to CPU Cache includes tags to identify which block of main memory is in each cache slot(line)4.3 Elements of Cache DesignCache size (capacity)容量 Mapping Function映射函數Replacement A

35、lgorithm替換算法 Write Policy寫策略Line Size行大小 Number of Caches Cache 數量1.Size does matter Cost More cache is expensiveSpeed More cache is faster (up to a point) 2.Mapping Function(1) 映射函數 determine which main memory block currently occupies a cache line Three techniques：Direct Mapping 直接映射 Associative Ma

36、pping 關聯(lián)映射Set Associative Mapping 組關聯(lián)映射*(1)Direct Mapping 直接映射 Each block of main memory maps to only one (the fixed) cache line i.e. if a block is in cache, it must be in one specific place Address code length is divided 3 parts ：技術處理 Right bits identify unique word in the block (word number :Word#

37、)字的編號 Middle bits specify caches location (line number : line #)行的編號 Left bits serve as mark ( tag ) 標志Note： Word number 字的編號（字號） Number of words 字數 Line number 行的編號（行號） Number of lines 行數 block number 塊的編號（塊號） Number of blocks 塊數 Address code length 地址碼長度(RA)Elements for all three casesCache of 64k

38、bytes ( or word ) Cache block of 4 bytesi.e. cache is 16k (214) lines of 4 bytes 16Mbytes main memory Cache Size=64KBytes = (216)bytes ( or word ) Cache Line size=4bytes=(22)bytes Number of cache Lines=(216)bytes/(22)bytes/line=(214) line Block size=Line size=4bytes =(22)bytes Main Memory Size=16MBy

39、tes=(224)bytes Number of memory blocks=(224)bytes/(22)bytes/block = (222) block Length of RA=24 bits (224=16M) M=2N NAddress code bits MAddressable memory capacityRA=Real Address 實地值 或真實地址e.g. 16 339CH 0001 0110 | 00 1100 1110 0111 | 00B tag=16H r=0CE7H w=0HDirect Mapping Summary Number of addressab

40、le units = 2n words or bytes =Address length = n bits (RA) Block size = line size = 2w words or bytes = Size of word# = w bits Number of blocks in main memory = 2n / 2w = 2n-w Number of lines in cache=2L = Size of line# = L bits RA=n bits Size of tag = (n-w-L)bits tag L w bits(2)Associative Mapping

41、(關聯(lián)映射/全關聯(lián)映射） A main memory block can load into any line of cache Memory address code is interpreted as tag and word#e.g. 16339CH 00 0101 1000 1100 1110 0111 | 00B tag=058CE7H w=0HAssociative Mapping Summary Address length =n bits=(tag bits + word#) Number of addressable units = 2n words or bytes Blo

42、ck size = line size = 2w words or bytes Number of blocks in main memory =2n / 2w = 2 n-w Number of lines in cache=undetermined Size of tag = n-w bits在地址格式中未確定 可映射到cache中的任意一行(3).Reviews（回顧） Direct Mapping Each block of main memory maps to only one (the fixed) cache line Simple/Inexpensive -Conflict/

43、hit miss highly Associative Mapping a main memory block can load into any line of cache Flexible -Compare tag difficulty(3)Set Associative Mapping 組關聯(lián)映射 Cache is divided into a number of sets Each set contains a number of lines A given block maps to any line in a given (the fixed) set e.g. Block B c

44、an be in any line of set i e.g. 2 lines per set 2-way associative mapping A given block can be in one of 2 lines in only one set (fixed)e.g. 16339CH 0001 0110 0 | 0 1100 1110 0111 | 00B tag=02CH set=0CE7H w=0HSet Associative Mapping Summary Address length = n bits Number of addressable units = 2n wo

45、rds or bytes Block size = line size=2w words or bytes Number of blocks in main memory = 2n-w Number of lines in set = k （k行一組） Number of sets = v = 2s Number of lines in cache = kv = k * 2s Size of tag = (n s w) bits3.Replacement Algorithms 替換算法(1)Direct mapping When a new block is brought into the

46、Cache,one of the existing block must be replaced ,No choice, Each block only maps to one line(a fixed line),Replace that line(2)Associative & Set Associative mappingLeast Recently used (LRU) 最近最少使用法Each line includes a Use bit,when a line is referenced(or accessed),its Use bit is set to 1 and the Us

47、e bit of the other line in same set is set to 0. So, the Use bit is 0,meaning the line is LRU, replacement is occurring in the line4.Write Policy寫策略(1)Write through All writes go to main memory as well as cache The data in a cache line is changed(write), the change must occur in memory block at the

48、same time(2)Write back寫回/拷回法 Updates initially made in cache only Update bit for cache line is set when update occurs If block is to be replaced, write to main memory only if update bit is set5.Line Size行的大小 Line size=block size Simple, a large block size(same as line size) may rise the hit in ratio

49、 But heavy traffic to bus尺寸大的行，可以增加命中率，但是傳輸過程中對總線的壓力增大。6.Number of Caches Cache數目 Multilevel Caches多級Cacheon chip cache(片內Cache),or board cache(板上Cache)CPU,L1 Cache,L2 Cache,Memory Unified versus Split Caches統(tǒng)一和分立Cacheon-chip cache holds data & instructionsUnified cache , dynamic adjust the size of

50、data or instruction by Hit On RadioSplit cache:data writes back memory, but instructions does not Exercise Set Associative MappingA four-way set associative cache has 64k words,main memory has 256M words and divided 32M blocks(12 points) 1.Show the mapping format. 2.Where in the cache is the data fr

51、om memory location FDB9753H?(when read from memory). 3.Where in the memory is the data from cache set number 09DH and tag value 1357H?(when write to memory).Analyze分析 A four-way set associative cache has 64k words,main memory has 256M words and divided 32M blocks four-way: 4 lines/set Cache size= 64

52、k words Memory size= 256M words =RA= 28 bits block size= 256M words/32M=8 words (Line size= 8 words =W#= 3 bits ) Cache size/line size/k lines/set =64k words /8 words /4 lines/set=2K sets =Set#= 11 bitsAnswer1.Line size=Block size=256Mwords/32Mblocks =23words Number of sets =64Kwords/ 23words/4lines

53、/set =211sets Memory size=256Mwords=228words RA=28 bits tag=28-3-11=14 bits2.FDB9753H=1111 1101 1011 10 01 0111 0101 0 011B 3F6EH 2EAH 3H The data in memory address FDB9753H is mapping to set 2EAH,tag is 3F6EH.3. 1357H 09DH xxxbits=01 0011 0101 0111 000 1001 1101 xxxB 4D5C4E8H4D5C4EFH the data in set 09DH and tag value 1357H write to memory address 4D5C4E8H.Chapter 5 Internal Memory內部存儲器5.1 Semiconductor Main Memory1.Organiza