Test: Cache Memory- 1 - Computer Science Engineering (CSE) MCQ

Detailed Solution

 Download Solution PDF

Data:

Cache latency = T₁ = 1 ms

Main memory latency = T₂ = 10 ms

Average read latency = T_avg

Formula:

T_avg = H₁T₁ + (1 – H₂) (T₁ + T₂)

Since, cost of checking whether a block exists in the cache is negligible

T_avg = H₁T₁ + (1 – H₂) (T₂)

Calculation:

CASE 1: Cache size = 10 MB

Hit rate = T₁ = 20% = 0.2

Miss rate = T₂ = 80% = 0.8

 T_avg = H₁T₁ + (1 – H₂) (T₂)

= 0.2 × 1 + 0.8 × 10

= 8.2 ms > 6 ms

CASE 2: Cache size = 20 MB

Hit rate = T₁ = 40% = 0.4

Miss rate = T₂ = 60% = 0.6

T_avg = H₁T₁ + (1 – H₂) (T₂)

= 0.4 × 1 + 0.6 × 10

= 6.4 ms > 6 ms

CASE 3: Cache size = 30 MB

Hit rate = T₁ = 60% = 0.6

Miss rate = T₂ = 40% = 0.4

T_avg = H₁T₁ + (1 – H₂) (T₂)

= 0.6 × 1 + 0.4 × 10

= 4.6 ms < 6 ms

Hence, smallest cache size required to ensure an average read latency of less than 6 ms is 30 MB.

Average memory access time = Time spend for read + Time spend for write= Read time when cache hit + Read time when cache miss+Write time when cache hit + Write time when cache miss= 0.8 ⨯ 0.9 ⨯ 50 + 0.8 ⨯ 0.1 ⨯ (500+50) (assuming hierarchical read from memory and cache as only simultaneous write is mentioned in question)+ 0.2 ⨯ 0.9 ⨯ 500 + 0.2 ⨯ 0.1 ⨯ 500 (simultaneous write mentioned in question)= 36 + 44 + 90 + 10 = 180 ns

It is D.
Locality of reference is actually the frequent accessing of any storage location or some value. We can say in simple language that whatever things are used more frequently, they are stored in the locality of reference. So we have cache memory for the purpose.

Number of sets = 4K /(64*4) = 16. So, we need 4 bits to identify a set => SET = 4 bits.
64 words per block means WORD is 6 bits.
So, (D)

Here
and  On substituting the a,b for the first case we get

T = 95ns for a = 0.8 and b = 0.995. i.e., L1 = 8M and L2 = 64M.

T = 75ns for a = 0.9 and b = 0.99. i.e., L1 = 16M and L2 = 4M

b.

Size of the loop = n × b = k × m × b

Size of a set = k × b (k − way associative)

Here, size of the loop is smaller than size of a set as . Now, however be the mapping (whether all be mapped to the same set or not), we are guaranteed that the entire loop is in cache without any replacement.
For the first iteration:

No. of accesses = n × b

No. of misses = n  as each new block access is a miss and loop body has blocks each of size for a total size of .
For, the remaining 99 iterations:

No. of accesses = n × b

No. of misses = 0

So, total no. of accesses = 100nb
Total no. of hits = Total no. of accesses − Total no. of misses
= 100nb − n
So, hit ratio = 

The hit ratio is independent if l, so for l = 1 also we have hit ratio = 1- 

Number of cache blocks = 2c
Number of sets in cache = 2c/2 = c since each set has 2 blocks. Now, a block of main memory gets mapped to a set (associativity of 2 just means there are space for 2 memory blocks in a cache set), and we have 2cm blocks being mapped to c sets. So, in each set 2m different main memory blocks can come and block k of main memory will be mapped to k
mod c.

exploit the spatial locality of reference in a program as, if the next locality is addressed immediately, it will already be in the cache.
Consider the scenario similar to cooking, where when an ingredient is taken from cupboard, you also take the near by ingredients along with it- hoping that they will be needed in near future.

What is the number of sets in the cache?
Number of sets = Cache memory/(set associativity * cache block size)
= 256KB/(4*16 B)
= 4096
What is the size (in bits) of the tag field per cache block?
Memory address size = 32-bit
Number of bits required to identify a particular set = 12 (Number of sets = 4096)
Number of bits required to identify a paticular location in cache line = 4 (cache block size = 16)
size of tag field = 32 -12 -4 = 16-bit
What is the number and size of comparators required for tag matching?

We use 4-way set associate cache. So, we need 4 comparators each of size 16 bits

How many address bits are required to find the byte offset within a cache block?
Cache block size is 16 byte. so 4 bits are required to find the byte offset within a cache block.
What is the total amount of extra memory (in bytes) required for the tag bits?
size of tag = 16 bits
Number of sets = 4096
Set associativity = 4
Extramemory required to store the tag bits = 16 * 4096 * 4 bits = 2¹⁸ bytes

(a)
Data cache size = 8KB.
Block line size = 16B.
Since each array element occupies 4B, four consecutive array elements occupy a block line (elements are aligned as
starting address is 0)
Number of cache blocks = 8KB/16B = 512. Number of cache blocks needed for the array = 2048/4 = 512. So, all the array
elements has its own cache block and there is no collision.
We can also explain this with respect to array address. Starting address is 0x00000000 = 0b0000..0 (32 0's). Ending
address is 0x00001FFF = 0b0000..0111111111111 (4*2048 = 8192 location).
Here, the last 4 bits are used as OFFSET bits and the next 9 bits are used as SET bits. So, since the ending address is not
extending beyond these 9 bits, all cache accesses are to diff sets.
(b) If the last element is accessed first, its cache block is fetched. (which should contain the previous 3 elements of the
array also since each cache block hold 4 elements of array and 2048 is and exact multiple of 4). Thus, for every 4
accesses, we will have a cache miss => for 2048 accesses we will have 512 cache misses. (This would be same even if we
access array in forward order).

We have 4 blocks and 2 blocks in a set => there are 2 sets. So blocks will go to sets as follows:

since the lowest bit of block address is used for indexing into the set.
So, 8, 12 and 0 first miss in cache with 0 replacing 8 (there are two slots in each set due to 2-way set) and then 12 hits in
cache and 8 again misses. So totally 4 misses.

By default we consider hierarchical access - because that is the common implementation and simultaneous access cache has great practical difficulty. But here the question is a bit ambiguous -- it says to ignore search time within the cache - usually search is applicable for an associative cache but here no such information given. So, may be they are telling to
ignore the search time for L1 and just consider the time for L2 for an L1 miss and similarly just consider memory access time for L2 miss. This is nothing but simultaneous access.
Access time for hierarchical access

Access time for simultaneous access

Both options in choice - :O

When 45 comes, the cache contents are 4 3 25 8 19 6 16 35
LRU array (first element being least recently used) [4 3 19 6 25 8 16 35]
So, 45 replaces 4 45 3 25 8 19 6 16 35 [3 19 6 25 8 16 35 45]
Similarly 22 replaces 3 to give
45 22 25 8 19 6 16 35 [19 6 25 8 16 35 45 22]
8 hits in cache 45 22 25 8 19 6 16 35 [19 6 25 16 35 45 22 8]
3 replaces 19 45 22 25 8 3 6 16 35 [6 25 16 35 45 22 8 3]
16 and 25 hits in cache
45 22 25 8 3 6 16 35 [6 35 45 22 8 16 25 3]
Finally 7 replaces 6, which is in block 5.

So, answer is (B)

Number of blocks = cache size/block size = 32KB/32 = 1024 bytes. So, indexing requires 10 bits. Number of OFFSET bits required to access 32 bit block = 5. So, number of TAG bits = 32 - 10 - 5 = 17. So, answer is (A).

128 main memory blocks are mapped to 4 sets in cache. So, each set maps 32 blocks each. And in each set there is place for two blocks (2-way set).
Now, we have 4 sets meaning 2 index bits. Also, 32 blocks going to one set means 5 tag bits.
Now, these 7 bits identify a memory block and tag bits are placed before index bits. (otherwise adjacent memory references- spatial locality- will hamper cache performance)
So, based on the two index bits (lower 2 bits) blocks will be going to sets as follows:

Since, each set has only 2 places, 3 will be throw out as its the least recently used block. So, final content of cache will be
0 5 7 9 16 55
(C) choice.

Cache size is 32 KB and cache block size is 32 B. So,

So, number of index bits needed = 9 ( since 29 = 512). Number of offset bits = 5 (since 25 = 32 B is the block size and assuming byte addressing). So, number of tag bits = 32 - 9 - 5 = 18 (as memory address is of 32 bits).
So, time for comparing the data = Time to compare the data + Time to select the block in set = 0.6 + 18/10 ns = 2.4 ns.
(Two comparisons of tag bits need to be done for each block in a set, but they can be carried out in parallel and the succeeding one multiplexed as the output).

Code being C implies array layout is row-major.
When A[0][0] is fetched, 128 consecutive bytes are moved to cache. So, for the next 128/8 -1= 15 memory references
there won't be a cache miss. For the next iteration of i loop also the same thing happens as there is no temporal locality in the code. So, number of cache misses for P1
= (512/16) × 512
= 32 × 512
= 2¹⁴ = 16384

Hence, answer = option C

Number of Cache Lines

In 1 Cache Line

P₁ 

P₂

It is so because for
P₁ for every line there is a miss, and once a miss is processed we get 16 elements in memory. So another miss happens after 16 elements.
for
P₂ for every element there is a miss coz storage is row major order(by default) and we are accessing column wise.
Hence, answer = option B