Circle the right answer
Suppose we designed a direct-mapped cache for a 32-bit microprocessor called the Uccs machine, the direct-mapped cache has 16 blocks (i.e., block 0, block 1, ...block 15). Each block has 32 bits. Uccs produces a 32-bitbyte address, so the bottom 2-bits are always 00 and are not used by the cache.
(1). How many bits are there in the tag field for each entry in this cache.
(a) 4 bits, (b) 16 bits, (c) 26 bits, (d) 28 bits, (e) none of the above
2 bits: byte offset; 4 bits: block selection, i.e., cache index
tag bits = 32 -2 -4 = 26 bits
answer: (C)
(2) We use the low-order address bits as the cache index because
(a) they are the first to arrive from the CPU.
(b) they ensure consecutive locations will be on the same virtual pages.
(c) we want nearby locations to occupy the same cache locations.
(d) we want nearby locations to occupy different cache locations.
(e) none of the above.
answer: (D)
(3) If we want to determine if the cache holds the data at address 0x3201C, which cache entry would we examine
(a) all of the cache entries (b) entry 6 (i.e., block 6) (c) entry 12
(d) entries 6 or 12 (e) none of the above
0x3201C = 0000 0000 0000 0011 0010 0000 0001 1100
cache index = 0111 - examine cache entry 7
answer: (E)
(4) What is the 32-bit byte address of the memory data currently cached in entry 3? Assume that high-order bits unspecified by hex constants are zero.
(a) 0x0l08 (b) 0xl080 (c) 0xl083 (d) 0x420C (e) none of the above
the last 6 bits of the address should be 001100, i.e., the last 4 bits = 1100 = C in hex
answer: (D)
The following questions ask you to evaluate alternative cache designs for the Uccs machine. Each of the cache under consideration has a total capacity of 8 words with one word stored in each cache block. Each word has 4 bytes. The cache designs under consideration are:
DM: a direct-mapped cache;
S2: a 2-way set-associative cache with a LRU replacement policy
FA: a fully-associative cache with a LRU replacement policy
(5) Which cache has the lowest hardware cost?
(a) DM (b) S2 (c) FA (d) they all have the same cost
answer: (A)
The following addresses are produced by the Uccs machine. Keep in mind that Uccs produces byte addresses; addresses of consecutive words in memory differ by 4.
(6) Which caches have the best hit rate for the sequence 0, 16,4,36, then repeat this
sequence.
(a) DM (b) S2 (c) FA (d) DM & S2 (e) S2 & FA
answer (E)
DM: 8 blocks, one word per block; 3 bits for index, 2 bits byte offset
Address (32 bits) / index / Cache Tag (27 bits) / Cache data / Hit/Miss0...00000000000000000000 / 000 / 0...000000000000000000 / M(0) / m
0...00000000000000010000 / 100 / 0...000000000000000000 / M(16) / m
0...00000000000000000100 / 001 / 0...000000000000000000 / M(4) / m
0...00000000000000100100 / 001 / 0...000000000000000001 / M(36) / m
0...00000000000000000000 / 000 / 0...000000000000000000 / M(0) / hit
0...00000000000000010000 / 100 / 0...000000000000000000 / M(16) / hit
0...00000000000000000100 / 001 / 0...000000000000000000 / M(4) / m
0...00000000000000100100 / 001 / 0...000000000000000001 / M(36) / m
S2: two way set associative, 4 sets, each way has one block; 2 bits for set index, Tag has 28 bits
Address / set / Way0 TAG(28bits) / Way0 data / Way1 Tag(28bits) / Way1 data / H/M0 / 00 / 0..00000000000 / M(0) / --- / --- / M
16 / 00 / 0..00000000000 / M(0) / 0..00000001 / M(16) / M
4 / 01 / 0..00000000000 / M(4) / --- / ---- / M
36 / 01 / 0..00000000000 / M(4) / 0..00000010 / M(36) / M
0 / H
16 / H
4 / H
36 / H
FA8 blocks available
Address (32 bits) / Cache Tag (30 bits) / Cache Data / Hit/Miss0...00000000000000000000 / 0...000000000000000000 / M(0) / m
0...00000000000000010000 / 0...000000000000000100 / M(16) / m
0...00000000000000000100 / 0...000000000000000001 / M(4) / m
0...00000000000000100100 / 0...000000000000001001 / M(36) / m
0...00000000000000000000 / 0...000000000000000000 / M(0) / hit
0...00000000000000010000 / 0...000000000000000100 / M(16) / hit
0...00000000000000000100 / 0...000000000000000001 / M(4) / hit
0...00000000000000100100 / 0...000000000000001001 / M(36) / hit
(7) Which caches have the best hit rate for the sequence 0, 4, 8, 12, 32, 36, 40, 44, 16, then repeat this sequence.
(a) DM (b) S2 (c) FA (d) DM & S2 (e) S2 & FA
answer: (B)
DM: 3 bits for cache index; 2 bits byte offset, tag has 27 bits
Address (32 bits) / index / Cache Tag (27 bits) / Cache data / Hit/Miss0...00000000000000000000 / 000 / 0...000000000000000000 / M(0) / m
0...00000000000000000100 / 001 / 0...000000000000000000 / M(4) / m
0...00000000000000001000 / 010 / 0...000000000000000000 / M(8) / m
0...00000000000000001100 / 011 / 0...000000000000000001 / M(12) / m
0...00000000000000100000 / 000 / 0...000000000000000001 / M(32) / m
0...00000000000000100100 / 001 / 0...000000000000000001 / M(36) / m
0...00000000000000101000 / 010 / 0...000000000000000001 / M(40) / m
0...00000000000000101100 / 011 / 0...000000000000000001 / M(44) / m
0...00000000000000010000 / 100 / 0...000000000000000000 / M(16) / m
now repeat the sequence
048123236404416
mmmmmmmmHIT
S2: two way set associative, 4 sets, each way has one block; 2 bits for set index, Tag has 28 bits
Address / set / Way0 TAG(28bits) / Way0 data / Way1 Tag(28bits) / Way1 data / H/M0 / 00 / 0..00000000000 / M(0) / --- / --- / M
4 / 01 / 0..00000000000 / M(4) / --- / --- / M
8 / 10 / 0..00000000000 / M(8) / --- / ---- / M
12 / 11 / 0..00000000000 / M(12) / --- / --- / M
32 / 00 / 0..00000000000 / M(0) / 0..00000000010 / M(32) / M
36 / 01 / 0..00000000000 / M(4) / 0..00000000010 / M(36) / M
40 / 10 / 0..00000000000 / M(8) / 0..00000000010 / M(40) / M
44 / 11 / 0..00000000000 / M(12) / 0..00000000010 / M(44) / M
16 / 00 / 0..00000000001 / M(16) / 0..00000000010 / M(32) / M
now repeat the sequence
048123236404416
mhhhmhhhm
FA:8 blocks available, no index bits needed
Address (32 bits) / Cache Tag (30 bits) / Cache Data / Hit/Miss0...00000000000000000000 / 0...000000000000000000 / M(0) / m
0...00000000000000000100 / 0...000000000000000001 / M(4) / m
0...00000000000000001000 / 0...000000000000000010 / M(8) / m
0...00000000000000001100 / 0...000000000000000011 / M(12) / m
0...00000000000000100000 / 0...000000000000001000 / M(32) / m
0...00000000000000100100 / 0...000000000000001001 / M(36) / m
0...00000000000000101000 / 0...000000000000001010 / M(40) / m
0...00000000000000101100 / 0...000000000000001011 / M(44) / m
0...00000000000000010000 / 0...000000000000000100 / M(16) / m
M(16) replaces M(0) since M(0) is the least recently used. M(0) is not in the cache
now the cache has M(4), M(8) M(12), M(32), M(36), M(40), M(44), M(16)
bring in M(0) to replace M(4), etc.
048123236404416
mmmmmmmmm
Consider a virtual memory system that uses a page table to translate virtual addresses into physical addresses. Each of the questions below asks you to consider what happens when one of the design parameters of the original system is changed.
(8) If the physical memory size (in bytes) is doubled, the number of bits in each entry of the page table
(a) stays the same (b) doubles (c) is reduced by half (d) increases by one
(e) decreases by one
answer: (D)
Double the physical memory size, then doubling the number of pages in main memory
i.e., need one more bits in selecting a page. the number of bits in each entry of the page table increases by 1 bit.
(9) If the physical memory size (in bytes) is doubled, the number of entries in the page table
(a)stays the same (b) doubles (c) is reduced by half (d) increases by one
(e) decreases by one
answer: (A)
The number of entries in the page table is determined by the virtual memory size.
Doubling the physical memory size will not change the number of entries in the page
table.
(10) If the virtual memory size (in bytes) is doubled, the number of bits in each entry of the page table
(a) stays the same (b) doubles (c) is reduced by half (d) increases by one
(e) decreases by one
answer: (A)
The number of bits in each entry of the page table is used to access a page in the physical
memory, independent of the virtual memory size.
Answer:
(1)C
(2)D
(3)E
(4)D
(5)A
(6)E
(7)B
(8)D
(9)A
(10)A