Understanding the basic concepts in memory organisation

Question

(Before actually proceeding to the question, I want to confess that this is a homework question, please do consider it and help me in improving my understanding a bit more.)

I have recently started learning computer organisation and architecture. I have gained fair understanding for how caches are organised, how mapping between cache and main memory takes place (direct , fully and set-associative mapping), what is a page table(what are pages, blocks etc.), i can that say I have basic knowledge of segmentation , paging, virtual address and physical addresses.( at the basic level ofcourse).

Well I have come across this question:

A computer has 46-bit virtual address ,32- bit physical address, and a three level page table organisation. The page table base-register stores the base address of the first level table(t1), which occupies exactly one page.Each entry of t1 stores the base address of the page of second level table t2. Each entry of t2 stores the base address of the page of the third level table t3. Each entry of t3 stores a page table entry (PTE). The PTE is 32 bit in size. The processor used in the computer has a 1MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 Bytes.

First of all I am facing difficulty in just imagining such type of a virtual computer. can any one help me by giving a simple steps on How to realize such a virtual computer on paper, or just how to understand what is given in the question. What is really asked? How would one represent a computer having a 46-bit virtual address and having three level page table?

What is virtually indexed and physically tagged cache?

After reading what is given above, I feel that I just know the terms but I am unable to relate them together to solve problems. I will be glad If someone tries to explain how my thought process should be understand and apply these concepts practically to solve such types of problems.

Some questions based on the above paragraph:

1. What is the size of a page in KB in this computer?

2. What is the minimum number of page colours needed to guarantee that no
   two synonyms map to different sets in the processor cache of this computer?

A good resource where such problems are actually taught to solve will a appreciated. Good articles and views are most welcome.

Answer 1

One can derive the page size from knowing that the page table has three levels, the virtual address space is 46 bits (assume byte addressing), and a PTE is 4 bytes. P bits (where P = log2(page_size)) of the virtual address are not involved in the translation (these provide the offset within the page), so the three levels must translate a 46-P bit address value.

Each node of the page table contains page_size/PTE_size entries, and so each node covers log2(page_size/PTE_size) bits, which is P-2 bits. The page size can then be derived since 46 = (P-2)*3 + P.

(In a simple hierarchical page table, the first level is a single page [in the given design providing 2^(P-2) entries]. Each valid entry points to a page-sized table at the second level. Likewise each valid entry in the second level points to a page-sized table in the third level. Each valid entry in the third level provides a page translation. If all the first and second level entries were valid, there would be 2^(P-2) * 2^(P-2) third level tables each with 2^(P-2) entries. Thus 2^(P-2)*3 entries would be available, each covering 2^P (page_size) bytes.)

With respect to page coloring, one must determine the number of bits that are not part of the page offset which are used for indexing the cache. The number of sets is equal to cache_size/block_size/associativity, so to index to a specific set requires log2(cache_size/block_size/associativity) bits. The offset within the block uses log2(block_size) bits. Using C= log2(cache_size), B= log2(block_size), and A=log2(associativity), C-B-A bits are used to index the set and C-B-A+B, i.e. C-A, bits are used to address the given byte.

Since only P bits are provided as part of the page offset, C-A-P bits use virtual address bits. In order to avoid the problem of two different virtual addresses with the same physical address mapping to different sets, the virtual addresses of any physical pages that are so shared can be colored, i.e., share the same value for the C-A-P virtual address bits. (This forces them to map to the same set. With tagging based on physical addresses, this is sufficient to avoid aliasing issues like a write to one virtual address not updating a cached entry at the same physical address but a different virtual address.)

Each index group is called a color, so to provide C-A-P virtual address bits requires 2^{(C-A-P) colors.}

(The above assumes an "ordinary" cache. Indexing not using simple modulo 2N, e.g., skewed associativity, would have different coloring requirements; but such complexities are typically ignored for problems like this.)