Patent Publication Number: US-8543792-B1

Title: Memory access techniques including coalesing page table entries

Description:
BACKGROUND OF THE INVENTION 
     Instructions and data used by a computing device are stored at physical addresses in one or more primary or secondary memory devices. Primary memory device, such as system memory, graphics memory and the like, is characterized by quick access times but stores a limited amount of data. Secondary memory devices, such as magnetic disk drives, optical disk drives and the like, can store large amounts of data, but have relatively longer access times as compared to the primary memory devices. 
     Generally, instructions and data are stored in pages in the one or more secondary memory devices. As pages are needed by a given application, they can be moved into one or more primary memory devices. Pages that are no longer needed by the application can be moved from the primary memory device back to the secondary memory device to make room for other pages that are needed by a given application. When pages are moved from secondary to primary memory or moved from primary memory back to secondary memory, their physical addresses change. However, it is undesirable and inefficient for applications running on a computing device to keep track of these changing physical addresses. 
     Accordingly, the applications utilize virtual addressing to access instructions and data. Virtual addressing provides a separation between the physical memory and the virtual addresses that an application utilized to load or store data and instructions. Processes running inside a virtual memory space do not have to move data between physical memory devices, and do not have to allocate or reallocate portion of the fixed amount of system level memory between them. Instead, a memory management unit (MMU) and/or the operating system (OS) keeps track of the physical location of each piece of data, and moves data between physical locations to improve performance and/or ensure reliability. 
     Referring to  FIG. 1 , an exemplary address translation data structure utilized to translate virtual addresses  110  to physical addresses  120  is illustrated. The address translation data structure may include a page table data structure  130  and a translation lookaside buffer (TLB)  140 . The page table data structure  130  may include a page directory  150  and one or more page tables  160 - 190 . The page directory  150  includes a plurality of page directory entries (PDE). Each PDE includes the address of a corresponding page table  160 - 190 . Each PDE may also include one or more parameters. Each page table  160 - 190  includes one or more page table entries (PTE). Each PTE includes a corresponding physical address of data and/or instructions in primary or secondary memory. Each PTE may also include one or more parameters. 
     Upon receiving a virtual address, the TLB  140  is accessed to determine if a mapping between the virtual address  110  and the physical address  120  has been cached. If a valid mapping has been cached (e.g., TLB hit), the physical address  120  is output from the TLB  140 . If a valid mapping is not cached in the TLB, the page table data structure is walked to translate the virtual address  110  to a physical address  120 . More specifically, the virtual address  110  may include a page director index, a page table index, and a byte index. The page directory index in the virtual address  110  is used to index the page directory  150  to obtain the address of an appropriate page table  170 . The page table index in the virtual address  110  is used to index the appropriate page table specified in the given PDE to obtain the physical address  120  of the page containing the data. The byte index in the virtual address  110  is then used to index the physical page to access the actual data. The resulting mapping is then typically cached in the TLB  140  for use in translating subsequent memory access requests. Furthermore, as a page moves from secondary memory to primary memory or from primary memory back to secondary memory, the corresponding PTE in the page table data structure  130  and TLB  140  is updated. 
     Generally, the PTE can also store additional attributes associated with memory accesses. An exemplary page table  140  that stores a plurality of PTEs is shown in  FIG. 2 . Each PTE in the page table  140  includes a page frame address  120  and one or more attributes  220 . The attributes  220  may include a dirty bit, an accessed bit, a page check disable bit, page write transparent bit, a user accessible bit, a writeable bit, a present bit, a hash function identification bit, a valid bit, an address compare bit, a referenced bit, a changed bit, storage control bits, a no execute bit, page protection bits and/or the like. The attributes  220  can be used by the MMU and/or OS to manage the data in the primary and secondary memories and access thereto. 
     Referring now to  FIG. 3 , an exemplary memory subsystem according to the conventional art is shown. The memory subsystem includes a memory management unit  305  communicatively coupled to a computing device readable medium (e.g., primary memory), such as random access memory (RAM)  310 . The memory  310  is adapted to store at least a portion of one or more address translation data structures  315 , and data and instructions  320 . In one implementation, the address translation data structure includes a page directory and one or more page tables  325  A given page table  325  may include a plurality (X) of PTEs. 
     The memory management unit  305  includes a paging module  320  and a cache  335 . The paging module  330  is adapted to manage caching of page table entries  325 ′ and translation of virtual address to physical addresses. In particular the paging module  330  caches one or more address translation mappings to service memory access requests. Each mapping includes a previously utilized page table entry and is stored as part of a translation lookaside buffer (TLB)  325 ′. Because the cache  335  in the memory management unit  305  is relatively small, the paging module  330  swaps mappings in an out of the cache  335  in accordance any conventional replacement algorithm. Accordingly, there are various tradeoffs between the size of the cache  335 , latency resulting from having to swap page table entries between the cache  335  and memory  310 , and communication traffic generated between the cache  335  and the memory  310 . 
     SUMMARY OF THE INVENTION 
     Each page in a virtual memory space may be mapped to a page in a physical address space. Furthermore, there may be cases when a plurality of contiguous virtual pages are mapped to a plurality of contiguous physical pages. Accordingly, embodiments of the present invention are direct toward memory access techniques including coalesced mappings between contiguous pages. In one embodiment, a computing device includes memory and a memory management unit. The memory is adapted to store an address translation data structure used to translate virtual addresses to physical addresses. The memory management unit includes a cache and a paging module. The cache is adapted to store some or all of the mappings of the address translation data structure. The paging module is adapted to coalesce a plurality of mappings between contiguous virtual and physical memory. The paging module may further be adapted to load one of the plurality of coalesced mappings in the address translation data structure, instead of all of them, when loading some or all of the mappings into the cache. The paging module may further be adapted to use one of the coalesced mappings to translate any of the coalesced virtual address to the corresponding physical address. 
     In another embodiment, a technique for generating an address translation data structure includes 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. If a given page is not contiguous, a mapping between the given virtual address and the corresponding physical address is generated and a contiguous attribute corresponding to the mapping is set to indicate that the page is not contiguous. If the page is contiguous with another page, a mapping for each contiguous virtual address and corresponding contiguous physical address is generated and the contiguous attribute corresponding to each such mapping is set to indicate that there are a plurality of contiguous pages. 
     In yet another embodiment, a method of accessing memory includes receiving a memory access request that includes a virtual address. Upon receipt of the request it is determined if there is a valid mapping between the virtual address and a physical address stored in a cache. If a valid mapping is not stored in the cache, it is determined if the virtual address in the request is greater than or equal to a virtual address in any other mapping in the cache, and less than the sum of the virtual address in a mapping and one less than a number of coalesced pages indicated in an attribute of the other mapping containing the virtual address. In such a case, the physical address may be calculated as a function of the physical address and the virtual address in the mapping and the virtual address in the request. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the present invention are illustrated by way of example and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: 
         FIG. 1  shows a block diagram of an exemplary address translation data structure according to the conventional art. 
         FIG. 2  shows a block diagram of an exemplary page table according to the conventional art. 
         FIG. 3  shows a block diagram of an exemplary memory subsystem according to the conventional art. 
         FIG. 4  shows a block diagram of an exemplary computing device for implementing embodiments of the present invention. 
         FIG. 5  shows a block diagram illustrating a mapping between a virtual address space and a physical address space. 
         FIG. 6  shows a block diagram of an exemplary page table, in accordance with one embodiment of the present invention. 
         FIG. 7  shows a block diagram of a memory access subsystem, in accordance with one embodiment of the present invention. 
         FIG. 8  shows a flow diagram of a method of generating a page table, in accordance with one embodiment of the present invention. 
         FIG. 9  shows a flow diagram of a method of translating a virtual address to a physical address, in accordance with one embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Reference will now be made in detail to the embodiments of the invention, examples of which are illustrated in the accompanying drawings. While the invention will be described in conjunction with these embodiments, it will be understood that they are not intended to limit the invention to these embodiments. On the contrary, the invention is intended to cover alternatives, modifications and equivalents, which may be included within the scope of the invention as defined by the appended claims. Furthermore, in the following detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it is understood that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention. 
     Referring to  FIG. 4 , an exemplary computing device  400  for implementing embodiments of the present invention is shown. The computing device  400  may be a personal computer, server computer, client computer, laptop computer, hand-held device, minicomputer, mainframe computer, distributed computer system or the like. The computing device  400  includes one or more processors (e.g., CPU)  410 , one or more computing device-readable media  415 ,  420 ,  425  and one or more input/output (I/O) devices  420 ,  430 ,  435 ,  440 ,  445 . The I/O device  430 ,  435 ,  440 ,  445  may include a network adapter (e.g., Ethernet card), CD drive, DVD drive and/or the like, and peripherals such as a keyboard, a pointing device, a speaker, a printer, and/or the like. The computing device  400  may also include one or more specialized processors, such as a graphics processing unit (GPU)  450 . 
     The computing device-readable media  415 ,  420 ,  425  may be characterized as primary memory and secondary memory. Generally, the secondary memory, such as a magnetic and/or optical storage, provides for non-volatile storage of computer-readable instructions and data for use by the computing device  400 . For instance, the disk drive  420  may store the operating system (OS)  455  and applications and data  460 . The primary memory, such as the system memory  415  and/or graphics memory  425 , provides for volatile storage of computer-readable instructions and data for use by the computing device  400 . For instance, the system memory  415  may temporarily store a portion of the operating system  455 ′ and a portion of one or more applications and associated data  460 ′ that are currently used by the CPU  410 , GPU  450  and the like. 
     The computing device-readable media  415 ,  420 ,  425 , I/O devices  420 ,  430 ,  435 ,  440 ,  445 , and GPU  450  may be communicatively coupled to the processor  410  by a chip set  465  and one or more busses. The chipset  465  acts as a simple input/output hub for communicating data and instructions between the processor  410  and the computing device-readable media  415 ,  420 ,  425 , I/O devices  420 ,  430 ,  435 ,  440 ,  445 , and GPU  450 . In one implementation, the chipset  465  includes a northbridge  470  and southbridge  475 . The northbridge  470  provides for communication with the processor  410  and interaction with the system memory  415 . The southbridge  475  provides for input/output function. 
     The graphics processing unit  450  may include a memory management unit (MMU)  480  for managing the transfer of data and instructions. However, in other embodiments the MMU  480  may be independent circuit, a part of the chip set  465 , a part of the primary or secondary memory, or other component in the computing device. 
     The MMU  480  translates virtual address to physical addresses. In one implementation, the virtual address space is divided into pages of size 2 N  bytes. The pages may be from 2 kilobytes to 512 megabytes or more, and are typically 4 kilobytes to 64 kilobytes in size. In such cases, the MMU  480  translates virtual page numbers to physical page numbers utilizing an address translation data structure. 
     The MMU  460  and/or OS  455  also creates and manages the address translation data structure. In addition to the conventional management, the MMU  460  and/or OS  455  also may coalesce mappings between virtual memory and physical memory that are stored in the address translation data structure, when a contiguous plurality of virtual pages map to a contiguous plurality of physical pages. The MMU  460  may then use any of the coalesced mappings to translate virtual address to physical addresses for the corresponding contiguous memory spaces. 
     Referring now to  FIG. 5 , an illustration of a mapping between a virtual address space and a physical address space, is shown. As depicted, each page in the virtual memory space may be mapped to a page in the physical address space. There may be cases during operation of the computing device  400  when a plurality of contiguous virtual pages are mapped to a plurality of contiguous physical pages. If a plurality of contiguous virtual pages are mapped to a plurality of contiguous physical pages, entries in an address translation data structure (e.g., page table data structure and/or TLB) may be coalesced. 
     Referring now to  FIG. 6 , an exemplary page table, in accordance with one embodiment of the present invention, is shown. Each PTE in the page table  600  includes a page frame address  610  and one or more attributes  620 . The attributes  620  may include one or more contiguous bits  630 , a dirty bit, an accessed bit, a page check disable bit, page write transparent bit, a user accessible bit, a writeable bit, a present bit, a hash function identification bit, a valid bit, an address compare bit, a referenced bit, a changed bit, storage control bits, a no execute bit, page protection bits and/or the like. If a plurality of contiguous virtual pages are mapped to a plurality of contiguous physical pages, the frame address  610  of each corresponding PTE (e.g., PTE  2 , PTE  3 , PTE  4 , PTE  5 ) may be the physical page number of the base physical page number (e.g., lowest address—0020) and the contiguous bits  630  are set to the number of contiguous pages (e.g., 4). 
     In one implementation, the contiguous bits directly specify the number of contiguous pages. For example, if there are three bits for specifying the number of contiguous pages and the bits are set to a value of “2,” then the contiguous bits indicate that there are two contiguous virtual pages mapped to two contiguous physical pages. In another implementation, the contiguous bits specify a power-of-two number of pages. For example, if there are three bits for specifying the number of contiguous pages and the bits are set to a value of “2,” then the contiguous bits indicate that there are four (e.g., 2 2 ) contiguous virtual pages mapped to four contiguous physical pages. In another implementation, the contiguous bits include a first bit that indicates whether the remaining contiguous bits directly specify the number of contiguous pages or if the contiguous bits specify a power-of-two number of pages. 
     Referring now to  FIG. 7 , a memory access subsystem, in accordance with one embodiment of the present invention, is shown. The memory subsystem  700  includes a memory management unit (MMU)  705  communicatively coupled to a computing device readable medium (e.g., primary memory), such as random access memory (RAM)  710 . In one implementation, the computing device-readable medium  710  may be system memory  415 . In another implementation, the computing device-readable medium  710  may be graphics memory  425 . The memory  710  is adapted to store at least a portion of one or more address translation data structures  715 , and data and instructions  720 . A given page table  725  of the address translation data structure  715  stored in the memory  710  may include a plurality of PTEs. 
     In one implementation, the MMU  705  may be an integral part of a graphics processor  450  or chip set  465 . In other implementations, the MMU  705  may be an independent circuit, a part of the primary or secondary memory, or the like. The memory management unit  705  includes a paging module  730  and a cache  735 . The paging module  730  is adapted to manage the caching of address translation mappings and translation of virtual address to physical addresses. In particular the paging module  730  caches one or more address translation mappings to service memory access requests. Each mapping includes a previously utilized page table entry and is stored in a translation lookaside buffer (TLB)  725 ′. If the page table  725  and/or TLB  725 ′ includes coalesced PTEs, any PTE within the coalesced region will be sufficient to map all pages within the coalesced region. Accordingly, the paging module  730  loads one of the coalesced PTEs and not all of them into the TLB  725 ′ in the cache  735 . In one implementation, the paging module  730  loads the PTE for the base physical page number. 
     When translating the virtual address to a physical address, the paging module  730  determines whether the virtual address of the request matches an entry in the TLB or page table data structure, or the virtual address of the request falls into the virtual address region covered by a coalesced TLB or page table entry. If the virtual address of the request has valid coalesced or non-coalesced entry, the physical address can be generated from the given entry. 
     Referring now to  FIG. 8 , a method of generating an address translation data structure, in accordance with one embodiment of the present invention, is shown. The method  800  includes determining if a set of N contiguous pages in a virtual address space are mapped to a set of N contiguous pages in a physical address space, at  810 . Pages that satisfy the condition that both the N virtual pages are contiguous and the N physical page are contiguous are simply referred herein to as contiguous pages. At  820 , a PTE is generated for each non-contiguous page and the contiguous attribute in the PTE is set accordingly. At  830 , a PTE is generated for each of the N contiguous page and the contiguous attribute in each PTE is set to indicate that there are N contiguous pages. At  840 , the generated PTEs are stored in an address translation data structure. In one implementation, the PTE are stored in a page table and or a translation lookaside buffer (TLB). Furthermore, in one implementation, the PTE are generated by the OS  455  of the computing device  400 . 
     Referring now to  FIG. 9 , a method of translating a virtual address to a physical address, in accordance with one embodiment of the present invention, is shown. In one implementation, the following method of translating a virtual address to a physical address may be performed by the memory management unit  480  of the computing device  400 . As depicted in  FIG. 9 , the method  900  includes receiving a memory access request at  910 . At  920 , it is determined if a valid PTE is cached in a translation lookaside buffer (TLB) for the virtual address contained in the memory access request. At  930 , if there is a valid PTE cached for the virtual address (e.g., a hit) than the page frame number in the valid PTE and the byte offset contained in the virtual address are utilized to access the physical memory. 
     At  940 , if the virtual address does not result in a TLB hit, it is determined if there is a valid contiguous PTE cached for the virtual address. In one implementation, the virtual address is 1) greater than a virtual address that maps to a given PTE in the cache and 2) less than the sum of that virtual address and one less than the number of contiguous pages as indicated by the contiguous attribute in the given PTE. In one implementation, the contiguous attribute directly specifies the number of contiguous pages. Accordingly, a hit for a contiguous PTE occurs if VA REQ &gt;=VA TLB  and VA REQ &lt;VA TLB +(CONFIG−1). In another implementation, the contiguous attribute specifies a power-of-two number of contiguous pages. Accordingly, a hit for a contiguous PTE occurs if VA REQ &gt;=VA TLB  and VA REQ &lt;VA TLB +(2 CONFIG −1). 
     At  950 , if a hit for a contiguous PTE is determined then the physical address of the page mapped to the virtual address of the memory access request is calculated based upon a virtual address in the contiguous PTE, a base physical address in the contiguous PTE and the virtual address in the request. In one implementation. The physical address is the sum of the physical address from the given PTE and the difference of the virtual address contained in the given PTE and the virtual address contained in the memory access request (e.g., PA REQ =PA TLB +(VA TLB −VA REQ )). At  960 , the calculated physical address and the byte offset contained in the virtual address are utilized to access the physical memory. 
     At  970 , if a miss for both a valid PTE and a contiguous PTE is determined, than an appropriate valid PTE or contiguous PTE is fetched from a page table data structure stored in a separate memory. The appropriate valid PTE or contiguous PTE stored in the separate memory maybe determined by utilizing the processes at  920  and  940 . Likewise, the processes at  930 ,  950  and  960  may be utilized for the appropriate valid PTE or contiguous PTE found in separate memory. The appropriate valid PTE or contiguous PTE retrieved from the separate memory may then be cached in the TLB for reference in subsequent memory access request. 
     Accordingly, embodiments of the present invention advantageously reduce the number of PTEs cached to service memory access requests when there are a plurality of contiguous virtual pages mapped to a plurality of contiguous physical pages. The technique also may reduce the amount of communication traffic and access latency associated with page misses by utilizing the PTE of a coalesced page to map the other contiguous virtual pages to physical pages. 
     The foregoing descriptions of specific embodiments of the present invention have been presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the Claims appended hereto and their equivalents.