Results and Analysis

All of the experimental results are presented in appendices A through D. The importance of these results lie in the overall reaction of the algorithms to a variety of workloads and test parameters. Hence no results are brought forward into this chapter, but rather references are made to individual and ranges of results in the appendices.

Figure 

 
Figure 9.2: The layout of the results in appendices A through D.

The appendices represent only a fraction of the experimental space described in section 9.2.3. In particular, each graph has only one variable parameter, requiring the remaining parameters to be fixed. Table 

 
Table 9.2: The fixed input parameters.

The fixing of these parameters deserves explanation, especially when different values could produce different results.

• Fixing Mobility: The question for graphs *.*.4 is whether selecting a different workload mobility would affect the gradient (the significant result) as the fixed transfer cost is varied. Figure 

   
  Figure 9.3: The gradient is constant over a large range of workload mobilities.
  

• Fixed Transfer Cost: The transfer cost is fixed for graphs *.*.2 and *.*.3. From figure 

   
  Figure 9.4: The least loaded algorithm exhibits overdistribution at varying thresholds during the heaviest workload period .
  

  This reliance on a `tunable' threshold indicates a less than satisfactory aspect of the more primitive algorithms, where the best threshold varies with the workload. Thus figure 

Prediction

The prediction mechanism is common to all algorithms except for random, least loaded and hbd-mig. It is used at two different levels, firstly for estimating job and process lifetimes (average and ll-mig), and secondly for estimating the full resource demands of a job or process (wf-ip and wf-mig). There is no training prior to the start of the trace period, and previously unseen processes are always executed locally. A caveat is that this may initially discriminate against the algorithms using the prediction mechanism.

Graphs

All graphs were produced using the Splus statistical package, and consist of twenty data points for each algorithm, smoothed using running medians. Consequently, different neighbouring points (context) may produce a different smoothed value, and this is responsible for the differences between plotted values where the parameters coincide.

The Process Mix Hypothesis

 

To restate, the hypothesis is:

• Process Mix: The distribution of a balanced mix of CPU, memory and IO bound processes to each host will lead to the more effective use of resources and delay the onset of bottlenecking.

To support this hypothesis, a more effective use of resources needs to be shown by the algorithms which maintain a balanced process mix. This is most visible in a reduction of the average response time compared to algorithms which do not maintain a balanced process mix.

The process mix of a system can be maintained using either initial placement or process migration, and therefore both of these approaches need to be examined to fully, to determine the support for the hypothesis. For reasons of clarity I will treat them separately, and leave the question of which transfer mechanism performs better, until the discussion of the initial placement hypothesis in section 9.3.5.

Maintaining the Process Mix with Initial Placement

The experiments in appendix A evaluate the performance of the initial placement algorithms.

Results:

• Graphs A.*.1 show that in six of the eight cases wf-ip clearly has the lowest average batch job response time over a mobility range of approximately . Of the remaining two graphs, A.4.1 shows indistinguishable performance between average and wf-ip, while wf-ip has a marginally lower average batch job response time over the mobility range of in graph A.7.1. Overall, the performance advantage over random is large, and over average the advantage is smaller, but consistently in favour of wf-ip.

  Wf-ip suffers least from overdistribution, showing an increase with a workload mobility greater than 0.8 in only three test sets, as opposed to average, which exhibits an increase in all eight test sets. This suggests that the wf-ip algorithm is less susceptible to the threshold parameter.

• Graphs A.*.2 show that the standard deviation of the batch job response times is reduced as the workload mobility increases, although again, in some situations there is an increase when the algorithm overdistributes. However, wf-ip is only better in three graphs, with the remaining five outcomes undecided.

  One anomaly worth noting, is that graph A.7.1 shows a reduction in the average response time of approximately 50%, however graph A.7.2 only shows a reduction in the standard deviation of approximately 25%. This is substantially less than the expected improvement based on the average response time.

• Graphs A.*.3 show two clear groups of algorithms, those with and those without candidate selection policies. The three algorithms with candidate selection use the same policy, and exhibit a very similar number of remote executions.
• Graphs A.*.4 show that the two classes of algorithms identified in A.*.3 have correspondingly different gradients as the fixed transfer cost increases. The gradients of the algorithms without a candidate selection policy are greater, and perform worse than no load distribution at a lower fixed cost, examples are graphs A.2.4, A.6.4, and A.8.4.

  The only other notable feature between the five algorithms is shown in graph A.3.4, where the two predictive fitting algorithms (wf-ip and ff-ip) are more stable than the others. Graph A.3.3 shows that average initiates roughly the same number of remote executions as the two fitting algorithms, and therefore the candidate selection policy is not at fault, but rather the location selection policy. However, one result is insufficient to draw a firm conclusion.

• Graphs A.*.5 in indicate that the standard deviation of the response times increases only minimally as the fixed transfer cost increases. There is no obvious separation of the algorithms based on their candidate selection policies as was evident in graphs A.*.4.

Conclusions:

Random, while gaining a large improvement in performance over no load balancing, produced less consistent and poorer average response times than wf-ip. Average represents the closest competitor to wf-ip, tying one test set and remaining within five to eight percent in all but two of the remaining sets. The best performance for wf-ip was approximately fifteen percent better than average, evident in two test sets at workload mobility of 1.

Thus the performance premium is not high, however, it is sufficient for supporting the hypothesis. In practical terms, the algorithm offers better consistency over a range of workloads, and is less susceptible to overdistribution.

Thus I will conclude that the process mix hypothesis is supported for initial placement.

Maintaining the Process Mix with Process Migration

The flexibility of process migration encourages a larger number of possible algorithms, and choosing which is more effective requires them to be evaluated on the testbed.

Selecting a wf-mig Algorithm

The numbering of the wf-mig algorithms shown in graphs appendix B does not relate directly to their order in chapter 8, the translation to the experimental numbering is shown in table 

 
Table 9.3: The experimental numbering.

Results:

• Graphs B.*.1 show that wf-mig 4 has the worst response time for five of the eight test sets. Algorithm wf-mig 3 has the lowest response times in graphs B.4.1 and B.5.1, with the remaining graphs providing no distinction between the three highest contributing candidate algorithms.
• Graphs B.*.2 offer little distinction between the algorithms.
• Graphs B.*.3 show that wf-mig 4 consistently migrates the fewest number of processes.
• Graphs B.*.4 show that the behaviour of wf-mig 4 is inconsistent, with four graphs having different gradients to those of the highest contributing candidate algorithms. The remaining four graphs show consistent gradients.
• Graphs B.7.5 has a peculiar response for wf-mig 4, otherwise graphs B.*.5 show little helpful in distinguishing the algorithms.

Results:

It is difficult to choose between the highest contributing candidate algorithms, as all generally have very similar levels of performance. However, as wf-mig 3 shows better response time performance in two traces, it is this algorithm that is the better candidate with which to test the hypothesis. I therefore will use wf-mig 3, which is the highest contributing candidate algorithm with the use of estimation to adjust the current behaviour with the historical behaviour. For all later experiments I will simply refer to wf-mig 3 as wf-mig.

Investigating the Process Mix Hypothesis

Appendix C contains the results for the comparison of wf-mig against the two non process mix maintaining algorithms.

Results:

• Graphs C.*.1 show wf-mig produced consistently lower average batch job response times than both competitors in seven of the eight test sets, over the range of workload mobilities. The only marginal result was for test set eight, where wf-mig was better over the more restricted mobility range of .
• Graphs C.*.2 produce no conclusive results for any one algorithm.
• Graphs C.*.3 show that wf-mig consistently has the highest number of migrations.
• Graphs C.*.4 show that all three migration algorithms have similar gradients in response to the increase in the fixed transfer cost, even with wf-mig migrating more processes.
• Graphs C.*.5 produce no conclusive results for any one algorithm.

Conclusions:

The wf-mig algorithm shows a consistently better average response time in graphs C.*.1, over a large range of workload mobilities. The higher number of migrations performed by wf-mig does not reduce its performance with respect to the other migration algorithms, as the fixed transfer cost is increased. Therefore these results strongly support the process mix hypothesis for process migration.

All algorithms reduce the standard deviation of response times, and no one algorithm stands out as performing better in this regard.

The Prediction Accuracy Hypothesis

• Prediction Accuracy: Perfect prediction accuracy is not required nor realistic, a reasonable estimate is sufficient for good performance.

Average is quite a weak predictor when applied to workload resource demands, as it exhibits a large standard deviation [LO86, DI89]. However, the results of test sets A.* show that even this weak form of prediction gives good performance when coupled with wf-ip. Whilst this supports the hypothesis by implication, the relationship between prediction quality and performance is still unknown. This deserves further work and is discussed further in chapter 10.

The Initial Placement Hypothesis

 

• Initial Placement:

  Initial placement can use prediction to attain performance comparable to that of process migration.

The previous sections have found that both process migration and initial placement are improved by maintaining a balanced process mix. Graphs D.* compare these two approaches, and also show the results of a combined metric which is discussed later in section 9.3.6.

Results:

• Graphs D.*.1 show wf-ip has the lowest response time with four test sets, wf-mig produces the lowest response times in two, while the remaining two are too marginal to decide.
• Graphs D.*.2 show that wf-ip consistently gives the lowest standard deviations.
• Graphs D.*.3 show widely different behaviour between the number of candidates selected by wf-ip and wf-mig. This is inline with the expected behaviour due to the different types of distribution candidates selected by the migration and initial placement algorithms. These graphs show that the number of remote executions generated by wf-ip decrease much more rapidly than the number of migrations initiated by wf-mig, and in three cases, wf-ip eventually transfers fewer jobs than wf-mig migrates. The interesting point is that even though the initial placement algorithm transfers fewer candidates, the performance is no worse than process migration.
• Graphs D.*.4 show no substantial difference in gradient between wf-ip and wf-mig.
• Graphs D.*.5 show that in six cases, wf-ip has dramatically better standard deviation results, up to 25% as the fixed transfer cost increases.

These results demonstrate that wf-ip does indeed perform at least as well as wf-mig, in both the average and standard deviation of response times. This conclusion also extends to the other initial placement algorithms which perform almost as well as wf-ip, showing that they are often better than the non process mix maintaining process migration algorithms.

The Combination Hypothesis

 

• Combination: Combining initial placement and process migration in a single load distribution policy, will enable placement errors to be corrected, thus improving system performance.

The combination hypothesis does not have a specific algorithm, instead the two best performing initial placement and process migration algorithms (worst fit) were run side by side.

Graphs D.1.* though D.8.* show the reaction of the combined algorithm, along with the wf-ip and wf-mig components.

Results:

The first observation is that the combined algorithm is often the average between the wf-ip and wf-mig algorithms. The only real exception is with regard to the average response time for D.7.1, where the combined algorithm results in a lower average response time than either of its component parts. Although this test set is clearly an exception, there is also a little promise evident in the graphs D.4.1 and D.6.1. This may indicate that there is perhaps some scope for future work on this - with a less naive combination of the two algorithms, however the advantage seems minimal.

The number of transfers carried out by the combined algorithm is substantially lower than the number required for wf-ip, and only slightly more than the number of transfers carried out by wf-mig. However, at some points the number of transfers is greater than either of the two component algorithms, perhaps an artifact of the simple integration of the algorithms .

The only conclusion possible is that there is insufficient evidence either way, and future work is required to resolve this problem.

Additional Observations

There are a number of observations that can be made about the algorithms and results which are not directly related to the support of the hypotheses.

• Candidate selection is important and increases in significance as placement costs increase.
• The average response time increases linearly with respect to the transfer cost over the range of 50 to 1000ms.
• The results confirm Zhou's [Zho87] finding that the average response time is concave and decreasing, as mobility increases, although with the additional note that overdistribution can result in an increase as the workload mobility approaches 100%.