CS 473 HW6 Solution


Why Not to Allow Unaligned Accesses

Considering only the virtual memory, and assuming no hits in the TLB, how many memory accesses does it take to write four bytes starting at virtual address 0x123fffff on an Intel machine using only small (4K) pages?

Solution :
Since the page size is 4K, address 0x123fffff points to the last cell in page starting at 0x123ff000. Writing four bytes starting at 0x123fffff will involve writing into two pages, i.e., the first byte to page starting at 0x123ff000 and the next three bytes to page starting at 0x12400000. Therefore the following memory accesses need to be performed twice to achieve this intended write:
  1. Directory look-up
  2. Page table look-up
  3. Write to physical memory


Cache, VM, TLB Practice

Following this question will be the contents of the PDBR, some of memory, some of cache, and the small page data TLB for an Intel Pentium Pro. All the numbers are in hexadecimal. 

The L1 data cache on this machine was an 8KB, 4-way set-associative cache with a 32 byte line size.

Assume a program running in User mode attempts to write to each of the following virtual addresses. In each case, what happens? You may get page faults at either the directory entry or page table entry level, cache hits, cache misses, TLB hits, TLB misses.... However, you should never have reason to attempt a lookup in one of the tables and simply not find a table entry.

  1. 6141fac4
  2. 5eef358c
  3. 4ff2dfbc
  4. 6cc8e224
  5. 2153b858
  6. 4bf6af30
  7. 52b8525c
  8. 7559989c

Solution :

Important Notes:
   TLB tag:
        Since the TLB has 2^3=8 sets and we need 12 bits to specify the address 
of a page table, every tag in TLB consists of 32-(3+12) = 17 bits.
   Cache tag:
        a). Since the line size (the size of data in each block) is 32 bytes, so the 
byte offset in a virtual address is 5 bits.
b). Since the cache is 4-way associative, so the total data within one set
is 4*32=2^7 bytes.
c). Since the cache size is 8KB, so the total number of sets
is 8KB / 2^7 = 2^13 / 2^7 = 2^6 and the set index takes 6 bits.
d). Therefore the higher 32-6-5=32-11=21 bits of a virtual address
is used as a tag to look up the cache.
e). The number of associativity does not directly take bits in the virtual
address. Given the cache size, more associativity, less set numbers.
Thus the number of associativity is indirectly reflected in virtual
address through the set index bits.





1. 6141fac4

Virtual address
                   6    1    4    1    f                  a    c    4
binary format
                 0110 0001 0100 0001 1111                1010 1100 0100
TLB look-up
tag:        0110 0001 0100 0001 1 Index:  111(binary)
            0 1100 0010 1000 0011         111(binary)
            0   c    2    8    3           7 (hex)
TLB miss
break down
page table #:1  8  5
page #: 0 1 f
offset: ac4


VM steps

1
3
5
2
4
6

directory entry:
27060000 + 185<<2 =
27060614
can not continue
until the directory and
page table are updated

page table info:
  mem[27060614]=02397006
  decode:
page table addr: 02397000
11-0 bits: 0000 0000 0110
user accessible
writable

not present in directory









2. 5eef358c

Virtual address
                   5    e    e    f    3                    5    8    c
binary format
                 0101 1110 1110 1111 0011                 0101 1000 1100
TLB look-up
tag:        0101 1110 1110 1111 0 Index:  011 (binary)
            0 1011 1101 1101 1110         011 (binary)
            0   b    d    d    e           3  (hex)
TLB miss

break down
page table #: 1  7  b
page #: 2  f 3
offset: 58c
   

VM  steps

1
3
5
2
4
6

directory entry:
27060000 + 17b<< =
270605ec
page table entry:
3edd1000+2f3<<2 =
3edd1bcc
can not continue
until the page fault
is resolved
page table info:
mem[270605ec]=3edd1007
decode:
page table addr: 3edd1000
11-0 bits: 0000 0000 0111
user accessible
writable
present in directory

page info:
mem[3edd1bcc]=17cb1006
decode:
page addr: 17cb1000
11-0 bits: 0000 0000 0110
user accessible
writable

not present in page table







3. 4ff2dfbc

Virtual address
                   4    f    f    2    d                    f    b    c
binary format
                 0100 1111 1111 0010 1101                 1111 1011 1100
TLB look-up
tag:        0100 1111 1111 0010 1 Index:  101 (binary)
            0 1001 1111 1110 0101         101 (binary)
            0   9    f    e    5            5 (hex)
TLB miss
break down
page table #: 1 3  f
page #: 3 2 d
offset: fbc
   

 VM steps

1
3
5
2
4
6

directory entry:
27060000 + 13f<<2  =
270604fc
No way to continue. Protection failure.

page table info:
mem[270604fc]=083ae005
decode:
page table addr: 083ae000
11-0 bits: 0000 0000 0101
user accessible
not writable in directory
present








4. 6cc8e224

Virtual address
                   6    c    c    8    e                    2    2    4
binary format
                 0110 1100 1100 1000 1110                 0010 0010 0100
TLB look-up
tag:        0110 1100 1100 1000 1 Index:  110 (binary)
            0 1101 1001 1001 0001         110 (binary)
            0   d    9    9    1           6 (hex)
TLB hit: entry=3a951003
break down
page table #: 1 b  3
page #: 0 8  e
offset: 224
   

VM  steps

1
3
5
2
4
6



physical addr:
   3a951000 + 224 =
   3a951224
page table info:
3a951003
decode:
page table addr: 3a951000
11-0 bits: 0000 0000 0011
not user accessible
writable

present in directory

cache look-up:
  3    a    9    5    1    2    2    4  
0011 1010 1001 0101 0001 0010 0010 0100
set index: 010 001
01 0001
1 1 (hex)
tag to match in cache:
0011 1010 1001 0101 0001 0
0 0111 0101 0010 1010 0010
0 7 5 2 a 2 (hex)

cache hit







5. 2153b858

Virtual address
                   2    1    5    3    b                    8    5    8
binary format
                 0010 0001 0101 0011 1011                 1000 0101 1000
TLB look-up
tag:        0010 0001 0101 0011 1 Index:  011 (binary)
            0 0100 0010 1010 0111         011 (binary)
            0   4    2    a    7           3  (hex)
TLB miss    
break down
page table #: 0 8  5
page #: 1 3 b
offset: 858
   

 VM steps

1
3
5
2
4
6

directory entry:
27060000 + 085<<2 =
27060214
page table entry:
45601000+13b<<2 =
456014ec
physical addr:
5bdd1000 + 858 =
5bdd1858
page table info:
mem[27060214]=45601007
decode:
page table addr: 45601000
11-0 bits: 0000 0000 0111
user accessible
writable
present

page info:
mem[456014ec]=5bdd1067
decode:
page addr: 5bdd1000
11-0 bits: 0000 0110 0111
dirty
has been accessed
user accessible
writable
present

cache look-up: 
  5    b    d    d    1    8    5    8  
0101 1011 1101 1101 0001 1000 0101 1000
set index: 000 010
00 0010
0 2 (hex)
tag to match in cache:
0101 1011 1101 1101 0001 1
0 1011 0111 1011 1010 0011
0 b 7 b a 3 (hex)

cache miss (valid = 0)





6. 4bf6af30

Virtual address
                   4    b    f    6    a                    f    3    0
binary format
                 0100 1011 1111 0110 1010                 1111 0011 0000
TLB look-up
tag:        0100 1011 1111 0110 1 Index:  010 (binary)
            0 1001 0111 1110 1101         010 (binary)
            0   9    7    e    d           2  (hex)
TLB hit:    entry=09258027    
break down
page table #: 1  2  f
page #: 3 6 a
offset: f30
   

 VM steps

1
3
5
2
4
6


 
physical addr:
09258000 + f30 =
09258f30
page table info:
09258027
decode:
page table addr: 09258000
11-0 bits: 0000 0010 0111
user accessible
writable
present

  cache look-up: 
  0    9    2    5    8    f    3    0  
0000 1001 0010 0101 1000 1111 0011 0000
set index: 111 001
11 1001
3 9 (hex)
tag to match in cache:
0000 1001 0010 0101 1000 1
0 0001 0010 0100 1011 0001
0 1 2 4 b 1 (hex)

cache miss (valid = 0)


7. 52b8525c


Virtual address
                   5    2    b    8    5                    2    5    c
binary format
                 0101 0010 1011 1000 0101                 0010 0101 1100
TLB look-up
tag:        0101 0010 1011 1000 0 Index: 101 (binary)
            0 1010 0101 0111 0000        101 (binary)
            0   a    5    7    0          5  (hex)
TLB hit: entry=4698e027
break down
page table #: 1  4  a
page #: 3 8 5
offset: 25c
   

 VM steps

1
3
5
2
4
6


 
physical addr:
4698e000 + 25c =
4698e25c
page table info:
6498e027
decode:
page table addr: 6498e000
11-0 bits: 0000 0010 0111
user accessible
writable
present

  cache look-up: 
  4    6    9    8    e    2    5    c  
0100 0110 1001 1000 1110 0010 0101 1100
set index: 010 010
01 0010
1 2 (hex)
tag to match in cache:
0100 0110 1001 1000 1110 0
0 1000 1101 0011 0001 1100
0 8 d 3 1 c (hex)

cache hit



8. 7559989c

Virtual address
                   7    5    5    9    9                    8    9    c
binary format
                 0111 0101 0101 1001 1001                 1000 1001 1100
TLB look-up
tag:        0111 0101 0101 1001 1 Index:  001 (binary)
            0 1110 1010 1011 0011         001 (binary)
            0   e    a    b    3           1  (hex)
TLB hit:    entry=7bd5c025
break down
page table #: 1  d  5
page #: 1 9 9
offset: 89c
   

 VM steps

1
3
5
2
4
6


No way to continue. Protection failure.
page table info:
07bd5c025
decode:
page table addr: 08ce6000
11-0 bits: 0000 0010 0101
user accessible
not writable
present