Cache and Main Memory

Introduction

A memory is similar to the human brain. It's where you keep your data and instructions. Technically, the storage space in a computer where data to be processed and instructions to be processed are stored is referred to as computer memory.

In this article, we will discuss some questions related to Computer memory(cache and main memory) which were previously asked in the gate exam.

Questions

Question 1

In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from.

1. (A) (j mod v) * k to (j mod v) * k + (k-1)
2. (B) (j mod v) to (j mod v) + (k-1)
3. (C) (j mod k) to (j mod k) + (v-1)
4. (D) (j mod k) * v to (j mod k) * v + (v-1)

Answer: A

Explanation: v = cache number of sets, As a result, main memory block j will be mapped to set (j mod v), which will be any of the cache lines from (j mod v) * k to (j mod v) * k + (k-1). (Associativity has no bearing on mapping; k-way associativity indicates that a block has k spaces, which reduces the likelihood of replacement.)

Question 2

A RAM chip has a capacity of 1024 words of 8 bits each (1K × 8). The number of 2 × 4 decoders with enabling line needed to construct a 16K × 16 RAM from 1K × 8 RAM is

1. 4
2. 5
3. 6
4. 7

Answer: B

Explanation:  RAM chip size = 1k ×8[1024 words of 8 bits each]

RAM to construct =16k ×16

Number of chips required = (16k x 16)/ ( 1k x 8)

                         = (16 x 2)

[16 chips vertically with 2 chips horizontally on each]

So we'll need a 4 x 16 decoder to pick one chip out of 16 vertical chips.

The decoder available is a 2 x 4 decoder.

To be constructed is 4 x 16 decoder

As a result, 4 + 1 = 5 decoders are needed.

Question 3

A computer has a 256 KByte, 4-way set associative, write back data cache with a block size of 32 Bytes. The processor sends 32-bit addresses to the cache controller. Each cache tag directory entry contains, in addition, to the address tag, 2 valid bits, 1 modified bit, and 1 replacement bit.

The number of bits in the tag field of an address is

1. 11
2. 14
3. 16
4. 27

Answer: C

Explanation: A set-associative scheme combines the benefits of both fully associative and direct-mapped caches. It's thought to be a good compromise between the complicated hardware required for fully associative caches (which necessitates parallel searches of all slots) and the simple direct-mapped scheme, which can result in address collisions (similar to collisions in a hash table). 

Number of blocks = Cache-Size/Block-Size 

= 256 KB / 32 Bytes 

= 2¹³ Number of Sets 

= 2¹³ / 4 = 2¹¹ Tag + Set offset + Byte offset 

= 32 Tag + 11 + 5 

= 32 Tag = 16
 

Question 4

Consider the information provided in the previous question. The cache tag directory has a size of

1. 160 Kbits
2. 136 Kbits
3. 40 Kbits
4. 32 Kbits

Answer: A

Explanation: 16 bit address

2 bit valid 

1 modified 

1 replace 

Total bits = 20 

20 × no. of blocks 

= 160 K bits.

Question 5

An 8KB direct-mapped write-back cache is organized into multiple 32-byte blocks. 32-bit addresses are generated by the processor. The tag information for each cache block is kept by the cache controller and consists of the following. 1 bit that is a valid 1 bit has been changed. The minimum number of bits is required to identify the memory block mapped in the cache. What is the total amount of memory required by the cache controller to store cache meta-data (tags)?

1. 4864 bits
2. 6144 bits
3. 6656 bits
4. 5376 bits

Answer: D

Explanation:  Cache size = 8 KB

   Block size = 32 bytes

   Number of cache lines = Cache size / Block size = (8 × 1024 bytes)/32 = 256

   total bits required to store meta-data of 1 line = 1 + 1 + 19 = 21 bits

   total memory required = 21 × 256 = 5376 bits
 

Question 6

How many 32K x 1 RAM chips are required to provide a 256K-byte memory capacity?

1. 8
2. 32
3. 64
4. 124

Answer: C

Explanation: 256 Kbytes, or 256 x 1024 x 8 bits, is required. 

RAM chips with a capacity of 32 Kbits (32 x 1024 bits) are available. 

(256 * 1024 * 8)/(32 * 1024) = 64

Question 7

Which of the following is guaranteed to be unaffected if the associativity of a processor cache is doubled while the capacity and block size remain unchanged?

1. Width of tag comparator
2. Width of set index decoder
3. Width of way selection multiplexor
4. Width of processor to main memory data bus

Answer: D

Explanation: When associativity is doubled while capacity and block size remains constant, the number of sets is cut in half. As a result, the width of the set index decoder can undoubtedly be reduced - (B) is false. Because we need to double the number of ways to choose from, the width of the way-selection multiplexer must be increased- (C) is false. The number of possible cache block entries that a set maps to grows as the number of sets decreases. As a result, we'll need more tag bits to find the correct entry. As a result, (A) is also false. The correct answer is (D) because the main memory data bus has nothing to do with cache associativity. This can be answered without considering the other options.

Question 8

A CPU has a cache with a 64-byte block size. The main memory is divided into k banks, each of which is c bytes wide. With wrap-around, consecutive cbyte chunks are mapped on consecutive banks. All k banks can be accessed simultaneously, but two simultaneous accesses to the same bank must be serialised. Depending on the amount of data obtained by accessing all k banks in parallel, a cache block access may require multiple iterations of parallel bank accesses. Each iteration necessitates the simultaneous decoding of bank numbers, which takes time. k/2 ns k/2 ns k/2 ns One bank access takes 80 nanoseconds. If c = 2 and k = 24, the latency of retrieving a cache block from main memory starting at address zero is:

1. 92 ns
2. 104 ns
3. 172 ns
4. 184 ns

Answer: D

Explanation: Cache block size is 64 bytes. K=24 number of main memory banks Each bank's size C=2 bytes, i.e. each memory bank is 2 bytes long, and there are 24 of them. So, we can get 2*24 = 48 bytes in one iteration, and 64 bytes requires two iterations. As a result, the time required for parallel access is 

T=decoding time + latency time. 

T = (K/2)+latency = 12+80 = 92 ns 

However, C=2 for accesses =2*92=184ns (because we must select the banks in each iteration and the bank decoding time (k/2) is independent of the number of banks we will access).

Question 9

Consider a 4-way set associative cache with 128 lines and a 64-word line length. A 20-bit address of a word in main memory is generated by the CPU. The TAG, LINE, and WORD fields have the following bit counts:

1. 9,6,5
2. 7, 7, 6
3. 7, 5, 8
4. 9, 5, 6

Answer: D

Explanation:  The number of sets in this case is 128/4 = 32. (Since the set is associative, we'll call it that.)

We have a total of 64 words, so we will need 6 bits to identify each one.

As a result, the word offset is 6 bits and the line offset is 5 bits.

TAG = 20 - (5 + 6) = 9 bits

As a result, it should be 9,5,6.

Question 10

A cache line is made up of 64 bytes. The main memory has a latency of 32 nanoseconds and a bandwidth of 1 gigabyte per second. The time it takes to retrieve the entire cache line from main memory is.

1. 32 ns
2. 64 ns
3. 96 ns
4. 128 ns

Answer: C

Explanation: For a 1 GBps bandwidth, loading 109 bytes on line takes 1 second, so 64 bytes will take 64 * 1 /109 = 64 ns.

Because the main memory latency is 32, the total time to place a cache line is 64+32 = 96 ns.

You can also read about the memory hierarchy.