Patent Publication Number: US-8527988-B1

Title: Proximity mapping of virtual-machine threads to processors

Description:
BACKGROUND 
     Herein, related art is described for expository purposes. Related art labeled “prior art”, if any, is admitted prior art; related art not labeled “prior art” is not admitted prior art. 
     Running applications in virtual machines executing on a multi-processor system can be cost-effective as computing resources can be dynamically allocated to workloads according to demand. Each virtual machine can have one or more process threads that are assigned to processors for execution. Since threads from the same virtual machine are likely to be working on a common task, they are more likely to interact than are threads from different virtual machines. Therefore, the different threads from a given virtual machine can be assigned to different processors so that they can execute concurrently and do not have to wait for each other to be activated to exchange data. Where there are more total threads than processors, threads can time-share a processor. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic diagram of a multi-processor system running virtual machines. 
         FIG. 2  is a graph representing thread interactions between virtual processors of the system of  FIG. 1 . 
         FIG. 3  is a flow chart of a method of assigning virtual machine threads to processors of the system of  FIG. 1 . 
         FIG. 4  is a flow chart of a recursive implementation of a portion of the method of  FIG. 3 . 
         FIG. 5  is a flow chart of another recursive implementation of a portion of the method of  FIG. 3 . 
     
    
    
     DETAILED DESCRIPTION 
     In systems where inter-processor communications speeds vary among processor pairs, some assignments of threads to processors offer better performance than others. For example, to avoid contention issues involving communications over a common system bus, processors can be arranged in “proximities”; within each proximity, processors communicate over a local bus. Communications between processors within a proximity are faster than communications between processors of different proximities. Generally speaking, assigning the threads of a virtual machine to different processors of the same proximity allows them to execute concurrently and communicate expeditiously. However, competing considerations, e.g., the desirability of distributing work evenly among processors, may make it difficult to ensure all threads of each virtual machine are assigned to different processors of the same proximity. 
     Herein, the complexity associated with assigning threads to processors is reduced by breaking the task into two more-readily optimized steps: 1) assigning threads to virtual processors; and 2) assigning virtual processors to physical processors. The latter task is further simplified by forming groups of virtual processors; the groups are sized to match the available capacities of proximities. The virtual processors of a group are selected with an aim toward maximizing the estimated amount of inter-processor communication so as to leverage the faster communications available within the proximity to which the group is to be assigned. 
     A system AP 1 , a portion of which is shown in  FIG. 1 , includes sixty-four processors (not all are shown) arranged in sixteen four-processor proximities, including proximities  12 A and  12 B. Proximity  12 A includes four processors PP 1 -PP 4  and a local intra-proximity bus  14 A, over which processors PP 1 -PP 4  communicate with each other. Proximity  12 B includes four processors PP 5 -PP 8  and a local intra-proximity bus  14 B over which processors PP 5 -PP 8  communicate with each other. An inter-proximity bus  16  provides for communications between proximities  12 A,  12 B, and other proximities. Other embodiments provide for different numbers of proximities, differing numbers of processors per proximity, and various provisions for inter-proximity communications. The proximities of a system need not all have same number of active processors, especially since processors can fail or be powered down to save energy costs, etc. 
     A hypervisor  18  and a number of virtual machines including virtual machines VMA, VMB, VMC, and VMD are running on system AP 1 . Alternative embodiments can include different types (Type I, Type II, etc.) of hypervisors and other numbers and underlying technologies of virtual machines. The virtual machines of system AP 1  can be assigned different virtual-machine weights, e.g., corresponding to different priorities or entitlements. For example, virtual machines may be guaranteed different entitlements (minimum levels of resources) or conflicts over resources may be resolved in favor of one virtual machine over another. For virtual machines VMA-VMD, the weights are all 0.5 CPU. However different weights can be assigned to the virtual machines. 
     Hypervisor  18  provides for mapping virtual-machine threads to virtual processors, the number of which matches the number of available physical processors. In the time period represented by  FIG. 1 , virtual machines VMA-VMD have threads TA 1 -TA 4 , TB 1 , TB 7 , TB 8 , TC 5 -TC 8 , and TD 5 . Hypervisor  18  includes a virtual-machine scheduler that maps these threads to virtual processors VP 1 -VP 8  as shown in  FIG. 1 . The virtual processors can be time shared so that more than one thread can be mapped to a virtual processor; however, threads from the same virtual machine are assigned to different virtual processors so that they can execute concurrently, and, thus, interact more expeditiously. 
     An octagonal graph  14  (shown in the middle of the virtual processors in  FIG. 1 ) represents virtual processors VP 1 -VP 8  as vertices; the “edges” connecting the vertices collectively represent all communications paths between pairs of virtual processors. In general, for n processors, there are n*(n−1)/2 such edges. For eight virtual processors, there are twenty-eight pair-wise edges. Graph  14  is one of several subgraph communities for system AP 1 ; other subgraph communities are associated with virtual machines and virtual processors not represented explicitly in  FIG. 1 . 
     Graph  20  is shown enlarged in  FIG. 2 . Vertices V 1 -V 8  correspond to virtual processors VP 1 -VP 8  of  FIG. 1 . Edges E 12 -E 18 , E 23 -E 28 , E 34 -E 38 , E 45 -E 48 , E 56 -E 58 , E 67 -E 68 , and E 78  correspond to the expected interaction weights associated with respective pairs of processors. For example, edge E 78  represents the magnitude of the expected interaction between virtual processors VP 7  and VP 8 . Edge E 78  is thicker than the rest, indicating a greater interactivity weight is assigned to the virtual processor pair (VP 7 , VP 8 ) than to the other pairs. The greater weight is due primarily, but not exclusively, to the fact that virtual processors VP 7  and VP 8  share two virtual machines (VMB and VMC), whereas other pairs share one or none. Quantitatively, edge E 78  has an expected interaction weight of 1.0, the medium thickness edges have a weight of 0.5, and the thin dotted lines have a weight of 0.0. 
     Medium thickness edges E 12 , E 13 , E 14 , E 17 , E 23 , E 24 , E 34 , E 45 , E 56 , E 57 , E 58 , E 67 , and E 68  connect virtual processor pairs that share one virtual machine. For example, edge E 12  connects virtual processor VP 1  (to which threads from virtual machines VMA and VMB are assigned) and virtual processor VP 2  (to which virtual machine VMA is assigned), which share virtual machine VMA. The other depicted edges E 15 , E 16 , E 25 -E 28 , E 35 -E 38 , and E 45 -E 48  connect virtual processors that do not share a virtual machine; such edges are shown as thin dotted lines. For example, edge E 15  connects virtual processor VP 1  and virtual processor VP 5  (to which virtual machines VMC and VMD are assigned), which have no common virtual machines. 
     The illustrated edge thicknesses convey that different edge weights can be assigned to the expected interactivities associated with different pairs of processors. However the precise edge weight assigned to a pair of virtual processors depends on the weight or weights assigned to the virtual machine or virtual machines whose threads are involved in the interactions. In this case, the edge weight associated with an edge is the sum of the weights of the virtual machines involved in the interactions. Thus, the weight (1.0) of edge E 78  is the sum of the weights (0.5+0.5) associated with virtual machines VMC and VMD; the heavy thickness of edge E 78  corresponds to a high expected interactivity between virtual processors VP 7  and VP 8 . The edge weight can be zero (no interactivity) if no virtual machines are shared, or equal to the weight of a single virtual machine if only one virtual machine is shared. Other embodiments provide other methods for computing edge weights from virtual-machine weights. It is expected that the relative degree of communication between virtual processors connected by an edge is proportional to the edge weight. 
     Once threads are assigned to virtual processors, hypervisor  18  divides the sixty-four virtual processors into communities such that: 1) edges between communities have zero or at most negligible weight; and 2) each virtual processor within a community is connected to every other virtual processor in that community via a series of one or more non-zero-weight edges. Virtual processors VP 1 -VP 8  constitute one such community  22 . Note, for example, while virtual processors VP 4  and VP 5  are directly connected by a zero weight edge E 45 , they are also connected to each other by a series of edges including E 14 , E 18 , and E 58 . 
     Ideally, all processors in a community would be assigned to a single proximity. However, community  22  cannot be assigned to either of proximities  12 A and  12 B, because they include only four processors each, while community  22  has eight virtual processors. Therefore, one or more groups of processors from community  22  must be formed that can fit into one or more proximities. In the illustrated example, the eight virtual processors of community  22  end up being divided into two groups  24  and  26  of four; these two groups  24  and  26  are then respectively assigned to proximities  12 A and  12 B. 
     Bisecting axis A 1  ( FIGS. 1 and 2 ) represents the division of community into group  24  with virtual processors VP 1 -VP 4  and group  26  with virtual processors VP 5 -VP 8 . This grouping leaves only two medium weight edges E 17  and E 18  between groups, for a total weight of 1.0; this is near the minimum possible (0.5) between groups from the same community). In contrast, bisecting axis A 2  ( FIG. 2 ) intersects a heavy weight edge E 78  and six medium weight edges E 34 , E 24 , E 14 , E 58 , E 17 , and E 68 , for a total weight of 4.0. Thus, axis A 1  represents a much better division than does axis A 2 . It should be noted that there are hundreds of ways of dividing community  22  into groups and that most of these ways are not readily represented by a bisecting axis, at least not without rearranging the depiction of the virtual processors. 
     Formation of a group from a community (or the full set of virtual processors) takes into account the following considerations: 1) the group size is to match the available capacity of a target proximity (typically, the proximity with the greatest available capacity); 2) the virtual processors of the group are selected to favor high intra-group activity to leverage fast inter-proximity communication speeds. However, the problem of optimally grouping virtual processors to this end can be computationally intense, if not infeasible. However, a significant performance advantage can be achieved with reasonable computation effort as long as groups with significantly higher than random-average estimated interactivity are formed. 
     While assigning such groups to proximities can achieve a performance advantage, further optimization may be available. For example, it may be possible to move a thread from a source processor in a proximity in which it is “alienated”, i.e., all the threads with which it interacts are assigned to other proximities, to a target processor in one of those other proximities. Such a transfer can take place, for example, if there is a “loner” thread (i.e., the sole thread of a virtual machine that will not interact with other threads) assigned to the target processor of substantially equal virtual-machine weight as that of the alienated thread. In such a case, the threads can be swapped without significantly altering the work distribution among processors. 
     For example, thread TB 1  (of virtual machine VMB) can be “moved” from source proximity  12 A (which contains no other threads from virtual machine VMB) to target proximity  12 B, where it joins other threads from virtual machine VMB. This move can be made without significantly adversely affecting the distribution of work to processors by swapping thread TB 1  for thread loner TD 5 . In other words, thread TD 5  can be “moved” from processor PP 5  to processor PP 1  with no adverse effect since it does not interact. In some cases, a loner thread cannot be swapped, either because swapping would adversely affect the distribution of work or because configuration differences between the source and target proximities would adversely affect the loner thread. For example, the loner thread could require non-interleaved memory, which the source proximity provides but the target proximity does not. 
       FIG. 3  schematically depicts computer-readable storage media  30 , which is encoded with code  32 , which defines hypervisor  18  and virtual machines VMA-VMD. Code  32 , when executed, provides for a method ME 1 . Method segment M 1  of method ME 1  provides for assigning weights to virtual machines, e.g., according to business policies or the nature (e.g., real-time v. non-real-time) of the respective tasks for the virtual machines. Method segment M 2  provides for mapping virtual-machine threads to virtual processors so that the expected work associated with the threads is practically evenly distributed, with the expected work associated with a thread corresponding to the virtual-machine weight associated with its source virtual machine. 
     Method segment M 3  involves forming groups of virtual processors selected to favor high total estimated interactivity (edge weight) associated with the group. This can involve dividing virtual processors into communities so that inter-community interaction is at most negligible and so that each virtual processor in a community is connected to every other virtual processor in the community through a series of one or more non-zero-weight edges. Edge weights can be calculated or otherwise determined from virtual machine weights, e.g., by summing the weights associated with the virtual machines shared by the virtual-processors associated with the edge. Likewise, virtual processor weights can be determined from the edge weights, e.g., by summing the weights of all edges connected to a virtual processor. 
     At least one group of virtual processors that can fit within the available capacity of a proximity is formed from a community that is too large to fit within the available capacity of any proximity. For example, at least one group (in this case two groups) of virtual processors is formed from community  22  because its eight virtual processors exceeds the available capacity (four each) of proximities  12 A and  12 B. Groups are formed with an aim of maximizing or at least favoring a high group weight, a high total edge weight associated with the group. 
     Once the groups are formed, they can be assigned to proximities at method segment M 4 . In system AP 1 , the assignment of virtual processors in a group to processors in the assigned proximity can be arbitrary. However, further optimization may be achievable at method segment M 5  by swapping threads between physical processors that are in different proximities, as explained above with respect to alienated thread TB 1  and loner thread TD 5  of  FIG. 1 . 
     As the number of active threads associated with a virtual machine can vary over time, method ME 1  can be iterated so that the assignment of threads to physical processors varies dynamically. For example, method ME 1  can be iterated every ten seconds. Finding an absolute optimum division of virtual-processor communities for each iteration can be infeasible, but a practically favorable division can be found using a more recursive “greedy” procedure with a relatively modest computational load. 
     Thus, as shown in  FIG. 4 , method segment M 3  can involve evaluating edges and virtual processors at method segment M 11 . This can involve assigning an edge weight equal to the weights of the virtual machines shared by the virtual processors associated with the edge. The weight of a virtual processor, in this case, is the weight of the edges connecting it to processors. For example, the virtual-processor weight of virtual processor VP 1 ,  FIG. 1 , is the sum of the weights of edges E 12 -E 18 , and the virtual-processor weight of virtual processor VP 8  is the sum of the weights of edges E 18 -E 78 . 
     In the illustrated embodiment, the virtual processors are then arranged into “isolated” communities. Thus, the sixty-four virtual processors of system AP 1 , can be divided into several communities, one of which, community  44 , is shown in  FIG. 1 . A community is “isolated” when none of its processors are connected by an edge having more than a zero or other negligible weight. Within each of the communities formed at method segment M 12 , each virtual processor in the community is connected to at least one other virtual processor in the community by an edge with significant weight. 
     Method segment M 13  involves identifying a “new” proximity that is the proximity with the largest available “capacity”, i.e., the greatest number of physical processors that have not been already been assigned to virtual processors (in the current iteration of method ME 1 ). Where, as will commonly be the case initially, many proximities have the same number of available processors, the selection of the “new” proximity can be arbitrary. However, the selection becomes less arbitrary as virtual processors are assigned to proximities and available capacities are reduced. This greatest available number of processors in any proximity determines 1) whether or not a selected community can fit into a proximity, and 2) if not, the size (number of virtual processors in) of a group to be “carved out of” the community and assigned to that proximity. 
     At method segment M 14 , the largest community is selected. In case of ties, the community with the greatest total edge weight can be selected. Other embodiments employ other criteria to sequence community selections. If this “new” community fits the current proximity (i.e., the new proximity of method segment M 13 ), it is assigned to that proximity at method segment M 15 . In other words, each virtual processor of the current community is assigned to a physical processor of the current proximity. 
     If the current community does not fit in the current proximity, a new group of virtual processors from the current community will be formed that matches the available capacity of the current proximity. The group can be formed one virtual processor at a time. The first virtual processor to be assigned, at method segment M 16 , to the current group is the “heaviest” virtual processor, i.e., the virtual processor with the greatest weight in the current community. 
     If the current size of the group being formed is less than the (largest available) capacity of the current proximity, the remaining virtual processor (i.e., in the current community but not yet assigned to the current group) with the most interaction with the heaviest member of the group is assigned to the group at method segment M 17 . Method segment M 17  is repeated until the current group size matches the available capacity of the current proximity. In a variation, the virtual processor with the most total interaction with previously assigned members of the group is added to the group. 
     Once the group size matches the available capacity of the current proximity, the current group is assigned to the current proximity at method segment M 4 , with the assignment of virtual processors to physical processors being arbitrary. In an alternative embodiment, slight differences in intra-proximity communications speeds are taken into account in assigning virtual processors to physical processors. 
     Method ME 1  returns to method segment M 13  for the next recursive iteration. A new proximity is likely to be picked because the capacity of the previous proximity will have been filled or at least reduced in the previous iteration. The community selected at method segment M 12  will likely not be the previous community, as any members of a community that have already been assigned to physical processors are not considered as part of the community for purposes of the recursive steps. 
     In another variation of method ME 1 , method segment M 3  is implemented differently, as flow-charted in  FIG. 5 . Method segments M 11 -M 15  are basically unchanged, but method segments M 16  and M 17  of  FIG. 4  are replaced by method segments M 26  and M 27  of  FIG. 5 . At method M 26   m  if the current community does not fit into the current proximity, the lightest virtual processor is removed from the current community. If the resulting current community (group) size is less than the available capacity of the current proximity, the virtual processor weights are recalculated at M 27 . In the recalculation, the edge weights associated with virtual processors that have been removed from the community are not taken into account. Method ME 1  then returns to method segment M 26  to remove the virtual processor with the lightest weight as just recalculated. 
     Once the community size has been pared down to the available capacity of the current proximity, the current community is assigned to the current proximity at method segment M 4 . In the variation of  FIG. 5 , method ME 1  returns to method segment M 12 , which involves arranging the virtual processors into isolated communities. This is done to accommodate virtual processors that have been removed from communities in previous iterations of method segment M 26 . In the illustrated variation, all virtual processors removed from a community are arranged into a single community, even though this may mean one or more virtual processors may not have significant interactions with any other virtual processors in the community. In another subvariation, the virtual processors removed from a community are arranged into as many communities as are necessary to ensure that each processor in a community has significant expected interaction with at least one other virtual processor in its community. 
     For an example regarding system AP 1 , virtual processors VP 1 , VP 7 , and VP 8  have initial weights of 2.5 each. All other virtual processors VP 2 -VP 6  have initial weights of 1.5 each. The first proximity can be proximity  12 B and the first virtual processor removed can be virtual processor VP 2 . The weights of remaining virtual processors VP 1  and VP 3 -VP 8  are then recomputed. Virtual processors VP 1 , VP 3 , and VP 4  each get 0.5 lighter as a result of the removal of virtual processor VP 2 . Thus, the recalculated weight of virtual processor VP 1  is 2.0, and the recalculated weights of virtual processors VP 3  and VP 4  are both 1.0. Thus, virtual processors VP 3  and VP 4  will be removed in the next two iterations of method segment M 26 . By the end of the third iteration of method segment M 27 , virtual processor VP 1  has a weight of 0.0, so it is removed in the fourth iteration. Now the current community fits and is assigned to proximity  12 B at method segment M 4 . Upon the return to method segment M 12 ,  FIG. 5 , removed virtual processors VP 1 -VP 4  are formed into a community, which can be assigned to proximity  12 A, as indicated in  FIG. 1 . 
     Other constraints and factors can affect the assignment of threads to physical processors. For example, system AP 1  can be a 64-processor system, with the processors arranged in eight eight-processor cells. Each cell can include memory media that can be accessed more rapidly by local processors (of the same cell) than by remote (from other cells) processors. 
     In general, spinlock cache access from the same bus can be 2-3 times faster than remote cache access. Well-written programs spend less than 2 percent of their time pended on locks, the net benefit can be on the order of 5 percent, which is a significant measurable gain from a software change. The described and other variations upon and modifications to the illustrated embodiment are within the scope of the following claims.