Description
1. [Memory Hierarchy]
The following code snippet is written in C, where elements within the same row are
stored contiguously. Assume each word is a 64-bit integer.
for (i=0; i<10; i++)
for (j=0; j<1000; j++)
A[i][j] = B[i][0] + A[j][i];
a) How many 64-bit integers can be stored in a 16-byte cache block?
b) Which variable references exhibit temporal locality?
c) Which variable references exhibit spatial locality?
2. [Memory Hierarchy]
The following is a list of 64-bit memory address references, given as word addresses:
0x03, 0xB4, 0x2B, 0x02, 0xBF, 0x58, 0xBE, 0x0E, 0xB5, 0x2C, 0xBA, 0xFD
a) For each of the references, provide the binary word address, the tag, and the
index, for a direct-mapped cache with 16 one-word blocks. Also list for each
reference whether it is a hit or a miss, assuming that the cache is initially empty.
b) For each of the references, provide the binary word address, the tag, the index,
and the offset, for a direct-mapped cache with two-word blocks and a total size of
eight blocks. Also list for each reference whether it is a hit or a miss, assuming
that the cache is initially empty.
c) Which of the following eight-word direct-mapped cache designs provides the best
performance for the above reference? Explain.
C1: 1-word blocks
C2: 2-word blocks
C3: 4-word blocks
3. [Memory Hierarchy]
In a direct-mapped cache and 64-bit addresses, the following bits of the address are
utilized for cache access: Tag – bits 63-10, Index – bits 9-5, Offset – bits 4-0. Assume
byte-addressing, and you may also assume that words are 8-bytes.
a) What is the cache block size, in words?
b) How many blocks does the cache have?
c) What is the ratio between total bits required for such a cache and the data storage
bits?
d) Starting from an empty cache, the following byte-addressed cache references are
recorded:
0x00, 0x04, 0x10, 0x84, 0xE8, 0xA0, 0x400, 0x1E, 0x8C, 0xC1C, 0xB4, 0x884
EC605 Computer Engineering Fundamentals, Fall 2021
For each reference, list its tag, index, and offset, whether it is a hit or a miss, and
which bytes were replaced (if any).
e) What is the hit ratio of the above reference pattern?
f) For the above reference pattern, list the final state of the cache, with each valid
entry represented as a record of <index, tag, data>. For example, <0, 3, Mem[0xCC0]-Mem[0xC1F]>
4. [Memory Hierarchy]
Cache access time is proportional to capacity. Assume that main memory accesses
take 70ns and that 36% of all instructions access data cache/memory. The following
table shows data for L1 caches attached to each of two processors, P1 and P2.
L1 Size L1 Miss Rate L1 Hit Time
P1 2KB 8.0% 0.66ns
P2 4KB 6.0% 0.90ns
a) Assuming that the L1 hit time determines the cycle times for P1 and P2, what are
their respective clock rates?
b) What is the Average Memory Access Time for P1 and P2 for instructions only
(not data), in cycles?
c) Assuming a base CPI of 1.0 without any memory stalls, what is the total CPI for
P1 and P2? Which processor is faster? (When we say a “base CPI of 1.0”, we
mean that instructions complete in one cycle, unless either the instruction access
or the data access causes a cache miss.)
5. [Memory Hierarchy]
The following is a list of 64-bit memory address references, given as word addresses:
0x03, 0xB4, 0x2B, 0x02, 0xBE, 0x58, 0xBF, 0x0E, 0x1F, 0xB5, 0xBF, 0xBA, 0x2E,
0xCE
a) Describe the organization of a 3-way set associative cache with two-word blocks
and a total size of 48 words. Include the width of the tag and data fields.
b) Trace the behavior of the cache, assuming a true LRU replacement policy. For
each reference, specify the binary word address, the tag, the index, the offset,
whether the reference is a hit or a miss, and which tags are in each way of the
cache after the reference has been handled.
c) Now assume a fully associative cache with one-word blocks and a total size of
eight blocks. Trace the behavior of the cache, assuming a true LRU replacement
policy. For each reference, specify the binary word address, the tag, the index, the
offset, whether the reference is a hit or a miss, and which tags are in the cache
after the reference has been handled.
6. [Virtual Memory]
A virtual memory system consists of a virtual address size of 32 bits, a page size of
8KB, and a page table entry size of 4 bytes. What is the maximum possible page table
EC605 Computer Engineering Fundamentals, Fall 2021
size for a system running five processes?
7. [Virtual Memory]
A virtual memory system consists of 4KB pages, a four-entry fully-associative TLB,
and true LRU replacement. If pages need to be brought in from disk, the page that is
one larger than the largest occupied physical page number is assigned.
Following is a stream of virtual byte addresses:
0x123D, 0x08B3, 0x365C, 0x871B, 0xBEE6, 0x3140, 0xC049
The TLB content is as follows:
Valid Tag Physical Page
Number
Time Since
Last Access
1 0xB 12 4
1 0x7 4 1
1 0x3 6 3
0 0x4 9 7
The page table content is as follows (assume all other entries are invalid):
Index Valid Physical Page
Number
0 1 5
1 0 4
2 0 7
3 1 6
4 1 9
5 1 11
6 0 9
7 1 4
8 0 2
9 0 5
A 1 3
B 1 12
For each of the above accesses, list whether the access is: a TLB hit or miss, a page
table hit or a page fault. Also list the final state of the TLB.
