Dynamic partitioning of parallel Lisp programs
Dynamic partitioning of parallel Lisp programs
复制标题
并行 Lisp 程序的动态分区
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Eric Mohr
中科院分区：
文献类型：
--
作者：
Eric Mohr
许多并行算法最容易在细粒度级别上表示，但大多数并行系统不能有效地执行细粒度程序。为了提高效率，研究人员经常通过将许多潜在的并行操作组合到单个顺序线程中来增加并行任务的粒度。大多数研究人员都依赖于程序员或并行编译器作出这样的分区决定，这项工作探讨了在运行时动态分区的替代方法。动态分区可以通过消除程序员对显式分区的需要来简化并行程序，并且可以产生比编译时方法更好的分区，编译时方法必须提前预测程序执行路径和成本。
提出并分析了两种动态分区策略：基于负载的分区（LBP），其中任务根据动态负载水平进行组合，以及惰性任务创建（LTC），其中任务仅在处理资源可用时追溯创建。以前已经提出过基于负载的分区等方法;在这里，我描述了这种方法的几个缺陷，并展示了惰性任务创建如何在理论上和实践中克服这些缺陷。特别是，惰性任务创建永远不会引入死锁或恶化负载平衡，这在一些基于负载的分区的程序中可能发生。惰性任务创建始终比基于负载的分区创建的任务少得多。
LTC相对于LBP的优势在于，LTC延迟了所有划分决策，因此可以在LBP做出不幸且不可撤销的划分决策的情况下灵活地恢复。此外，当延迟分区决策时，LTC只执行最少的一组操作，允许令人惊讶的低运行时开销。这组操作比相关方法中的操作要小得多，因为关键的设计决策是在潜在的分叉点延迟父任务而不是子任务。
我提出了一个成功的实现懒惰的任务创建的细节Mul-T，一个高效的并行版本的计划上运行的共享内存的Encore Multimax。Encore Mul-T的测试结果表明，绝对性能和相对加速比都相当不错的一套并行Lisp基准程序运行的动态分区。
Many parallel algorithms are most easily expressed at a fine level of granularity, but most parallel systems cannot execute fine-grained programs efficiently. In search of efficiency, researchers often work to increase the granularity of parallel tasks by grouping a number of potentially parallel operations together into a single sequential thread. Most researchers have relied on either the programmer or a parallelizing compiler to make such partitioning decisions; this work explores the alternative approach of dynamic partitioning at runtime. Dynamic partitioning can simplify parallel programs by eliminating the need for explicit partitioning by the programmer and can produce a better partition than compile-time methods which must predict program execution paths and costs in advance.
Two dynamic partitioning strategies are presented and analyzed: load-based partitioning (LBP), where tasks are combined based on dynamic load level, and lazy task creation (LTC), where tasks are created only retroactively as processing resources become available. Methods like load-based partitioning have been proposed before; here I describe several deficiencies of the approach and show how lazy task creation overcomes them, both theoretically and in practice. In particular, lazy task creation will never introduce deadlock or worsen load balancing, as can happen in some programs with load-based partitioning. And lazy task creation consistently creates significantly fewer tasks than load-based partitioning.
The advantage of LTC over LBP arises because LTC delays all partitioning decisions and thus can recover flexibly in situations where LBP has made an unfortunate and irrevocable partitioning decision. Further, LTC performs only a minimal set of operations when delaying a partitioning decision, allowing surprisingly low runtime overhead. This set of operations is much smaller than in related approaches because of the key design decision to delay the parent task rather than the child task at potential fork points.
I present details of a successful implementation of lazy task creation in Mul-T, an efficient parallel version of Scheme running on the shared-memory Encore Multimax. Measurements of Encore Mul-T demonstrate that absolute performance and relative speedup are both quite good for a suite of parallel Lisp benchmark programs run with dynamic partitioning.