深入调度
深入调度¶
注意：此技术文档未针对用户可读性进行优化。
大多数 dask 集合使用的默认共享内存调度器位于 dask/local.py 中。该调度器在有新工作线程可用时动态调度任务。它在共享内存环境中运行，不考虑数据局部性，所有工作线程都可以平等地访问所有数据。
我们发现，通过尽量减少内存占用，我们的工作负载能得到最佳服务。本文档讨论了我们在每任务一毫秒的调度预算内，实现这一目标的政策，无论任务数量多少。
通常我们面临以下情况：一个工人带着一个新完成的任务到达。我们更新执行状态的数据结构，并且需要为该工人提供一个新任务。通常有很多可用的任务，我们应该给工人哪一个任务？
问：我们应该把我们可用的任务中的哪一个交给新准备好的工人？
这个问题简单且局部，但却对我们的算法性能有重大影响。我们希望选择一个任务，让我们现在和未来都能释放内存。我们需要一种聪明且廉价的方法来打破可用任务集之间的平局。
在这个阶段，我们选择“后进先出”的政策。也就是说，我们选择最近变得可用的任务，很可能是由刚刚返回的工作者提供的。这鼓励了在开始新事物之前完成事物的总体主题。
我们通过一个栈来实现这一点。当一个工人带着完成的任务到达时，我们根据新数据确定可以计算哪些新任务，如果有的话，将这些任务放在栈顶。我们从栈顶弹出一个项目，并将其交付给等待的工人。
然而，如果新完成的任务使多个新任务准备就绪，我们应该按什么顺序将它们放在栈上？这是另一个打破平局的机会。这在执行的*开始*阶段尤为重要，我们通常会在栈上添加大量叶子任务。我们在这种平局中的选择也会在许多情况下强烈影响性能。
我们希望鼓励深度优先的行为，即如果我们的计算由许多树组成，我们希望在转向下一棵树之前完全探索一棵子树。这鼓励我们的工作者在转向新的块/子树之前完成图的块/子树。
为了鼓励这种“深度优先行为”，我们进行深度优先搜索，并根据深度优先搜索（DFS）遍历中的编号对所有节点进行编号。我们使用这个编号来在将任务添加到堆栈时打破平局。请注意，虽然我们在上面讨论了优化许多不同子树的情况，但这个选择完全是局部的，并且在这个情况之外也相当普遍地适用。任何行为与许多不同子树情况相似的事物都将相应地受益，这种情况在正常工作负载中相当常见。
然而，我们忽略了另一个打破平局的方法。在进行深度优先搜索时，当我们到达一个有多个子节点的节点时，我们可以选择遍历子节点的顺序。我们通过选择那些其结果被最多节点依赖的子节点来解决这个平局。这种依赖可以是直接的，对于那些将该数据作为输入的节点，也可以是间接的，对于图中的任何祖先节点。这强调首先遍历那些是关键路径一部分的节点，这些路径具有长垂直链，依赖于此节点的结果，以及那些其数据被未来许多节点依赖的节点。我们选择在深度优先搜索中首先深入这些子树，以便未来的计算不会因为等待它们完成而被卡住。
因此我们有三个决胜局
Q: 我应该运行这些可用任务中的哪一个？
A: 后进先出
Q: 我应该先把哪个任务放在堆栈上？
A: 在计算之前进行深度优先搜索，使用该顺序。
Q: 在进行深度优先搜索时，我应该如何选择子节点？
选择那些依赖最多数据的子节点
我们已经发现了一些常见的流程类型，这些类型需要每一种决策。在数据分析中，我们尚未遇到一种常见图形类型，这些图形类型在最小化内存使用的目的下，不能被这些启发式方法很好地处理。