Title :
An O(p + log p) algorithm of discrete FGDLS
Author :
Tabirca, Tatiana ; Tabirca, Sabin ; Freeman, Len ; Yang, Laurence Tianruo
Author_Institution :
Dept. of Comput. Sci., Univ. Coll. Cork, Ireland
Abstract :
Feedback guided dynamic loop scheduling (FGDLS) is a recent dynamic method (Bull, 1998) that aims to schedule a parallel loop within a sequential outer loop. The method uses the feedback from the execution times of the current parallel loop to guide the scheduling of the next parallel loop. In this paper we propose an O(p + log p) algorithm for the FGDLS method in the discrete case. This approach applies the balanced workload scheduling (Tabirca et al., 2002) to the piecewise constant workloads to obtain the iteration bounds.
Keywords :
computational complexity; parallel algorithms; piecewise constant techniques; processor scheduling; program control structures; resource allocation; O(p + log p) algorithm; balanced workload scheduling; discrete FGDLS; feedback guided dynamic loop scheduling; iteration bounds; parallel loop; sequential outer loop; Computer numerical control; Computer science; Dynamic scheduling; Educational institutions; Feedback loop; Integral equations; Parallel processing; Performance loss; Processor scheduling; Scheduling algorithm;
Conference_Titel :
Parallel Processing Workshops, 2003. Proceedings. 2003 International Conference on
Print_ISBN :
0-7695-2018-9
DOI :
10.1109/ICPPW.2003.1240367
