Memory organization in processor architecture

Lecture Notes

1. Module III: Processor Design flow: Capturing requirements, Instruction coding, Exploration of architecture organizations, hardware and software development. Extreme CISC and extreme RISC ,Very long instruction word (VLIW), Memory: Organization, Memory segmentation, Multithreading, Symmetric multiprocessing.

2. Memory Hierarchy

3. Cache Small amount of fast memory Sits between normal main memory and CPU May be located on CPU chip or module

4. Cache Memory Characteristics Location: Internal or External Capacity: word size Unit of transfer Access method: Sequential or Direct Performance: Access time, Memory Cycle time, Transfer Rate Physical type: Semiconductor or magnetic Physical characteristics: Erasable, volatile Organisation: Big Endian and Little Endian

5. Direct Mapping Each block of main memory maps to only one cache line i.e. if a block is in cache, it must be in one specific place Address is in two parts Least Significant w bits identify unique word Most Significant s bits specify one memory block The MSBs are split into a cache line field r and a tag of s-r (most significant)

6. Direct Mapping Address Structure Tag s-r Line or Slot r Word w 8 14 2 24 bit address 2 bit word identifier (4 byte block) 22 bit block identifier 8 bit tag (=22-14) 14 bit slot or line No two blocks in the same line have the same Tag field Check contents of cache by finding line and checking Tag

7. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 1: Mapping: 0 modulo 4 = 0 Block 0 Block 1 Block 2 Block 3 Mem Block DM Hit/Miss

8. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 1: Mapping: 0 mod 4 = 0 Block 0 Mem[0] Block 1 Block 2 Block 3 Mem Block DM Hit/Miss miss Set 0 is empty: write Mem[0]

9. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 2: Mapping: 8 mod 4 = 0 Block 0 Mem[0] Block 1 Block 2 Block 3 Mem Block DM Hit/Miss miss 8

10. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 2: Mapping: 8 mod 4 = 0 Block 0 Mem[8] Block 1 Block 2 Block 3 Mem Block DM Hit/Miss miss 8 miss Set 0 contains Mem[0]. Overwrite with Mem[8]

11. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 3: Mapping: 0 mod 4 = 0 Block 0 Mem[8] Block 1 Block 2 Block 3 Mem Block DM Hit/Miss miss 8 miss

12. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 3: Mapping: 0 mod 4 = 0 Block 0 Mem[0] Block 1 Block 2 Block 3 Mem Block DM Hit/Miss miss 8 miss miss Set 0 contains Mem[8]. Overwrite with Mem[0]

13. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 4: Mapping: 6 mod 4 = 2 Block 0 Mem[0] Block 1 Block 2 Block 3 Mem Block DM Hit/Miss miss 8 miss miss 6

14. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 4: Mapping: 6 mod 4 = 2 Block 0 Mem[0] Block 1 Block 2 Mem[6] Block 3 Mem Block DM Hit/Miss miss 8 miss miss 6 miss Set 2 empty. Write Mem[6]

15. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 5: Mapping: 8 mod 4 = 0 Block 0 Mem[0] Block 1 Block 2 Mem[6] Block 3 Mem Block DM Hit/Miss miss 8 miss miss 6 miss 8

16. Example: Accessing A Direct-Mapped Cache DM cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 DM Memory Access 5: Mapping: 8 mod 4 = 0 Block 0 Mem[8] Block 1 Block 2 Mem[6] Block 3 Mem Block DM Hit/Miss miss 8 miss miss 6 miss 8 miss Set 0 contains Mem[0]. Overwrite with Mem[8]

17. Direct Mapping pros & cons Simple Inexpensive Fixed location for given block If a program accesses 2 blocks that map to the same line repeatedly, cache misses are very high

18. Associative Mapping A main memory block can load into any line of cache Memory address is interpreted as tag and word Tag uniquely identifies block of memory Every line’s tag is examined for a match Cache searching gets expensive

19. Set-Associative Cache Basics Set 00 Block 0 Block 1 Set 01 Set 10 Set 11 n/m sets, m blocks (m-way): blocks are mapped from memory location to a specific set in cache Mapping: Mem Address % n/m . If n/m is a power of 2, log2(n/m) = #low-order bits of memory address = cache set index 0…0000 Mem block 0 0…0001 0…0010 0…0011 0…0100 0…0101 0…0110 0…0111 0…1000 Mem block 8 0…1001 0…1010 0…1011 0…1100 0…1101 0…1110 0…1111 … Example: 4 set, 2-way SA cache (ADD mod 4)

20. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 1: Mapping: 0 mod 2 = 0 Set 0 Set 1 Mem Block DM Hit/Miss SA Block Replacement Rule: replace least recently used block in set

21. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 1: Mapping: 0 mod 2 = 0 Set 0 Mem[0] Set 1 Mem Block DM Hit/Miss miss Set 0 is empty: write Mem[0] to Block 0

22. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 2: Mapping: 8 mod 2 = 0 Set 0 Mem[0] Set 1 Mem Block DM Hit/Miss miss 8

23. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 2: Mapping: 8 mod 2 = 0 Set 0 Mem[0] Mem[8] Set 1 Mem Block DM Hit/Miss miss 8 miss Set 0, Block 1 is LRU: write Mem[8]

24. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 3: Mapping: 0 mod 2 = 0 Set 0 Mem[0] Mem[8] Set 1 Mem Block DM Hit/Miss miss 8 miss

25. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 3: Mapping: 0 mod 2 = 0 Set 0 Mem[0] Mem[8] Set 1 Mem Block DM Hit/Miss miss 8 miss hit Set 0, Block 0 contains Mem[0]

26. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 4: Mapping: 6 mod 2 = 0 Set 0 Mem[0] Mem[8] Set 1 Mem Block DM Hit/Miss miss 8 miss hit 6

27. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 4: Mapping: 6 mod 2 = 0 Set 0 Mem[0] Mem[6] Set 1 Mem Block DM Hit/Miss miss 8 miss hit 6 miss Set 0, Block 1 is LRU: overwrite with Mem[6]

28. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 5: Mapping: 8 mod 2 = 0 Set 0 Mem[0] Mem[6] Set 1 Mem Block DM Hit/Miss miss 8 miss hit 6 miss 8

29. Example: Accessing A Set-Associative Cache 2-way Set-Associative cache contains 2 sets, 2 one-word blocks each. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 SA Memory Access 5: Mapping: 8 mod 2 = 0 Set 0 Mem[8] Mem[6] Set 1 Mem Block DM Hit/Miss miss 8 miss hit 6 miss 8 miss Set 0, Block 0 is LRU: overwrite with Mem[8]

30. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 1: S e t Mem Block DM Hit/Miss FA Block Replacement Rule: replace least recently used block in set

31. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 1: S e t 0 Mem [0] Mem Block DM Hit/Miss miss Set 0 is empty: write Mem[0] to Block 0

32. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 2: S e t 0 Mem [0] Mem Block DM Hit/Miss miss 8

33. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 2: S e t 0 Mem [0] Mem [8] Mem Block DM Hit/Miss miss 8 miss Blocks 1-3 are LRU: write Mem[8] to Block 1

34. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 3: S e t 0 Mem [0] Mem [8] Mem Block DM Hit/Miss miss 8 miss

35. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 3: S e t 0 Mem [0] Mem [8] Mem Block DM Hit/Miss miss 8 miss hit Block 0 contains Mem[0]

36. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 4: S e t 0 Mem [0] Mem [8] Mem Block DM Hit/Miss miss 8 miss hit 6

37. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 4: S e t 0 Mem [0] Mem [8] Mem [6] Mem Block DM Hit/Miss miss 8 miss hit 6 miss Blocks 2-3 are LRU : write Mem[6] to Block 2

38. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 5: S e t 0 Mem [0] Mem [8] Mem [6] Mem Block DM Hit/Miss miss 8 miss hit 6 miss 8

39. Example: Accessing A Fully-Associative Cache Fully-Associative cache contains 4 1-word blocks. Find the # Misses for each cache given this sequence of memory block accesses: 0, 8, 0, 6, 8 FA Memory Access 5: S e t 0 Mem [0] Mem [8] Mem [6] Mem Block DM Hit/Miss miss 8 miss hit 6 miss 8 hit Block 1 contains Mem[8]

40. Two-way Set-associative

41. Four-way Set Associative Cache

42. Virtual Memory Address

43. Replacement Policies Least Recently Used (LRU), Least Frequently Used (LFU) First-In-First-Out (FIFO).

44. M EMORY AND I / O INTERFACING

45. BASIC INTERFACING IN MICROPROCESSOR 45

46. BASIC INTERFACING IN MICROPROCESSOR 46 In memory interfacing, 8 bit data line, 16 bit address line , control signals are connected to corresponding lines of memory IC. In I/O device interfacing, 8 bit data line, only 8 bit address line , control signals are connected to corresponding lines of I/O devices.

47. D ATA T RANSFER USING I/O STRUCTURE

48. D ATA T RANSFER USING I/O STRUCTURE There are three major types of data transfer between the microprocessor and I/O device. Programmed I/O : In programmed I/O the data transfer is accomplished through an I/O port and controlled by software. Interrupt driven I/O : In interrupt driven I/O, the I/O device will interrupt the processor, and initiate data transfer. Direct memory access (DMA) : In DMA, the data transfer between memory and I/O can be performed by bypassing the microprocessor. 5

49. T HREE T ECHNIQUES FOR INPUT OF D ATA