(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.

  • $\begingroup$ This question is probably too broad. Do you have a specific issue you are not clear on? The purpose of exercises is to force you to work through a concrete problem yourself -- and that's an extremely good way to help you figure out where you are lost. So, try to use the exercise to identify aspects that you're not clear on, and then ask a more specific, narrowly focused question about the aspect that you don't understand. $\endgroup$
    – D.W.
    Nov 1, 2013 at 23:03
  • $\begingroup$ Can You suggest me a good online resource or a book where I can learn to apply my basic concepts to solve more complex problems like these from basic level? Please let me know, Because I am very eager to learn these things and have no guidance. I am reading william stallings book( but it has no solved problems, and on that basis I am not able to handle such questions)..... I am sure there must be good problem solving book/online resource.. please let me know if you know of some. $\endgroup$ Nov 8, 2013 at 3:21

1 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 2P (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.)

  • $\begingroup$ I fear the above may being "doing the work" too much rather than guiding the reader into how to solve such problems and understand the basic principles. $\endgroup$
    – user4577
    Nov 2, 2013 at 17:06
  • $\begingroup$ hello Paul, thanks for such a good explanation. But I still find it difficult to club the basic concepts that i have learned , to solve such problems.I understand things when i read a solution(like yours).Can you suggest a good online resource or a book where I can sharpen my skills by solving more similar questions starting from the basic level and developing my abiltity to solve more complex questions. I have no professor or guide with me (just doing self study). I want to increase my knowledge on memory concepts like these: RAM, Virtual addres, physical address, Paging etc and solve probs. $\endgroup$ Nov 8, 2013 at 3:16
  • $\begingroup$ @neerajdorle Sorry, I do not know of any good source for a large number of problems. I thought that exams/homework from computer architecture classes at universities might have some, but these classes seem to concentrate on other areas. Most computer architecture books only have a chapter or two on the memory system, so these are probably not great sources for such problems. You can, of course, generate "new" problems by changing numbers, but that brings limited insight. $\endgroup$
    – user4577
    Nov 8, 2013 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.