Optimized Distributed Work-Stealing
Optimized Distributed Work-Stealing
复制标题
优化的分布式工作窃取
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yili Zheng
中科院分区：
文献类型：
--
作者：
Vivek Kumar;K. Murthy;Vivek Sarkar;Yili Zheng
工作窃取是任务并行程序动态负载平衡的一种流行方法。然而，正如已经广泛研究的那样，在大规模并行和分布式超级计算机上使用经典的工作窃取算法会带来几个性能问题。一个这样的问题是失败窃取的开销(与没有工作的受害者通信)，这在分布式环境中比在单个SMP节点内严重得多。由于节点间通信的开销，在分布式环境中减少失败的窃取次数至关重要。针对负载感知的分布式工作窃取算法在HabaneroUPC++PGAS库中的两种不同的负载感知实现--BaselineWS和SuccessOnlyWS。BaselineWS遵循实现分布式工作窃取策略的先前工作。SuccessOnlyWS实现了一种新颖的分布式工作窃取策略，该策略通过引入新的策略将工作从繁忙的处理器转移到空闲的处理器，从而完全消除节点间的失败尝试。此策略还可以避免多次查询同一个处理器，从而导致窃取失败。我们通过使用Cray-XC30超级计算机爱迪生的多达12288个内核并使用动态不规则应用程序来评估BaselineWS和SuccessOnlyWS，如UTS和NQueens基准测试所示。我们演示了SuccessOnlyWS比BaselineWS提供高达7%的性能改进。
Work-stealing is a popular approach for dynamic load balancing of task-parallel programs. However, as has been widely studied, the use of classical work-stealing algorithms on massively parallel and distributed supercomputers introduces several performance issues. One such issue is the overhead of failed steals (communicating with a victim that has no work), which is far more severe in the distributed context than within a single SMP node. Due to the cost of inter-node communication, it is critical to reduce the number of failed steals in a distributed context. Prior work has demonstrated that load-aware victim processor selection can reduce the number of failed steals, but it cannot eliminate the failed steals completely.In this paper, we present two different load-aware implementations of distributed work-stealing algorithm in HabaneroUPC++ PGAS library — BaselineWS and SuccessOnlyWS. BaselineWS follows prior work in implementing a distributed work-stealing strategy. SuccessOnlyWS implements a novel distributed work-stealing strategy that completely eliminate inter-node failed attempts by introducing a new policy for moving work from busy to idle processors. This strategy also avoids querying the same processor multiple times with failed steals. We evaluate both BaselineWS and SuccessOnlyWS by using up to 12288 cores of Edison, a CRAY-XC30 supercomputer and by using dynamic irregular applications, as exemplified by the UTS and NQueens benchmarks. We demonstrate that SuccessOnlyWS provides performance improvements up to 7% over BaselineWS.