Question on hierarchical vs. inverted page tables / TLB

[alzamabar]

Hi,

How would you say that hierarchical page table organisation as opposed as inverted page table affects TLB efficiency? Is that because, on 64-bit address spaces, the number of PTEs is reduced, therefore the size of TLB is less?

[Brendan]

Hi,

How would you say that hierarchical page table organisation as opposed as inverted page table affects TLB efficiency? Is that because, on 64-bit address spaces, the number of PTEs is reduced, therefore the size of TLB is less?

Does the hierarchical page table necessarily need to be hierarchical, and can the inverted page tables also be hierarchical? Also, what do you mean by "efficiency" (latency, bandwidth or power consumption/heat)?


Cheers,

Brendan

[alzamabar]

Hi,

How would you say that hierarchical page table organisation as opposed as inverted page table affects TLB efficiency? Is that because, on 64-bit address spaces, the number of PTEs is reduced, therefore the size of TLB is less?

Does the hierarchical page table necessarily need to be hierarchical, and can the inverted page tables also be hierarchical? Also, what do you mean by "efficiency" (latency, bandwidth or power consumption/heat)?


Cheers,

Brendan

The hierarchical approach entails indexes of indexes. So for a typical 4G of address space, 32-bit address, byte addressing, and pages of 4k each, there would be 1048756 pages. If each of these pages were mapped to a 4-byte PTE, a 4M linear structure could be organised in 1024 pages. If finally we mapped each of these pages with 1024 PTEs of 4 bytes each we would have Level-1 and Level-2 hierarchical tables. Since the 1024 points to the 4k PTEs would occupy only 4k, usually OS would wire down the root table with each running process. So I think that to make sense a hierarchical table needs to be hierarchical.

However I'm studying that inverted page tables are better. They are mainly organised by a hashing function and there is a substantial difference between hierarchical and inverted pages. The former are indexed by virtual address, the latter by phisical address. Thus the latter grow with phisical memory instead of virtual address space. Obviously there is a trade-off with hashing functions: the same address may map to more than one physical address, in which case the duplicated entry is written to the bottom of the inverted page table (kinda of linked list structure). The trick here is to increase the size of the Hash ancor table to reduce the number of collisions, so I don't think that inverted pages could be hierarchical, according to what I'm studying. However, the probability of hitting an entry after the hash mapping is high (depending on the implementation) therefore only seldomly the PTE is not found (after visiting all linked list entries) and a page fault triggered.

As performance I mean latency.

M.

[Craze Frog]

They are mainly organised by a hashing function

Hash speed is grossly overestimated. Sure, it's constant, but most definetely not fast. To get any decent performance the hash function would have to be in the hardware and also accessible to software.

[alzamabar]

They are mainly organised by a hashing function

Hash speed is grossly overestimated. Sure, it's constant, but most definetely not fast. To get any decent performance the hash function would have to be in the hardware and also accessible to software.

I think that later OS hash directly the inverted page, thus saving on that part, but on the other hand they need more space, because both the virtual address and the physical address must be stored in the PTE.

The more I look at Operating Systems, the more I find that it's a question of trade-offs, between performance and flexibility.

M.