Memory management for virtual address space with translation units of variable range size Number:7,386,697 from the United States Patent and Trademark Office (PTO) owispatent In a virtual memory system, address translation information is provided using a cluster that is associated with some range of virtual addresses and that can be used to translate any virtual address in its range to a physical address, where the sizes of the ranges mapped by different clusters may be different. Clusters are stored in an address translation table that is indexed by virtual address so that, starting from any valid virtual address, the appropriate cluster for translating that address can be retrieved from the translation table. The clusters are dynamically created from a fragmented pool of physical addresses as new virtual address mappings are requested by consumers of the virtual memory space.<H translation, management, Memory, manageme, 7386697.html, Patent, pto, 7386697

Title: Memory management for virtual address space with translation units of variable range size

Abstract: In a virtual memory system, address translation information is provided using a cluster that is associated with some range of virtual addresses and that can be used to translate any virtual address in its range to a physical address, where the sizes of the ranges mapped by different clusters may be different. Clusters are stored in an address translation table that is indexed by virtual address so that, starting from any valid virtual address, the appropriate cluster for translating that address can be retrieved from the translation table. The clusters are dynamically created from a fragmented pool of physical addresses as new virtual address mappings are requested by consumers of the virtual memory space.

Patent Number: 7,386,697 Issued on 06/10/2008 to Case, et al.

Inventors: Case; Colyn S. (Hyde Park, VT), Lorensen; Gary D. (San Jose, CA), Clay; Sharon Rose (Los Altos, CA)
Assignee: NVIDIA Corporation (Santa Clara, CA)

Appl. No.: 11/077,662

Filed: March 10, 2005

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
10769326	Jan., 2004	7296139

Current U.S. Class: 711/171 ; 710/9; 711/209

Field of Search: 711/209,171 710/9

References Cited [Referenced By]

U.S. Patent Documents


4992936	February 1991	Katada et al.
5058003	October 1991	White
5375214	December 1994	Mirza et al.
5446854	August 1995	Khalidi et al.
5479627	December 1995	Khalidi et al.
5796978	August 1998	Yoshioka et al.
5809554	September 1998	Benayon et al.
5928352	July 1999	Gochman et al.
5956756	September 1999	Khalidi et al.
5963984	October 1999	Garibay, Jr. et al.
5978893	November 1999	Bakshi et al.
6205530	March 2001	Kang
6205531	March 2001	Hussain
6356991	March 2002	Bauman et al.
6374341	April 2002	Nijhawan et al.
6418523	July 2002	Porterfield
6457068	September 2002	Nayyar et al.
6618770	September 2003	Nayyar et al.
6628294	September 2003	Sadowsky et al.
7003647	February 2006	Jacobs et al.
7050061	May 2006	Baldwin
7181585	February 2007	Abrashkevich et al.
2004/0117594	June 2004	VanderSpek

Primary Examiner: Sparks; Donald
Assistant Examiner: Rutz; Jared I
Attorney, Agent or Firm: Townsend and Townsend and Crew, LLP

Parent Case Text

CROSS-REFERENCES TO RELATED APPLICATIONS

This application is a continuation-in-part of application Ser. No. 10/769,326, filed Jan. 30, 2004, which disclosure is incorporated herein by reference for all purposes.

The present disclosure is related to the following commonly-assigned co-pending U.S. patent applications: Ser. No. 10/769,388, filed Jan. 30, 2004, entitled "Multi-Client Virtual Address Translation System with Translation Units of Variable Range Size"; and Ser. No., 10/769,357, filed Jan. 30, 2004, entitled "Virtual Address Translation System with Caching of Variable-Range Translation Clusters." The respective disclosures of these applications are incorporated herein by reference for all purposes.

Claims

What is claimed is:

1. A method for managing a virtual memory space, the method comprising: providing a pool of physical addresses; receiving a request for a virtual memory allocation from a client; creating a plurality of clusters from the pool, wherein each cluster represents a plurality of physical addresses selected from the pool and wherein the respective pluralities of physical addresses represented by different ones of the plurality of clusters correspond to different amounts of memory, wherein at least one of the clusters includes references to a plurality of blocks, each block comprising a range of contiguous physical addresses, and at least one of the referenced blocks is not contiguous with any other one of the referenced blocks; removing from the pool the physical addresses represented by each cluster that is created; for each of the clusters, defining a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster; and returning a reference to a mapped virtual address to the client.

2. The method of claim 1, wherein the act of providing a pool of physical memory includes: allocating memory from an operating system; and adding physical addresses for the allocated memory to the pool.

3. The method of claim 2, wherein the act of allocating memory from the operating system is performed in the event that the pool includes physical addresses corresponding to less than a threshold amount of memory.

4. The method of claim 2, wherein the act of allocating memory from the operating system includes allocating an amount of memory that is independent of a size of the virtual memory allocation requested by the client.

5. The method of claim 1, wherein the act of creating the plurality of clusters is terminated when the physical addresses represented by the plurality of clusters correspond to an amount of memory that equals or exceeds a size of the virtual memory allocation requested by the client.

6. The method of claim 1, wherein the act of creating the plurality of clusters is terminated when the physical addresses remaining in the pool correspond to an amount of memory that is less than a minimum amount.

7. The method of claim 6, wherein the minimum amount is independent of a size of the received request.

8. The method of claim 1, wherein defining the mapping includes adding each of the plurality of clusters to a cluster table representing the virtual memory space, wherein each cluster is added at a number of entries determined by the amount of memory represented by that cluster.

9. The method of claim 1, wherein the act of creating the plurality of clusters includes: attempting to create exactly one cluster that represents all of the physical addresses in the pool; and in the event that the attempt is not successful: separating the pool into two or more sub-pools; and attempting to create exactly one cluster that represents all of the physical addresses in one of the two or more sub-pools.

10. The method of claim 1, wherein the act of creating the plurality of clusters includes: setting a target range size to a maximum range size; attempting to create a cluster that represents a plurality of physical addresses corresponding to an amount of memory equal to the target range size; and in the event that the attempt is unsuccessful: setting the target range size to a smaller value; and repeating the act of attempting to create a cluster.

11. The method of claim 10, further comprising: in the event that the attempt is successful, attempting to create another cluster of the target range size.

12. The method of claim 1, wherein the act of creating the plurality of clusters includes: selecting a plurality of blocks for inclusion in one of the clusters based at least in part on respective bank identifiers of physical addresses in the blocks.

13. The method of claim 1, further comprising: in the event that a mapped virtual address is within an aperture range, providing mapping information to an operating system.

14. The method of claim 1, wherein each cluster includes a size field configured to store a value indicating the amount of memory represented by that cluster.

15. The method of claim 1, wherein the sizes of the clusters are independent of the size of the respective amounts of memory represented by the clusters.

16. The method of claim 1, wherein different ones of the clusters include references to different numbers of blocks and each cluster further includes a format field indicating the number of block references included in that cluster.

17. A method for managing a virtual memory space, the method comprising: providing a pool of physical addresses; receiving a request for a virtual memory allocation from a client; creating a plurality of clusters from the pool, wherein each cluster represents a plurality of physical addresses selected from the pool and wherein the respective pluralities of physical addresses represented by different ones of the plurality of clusters correspond to different amounts of memory, wherein at least one of the clusters includes references to a plurality of blocks of contiguous physical addresses, and wherein creating the plurality of clusters further comprises: selecting a candidate block from the pool based on an order of physical addresses, the first candidate block having a first block size; attempting to create a cluster that references the candidate block and at least one other block having the first block size; and in the event that the attempt is unsuccessful: selecting a portion of the candidate block as a new candidate block, the new candidate block having a second block size; and attempting to create a cluster that references the new candidate block and at least one other block having the second block size; removing from the pool the physical addresses represented by each cluster that is created; for each of the clusters, defining a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster; and returning a reference to a mapped virtual address to the client.

18. A computer program product comprising: a computer readable storage medium encoded with program code, the program code including: program code for providing a pool of physical addresses; program code for receiving a request for a virtual memory allocation from a client; program code for creating a plurality of clusters from the pool, wherein each cluster represents a plurality of physical addresses selected from the pool and wherein the respective pluralities of physical addresses represented by different ones of the plurality of clusters correspond to different amounts of memory, wherein at least one of the clusters includes references to a plurality of blocks, each block comprising a range of contiguous physical addresses, and at least one of the referenced blocks is not contiguous with any other one of the referenced blocks; program code for removing from the pool the physical addresses represented by each cluster that is created; program code for defining, for each of the clusters, a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster; and program code for returning a reference to a mapped virtual address to the client.

19. The computer program product of claim 18, wherein the program code for creating a plurality of clusters includes: program code for attempting to create exactly one cluster that represents all of the physical addresses in the pool; and program code for determining whether the attempt is successful and, in the event that the attempt is not successful, separating the pool into two sub-pools and attempting to create exactly one cluster that represents all of the addresses in one of the two sub-pools.

20. The computer program product of claim 18, wherein the program code for creating a plurality of clusters includes: program code for setting a target range size to a maximum range size; program code for attempting to create a cluster that represents a plurality of physical addresses corresponding an amount of memory equal to the target range size; and program code for determining whether the attempt is successful and, in the event that the attempt is not successful, setting the target range size to a smaller value and repeating the act of attempting to create a cluster.

21. The computer program product of claim 18, wherein the program code for creating a plurality of clusters includes: program code for selecting a candidate block of contiguous addresses from the pool based on an order of physical addresses, the first candidate block having a first block size; program code for attempting to create a cluster that references the candidate block and at least one other block having the first block size; and program code for determining whether the attempt is successful and, in the event that the attempt is not successful, selecting a portion of the candidate block as a new candidate block, the new candidate block having a second block size and attempting to create a cluster that references the new candidate block and at least one other block having the second block size.

Description

BACKGROUND OF THE INVENTION

The present invention relates in general to memory management systems and in particular to memory management for a virtual address space with translation units of variable range size.

Most modern computer systems generally implement some form of virtual memory, in which processes reference system memory locations using a "virtual" address rather than an address of a specific location in the memory. When a process makes a memory request using a virtual address, the system uses a page table to translate the virtual address to a specific location and accesses that location. The page table is typically implemented in a block of memory that includes an entry for each page (e.g., 4 kilobytes) of the virtual address space; the entry stores a physical address of a corresponding page of a physical address space. Page tables can also be structured hierarchically, so that only a portion of the page table needs to be resident in system memory at all times; the portion held in system memory can be used to locate other portions that may have been swapped out.

Virtual memory has a number of common uses. For example, general-purpose computer systems generally cannot guarantee that a process will receive memory resources in any particular arrangement or at any particular location. Virtual addressing enables processes to treat the memory as if it were arranged in a convenient manner, regardless of how it is actually arranged. As another example, systems that support parallel execution of multiple processes can provide a different virtual memory space for each process. This helps to avoid address conflicts between processes. Virtual addressing can also be used to map storage other than system memory, thereby enabling the system to swap data in and out of the system memory, address data in storage devices other than memory storage (e.g., image files resident on a system disk), and so on.

Within graphics processing subsystems, use of virtual memory has been relatively uncommon. Typically, a graphics processing subsystem is implemented on a plug-in printed circuit card that connects to a system bus, such as a PCI (Peripheral Component Interconnect) or AGP (Accelerated Graphics Port) bus. The card usually includes a graphics processing unit (GPU) that implements graphics functionality (e.g., rasterization, texture blending, etc.) and dedicated graphics memory. This memory is generally managed by the GPU or by a graphics driver program executing on the system central processing unit. The GPU can address graphics memory using either physical addresses or offset values that can be converted to physical addresses by the addition of a constant base address. The GPU (or graphics driver program) can also control the arrangement of physical memory allocations. For instance, a pixel buffer that is to be scanned out to a display device can be arranged to occupy a contiguous block of the graphics memory address space. Elements of graphics processing subsystems, including scanout control logic (or display drivers), graphics driver programs, GPUs, and the like are generally designed to use physical addressing and to rely on particular arrangements and allocations of memory.

As the amount of data (e.g., texture data) needed for graphics processing increases, graphics processing subsystems are beginning to rely on system memory for at least some storage of data (and in some instances command lists, etc.). Such subsystems generally use virtual addressing for system memory, with the required address translation being performed by a component external to the graphics processing subsystem. For instance, the AGP bus includes a Graphics Address Relocation Table (GART) implemented in the host-side chipset. Emerging high-speed bus technologies, such as PCI Express (PCI-E), do not provide GART or any other address translation functionality. As a result, graphics cards configured for such protocols will need to implement their own address translation systems if they are to access system memory.

An alternative to the graphics card is an integrated graphics processor (IGP). An IGP is a graphics processor that is integrated with one or more other system bus components, such as a conventional "north bridge" chip that manages the bus connecting the CPU and the system memory. IGPs are appealing as an inexpensive alternative to graphics cards. Unlike conventional graphics cards, an IGP system usually does not include much (or in some cases any) dedicated graphics memory; instead the IGP relies on system memory, which the IGP can generally access at high speed. The IGP, however, generally does not control the physical arrangement or address mapping of the system memory allocated to it. For example, it is not guaranteed that the pixel buffer will occupy a single contiguous block in the physical address space. Thus, designers of IGPs are faced with the choice of redesigning the co-processor and the associated driver programs to use physical addresses provided by the system or relying on virtual addressing.

Given the level of complexity and sophistication of modern graphics processing, redesigning around (unpredictable) physical addresses is a daunting task, which makes a virtual addressing solution desirable. Unfortunately, in many computer systems, virtual addressing can introduce a significant degree of memory overhead, making this option too slow or resource intensive for graphics processing components such as display systems. For example, a typical display system provides a screen's worth of pixel data (e.g., 1280.times.1024 pixels at four bytes per pixel, for a total of over 5 MB per screen) from the pixel buffer to a display device at a constant screen refresh rate of about 70 Hz. Virtual address translation for this much data would introduce an additional latency that is potentially long and may be highly variable. Such long or variable delays in receiving pixel data from memory could result in incorrect (or black) pixels, or other undesirable artifacts. In addition, if address translation for scanout or other purposes requires a large number of page table accesses, performance of other system components may be adversely affected (e.g., due to congestion on the bus or in the system memory). Conventional address caching and translation lookaside buffer techniques do not alleviate the problem because it is difficult and expensive to provide an on-chip cache large enough to hold all the page addresses needed for scanout.

Another solution is to maintain a complete page table on the graphics chip, thereby allowing faster access times and/or less variability in latency. This solution, however, becomes impractical for large page table sizes. Still another solution divides the virtual address space into "large" and "small" sections, depending on whether the section is mapped to blocks of contiguous physical addresses that exceed a "large size" threshold of e.g., 32 or 64 KB. Pointers to the physical address blocks for "large" sections are stored on chip, while for "small" sections, a lookup in the complete page table is required to complete the translation. In some cases, the result of the most recent page table lookup for each of some number of translation clients can be stored and re-used until the client requests a virtual address on a different page. Such systems can reduce the number of page table accesses in some situations, but the ability to store only one result per client and the inability to share results can still lead to a large number of page table accesses.

Thus, an improved virtual memory system that reduces the number of page table accesses required to translate a group of virtual addresses would be desirable.

BRIEF SUMMARY OF THE INVENTION

Embodiments of the present invention provide systems and methods for managing a virtual memory space in which address translation information is provided using a translation data structure, referred to herein as a "cluster," that is associated with some range of virtual addresses; the cluster can be used to translate any virtual address in its range to a physical address. The sizes of the ranges mapped by different clusters may be different, and the size of the cluster data structure may be independent of its range size. Clusters may be stored in an address translation table that is indexed by virtual address so that, starting from any valid virtual address, the appropriate cluster for translating that address can be retrieved from the translation table.

According to one aspect of the present invention, a method is provided for managing a virtual memory space. A pool of physical addresses is provided. A request for a virtual memory allocation is received from a client. A plurality of clusters is created from the pool. Each cluster represents a number of physical addresses selected from the pool, and the respective numbers of physical addresses represented by different ones of the clusters correspond to different amounts of memory. The physical addresses represented by each cluster that is created are removed from the pool. For each of the clusters, a mapping is defined between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster. A reference to a mapped virtual address is returned to the client.

Clusters may be created from the pool in a variety of ways. In one embodiment, an attempt is made to create exactly one cluster that represents all of the physical addresses in the pool. In the event that the attempt is not successful, the pool is separated into two or more sub-pools, and an attempt is made to create exactly one cluster that represents all of the physical addresses in one of the two or more sub-pools.

In another embodiment, a target range size is set to a maximum range size, and an attempt is made to create a cluster that represents physical addresses corresponding to an amount of memory equal to the target range size. In the event that the attempt is unsuccessful, the target range size is set to a smaller value, and the attempt to create a cluster is repeated.

In still another embodiment, where each cluster includes references to two or more blocks of contiguous physical addresses, a candidate block is selected from the pool based on an order of physical addresses, the first candidate block having a first block size. An attempt is made to create a cluster that references the candidate block and at least one other block having the first block size. In the event that the attempt is unsuccessful, a portion of the candidate block is selected as a new candidate block, the new candidate block having a second block size, and an attempt is made to create a cluster that references the new candidate block and at least one other block having the second block size.

The following detailed description together with the accompanying drawings will provide a better understanding of the nature and advantages of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a computer system according to an embodiment of the present invention;

FIG. 2 is a block diagram of a computer system according to another embodiment of the present invention;

FIG. 3 illustrates a mapping from a cluster table to physical addresses according to an embodiment of the present invention;

FIGS. 4A-C are bit-field representations of cluster data structures according to embodiments of the present invention;

FIGS. 5A-B are flow diagrams of a process for translating a virtual address given a corresponding cluster according to an embodiment of the present invention;

FIG. 6 is a flow diagram of a process for managing a virtual address space according to an embodiment of the present invention;

FIG. 7 illustrates a fragmented pool of physical addresses according to an embodiment of the present invention;

FIG. 8 is a flow diagram of a first process for forming clusters from physical addresses according to an embodiment of the present invention;

FIG. 9 illustrates subpools that may be created during the process shown in FIG. 8;

FIG. 10 is a flow diagram of a second process for forming clusters from physical addresses according to an embodiment of the present invention;

FIGS. 11A-B illustrate clusters that may be created during the process shown in FIG. 10; and

FIG. 12 is a flow diagram of a third process for forming clusters from physical addresses according to an embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the present invention provide systems and methods for managing a virtual memory space in which address translation information is provided using a translation data structure, referred to herein as a "cluster," that is associated with some range of virtual addresses; the cluster can be used to translate any virtual address in its range to a physical address. The sizes of the ranges covered by (or mapped by) different clusters may be different, and in some embodiments, the size of the cluster data structure is independent of its range size. For example, in one embodiment, each cluster is 16 bytes and can map anywhere from 4 to 512 pages of the virtual address space. Clusters may be stored in an address translation table (e.g., in system memory) that is indexed by virtual address so that, starting from any valid virtual address, the appropriate cluster for translating that address can be retrieved from the translation table.

The present description is organized as follows: Section I describes examples of computer systems according to embodiments of the present invention; Section II describes a cluster table implementation of an address translation table according to one embodiment of the present invention; and Section III describes further embodiments of the invention. It is to be understood that all embodiments described herein are illustrative and not limiting of the scope of the invention.

I. COMPUTER SYSTEM OVERVIEW

FIG. 1 is a block diagram of a computer system 100 according to an embodiment of the present invention. Computer system 100 includes a central processing unit (CPU) 102 and a system memory 104 communicating via a bus 106. User input is received from one or more user input devices 108 (e.g., keyboard, mouse) coupled to bus 106. Visual output is provided on a pixel based display device 110 (e.g., a conventional CRT or LCD based monitor) operating under control of a graphics card 112 coupled to system bus 106. A system disk 128 and other components, such as one or more removable storage devices 129 (e.g., floppy disk drive, compact disk (CD) drive, and/or DVD drive), may also be coupled to system bus 106. System bus 106 may be implemented using one or more of various bus protocols including PCI (Peripheral Component Interconnect), AGP (Accelerated Graphics Port) and/or PCI Express (PCI-E); appropriate "bridge" chips such as a north bridge and south bridge (not shown) may be provided to interconnect various components and/or buses.

Graphics card 112 includes a graphics processing unit (GPU) 114, a graphics memory 116, a graphics translation lookaside buffer (GTLB) 142, and scanout control logic 120, which may be implemented, e.g., using one or more integrated circuit devices (including programmable processors and/or application specific integrated circuits (ASICs)). GPU 114 may be configured with one or more processing cores to perform various tasks, including generating pixel data from graphics data supplied via system bus 106, interacting with graphics memory 116 to store and update pixel data, and the like. Such elements of GPU 114 may be of generally conventional design, and a detailed description is omitted. Communication with graphics memory 116 is managed by GTLB 142.

Scanout control logic 120 reads pixel data from graphics memory 116 (or, in some embodiments, system memory 104) via GTLB 142 and transfers the data to display device 110 to be displayed. In one embodiment, scanout occurs at a constant refresh rate (e.g., 80 Hz); the refresh rate can be a user selectable parameter. Scanout control logic 120 may also perform other operations such as adjusting color values for particular display hardware; generating composite screen images by combining the pixel data with data for a video or cursor overlay image or the like obtained, e.g., from graphics memory 116, system memory 104, or another data source (not shown); converting digital pixel data to analog signals for the display device; and so on. It will be appreciated that the particular configuration of graphics card 112 or its components is not critical to the present invention.

During operation of system 100, CPU 102 executes various programs that are (temporarily) resident in system memory 104. In one embodiment, these programs include one or more operating system (OS) programs 132, one or more application programs 134, one or more driver programs 136 for graphics card 112, and a resource manager program 138 that provides various support services to driver program 136. It is to be understood that, although these programs are shown as residing in system memory 104, the invention is not limited to any particular mechanism for supplying program instructions for execution by CPU 102. For instance, at any given time some or all of the program instructions for any of these programs may be present within CPU 102 (e.g., in an on-chip instruction cache and/or various buffers and registers), in a page file or memory mapped file on system disk 128, and/or in other storage space.

Operating system programs 132 and/or application programs 134 may be of conventional design. An application program 134 may be, for instance, a video game program that generates graphics data and invokes appropriate rendering functions of GPU 114 to transform the graphics data to pixel data. Another application program 134 may generate pixel data and provide the pixel data to graphics card 112 for display. It is to be understood that any number of application programs that generate pixel and/or graphics data may be executing concurrently on CPU 102. Operating system programs 132 (e.g., the Graphical Device Interface (GDI) component of the Microsoft Windows operating system) may also generate pixel and/or graphics data to be processed by graphics card 112.

Driver program 136 enables communication with graphics card 112. Driver program 136 advantageously implements one or more standard application program interfaces (APIs), such as Open GL, Microsoft DirectX, or D3D for communication with graphics card 112; any number or combination of APIs may be supported, and in some embodiments separate driver programs 136 are provided to implement different APIs. By invoking appropriate API function calls, operating system programs 132 and/or application programs 134 are able to instruct driver program 136 to transfer graphics data or pixel data to graphics card 112 via system bus 106, to invoke various rendering functions of GPU 114, and so on. The specific commands and/or data transmitted to graphics card 112 by driver program 136 in response to an API function call may vary depending on the implementation of GPU 114, and driver program 136 may also transmit commands and/or data implementing additional functionality (e.g., special visual effects) not controlled by operating system programs 132 or application programs 134.

Resource manager 138 is advantageously provided to support interactions of driver program 136 with system hardware components such as system memory 104. Resource manager 138 implements low-level hardware- and operating-system-specific functionality that is used by driver program 136 in processing requests from operating system programs 132 and/or application programs 134. For example, resource manager 138 may handle tasks such as allocation and deallocation of system memory for driver program 136 and/or GPU 114. Providing resource manager 138 enables program code for driver program 136 to be written at a level of abstraction that hides details of the hardware and/or operating system on which driver program 136 is executed; thus, the same driver code can be adapted to different hardware configurations by providing a different implementation of resource manager 138. It will be appreciated that the functionality of resource manager 138 might also be implemented in driver program 136.

In system 100, GPU 114 can access system memory 104 by reference to virtual addresses, which are translated to physical addresses in order to fulfill the memory access request. An address translation table 140, shown as being resident in system memory 102, stores translation information that can be used to convert a given virtual address to the corresponding physical address. In accordance with an embodiment of the present invention, the translation information is advantageously stored in one or more clusters, where a cluster is a data structure that provides the translation information for a variable-size range of the virtual address space. Embodiments of cluster data structures and cluster tables that implement address translation table 140 are described in Section II below. Although address translation table 140 is shown as being resident in system memory 104, it may also be stored elsewhere, e.g., in graphics memory 116 or in GPU 114.

GTLB 142 receives memory requests from various "clients" executing in a processing core (not shown) of GPU 114 and/or from scanout control logic 120 and performs address translations in the course of responding to these requests. In response to a memory request that includes a virtual address (or in response to an address translation request that does not include a memory access request), GTLB 142 retrieves a cluster from address translation table 140 or from its own cache of recently used clusters and converts the virtual address to a physical address based on data contained in the cluster. GTLB 142 is advantageously implemented such that address translation can be made invisible to some or all clients; that is, a client can simply issue a memory access command referencing a virtual address and receive a response (including the data, in the case of a read command) from the appropriate physical memory system, without the client needing to be aware that any translation has occurred. Thus, existing driver programs and/or GPU-implemented algorithms can be used regardless of whether the memory being used is dedicated graphics memory 116 or system memory 104. In this embodiment, GTLB 142 also manages access by components of graphics processing subsystem 112 to system memory 104, graphics memory 116, and any other physical memory resource of system 100 that is accessible to graphics processing components. For each such resource, GTLB 142 performs the appropriate address translation; in some instances (e.g., for graphics memory 116), no translation may be required. In other embodiments, GTLB 142 manages only accesses to system memory 104; access to graphics memory 116 may be provided via an alternative path.

In the course of its operations, GTLB 142 may store copies of some or all of the clusters retrieved from address translation table 140 in its own cache (not shown), thereby facilitating the handling of subsequent requests for similar addresses. GTLB 142 may be implemented in various ways, examples of which are described in application Ser. No. 10/769,326, parent of the present application. GTLB 142 can be implemented in hardware resident on graphics card 112 (optionally integrated with GPU 114), in software executing on GPU 114 and/or CPU 102, or any combination thereof.

FIG. 2 is a block diagram of another computer system 200 according to another embodiment of the present invention. Computer system 200 includes a CPU 202 and system memory 204 communicating via a "north bridge" chip 206. North bridge chip 206 advantageously implements one or more high-speed bus protocols (these may be conventional protocols) that facilitate rapid communication between CPU 202 and system memory 204. North bridge chip 206 also communicates with a "south bridge" chip 207 that implements one or more bus protocols (which may be the same as or different from protocols used by north bridge chip 206) for connecting various peripheral devices, such as a user input device 208, a system disk 228, and a removable storage device 229. South bridge chip 207 and any peripheral devices may be of generally conventional design.

North bridge chip 206 includes an integrated graphics processor (IGP) 214 that implements graphics functionality similar to that of GPU 114 of system 100 (FIG. 1). For example, IGP 214 includes scanout control logic 220 that provides pixel data to a display device 210. (Scanout control logic 220 may be generally similar to scanout control logic 120 of FIG. 1.) IGP 214 also includes a GTLB 242 that manages access to system memory 204 for IGP 214 and its components, including scanout control logic 220.

Operation of system 200 is generally similar to operation of system 100 described above. For example, a graphics driver program, a resource manager program, application programs, and operating system programs (not shown) may be executed by CPU 202. In system 200, IGP 214 might not have access to a dedicated graphics memory area at all, although some embodiments may include at least a small amount of dedicated graphics memory. If IGP 214 does not have dedicated graphics memory, or if additional memory beyond the dedicated graphics memory is required, IGP 214 accesses system memory 204 by reference to virtual addresses that are translated to corresponding physical addresses. An address translation table 240 is provided for storing address translation data (e.g., clusters), and GTLB 242 performs the address translations. Address translation table 240 and GTLB 242 may be generally similar in design and operation to address translation table 140 and GTLB 142 of FIG. 1.

It will be appreciated that systems 100 and 200 are illustrative and that variations and modifications are possible. Arrangement of system components may be varied; for instance, in some embodiments, communication with system memory may be routed through the CPU. Some components may be duplicated or absent as desired. A graphics card may be implemented with any amount of on-card memory or with no dedicated graphics memory at all, and a GPU can use a combination of on-card memory and system memory in any manner desired. Where a graphics card has no on-card memory, the GPU may use system memory exclusively. An IGP can be provided with dedicated memory if desired and can use a combination of dedicated memory and system memory in any manner desired. A single computer system may include multiple graphics processors implemented using any combination of IGPs and/or GPUs. For example, a graphics card based on the AGP or PCI-E bus standard can be connected to north bridge chip 206 or south bridge chip 207 of FIG. 2, as is known in the art, and various control technologies can be provided for controlling operations of the multiple graphics processors. One or more graphics processors may also be implemented as a separate chip that mounts onto the motherboard of a computer system. In view of the present disclosure, persons of ordinary skill in the art will recognize that the present invention can be embodied in a wide variety of system configurations.

It will also be appreciated that, although the address translation techniques described herein are introduced in the context of graphics processing subsystems, these techniques may also be adapted for other computer system components that use virtual addressing. For example, an address translation table in accordance with an embodiment of the present invention may be implemented for other peripheral devices (e.g., disk drives), for virtual memory management by a CPU, and so on. Accordingly, where the following description refers to a "client," it is to be understood that the client may be any component of a computer system that accesses any memory resource by reference to a virtual address or that requests a translation of a virtual address.

In embodiments described herein, the physical memory resource is of generally conventional design. Physical memory is byte-addressable and is allocated by the operating system in fixed-size units (e.g., 4 KB) of physically adjacent memory locations; the fixed-size unit is a "page" in the physical address space. The physical address of a byte of memory is specified by a page address and a byte offset within the page. It is to be understood that a physical address may be expressed in various ways, including as a "linear address" that may be further converted to a hardware-dependent identifier of a particular storage location (e.g., row and column addresses for a memory cell array).

The number of bits in a physical address or page address is implementation dependent and may vary, e.g., according to the size of the physical address space for a particular system. By way of illustration, some examples herein refer to a 36-bit physical address space in which the 24 most significant bits (MSBs) of an address determine the page address and the 12 least significant bits (LSBs) correspond to the byte offset within a 4 KB page. Bit ranges within addresses are sometimes represented herein as a range of bits, e.g., [Addr.sub.35:Addr.sub.12] for the page address, and [Addr.sub.11:Addr.sub.0] for the byte offset. Those of ordinary skill in the art will recognize that other embodiments adapted to different implementations of physical memory (e.g., different page sizes, different sizes and organizations of physical address space, addressability in units other than bytes) and that the present invention is not limited to any particular memory system or physical address space.

II. CLUSTER TABLE

A cluster table that implements an address translation table according to an embodiment of the present invention will now be described. This cluster table, which can be resident in the main system memory (e.g., cluster table 140 of FIG. 1 or 240 of FIG. 2) or elsewhere in the system, provides data that can be used to translate virtual addresses to physical addresses. Like a conventional page table, an entry in the cluster table is accessed by reference to a virtual address. Unlike a conventional page table, the cluster table entry does not directly provide the address for the corresponding page of physical memory. Instead, each cluster table entry stores a data structure (called a cluster) that maps some range of the virtual address space to physical addresses. As will become apparent, the size of the range mapped by a cluster can vary, depending on how the physical memory is allocated; a single cluster can map an arbitrarily large range of virtual address space.

A. Cluster Table Structure

FIG. 3 is a conceptual illustration of a mapping from a cluster table to physical addresses according to an embodiment of the present invention. At the left is a cluster table 302, which contains a number of entries 304. (Herein, multiple instances of like objects are denoted with reference numbers identifying the object and parenthetical numbers identifying the instance where needed.) An entry 304 in cluster table 302 is accessed by reference to the virtual address index 306 shown at left; index 306 may be obtained for any given virtual address, e.g., by aligning that virtual address at a 16K boundary. For example, a virtual address of 86K would align to an index 306 value of 80K, which corresponds to entry 304(6). In some embodiments, determining the virtual address index from a virtual address includes additional manipulations, such as dividing by 1024, so that the index can be used as an offset relative to a base address of the cluster table in system memory. Such manipulations are known in the art.

Each entry 304 stores a cluster (represented as CLUS n, where n=0, 1, 2, . . . ), and the same cluster can be stored in multiple entries (e.g., CLUS 0 is stored in each of entries 304(1)-304(4)). In this embodiment, each cluster is a fixed-size data structure (e.g., 16 bytes) that can map a variable range of the virtual address space to corresponding physical addresses; it is to be understood that in other embodiments, different clusters may have different sizes. The mapping is provided by address translation data in the cluster. The address translation data generally includes a starting address for a block of contiguous addresses (e.g., page addresses) in the physical address space, and sequential virtual addresses in the cluster's range are mapped to sequential physical addresses in the block. In some embodiments, clusters may include starting addresses for more than one block; sequential virtual addresses can be mapped to sequential physical addresses in the first block until the first block is exhausted, then to sequential physical addresses in the second block, and so on for any number of blocks.

FIG. 3 also illustrates how clusters CLUS 0-CLUS 4 of cluster table 302 might map to a physical address space 316. Physical address space 316 includes a number of blocks 314, where each block 314 is a contiguous range of physical addresses and is mapped to a contiguous range of virtual addresses. Each block is also labeled with its size (in KB). In this example, each cluster CLUS n provides mappings via pointers to four blocks 314. (Examples of encoding such pointers into a cluster data structure are described below.) The four blocks 314 pointed to by a particular cluster CLUS n are all the same size (e.g., CLUS 0 points to four blocks 314(4), 314(9), 314(11), 314(17) that are 16 KB each), but there is no necessary relationship between the locations of the four blocks. In addition, blocks pointed to by different clusters may be of different sizes (e.g., CLUS 0 points to 16-KB blocks 314(4), 314(9), 314(11), 314(17) while CLUS 1 points to 8-KB blocks 314(6), 314(7), 314(15), 314(20)). The block size for each cluster is determined when that cluster is created, as described in Section II.D below. In general, block size is affected by the degree of fragmentation present in the physical memory. In other embodiments, one cluster may point to blocks of different sizes; in still other embodiments, some relationship (e.g., locality) between the addresses of blocks pointed to by a cluster may be required.

Each entry 304 in cluster table 302 may be regarded as a "virtual block" in the virtual address space. All virtual addresses within the address range of a virtual block are guaranteed to be mapped to physical addresses by the cluster stored in that entry; e.g., all addresses in the 80-96 KB range corresponding to entry 304(6) are mapped by CLUS 1. It is to be understood that the virtual block size need not correspond to a physical page size of the physical address space; e.g., each virtual block (i.e., entry) in cluster table 302 covers four 4-KB physical pages. It should also be noted that some clusters might map virtual addresses for more than one virtual block; e.g., CLUS 1 is also stored in entry 304(5) and therefore also maps virtual addresses in the 64-80 KB virtual block. Thus, the "range" of a cluster (i.e., the set of all virtual addresses mapped by that cluster) may include any number of virtual blocks.

To the extent that an entry 304 may be regarded as a virtual block, the index 306 used to find the cluster for that entry may be regarded as a virtual block address. For instance, in cluster table 302, a virtual address (e.g., vAddr=86 KB) can be translated by first identifying the virtual block to which it belongs, i.e., the corresponding index 306 (e.g., 80 KB, or in some embodiments 80). Using the index 306, a cluster (e.g., CLUS 1) for the virtual block (e.g., entry 304(6)) is obtained from cluster table 302, and a translation operation is performed on the cluster to obtain the physical address, which in this example would be in one of physical blocks 314(6), 314(7), 314(15), 314(20). It should be noted that in this embodiment, prior knowledge of the size of the virtual address range mapped by a cluster is not required to obtain the correct cluster. Thus, no more than one access to cluster table 302 is required to translate any virtual address.

Given a cluster, the translation operation for a virtual address mapped by that cluster depends on the particular cluster structure used in a given embodiment. Examples of cluster structures and associated translation operations will now be described; it will be appreciated that these structures and operations are illustrative and not restrictive of the scope of the invention.

B. Cluster Structure Examples

FIGS. 4A-B are bit-field representations of two cluster data structures according to embodiments of the present invention. FIG. 4A shows bit fields of a four-block cluster 400 (which may be stored as clusters CLUS n in cluster table 302 of FIG. 3), and FIG. 4B shows bit fields of an eight-block cluster 450 that may be stored in the same cluster table with four-block clusters 400 of FIG. 4A.

Turning first to FIG. 4A, four-block cluster 400 is a 16-byte (128-bit) data structure for mapping part of a 36-bit physical address space. Cluster 400 provides physical addresses for the respective starting locations of each of four blocks, which may be located anywhere in the physical address space. Blocks of varying sizes can be mapped by cluster 400, although each of the four mapped blocks has the same size.

In this embodiment, cluster 400 includes a 3-bit size index 402. Size index 402 encodes the size of each of the four blocks mapped by the cluster. Eight block sizes are supported, from a minimum size of 4 KB (one page) up to a maximum size of 512 KB (128 pages). Since the total amount of memory mapped by cluster 400 (referred to herein as the "range size") is four times the block size, size index 402 also encodes the range size, which varies from 16 KB (four one-page blocks) to 2048 KB (four 128-page blocks). Block sizes and range sizes corresponding to each value of size index 402 for cluster 400 are summarized in Table 1. It will be appreciated that other block or range sizes, including larger sizes, could be supported if desired, e.g., by expanding size index 402 to a larger number of bits.

TABLE-US-00001 TABLE 1 Size index Block Size (KB) Range Size (KB) 0 4 16 1 8 32 2 16 64 3 32 128 4 64 256 5 128 512 6 256 1024 7 512 2048

Format field 404 comprises one bit. In this embodiment, the bit is set to "0" for a four-block cluster. As will be seen below, format field 404 allows four-block clusters 400 and eight-block clusters 450 to co-exist in the same cluster table. In other embodiments, more than two formats can be supported, and format field 404 may contain additional bits so that each format has a unique identifier. In still other embodiments, only one cluster format is supported, and format field 404 may be omitted.

Valid field 406 also comprises one bit, which is set to "1" (or logical True) if the cluster contains valid block addresses and to "0" (or logical False) otherwise. For example, when the system is initialized, before any memory is mapped to virtual addresses, the cluster table would be filled with clusters with a valid bit of "0." As memory is mapped, the valid bit is changed for the appropriate clusters. When a cluster is accessed, its valid bit can be checked and any requests that return invalid clusters can be flagged.

Cluster 400 also includes four 24-bit "block pointer" fields 410. Each block pointer field 410 stores the page address (e.g., physical address or pointer) of the first page in one of the four blocks of physical address space mapped by cluster 400. Each page address is advantageously stored as a page index (e.g., without the 12 LSBs that correspond to byte offset within a page). The block pointers are advantageously arranged so that the lowest virtual addresses mapped by cluster 400 correspond to block pointer 410(0), the next virtual addresses correspond to block pointer 410(1), and so on. Accordingly, if a requested virtual address is in the first quarter of the range mapped by cluster 400, block pointer 410(0) is used to obtain the physical address; if the requested virtual address is in the second quarter, then block pointer 410(1) is used; and so on. It should be noted that the block pointers need not be arranged in order of physical address.

As an example, in cluster table 302 of FIG. 3, entry 304(1) stores a cluster CLUS 0, which may be an instance of cluster 400. In this example, block pointer 410(0) would store the starting address for block 314(4), block pointer 410(1) would store the starting address for block 314(9), block pointer 410(2) would store the starting address for block 314(11), and block pointer 410(3) would store the starting address for block 314(17).

For an invalid cluster, valid field 406 is set to logical false, and each block pointer field 410 is advantageously set to reference a "bit bucket" page in the system memory. As is known in the art, a bit bucket is an area of system memory that is guaranteed not to be used for storing meaningful data and therefore is a safe target for invalid (or null) pointers. When block pointer fields 410 of invalid clusters are set to reference a bit bucket page, any memory access operations that reference (by virtual address) an invalid cluster can be processed normally without affecting any data.

The remaining pad fields 420-424 include a total of 27 bits, bringing the size of cluster 400 to 16 bytes. Any number of pad fields can be arranged as desired within cluster 400. In this embodiment, pad fields 420-424 are not used to share cluster information, but other embodiments may use some or all of these bits (e.g., if more than 24 bits are needed for each block pointer 410).

Turning now to FIG. 4B, eight-block cluster 450 is also a 16-byte (128-bit) data structure for mapping part of a 36-bit physical address space. Cluster 450 provides physical addresses for the respective starting locations of each of eight blocks. The eight-block cluster allows a larger number of mappings (eight rather than four) to be stored in a single cluster although, as will be seen, the physical addresses of each of the eight blocks are required to have some number of MSBs in common. (Where this is not the case, two four-block clusters 400 can be used instead.)

In this embodiment, cluster 450 includes a three-bit size index 452. Like size index 402 of cluster 400, size index 452 encodes the size of each of the blocks mapped by the cluster 450, as well as the range size (which in the case of an eight-block cluster is eight times the block size). Block sizes and range sizes for size index 452 are summarized in Table 2. It will be appreciated that other block sizes or range sizes, including larger sizes, could also be supported, and that size index 452 may be modified to include the appropriate number of bits.

TABLE-US-00002 TABLE 2 Size field Block Size (KB) Range Size (KB) 1 4 32 2 8 64 3 16 128 4 32 256 5 64 512 6 128 1024 7 256 2048

Comparing Table 2 with Table 1, it will be apparent that size indices 402 and 452 are defined such that a given value of size index 402 or 452 corresponds to the same range size, regardless of whether the cluster is a four-block cluster 400 or an eight-block cluster 450. (Thus, for eight-block clusters, a size index value of zero is not used.) In embodiments where four-block clusters 400 and eight-block clusters 450 co-exist, this size-index definition allows the range size of a cluster to be readily determined without knowing whether the cluster is a four-block or eight-block cluster. Other definitions may also be used, and a particular size index value in eight-block cluster 450 need not correspond to any particular size index value in four-block cluster 400.

In eight-block cluster 450, format field 454 comprises one bit, which is set to "1" to distinguish eight-block cluster 450 from four-block cluster 400. Thus, a cluster table can store any combination of four-block and eight-block clusters, and the format field (advantageously placed at the same bit position for both cluster types) can be used to determine whether a particular cluster is a four-block or eight-block cluster.

Unlike four-block cluster 400, eight-block cluster 450 does not include a valid field, and eight-block clusters 450 are presumed valid. Eight-block cluster 450 may be invalidated by setting format field