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

fYear

2003

fDate

6-9 Oct. 2003

Firstpage

164

Lastpage

170

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing Workshops, 2003. Proceedings. 2003 International Conference on

ISSN

1530-2016

Print_ISBN

0-7695-2018-9

Type

conf

DOI

10.1109/ICPPW.2003.1240367

Filename

1240367