When a job reaches the head of the queue and there are not enough free processors to satisfy its request, we calculate n', the number of additional processors required. We then consider the number of jobs in the system with cluster sizes greater than n'; that is, the jobs that will single-handedly satisfy the request if they complete.
In our simulations, the number of processors required tended to be small (50% below 16), and thus the number of potential benefactors was often large (75% of the time there are 3 or more). Under these circumstances, we expect Predictor A to perform well. Table 3 shows the average and median values of n' and the number of benefactors.
Table 3
Of the 8545 times that a job waited at the head of the queue, 393 times it found no jobs running that could satisfy the request. Under these circumstances, Predictor A cannot make a prediction.
The remaining 8152 predictions are shown in Figure 4, which is a scatter plot of predicted times on the x-axis and actual queue times on the y-axis. There is a clear correlation between the predicted and actual values; the coefficient of correlation (CC) between them is 0.63.
Figure 4: Scatterplot of actual queue times and predictions calculated by
Predictor A. The white line shows the
identity function; i.e. a perfect predictor. The solid line shows the
average of the actual queue times in each column. The broken line
shows the median.
The solid line in the figure shows the mean of the actual queue times in each column; the broken line shows the median. For predicted values between 5 seconds and 3000 seconds, the mean and median values closely follow the 45-degree line, indicating that the predictions are accurate, at least on average. For predicted values greater than 3000 seconds, the predictions tend to be too high. This bias reflects the inherent conservative nature of the approximation: the predictor ignores the possibility of multiple jobs completing in order to fulfill a request. When there are few jobs that can satisfy a request single-handedly, the predictions tend to be too high.
Throughout the range, the median and mean are similar, indicating that the distribution of actual queue times in each column is roughly symmetric. In other words, for a given prediction, the actual queue time is equally likely to be higher or lower by a given amount.