Designing a virtual memory with TLB

Question

I've been given the following problem and I'm not sure exactly how to approach it:

Consider a virtual memory system with the following properties:

· 35-bit virtual address

· 16 KB pages

· 32-bit physical address

Assume that this virtual memory system is implemented with an eight-way set associative TLB. The TLB has total of 256 TLB entries, with each TLB entry representing one virtual-to-physical page number translation.

A 64 KB data cache is a two-way set associative cache. The data cache’s block size is 128 Bytes.

Show the virtual to physical mapping with a figure drawn in a way similar to the figure below (but with all necessary changes required for the TLB and the data cache specified in this question).

Specify the width of all fields and signals coming in and out of (as well as the number of comparisons done by) the TLB and the data cache for each memory address.

I sort of have an idea on how to compute some parameters, but otherwise, I'm lost.

For instance, since the virtual address is 35-bits wide, I know that I have 2^35 possible virtual addresses.

Since I have 16KB pages (16*1KB = 2^4 * 2^10 = 2^14KB), I know that I must have (3^35)/(2^14) = 2^21 page table entries.

Finally, I know that my cache size is 64 * 1KB = 2^16 bytes of cache.

But I am lost after these steps. Any help would be appreciated.

Answer 1

The page offset is composed of the bits that address within a page and are not translated by the TLB. With 16 KiB pages, the page offset would be 14 bits.

With a 35-bit virtual address, this leaves 21 bits to index a set in the TLB and tag entries in that set. Since the TLB has 256 entries and each set has eight entries (8-way associative), there are 32 sets, requiring 5 bits to index a set. This leaves 16 bits for the tag.

The size of the physical page number is equal to the size of the physical address minus the size of the page offset: 32 - 14 = 18 bits.

Illustrating a TLB that is neither direct-mapped nor fully associative is more complex than the example fully associative TLB as such adds a dimension of set indexing. This can be handled by overlaying ways so that one way (indexed dimension) is fully visible. Here is an ASCII art version for a 4-way structure with 8 entries per way:

               +----------+----------+
             +----------+----------+ |  
           +----------+----------+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+ |
         |          |          |-+ |-+
         +----------+----------+ |-+
         |          |          |-+
         +----------+----------+

For 32 sets, one may wish to use ellipsis (...) to imply most of them. Similarly, ellipsis can be used to imply entries within a way (rather than having to draw hundreds of them).

For the cache, assuming a 4 byte access, the byte offset would be 2 bits. The block offset is used to index a 4-byte chunk within the cache block. With 128-byte cache blocks, indexing a specific byte would require 7 bits, so indexing a 4-byte chunk would only require 5 bits.

A 2-way associative 64 KiB will have 32 KiB in each way. With 128-byte cache blocks, this means that each way will have 256 blocks, so 8 bits of the physical address — beyond the block and byte offsets — are needed to index the specific set (cache block within each way). This is the cache index.

Given a 32-bit physical address, 8 bits of cache index, 5 bits of block offset, and 2 bits of byte offset, the tag will be 17 bits (32 - 8 - 5 - 2).