Using early phase termination to eliminate load imbalances at barrier synchronization points
Using early phase termination to eliminate load imbalances at barrier synchronization points
复制标题
使用早期阶段终止来消除屏障同步点处的负载不平衡
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Rinard
中科院分区：
文献类型：
--
作者：
M. Rinard
我们提出了一种新的技术，早期阶段终止，用于消除空闲的处理器在并行计算中使用屏障同步。这种技术简单地终止每个并行阶段，只要有太少的剩余任务，使所有的处理器忙碌。虽然这种技术完全消除了在屏障同步点处可能发生的空闲，但它也可能改变计算，从而改变计算产生的结果。我们通过提供概率失真模型来解决这个问题，该模型描述了早期相位终止的使用如何使计算产生的结果失真。我们的实验结果表明，对于我们的一组基准应用程序，1）早期相位终止可以提高并行计算的性能，2）失真很小（或可以使用适当的补偿技术变得很小）和3）失真模型提供准确和严格的失真范围。这些界限可以使用户能够评估早期相位终止的效果，并且如果他们发现失真界限是可接受的，则可以自信地接受来自使用该技术的并行计算的结果。最后，我们确定了一个一般的计算模式，以及早期阶段终止，并解释为什么计算表现出这种模式可以容忍的并行任务的提前终止，而不会产生不可接受的结果。
We present a new technique, early phase termination, for eliminating idle processors in parallel computations that use barrier synchronization. This technique simply terminates each parallel phaseas soon as there are too few remaining tasks to keep all of the processors busy. Although this technique completely eliminates the idling that would other wise occur at barrier synchronization points, it may also change the computation and therefore the result that the computation produces. We address this issue by providing probabilistic distortion models that characterize how the use of early phase termination distorts the result that the computation produces. Our experimental results show that for our set of benchmark applications, 1) early phase termination can improve the performance of the parallel computation, 2) the distortion is small (or can be made to be small with the use of an appropriate compensation technique) and 3) the distortion models provide accurate and tight distortion bounds. These bounds can enable users to evaluate the effect of early phase termination and confidently accept results from parallel computations that use this technique if they find the distortion bounds to be acceptable. Finally, we identify a general computational pattern that works well with early phase termination and explain why computations that exhibit this pattern can tolerate the early termination of parallel tasks without producing unacceptable results.