Part 3.pdf

COMPUTER ORGANIZATION: 3. MEMORY Instructor: Dr. Abrar Wafa Based on notes from Dr. Fakhry Kellah COMPUTER ORGANIZATION: 3. MEMORY Instructor: Dr. Abrar Wafa Based on notes from Dr. Fakhry Kellah OVERVIEW CLO3: Describe the organization of the basic computer system and its major functional uni...

COMPUTER ORGANIZATION: 3. MEMORY Instructor: Dr. Abrar Wafa Based on notes from Dr. Fakhry Kellah COMPUTER ORGANIZATION: 3. MEMORY Instructor: Dr. Abrar Wafa Based on notes from Dr. Fakhry Kellah OVERVIEW CLO3: Describe the organization of the basic computer system and its major functional units. CLO4: Describe the organization and architecture of computer memory and buses. Outline: q Memory definitions q Memory organization q Basic operations q ROM q Cache 3 ORGANIZATION OF COMPUTER MAIN MEMORY Stores programs & data (input, output, intermediate). 4 MEMORY DEFINITIONS Memory ─ A collection of storage cells together with the necessary circuits to transfer information to and from them. Memory Organization ─ the basic architectural structure of a memory in terms of how data is accessed. Random Access Memory (RAM) ─ a memory organized such that data can be transferred to or from any cell (or collection of cells) in a time that is not dependent upon the particular cell selected. Memory Address ─ A vector of bits that identifies a particular memory element (or collection of elements). 5 MEMORY DEFINITIONS (CONTINUED) Memory Data ─ a bit or a collection of bits to be stored into or accessed from memory cells. Typical data size: ­ bit ─ a single binary digit ­ byte ─ a unit of digital information that most commonly consists of eight bits. Ø A byte (of 8 bits) has a limited range of 256 values. When a value is beyond this range, it has to be stored in multiple bytes. A number such as 753 requires at least two bytes of storage. ­ word ─ a group of n-bits which can be accessed together Ø Word size is processor dependent. Ø Normally in multiples of 8. For example: 8, 16, 32 or 64-bits. Memory Operations ─ operations on memory data supported by the memory unit. Typically, read and write operations over some data element (bit, byte, word, etc.). 6 MEMORY ORGANIZATION Ø Memory is built from millions of storage cells that are organized as an indexed array of words. Ø Value of the index for each word is the memory address. Ø Each word is assigned a location number called the word address. Ø If address is given to individual words then the memory is word-addressable (Figure a, assuming word size = 4 bytes). Ø However, if the address is given to individual bytes then the memory is byte-addressable (Figure b). In this case, the word address is the address of the first byte in the word. 7 MEMORY SIZE The memory size represents the total number of bits the memory can store. The size can be given in terms of Kilo = 210 or Mega = 220 or Giga = 230. There are many ways to interpret the memory size for example, if the total memory size is 96bit, then it can be interpreted as: Ø 96 memory words each of size one bit, or Ø 12 memory words each of size 8 bits , or Ø 6 memory words each of size 16 bits, or Ø 1 memory word of size 96 bits. To have a full knowledge about the memory, the size is always expressed as product of the number of words and the size of each word in bits. Ø Memory total size (bits) = # of words x size of each word in bits. 8 BASIC MEMORY OPERATIONS Memory operations require the following: 1. Data ─ data written to, or read from, memory as required by the operation. 2. Address ─ specifies the memory location to operate on. The address lines carry this information into the memory. Typically: n bits specify locations of 2n words. 3. Operation Control – Information sent to the memory and interpreted as control information which specifies the type of operation to be performed. Typical operations are READ and WRITE. Chapter 8 9 MEMORY CHIP BLOCK DIAGRAM m Data Input Lines Any memory chip has three sets of pins or connectors that are used to connect the memory to the outside world. These sets are: 1. 2. 3. Address Pins: in the figure, n address lines are used to reference 2n words of memory. Data Pins: in the figure, each word is m bits. Control Pins: in the figure, Read, Write, and Enable are single control lines defining the simplest of memory operations. m n Address Lines n Read Write Enable 1 Memory Unit 1 1 m m Data Output Lines 10 MEMORY SIZE m Data Input Lines Ø Ø Ø Ø Number of Address pins = n Number of words = 2n Number of data pins = size of each word in bits (m) n Address Lines Memory total size (bits) = # of words x size of each n word in bits. 1 Read 1 Write 1 Enable m Memory Unit m m Data Output Lines 12 EXAMPLE 1 A memory with 3 address bits & 8 data bits has: How many words are there? ­ n = 3 and m = 8 ­ 23 = 8 words What is the size of each word? ­ 8-bits Memory Address Binary Decimal Memory Content 000 0 10001111 001 1 11111111 010 011 2 3 10110001 00000000 100 4 10111001 101 5 10000110 11 0 6 00110011 111 7 11001100 EXAMPLE 1- SIZE OF MAR AND MDR A memory with 3 address bits & 8 data bits has: How many words are there? ­ n = 3 and m = 8 ­ 23 = 8 words What is the size of each word? ­ 8-bits Ø What is the size of MAR and MDR? Ø Size of MAR is equal to number of address lines (n) bits MAR = 3 Ø Size of MDR is equal to size of each word (m) bits MDR = 8 EXAMPLE 2 Draw a figure for memory chip of size 512K x 8 Example memory contents: A memory with 19 address bits & 8 data bits (n = 19 and m = 8) How many words? 512 KB = 29 * 210 = 219 bits What is the size of each word? 8-bit data. How many control pins? 3 What is the size of MDR? 8 What is the size of MAR? 19 x R W EN 15 EXAMPLE 2 Draw a figure for memory chip of size 512K x 8 Example memory contents: A memory with 19 address bits & 8 data bits (n = 19 and m = 8) How many words? 512 KB = 29 * 210 = 219 bits What is the size of each word? 8-bit data. How many control pins? 3 What is the size of MDR? 8 What is the size of MAR? 19 x R W EN 15 EXAMPLE 3 In 2K x 10 Memory - find number of address pins, number of data pins, memory size, MDR and MAR size? Solution: Number of data pins = size of each word in bits = 10 bits Number of words = (2K = 21 x 210 = 211=2048) Number of address pins (n) =11 Memory total size in bits = # of words x size of each word in bits = 2048 x 10 = 20480 bits Size of MDR is 10 bits Size of MAR is 11 bits 16 COMMUNICATION BETWEEN THE MAIN MEMORY AND THE CPU Ø The memory is connected to the processor by the address, data, and control lines. Address lines Control lines Data lines Ø Address lines at the processor side are connected to the MAR which has the same size as the number of address lines (Pins). Ø Address lines are unidirectional. Ø Data lines at the processor side are connected to the MDR register which has the same size as the memory word. Ø Data lines are bi-directional. 17 READ AND WRITE OPERATION Ø Read Memory ─ an operation that reads a data value stored in memory: 1. CPU places the address of the memory word to be retrieved into MAR register. 2. CPU will set the read control to 1 3. The memory will respond by putting the content of the specified word into the data lines. Address lines Control lines Data lines Ø This means that the word is now loaded into the CPU MDR register. 18 READ AND WRITE OPERATION Ø Write Memory ─ an operation that writes a data value to memory: Address lines Control lines Data lines 1. CPU loads the address of the memory word to be written into MAR register. 2. CPU loads the word to be written into MDR. 3. CPU will set the write control to 1 4. The memory will respond by storing the word at the specified address. 19 CHARACTERISTICS OF RAM Ø The Main Memory is called Radom Access Memory (RAM). Ø Random access means that individual memory words can be accessed directly by specifying their addresses, with same access time regardless of location. Types of Random Access Memory (RAM): ­ Static (SRAM) – information stored in latches/ flip-flops ­ Dynamic (DRAM) – information stored as electrical charges on capacitors 20 CHARACTERISTICS OF RAM The following table shows the difference between both types SRAM and DRAM: Static RAM (SRAM) Dynamic RAM (DRAM) Storage cell is a single Flip Flop which is Storage cell is made of a single transistor built from six transistors è Large storage and a capacitor è smaller storage cell cell Contents are saved as long as the power Contents must be refreshed (reloaded) is kept on. every few milliseconds to prevent loss. Fast because no refreshing Slow because of the refreshing Used for cache Used for main memory 21 SYNCHRONOUS DRAM (SDRAM) SDRAM Ø Access is synchronized with a clock. Ø SDRAM moves data in time with system clock, CPU knows when data will be ready. Ø CPU does not have to wait; it can do something else. DDR-SDRAM Ø Double data rate DRAM (DDR-SDRAM) sends data twice per clock cycle. RAM INTEGRATED CIRCUITS The main memory (RAM) is volatile, which means if the power turns off, the memory loses its content. Ø Dependence on Power Supply: ­ Volatile – loses stored information when power turned off ­ Non-volatile – retains information when power turned off Chapter 8 23 READ ONLY MEMORY (ROM) 24 READ ONLY MEMORY (ROM) Ø Read Only memory (ROM) contains data that cannot be changes. Ø Data are written into ROM when it is manufactured. Ø ROM is nonvolatile; that is , no power source is required to keep the stored data. Ø It is possible to read the ROM but not possible to write new data into it. Ø ROM is used in many applications: § Store the compiler/interpreter inside the CPU. § Store the program that will load the operating system when the computer is turned on. 25 READ ONLY MEMORY (ROM) Ø Types of ROM: § PROM § EPROM § EEPROM § Flash Memory All the memories listed in the following table are considered to be random access. 26 BYTE ORDERING 27 BYTE ORDERING PROBLEM Ø There are two systems for storing bytes representing numbers in memory words: 1. Little-endian 2. Big-endian Ø Little and big endian are two ways of storing multi-byte data-types (int, float, etc.). 28 BYTE ORDERING PROBLEM 1. little-endian: Bytes representing numbers are stored starting from the rightmost byte (the least significant byte) then remaining bytes in increasing order of significance. § This system is used in Intel Processors. 2. Big-endian: Bytes representing numbers are stored starting from the leftmost byte (the Most significant byte) then remaining bytes in decreasing order of significance.. § This system is used in SUN SPARC processors, IBM mainframes, Apple Mac, and most RISC machines. 29 EXAMPLE Show how number (15)10 is stored in a 32-bit word size for both systems? 32-bit representation of (15)10 is (0000000F)16 Solution: Little-end 0F 00 00 00 Big-endian 00 00 00 0F 30 CACHE MEMORY 31 MEMORY HIERARCHY 32 WHY CACHE MEMORY? Ø Analysis of programs shows that most of the program time is spent on executing many instructions repeatedly. Ø Many instructions in localized areas of the program are executed repeatedly during some period of time, and the remainder of the program is accessed relatively infrequently. Ø These instructions may be § a simple loop, § nested loops, or § a few procedures that repeatedly call each other. 33 CACHE MEMORY Ø Can we have those frequently/repeatedly executed instruction in a faster storage that is closer to CPU? Ø Yes, in cache. Ø The effectiveness of the cache operation is based on the locality of reference or locality principle. Ø Cache memory is small and fast memory that sits between the main memory and the CPU which may be located on the CPU chip. 34 TEMPORAL VS. SPATIAL LOCALITY Locality of reference happens in two ways: temporal and spatial. Temporal Locality ØMeans that a recently referenced memory word will be referenced again very soon. ØTemporal locality happens when CPU executes § Iterative loops § Calls to subroutines Spatial Locality Ø Means that memory words close to recently referenced memory word will be referenced soon. Ø Spatial locality is seen when the CPU performs operations on § Tables § Arrays 35 TEMPORAL VS. SPATIAL LOCALITY Ø The temporal locality suggests that whenever a word is first needed, it should be brought to cache where it will hopefully remain until it is needed again. Ø The spatial locality suggests that instead of fetching just one word from the main memory to the cache, several words adjacent to the needed word are also fetched into the cache. The memory circuitry is designed to take advantage of the locality of reference. 36 CACHE/MAIN MEMORY STRUCTURE CACHE READ OPERATION § The processor will first look for the word in the cache. Ø If the word exists, then cache hit occurs, and the word will be delivered to the processor. Ø If the word is not in the cache, then cache miss occurs, and the block (in the main memory RAM) containing the word is loaded into the cache and the word is delivered to the processor. 38 CACHE WRITE OPERATION There are two cache write policies: 1. Write Through Policy § All write operations are made to the main memory as well as to the cache at the same time. § Advantage: Both Cache memory and main memory will have same data all the times (consistency) § Disadvantage: Generates a lot of memory traffic, thus, slows down memory write operation. 39 CACHE WRITE OPERATION 2- Write Back Policy § All write operations are made to the cache memory ONLY. § Advantage: Fast write operation and no additional memory traffic § Disadvantage: Ø not all the main memory content is consistent with the cache content all the times. Ø All access by I/O devices should be done through the cache and this requires complex hardware. 40 CACHE TYPES There are two main cache types: Uniform cache and Split cache. Uniform Cache Ø Stores both instruction and data. Ø Uniform cache will not allow fetching instruction and data to happen at the same time. Split cache Ø Internally divided into two caches one stores only instructions (I-cache) and the other one stores only data (D-cache). Ø When split cache is used, the fetch instruction unit can access I-cache to fetch one instruction and at the same time the fetch operand unit can access the D-cache to fetch operands of another instruction. Ø Allows parallel processing of instructions and used with the pipelined processor. 41 CACHE TYPES Uniform Cache Split cache Memory hierarchy showing uniform and split caches 42 MULTILEVEL CACHES In the computer system, there are usually three cache levels as follows. level 1 cache (L1 Cache) Level 2 cache (L2 Cache) Level 3 cache (L3 Cache) §Located inside the CPU chip itself. §Usually split cache. §Typical size is 16 Kbytes to 64 Kbytes. §Connected to the CPU by very highspeed bus. §Slower than L1 cache but much larger in size. §Usually uniform. §Typical size is 512 Kbytes to 1 Mbytes. § Originally located on motherboard and accessible over the external bus. § Faster than the main RAM memory. § Usually uniform. § Typical size is few megabytes. 43 MULTILEVEL CACHES § Recently, most processors have added L2 and L3 caches to the processor chip. § A system with multilevel cache would appear to the processor as a single memory unit but much faster than it really is. 44 COMPUTER PERFORMANCE WITH CACHE The hit ratio is defined as the fraction of all memory accesses that are found in the cache. It is calculated as follows: ­ If the number of times the CPU access the same memory location to Read or Write within a very short period of time is K, then ­ Hit ratio h !"# = ! ­ Miss ratio # 1–h=! 45 Example Ø Suppose that CPU accesses the same memory location 10 times within a very short period of time. What is the hit an Miss ratio? Answer: Ø Hit Ratio: h=(10-1)/10= 0.90 =90%. Ø Miss Ratio: 1 - 0.90= 0.10 =10% 46 COMPUTER PERFORMANCE WITH CACHE § Mean access time: the time a program or device takes to locate a single piece of information and make it available to the computer for processing. Ø Dynamic RAM (DRAM) chips for personal computers have access times of 50 to 150 nanoseconds (where 1 ns = 10-9 second). Ø Static RAM (SRAM) has access times as low as 10 nanoseconds. § Ideally, the access time of memory should be fast enough to keep up with the CPU. § If not, the CPU will waste a certain number of clock cycles looking for the data in the memory, which will make it slower. 47 COMPUTER PERFORMANCE WITH CACHE Mean access time for a system with cache is given by: Word mean access time = & + (1 − ℎ) , ­ Where c is the cache access time. ­ m is the main memory access time. ­ h is the hit ratio. 48 EXAMPLE § Suppose that the processor has the following two memories. Ø Main memory has an access time of 0.1 µs; This is (m) Ø Cache Memory has an access time of 0.01 µs. This is (c) § Assuming that the CPU needs to access the same memory word 10 times within a very short time. Find Word mean access time? Answer: Word mean access time = ! + (1 − ℎ) ( ) The hit ratio h = !"#! !" = 0.9 Then the average time to access a word can be expressed as: ! + (1 − ℎ) ( ) *. *, µ- + (, − *. .*)( *. ,µ-) = *. *0 µ49 COMPUTER PERFORMANCE WITH CACHE The improvement in performance that results from using the cache can be obtained by: Time without cache Ø Performance Improvement = Time with cache 50 MEMORY TUTORIAL Dr. Abrar Wafa QUESTIONS Q1: In a computer with cache hit rate of 90% where the cache access time is 10ns and the memory access time is 100ns, the average access time is? Average access time = c +(1-h) . m= 10 + (1-0.9) x100= 10 + 0.1x100=20 ns Q2: Find the improvement in performance where time to access main memory without cache is 1150 ns and time to access with cache is 150 ns. Performance Improvement = Time without cache Time with cache = ##$% #$% = 7.66 12 52 QUESTIONS (CONTINUED) Review questions 1. Show the difference between Temporal and Spatial locality with example. 2. Explain the difference between uniform and split caches. 3. What is hit ratio, what is miss ratio. 4. Draw and explain the five level Memory Hierarchy. 53