An O(log p) algorithm for the discrete feedback guided dynamic loop scheduling
Tatiana Tabirca, Sabin Tabirca, Laurence Tianruo Yang · 2006
In this paper we investigate a new algorithm for the feedback-guided dynamic loop scheduling (FGDLS) method in the discrete case. The method uses a feedback-guided mechanism to schedule a parallel loop within a sequential outer loop. The execution times and the scheduling bounds for the current outer iteration are used to find the scheduling bounds of the next outer iteration. An O(p+log p) algorithm has been proposed for the discrete case where it was proved to achieve optimal bounds in only a few iterations. This articles introduces an O(log p) algorithm for the discrete case and presents some properties of it.