Facilitating distributed thread migration within an array of computing nodes

One embodiment of the present invention provides a system that performs thread migration within an array of computing nodes, wherein computing nodes in the array contain central processing units (CPUs) and/or memories. During operation, the system identifies CPUs within the array of computing nodes that are available to accept a given thread. For each available CPU, the system computes an average communication distance between the CPU and memories which are accessed by the given thread. Next, the system determines whether to move the given thread to an available CPU based on the average communication distance for the available CPU.

BACKGROUND

1. Field of the Invention

The present invention relates to the scheduling of threads within a multiprocessor system.

2. Related Art

Multiprocessor systems typically contain a number of central processing units (CPUs) and memories, which are coupled together through a communication network. For example, in an exemplary system, nodes containing CPUs and memories are organized into a two-dimensional grid, wherein each node can communicate with neighboring nodes (in north, east, south or west directions). Furthermore, each CPU can execute one or more threads in parallel.

While executing on a CPU, a thread can access memory locations within other nodes in the grid. The latency of these memory accesses depends largely on the communication distance (number of hops) between the CPU executing the thread and the memory location being accessed. Hence, it is generally desirable to minimize the distance between the CPU, which is executing the thread, and the memory locations that the thread is accessing. However, it is not easy to minimize this distance because the memory locations with which the thread communicates can change frequently during the thread's lifetime. Furthermore, new threads can be added to the system over time, and existing threads can be removed when they complete their tasks.

Moreover, simply minimizing communication distance may not lead to optimal performance because when a thread communicates with a specific memory location, it can create contention for communication bandwidth with other threads if their communication paths cross. Such memory contentions slow down accesses for all threads involved.

SUMMARY

One embodiment of the present invention provides a system that performs thread migration within a graph containing computing nodes, wherein computing nodes in the graph contain central processing units (CPUs) and/or memories. During operation, the system identifies CPUs within the graph of computing nodes that are available to accept a given thread. For each available CPU, the system computes an average communication distance between the CPU and memories which are accessed by the given thread. Next, the system determines whether to move the given thread to an available CPU based on the average communication distance for the available CPU.

In a variation on this embodiment, the system estimates, for each available CPU, the communication contention that would result from migrating the given thread to the available CPU. The system subsequently uses this estimated communication contention while determining whether to move the given thread to an available CPU.

In a further variation, while estimating the communication contention for a given CPU, the system computes a communication vector for the given CPU, wherein the communication vector is a sum of vectors from the given CPU to the memories accessed by the given thread. The system also identifies threads associated with neighboring CPUs that have average communication distances which are less than the communication distance for the given CPU, and which have communication vectors with a similar absolute angle to the communication vector for the given CPU. Next, the system obtains performance measurements of contention-related slowdowns for the identified threads, and averages the contention-related slowdowns to produce an estimated contention-related slowdown for the given CPU.

In a further variation, the system determines whether to move the given thread to a given CPU by using a weighting scheme to make a tradeoff between the average communication distance and the estimated communication contention for the given CPU.

In a further variation, the system uses a reinforcement-learning technique to make the tradeoff between the average communication distance and the estimated communication contention for the given CPU.

In a variation on this embodiment, while determining whether to move the given thread to an available CPU, the system considers the costs of the moving process.

In a variation on this embodiment, when more threads want to move to a given CPU than the given CPU can support, only threads with the highest positive benefit from moving to the given CPU are allowed to move.

In a variation on this embodiment, the thread migration is performed in a distributed manner, wherein each CPU performs the method for threads which are currently executing on the CPU.

In a variation on this embodiment, each CPU can accommodate multiple threads, and an “available CPU” is defined as a CPU which has an available CPU slot to accept a thread.

DETAILED DESCRIPTION

The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices, such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs).

Multiprocessor System

FIG. 1illustrates a multiprocessor system which includes an array of computing nodes102in accordance with an embodiment of the present invention. Each node in the array can contain a processor and/or a memory.

For example, in the embodiment of the present invention illustrated inFIG. 1, the array of computing nodes102is comprised of a 19-by-19 grid of nodes, with 9 even-numbered rows containing only memory chips (9 in each row) and the 10 odd-numbered rows, which contain memory chips, CPUs or interface chips. Note that chips on the edge of the grid labeled MI support interface functions, while chips on the corners of the grid labeled I/O support I/O functions. In the embodiment of the present invention illustrated inFIG. 1, the array contains 32 CPUs and 113 memory chips. Moreover, each CPU provides hardware support for 8 execution strands.

For purposes of the present invention, the actual layout of the multiprocessor system is not important; it does not have to be a regular grid. In general, any kind of a graph will work, as long as distances between CPUs and memory chips, e.g. in terms of the number of hops, can be defined.

On each CPU, the mechanism that maps from virtual-to-physical addresses is simple enough that each thread knows what physical memory chip it accesses if there are no failures in the system. (During a memory failure, this mapping can change.)

The communication path between a thread and a memory chip it accesses can be represented by a vector ending at the location of the memory chip. If a thread's communication vector is intersected by another vector (representing the communication path of another non-idle thread), and if both vectors point in the same general direction (NE., NW., SE., SW.), then a contention takes place. Each contention reduces the amount of data that can be read from a memory chip.

In the present invention, array of computing nodes102is associated with a thread migration mechanism, which migrates threads to CPUs in a manner that minimizes communication distance as well a communication contention between threads. This thread migration mechanism can reside within a special service processor supervising the system. Or, alternatively, the thread migration mechanism can be distributed across the CPUs, so that each CPU performs its own thread-migration computations to determine whether to migrate any of its threads to other CPUs.

Thread Migration Process

During the thread migration process, every thread in the system considers all available CPUs and computes the potential benefit from moving to each available CPU in terms of reducing the thread's expected completion time. This computation involves considering communication distance and possibly communication contention.

More specifically,FIG. 2presents a flow chart illustrating the thread-migration process in accordance with an embodiment of the present invention. The system first identifies CPUs with available slots to accommodate an additional thread (step202). CPUs without available slots are not considered further.

Next, the system considers a given thread in the system (step204). For this given thread, and for each given CPU (which is available), the system computes the average communication distance and communication angle to memories which are accessed by the given thread (step206). This can involve computing the “vector sum” of the communication paths for the given thread on the given CPU.

Next, for the given CPU, the system considers all threads on nearly CPUs and all threads that are accessing memory chips on nearby CPUs. The system then selects those threads which have a communication vector, which is less than or equal to in length to the given thread's supposed communication vector at the new location, and that have a similar (absolute) communication angle (step208). Note that the system does not consider neighboring threads with longer communication distances, because these longer communication distances may cause communication pathways from a neighboring thread to encounter congestion in distant regions of the array, which are not relevant for the shorter communication distances from the given CPU.

In an alternative embodiment of the present invention, the vector sum of communication vectors of the selected threads is computed and used as the average communication vector for the neighborhood around the new location. In this embodiment, locations where the average communication vector (as computed above) is more colinear with the given thread's new communication vector are preferred while determining where to move the given thread.

Alternatively, possible locations for migration can be ranked in terms of the length of the given thread's own communication vector after migration. The first migration strategy is generally preferable when threads access each memory location for a long time, while the second migration strategy is generally preferable when threads switch often between memory locations they access. (Ideally, a reinforcement learning algorithm can be used for weighing these two measures—length of the given thread's own communication vector after supposed migration versus co-linearity with the neighborhood communication vector—in the context of the given thread's memory access pattern.)

In one embodiment of the present invention, the system also obtains measurements of contention-related slowdowns from the identified neighboring threads (step210) and averages them to produce an estimated contention-related slowdown for the given CPU (step212). Note that the system assumes that neighboring threads with similar communication patterns will exhibit similar contention-related slowdowns to the given thread on the given CPU. Next, the system determines whether to move the given thread to the given CPU by using a (possibly dynamic) weighting scheme to trade off the average communication distance and the estimated contention-related slowdown (step214). Note that when more threads want to move to a CPU than it can support, the system allows the threads with the highest positive benefit make the move. If any threads have not been considered, the system returns to step204to consider another thread.

Also note any type of weighting scheme that trades off average communication distance and contention-related slowdown can be used. For example, in one embodiment of the present invention, the system uses a dynamic weighting scheme, which employs a reinforcement-learning technique to update weight values. (For a description of reinforcement learning techniques, please refer to R. S. Sutton and A. G. Barto,Reinforcement Learning: An Introduction.MIT Press, 1998.) In one embodiment of the present invention, this reinforcement learning technique learns the benefit of migration based on the two variables: individual decrease in the expected “no-contention” completion time and an increase in the communication alignment with new neighbors.