1.
Introduction
2.
Questions
3.
3.1.
What is Gate Exam?
3.2.
Who is eligible for the GATE exam?
3.3.
Is GATE compulsory for Masters?
3.4.
Are there any restrictions or age limits to applying for the GATE Exams 2023?
3.5.
Is a 3rd-year B.A./B.Com./B.Sc. student eligible to appear for GATE 2021?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Cache and Main Memory

Apoorv Dixit
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## 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)

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

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

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

= 213 Number of Sets

= 213 / 4 = 211 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

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

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

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

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

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

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

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

#### What is Gate Exam?

Gate stands for Graduate Aptitude Test in Engineering which is conducted for admission into the Master's Program and Job in Public Sector Companies.

#### Who is eligible for the GATE exam?

A student who is currently studying in the 3rd or higher years of any undergraduate program.

#### Is GATE compulsory for Masters?

No.it's not at all compulsory. However, if you want to pursue a master's degree in India, GATE is the best option.

#### Are there any restrictions or age limits to applying for the GATE Exams 2023?

No, there are no restrictions on the number of times.

#### Is a 3rd-year B.A./B.Com./B.Sc. student eligible to appear for GATE 2021?

Yes, any undergraduate student currently in the 3rd year or higher years of any government-approved program in Engineering / Technology / Architecture / Arts / Commerce / Science is eligible to appear for GATE 2021.

## Conclusion

In this article, we have discussed many questions on Cache and Main Memory. These were all previous year's questions that appeared in the Gate paper.

We hope you learned something new. If you want to learn more, check out our articles on Introduction to GATEHow to prepare in the Last 10 days to score high in GATE?

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning, Ninja :)

Live masterclass