KR20040053153A - Method and apparatus for dispatching tasks in a non-uniform memory access (numa) computer system - Google Patents

Abstract

The dispatcher for a non-uniform memory access computer system dispatches threads from a common ready queue that is not associated with any CPU 201-204, but prefers to dispatch threads to CPUs with shorter memory access times. do. Preferably the system comprises a plurality of discrete nodes 101-104, each node having a local memory 205 and one or more CPUs. System main memory is distributed memory that includes a collection of local memory. Individual and preferred CPUs and preferred nodes can be associated with each thread. When the CPU is enabled, this dispatcher gives at least some relative priority (714-717; 801-804) to the thread having the desired CPU of the same node as the valid CPU with respect to the thread having the desired CPU at different nodes. . This preference is relative and does not prevent the dispatcher from overriding the preference to avoid lack or other problems.

Description

TECHNICAL AND APPARATUS FOR DISPATCHING TASKS IN A NON-UNIFORM MEMORY ACCESS (NUMA) COMPUTER SYSTEM}

Modern computer systems generally include a central processing unit (CPU) and supporting hardware for storing, retrieving, and transmitting information, such as communication buses and memories. The computer system also includes hardware necessary for communicating with the outside, such as an input / output controller or storage controller, and various devices such as keyboards, monitors, tape drives, communication lines coupled with a network, and the like. The CPU is the heart of this system. The CPU includes one computer program and executes instructions for instructing operation of other system elements.

From the computer's hardware point of view, most systems basically work the same way. Processors can perform a limited set of very simple operations, such as mathematical and logical comparisons and moving data from one place to another. However, each operation is executed very quickly. Programs that cause a computer to perform many of these simple operations give the illusion that the computer will perform sophisticated tasks. It is possible to allow the user to perceive the new, improved performance of the computer, in essence, by performing the same set of very simple operations, but by performing very quickly. Therefore, continuous improvement of computer systems requires these systems to be faster.

The overall speed (also called throughput) of a computer system is measured as is the number of operations performed per unit time as is. Conceptually, the simplest of all possible improvements in system speed is to increase the clock speed of various components, in particular to increase the clock speed of the processor. For example, if everything is executed correctly at high speed, but in the same way twice, significant speed improvements will be possible by reducing the element size, reducing the number of elements, and ultimately packaging the entire processor as an integrated circuit on a single chip. will be. Due to the reduction in size, it is possible to increase the clock speed of the processor and thus increase the system speed.

Despite the significant improvements obtained from integrated circuits, there is a continuing need for very fast computer systems. Hardware developers have gained significant improvements in speed with more advanced integration (in other words, increasing the number of circuits packaged on a single chip), reducing the size of the circuit, and various other technologies. However, developers know that the reduction in physical size cannot continue vaguely, and there is a limit to the ability to increase the clock speed of the processor. Therefore, attention is drawn to the need for a different approach for significant improvements in the throughput of computer systems.

It is possible to improve the throughput of the system by using a plurality of processors without changing the clock speed. Packaging each processor on an integrated circuit chip at a reasonable cost has been this practical approach. However, increasing the processor from one to two does not simply double the system's throughput. The introduction of multiple processors into the system has created a number of architectural problems. For example, multiple processors typically share the same main memory (although each processor has its own cache). Therefore, there is a need to devise a mechanism to prevent memory access conflicts and to ensure that extra copies of data in the cache are tracked in a consistent format. Furthermore, each processor places additional demands on other elements of the system, such as storage, I / O, memory, and especially the communication bus that connects the various elements. As more processors are being introduced, this architectural problem is becoming increasingly complex, versatility becomes more difficult, and it is more likely that processors will spend significant time waiting for any resources used by another processor. System developers are aware of all these issues, and these issues have been raised in one or another form. There is no perfect solution, but improvements in this area have continued.

One architectural approach that has recently emerged is the design of a computer system with discrete nodes of memory associated with a processor, also known as a distributed shared memory computer system or non-uniform memory access (NUMA). In a conventional symmetrical multi-processor system, the main memory is designed as a single large data storage body, which is equally accessible to all CPUs in the system. NUMA systems approach this problem by dividing the main memory into discrete subsets, each subset being physically associated with each CPU or each set of CPUs in general. Subsets of memory, associated CPUs and other hardware are often referred to as "nodes." One node typically has an internal memory bus that provides direct access from the CPU to local memory inside the node. Slower, indirect mechanisms exist to access memory across node boundaries. Therefore, if any CPU still accesses any arbitrary memory location, the CPU can access its own node's address faster than it can access an address outside that node (so, non-uniform). Memory access). By limiting the number of devices on a node's internal memory bus, bus arbitration mechanisms and bus traffic can be maintained at manageable levels even in systems with multiple CPUs, where most of these CPUs are different nodes. Because it is within. From a hardware point of view, this means that the NUMA system architecture has the potential benefit of increased versatility.

NUMA systems provide inter-node access, which has a single logical main memory, and each main memory location has a unique address. In order for a NUMA system to work efficiently, the data needed by the CPU should generally be stored in real memory on the same node. It is impractical to ensure that this is always the case without imposing excessively strict restrictions. A memory allocation mechanism that reduces the need for inter-node memory access is desirable.

Multitasking System In a computer system, the operating system generally manages the allocation of any system resources, and in particular dispatches tasks (or threads) to the CPU and allocates memory. In such a system, a plurality of threads are activated at the same time. Normally, the number of active threads exceeds the number of CPUs inside the system. A given thread generally runs within the CPU for a certain number of cycles, and then, although not completed, is temporarily suspended and placed in a queue to continue execution later. A thread may hang because a thread has reached a time limit, has been emptied by a higher priority thread, has to wait for some wait time, such as a store access or lock release, or for some other reason. By allowing another thread to run while the first thread is waiting, CPU resources are more fully utilized. If the CPU is to be able to run a thread for this or other reason, the dispatcher in the operating system generally determines which of the plurality of waiting threads will be dispatched to the CPU valid for execution.

Conventional dispatchers are usually designed for symmetric multiprocessor computer systems, where the memory in the system can equally access all CPUs, but cannot optimally take into account the effects of non-uniform memory access on task dispatching. For example, within the dispatcher used by the Microsoft Windows 2000 ^™ operating system, threads are selected for dispatch according to various considerations. These considerations include pre-assinged priority, length of queue time, whether the thread is running continuously on the same CPU, whether the CPU is the preferred processor indicated for the thread, and so on. These factors are intended to optimize the utilization of the normally targeted CPU. However, the dispatcher does not consider the node location of the CPU, and although the CPUs can be used to a high degree, the system workload is degraded as a result of unnecessary memory access of many inter-nodes. Some dispatchers may impose strict limits on the allocation of threads or jobs to CPUs so that certain threads always run within the same CPU or the same node. A logical partition of a computer system in which resources are divided into discrete subsets and processes are allocated to each subset can achieve a similar effect. In some examples, these effects are intended (eg, one group of processes guarantees a certain amount of resources without interference from another process). However, this can lead to bottlenecks that are under-using some CPUs or over-using the CPUs.

One known operating system designed for the NUMA platform is the PTX operating system of SeQuent Computer (currently a division of IBM). PTX provides a plurality of run queues, one for each CPU, and allows the user to define additional run queues for any group of CPUs. When a process is initialized, it is assigned to any of the drive queues, and all threads created by the process are placed in that drive queue while waiting for execution. The operating system then preferentially dispatches the threads of this process to the CPU or CPUs of the assigned drive queue, and at a somewhat lower priority level, within the same system node as the CPU (or CPUs) of the allocated drive queue. Dispatch to the CPUs. The operating system further includes the ability to monitor CPU usage for each CPU and memory usage for each node on-going. If the CPU usage and / or memory usage at a particular node is high enough, the operating system dispatches one thread to nodes other than the node containing the preferred CPU or CPUs. In this way, PTX uses the NUMA architecture, but avoids strict limitations on thread dispatching that can make a big difference in resource usage.

While not required, there is a need for an improved dispatcher for NUMA systems, which has the significant advantage of PTX considering node location of various CPUs when dispatching threads, and therefore inter-nodes. While reducing the frequency of memory accesses, it can be applied to simpler operating systems, especially those that do not support monitoring of multiple drive queues and CPU / memory usage.

TECHNICAL FIELD The present invention relates to a multi-tasking computer system, and more particularly, to a task or thread that is dispatched within a system having a plurality of central processing units and non-uniform memory access.

1 is a high-level block diagram of the main elements of a multi-node, multiprocessor computer system, in accordance with a preferred embodiment of the present invention.

2 is a block diagram of the major hardware elements of a typical node of a multi-node computer system, according to a preferred embodiment.

3 is a conceptual explanatory diagram showing the division of hardware and software functions at different levels of abstraction within a multi-node computer system according to a preferred embodiment 100.

4 depicts a ready queue structure of a thread waiting for a valid processor to be used by the dispatcher, according to a preferred embodiment.

5 illustrates any thread-specific information from the ready queue used by the dispatcher, according to a preferred embodiment.

6 is a high-level flow chart showing the initialization of any thread control value, according to a preferred embodiment.

7A and 7B are alternative flow diagrams illustrating the selection of threads to be executed, according to a preferred embodiment.

8 is a flow chart showing CPU selection for executing a new prepare thread, according to a preferred embodiment.

According to the present invention, a dispatcher for a non-uniform memory access computer system dispatches all threads from a single common ready queue (also known as a run queue), which queue is any CPU or CPU group. Transition is not primarily related. When the dispatcher preferentially dispatches a thread to a CPU that has a shorter memory access time to access a subset of memory that is more likely to contain a relatively large amount of data that the thread needs, the dispatcher is the physical Consider the location.

In a preferred embodiment, a NUMA system is designed as a system of a plurality of discrete nodes, each having local memory, one or more CPUs, an internal node bus, and an interface for inter-node communication. System main memory is distributed memory that includes an association of local memories to each node. Memory access to locations within a processor node is faster than memory access across node boundaries.

In one preferred embodiment, each preferred CPU is associated with each thread. When the CPU is enabled, the dispatcher gives at least a certain relative priority to one thread having the preferred CPU in the same node as the valid CPU with respect to the thread having the preferred CPU of the different node. This is a relative priority, not an absolute limitation. It is still possible to select a thread for dispatch to a CPU that is not on the same node as the thread's desired CPU, thus avoiding starvation or other problems that can arise by restricting this thread dispatching choice too strictly. Can be. In one preferred embodiment, a preferred node, referred to as an "ideal node," is generally assigned to a user process. When a process creates a thread, that thread inherits this ideal node of the process. In addition, the CPU in the ideal node is chosen as the "ideal processor" for the thread. The selection of the ideal processor for a thread created by a single process generally rotates on a round-robin basis. If the other selection criteria are the same, the thread is dispatched first to the ideal processor and second to the ideal node. Under certain circumstances, the dispatcher may choose an idle processor rather than dispatch threads with different ideal nodes, but in other environments it may dispatch such threads.

Various alternative dispatching techniques are possible that account for non-uniform memory access. Optionally, if the CPU is available, the dispatcher gives at least some relative priority to the recently executed thread on the CPU of the same node as the valid CPU for the recently executed thread on a different node.

The use of a single common ready queue for all threads is consistent with various non-NUMA operating systems, regardless of any particular CPU or group of CPUs. By maintaining the relative priority of dispatching a thread to the same node according to the embodiment of the present invention described herein, the thread is likely to run on the same node, and the ideal memory of the node has a large amount of sharing proportional to the data needed by this thread. It is easy to accumulate. As a result, the frequency of the inter-node memory access is reduced than the frequency of the system, which does not consider the position of the node when dispatching threads. At the same time, strict node limitations are avoided, the entire system can be used, and deprivation and other problems can be avoided.

Other aspects and advantages of the invention will become more apparent from the following detailed description of the preferred embodiment of the invention, in conjunction with the drawings.

<Overview>

As described herein, the dispatcher for a multiprocessor, non-uniform memory access (NUMA) computer system dispatches threads for a single, broadly ready queue, and in selecting threads or tasks for dispatch to various processors. Given the similarity of nodes, each thread is likely to run on a consistent node, and the memory pages that a thread needs are likely to accumulate in that node's local real memory. For consistency, the term "thread" is used herein to be described as an example of a computer executable instruction sequence having a unique state, which is the entity dispatched by the dispatcher. In some circumstances, this is referred to as a "task", where "thread" and "task" are not distinguished. The term "thread" is used to mean that a process creates a plurality of threads that are currently executable from a single program; However, here, not so limitedly used, a process may generate only a single thread of execution or a plurality of threads.

<NUMA System Hardware>

1 is a high-level block diagram of the major hardware elements of a multi-node, multiprocessor computer system 100 in accordance with a preferred embodiment of the present invention. Computer system 100 uses a computer architecture based on Distributed Shared Memory (DSM), which is a NUMA system. Computer system 100 includes a plurality of nodes 101-104 described illustratively (four) in FIG. 1, the number of nodes being variable. This node is connected by an inter-node communication network 105 that allows communication with other nodes. The purpose of an inter-node communication network is to allow devices to communicate across node boundaries, and in particular to allow processors within any node to access memory residing on another node. In a preferred embodiment, inter-node network 105 is a switch based network. A switch-based network that uses the Scalable Coherent Interface (SCI) interconnect mechanism that conforms to the IEEE 1596-1992 standard. SCI is a high bandwidth interconnect network implemented by a pump bus that transmits packets on each individual point-to-point interconnect and provides for cache coherency through the system. More information about SCI can be found in IEEE 1596 (Aug 3,1993) referenced herein.

Inter-node network 105, preferably an SCI compatible communication medium, may be used in any of a variety of alternatives that have existed or since developed. Inter-node communication media preferably provide high bandwidth and low latency and are variable to allow for the addition of more nodes. Suitable media include point-to-point interconnect links with high data throughput (eg, 1 gigabyte or more per second). This link can be configured in any suitable and various ways such as a ring topology, any topology through a switch or a combination of both. This link can be wired or wireless (optional, RF, etc.) depending on the performance requirements of the system. Examples of additional topologies are described in "Interconnect Topologies with Point-To-Point Rings" (Ross E. Johnson and James E. Goodman December 1991, Computer Science Technical Report # 1058, University of Wisconsin-Madison). All examples do not need to be covered by all kinds of suitable networks.

2 is a block diagram of the major hardware elements of a general node 101 of a computer system 100, according to a preferred embodiment. Consistent with the description contained herein, a node is indicated generically by the reference numeral 101, which is equivalent to referring to any node 101-104. Node 101 includes a plurality of central processing units (CPUs) 201-204 that perform instructions and machine processing functions on other data from distributed main memory. Each CPU 201-204 includes or controls a respective cache 205-208 for temporary storage of data and instructions. For large multiprocessor computer systems, caches generally exist in multiple levels and in multiple structures. For example, the CPU may have a level 1 cache that contributes to the storage of instructions executing on the CPU (L1 instruction cache) and a physically separate level 1 cache that contributes to the storage of data except instructions manipulated by the CPU (L1 data cache). And a level 2 cache (L2 cache) that stores both instructions and other data, the L2 cache being used to feed the L1 instruction cache and the L1 data cache. The cache structure or structures are shown in simplified form in FIG. 2 as a single block 205-208 for each individual processor. For the purposes of the present invention, it is not important to exactly and specifically implement the cache on each processor. Many other variations are possible, and the present invention is not limited to any particular cache design and does not necessarily require the use of a cache.

Computer system 100 uses distributed main memory, including local memory 210 separated within each individual node 101. The total addressable main memory in system 100 is the sum of the addressable local memories 210 in each individual node. Therefore, the real address space of the mail memory is constant throughout the system, and any memory location in local memory 210 has the same, unique real address for all processors and all nodes.

Inter-node interface device 215 connects node 101 to inter-node network 105, where node 101 is able to communicate with other nodes in system 100. Interface unit 215 generally includes a cache or buffer for temporary storage of data passed between nodes.

I / O bus interface unit 220 provides for communication to one or more I / O devices via one or more I / O buses 221-222. I / O buses 221-222 are direct access storage devices (DASDs, 224), tape drives, workstations 225, printers and remote devices, or other computer systems via a line or network for communication. And any kind suitable for communicating with conventional I / O devices, such as telecommunication adapters for communicating with the device. For example, I / O bus 221 is an industry standard PCI bus. Although two I / O buses and two I / O devices are shown in FIG. 2, the number of such buses and devices is variable, and furthermore, all nodes 101 may have an I / O interface unit 220 or attached I. There is no need to include / O devices.

Internal node bus 212 provides communication between the various elements of node 101. In particular, the bus 212 transfers data between the local memory 210 and the caches 205-208 of the individual CPUs 201-204 in response to the memory accesses made by the CPU. By monitoring the logic on local memory 210, inter-node interface 215 and / or bus 212, the specific real address requested on the memory access may be in or out of the local memory 210 of node 101. Determine whether it is included in the local memory of the remote node, and direct memory access to the local memory 210, or the inter-node interface 215 for communicating with the remote node. In order to reach the local memory of the responding node where the data resides, the node bus 212 of the requesting node, the inter-node interface 215 of the requesting node, the inter-node network 215, the corresponding inter-node of the responding node While crossing the corresponding node buses of the interface and response nodes, one may observe that memory accesses to real addresses inside local memory 210 return back to a relatively small number of device cycles via bus 212 ( If the request data is in any of the interface caches, this operation is shortened in some cases). As a result, memory accesses to remote nodes generally require a relatively larger number of cycles.

Although a system with four nodes is shown in FIG. 1, and a typical node with four CPUs and various other devices is shown in FIG. 1, FIGS. 1 and 2 are simplified examples of one possible configuration of NUMA for illustrative purposes. It is to be understood that the number and type of devices possible in such a configuration is variable, and that the system may include additional devices not shown in the figures. Also, not all nodes need to be the same, nor do all nodes need to have the same number of CPUs or local memory capable of the same number of addresses.

<Operating System Perspective>

3 is a conceptual explanatory diagram showing the division of hardware and software functions of different levels of abstraction within a multi-node computer system according to a preferred embodiment 100. As is known, a computer system is a sequential state machine that performs a process. These processes appear to change the level of abstraction. At a higher level of abstraction, the user enumerates one process and input, and receives output. As it progresses down the level, it becomes known that these processes are a sequence of instructions in some programming languages, and as it progresses further down the level registers are translated into device registers that ultimately force arbitrary operation through the operating system. Is sent in the data bits. At a lower level, changing the electrical potential enables various transistors to be turned on and off. In Figure 3, the "higher" level of abstraction means towards the top of the form, while the lower level means towards the bottom.

The hardware level 301 shown in FIG. 3 refers to the physical processor, memory bus, and other components that cause instructions to be executed. As used herein, hardware level 301 refers to a collection of physical devices (as opposed to data stored in the device) shown in FIGS. 1 and 2, which are not shown in FIGS. 1 and 2. Include hardware.

Just above the hardware is a low-level operating system level (302), which is called a "kernel" in some operating systems. In a physical sense, an operating system is code, such as data in the form of instructions that are executed on one or more processors or stored in various memory locations to perform a requested function. The low-level operating system provides any basic operating system functions necessary for sharing system resources, allocating memory, enhancing security, and the like. Among the functions provided by the low-level operating system 302 are the paging function 303 and the dispatching function 304. Phaser 303 is called when an execution thread attempts to access data that is not currently in the system's distributed main memory, for example when the data is not in any local memory 210 of the various nodes. In this case, pager 303 causes the request data to come out of the storage device (such as a rotating magnetic disk drive storage device) and be located in any of local memory 210. As described in more detail herein, dispatcher 304 hits a thread waiting to be executed by a processor for execution. Dispatch ready queue structure 305 includes a thread waiting for dispatch by dispatcher 304.

Above the level of the low-level operating system 302 is an additional higher-level operating system function 308, as well as various user processes 310-312, such as user application code and data. In general, the higher-level operating system function 308 provides additional means and functions to the user who wants access, but the user process may directly access the low-level operating system 302 for execution.

In a preferred embodiment, the operating system is a Microsoft Windows 2000 ^™ operating system, where the task dispatcher and pager have been modified as described with regard to the node location of the CPU and memory. However, any virtual multi-tasking operating system with a single, co-ready queue to which jobs are dispatched may be used here, such as a UNIX ^TM based operating system, including an advanced operating system, an IBM AS / 400 ^TM operating system, and the like. It can be applied to the functions described in.

In a typical computer system design, it is desirable that higher level entities are protected from doing specific implementations of lower level entities. In the case of a hardware design of a NUMA system, this means that the operating system and higher level software preferably do not require knowledge of the NUMA characteristics. Thus, in general, a NUMA system requires that the operating system share its distributed main memory, a single monolithic entity-this single monolithic entity returns the request data if it exists. If not present, it is designed to be considered as responding to a data request by generating a page fault. Similarly, an operating system simply considers a collection of nodes and processors as a large pool of processors, which means that any processor can execute any process. This does not mean that all processors perform a given task at the same time, or that all memory accesses are achieved at the same time; The reason is as mentioned previously. However, that does not mean that the request memory is achieved without a memory access error, whether or not it is in the same node. Therefore, the operating system can dispatch a thread regardless of the node where the processor is located.

Although NUMA system hardware is designed to be functionalized with standard low-level operating system functions, if the low-level operating system is better aware of the hardware design, especially if the node location of the processor is taken into account when dispatching threads, Computer systems will operate more efficiently.

<Dispatching and Paging Functions>

The thread dispatcher described herein is manipulated on the principle that if a thread runs on consistent nodes, the data needed by the thread will tend to accumulate in a general execution node, and thus the frequency of inter-node memory access will be reduced. This is true if the memory paging mechanism reveals the locality of placement, in other words, if the pager 303 tends to be very inconsistent to place the request page at some particular local node. do.

A simple and straightforward way to implement a pager indicating locality of location is to limit the page location to the node of the requesting processor, which is the method used in the preferred embodiment. In other words, in the case of a page fault, the pager 303 always places a new page in the local memory of the node containing the processor, the processor making a memory access request causing a page fault. Say that. Phaser 303 selects the best candidate to be paged out from a valid page in the node's local memory. An alternative way to implement the pager is to limit the page position to the ideal node of the request process. In other words, an ideal node is associated with each process (which will be described more fully below), and even if the node is not the same as the processor giving the memory access, one page is always associated with the process that caused the page fault. It is located in the local memory of the ideal node. The reason for this optional method is that the page is located on a consistent local node, even if the thread created by the process is often run on another node. However, these two selectivities are not the only possible techniques that can be adopted by the pager, and various optional standards or combinations of standards can be used to achieve some degree of localization of the page position.

Thread dispatching depends on the state and priority of the thread. At any moment in time, a thread is in one of several states. For example, a thread may be in a running state running on a processor, may not be executed until some external event occurs, and may be in an event waiting state waiting for an event to occur, or only waiting for a valid processor You may be ready to run. Depending on the operating system, additional states or advanced states of those states may be defined. In addition, the priority of execution relates to each thread. Various priority assignment schemes known in the art may be used. Priorities are usually assigned by the user, the system administrator, or the operating system itself. For example, the priority of a user application process is often governed by an override by the user, resulting in a default priority for the user process enumerated by the operating system. The priority can be fixed for the duration that the thread is present, or adjusted depending on various factors, such as the length of time the thread is waiting on the ready queue. Conventionally, although the priority may optionally be in reverse order, a higher number indicates a higher priority.

Dispatcher 304 selects a thread for dispatch from thread ready queue structure 305. The ready queue structure 305 is described in more detail in FIG. As shown in FIG. 4, the ready queue structure includes a plurality of lists 401-403 of control blocks 410-412, and the number of three leases shown for explanation in FIG. 4 is variable. Each control block list 401-403 is sorted in FIFO order. Control blocks 410-412 of a given list represent the threads associated with the desired priority, which are ready to run and wait. In other words, the control block lists 401-403 include threads that are in a ready state. When a thread enters the ready state, the control block is placed at the end of the list with priority associated with the thread. When the dispatcher 304 dispatches it to the execution CPU, the control block is normally removed from the list.

In the preferred embodiment, there is only one ready queue structure 305 for the system 100, and every thread preparing to run is a list 401-403 of the ready queue structure 305 corresponding to its thread priority. ) The ready queue is not associated with any CPU or group of CPUs, meaning that no CPU or group of CPUs (such as nodes) receive preferential dispatch of jobs from the ready queue. If the ready queue is a memory structure, it will generally be stored on one of the nodes, and the dispatcher will generally run on that node's CPU, but this does not mean that it is "associated with the CPU or CPU group."

Each control block 410-412 includes any state information about an active thread, and a portion of the control block is used by the dispatcher 304 to select a thread for dispatch. 5 illustrates any thread-specific information from a typical control block 410 used by the dispatcher. As shown in FIG. 5, the control block includes a priority 501, an affinity mask 502, an ideal node mask 503, a recently executed processor 505 and a queue time 506. Priority area 501 includes the target numerical priority of the thread. Similarity mask 502 is a series of mask bits corresponding to individual CPUs, whereby a user or system administrator may request that a process may only run on a subset of CPUs that are valid on the system, where the subset is similarity. To enumerate by a mask; In most caches, the user does not restrict execution, and the similarity mask is set to make all CPUs executable. The ideal node mask 503 is a set of mask bits corresponding to individual nodes, whereby one or more preferred nodes for execution may be named as described herein. The ideal processor area 504 is a numerical designation of a single preferred CPU for the execution of the thread. Recently executed processor region 505 is a numerical designation of the CPU as to which thread was most recently executed. Queue time area 506 contains a value indicating the length of time that a thread is in the ready queue. For example, this value may be a time-stamp that records when a thread enters the queue, although it may be a counter that increments when some event occurs or another value.

4 and 5 illustrate ready queues and control blocks in a simplified form for illustrative purposes, and are not intended to provide an accurate blueprint of the data structure type used by the dispatcher. The ready queue shows that it contains a plurality of control blocks 410-412 of linked list sorts, each block 410-412 corresponding to a single individual thread and containing all the necessary state information. However, the exact structural details of the queue data structure are variable, which can be implemented as one array or other form of data structure. Furthermore, while showing that the control blocks 410-412 contain complete state information for each individual thread, the writes in the queue may contain only partial information requiring dispatchers, and the necessary data may be found. It may simply contain more pointers or other indices to places where it can be. The control block may include other and additional state information used by the dispatcher or other functions.

Any value of the control block that controls the dispatching selection is initialized if the processor creates a thread and may inherit from a value generated in process initialization. 6 is a flow chart showing any high level step taken by the operating system to initialize thread control values. As shown in FIG. 6, the process is initiated by conventional methods, allowing any data structure to be generated, initialized, and in particular a control block or similar structure that maintains the values depicted in FIG. 5. In addition, priority and processor similarity are assigned to the process. This step is optionally represented at high level as step 601.

One ideal node is involved in the process as follows. If the process is a system process or has a particular processor similarity assigned to it, then a "Y" branch is selected from step 602 and the ideal node is set to all (step 603). In other words, the ideal node mask associated with the process is set to "on" with all nodes, which effectively means that no ideal node selection exists. The system process is one of various target operating systems intended to run on every node. Processor similarity is dictated by a user or system administrator and limits the process to running on a specific subset of valid CPUs. Although processor similarity is rarely indicated, ideal node allocation is not used in this case, if such similarity is indicated, as it will override the "ideal node" assigned to the system.

If the process is not a system process and does not have a particular processor similarity (in other words, it can run on any processor), then an "N" branch is selected at step 602. In this case, the operating system allocates the ideal node using a round robin algorithm. In other words, the number of nodes most recently assigned to the process increases (step 604), and this node is allocated as the ideal node of the process (step 605). The assignment operation is performed by setting the bits of the ideal node mask corresponding to the selected ideal node.

For high adaptability, a node mask may be used such that a single node may be the indicated ideal node, all nodes may be indicated, or any subset of nodes may be indicated. By default, the operating system chooses a single node for most user processes, as shown below. However, it is possible for the user to override this selection through a special function call. This function tends to interfere with the equilibrium of resources performed by the operating system, but it is thought that this function is rarely used because there may be special circumstances justifying it.

A simple round-robin algorithm is used as a default to distribute processes and balance resource usage between valid nodes on an equal basis. However, any number of alternative methods for assigning preferred nodes can be used by the operating system. For example, if the number of processors in each node is not the same, it is desirable to weigh the allocation. Optionally, statistics about recent CPU usage can be provided, and processes can be assigned to nodes with the lowest recent CPU usage.

At some point, as shown in step 610, the process creates a thread. The process may create a single thread or may create multiple threads, but only one is shown in FIG. 6 for illustration. Among other things, creating a thread means that a status record or records (eg, control block 410) has been created for the thread and initialized to an arbitrary value. As initiating a process, creating a thread may include a number of steps, as known in the art, and is not described herein, but only as a high level of step 610. Thread priority value 501, similarity mask 502 and ideal node mask 503 are inherited from similar values for the process that created the thread (step 611); This may mean that the process value is copied to the thread control block or that the thread control block simply references the process value.

Preferred CPUs for execution (called "ideal CPUs") are assigned to each thread by starting with a random CPU at the ideal node and rotating a round-robin based ideal CPU allocation. In other words, if the created thread is the first thread created by the process, then the "Y" branch is selected in step 612 and the CPU in the ideal node or nodes (indicated by the thread's ideal node mask) is Randomly selected (step 613). If the created thread is not the first thread, an "N" branch is selected in step 612, and the operating system increases the number of CPUs in the ideal node or nodes (step 614), and then creates a new CPU. The allocated thread (step 615).

6 is a very simplified flow chart of process and thread initialization to illustrate the initialization of any variable used by the dispatcher and is not intended to fully describe the steps of initializing a process or creating a thread.

The operation of the ready dispatcher 305 included in the control block 410 and the thread dispatcher associated with the information will be described. In general, the dispatcher responds to external events indicating that a new thread should be dispatched or may be dispatched, and determines that the thread is to be dispatched, or the CPU decides to execute the thread. In the first mode (shown in FIG. 7), the dispatcher causes the CPU to select a valid thread from the ready queue 305 when it becomes available to execute the thread. This may be the case, for example, if a previously executed thread on the CPU encounters a long latency event, or the execution of the thread previously terminated, or the execution of a previously interrupted thread, or terminates execution. May occur. In the second mode (shown in Figure 8), the dispatcher is called to select a valid processor because the thread is ready to run (e.g., a new thread has been created or an external event that the thread was waiting on has occurred). Or some other event caused the thread to be ready). Depending on the design of the operating system, the dispatcher may also be called for other reasons.

The center of the dispatcher is the thread selection mechanism, which selects a thread for dispatch. Since one thread is selected as the best match for a valid CPU, when this thread selection function is called, the target CPU for dispatching the thread is considered. In a preferred embodiment, this target CPU is generally a CPU that has just become available and has triggered a dispatch function.

7A and 7B (optionally referred to as FIG. 7) are flow diagrams illustrating the operation of the thread selection function in dispatcher 304. The thread selection function is called to select a thread for the target CPU (indicated by P), which is generally the just-validated CPU described above. This thread selection function examines the various control block lists 401-403 in the ready queue from the highest priority to the lowest priority until a suitable thread is found. As shown in Fig. 7, the thread selection function first selects the list examined (step 701). Initially, the selected control block list is the highest priority list, and with subsequent iterations of the main loop, step 701 selects the highest priority list of the list that has not yet been tested. The variables ideal_node_hit and ideal_CPU_hit are initialized with null values (step 702). In addition, the dispatcher determines a maximum waiting time (wmax) for a thread of the selection control block list (also step 702). The maximum wait time varies for each list, less for higher priority and greater for lower priority list; Therefore, it is necessary to reset the wmax value for each selection list tested.

The thread selection function loops through steps 710-718 to test each thread in the alternately selected control block list or at the end of the reached list, as shown in FIG. 7, until a match is found. Thread t from the list is selected (step 710). This thread initially becomes the first thread in the list, and its control block has been on the list for the longest, and subsequently the thread on the list that has not been selected yet. The thread selection function then determines whether P is one of the CPUs in thread t's processor similarity, eg, whether the bit corresponding to processor P is set in thread t's processor similarity mask 502. If not, thread t is excluded from running on processor P, and the thread selection function proceeds to step 718 to test the next thread.

If P is in the processor similarity of t (" Y " from step 711), then the thread selection function determines whether t meets the criteria for immediate selection (step 712). The test performed at step 712 is logically represented as:

(t is the real-time priority list) OR (1)

(t waited longer than wmax) OR (2)

((P = last_CPU) AND (P = ideal_CPU)) OR (3)

((P = last_CPU) AND (P is within the ideal node of t)) OR (4)

((P = last_CPU) AND (ideal_CPU similar to t)) OR (5)

((No ideal node exists) AND (P = ideal_CPU)) (6)

Conditions (1) and (2) override the normal node that matches the consideration when dispatching thread t urgently. The real-time priority list is a special high-priority control block list, which effectively has a wmax of zero, and any thread control block waiting on this list has exceeded its maximum waiting period. In all other control block lists, if thread t has already been waiting longer than the predetermined time period wmax for the list on which t is waiting, t is immediately selected for dispatch. If the thread was last executed at P (as listed in last_CPU region 505), condition (3) selects the thread, and P is the ideal CPU of the thread listed by ideal_CPU region 504. Condition (4) is similar to (3), but extends the concept of ideal to any processor of the ideal node of t, in other words, the node listed by the ideal node mask 503 of t. Condition (5) deals with the special case where there is no ideal CPU within the similarity of thread t; This only happens where some arbitrary value (such as similarity) has changed after process initialization, such as by an API call. Condition (6) deals with the special case where there are no ideal nodes listed in mask 503, in which case an ideal CPU is preferred.

If the criterion expressed above for the immediate selection is satisfied, the "Y" branch is selected in step 712, and thread t becomes the indicated selection thread (step 713), and this thread selection function further tests the remaining threads. Is returned. If not, the "N" branch is selected. In that case, if P is the ideal CPU listed by ideal_CPU region 504, and this is the first thread to meet (in other words, ideal_CPU_hit = null), then the "Y" branch is selected at step 714, ideal_CPU_hit is set to t (step 715). If the "N" branch is selected at step 714, then if P is at the ideal node listed by the ideal node mask 503 and this is the first thread to meet (e.g., ideal_node_hit = null), then "Y" The branch is selected from step 716 and ideal_node_hit is set to t (step 717). If more threads remain in the selection control block list (step 718), this thread selection function is returned to select and test the next thread on the lease. If all threads in the select list have been tested, an "N" branch is selected from step 718. The thread selection function continues to step 720.

If the ideal_CPU_hit is not null, then the "N" branch is selected in step 720, and the thread listed by ideal_CPU_hit becomes the indicated selection thread (step 721), and the function is additional The list is returned without testing. If ideal_node_hit is null, a "Y" branch is selected at step 720. In this case, if ideal_node_hit is not null, an "N" branch is selected in step 722, and the thread listed by ideal_node_hit is the indicated selection thread, and the function returns without testing the additional list. If both ideal_CPU_hit and ideal_node_hit are null, a "Y" branch is taken, and the list with the priority immediately below the current list is selected for testing. If all lists have been examined, an "N" branch is selected in step 724, where a null value is indicated as the selection thread (step 725), and this thread selection function is returned. If the thread has been enabled for execution, the dispatcher is called to select the appropriate CPU to run the thread, if possible. The CPU selection process is invoked to select a CPU from the plurality of potential CPU candidates of FIG. This process is described in FIG.

The CPU selection function first determines whether an ideal CPU is within the similarity of thread t and whether it is currently idle (step 801). If so, a "Y" branch is selected in step 801, this ideal CPU is selected (step 802), and this thread selection function is returned. If not, an "N" branch is selected at step 801.

If at least one idle CPU is within the similarity of thread t, and an ideal node exists, if this CPU is within the ideal node for thread t (in other words, if no ideal node exists, the test is at least one) Whether the idle CPU of is within the similarity of thread t), and then the "Y" branch is taken from step 803. In this case, one such CPU is selected (step 804). Where there is one or more idle CPUs that meet the criteria of step 803, if it is one of the CPUs that satisfy the criteria, the CPU selection function selects the CPU finally used by thread t, If not, select one of the CPUs under the base of the default selection logic. The thread selection function is then returned. If no CPU meeting the criteria is found in step 803, the " N " branch is selected taking into account any processor that is not idle.

If the idle CPU is within the similarity of thread t, the "Y" branch is selected in step 805, and this ideal CPU is temporarily selected as a candidate CPU (step 806). In this case, the CPU must be busy or selected in step 801. If an "N" branch is taken at step 805, there is a CPU in the similarity of thread t, and if there is an idle node, it is also within the idle node of thread t (in other words, where there is no idle node) In this case, the test target is whether or not there is a CPU in the similarity of the thread t), the "Y" branch is selected in step 807, and one such CPU is temporarily selected (step 808). Where there is more than one such CPU, if it is one of those that meets the criteria, the CPU selection function temporarily selects the CPU finally used by thread t, and if not, temporarily based on the default selection logic. Choose one of the CPUs. If the "N" branch was taken in step 807, the CPU selection function temporarily selects the CPU within the similarity of thread t using the default selection logic (step 809).

If the candidate CPU has been temporarily selected in step 806, 808 or 809, the priority of any currently running thread in the candidate processor is compared with that of thread t (step 810). If the priority of t is greater, an "N" branch is taken from step 810, and the candidate CPU is identified as the selection CPU. In this case, the selection of a non-idle CPU will free up the currently running thread in advance. If the priority of t is not greater than the priority of the running thread, then a "Y" branch is taken at step 810, and the selection CPU is set to null. In either case, the CPU selection function is returned. Where the CPU selection function returned null selection, no suitable CPU could be found for immediate dispatch of thread t, so thread t waits for the ultimate dispatch from the queue if selected by the thread selection function described previously. Located in the ready queue. Therefore, if similar to the thread selection function, no CPU is selected, and even at the point where thread t is ultimately placed in the ready queue, the CPU selection function may refuse to select the idle CPU of the non-ideal node.

In general, the routines executed to implement the described embodiments of the invention, i.e. whether implemented as an operating system or as part of a particular application, program, object, module or sequential instruction, are referred to herein as a "computer program" or It is simply referred to as a "program." A computer program is typically prepared or executed by one or more processors in a device or system of a computer system consistent with the present invention, where the device or system generates elements that perform steps or implement various aspects of the present invention. Instructions to perform the steps necessary to perform. In addition, while the invention describes a computer system that functions to the maximum, various embodiments of the invention may be distributed as various types of program products, the present invention being capable of maintaining a particular kind of signal used to actually accomplish the distribution. Notwithstanding the medium, the same applies. Examples of signal bearing media include, but are not limited to, recordable media such as volatile and nonvolatile memory devices, digital media including floppy disks, hard-disk drives, CD-ROMs, DVDs, magnetic tapes and wireless communication links; Transmission type media such as analog communication links. Examples of signal holding media are described in FIG. 2 with memory 210 and storage 224.

Additional Optional Embodiments

Specific algorithms for dispatching threads of NUMA systems have been described as preferred embodiments so far. However, it should be understood that various variations of the above algorithms are possible. The exact algorithm chosen often depends on various hardware and software considerations specific to the computer on which it is designed. In general, an algorithm for dispatching any thread from a common ready queue that takes into account the physical location of a processor relative to a subset of a distributed memory system may be used to reduce long latency real memory access. Can be used. Most obvious alternatives are to remove one or more of the conditions described herein with respect to the preferred embodiment, or to add certain conditions to the above algorithm. Some specific examples of additional changes are described below, which are mentioned as examples only and should not be considered as a complete list of possible alternatives. In one alternative, there is no need to indicate an ideal processor or ideal node. The processor on which the process or thread runs first is randomly determined. The thread selection algorithm prefers the last thread running on the target processor or another processor on the same node. Since processors on the same node are more desirable, threads tend to run within a consistent node, despite the lack of ideal instructions.

In another option, the thread may be selected by a mathematical measurement function as opposed to the above logic. The measure function provides a specific score for each thread in the queue, which has the optimal score selected for dispatch. For example, the form of such a measurement function is as follows:

F ₁ (wait_time) + F ₂ (node) + F ₃ (CPU) + F ₄ (Priority) +.

Where F _N is the pneumatic function of the individual independent variables. Of course, such a measurement function is more complicated.

In the above preferred embodiment, the NUMA computer system is architecturally designed as a collection of semi-independent nodes, each node having an internal bus, a processor, a local memory, and the like, coupled to each other as an inter-node communication medium. It is. In addition, some examples of such NUMA system architectures have been constructed, publicly available, and any practical experience has already been gained with this approach. However, the NUMA system according to the present invention does not necessarily need to be designed with such a node model. Although the system is based on a certain design model except for the node system described above, in selecting a processor that executes a thread or task, the dispatcher describing non-uniform memory access is potentially valued in any NUMA system. have. Therefore, any optional system architecture known or later developed (indicating the nature of non-uniform memory access) may be employed. As an example of such an optional architecture, a NUMA system is a system with a complex memory bus structure, which includes a web of bus segments linked by an interface, and some memory accesses only a single bus. Segments, while other memory accesses require more time to review multiple segments. Other alternatives are possible. Furthermore, in a preferred embodiment, even though memory access is divided into two classes (intra-node and inter-node), one system may have two or more memory access classes, each class being a separate individual Requires access time.

Although specific embodiments of the invention may be described for illustration, it should be understood that various modifications may be made without departing from the spirit and scope of the invention. Therefore, the protection scope of the present invention shall not be limited by the following claims and their equivalents.

Various observations may be made regarding the operation of the thread selection algorithm. The dispatcher can achieve NUMA-perceived operation despite the presence of a single ready queue that is not associated with any CPU or group of CPUs. For most threads (with a single ideal node indicated and a single ideal CPU indicated), if processor P is not at least at the ideal node of the thread, the thread is generally not selected for dispatch. Within an ideal node, a weak priority is given to a thread with P as its ideal processor for a thread with P that is at that ideal node and not to that ideal processor. If P is the last processor that the thread executes and any other condition is satisfied ((3)-(5) of steps 712), then no more tests for the queue, and one thread is immediately selected as an ideal candidate; The last processor is important because in addition to the node's local memory, there may be useful data in the processor's cache. If processor P is not the last processor the thread ran on, but is at the ideal node or is the ideal processor, the selection is temporary by the ideal_CPU_hit and ideal_node_hit variables, and if a better candidate is found while examining the queue, it is overridden. The thread selection algorithm does not necessarily select any thread even though the thread is waiting in the queue. Finally, the thread waiting on the queue is ultimately chosen for dispatch, even though P does not match the ideal node or the ideal processor of the thread.

As a result of pointing to an ideal node, threads tend to run on the same node even if the ideal processor is not valid. The pager loads the page data into the local memory of the node of the processor making the page request, so the data needed by the thread tends to accumulate in the local real memory of the indicated ideal node. As a result, memory access from the CPU to the system distributed real memory will access the CPU node's local real memory (rather than memory beyond the node boundary) at a greater rate than for similar task dispatchers that do not consider the location of the node. . Increasing proportional to intra-node memory access improves system throughput by reducing traffic in inter-node communication media and reducing memory access time.

Claims (17)

A method of dispatching threads to central processing units (CPUs) of a computer system, the computer system comprising a plurality of computers 201-204 and a memory 210 that can be divided into a plurality of discrete subsets, Identifying a target CPU; Identifying one set of threads suitable for execution on the target CPU (710), wherein the set of threads waits on a common ready queue 305 that is not associated with any CPU or group of CPUs. Wow; Identifying at least one target subset of the plurality of discrete memory subsets for each individual thread of the thread set, wherein the target subset is memory to a location in the target subset by the target CPU. An identification step having an individual latency period for access; Selecting one thread from the set of threads for execution on the target CPU, the selection step being based at least in part on the respective latency of each target subset; Thread dispatch method comprising a. 2. The system of claim 1, wherein each of the plurality of CPUs is associated with an individual subset of one of the plurality of discrete memory subsets and identifies at least one target subset of the plurality of discrete memory subsets. Said step of instructing an individual CPU desired to execute each thread of said thread set, wherein said target subset of said plurality of discrete memory subsets is a memory subset associated with said preferred CPU. Thread dispatch method. 3. The method of claim 1 or 2, wherein the plurality of CPUs are associated with each individual subset of the plurality of discrete memory subsets. The method of claim 1, wherein the step of selecting one thread from the set of threads for execution comprises: Assigning a first relative priority to a thread for which the indicated preferred CPU is the target CPU (714-715), Assigning (716-717) a second relative priority to a thread in which the indicated preferred CPU is associated with the same subset of memory as the target CPU; Assigning a third relative priority to a thread for which the indicated preferred CPU is not associated with the same subset of memory as the target CPU; The first relative priority is greater than the second relative priority, and the second relative priority is greater than the third relative priority Thread dispatch method. 5. The computer system of claim 1, wherein the computer system comprises a plurality of discrete nodes 101-104, wherein each node is a separate sub-set of at least one CPU and one of the plurality of discrete memory subsets. 6. Identifying a target subset of at least one of the plurality of discrete memory subsets for each individual thread, identifying at least one target node for each individual thread (605). Thread dispatch method comprising a. 6. The method of claim 1, wherein the step of identifying at least one target node for each individual thread includes the step 615 of indicating an individual CPU desired to run each thread of the thread set. And wherein the target node is the node on which the preferred CPU is located. 7. The method of claim 2, wherein the step of instructing a desired individual CPU to execute each thread of the thread set is performed when the thread is created (610). Instructions for performing the method of any one of claims 1 to 7; Signal bearing media in which the command is recorded Computer program product comprising a. Each node includes one or more central processing units (CPUs) 201-204 and local memory 210, wherein the set of all local memory in a plurality of discrete nodes includes distributed main memory of the computer system. A plurality of discrete nodes; An interface network (105) for providing data communication between the plurality of nodes; A common ready queue for holding a plurality of threads ready to run on said computer system, said queue not being associated with any particular CPU or group of CPUs; A thread that dispatches a thread from the common ready queue to run on the CPU, wherein the thread dispatcher considers the node location of the CPU when dispatching the thread, and the thread dispatcher is the data requested by the thread in the local memory of the node. Thread dispatcher 304 to preferentially dispatch threads to CPUs within nodes that are likely to contain relatively large shares of A non-uniform memory access computer system comprising a. 10. The system of claim 9, wherein one location is selected in the distributed main memory for storing paged-in data, and the pager stores at least page-in data that has generated a page fault. A pager 303 for storing in the local memory of the node determined by one thread; Containing the CPU that was running the thread that caused the page fault Non-Uniform Memory Access Computer System. The non-uniform memory access computer system of claim 9, wherein each node comprises a plurality of CPUs. 12. The non-uniform memory access computer system of claim 9, wherein the dispatcher selects one thread from a plurality of ready threads running on a target CPU. 12. The non-uniform memory access computer system of claim 9, wherein the dispatcher selects one CPU from among a plurality of CPUs suitable for execution on a preparation thread. 14. The method of claim 9, wherein the preferred individual node is associated with at least some threads when a thread is created, wherein the thread dispatcher causes the thread to be preferentially dispatched to the CPU at the preferred node of the thread. Non-Uniform Memory Access Computer System. In a thread dispatching mechanism for a non-uniform memory access computer system, the non-uniform memory access computer system includes a plurality of central processing units (CPUs) 201-204, For each of a plurality of threads in a common ready queue that is not associated with any CPU or set of CPUs, for determining one CPU set that the thread is likely to have shorter memory access time to the requested data. Means for each individual CPU set having at least one CPU; Means for selecting a thread and a CPU for executing the threads 610-615, wherein the selecting means preferentially selects a thread and a CPU for executing the thread, the CPU for executing the thread Thread dispatching mechanism, wherein the thread is a member of one of said CPU sets that is more likely to have shorter memory access times to the requested data. 16. The non-uniform memory access computer system of claim 15, wherein the non-uniform memory access computer system comprises a plurality of discrete nodes 101-104, wherein each node is an individual of at least one CPU and one of the plurality of discrete memory subsets. Means for selecting one CPU set that includes a subset 210 and, for each thread, is more likely to have a shorter memory access time for the data requested by the thread, for each thread, the individual thread. And means for identifying a set of CPUs in the node that are likely to contain the data requested by the thread dispatching mechanism. 17. The thread dispatching mechanism of claim 15 wherein said selecting means preferentially selects said thread when a thread is created.