Techniques for servicing fetch requests utilizing coalesing page table entries

• US 8,601,223 B1
• Filed: 10/24/2006
• Issued: 12/03/2013
• Est. Priority Date: 09/19/2006
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Yuan, Lingfeng
• Primary Examiner(s): Elmore, Stephen C
• Assistant Examiner(s): Giardino, Jr., Mark A
• Application Number:
  US11/586,826
• Time in Patent Office: 2,597 Days
• Field of Search: 711/154, 711/167, 711/208, 711/209, 711/170, 711/156, 711/165, 345/535, 345/543
• US Class Current: 711/154
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/652 Page size control

Abstract

A memory access technique, in accordance with one embodiment of the present invention, includes coalescing mappings between virtual memory and physical memory when a contiguous plurality of virtual pages map to a contiguous plurality of physical pages. Any of the coalesced page table entries are sufficient to map all pages within the coalesced region. Accordingly, a memory subsystem can redirect one or more pending page table entry fetch requests to an appropriate coalesced page table entry.

Claims

1. A method of accessing memory comprising:

determining if a fetched page table entry is a coalesced page table entry from a contiguous attribute of the fetched page table entry, wherein;

a first bit of the contiguous attribute specifies a type of encoding;

a plurality of other bits of the contiguous attribute specifies an actual number of contiguous pages when the first bit is set to a first state;

the plurality of other bits of the contiguous attribute specifies a power of two representation of the number of contiguous pages when the first bit is set to a second state;

determining if the coalesced page table entry can service one or more fetch requests pending in a queue; and

redirecting the one or more appropriate fetch requests in the queue to the coalesced page table entry if the coalesced page table entry can service the fetch requests.

2. The method according to claim 1, further comprising accessing physical memory utilizing a base page frame number in the fetched coalesced page table entry, a virtual page number of a given memory access request, the virtual page number in the fetched coalesced page table entry and an offset in the given memory access request.

3. The method according to claim 2, further comprising accessing the physical memory utilizing a page frame number in the fetched page table entry and an offset in the given memory access request if the fetched page table entry is non-coalesced page table entry.

4. The method according to claim 3, further comprising:

receiving a memory access request;

determining if a valid non-coalesced page table entry for the virtual address is cached in a translation lookaside buffer;

accessing the physical memory utilizing a page frame number in the cached page table entry and an offset in the memory access request if a valid non-coalesced page table entry for the virtual address is cached in a translation lookaside buffer;

determining if a valid coalesced page table entry for the virtual address is cached in the translation lookaside buffer; and

accessing the physical memory utilizing a base page frame number in the valid coalesced page table entry, the virtual page number of the memory access request, the virtual page number in the valid coalesced page table entry and an offset in the memory access request if the valid coalesced page table entry is cached in the translation lookaside buffer

adding a page table entry fetch request to a queue if neither a valid non-coalesced nor a valid coalesced page table entry are not cached in the translation lookaside buffer;

fetching the valid page table entry from a page table data structure if neither the valid non-coalesced nor the valid coalesced page table entry are not cached in the translation lookaside buffer.

5. The method according to claim 1, further comprising:

determining if a plurality of contiguous pages in a virtual address space are mapped to a plurality of contiguous pages in a physical address space;

generating a mapping between a virtual address and a corresponding physical address for each non-contiguous page and setting the contiguous attribute in the mapping to indicate that the mapping is not part of a set of contiguous pages; and

generating a mapping for each contiguous virtual address and a corresponding contiguous physical address containing a page frame address of a given contiguous page and setting the contiguous attribute in the mapping to indicate that there are a plurality of contiguous pages.

6. The method according to claim 5, further comprising caching each mapping as a page table entry in a page table.

7. The method according to claim 6, further comprising caching one or more of the page table entries in a translation lookaside buffer.

8. A method of accessing memory comprising:

receiving one or more memory access requests;

generating a fetch request for a given page table entry if a valid non-coalesced or a valid coalesced page table entry for each given memory access request not cached in the translation lookaside buffer;

sorting information about the fetch requests into a queue;

determining if a fetched page table entry is a coalesced page table entry or a non-coalesced page table entry from a contiguous attribute of the fetched page table entry, wherein;

a first bit of the contiguous attribute specifies a type of encoding;

a plurality of other bits of the contiguous attribute specifies an actual number of contiguous pages when the first bit is set to a first state;

the plurality of other bits of the contiguous attribute specifies a power of two representation of the number of contiguous pages when the first bit is set to a second state;

calculating a physical address for a given memory access request utilizing the fetched page table entry; and

servicing appropriate fetch requests pending in the queue utilizing the fetched coalesced page table entry, if the fetched coalesced page table entry can service one or more other fetch requests.

9. The method according to claim 8, further comprising:

determining if a valid page table entry is cached in a translation lookaside buffer; and

calculating the physical address for the given memory access request utilizing the cached page table entry.

10. The method according to claim 9, further comprising accessing a computing device-readable medium at the physical address.

11. The method according to claim 8, wherein the fetch requests are sorted in the queue per page.

12. A computing device comprising:

a first computing device-readable medium to store an address translation data structure;

a memory management unit, communicatively coupled to the first computing device-readable medium, including;

a second computing device-readable medium to cache one or more page table entries and one or more pending page table entry fetch requests; and

a paging unit to determine if a given page table entry fetched from the first computing device-readable medium is a coalesced page table entry or a non-coalesced page table entry, to service a given pending page table entry fetch request utilizing the coalesced page table entry and to redirect another pending page table entry fetch request to the coalesced page table entry, wherein a first bit of a contiguous attribute in the given page table entry specifies a type of encoding, a plurality of other bits of the contiguous attribute specifies an actual number of contiguous pages when the first bit is set to a first state and the plurality of other bits of the contiguous attribute specifies a power of two representation of the number of contiguous pages when the first bit is set to a second state.

13. The computing device of claim 12, wherein the page unit is further adapted to determine if a valid coalesced page table entry or a valid non-coalesced page table entry is cached in the second computing device-readable medium and to translate each given virtual address to a given physical address utilizing a given cached page table entry.

14. The computing device of claim 12, wherein the first computing device-readable medium comprises a system memory.

15. The computing device of claim 12, wherein the first computing device-readable medium comprises a graphics memory.

16. The computing device of claim 12, wherein the memory management unit:

caches the one or more page table entries in a translation lookaside buffer; and

stores the one or more page table entry fetch requests in a queue.

17. The computing device of claim 16, wherein the queue comprises a plurality of registers and a hardware linked list.

18. The computing device of claim 16, wherein the one or more page table entry fetch requests are sorted in the queue per page.