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 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.
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
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.
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.
To restate, the hypothesis is:
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.
The experiments in appendix A evaluate the performance of the initial placement algorithms.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
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.