Answer to Question #188422 in Software Engineering for waleed

Question

Consider a computer with the following characteristics: total of 256Mbyte of main memory; block size of 8 bytes; and cache size of 128 Kbytes.

i. Design a direct-mapping address structure.

ii. Design an associative-mapping address structure.

iii. Design a two-way set-associative-mapping address structure.

iv. For the main memory addresses of F0010ABH, F012356H, and 00CABBEH, give the corresponding tag, cache line address, and word offsets for a direct-mapped cache.

v. For the main memory addresses of F0010ABH, F012356H, and 00CABBEH, give the corresponding tag and offset values for a fully-associative cache.

vi. For the main memory addresses of F0010ABH, F012356H, and 00CABBEH, give the corresponding tag, cache set, and word offset values for a two-way set-associative cache.

Answer 1

Given:

• Main memory size = 256 MB = 2⁸ x 2²⁰ Bytes = 2²⁸ Bytes
• Cache Block Size = 8 Bytes = 2³ Bytes
• Cache Size = 128 KB = 2⁷ x 2¹⁰ Bytes = 2¹⁷ Bytes

Solution:

1. Direct mapping address structure:

In direct mapped cache, a block in main memory can map to a single cache block. Thus, in direct mapping the physical address is divided as follows:

Physical Address Bits = Bits for Tag + Bits for Cache Line Number + Bits for Block offset

Here, Physical address bits = 28 bits(obtained from main memory size)

Bits for block offset = 3

To calculate bits for cache line number, we need total number of cache lines which is obtained as:

Number of cache lines = (Cache Size) / (Cache Line Size) NOTE: Cache blocks are also called Cache lines

Number of cache lines = (2¹⁷ Bytes) / (2³ Bytes) = 2¹⁴ lines

Therefore, bits for cache line number = 14 bits

Thus, from above equation,

28 = Bits for tag + 14 + 3

Bits for tag = 28 - 17 = 11

Direct mapping address structure:

Physical Address(28 bits)

2. Fully Associative Mapping Address Structure:

In fully associative mapping, any block of main memory is mapped to any cache block. Thus, in fully associative mapping physical address is divided as follows:

Physical Address Bits = Bits for Tag + Bits for Block offset

Here, physical address bits = 28,

bits for block offset = 3

Thus, from above equation,

28 = Bits for Tag + 3

Bits for Tag = 25

Fully Associative mapping address structure:

Physical Address(28 bits)

3. Two way Set Associative Mapping Address Structure:

In set associative mapping, the cache lines are grouped together in sets. A main memory block is direct mapped to a particular set, but within the set it can map to any cache line. In this case, we have 2 cache lines in each set since it is 2-way Set associative mapping. So, you can say that Set associative mapping is a combination of Direct and Associative Mapping.

Thus, in set associative mapping physical address is divided as follows:

Physical Address Bits = Bits for Tag + Bits for Set Number + Bits for Block offset

Here, physical address bits = 28,

bits for block offset = 3

To calculate bits for set number, we need total number of sets which can be found as:

Number of sets = (Number of cache lines) / (Number of cache lines per set)

Number of sets = ( 2¹⁴ lines ) / (2 lines/set) = 2¹³ lines

Therefore, bits for set number = 13 bits

Thus, from above equation,

28 = Bits for Tag + 13 + 3

Bits for Tag = 28 - 16 = 12

2 Way Set Associative mapping address structure:

Physical Address(28 bits)

4. i) Main memory address given = (F0010AB)₁₆ = (1111 0000 0000 0001 0000 1010 1011)₂

Physical Address(28 bits)

ii) Main memory address given = (F012356)₁₆ = (1111 0000 0001 0010 0011 0101 0110)₂

Physical Address(28 bits)

iii) Main memory address given = (00CABBE)₁₆ = (0000 0000 1100 1010 1011 1011 1110)₂

Physical Address(28 bits)

5. i) Main memory address given = (F0010AB)₁₆ = (1111 0000 0000 0001 0000 1010 1011)₂

Physical Address(28 bits)

ii) Main memory address given = (F012356)₁₆ = (1111 0000 0001 0010 0011 0101 0110)₂

Physical Address(28 bits)

iii) Main memory address given = (00CABBE)₁₆ = (0000 0000 1100 1010 1011 1011 1110)₂

Physical Address(28 bits)

6. i) Main memory address given = (F0010AB)₁₆ = (1111 0000 0000 0001 0000 1010 1011)₂

Physical Address(28 bits)

ii) Main memory address given = (F012356)₁₆ = (1111 0000 0001 0010 0011 0101 0110)₂

Physical Address(28 bits)

iii) Main memory address given = (00CABBE)₁₆ = (0000 0000 1100 1010 1011 1011 1110)₂

Physical Address(28 bits)