Fully associative mapping lets any block sit in any line, and that one freedom is where marks go missing: the argument register gets mixed up with the mask register, the block offset gets counted as an index, and a memory block number gets read as a fixed cache line. Attempt each of the eleven questions below before you look at its answer. Ten take a single correct option and Q8 takes more than one, so check MCQ, MSQ or NAT? GATE Question Types Explained if that distinction is new. Seven of the eleven come from a named past paper, printed beside the question number. If the three mapping schemes themselves are still shaky, start with Cache Memory Mapping and Hit Ratio: Solved Examples.
1. Content-addressed lookup: what associative memory changes
RAM starts with a location such as 0x3A. Content-addressable memory starts with a search word such as 10110010. The stored data is itself the key, so the hardware compares instead of decoding, and the address bus stops being the way in. For the wider syllabus this topic sits inside, see GATE CS Exam Preparation.
Q1 (Beltron Programmer 2025, Shift 3)
Which of the following is a key benefit of associative memory using an argument register?
(a)
Lower cost per bit(b)
Larger capacity than RAM(c)
Fast content-based data retrieval(d)
Better for arithmetic processing
Answer: (c). The argument register supplies the search word that every stored word is compared against at once. That parallel compare is what buys fast content-based retrieval; it does nothing for cost per bit, for capacity, or for arithmetic throughput. Practise Q1 in the associative mapping module.
Q2 (HPSC 2021)
Find out the reference to the associative memory.
(a)
The data address is generated by the CPU(b)
The data address of the data is supplied by the users(c)
The data itself is used as an address and there is no need for an address(d)
The data are accessed sequentially
Answer: (c). The content pattern is itself the key, so the search never begins from an address supplied by the CPU or by the user. Read it as shorthand: match lines and selection circuitry still report where the match sits. Practise Q2 in the associative mapping module.
Q3 (ISRO 2011)
The search concept used in associative memory is
(a)
Parallel search(b)
Sequential search(c)
Binary search(d)
Selection search
Answer: (a). Every stored word, or every resident tag, is compared in the same cycle. Sequential and binary search both examine candidates one after another, which is precisely the cost associative memory exists to remove. Practise Q3 in the associative mapping module.
2. Argument register and key register: search word versus mask
Argument register A holds the search pattern; key or mask register K selects participating positions. For A = 10101100 and K = 11100000, compare only the leftmost 101.
Q4 (Beltron Programmer 2025, Shift 3)
In an associative memory system, what is the purpose of the Argument Register?
(a)
To hold the data that is read from memory(b)
To store the memory address for access(c)
To count the number of matches in memory(d)
To store the key used for matching in associative search
Answer: (d). The argument register carries the comparison word, the pattern being searched for. It is not an address register, not a data buffer, and not a match counter. Practise Q4 in the associative mapping module.
Q5 (Beltron Programmer 2025, Shift 3)
In associative memory, the function of the Key Register is to __________.
(a)
store the operand used in arithmetic operations(b)
act as a temporary buffer for read/write operations(c)
mask specific bits during a match operation(d)
hold the memory address for data retrieval
Answer: (c). Here K_i = 1 compares position i, while K_i = 0 masks it. With the values above, any stored word beginning with 101 matches, whatever its remaining five bits hold. Practise Q5 in the associative mapping module.
Q6 (UGC NET 2019, Paper 2)
Registers A and K hold the bit configuration A = 10101100 and K = 11100000. Only the three leftmost bits of A are compared with memory words, because K has 1s in those positions. Because of this organisation, the memory is uniquely suited to parallel searches by data association. This type of memory is known as:
(a)
RAM(b)
ROM(c)
content addressable memory(d)
secondary memory
Answer: (c). The mask selects three positions for parallel comparison. This defines content-addressable memory; RAM and ROM are ordinarily location-addressed.
3. Comparator count and tag-directory growth
For a 16 KiB cache, 16,384 / 64 = 256 lines, while 16,384 / 32 = 512 lines. Halving block size doubles tag-directory entries.
Q7
Consider the following statements:
S1: When the cache block size decreases, tag directory size increases.
S2: A fully associative cache needs more comparators to match tag bits than a direct mapped cache.
Select the correct option.
(a)
S1 is true(b)
S2 is true(c)
both are true(d)
none of them true
Answer: (c). The directory grows from 256 to 512 entries. Fully associative lookup compares all 256 resident tags in the first case; direct mapping compares one selected line.
Q8
Which of the following statements is/are true in the context of associative mapped cache memory?
(a)
Fully associative cache needs more number of comparators to match tag bits compared to direct and set associative map(b)
Hardware architecture of direct mapped cache requires OR gate, but Fully associative doesn’t require any OR gate.(c)
Fully Associative and Set-Associative mapping both require OR Gates.(d)
k-way Set associative mapping (k>1) we require only 1 comparator.
Answer: (a) and (c). Fully associative hardware compares all resident tags and combines hit signals. Set-associative hardware combines its k results; 4-way means four selected-set comparisons, not one.
4. Fully associative tag and index numericals
Use address bits = tag + index + block offset. Fully associative placement makes index = 0, but byte selection still needs the offset.
Q9
If the main memory is of 8K bytes and the cache memory is of 2K words. It uses associative mapping. Then each word of cache memory shall be
(a)
11 bits(b)
21 bits(c)
16 bits(d)
20 bits
Answer: (b). 8K bytes = 8192 = 2^13, so a full main-memory address is 13 bits, and each cache word holds one 8-bit byte of data. Every entry therefore stores 13 + 8 = 21 bits, because fully associative placement leaves the hardware no index field to find the entry by.
Q10 (GATE CS 2019)
A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
(a)
24 bits and 0 bits(b)
28 bits and 4 bits(c)
24 bits and 4 bits(d)
28 bits and 0 bits
Answer: (d). A 16-byte block needs 4 offset bits, and fully associative placement needs 0 index bits, so 32 - 4 - 0 = 28 bits are left for the tag. The cache does hold 16 kB / 16 B = 1024 lines, but a line is chosen by comparison, never by an index field. Work through the rest of the associative mapping PYQ set.
5. Row-major address calculation: memory block is not cache index
Row-major storage puts A[i][j] of a 1024-column array at element number i x 1024 + j. Multiply by the element size for a byte offset, then divide by the block size for the memory block number. Stop there: in a fully associative cache that block number tells you nothing about which physical line will hold it.
Q11
A computer system is designed with a 64 KB fully associative cache having a block size of 256 bytes. The main memory contains a two-dimensional array A[1024][1024], where each element occupies 4 bytes. During program execution, the following code segment is executed:
for (i = 0; i < 1024; i++) {for (j = 0; j < 1024; j++) {p = p + A[i][j];}}The cache is initially empty. The array A is stored in row-major order, following the C convention, so elements of the same row occupy contiguous locations. Only references to array A count as cache accesses, and each access is one 4-byte element. The cache uses Least Recently Used (LRU) replacement.
Determine which cache block the element A[4][257] will be loaded into.
(a)
Block 64(b)
Block 128(c)
Block 256(d)
None of these
Answer: (d). The linear index is 4 x 1024 + 257 = 4353, giving byte offset 4353 x 4 = 17,412. Therefore floor(17,412 / 256) = 68, with offset 17,412 - 68 x 256 = 4, so no listed number matches. The cache has 64 KiB / 256 B = 256 lines, but block 68 can occupy any line. LRU only chooses a replacement victim.
6. The traps behind these 11 associative mapping questions
Keep four distinctions visible:
Trap | Correct model |
|---|---|
Register roles |
|
Address fields | Fully associative means |
Block versus line | Memory block 68 may occupy any physical cache line. |
Hardware trade-off | Fewer conflict misses require more parallel comparison hardware. |
Q10 has 1024 lines but zero index bits. Q11 lands on block 68 and still names no line. Q7 moves the directory from 256 to 512 entries. Sort your own misses by which of those three confusions caused them, which is the habit Why PYQs Beat Buying Another Question Bank argues for.
7. Score the set and choose the next drill
Misses on Q1 to Q6 point to a weak content-search or register model. Misses on Q7 and Q8 point to comparator and hit-combine hardware. Misses on Q9 to Q11 mean tag, offset, and row-major arithmetic need another pass.
The practice bank holds 18 associative mapping questions in all, so seven are left once you finish this set. Redraw Q10 from memory and recompute Q11 without looking at the options. Write A = search, K = mask, index = 0, and tag = address - offset out from memory, then retry your misses after a day. GATE Guidance by Sanchit Sir carries the same COA sequence in full.
