OREGON STATE UNIVERSITY

You are here

Towards the Precise Determination of DOACROSS Performance

TitleTowards the Precise Determination of DOACROSS Performance
Publication TypeReport
Year of Publication2009
AuthorsZier, D. A., and B. Lee
Date Published12/2009
Keywordsmultithreading, parallel
Abstract

This paper explores the effects that regular, inter-iteration dependencies have on the total parallel execution time of a DOACROSS loop from a theoretical perspective. This work finds that the total parallel execution time of a DOACROSS loop is directly proportional to a single, dominate dependency and that additional dependencies may only produce small additional time cost due to initial synchronization. The result of this analysis is an efficient algorithm capable of calculating an exact upper bound for the total parallel execution time of a loop with any number of dependencies. With knowing how to determine the exact total parallel execution of a loop, a simple, platform independent, speedup metric is proposed and is shown that the absolute upper bound on the speedup of a loop is directly proportional to the dependency depth and inversely proportional to the synchronization distance of the dominate dependency. This paper also explores the effects that a finite number of processors have have on the parallel performance of a loop.