Concluding remarks

In this chapter, the performance of a threshold-based policy for reducing delay in cycle stealing is studied via dimensionality reduction (DR), as its analysis involves multidimensional Markov chains. DR allows us to evaluate the mean response time under a wide range of parameter settings, and this leads to many insights into the characteristics and performance of cycle stealing.

Our analysis shows that cycle stealing can provide unbounded benefit even under high switching costs. The unbounded benefit stems from the increased stability region under cycle staling, and we have provided the necessary and sufficient condition for the stability under the threshold-based policy for reducing delay in cycle stealing. Interestingly, we find that the beneficiary side threshold, $N_B^{th}$, does not affect the stability region, but increasing the donor side threshold, $N_D^{th}$, increases the stability region. We also find that the impact of changes in $N_D^{th}$ on mean response time is more dramatic than the impact of changes in $N_B^{th}$

Switching times (both $K_{sw}$ and $K_{ba}$) also affect the stability region (of the beneficiary jobs), and they also have a significant impact on the mean response time when the beneficiary is overloaded without cycle stealing ($\rho_B \geq 1$). However, when $\rho_B < 1$, we find that whereas the mean response time of the donor jobs is still sensitive to the switching times, the mean response time of the beneficiary jobs is far less sensitive.

An advantage of the analysis via DR is that the job sizes can be modeled as a PH distribution. This allows us to study the impact of job size variability on performance. In particular, we study the impact of the variability of the donor job sizes on the mean response time of the beneficiary jobs. We find that the impact is surprisingly small when $\rho_B < 1$. This is in parallel to our findings in Chapter 5, where we find that the variability of the long job sizes has a surprisingly small impact on the mean response time of the short jobs under SBCS-ID (size-based task assignment with cycle stealing under immediate dispatching).

In this chapter, we limit our discussion to a particular multiserver system, but the analysis via DR can be extended to other multiserver systems in various ways. For example, we do not need to require that the donor switches back immediately when $N_D^{th}$ is reached; we can allow the donor to first complete the beneficiary job in progress. Completing the beneficiary job obviates the need for checkpointing the job; however it sometimes reduces system performance, particularly when beneficiary jobs have higher variability than donor jobs. We found that this change has almost no effect on performance, even under long switching times (see [150]). It is also easy to generalize our analysis to the case where the beneficiary requires a ``switching time'' before it can resume a job that the donor started, and to the case where the donor must complete the beneficiary job in progress before it switches back.

Another interesting case is where servers function as both beneficiaries and donors (two way cycle stealing), as in [180]. Since the two way cycle stealing does not appear to be modeled as a GFB process, DR does not allow us to analyze this model. In [180], the state of each processor is assumed to be stochastically independent and identical to the state of the other processors; i.e. a multidimensional Markov chain is decomposed into 1D Markov chains. In theory, the analysis of the two way cycle stealing can be reduced to a boundary value problem (see Section 3.3), but this leads to a complex expression whose evaluation often experiences numerical instability. It would be interesting to pursue how computational approaches such as DR can be applied to an analysis of the two way cycle stealing.