Predicting the Benefits of Mixed Data and Task Parallelism
       Soumen Chakrabarti  James Demmel  Katherine Yelick 

Mixed task and data parallelism exists naturally in many applications,
but utilizing it may require sophisticated scheduling algorithms and
software support.  Recently, significant research effort has been
applied to exploiting mixed parallelism in both theory and systems
communities.  In this paper, we ask how much mixed parallelism will
improve performance in practice, and how architectural evolution
impacts these estimates.  First, we build and validate a performance
model for a class of mixed task and data parallel problems based on
machine and problem parameters.

Second, we use this model to estimate the gains from mixed parallelism
for some scientific applications on current machines.  This quantifies
our intuition that mixed parallelism is best when either communication
is slow or the number of processors is large.  Third, we show that,
for balanced divide and conquer trees, a simple one-time switch
between data and task parallelism gets most of the benefit of general
mixed parallelism.  Fourth, we establish upper bounds to the benefits
of mixed parallelism for irregular task graphs.  Apart from these
detailed analyses, we provide a framework in which other applications
and machines can be evaluated.