只为几个可用的核心创建大量的任务是个坏主意吗？
我刚开始使用TPL进行并行编程，刚刚听完一个TPL课程。我刚刚写了一个小的演示软件来测试我对它的理解。
在问我的一般问题之前，让我解释一下我的基因编码的上下文：(如果无聊，直接跳到问题;-)
上下文：
我首先编写了一个顺序递归树，遍历递归代码(对于任何两个人状态已知的游戏)，然后尝试对其进行解析，通过在每个遍历(和评估)节点上创建并发子任务，尽可能公开并行性。(为每个子节点启动一个子任务)。从当前被评估的头节点的每个子节点发出的子树，它们通过一个已启动的并发子任务调用的相同的递归方法来评估自己。
在游戏树中，节点表示游戏位置.根节点位于当前游戏位置及其n个子节点(在第2树级上)，该根节点通过将玩家A在根位置的n个合法移动而达到的游戏位置。第三级节点通过在每个二级位置/节点上应用玩家B的合法移动来表示可到达的位置，等等，直到达到给定的最大搜索深度。
该树以深度优先遍历顺序遍历，直到给定的最大搜索深度，其中“叶”位置将由一个启发式评估函数计算，该函数返回一个整数值，表示玩家A对B在此游戏位置上的优势。这个值越大，A的位置就越好。
所有子节点的最佳值都报告给它们的公共父节点(当然，如果父节点表示由player A播放的位置，则最好的子节点是值最高的子节点，如果由player B播放，则最好的子节点是值最低的节点)。
最佳子值最终报告给根节点，第二级子节点的索引将其最佳值报告给根节点。当然，这个索引代表玩家A的“最佳”移动，这意味着向玩家A保证无论玩家B所做的移动，都可以在探索的深度(“叶”位置)达到报告的值(或更好的值)。
好的，这是众所周知的两人状态博弈的极大极小算法。
你可能也知道这种顺序算法的经典优化，称为α-β，允许修剪一些分支/子分支的游戏树，当我们知道他们没有导致有趣的叶子位置。
因此，我尝试并行这个递归树遍历，将叶值报告给根节点，并允许完全的树遍历取消(如果用户取消搜索)，但也允许部分子树任务取消来实现alpha-beta剪枝，这必须中止执行一些子节点子树的评估任务，而不需要在其他子树上互置任务。
这项工作是成功完成的，并行搜索比顺序搜索更快，并且将工作分派到所有可用的核心上，几乎总是100%地运行(根据任务管理器)。我不想用我的源代码来烦你。我只想确切地说，我还将.Net 4.5异步等待模式应用于我的递归并行化方法，并实现了“逐个等待”模式(实际上等待Task.WhenAll())来创建子任务，探索从每个子节点发出的子树。(注意:为了允许子树遍历取消，我必须向递归异步子树探测方法传递一个取消令牌列表，每个递归探测级别向列表中添加一个新的CancellationToken )。
现在您已经理解了上下文，下面是我的问题：
- 启动搜索将快速创建数百万任务，评估从每个树节点发出的数百万个子树，但实际上只有几个处理器核可以使用几个线程(每个内核一个?)来执行这些任务。因此，这是一个好主意，不考虑这一点，并创建每个子节点/子树必须评估/遍历的任务？是否没有创建更多任务所导致的开销，而不是公开最大并行性所必需的？限制已启动任务的数量不是更好吗(例如，只对最高级别的节点调用任务，对于最低级别的节点使用纯粹的顺序遍历方法)？或者，即使我们知道其中一些任务(这些任务是在最深的树节点上启动的)执行非常小的工作，我们也不能通过创建数百万个任务来关心这一点吗？
- 我没有使用lambda表达式参数(如本课程中提出的那样)阻止“通过闭包将循环索引变量传递给已启动的任务”问题，而是在启动任务并通过闭包引用此副本之前，将循环索引变量复制到本地副本变量中，而不是从lambda表达式中引用索引循环变量。你觉得这个解决办法怎么样？这和通过lambda表达式的参数一样安全吗？
- minimax算法的α-β剪枝优化是基于每个子树的顺序遍历。并行遍历降低了α-beta剪枝的效率，因为如果子节点的所有并行子树遍历几乎同时返回，则没有一个子树遍历任务会被中止，如果会的话，它们将被中止，因为它们都已几乎完成.这将极大地限制α-β优化所带来的收益。当将游戏树遍历与α-beta优化并行时，您知道解决这个问题的聪明策略吗？
回答 1
Stack Overflow用户
发布于 2015-11-11 13:58:34
关于“多少任务”的问题实际上是由两件事驱动的：
- 概念程序组织
- 任务开销
在树中为每个节点分配一个任务在概念上是干净和简单的。这是好的一面。
缺点是使用任务的理由是有效地利用并行性，而不是程序组织。当您有大量的处理器要做的工作时，您将得到最好的并行化，并且与工作相比，管理该工作的开销很小。
在节点级别选择任务的原因是很容易看到(可以说)有很多节点。在您的评论中，您指出，对于深度搜索树而言，工作单位比您预期的要少！另一个原因是你不知道一个节点需要做多少工作，所以周围有很多任务意味着一个处理器可以完成一个任务，直到完成，然后再去得到另一个任务。如果它们都有一些平均时间，处理器将执行并找到其他工作，而不会浪费大量时间等待其他工作的出现。
关键问题是开销。要“拥有”一项任务，就需要大量的开销:一些东西必须创建它，用工作填充它，然后把它放到其他处理器可以得到的工作队列中；另一个处理器必须将它从队列中提取出来，获取它的内容，而不是开销:执行它，最后取消创建它。这些开销中的每一个都需要一些计算机指令、一些内存访问(如果幸运的话)，以及处理器之间的一些昂贵的同步(不能让所有CPU同时将新任务放入可用的工作队列中)。
我不知道C# TPL的工作开销是什么。您可能可以通过编写模拟任务主体的简单循环来度量它，然后度量将该循环转储到任务中所花费的时间。我知道您希望最小化开销(我围绕这个想法设计了一种并行编程语言帕拉尼 )，并将您投入到任务中的工作最大化。
在您的例子中，我会担心节点中的工作(“生成下一个移动并对其进行琐碎的评估”)实际上并不是很多，而且您实际上会因为并行而失去性能。如果去掉并行性，您是否测量过相同程序运行的速度？(PARLANSE足够快，因此一个人可以编写一个并行的8字谜解谜器。，尽管具有生成-移动-评估，仍然是相当多的工作量比开销)。
当您的任务中没有足够的工作来克服开销时，标准的技巧是将更多的工作投入到任务中。
在您的示例中，您可能决定让任务表示2层或3层的搜索；这将为每个任务创建大量的工作。对于一个8层的游戏搜索，您仍将有大量生成的任务来保持处理器的忙碌。我展示了一个类似的技巧(粗粒度阈值)使平行斐波纳契工作，这是一个可怕的工作/开销比率方案，人们可以发明。
在国际象棋界是众所周知的，复杂的棋盘评估就像一个人在棋盘位置上做了2到3次搜索一样。因此，您的另一个选择是执行一个昂贵的董事会评估例程；这将使开销较小的叶子。
α-beta可能会从由于“大堆栈”和许多任务而耗尽VM中拯救你(“只有1000个任务”)。关于产生大量工作的好消息是，您有很多东西要给CPU。坏消息是，它们可以在VM中占用大量空间，而不执行；MS的大堆栈模型加剧了这一点。即使它没有在VM中运行，它也可能导致程序接触大量内存，从而否定处理器缓存的价值。我担心这一点，但对C#没有很好的建议；为了避免这些问题，我构建了PARLANSE；当任务生成“足够多”时，它会自动抑制任务生成。不过，女士们有一些聪明的饼干。
https://stackoverflow.com/questions/33626992
复制相似问题
腾讯云开发者
