Cache Memory and Virtual Memory

Due: 11:00pm, Friday December 10, 2021

Problems

  1. (25 points) Complete the following table that has parameters for several different caches.

    m C B E S t s b
    32 1024 4 4
    32 1024 4 256
    32 1024 8 1
    32 1024 8 128
    32 1024 32 1
    32 1024 32 4

    Key:

    • m: number of physical bits
    • C: cache size
    • B: block size in bytes
    • E: associativity
    • S: number of cache sets
    • t: number of tag bits
    • s: number of index bits
    • b: number of block offset bits

  2. (25 points) Suppose we have a system with the following properties:

    • The memory is byte addressable.
    • The memory accesses are to 1-byte words (not 4-byte words.)
    • The addresses are 13 bits wide.
    • The cache is four-way set associative (E=4), with a 4-byte block size (B=4) and eight sets (S=8).

    Consider the following caches state. All addresses, tags, and values are given in hexadecimal format. The Index column contains the set index for each set of four lines. The Tag column contains the tag value for each line. The V column contains the valid bit for each line. The bytes 0-3 column contains the data for each line numbered left-to-right starting with byte 0 on the left.

    Index Tag V Bytes 0-3
    0 F0 1 ED 32 0A A2
    8A 1 BF 80 1D FC
    14 1 EF 09 86 2A
    BC 0 25 44 6F 1A
    1 BC 0 03 3E CD 38
    A0 0 16 7B ED 5A
    BC 1 8E 4C DF 18
    E4 1 FB B7 12 02
    2 BC 1 54 9E 1E FA
    B6 1 DC 81 B2 14
    00 0 B6 1F 7B 44
    74 0 10 F5 B8 2E
    3 BE 0 2F 7E 3D AB
    C0 1 27 95 A4 74
    C4 0 07 11 6B D8
    BC 0 C7 B7 AF C2
    4 7E 1 32 21 1C 2C
    8A 1 22 C2 DC 34
    BC 1 BA DD 37 D8
    DC 0 E7 A2 39 BA
    5 98 0 A9 76 2B EE
    54 0 BC 91 D5 92
    98 1 80 BA 9B F6
    BC 1 48 16 81 0A
    6 38 0 5D 4D F7 DA
    BC 1 69 C2 8C 74
    8A 1 A8 CE 7F DA
    38 1 FA 93 EB 48
    7 8A 1 04 2A 32 6A
    9E 0 B1 86 56 0E
    CC 1 96 30 47 F2
    BC 1 F8 1D 42 30

    1. What is the size (C) of this cache in bytes?

    2. For a 13-bit address, indicate which bits are the cache block offset (CO), cache set index (CI), and cache tag (CT). Note that bit 12 is the left-most bit and bit 0 is the right-most bit.

    3. Complete the following table for references to 1-byte words. Numeric values must be in hexadecimal. In the case of a cache miss use “-” for the “Cache byte returned”.

      Address Block offset (CO) Index (CI) Cache tag (CT) Cache hit? (Y/N) Cache byte returned
      0x071A
      0x13DE
      0x16C9

  3. (25 points) A given computer system has the following cache access times:

    • L1 cache: 3 processor cycles
    • L2 cache: 10 processor cycles
    • L3 cache: 30 processor cycles
    • Main memory: 120 processor cycles

    1. Program A has the following miss rates:

      • L1 cache: 4%
      • L2 cache: 30%
      • L3 cache: 50%
      • Main memory: 0% (assume it is always in main memory.)

      What are the hit rates for each cache level and what is the average memory access time for program A?

    2. Program B has the following hit rates:

      • L1 cache: 93%
      • L2 cache: 80%
      • L3 cache: 65%
      • Main memory: 100% (assume it is always in main memory.)

      What are the miss rates for each cache level and what is the average memory access time for program B?

    3. Oftentimes, the program with the lower L1 cache miss rate has the better (lower) average memory access time. Is that true in this case? If not, why?

    4. For program A, what speedup would be acheived if you were able to optimize the program to acheive an 85% hit rate in L2 cache?

    5. For program B, if the L1 cycle access time was increased from 3 cycles to 4 cycles, what minimum hit rate would be needed in the L1 cache to achieve the same average memory access time?

  4. (25 points) Consider a virtual memory system that has the following parameters:

    • Virtual addresses are 20 bits wide.
    • Physical addresses are 18 bits wide.
    • The page size is 1024 bytes.
    • The TLB is 2-way set associative with 16 total entries.

    The contents of the TLB and the first 32 entries of the page table are shown as follows. All numbers are in hexadecimal.

    TLB

    Index Tag PPN Valid Tag PPN Valid
    0 03 C3 1 01 71 0
    1 00 28 1 01 35 1
    2 02 68 1 3A F1 0
    3 03 12 1 02 30 1
    4 7F 05 0 01 A1 0
    5 00 53 1 03 4E 1
    6 1B 34 0 00 1F 1
    7 03 38 1 32 09 0

    Page Table

    VPN PPN Valid VPN PPN Valid
    000 71 1 010 60 0
    001 28 1 011 57 0
    002 93 1 012 68 1
    003 AB 0 013 30 1
    004 D6 0 014 0D 0
    005 53 1 015 2B 0
    006 1F 1 016 9F 0
    007 80 1 017 62 0
    008 02 0 018 C3 1
    009 35 1 019 04 0
    00A 41 0 01A F1 1
    00B 86 1 01B 12 1
    00C A1 1 01C 30 0
    00D D5 1 01D 4E 1
    00E 8E 0 01E 57 1
    00F D4 0 01F 38 1

    1. For a 20-bit virtual address, indicate which bits are the virtual page offset (VPO), virtual page number (VPN), TLB index (TLBI), and TLB tag (TLBT). Note that bit 19 is the left-most bit and bit 0 is the right-most bit.

    2. For a 18-bit physical address indicate which bits are the physical page offset (PPO) and physical page number (PPN).

    3. Complete the following table for address translation. Numeric values must be in hexadecimal. In the case of a cache miss use “-” for “PPN” and leave the physical address blank.

      Virtual Address VPN TLB Index TLB Tag TLB Hit? (Y/N) Page Fault? (Y/N) PPN Physical Address
      0x078E6
      0x04AA4

Turning in the Assignment

Submit a single file containing your answers to the problems to the appropriate folder on D2L. Note that your answers must be correctly numbered. A solution that does not satisfy this requirement will be marked as a zero.