Solved Assignment: Cache Memory, Address Mapping and Virtual Memory

This assignment provides solutions to problems related to cache memory, address mapping, and virtual memory. It includes calculations for determining the number of blocks in main memory, the format of memory addresses (tag, block, and offset fields) for direct-mapped, fully associative, and set-associative caches, and the mapping of memory addresses to cache blocks. Additionally, it covers page table calculations, TLB hit time, and effective access time. The solutions demonstrate how to calculate address bits based on memory size, page size, and the relationship between virtual and physical addresses, offering a comprehensive understanding of memory organization and management in computer architecture. Desklib provides more solved assignments for students.

Q1.
a. Number of blocks in main memory = 2 ^ 64 / 2 ^ 6 = 2 ^ 58 blocks
b. Byte Offset size bit = Log264 = 6 bits
Block Size Bits = Log22048 = 11 Bits
Tag Field Bits = 64 – 6 -11 = 47 Bits
c. 0x0000 0000 0001 63FA
Binary of LSB 5 hex digits is 0001 0110 0011 1111 1010
Block bits are = 101 1000 1111 = 0x58F block number
Q2.
a. Blocks of main memory = 2 ^ 24 / 2 ^ 6 = 2^ 18 blocks
b. Byte Offset = 6 bits; Tag bits = 24 – 6 = 18 bits
c. In a fully associative Cache the block can map to any of the available slots that may be empty
Q3.
a. Offset = 2 bits ; Set = Log (64 / 2) = Log32 = 5 bits ; Tag field = 21 – 5-2 = 14 bits
b. Offset = 2 bits ; Set = Log (64 / 4) = Log16 = 4 bits ; Tag field = 21 – 4 - 2 = 15 bits
Q4.
a. Pages in virtual memory = 2 ^ 20 / 2 ^ 8 = 2 ^ 12 pages
b. Pages in Main memory = 2 ^ 16 / 2 ^ 8 = 2 ^ 8 pages
c. Page table entries = Number of Pages in virtual memory = 2 ^ 12 entries.
Q5.
a. TLB hit time= TLB access time = 7 ns
Cache hit time = TLB hit rate * TLB access time +
TLB miss rate * (TLB access time + Cache hit time)
= .95 * 7ns + .05 * (7+15)= 7.75 ns
b) EAT for TLB hit = TLB hit rate * (TLB access time + Cache hit rate * cache access time + cache miss rate
* (cache + main memory access time) )
+ TLB miss rate * (TLB access time + main memory access time + cache hit rate * cache
access time + cache miss rate (cache + main memory access time))
= .95 *( 7 + (.97*15) + .03(15+30))+ .05*(7+30+(.97*15) + .03 ( 15 + 30))=24.4 ns
Q6.
a. Virtual Address bits = Log32M = 25 bits
b. Physical Address bits = Log 4M = 22 bits
c. Maximum page Table entries = 2 ^ 25 / 2 ^ 11 = 2 ^ 14 page entries
d. 0x37F is address on Virtual Page 0. It is in Page frame 1 of Physical memory
e. 0x1203 is on Page Frame 2 of physical memory. Address from Virtual Page 4 0x2203 will map
here.

Each of these questions involves calculation of address bits. The number of
address bits needed depends upon size of memory. Total number of locations
that we can address using n bits is equal to 2 ^ n locations.
For example with 5 bits I can address 2 ^ 5 = 32 locations. Using the same
principle we can deduce the bits required to address given number of locations.
Like 1024 locations will need 10 bits because 2 ^ 10 = 1024.
The formula is also given as
Log2Number of locations = required number of bits
Using these relationships between number of bits and
address locations. We can proceed with the questions.
Part a
One information given is virtual memory size of 32MB (=32 X 1MB). Using Log
based formula Log232M = 25 bits. This means Virtual memory needs 25 bits to
address all its locations.
Part B
Next information is physical memory of machine given as 4MB = 4096Bytes.
This means it requires Log24096 bits = 22 for addressing the memory.
2 ^ 22 = 4MB.
Other information :
The first information to look for is page size given as 2048Bytes.
This means each page takes Log22048 bits for address = 11 bits
because 2 ^ 11 =2048.
Part c
Now we have required number of bits for each address type. Page table holds
data about each page of Virtual memory. Total number of pages possible in
Virtual Memory is Total size / Page Size
That is 32MB/2048 = 2 ^ 25 / 2 ^ 11. Using mathematics, powers when divided
subtract if base values are same . This gives us page table entry count as

2^ (25-11) = 2 ^ 14 entries.
Part D
Total address range in Virtual memory is divided into pages having size of 2048
bytes. This means lower 11 address bits (Page size related address bit count) of
each address indicate position of byte with in page and higher 14 address bits
indicate the page number.
For given address 0x37F, written in 25 bit binary is
0 0000 0000 0000 0011 0111 1111
the lowers 11 bits are 011 0111 1111 This gives us address with in page.
Upper 14 bits give us page number 0 0000 0000 0000 0 that is 0.
Now in given question it is mentioned Page 0 of Virtual memory is mapped to
page 1 of Physical memory.
Part E
Physical memory also uses same page size so is divided into pages that are each
2048 bytes in size. Or 11 bits of address for byte with in page and upper 5 bits for
page number
Physical address 0x1203 in binary is
0001 0010 0000 0011
010 0000 0011 is location with in page 0x203
0001 0 is page number that is 2
On physical page 2 we have Virtual page 4.
So virtual address = page number 4 + location with in page
25 bit virtual address is then
14 bits of page (0x4) + 11 bits of byte location (0x203)
0 0000 0010 0010 0000 0011
So address 0x2203 in virtual memory will map on location 0x1203 in physical
memory