Modeling the benefits of mixed data and task parallelism
Modeling the benefits of mixed data and task parallelism
复制标题
DOI：
10.1145/215399.215423
复制
发表时间：
1995-07
期刊：
影响因子：
--
通讯作者：
Soumen Chakrabarti;J. Demmel;K. Yelick
中科院分区：
文献类型：
--
作者：
Soumen Chakrabarti;J. Demmel;K. 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 practzce, and how architectural evolution impacts these est imat es. 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.