Module-4.pptxMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambare

Mihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambareMihir pitambare

1. Module 4 Memory System Organization and Architecture

2. Overview Memory systems hierarchy Main memory organization Types of Main memory-memory inter- leaving and its characteristics and performance- Cache memories: address mapping-line size- replacement and policies- coherence- Virtual memory systems- TLB- Reliability of memory systems- Error detecting and error correcting systems

3. Introduction Programs and the data that processor operate are held in the main memory of the computer during execution, and the data with high storage requirement is stored in the secondary memories.

4. Characteristics Of Memory Systems The key characteristics of memory systems are: Location : The computer memory is placed in three different locations, CPU, Internal and External Capacity : It is expressed using two terms: Word size and number of words. Unit of Transfer : It is the maximum number of bits that can be read or written into the memory at a time Access Method : Sequential access and Random access Performance : Of the memory system is determined using three parameters, Access time, Memory cycle time and Transfer rate. Physical Type : Two most common physical types used today are semiconductor memory and magnetic surface memory. Physical characteristics : Volatile/Nonvolatile and Erasable/ Nonerasable

5. Memory Hierarchy / Multilevel Memory

6. Memory Hierarchy / Multilevel Memory Memory unit is essential component of digital computer since it is needed for storing programs and data. Memory unit that communicates directly with CPU is called Main memory. Devices that provide backup storage is called auxiliary memory. Only programs and data currently needed by processor reside in the main memory. All other information is stored in auxiliary memory and transferred to main memory when needed. Click to add text

7. Main Memory It is the memory used to store programs and data during the computer operation. The principal technology is based on semiconductor integrated circuits. It consists of RAM and ROM chips. RAM chips are available in two form static and dynamic.

8. Main Memory ROM is uses random access method. It is used for storing programs that are permanent and the tables of constants that do not change. ROM store program called bootstrap loader whose function is to start the computer software when the power is turned on. When the power is turned on, the hardware of the computer sets the program counter to the first address of the bootstrap loader

9. ROM chip

10. Cache Memory A special very high-speed memory. Used to speed up and synchronizing with high-speed CPU. Costlier than main memory or disk memory but economical than CPU registers. Extremely fast memory type that acts as a buffer between RAM and the CPU. It holds frequently requested data and instructions so that they are immediately available to the CPU when needed. Used to reduce the average time to access data from the Main memory. Smaller and faster memory which stores copies of the data from frequently used main memory locations. Various different independent caches in a CPU, which store instructions and data.

11. Cache Memory

12. Terminology Locality: memory references to cluster Temporal locality: tendency of the time intervals between references to a given address to be small Spatial locality: tendency of the distances between consecutive memory references to be small Memory hierarchy : characteristic of computer design in which a series of storage technologies are used such that the access time is faster as the memory is closer to the processor and the capacity is larger as the memory is further from the processor

13. Terminology Cache: memory closest to the processor in a memory hierarchy Caching: any storage management technique exploiting locality Upper/lower level: memory closer/further from the processor Block: unit of memory transfer between two levels in a memory hierarchy. Also called a cache line

14. Cache Performance Cache hit: If the processor finds that the memory location Cache miss: If the processor  does not  find the memory location The performance of cache memory is frequently measured in terms of a quantity called  Hit ratio. Hit ratio = hit / (hit + miss)= Number of hits/total accesses Miss penalty : time to move a block from a lower level in the hierarchy and satisfy the processor’s request

15. Cache Access Time Effective access time is a standard effective average. effective-access-time = hit-rate * cache-access-time + miss-rate * lower-level-access-time Miss penalty  is defined as the difference between lower level access time and cache access time. effective-access-time = cache-access-time + miss-rate * miss-penalty

16. Lower-Level Traffic Lower-level-traffic = miss-rate * requested traffic

17. Cache Memory (Levels of memory)

18. Cache Memory (Levels of memory) Level 1 or Register : Data is stored and accepted that are immediately stored in CPU. Most commonly used registers are accumulator, Program counter, address register etc. Level 2 or Cache memory: Fastest memory which has faster access time where data is temporarily stored. Level 3 or Main Memory: M emory on which computer works currently. It is small in size and once power is off data no longer stays in this memory. Level 4 or Secondary Memory: E xternal memory which is not as fast as main memory but data stays permanently in this memory.

19. Cache Mapping Direct mapping, Associative mapping, and Set-Associative mapping

20. First we conceptually divide the memory into blocks. Cache is also divided into lines. Note that these are conceptual things and they are not divided in physically. Here is how we divide the main memory into blocks and the size of a block is equal to the size of the cache line. In memory smallest addressable unit is called as word. It can be several Bytes but for the sake of the simplicity, I’ll take it a word equals to one Byte. 1. Direct-Mapped cache 1 word = 1 byte (for this example) word https://medium.com/breaktheloop/direct-mapping-map-cache-and-main-memory-d5e4c1cbf73e

21. Direct-Mapped cache A particular block of main memory can be mapped to one particular cache line only. Block ‘j’ of main memory will map to line number (j mod number of cache lines) of the cache. There is no need of any replacement algorithm.

22. https://www.youtube.com/watch?v=eObN3u3eAnU&t=1s Let’s see the main memory. Let’s assume that Cache is 16 words in size and Main memory is 64 words in size. If a block contains the 4 words then number of blocks in the main memory can be calculated like following. Number of blocks in the main memory = 64/4 = 16blocks. That means we have 16 blocks in the main memory and each block has four words in it. This is shown in the following diagram.

23. Let’s see the cache memory. If a line contains the 4 words, then number of line in the cache can be calculated like following. Number of lines in the cache memory = 16/4 = 4 lines. That means we have 4 lines in the cache memory and each line has four words in it.

24. Cache Mapping: Direct mapping Maps each block of main memory into only one possible cache line. Block address/No Block/word offset

25. Consider a direct mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find the number of bits in tag and Tag directory size. Solution: Given:- Cache memory size = 16 KB Block size = Frame size = Line size = 256 bytes Main memory size = 128 KB  Consider that the memory is byte addressable   Number of Bits in Physical Address- Size of main memory= 128 KB = 2 17  bytes Thus, Number of bits in physical address = 17 bits

26. Consider a direct mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find the number of bits in tag and Tag directory size. Solution: Number of bits in physical address = 17 bits

27. Consider a direct mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find the number of bits in tag and Tag directory size. Number of Bits in Block Offset-  Block size = 256 bytes = 2 8  bytes Thus, Number of bits in block offset = 8 bits

28. Consider a direct mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find the number of bits in tag and Tag directory size. Number of Bits in Line Number- Total number of lines in cache = Cache size /Line size = 16 KB / 256 bytes = 2 14  bytes / 2 8  bytes = = 2 6  lines Thus, Number of bits in line number = 6 bits

29. Number of Bits in Tag-  = Number of bits in physical address – (Number of bits in line number + Number of bits in block offset) = 17 bits – (6 bits + 8 bits) = 17 bits – 14 bits = 3 bits Thus, Number of bits in tag = 3 bits

30. Tag Directory Size  = Number of tags x Tag size = Number of lines in cache x Number of bits in tag = 2 6  x 3 bits = 192 bits = 24 bytes Thus, size of tag directory = 24 bytes

31. Problem-02: Consider a direct mapped cache of size 512 KB with block size 1 KB. There are 7 bits in the tag. Find Size of main memory, Tag directory size Solution Given: Cache memory size = 512 KB Block size = Frame size = Line size = 1 KB Number of bits in tag = 7 bits Consider that the memory is byte addressable.

32. Problem-02: Consider a direct mapped cache of size 512 KB with block size 1 KB. There are 7 bits in the tag. Find Size of main memory, Tag directory size Number of Bits in Block Offset-  Block size = 1 KB = 2 10  bytes Thus, Number of bits in block offset = 10 bits Number of Bits in Line Number Cache size / Line size = 512 KB / 1 KB = 2 9  lines Number of bits in line number = 9 bits

33. Problem-02: Consider a direct mapped cache of size 512 KB with block size 1 KB. There are 7 bits in the tag. Find Size of main memory, Tag directory size Number of Bits in Block Offset-  Block size = 1 KB = 2 10  bytes Thus, Number of bits in block offset = 10 bits Number of Bits in Line Number Cache size / Line size = 512 KB / 1 KB = 2 9  lines Number of bits in line number = 9 bits

34. Number of bits in physical address = Number of bits in tag + Number of bits in line number + Number of bits in block offset = 7 bits + 9 bits + 10 bits = 26 bits Number of bits in physical address = 26 bits Size of Main Memory-  Number of bits in physical address = 26 bits Thus, Size of main memory = 2 26  bytes = 64 MB Tag Directory Size-  Tag directory size = Number of tags x Tag size = Number of lines in cache x Number of bits in tag = = 2 9  x 7 bits = 3584 bits = 448 bytes Thus, size of tag directory = 448 bytes

35. 3. Consider a direct mapped cache with block size 4 KB. The size of main memory is 16 GB and there are 10 bits in the tag. Find the Size of cache memory and Tag directory size. Block size = Frame size = Line size = 4 KB Size of main memory = 16 GB Number of bits in tag = 10 bits Number of Bits in Physical Address ? Number of Bits in Block Offset ? Number of Bits in Line Number ? Number of Lines in Cache ? Size of Cache Memory? Tag Directory Size?

36. 2. Fully Associative Mapping A block of main memory can be mapped to any freely available cache line. This makes fully associative mapping more flexible than direct mapping. A replacement algorithm is needed to replace a block if the cache is full. https://www.youtube.com/watch?v=sLCJJdz0WAg&t=5s

37. Consider a fully associative mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find the number of bits in tag, Tag directory size. Cache memory size = 16 KB Block size = Frame size = Line size = 256 bytes Main memory size = 128 KB Size of main memory= 128 KB = 2 17  bytes Number of bits in physical address = 17 bits

38. Number of Bits in Block Offset Block size = 256 bytes = 2 8  bytes Number of bits in block offset = 8 bits Number of Bits in Tag

39. Number of Lines in Cache Total number of lines in cache = Cache size/Line size = 16 KB / 256 bytes = 2 14  bytes / 2 8  bytes = 2 6  lines Tag Directory Size = Number of tags x Tag size = Number of lines in cache x Number of bits in tag = 2 6  x 9 bits = 576 bits = 72 bytes Size of tag directory = 72 bytes

40. Consider a fully associative mapped cache of size 512 KB with block size 1 KB. There are 17 bits in the tag. Find the size of main memory, Tag directory size Cache memory size = 512 KB Block size = Frame size = Line size = 1 KB Number of bits in tag = 17 bits

41. Consider a fully associative mapped cache of size 512 KB with block size 1 KB. There are 17 bits in the tag. Find the size of main memory, Tag directory size Cache memory size = 512 KB Block size = Frame size = Line size = 1 KB Number of bits in tag = 17 bits Number of Bits in Block Offset Block size = 1 KB = 2 10  bytes Thus, Number of bits in block offset = 10 bits

42. Number of Bits in Physical Address Number of bits in physical address = Number of bits in tag + Number of bits in block offset = 17 bits + 10 bits = 27 bits Size of Main Memory= Number of bits in physical address = 27 bits Size of main memory = 2 27  bytes = 128 MB

43. Number of Lines in Cache- Total number of lines in cache = Cache size / Line size = 512 KB / 1 KB = 512 lines = 2 9  lines Tag Directory Size- = Number of tags x Tag size = Number of lines in cache x Number of bits in tag = 2 9  x 17 bits = 8704 bits = 1088 bytes Thus, size of tag directory = 1088 bytes

44. 3. Set Associative Mapping https://www.youtube.com/watch?v=pFndaJARM4Q&t=322s

45. Set Associative Mapping Consider a 2-way set associative mapped cache of size 16 KB with block size 256 bytes. The size of main memory is 128 KB. Find Number of bits in tag and Tag directory size Given:- Set size = 2 Cache memory size = 16 KB Block size = Frame size = Line size = 256 bytes Main memory size = 128 KB

46. Number of Bits in Physical Address Size of main memory= 128 KB = 2 17  bytes Thus, Number of bits in physical address = 17 bits Number of Bits in Block Offset Block size = 256 bytes = 2 8  bytes Thus, Number of bits in block offset = 8 bits

47. Number of Lines in Cache-  Total number of lines in cache = Cache size / Line size = 16 KB / 256 bytes = 2 14  bytes / 2 8  bytes = 64 lines Thus, Number of lines in cache = 64 lines Number of Sets in Cache- Total number of sets in cache = Total number of lines in cache/Set size = 64 / 2 = 32 sets = 2 5  sets Thus, Number of bits in set number = 5 bits

48. Number of Bits in Tag- = Number of bits in physical address – (Number of bits in set number + Number of bits in block offset) = 17 bits – (5 bits + 8 bits) = 17 bits – 13 bits = 4 bits Thus, Number of bits in tag = 4 bits

49. Tag Directory Size- = Number of tags x Tag size = Number of lines in cache x Number of bits in tag = 64 x 4 bits = 256 bits = 32 bytes Thus, size of tag directory = 32 bytes

50. Consider a 8-way set associative mapped cache of size 512 KB with block size 1 KB. There are 7 bits in the tag. Find Size of main memory and Tag directory size.

51. 12 bit main memory, Cache and block size problems

52. Hit ratio calculations

53. Model questions Single and multi cycle data path and problems Equation implementation in 3,2,1,0 Addressing modes Qn on Instruction set Qn on addressing modes Hit ratio calculations Bits calculations for Cache mapping