Backtracking-based load balancing
Backtracking-based load balancing
复制标题
DOI：
10.1145/1504176.1504187
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
Tasuku Hiraishi;M. Yasugi;Seiji Umatani;T. Yuasa
中科院分区：
文献类型：
--
作者：
Tasuku Hiraishi;M. Yasugi;Seiji Umatani;T. Yuasa
随着包括Multicores在内的平行环境变得更加普遍，用于并行计算的高生产力语言变得更加重要。 CILK是一种语言。它为包括不规则的应用程序提供了良好的负载平衡；也就是说，它通过创建大量“逻辑”线程并采用最古老的第一笔窃取策略来使所有工人忙碌。本文提出了一个称为Tascell的“逻辑线程”的“逻辑线”，该框架可实现更高的性能，并支持更广泛的平行环境，包括群集而不会损失生产力。 Tascell工人只有在另一个闲置工人的要求时才会产生“真正的”任务。工人通过临时“回溯”并恢复其最古老的任务产生状态来执行产卵。我们的方法消除了产卵/管理逻辑线程的成本。它还可以促进工作空间的重复使用并改善参考的位置，因为它不需要为每个同时运行的逻辑线程准备一个工作区。此外，Tascell可以通过延迟的工作空间复制来实现优雅，高效的回溯搜索算法。例如，我们的16个问题解决方案求解器的速度比具有两个双核处理器的系统的CILK快1.86倍。我们的方法还使一个程序可以在具有合理效率和可扩展性的共享和分布式内存环境中运行。
High-productivity languages for parallel computing become more important as parallel environments including multicores become more common. Cilk is such a language. It provides good load balancing for many applications including irregular ones; that is, it keeps all workers busy by creating plenty of "logical" threads and adopting the oldest-first work stealing strategy. This paper proposes a "logical thread"-free framework called Tascell, which achieves a higher performance and supports a wider range of parallel environments including clusters without loss of productivity. A Tascell worker spawns a "real" task only when requested by another idle worker. The worker performs the spawning by temporarily "backtracking" and restoring its oldest task-spawnable state. Our approach eliminates the cost of spawning/managing logical threads. It also promotes the reuse of workspaces and improves the locality of reference since it does not need to prepare a workspace for each concurrently runnable logical thread. Furthermore, Tascell enables elegant and highly-efficient backtrack search algorithms with delayed workspace copying. For instance, our 16-queens problem solver is 1.86 times faster than Cilk on a system with two dual-core processors. Our approach also enables a single program to run in both shared and distributed memory environments with reasonable efficiency and scalability.