Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2001-07-26
2003-11-25
Verbrugge, Kevin (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S203000
Reexamination Certificate
active
06654859
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to memory page selection in a multiprocessor computing environment. More specifically, the invention implements a selection policy based upon both nodal identification and page color.
2. Description of the Prior Art
Multiprocessor systems contain multiple processors (also referred to herein as “CPUs”) that can execute multiple processes or multiple threads within a single process simultaneously in a manner known as parallel computing. In general, multiprocessor systems execute multiple processes or threads faster than conventional single processor systems, such as personal computers, that execute only one thread at a time. The actual performance advantage is a function of a number of factors, including the degree to which parts of a multithreaded process and/or multiple distinct processes can be executed in parallel and the architecture of the particular multiprocessor system. The degree to which processes can be executed in parallel depends, in part, on the extent to which they compete for exclusive access to shared memory resources.
Shared memory multiprocessor systems offer a common physical memory address space that all processors can access. Multiple processes therein, or multiple threads within a process, can communicate through shared variables in memory in which all the processes read or write to the same memory location in the computer system. Message passing multiprocessor systems, in contrast to shared memory system, have a separate memory space for each processor. They require processes to communicate through explicit messages to each other.
The architecture of shared memory multiprocessor systems may be classified by how their memory is physically organized. In distributed shared memory (DSM) machines, the memory is divided into modules physically placed near one or more processors. Although all of the memory modules are globally accessible, a processor can access local memory on its node faster than remote memory on other nodes. Because the memory access time differs based on memory location, such systems are also called non-uniform memory access (NUMA) machines. In symmetrical shared memory machines, on the other hand, the memory is physically in one location. Symmetrical shared memory computers are called uniform memory access (UMA) machines because the memory is equidistant in time for each of the processors. Both forms of memory organization typically use high-speed caches in conjunction with main memory to reduce execution time.
For systems with a physically indexed cache, operating systems may utilize a page color scheme to identify pages of memory and their physical placement in the cache, thereby increasing the average cache hit rate. The page color scheme allows the operating system to work with physically indexed caches to commit pages that have good processor cache utilization properties. Page coloring uses the operating system, or resource control software, to control the mapping of virtual addresses to physical addresses by controlling the physical memory page to which virtual pages are allocated. In the case of physically indexed caches, the lower address bits in a page address is used as a cache index. Accordingly, the operating system commits real physical memory pages according to how they layout in the cache.
The prior art page coloring method functions well in a UMA computer system and provides good processor cache utilization properties. However, this method does not provide efficient results in a NUMA system. Specifically, the prior art page coloring method selects pages that have an inverse probability of being on the same node as the current processor in a NUMA system, as well as being on the same node as previous or future allocations. Accordingly, it is desirable to develop a page coloring method for use in a NUMA operating environment which overcomes the limitation of the prior art.
SUMMARY OF THE INVENTION
This invention comprises a method for selecting physical pages of memory in multiprocessing computer environment. The page selection process enables the operating system or other resource controlling software to request memory pages for a specified process, or other scheduled entity, on a specified node wherein the selected pages have good processor cache distribution.
A first aspect of the invention is a method of increasing application performance in a multiprocessor computer system. Intra-nodal page allocations are increased and processor cache utilization is increased. Each physical page of memory is identified according to a nodal page color. In addition, each page of memory is organized into a data structure based upon the nodal page color. For each process a preferred node is selected, as well as a preferred page color. Processor cache utilization is increased by incrementing the page color for a subsequent page allocation. The preferred page color is updated during the subsequent page allocation.
A second aspect of the invention is a multiprocessor computer system including a memory manager to increase intra-nodal page allocations and a process manager to increase cache utilization. The memory manager identifies each physical page of memory according to a nodal page color and organizes each physical memory page into a data structure according to the nodal page color. Thereafter, the process manager selects a preferred node for the process. Following the selection of a preferred node, the process manager selects a preferred page color for the process. The process manager increments the page color for a subsequent page allocation, and updates the preferred page color during the subsequent page allocation:
A third aspect of the invention is an article comprising a computer-readable signal bearing medium with multiple processors operating within the medium. The article includes means in the medium for increasing intra-nodal page allocations, and means in the medium for increasing processor cache utilization. The means for increasing intra-nodal page allocations includes a memory manager to identify a page of memory according to a nodal page color. The memory manager organizes the pages of memory into a data structure based upon the nodal page color. In addition, the means for increasing intra-nodal page allocations includes a process manager to select a preferred node for a process and a preferred page color. The means for increasing processor cache utilization includes a process manager to increment the page color for a subsequent page allocation, and to update the preferred page color during the subsequent page allocation.
Other features and advantages of this invention will become apparent from the following detailed description of the presently preferred embodiment of the invention, taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5860095 (1999-01-01), Iacobovici et al.
patent: 5913222 (1999-06-01), Liedtke
patent: 6009503 (1999-12-01), Liedtke
patent: 6112286 (2000-08-01), Schimmel et al.
patent: 6167437 (2000-12-01), Stevens et al.
patent: 6347364 (2002-02-01), Liedtke
patent: 6370622 (2002-04-01), Chiou et al.
patent: 6381735 (2002-04-01), Hunt
patent: 2002/0072830 (2002-06-01), Hunt
US 6,021,479, 2/2000, Stevens (withdrawn)
Nagar, “Windows NT File Systems Internals: A Developer's Guide”, O'Reilly & Associates, Inc., 1997, pp. 194-242.
Lynch, “Page Coloring”, Research In Computer Architecture by Michael J. Flynn, Dec. 1994.
Lieberman Rochelle
Verbrugge Kevin
LandOfFree
NUMA page selection using coloring does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with NUMA page selection using coloring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NUMA page selection using coloring will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3184665