A Convergence Proof of FGDLS when the Workload is Monotous

Published in Volume XI, 2002, p. 132-141

Author(s): Tatiana TABIRCA, Len FREEMAN, Sabin TABIRCA

Abstract

In this paper we consider convergence of the feedback-guided dynamic loop scheduling (FGDLS) method that was proposed in Bull et al.~ \cite{BullFD} and Bull \cite{Bull}. The method uses a feedback-guided mechanism to schedule a parallel loop within a sequential outer loop. Computational studies have shown that the loop bounds defined by the method are convergent (for a constant workload or for a workload that changes only slowly with the outer sequential loop) to the optimal loop partition. In an earlier paper \cite{Tab2001b} we established formally that the FGDLS algorithm is guaranteed to converge, for a constant workload, provided that the variations in workload with iteration index are bounded. In this paper we extend this analysis to establish convergence of the method when the workload is monotone with iteration index.