Digital Equipment Corporation

Kenneth D Abramson

David A Orbits

H Bruce Butts, Jr

A computer system executing virtual memory management and having a cache is operated in a manner to reduce cache misses by remapping pages of physical memory from which cache misses are detected. The method includes detecting cache misses, as by observing cache fill operations on the system bus, and then remapping the pages in the main memory which contain the addresses of the most frequent cache misses, so that memory references causing thrashing can then coexist in different pages of the cache. For a CPU executing a virtual memory operating system, a page of data or instructions can be moved to a different physical page frame but remain at the same virtual address, by simply updating the page-mapping tables to reflect the new physical location of the page, and copying the data from the old page frame to the new one. The primary feature of the invention is to add bus activity sampling logic to the CPU and enhance the operating system to allow the operating system to detect when cache thrashing is occurring and remap data pages to new physical memory locations to eliminate the cache thrashing situation.

Enhanced cache operation with remapping of pages for optimizing data

A method of scheduling processes on a symmetric multiprocessing system that maintains process-to-CPU affinity without introducing excessive idle time is disclosed. When a new process is assigned, the process is identified as young and small, given a migtick value and assigned to a specific CPU. If the priority of a process placed on a run queue is above a threshold, the high priority count of the assigned CPU is incremented. At predetermined clock intervals, an interrupt occurs that causes the migtick value of running processes to be decremented. Then each CPU is tested to determine if its high priority count is greater than zero. CPUs having high priority counts greater than zero are tested to determine if any processes having a priority greater than the priority of the running process are assigned. If higher priority processes are assigned to a CPU having assigned processes lying above the threshold, a context switch takes place that results in the higher priority process being run. At regular intervals, a migration deamon is run to load balance the multiprocessor system. First, a large/small process threshold is determined. Then processes whose migtick values are below a migtick threshold (e.g., 0) are identified as old. Old processes then are identified as large or small processes based on their memory usage. Next, a determination is made of whether the small and large process load balances of the system can be improved. If either or both can be improved, the smallest small and/or the smallest large processes are migrated from their assigned CPU to the CPU with, as the case may be, the least large or the least small processes.

Affinity scheduling of processes on symmetric multiprocessing systems

A coherent coupled memory multiprocessor computer system that includes a plurality of processor modules (11a, 11b . . . ), a global interconnect (13), an optional global memory (15) and an input/output subsystem (17,19) is disclosed. Each processor module (11a, 11b . . . ) includes: a processor (21); cache memory (23); cache memory controller logic (22); coupled memory (25); coupled memory control logic (24); and a global interconnect interface (27). Coupled memory (25) associated with a specific processor (21), like global memory (15), is available to other processors (21). Coherency between data stored in coupled (or global) memory and similar data replicated in cache memory is maintained by either a write-through or a write-back cache coherency management protocol. The selected protocol is implemented in hardware, i.e., logic, form, preferably incorporated in the coupled memory control logic (24) and in the cache memory controller logic (22). In the write-through protocol, processor writes are propagated directly to coupled memory while invalidating corresponding data in cache memory. In contrast, the write-back protocol allows data owned by a cache to be continuously updated until requested by another processor, at which time the coupled memory is updated and other cache blocks containing the same data are invalidated.

Coupled memory multiprocessor computer system including cache coherency

An adaptive memory management method for coupled memory multiprocessor computer systems is disclosed. In a coupled memory multiprocessor system all the data and stack pages of processes assigned to individual multiprocessors are, preferably, located in a memory region coupled to the assigned processor. When this becomes impossible, some data and stack pages are assigned to global memory or memory regions coupled to other processors. The present invention is a method of making certain that the most referenced data and stack pages are located in the coupled memory of the processor to which a specific process is assigned and lesser referenced pages are located in global memory or the coupled memory region of other processors. This result is accomplished by sampling the memory references made by the processors of the computer system and causing the most recently referenced pages in each coupled memory region to be maintained at the head of an active page list. References to remote data and stack pages are stored in a remote page hash table. Remote pages are pages stored in global memory or in coupled memory other than the coupled memory of the processor to which the process owning the pages is assigned. Any remote data and stack pages referenced more frequently than pages stored in a processor's coupled memory region are transferred to the processor's coupled memory region. If a processor's coupled memory region is tight, pages are transferred from the processor's coupled memory region to global memory or to the coupled memory region of another processor.

Adaptive memory management method for coupled memory multiprocessor

A method of managing the memory of a CM multiprocessor computer system is disclosed. A CM multiprocessor computer system includes: a plurality of CPU modules 11a . . . 11n to which processes are assigned; one or more optional global memories 13a . . . 13n; a storage medium 15a, 15b . . . 15n; and a global interconnect 12. Each of the CPU modules 11a . . . 11n includes a processor 21 and a coupled memory 23 accessible by the local processor without using the global interconnect 12. Processors have access to remote coupled memory regions via the global interconnect 12. Memory is managed by transferring, from said storage medium, the data and stack pages of a process to be run to the coupled memory region of the CPU module to which the process is assigned, when the pages are called for by the process. Other pages are transferred to global memory, if available. At prescribed intervals, the free memory of each coupled memory region and global memory is evaluated to determine if it is below a threshold. If below the threshold, a predetermined number of pages of the memory region are scanned. Infrequently used pages are placed on the end of a list of pages that can be replaced with pages stored in the storage medium. Pages associated with processes that are terminating are placed at the head of the list of replacement pages.

Growing community of inventors

Seattle, WA, United States of America

Kenneth D Abramson