ALLOCATING PHYSICAL PAGES TO SPARSE DATA SETS IN VIRTUAL MEMORY WITHOUT PAGE FAULTING

A processing system for reduction of a virtual memory page fault rate that includes a first memory to store a dataset, a second memory to store a subset of the dataset, and a processing unit. The processing unit is configured to receive a memory access request including a virtual address and determine whether the virtual address is mapped to a first physical page in the first memory and or a second physical page in the second memory. The processing unit maps a third physical page in a free page pool of the second memory to the virtual address in response to the virtual address not being mapped to the second physical page. The processing unit also grants access to the third physical page that is mapped to the virtual address.

BACKGROUND

Processing systems implement many applications that operate on sparse datasets that are subsets of (or representative of) a much larger scale complete data set. For example, a volumetric flow simulation of smoke rising from a match in a large space can be represented with a sparse dataset including cells that represent a small volume of the large space that is occupied by the smoke. The number of cells in the sparse dataset may increase as the smoke diffuses from a small region near the match into the large space and consequently occupies an expanding volume in the space. For another example, propagation of light through a large space often is represented by a sparse dataset that includes cells that represent an illuminated volume within the large space. For yet another example, textures used for graphics rendering are stored as a mipmap with multiple levels of detail or the textures are generated on the fly. In either case, texture information is only applied to surfaces of objects in a scene that are visible from the point of view of a “camera” that represents the location of a viewer of the scene during the current frame. Thus, textures are only generated or retrieved from a remote memory and stored in a local memory for a sparse subset of surfaces, levels of detail, or other characteristics that define the textures that are applied to the visible surfaces. For yet another example, visualization systems such as flight simulators or marine simulators may consume or generate a terrain representation that includes large mega-scale and giga-scale partially-resident textures (PRT), which are locally stored portions of a complete set of textures that are stored in a remote memory.

DETAILED DESCRIPTION

Virtual memory systems are used to allocate physical memory locations, such as pages in a local memory, to sparse datasets that are currently being used by the processing system instead of allocating local memory to the complete data set. For example, a central processing unit (CPU) in the processing system manages a virtual memory page table implemented in a graphics processing unit (GPU) in the processing system. The CPU allocates pages in the local memory to a sparse data set that stores texture data that is expected to be used to render a scene in one or more subsequent frames. The CPU configures the virtual memory page table to map a subset of the virtual memory addresses used by applications running on the GPU to the allocated physical pages of the local memory. A cache hierarchy may be used to cache recently accessed or frequently accessed pages of the local memory. Compute units in the GPU are then able to access the sparse data set using memory access requests that include the virtual memory addresses. The memory access requests may be sent to address translation caches associated with the cache hierarchy and the local memory. The address translation caches store frequently accessed mappings of the virtual memory addresses to physical memory addresses. Since the dataset stored in the local memory (and the corresponding caches) is sparse, some variations of the compute units in the GPU generate memory access requests to virtual memory addresses that are not mapped to pages of the local memory. In a conventional processing system, a memory access request to an unmapped virtual memory address results in a page fault, which typically causes a very high latency interrupt in processing.

Conventional processing systems implement different techniques for recovering from page faults. For example, CPUs that implement full virtual memory subsystems use “fault-and-switch” techniques to stall the thread that generated the page fault while the requested page is generated or retrieved from a remote memory. In addition, the local memory must be configured to store the requested page, e.g., by rearranging previously stored memory pages to provide space for the requested page. Stalling the thread may also preempt the thread to allow another thread to execute on the processor core. Fault-and-switch techniques therefore often introduce unacceptably long delays for stalled threads in heavily parallel workloads or massively deep, fixed function pipelines such as graphics processing pipelines implemented in GPUs. In order to avoid page faults, some conventional processing systems populate the sparse datasets in the local memory ahead of time (e.g., one or more frames prior to the frame to be rendered using the sparse dataset) using conservative assumptions that require speculatively generating or retrieving larger amounts of data that may or may not be accessed by the workloads. Typically, much of the pre-populated sparse dataset is never used by the workload. Additional system resources are consumed by fallbacks that are created to handle incorrect predictions of the required data and blending that is used to hide “popping” that occurs if the requested data becomes available after a relatively long latency. Furthermore, large latencies are introduced when virtual pages are remapped to physical pages in response to changes in the sparse dataset that is stored in the local memory.

The long latencies incurred by moving portions of a dataset from a remote memory to a local memory implemented by a processing unit such as a graphics processing unit (GPU) can be reduced by allocating one or more physical pages in the local memory to a free page pool associated with an application executing on another processing unit such as a central processing unit (CPU). Physical pages in the free page pool are mapped to a virtual address in response to a memory access request that would otherwise have a page fault. For example, a physical page in the free page pool is mapped to a virtual address in a write command that is used to write data to the virtual address. The physical page is initialized (e.g., to all zeros so that the data in the physical page is in a known state) and the write command writes the data to the physical page that has been mapped to the virtual address. For another example, if a read command attempts to read texture data at a virtual address that is not mapped to a physical address in the local memory, the GPU spawns a process to compute locally the requested texture data and writes the requested texture data to a physical page from the free page pool that is mapped to the virtual address in the read command. Physical pages can be unmapped and returned to the free page pool, e.g., based on information such as access bits or dirty bits that indicate how frequently the physical pages are being utilized. Mapping of the physical pages in the free page pool to virtual addresses, initialization of the physical pages, or unmapping of the physical pages and returning the physical pages to the free page pool is performed by hardware, firmware, or software in the GPU instead of requiring the application (or an associated kernel mode driver) implemented by the CPU to allocate or deallocate physical pages in the local memory.

FIG. 1is a block diagram of a processing system100according to some embodiments. The processing system100includes a processing device105that is connected to one or more external memories such as a dynamic random access memory (DRAM)110. The processing device105includes a plurality of processing units111,112,113,114(collectively referred to as the “processing units111-114”) such as CPUs111-113and the GPU114. For example, the processing device105can be fabricated as a system-on-a-chip (SOC) such as an accelerated processing unit (APU) or accelerated processing device (APD) that is formed on a substrate. Each of the processing units111-114includes a plurality of processor cores or compute units that concurrently process different instructions. The processing units111-114also include one or more resources that are shared by the processor cores, such as caches, arithmetic logic units, floating-point units, branch prediction logic, memory or bus interfaces, and the like.

The processing device105includes a memory controller (MC)115that is used to coordinate the flow of data between the processing device105and the DRAM110over a memory interface120. The memory controller115includes logic used to control reading information from the DRAM110and writing information to the DRAM110. The processing units111-114communicate with each other, with the memory controller115, or with other entities in the processing system100using a bus125. For example, the processing units111-114can include a physical layer interface or bus interface for asserting signals onto the bus125and receiving signals from the bus125that are addressed to the corresponding processing unit111-114. Some embodiments of the processing device105also include one or more interface blocks or bridges such as a northbridge or a southbridge for facilitating communication between entities in the processing device105.

The processing device105implements an operating system (OS)130. Although a single instance of the OS130is shown inFIG. 1, some embodiments of the processing device105implement multiple instantiations of the operating system or one or more of the applications. For example, virtual machines executing on the processing units111-114can execute separate instances of the operating system or one or more of the applications. The processing device105also implements one or more applications135that generate workloads in the processing device105and a kernel mode driver (KMD)140. Some embodiments of the kernel mode driver140are able to map physical pages to virtual pages. However, overhead associated with transitioning the processing device105(or one of the processing units111-114) to the kernel mode limits the number of physical-to-virtual mappings that can be performed in a given time interval, which typically forces the kernel mode driver140to perform physical-to-virtual mappings in a batch mode, e.g., by performing a list of physical-to-virtual mappings once per rendered frame in graphics processing.

Some embodiments of the processing device105perform graphics processing to render scenes represented by a 3-D model to generate images for display on a screen145. For example, the DRAM110stores a dataset including information representative of the 3-D model. However, in some cases a latency for conveying information between the GPU114and the DRAM110, e.g., via the bus125or the memory interface120, is too large to allow the GPU114to render images at a sufficiently high rate to provide a smooth viewing experience for a user.

A local memory system150is connected to the GPU114by an interconnect that does not include the interface120or the bus125. Consequently, a latency for accessing information stored in the local memory system150is lower than a latency for accessing information stored in the DRAM110. For example, the latency between the GPU114and the local memory system150is low enough to allow the GPU114to render images at a sufficiently high rate to provide a smooth viewing experience for the user. The local memory system150stores a subset of the dataset stored in the DRAM110. For example, the local memory system150may store a sparse dataset that includes (or is representative of) the subset of the dataset stored in the DRAM110. The subset that is stored in the local memory system150is retrieved or copied from the DRAM110, or the information in the subset is generated in response to memory access requests, as discussed herein. The GPU114uses the information stored in the local memory system150to render portions of the scene to generate an image for display on the screen145. The GPU114transmits information representative of the rendered images to the screen145via the bus125. Although not shown inFIG. 1, in some variations the local memory system150or other local memory systems (not shown) can be connected to any of the processing units111-114and the local memory systems can be used to store subsets of datasets that are stored in the DRAM110.

The local memory system150implements virtual addressing so that memory access requests from the GPU114refer to virtual addresses, which are translated to physical addresses of physical pages in the local memory system150or the DRAM110. Memory access requests including virtual addresses are provided to the local memory system150by the GPU114. The local memory system150determines whether the virtual address is mapped to a physical page in the local memory system150or a physical page in the DRAM110. If the virtual address is mapped to a physical page in the local memory system150, the local memory system150grants access to the physical page, e.g., to read information from the physical page or write information to the physical page based on the virtual address. However, if the virtual address is not mapped to physical page in the local memory system150, the local memory system150maps a physical page from a free page pool implemented in the local memory system150to the virtual address in the memory access request and grants access to the physical page that is mapped to the virtual address. Thus, the local memory system150avoids causing a page fault, which would typically occur if the GPU114attempted to access a virtual address that was not mapped to a physical page in the local memory system150.

FIG. 2is a block diagram of a portion200of a processing system according to some embodiments. The portion200is implemented in some embodiments of the processing system100shown inFIG. 1. The portion200includes a GPU205that is connected to a local memory system210. The GPU205exchanges signaling with one or more applications215and a kernel mode driver (KMD)220, which are implemented in a processing unit such as one of the CPUs111-113shown inFIG. 1. The GPU205implements one or more graphics engines225that are configured as portions of a graphics pipeline, for general purpose computing, or other functionality. For example, a geometry engine230in the GPU205implements a geometry front-end that processes high-order primitives, a tessellator that receives the high-order primitives and generates lower-order primitives from the input higher-order primitives, and a geometry back-end that processes the low-order primitives. A compute unit231in the GPU205is configured to perform general purpose computing operations. A rendering engine232in the GPU205is configured to render images based on the primitives provided by the geometry engine230. For example, the rendering engine232is able to receive vertices of the primitives generated by the geometry engine230in object space, e.g., via primitive, vertex, and index buffers. The rendering engine232is then able to perform rasterization of the primitives to generate fragments (or pixels) from the input geometry primitives and shade the fragments (or pixels) using applicable textures.

The local memory system210is used to store a subset of a complete dataset that is stored in a remote memory such as the DRAM110shown inFIG. 1. The subset includes physical pages that are likely to be accessed by the GPU205during a subsequent time interval, such as one or more frames. For example, in some variations, the application215is a videogame that utilizes the GPU205to render images of a scene represented by a 3-D model. A local store240includes physical pages that are allocated to the application215, which is able to access the physical pages using virtual addresses that are mapped to the physical pages. The local memory system210also includes a free page pool245made up of one or more physical pages that are not currently allocated to an application. The physical pages in the free page pool245can be mapped to a first virtual address that is used to reference the physical page before it is in the free page pool245. Physical pages in the free page pool245are mapped to a second virtual address in response to the GPU205generating a memory access requests to the second virtual address, which is not mapped to a physical page in the local memory system210. For example, the subset of the complete dataset stored in the local memory system210can be a sparse subset, in which case a memory access request may request a portion of the subset that is not currently stored in the local memory system210. Adding a physical page from the free page pool245to the local store240and mapping its physical address to the second virtual address in the memory access request allows the memory access request to be granted without causing a page fault, as discussed herein.

A page table250is included in the GPU205and used to store mappings of virtual addresses to physical addresses of physical pages in the local memory system210or a remote memory such as the DRAM110shown inFIG. 1. A free page table255is used to store information indicating the physical pages that are included in the free page pool245. Some embodiments of the free page table255include registers that indicate a number of pages in the free page pool245.

Some embodiments of the local memory system210also implement a cache hierarchy (not shown inFIG. 2) that includes caches for caching data or instructions for the GPU205. A corresponding set of address translation buffers260,261,262,263,264(collectively referred to herein as “the address translation buffers260-264”) that include physical-to-virtual address mappings that have been frequently or recently accessed by corresponding entities such as the GPU205, the graphics engine225, the geometry engine230, the compute unit231, or the rendering engine232. For example, the address translation buffer260stores physical-to-virtual address mappings that have been frequently or recently accessed by the geometry engine230, the address translation buffer261stores physical-to-virtual address mappings that have been frequently or recently accessed by the compute unit231, and the address translation buffer262stores physical-to-virtual address mappings that have been frequently or recently accessed by the rendering engine232. A higher level address translation buffer (VML1)263stores physical-to-virtual address mappings that have been frequently or recently accessed by the graphics engine225and the highest level address translation buffer (VML2)264stores physical-to-virtual address mappings that have been frequently recently accessed by the GPU205.

A command processor265receives commands from the application215and executes the commands using the resources of the GPU205. The commands include draw commands and compute dispatch commands, which cause the command processor265to generate memory access requests. For example, the command processor265can receive a command from the application215instructing the GPU205to write information to a memory location indicated by a virtual address included in the write command. For another example, the command processor265can receive a command from the application215instructing the GPU205to read information from a memory location indicated by a virtual address included in the read command. The application215is also configured to coordinate operation with the kernel mode driver220to allocate memory in the local store240, as well as add or monitor physical pages in the free page pool245.

As the commands are executed, the graphics engines225translate virtual addresses to physical addresses using the address translation buffers260-264. However, in some cases the address translation buffers260-264do not include a mapping for a virtual address, in which case a memory access request to the virtual address misses in the address translation buffers260-264. The address translation buffer264is therefore configured to add physical pages from the free page pool245to the local store240and map the added physical page to a corresponding virtual address. For example, the address translation buffer264pulls a free physical page from the free page pool245when a dynamically allocated surface (e.g., a surface generated by the geometry engine230) touches a page of virtual memory that has not yet been mapped to a physical page. The address translation buffer264then updates the page table250with the new virtual-to-physical mapping and removes the information indicating the physical page from the free page table255. Some embodiments of the address translation buffer264are configured to serialize and manage the free page pool245and update the page table250concurrently with mapping the physical pages from the free page pool245to virtual addresses. Some embodiments of the page table250also store access bits and dirty bits associated with each of the allocated physical pages. The application215or the kernel mode driver220are able to use the values of the access bits or the dirty bits to select physical pages that are available to be reclaimed and added to the free page pool245, e.g., by unmapping the physical-to-virtual address mapping and updating the page table250and the free page table255accordingly.

FIG. 3is a block diagram of a local memory system300according to some embodiments. The local memory system300is implemented in some embodiments of the local memory system150shown inFIG. 1or the local memory system210shown inFIG. 2. The local memory system300includes a local memory305that is connected to a cache hierarchy including a higher level L2 cache310and lower level L1 caches315,316,317, which are collectively referred to as the L1 caches315-317. Some embodiments of the L2 cache310are inclusive of the L1 caches315-317so that entries in the L1 caches315-317are also stored in the L2 cache310. Physical pages in the local memory305, the L2 cache310, and the L1 caches315-317are accessible using virtual addresses that are mapped to the physical addresses of the physical pages. The local memory305, the L2 cache310, and the L1 caches315-317are therefore associated with address translation buffers, such as the address translation buffers260-264shown inFIG. 2, which include mappings of virtual addresses to the physical addresses of the physical pages in the corresponding local memory305, L2 cache310, or L1 caches315-317.

The local memory305includes a local store320of physical pages325, which are allocated to applications such as the application215shown inFIG. 2. Copies of some of the physical pages325are stored in the L2 cache310and respective fractions of them in the L1 caches315-317. The local memory305also includes a free page pool330that includes physical pages335that have not been mapped to virtual addresses and are therefore available for on-demand allocation, e.g., in response to memory access requests to a virtual address that is not mapped to a physical page in the local store320. On-demand allocation of one of the physical pages335maps the physical page to a virtual address and adds the mapped to physical page to the local store320, as indicated by the arrow340. The newly mapped physical page is therefore accessible (e.g., the physical page can be written to or read from) by entities in a processing system such as the GPU114shown inFIG. 1or the GPU205shown inFIG. 2.

Mapped physical pages can also be reclaimed from the local store320and returned to the free page pool330, as indicated by the arrow345. For example, an application or a kernel mode driver such as the application135and the kernel mode driver140shown inFIG. 1or the application215the kernel mode driver220shown inFIG. 2decides whether to reclaim a physical page based on information such as access bits that indicate how frequently a mapped physical page has been accessed or dirty bits that indicate whether information stored in the mapped physical page has been propagated to other memories or caches in the processing system to maintain cache or memory coherency. Physical pages that are accessed less frequently or have fewer dirty bits may be preferentially reclaimed relative to physical pages that are accessed more frequently or have more dirty bits. Reclaimed physical pages are unmapped from their previous virtual addresses and become available for subsequent on-demand allocation.

FIG. 4is a block diagram of a portion400of a processing system including an address translation buffer405, a local memory410, and the remote memory415according to some embodiments. The portion400is implemented in some embodiments of the processing system100shown inFIG. 1. The local memory410and the remote memory415are implemented in some embodiments of the local memory system150and the DRAM110shown inFIG. 1, respectively. The address translation buffer405is implemented in some embodiments of the address translation buffers260-264shown inFIG. 2.

The local memory410includes a local store420of physical pages that are addressed by physical addresses such as PADDR_1, PADDR_2, PADDR_3, and PADDR_M. The local memory410also includes a free page pool425of physical pages addressed by physical addresses such as PADDR_X, PADDR_Y, and PADDR_Z. The physical pages and the corresponding physical addresses in the local store420and the free page pool425may or may not be contiguous with each other. Although not shown inFIG. 4in the interest of clarity, the remote memory415also includes physical pages that are addressed by corresponding physical addresses.

The address translation buffer405indicates mappings of virtual addresses to the physical addresses in the local memory410and the remote memory415. The address translation buffer405includes a set of virtual addresses (VADDR_1, VADDR_2, VADDR_3, and VADDR_N) and corresponding pointers that indicate the physical addresses that are mapped to the virtual addresses. For example, the address translation buffer405indicates that the virtual address VADDR_1is mapped to the physical address PADDR_1in the local store420, the virtual address VADDR_3is mapped to the physical address PADDR_M in the local store420, and the virtual address VADDR_N is mapped to the physical address PADDR_3in the local store420. The address translation buffer405also indicates that the virtual address VADDR_2is mapped to a physical address in the remote memory415. In some variations, some of the virtual addresses in the address translation buffer405are not mapped to a physical address.

Memory access requests that include the virtual addresses VADDR_1, VADDR_2, and VADDR_N will hit in the address translation buffer405because these virtual addresses are mapped to physical addresses in the local memory410. Memory access requests that include the virtual address VADDR_2will miss in the address translation buffer405because this virtual address is mapped to a physical address in the remote memory415. A miss in the address translation buffer405would lead to a page fault in a conventional processing system. However, the processing system that includes the portion400is configured to allocate a physical page from the free page pool425and map the physical page into a virtual address indicated in the address translation buffer405instead of causing a page fault. Physical pages from the free page pool425can be added to the local store420in response to a miss in the address translation buffer405that occurs because the corresponding virtual address is not mapped to any physical address.

FIG. 5is a block diagram of the portion400of the processing system shown inFIG. 4following on-demand allocation of a physical page from a free page pool according to some embodiments. In response to a miss in the address translation buffer405at the virtual address VADDR_2, a physical page indicated by the physical address PADDR_X has been pulled from the free page pool425and mapped to the virtual address VADDR_2, as indicated by the pointer500. The physical page indicated by the physical address PADDR_X is now a part of the local store420and is no longer one of the available physical pages in the free page pool425. The physical page indicated by the physical address PADDR_X is therefore made available for access to a GPU that is connected to the local memory410without interaction or intervention by another processor such as a CPU and without causing a page fault that would conventionally be needed to retrieve physical pages from the remote memory415.

FIG. 6is a flow diagram of a method600for on-demand allocation of physical pages from a free page pool in response to a miss in an address translation buffer generated by a write command according to some embodiments. The method600is implemented in an address translation buffer such as some embodiments of the address translation buffer264shown inFIG. 2.

At block610, a write command is received that includes a virtual address indicating a location that is to be written by the write command. At decision block615, the address translation buffer determines whether the virtual address is mapped to a physical address of a physical page in the local memory. If so, the address translation buffer translates the virtual address to the physical address that indicates the physical page in the local memory at block620. The information indicated by the write command is then written (at block625) to the physical page indicated by the physical address that corresponds to the virtual address in the write command. If the virtual address is not mapped to a physical address of a physical page in the local memory, the method flows to block630.

At block630, a physical address of a physical page in the free page pool is mapped to the virtual address. The physical page is therefore removed from the free page pool and added to the local store. In some embodiments, mapping the physical address to the virtual address includes updating page tables, free page tables, and other address translation buffers to reflect the mapping of the physical page to the virtual address. At block635, the physical page is initialized to a known state such as all zeros. At block640, the write command writes information to the physical page based on the virtual address. In some embodiments, the information that is written to the physical page is propagated to other memories or caches based on memory or cache coherence protocols.

Implementing on-demand allocation of physical pages from the free page pool in response to write commands improves the speed and efficiency of the processing system. For example, applications such as physical simulations or games frequently determine the physical pages that need to be written during execution of the application as the physical pages are being written by the application. On-demand allocation of the physical pages removes the need to perform a pre-pass to estimate the number and addresses of the physical pages that could potentially be written in the future. This approach also conserves memory by removing the need to conservatively estimate the number of physical pages that could potentially be written by the application during a particular time interval, which typically leads to numerous physical pages being loaded into the local store and mapped to virtual addresses, but never accessed.

FIG. 7is a flow diagram of a method700for on-demand allocation of physical pages from a free page pool in response to a miss in an address translation buffer generated by a read command according to some embodiments. The method700is implemented in an address translation buffer such as some embodiments of the address translation buffer264shown inFIG. 2.

At block710, a read command is received that includes a virtual address indicating a location that is to be read by the read command. At decision block615, the address translation buffer determines whether the virtual address is mapped to a physical address of a physical page in the local memory. If so, the address translation buffer translates the virtual address to the physical address that indicates the physical page in the local memory at block720. The physical page indicated by the virtual address in the read command is then read (at block725) from the physical page indicated by the physical address that corresponds to the virtual address in the read command. If the virtual address is not mapped to a physical address of a physical page in the local memory, the method flows to block730.

At block730, a new local compute process is spawned to generate the data that is to be read. Some embodiments of the process are executed concurrently or in parallel with the current process that includes the read command. For example, if the read command is being executed by one graphics engine implemented by the GPU, the newly spawned process is executed by another graphics engine implemented by the GPU.

At block735, a physical address of a physical page in the free page pool is mapped to the virtual address in the read command. The physical page is therefore removed from the free page pool and added to the local store. In some embodiments, mapping the physical address to the virtual address includes updating page tables, free page tables, and other address translation buffers to reflect the mapping of the physical page to the virtual address. At block740, the spawned process writes the computed data to the physical page indicated by the virtual address. In some variations, an application such as the application135shown inFIG. 1or the application215shown inFIG. 2provides the process that is used to write the computed data to the physical page. At block745, the read command reads the computed information from the physical page based on the virtual address. In some embodiments, the information that is written to the physical page by the spawned process (and read from the physical page by the read command) is propagated to other memories or caches based on memory or cache coherence protocols.

Implementing on-demand allocation of physical pages from the free page pool in response to read commands (e.g., by spawning a concurrent process to write the requested information to a physical page pool from the free page pool) improves the speed and efficiency of the processing system. For example, in the case of a GPU that is performing rendering that requires reading sparse texture data that is generated by the GPU, only the physical pages that correspond to surfaces rendered by the GPU are generated, which reduces the consumed memory by eliminating the need to conservatively estimate the physical pages that need to be generated in advance. In addition, the physical pages that are generated and mapped to virtual addresses on-demand do not require interaction with or intervention by one or more CPUs such as the CPUs111-113shown inFIG. 1. Instead, the GPU receives a “miss” response from one or more address translation buffers when the GPU executes a read command for an unmapped virtual address. The miss response is used to spawn a computation to generate the data and write it back to a new page which is then immediately available for reading without CPU interaction or intervention.

FIG. 8is a flow diagram of a method800for allocating physical pages to virtual memory that is used to implement portions of a local store and a free page pool according to some embodiments. The method800is implemented in some embodiments of the processing system100shown inFIG. 1and the portion200of the processing system shown inFIG. 2. In some embodiments, the physical pages are allocated by an application or a kernel mode driver such as the application135and the kernel mode driver140shown inFIG. 1or the application215and the kernel mode driver220shown inFIG. 2.

At block805, the application requests allocation of physical pages with virtual memory that is associated with the application. The kernel mode driver receives the request and allocates the physical pages to the virtual memory. For example, the application can allocate physical memory by requesting a virtual memory allocation that is mapped to physical memory. The physical pages that have been allocated to the virtual memory can therefore be accessed using a corresponding range of (first) virtual addresses. At block810, the application or the kernel mode driver initializes the physical pages in the local store using the first virtual addresses. In some variations, the application or the kernel mode driver initializes the physical pages to a known state, e.g., by initializing the physical pages to all zeros. Initializing the physical pages to a known state allows the application to write to only a small subset of a physical page after the physical page has been dynamically allocated from the free page pool because the remainder of the page has been initialized to the known value.

At block815, the application requests allocation of a second set of virtual addresses to a subset of the virtual memory. At this point in the method800, the second set of virtual addresses do not have physical memory mapped to them. Thus, the application is not able to directly access physical pages using second virtual addresses in the second set.

At block820, the application requests that the kernel mode driver add physical memory to the application's free page pool. Since the application has only been allocated the second set of virtual addresses, which are not yet mapped to physical memory, the application indicates the physical pages that are to be added to the free page pool using first virtual addresses in the first virtual address range that was allocated at block805. The kernel mode driver translates the first virtual addresses into physical addresses of physical pages that are then added to the application's free page pool. Once the physical pages have been added to the free page pool, they are mapped to corresponding second virtual addresses in the second set of virtual addresses. In some embodiments, the number of physical pages that are initially allocated to the free page pool is predetermined and the number is determined based upon analysis of previous allocations of physical pages to the free page pool. As discussed herein, physical pages can be pulled from the free page pool into the local store in response to read or write misses. Pulling a physical page from the free page pool into the local store is done by changing the virtual address of the physical page from the second virtual address that references the free page pool to a new virtual address that references the local store. Thus, the actual number of physical pages that are available in the free page pool fluctuates as physical pages are added to the local store or reclaimed from the local store, as discussed herein.

FIG. 9is a flow diagram of a method900for reclaiming physical pages from a local store and adding them to a free page pool according to some embodiments. The method900is implemented in some embodiments of the application135shown inFIG. 1, the kernel mode driver140shown inFIG. 1, the application215shown inFIG. 2, or the kernel mode driver220shown inFIG. 2. In some embodiments, the application and the kernel mode driver may coordinate operation to implement the method900.

At block905, the application (or kernel mode driver) accesses information indicating a number of physical pages that are in the free page pool. For example, the processing system can maintain one or more registers that are incremented in response to adding physical pages to the free page pool, allocating physical pages to the free page pool, or reclaiming physical pages for the free page pool. The registers are decremented in response to pulling physical pages from the free page pool, mapping them to virtual addresses, and adding the mapped physical pages to a local store.

At decision block910, the application (or kernel mode driver) compares the number of physical pages in the free page pool to a threshold value. If the number is greater than the threshold value, indicating that a sufficient number of physical pages are available in the free page pool, the application (or kernel mode driver) maintains (at block915) the current mapping of virtual addresses to physical pages and does not reclaim any physical pages for the free page pool. If the number is less than the threshold value, the method flows to block920.

At block920, the application (or kernel mode driver) unmaps virtual addresses of one or more physical pages that are included in the local store in the local memory. Some embodiments of the application (or kernel mode driver) select physical pages in the local store for unmapping based on access bits or dirty bits included in the physical pages, as discussed herein. At block930, the application (or kernel mode driver) as the unmapped physical pages to the free page pool so that the unmapped physical pages are available for on-demand allocation.

Physical pages can be reclaimed and added to the free page pool at any time. Pulling physical pages from the free page pool or adding them to the free page pool does not change the allocated memory or virtual addresses, it just changes the physical pages that are in the free page list. In some variations, only virtual addresses that are currently unmapped and flagged as wanting dynamic allocation are mapped by the hardware to pages in the free page pool. The application should not access pages in the free page pool using virtual address synonyms such as the original direct virtual address otherwise incoherent results may occur. Also, the kernel mode driver should wait until all potential dynamic allocations have been suspended before changing or removing pages from its free page list.