Browse Prior Art Database

"Fast Virtual Address Translation Using Hardware Hashing"

IP.com Disclosure Number: IPCOM000123995D
Original Publication Date: 1999-Sep-01
Included in the Prior Art Database: 2005-Apr-05
Document File: 8 page(s) / 257K

Publishing Venue

IBM

Related People

Neubauer, M: AUTHOR [+2]

Abstract

For implementing a 64-bit extension to an existing 31-bit architecture, a way to translate the 64-bit virtual addresses is necessary. Since backward compatibility to the existing 31-bit address structure is a strong criteria, only the newly added 33 bits should be subject to the new translation scheme. The low order 31 bits would have to be translated by an existing routine with only minor modifications to the translation table entry formats. &hc. tesssssst

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

"Fast Virtual Address Translation Using Hardware Hashing"

   For implementing a 64-bit extension to an existing 31-bit
architecture, a way to translate the 64-bit virtual addresses is
necessary.  Since backward compatibility to the existing 31-bit
address structure is a strong criteria, only the newly added 33 bits
should be subject to the new translation scheme.  The low order 31
bits would have to be translated by an existing routine with only
minor modifications to the translation table entry formats. &hc.
tesssssst

   First an overview of translation algorithms that were also
considered for the 64-bit architecture will be given, thereby
emphasizing the disadvantages of' these schemes.

   Address Translation Techniques

   Staged segmentation

   The virtual address is divided into several index
ranges.  Each index range is used as an offset into a translation
table.  The resulting table entry holds the origin of the table that
is indexed into by the next index range.  For a reasonable table
size, the 33 bits must be divided into three index ranges of 11 bits
each.  Larger ranges would result in tables larger than 8 KByte, an
allocation problem for current operating systems.  The division into
three index ranges adds three more memory accesses for every
translation.  Since analysis of actual systems showed that about 50%
of all such accesses cause a cache miss with subsequent linefetch
from slow main memory, this would take up too much CPU utilization
time.

   Pure segmentation

   This approach does not divide the virtual address into
ranges.  Instead only one table is used to map all 2 GB regions.
This reduces the number of additional translation table accesses to
one.  However, the table has a size of 2/33/ entries, which is not
acceptable.  Alternatively only some low order bits may be used to
index into the translation table.  The table entries would then hold
the higher order bits for a compare.  This of course is a. simple
form of hashing the 33 address bits.  There is a great disadvantage
in that synonym addresses cannot be held translatable simultaneously.

   Inverted page table

   A system-wide table is used to map all real memory
pages.  The virtual page number is used to obtain a hash value that
is used as an index into the page table.  The index designates a
single entry or a group of' entries.  These entries may contain a
pointer that allows chaining of entries within the page table.  The
page table size is again very large, since all real memory must be
mappable.  For example some architectures recommend that the number
of page table entries be at least four times the number of' real
pages.  For a real memory size of 256 MB the page table is 2MB.  For
a 32 GB system the page table size would then be 256 MB.  This
recommendation asserts that the hash function used produces many
collisions and therefore the table can be used efficiently only up to
a filling level of 25%.  The whole transla...