Cyclic staggered scheme: a loop allocation policy for DOACROSS loops

Author

Hurson, A.R. ; Kavi, K. ; Lim, J.T.

Author_Institution

Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA

Volume

47

Issue

2

fYear

1998

fDate

2/1/1998 12:00:00 AM

Firstpage

251

Lastpage

255

Abstract

Within the scope of the multithreaded dataflow, the problem of scheduling/allocation of DOACROSS loops has been discussed and it was shown that the so called staggered allocation offers higher performance and resource utilization than other schemes described in the literature. The staggered scheme, however, produces an unbalanced load among processors. The paper introduces an extension to the staggered scheme-cyclic staggered scheme-that produces a more balanced distribution of iterations among processors. The cyclic staggered scheme is simulated and its performance improvement is analyzed

Keywords

parallel architectures; parallel programming; processor scheduling; resource allocation; DOACROSS loops; cyclic staggered scheme; loop allocation policy; multithreaded dataflow; performance improvement; resource utilization; scheduling/allocation; staggered allocation; unbalanced load; Analytical models; Computational modeling; Computer science; Delay; Load management; Parallel processing; Performance analysis; Process control; Processor scheduling; Resource management;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.663774

Filename

663774