JPH0628262A - Look-aside buffer and method for high-speed translation of virtual address for physical address - Google Patents

Abstract

PURPOSE: To increase the operation speed of the memory management device of a computer device adopting a virtual memory addressing. CONSTITUTION: The translation look-aside buffer 10 used for a virtual memory includes a device for storage of virtual addresses and a device for storage of physinal addresses related to respective virtual addresses and is provided with at least a look-up table of a first level and a look-up table of a second level where some physical addresses indicate pages where information requested by virtual addresses exist and other physical addresses indicate pages where physical addresses of information requested by virtual addresses exist.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a computer memory management device, and more particularly to a method and device for translating virtual addresses into physical addresses in a computer memory device utilizing virtual memory addressing. is there.

[0002]

BACKGROUND OF THE INVENTION Virtual memory devices are those that allow addressing of very large amounts of memory, as if all memory were the main memory of a computer device. Such devices allow it to do so, even if the actual main memory consists of a memory space that is much smaller than the addressable memory. For example, the main memory may consist of 1 megabyte of random access memory and a virtual memory addressing device may be used to address 64 megabytes of memory.

Virtual memory devices do this by providing a memory management device that translates virtual memory addresses into physical memory addresses. A particular physical address can be located in main memory or long-term storage. Given that the physical address of the information sought is in main memory, the information is accessed and utilized by the computer. Given that the physical address is in long-term storage, the information is (usually in blocks called pages)
Transferred to main memory and used there. This transfer is
Another information needs to be exchanged from main memory to long-term memory to make room for new information. If so, this is done under the control of the memory manager.

For the virtual memory device of a computer,
Computers can have very large addressable space, but this does not guarantee that the computer will operate quickly. It is not guaranteed to work quickly. Rapid operation is determined by how fast the part operates and how fast memory can be accessed. The speed of memory access depends on the speed of operation of the components, but to a greater extent on the process required to translate an address from a virtual address to a physical address and then retrieve information from memory. The basic virtual memory device constitutes the look-up table. This look-up table is stored in main memory. The virtual address provided to the memory management unit is compared to the values stored in those tables to determine the physical address to access. Often there are several levels of tables and the comparison takes a very long system clock time.

To overcome this delay, virtual memory devices often include cache memory that uses very fast components to store recently used data and instructions. The cache memories are usually connected so that the processors can quickly access them. Before any information goes to main memory, those caches are first examined by the processor. The theory of those caches is that the most recently used information is more likely to be needed again before other information is needed. This theory is valid and the hit rate of many devices using cache memory is over 90 percent.

However, their cache memories still have to be addressed in some way, such as directly with virtual addresses or via translated physical addresses. Addressing by virtual address poses a major problem including multiple copies of information.
Some of that information may be outdated and unusable.
Overcoming this problem is expensive. Therefore, cache addressing by physical address is preferred because of its economics. This aspect of addressing requires translating virtual addresses into physical addresses before the cache memory can be accessed, so devices that use those cache memories do not have to go through the entire page table lookup process, and We have developed a device for quickly providing a dynamic address.

A typical device of this kind is called a translation lookaside buffer (TLB). A translation lookaside buffer is essentially a buffer for caching recently used virtual addresses along with their associated physical addresses. Such address caches operate on the same principles as caches that hold data and instructions, and more recently used addresses tend to be used more than others. Given the virtual address held in the translation lookaside buffer, the translation lookaside buffer provides the physical address for that information. Given that physical address is in the associated cache, the information is immediately available to the processor without having to go through the time-consuming procedure of looking up the page lookup table in main memory.

If the processor sends a virtual address to the translation lookaside buffer, the address is not included in the translation lookaside buffer, and the memory manager must then look up the address using a look-up table in main memory. . To do this,
A typical memory management device relies on a register for the address of the base table, which stores the addresses that specify other levels of the table. The memory management unit retrieves this pointer in the base table and places it in another register. The memory manager uses this pointer to advance to the next level table. This operation continues until the physical address of the desired information is recovered. When the physical address is recovered, it is stored in the translation lookaside buffer along with the virtual address so that it is available immediately the next time it is needed. When the information is recovered, it is cached under the physical address. This saves a lot of time the next time the information is used. This is because a typical lookup in a page table can take 10-15 clock cycles for each level of search, while accessing information using translation lookaside buffers and caches was tedious. This is because it only requires one or two clock cycles.

One of the difficulties in such devices is that a page table lookup operation is required when the physical address is not in the translation lookaside buffer.
This is so even if most of the search process (getting a pointer) occurs many times before a particular search operation. The reason is that the registers used to store pointers to different levels of page tables are in a separate resource from the translation lookaside buffer and can typically store only one address pointer at a time. Is. Therefore, once the search is initiated, it is necessary to go through the whole process for each level of table that must be traversed. That is, the processor looks for the first pointer, stores it, uses that pointer to find the next pointer, then stores the next pointer, and then uses that pointer to find the address. If). In the next search process, all of these pointers will be overwritten. In conventional economical devices without a separate cache memory for storing address pointers, there is no way to short-circuit this time-consuming process.

In addition to always delegating problems from the translation lookaside buffer to the page table, many addresses that must be forwarded are not simply stored in the translation lookaside buffer. For example, in addition to data and instructions, processors often handle input / output information. This information is available to the processor,
It is typically handled by another addressing means, such as an input / output processor or direct memory access device.

Therefore, conventional ultra-high speed computer systems that use separate caches for data and instructions and have a direct memory access function act as a translation lookaside buffer for addressing in the cache, and in the main memory. Individual memory management resources are typically required to perform lookups in page tables and manage addressing of input / output information. In conventional devices, very large amounts of silicon were needed to quickly address data, instructions and input / output functions. Moreover, conventional devices cannot have the desired address translation speed in a sufficient number of situations.

[0012]

SUMMARY OF THE INVENTION It is therefore an object of the present invention to provide a computer system using virtual memory addressing by using an extended caching system, without the added cost typically associated with increasing cached data. It is to improve the operation speed of the memory management device.

Another object of the present invention is to provide a translation lookaside buffer which can handle translation of addresses for data, instructions and inputs / outputs in a device having a data cache and an instruction cache. .

[0014]

These and other objects of the invention are configured to store page table entries and page table pointers for data addresses, instruction addresses, and input / output addresses. This is realized by the translation lookaside buffer. By storing the page table entry and the page table pointer, the translation lookaside buffer is a very high percentage of all virtual addresses, even if the particular virtual address is not in the translation lookaside buffer and there is no complete lookup in the page table. Can be translated.

Certain portions of the detailed description that follows is presented in a symbolic representation of operations on data bits within a computer memory. These descriptions and representations are the means used by those in the data processing arts to most effectively convey the substance of their work to others. Operations are those requiring physical manipulations of physical quantities. Usually, those quantities take the form of electrical or magnetic signals that can be stored, moved, combined, compared and otherwise handled, but this is not necessary. It has been found that sometimes convenient to call these signals bits, values, elements, symbols, characters, terms, numbers, etc., primarily because of their common use. However, it should be remembered that those terms and similar terms represent appropriate physical things and are merely convenient labels.

Moreover, the handling performed is generally associated with the mental work performed by a human operator,
Often referred to by terms such as addition or comparison. In any of the operations described herein that form part of the present invention, such capabilities of a human operator are in most cases unnecessary or undesirable.
The operation is a machine operation. Machines useful for performing the operations of the present invention include general purpose digital computers and similar devices. In all cases, the differences between the method operations in operating a computer and the method of calculation itself should be remembered. The present invention processes electrical signals or other (mechanical, chemical, physical) signals to generate other desired physical signals,
And a method of operating a computer.

[0017]

1 is a block diagram of a translation lookaside buffer 10 made in accordance with the present invention.
Refer to. This translation lookaside buffer 10
It includes a portion for storing a plurality of virtual memory addresses to compare with the incoming virtual address. In the preferred embodiment of the present invention, portion 12 is configured to store 32 virtual addresses in an all-associative cache. This part 12 is
A storage device is also included in addition to the bit for storing the virtual address. In the preferred embodiment of the invention, they are 3 bits indicating the level at which the page table search is to be performed,
It includes 6 bits indicating context, bits indicating supervisor control, bits indicating that the page table pointer is stored in the translation lookaside buffer 10, and input / output bits.

Although not required by the present invention,
The preferred embodiment of the present invention utilizes a memory that is capable of addressing the content for virtual address bits and context tag bits, such that each comparison with a stored value is accomplished by simply supplying the address to portion 12. To do. Alternatively, an external comparator can be combined with the first portion 12 to compare the virtual address being sought with the bits stored in the first portion 12.

In any case, the required virtual address is provided on one of the three sets of input lines 14, 15, 16. The address provided on line 14 is provided by the input / output circuitry of the computer system. The address provided on line 15 is the instruction address provided by the integer processor of the computing device. The address provided on line 16 is the data address provided by the integer processor of the computing device. In each case, the maximum required 20-bit virtual address is
Is fed to section 12 for comparison with. A specific virtual address is supplied to the virtual tag section by the multiplexer 18 in response to the control signal designating the specific type being sought. For example, an instruction in an integer processor specifies the data or information sought as the instruction, and the input / output circuitry indicates that the sought information is for input and output purposes.

At the same time that the high order bits of the virtual address are provided to multiplexer 18, multiplexer 20
Provides the context tag that is compared with the value in the context tag bit position. The context tag is supplied from the context register 19. It is written by memory management software. For data address and instruction address (when not in supervisor mode),
The virtual address tag and the context tag must match the bits that are expected to be a hit in the translation lookaside buffer 10. A context tag is a group of bits that allows a device to choose between different page table groups used by different software programs. For any particular program running on the device, the context tag remains the same throughout the program. For the purposes of the present invention, context tags can be considered as additional address bits.

In general, if the virtual address bit matches the context bit (assuming some other bit matches in the preferred embodiment), the high order bits of the physical address are provided as output. Those upper bits of each physical address are stored in the portion 22 of the translation lookaside buffer 10 in the same row as the virtual address to be translated. The low order bits of the virtual address and the low order bits of the physical address are the same and indicate a byte address within any particular page. Therefore, the lower bits of the virtual address are stored in the translation lookaside buffer 10.
To provide the complete physical address, combined with the number of physical pages supplied by

All the above is a very refreshing approach. But in order to manufacture economical equipment,
The physical addresses stored in the translation lookaside buffer 10 of the present invention are three types of addresses. The stored values can be page table entries, input / output page table entries, page table pointers. A normal page table entry provides the physical address of an entry and the permissions for that entry (what is required to access the entry). The page table entry is the normal physical page address information provided by the conventional translation lookaside buffer. This page address can be used to access the memory address for information. This address is combined by the multiplexer 21 with the lower virtual address bits and placed in the physical address register 23, where the translation lookaside buffer 1
When a hit occurs at 0, the information is obtained from either of the two physically addressed caches (or from memory when a cache miss occurs).

On the other hand, the page table pointer is the base physical address of another page table. Thus, the page table pointer specified when combined with the virtual address index points to an address in another page table that can be searched. Since the page table pointer points to an address in main memory, it is a physical address (similar to a page table entry). However, it is not used to get the required information immediately, but it is used to get another physical address for another level of page translation. This other address may be another page table pointer or page table entry (physical page address). Given that it is a page table entry, the physical address is stored in the translation lookaside buffer for the initially sought virtual address and used immediately to obtain the sought information. On the other hand, if the address is a page table pointer, the physical address is stored in the translation lookaside buffer for the physical base address of the next page table, and the physical address is stored in the first portion 12 of the translation lookaside buffer 10. The value is used to access the translation lookaside buffer 10 to determine if it exists in the.

As can be seen from the above description, once these two types of physical address information have been obtained, those information must be handled in different ways. Therefore, they must be clearly distinguished in the translation lookaside buffer 10. To do this, the virtual addresses pointing to those two types of physical values in the first portion 12 of the translation lookaside buffer 10 must be properly pointed to and used in the computer system as follows. For example, the number of bits actually used to match the virtual address varies depending on the level of the page table pointed to by the page table pointer.

In a similar manner, the virtual address provided by the input / output circuitry provides information that must be treated differently than the other two aspects of the physical address. Like other virtual addresses, the virtual address used for input / output purposes must be properly designated and selected when used by a computing device.

Three field bits of the other field bits are used to match different parts of the provided virtual address bits. They specify the size of pages within a particular virtual memory device. As one of ordinary skill in the art will appreciate, the size of a page of memory determines the number of bits of the address needed to specify that page and the number of bits needed to specify a byte within a page. . Assuming there is only one very large page, all bits are used to specify the address within that page, and, in fact, the virtual address is the physical address. On the other hand, a smaller page requires fewer bits to specify the bytes within a page, but more bits to address the page from more available pages. Therefore, three field bits are used to indicate that the comparison must include a certain number of high order bits of the virtual address.

In the preferred embodiment of the present invention, those three level bits are the three of the page table entries.
Coded as 100, 110 or 111 to indicate one of the possible levels. When the page table entry value is stored in the translation lookaside buffer 10, those bits are always set to the appropriate level. In the preferred embodiment of the invention, virtual address bits 31:24 are used to address the largest page at level 100 and virtual address bits 31:18 are used to address the next larger page at level 110. Used to address the smallest page at level 111, virtual address bits 31:
12 is used.

This bit is used to indicate the validity of an entry, since the most significant bit is set to 1 for each of those level values only when the entry is made to the translation lookaside buffer 10. You can also consider. This eliminates the need for additional bits in each row of the translation lookaside buffer 12. Since the memory used in the preferred embodiment is a content addressable memory,
This is a big savings.

In addition to the level bits, it is used to indicate the supervisor rather than user control of the device. For the purposes of the present invention, the bit needs very little operation, except that the bit is forced to 1 to indicate that a translation of the data or instruction address is taking place. This allows the context part to be used as part of the address tag. For input / output addresses stored in the translation lookaside buffer, that bit remains zero.

In addition to the level and supervisor bits, the page table pointer (physical address rather than virtual address) is stored in a particular row of portion 12 of the translation lookaside buffer 10. This bit is set whenever the pointer is stored, facilitating use of the invention as described below. When the page table pointer is held in the translation lookaside buffer as indicated by the page table pointer (PTP) bit, the level bit will always be set to 111 for that entry. This allows the entire address field to be compared with the input for searching the page table pointer. This is required because the translation lookaside buffer tag in portion 12 is a physical address that uses all virtual tag address fields and all context tag fields. The control state machine indicates the current page table level.

When handling input / output addresses, one one-level table separate from the other page tables is included. The IBAR register 29 contains the base address. An input / output control register includes a range field that indicates the size of the input / output page table and indicates the number of low order bits of the virtual address needed to access the address in the input / output page table. Once the physical address is obtained, the physical address is generated by the input / output controller so that the address is immediately available when the particular virtual address is provided by the input / output controller. Are again placed in the translation lookaside buffer 10. That bit is used at that address to indicate the type of input / output bit.

To better understand the invention, the operation of the device in response to a virtual address will be described. Assuming that the computer has just been powered on, the general process to which the invention pertains is that the operating system resides in main memory, the supervisor part of the operating system sets up the page table,
Then, the memory control function is delegated to the memory management device. At this point, nothing is placed in the cache or translation lookaside buffer 10. When the first virtual address is provided to the translation lookaside buffer 10 for comparison, the appropriate bits of the virtual address are compared with the bits stored in the context tag field and virtual tag field in portion 12. . Initially, no address is stored there, so a cache miss is signaled.

In the case of a virtual address generated by the input / output memory manager, the miss causes the base address to be generated using the value stored in IBAR register 29. The address pointed to is the base address of one page table that is unique for input / output addressing. The input / output control register of the input / output memory management device includes a field indicating the page size of the input / output page table. From this size, the number of lower virtual address bits required to select the entry location is determined. The low order bits and the base address in register 29 are combined using multiplexer 21 and the physical address for the input / output virtual address is found in the input / output page table. This value and the virtual address that causes it are stored in the translation lookaside buffer 10 so that the physical address is immediately available when the virtual address is next instructed.

On the other hand, if the virtual address that caused the translation lookaside buffer to miss is the address of the instruction or data, this is the base page address stored in the CTPR register 25 and the context register (C
The base address is generated by the combination of the 6 lower bits stored in (XR) 19. This base address refers to the word in the lowest level table of the page table used for all addressing except input / output. For instructions and data, this base level table is allowed to hold only page table pointers, since the size of the page available at this level includes all virtual memory. Given that this level holds page table entries (ie, the physical addresses of the information sought), it maps directly from physical memory to virtual memory (each physical address is unique to only one unique virtual address). There is no reason to have virtual memory). In fact, apart from the invention, the mode bits are provided by software in the control register. This effectively bypasses the translation and allows the device to set virtual memory to equal physical memory.

At this point, the virtual address caused the main memory to retrieve the page table pointer. This pointer is the address of the next level page table. This page table pointer is stored in the translation lookaside buffer 10 in the physical address field of portion 22. Translation lookaside buffer 10 in part 12
In the same row of the base address (physical address) generated from the bits in CTPR register 25 and context register 19, and an indication in the PTP bit that the tag portion of the translation lookaside buffer contains the physical address, The set of level bits to 111 is stored to allow a full comparison of all three fields of the address in the part 12. In addition, the page table pointer is part 1 of the translation lookaside buffer 10.
When stored in 2, the supervisor bit is set, allowing the context part to be used as part of the physical address tag. Also, the same input /
When the output virtual address is compared to this entry, it uses a different page table with different input / output translations, so the I / 0 bit is cleared for this entry to avoid hits.

The base address, which is still held in the physical address register 23, is reapplied to the translation lookaside buffer 10 from which a hit occurs. This bit results in the pointer just stored in the physical address subfield 23. This address is then loaded into the physical address register 23. The contents of the physical address register 23 are compared with the translation lookaside buffer portion 12 and then a miss occurs. Upon detection of a miss, main memory is accessed with the contents of the physical address register 23 combined with the index field from the original virtual address, as indicated by the control state machine. This new address points to the level 2 page table. This can include either a page table entry (the actual physical address corresponding to the physical address being translated), or a page table pointer that contains the physical address pointer to the next level page table.

Assuming that the retrieved entry is a page table entry, the contents of address reading (physical address having protection information) are stored in the physical address portion 22 of the translation lookaside buffer 10. In the same row of the translation lookaside buffer 10 in the portion 12, 20 bits (bits [26:
12]), the current value of the context register, a level bit indicating the level at which the current page table entry is found, a supervisor bit set according to the state of the IU machine, and PTP and IO bits (they are Will be stored). The original translation is then retried, producing a hit when compared to the recently updated hit.

On the other hand, if the entry read from the main memory is the page table pointer, it is the physical address portion 2 of the translation lookaside buffer 10.
Stored in 2. In the same row of the translation lookaside buffer 10 in the portion 12, the PTP that the physical address of the pointer read from the physical address register 23 and the tag portion 12 of the translation lookaside buffer 10 contain the physical address. Includes an indication in the bit and the setting of the supervisor bit, which is the same as the previous loading of the page table pointer.

The contents of physical address register 23 are then compared with portion 12 of translation lookaside buffer 10 and a hit occurs. This hit causes a pointer just stored in the field of the physical address portion 22. At this point, main memory is accessed to read the current page table entry. This entry is processed like a previous page entry read, except that the level field of the page table entry reflects the current page table entry. In the preferred embodiment of the present invention, three page table levels are supported. Therefore, only the third level page table contains page table entries. Therefore, 3 of the main memory
As a result of the second access, the page table entry is read. The page table entry is stored in the translation lookaside buffer 10 as described above. Following storage of the page table entry in the translation lookaside buffer 10, the original virtual address is always retried, resulting in a translated address for the cache requesting it.

Once the translated address of the sought information is recovered, it is used to help determine if the sought information is in the cache that was sought to translate the address. To be

After this one entry is restored, the translation lookaside buffer 10 stores not only the virtual address having the page table entry but also the base address having the physical pointer and up to two for the corresponding page table. It should be noted that additional physical pointers and are stored. In fact, it is also possible to store a third pointer to the page table. If a second virtual address is now provided to the translation lookaside buffer 10 and a miss occurs, it regenerates the base address into the context and generates a pointer to the second level table. This address is the translation lookaside buffer 1
It is compared with the address stored in 0. Since this address exists in the virtual field of one entry stored in the translation lookaside buffer 10,
Only one clock time is required, rather than the 10 or more clock times required to walk the page table for the first time to generate the next physical address. Then it is quite likely that recycling this new page table pointer will cause the next pointer to yield another pointer. Another pointer is that the size of the memory page at this point is 1 of memory.
Since it is 6 megabytes, it is stored in the translation lookaside buffer 10. The second pointer will probably also be recovered in the translation lookaside buffer 10, since it is unlikely that a program will take up more space than that space. Ultimately, a particular page table entry must be recovered, but generally this takes only one search level in the page table in main memory. Over 99% of the required pointers are translation lookaside buffers 10
Test results show that Therefore,
It can be seen that the operating speed of the translation lookaside buffer of the present invention greatly improves the operating speed of the computer device with which it is combined.

The instruction cache used in the translation lookaside buffer of the present invention is arranged to operate in parallel with the translation lookaside buffer so that cached instructions can be generated quickly. To that end, the data and instruction caches in the preferred embodiment of the present invention are page-sized and addressed by a combination of virtual and physical addresses. In the preferred embodiment, the least significant bit of the virtual address actually defines the particular cache line, and the physical bit determines whether the bit in the line is valid (from the correct page). To do this, the cache stores a tag at each entry, which tag contains the physical address of the informed page. If we compare this to the physical address provided by the translation lookaside buffer, then there is a cache hit. Thus, for example, the cache can preselect the particular line in which the instruction can reside, and the translation lookaside buffer determines the physical address. Given that the upper bits of the physical address are available, the information is available without delay.

FIG. 2 is a timing diagram showing the number of cycles saved by the use of the present invention. FIG. 2 compares the number of cycles used in a typical prior art device with the number of cycles used in a device utilizing the present invention. As can be seen from this figure, much of the machine operating time is saved by the present invention.

[Brief description of drawings]

FIG. 1 is a block diagram illustrating a translation lookaside buffer made in accordance with the present invention.

FIG. 2 is a timing diagram showing the number of cycles saved by use of the present invention.

[Explanation of symbols]

 10 Translation Lookaside Buffer 18, 20, 21 Multiplexer 19 Context Register 23 Physical Address Register 25 CTPR Register 29 IBAR Register

 ─────────────────────────────────────────────────── ─── Continued Front Page (72) Inventor Peter Mailing United States 01887 Wilmington Roosevelt Road, Massachusetts 11

Claims (2)

[Claims] 1. A physical address indicates a page in which information sought by a virtual address exists, and another physical address indicates a physical address of information sought by a virtual address. A page lookup table for at least a first level comprising means for storing virtual addresses and means for storing a physical address associated with each virtual address; A look-aside buffer for use in a virtual memory device, including a page-look-up table at each level. 2. A process of storing a virtual address to be translated into a page table entry in a translation lookaside buffer having an associated page table entry, and a page translation to a page table pointer in the same translation lookaside buffer having an associated page table pointer. In response to storing the virtual address to be translated, comparing the virtual address for which information is sought with the virtual address stored in the translation lookaside buffer, and comparing the virtual address to be translated to the page table entry. And a step of supplying a physical address that is a page table entry, and a step of supplying a physical address that is a page table pointer in response to a comparison of virtual addresses to be translated into a page table pointer. A fast way to translate addresses from virtual to physical.