Abstract:
SP (series-parallel) structured programming models are quite attractive
from programming, cost estimation, and scheduling point of view.
Expressing a parallel computation of which the DAG is non-SP
within the restrictive SP synchronization framework, however,
may introduce a loss of parallelism. Recently, it has been shown
that this loss of parallelism is often limited to tens of percents
which makes SP programming a viable option. In that research
we have introduced an analytic cost model that is capable to predict
the effects of DAG topology on the execution time of the computation.
While in previous research we have applied this model at the
programming level to substantiate the earlier claims, it appears
that the model can also be used at the implementation level
to predict or explain the sometimes surprising performance effects
of mapping decissions and specific language or library implementation
details.
In this paper we describe this cost modeling approach and demonstrate
its use in predicting various performance effects of real applications
having either restricted and non-restricted synchronization structures.