In this paper we review existing loop scheduling algorithms andalso describe the feedback-guided dynamic loop scheduling (FGDLS)algorithm that was proposed in Bull et al. (1996) and Bull (1998). TheFGDLS algorithm uses a feedback mechanism to schedule a parallel loopwithin a sequential outer loop. It has been shown to perform well forscheduling problems for which the load associated with the parallel loopchanges relatively slowly as the outer sequential loop executes. Howeverthe question of convergence of the FGDLS algorithm has remained an openquestion. In this paper we are able to establish sufficient conditions(essentially requiring that the workload does not change too rapidlywith loop iteration count) for the (global) convergence of a continuousanalogue of the feedback-guided algorithm
展开▼
