Computer Organization (Autonomous)

21-07-2017SYLLABUSComputer Organization(Autonomous) The Memory System: Memory Hierarchy, Main memory - RAM and ROM Chips,Memory Address Maps, Memory Connection to CPU, Auxiliary memory – MagneticDisks, Magnetic Tape, Associative Memory – Hardware Organization, Match Logic,Cache Memory – Associative Mapping, Direct Mapping, Set- Associative Mapping,Writing into Cache, Virtual Memory – Address Space and Memory Space, AddressMapping using Pages, Associative Memory Page Table, Page Replacement.UNIT IVSections - A & DPrepared byAnil Kumar Prathipati, Asst. Prof., Dept. of CSE.2Memory OrganizationINDEX Memory HierarchyThe memory system can be characterized with Main Memory Auxiliary Memory Location: Where it can be located, Processor, Internal, External .12-4 Capacity: size in terms of bytes, KB, MB, GB, etc Associative Memory Cache Memory Virtual Memory Unit of transfer: How many bits can be moved like bytes, words, Blocks, etc . Access method: How you pick of data Sequential, Direct, Random, etc Performance: Transfer rate n terms of bps Physical type: Which material we are using like semiconductor, Magnetic,Optical, etc Physical characteristics: like power consumption, information loss, volatile, etc Organization: How it stored like continues, interleaved, etc .3Chap. 12 Memory Organization1

21-07-201712-5Memory Organization 12-612-1 Memory Hierarchy Memory hierarchy in a computer system Main Memory : memory unit that communicates directly with the CPU (RAM) Auxiliary Memory : device that provide backup storage (Disk Drives) Cache Memory : special very-high-speed memory to increase the processing speed (Cache RAM)Auxiliary memoryMagnetictapesMainmemoryI/O processorMagneticdisksCachememoryCPU Multiprogramming enable the CPU to process a number of independent program concurrently.Chap. 12 Memory OrganizationChap. 12 Memory Organization12-7 Memory Address Map12-2 Main Memory Bootstrap Loader A program whose function is to start the computer software operating when power is turned on RAM and ROM Chips Typical RAM chip Memory Configuration : 512 bytes RAM 512 bytes ROM Memory Address Map» 1 x 512 byte ROM 4 x 128 bytes RAMTypical ROM chip512 X 8 ROM : 29 512 (9 bit address lines) Chip select 2CS2ReadRDWriteWR7 bit addressAD7 001 01 10987 - 1RD WR RAMRAMRAMRAM111100110101 128 8RAM8 bit data busMemory functionInhibitInhibitInhibitWriteReadInhibitState of data busHigh-impedanceHigh-impedanceHigh-impedanceInput data to RAMOutput data from RAMHigh-impedance Chip select 1CS1Chip select 2CS2ROM13 2 1 0CS1CS2: 0000: 0080: 0100: 0180RD- 007F- 00FF- 017F- 01FF Data128 8RAM 2Data128 8RAM 3Data128 8RAM 4Data128 8ROMDataCS1CS2RDWRAD7: 0200 - 03FFCS1Memory Connection to CPU 128 8RAM 1WRAD7CS2RD» 2 x 4 Decoder : RAM select (CS1)» Address line 10512 8ROMData busDecoder» Address line 10(a) Block diagramCS1 CS2 RD WRCPUAddress bus16 - 11» Address line 9 8 CS1010001 » 128 X 8 RAM : 2 7 128 (7 bit address lines)Chip select 100111112-8WRAD7CS1RAM select : CS2ROM select : CS2 InvertCS2RDWR8 bit data busAD7CS1CS29 bit address1-7AD98AD99(b) Function tableChap. 12 Memory OrganizationChap. 12 Memory Organization2

21-07-201712-9 Tracks12-3 Auxiliary MemorySector Magnetic Disk : FDD, HDD Magnetic Tape : Backup or Program Optical Disk : CDR, ODD, DVD 12-10textA1AjAnK1KjKn12-4 Associative Memory Content Addressable Memory (CAM) Read/WriteheadA memory unit accessed by contentBlock DiagramArgument register (A)Word 1C 11C1jC 1nM1Word iCCijCMiKey register (K)ArgumentA Register 101 111100K Register 111 000000InputWord 1Word 2Word mAssociative memoryarray and logic100 111100 M 0101 000011 M 1Match Logici1inMatchregisterKey (Mask)WriteC m1C mjC mnMmMBit 1ReadBit jBit nm wordsn bits per wordM 1OutputChap. 12 Memory OrganizationChap. 12 Memory Organization12-11 12-12 Mapping12-5 Cache Memory Locality of Reference the references to memory tend to be confined within a few localized areas in memory Cache Memory : a fast small memory keeping the most frequently accessed instructions and data in the fast cache memory Cache cache size : 256 K byte mapping method : 1) associative, 2) direct, 3) set-associative replace algorithm : 1) LRU, 2) LFU, 3) FIFO write policy : 1) write-through, 2) write-back The transformation of data from main memory to cache memory» 1) Associative mapping» 2) Direct mapping» 3) Set-associative mapping Example of cache memorymain memory : 32 K x 12 bit word (15 bit address lines)cache memory : 512 x 12 bit word Hit Ratio the ratio of the number of hits divided by the total CPU references (hits misses) to memory» hit : the CPU finds the word in the cache (0.9)» miss : the word is not found in cache (CPU must read main memory) cache memory access time 100 ns, main memory access time 1000 ns, hit ratio 0.9» 1 miss : 1 x 1000 ns penalty time(1 x 100 ns)» 9 hit : 9 x 100 nsChap. 12 Memory OrganizationMain memory32K 12CPUCache memory512 12» CPU sends a 15-bit address to cacheHit : CPU accepts the 12-bit data from cacheMiss : CPU reads the data from main memory (then data is written to cache) Associative mapping Cache memory associative memory Address Data Cache memoryTag field (n - k) Index field (k)2k words cache memory 2n words main memory Cache Coherence (Sec. 13-5)CPU address(15 bits)Argument registerAddressData010003450027776 710223451 234Tag 6 bit (15 - 9), Index 9 bitChap. 12 Memory Organization3

21-07-201712-136 bits12-149 bitsTag Index Tag (6 bit)00 - 63 00Index (9 bit)000 - 511Direct mapping cache with block size of 8 words64 block x 8 word 512 cache words size00000032K 12HexAddressOctaladdressMain memory1FF3F 1FF512 12Cache memoryAddress 9 bitsData 12 bits8 word block 8Block 0Address 15 bitsData 12 bitsIndexTagDataTagData0000 13 4 5 00 25 6 7 07770 26 7 1 00 02 3 4 0Index010Block 1 Memoryaddress Memory data0000001 2 2 0Direct mapping cache organization007772 3 4 0010003 4 5 0017774 5 6 0020005 6 7 0027776 7 1 0Indexaddress000017TagData001 2 2 0026 7 1 07700277702Block 637776710(b) Cache memory Set-associative mapping : Fig. 12-15 (two-way) Direct mapping Index tag ( 02777, 01777 )(a) Main memoryChap. 12 Memory OrganizationChap. 12 Memory Organization12-15 Replacement Algorithm : cache miss or full 1) LRU (Least Recently Used): On a miss, the frame that was least recently used in replaced.2) LFU (Least Frequently Used): It looks forward in time to see which frame to replace on a cache miss.3) FIFO (First-In First-Out): On a miss, the frame that has been in memory the longest is replaced. Ex: 1 2 3 2 1 5 2 1 6 2 5 6 3 1 3 6 1 2 4 3 Writing to Cache : Cache Coherence12-16 12-6 Virtual Memory Virtual Memory : Auxiliary memory Main memoryTranslate program-generated (Aux. Memory) address into main memory location Intel Pentium Processor» Give programmers the illusion that they have a very large memory, even though the computer actually has arelatively small main memory» Physical Address Lines A 0 - A31 : 232 230 X 22 4 Giga» Logical Address 46 bits address : 2 46 240 X 26 64 Tera» 1) Write-through» 2) Write-back Main memory» Address used by a programmerCache is initialized» 1) when power is applied to the computer» 2) when main memory is loaded with a complete set of programs from auxiliary memory Auxiliary memory Address Space & Memory Space Address Space : Virtual Address Cache Initialization Program 1Memory Space : Physical Address(Location)Data 1,1» Address in main memory Figurevalid bit» indicate whether or not the word contains valid data address space (N) 1024 K 220Program 2Data 2,1» Auxiliary Memory memory space (M) 32 K 215» main MemoryChap. 12 Memory OrganizationProgram 1Data 1,2Data 1,1Memory spaceM 32K 215Address spaceN 1024K 220Chap. 12 Memory Organization4

21-07-201712-17 Memory table in a paged system Memory table for mapping a virtual address 12-18Translate the 20 bits Virtual address into the 15 bits Physical addressPage no.Virtual address1 0 1Virtualaddressregister(20 bits)Main memoryaddressregister(15 01110111MainmemoryMemory tablebuffer registerMain memorybuffer registerPage 0 01 0101010011Main memoryaddress registerVirtual addressMain memoryBlock 0Block 1Block 2Block 3MBRPage 2Address mapping Address spacememory spacefixed size 01100110101101PresencebitPage 1 Address Mapping Using Pages 1100Line number0 1 0 1 0 1 0 0 1 1Page 3Page 4Block 0Page 5Block 1Page 6Address space : 1 K pageMemory space : 1 k blockPage 7Address spaceN 8K 21301Block 21Memory page tableBlock 3Memory spaceM 4K 212Chap. 12 Memory OrganizationChap. 12 Memory Organization12-19 Associative memory page table Associative memory block number(01)Virtual memoryPage no.10111100Key register00110101101010011010Associative memoryPage no.Line numberArgument registerBlock no. Page(Block) Replacement Page Fault : the page referenced by the CPU is not in main memory Replacement algorithm» a new page should be transferred from auxiliary memory to main memoryChap. 12 Memory Organization5

21-07-2017 2 Chap. 12 Memory Organization Memory Organization 12-5 12-1 Memory Hierarchy Memory hierarchy in a computer system Main Memory: memory unit that communicates directly with the CPU (RAM) Auxiliary Memory: device that provide backup storage (Disk Drives) Cache Memory: special very-high-