chapel - 使用嵌套的“forall”循环有什么好处或坏处吗

正如您所注意到的，这个问题的简短答案是“它取决于”，因为 Chapel 的forall循环调用可能由任何人编写的迭代器，因此可以做任何事情。但正如您也提到的，对于 Chapel 的许多标准类型，有一些控制执行策略的旋钮，如Executing Chapel Programs::Controlling Degree of Data Parallelism中所述，以及遵循的某些约定。我的其余答案将针对此类情况编写。

对于一个完全本地的嵌套forall循环，其中所有迭代都执行相似的工作量，您应该不会看到使用嵌套forall循环之间的巨大差异：

forall i in 1..m do
  forall j in 1..n do
    var twoPi = 2*pi;

并为内部循环使用串行for循环：

forall i in 1..m do
  for j in 1..n do
    var twoPi = 2*pi;

正如我认为您所预料的那样，其原因是外部forall循环将创建dataParTasksPerLocale此值默认为here.numPUs()（当前区域设置或计算节点上的处理单元或内核的数量）的任务。然后，当每个内部循环开始运行时，如果dataParIgnoreRunningTasks是false，默认情况下，它的迭代器会注意到它dataParTasksPerLocale已经在运行，因此将避免创建额外的任务。结果是每个内部循环可能会连续运行其所有迭代，因为它假定所有处理器内核都已经在忙于运行任务。

现在，想象一下外循环的迭代是极度负载不平衡的，以至于一些外循环任务将在其他任务之前完成。例如，这是一个特别人为的循环，其中后半部分的迭代比前半部分做的工作少得多：

forall i in 1..m do
  if (i < m/2) then
    forall j in 1..n do
      var twoPi = 2*pi;

在这种情况下，任何迭代都在范围内的任务m/2+1..m可能会在那些拥有迭代的任务之前完成1..m/2。假设这适用于一半的任务（这可能适用于像上面这样的范围内的循环，其中任务往往被分配连续的迭代块）。这些任务应该很快完成。一旦发生这种情况，另一半任务执行的每个内部循环可能会看到正在运行的任务少于，dataParTasksPerLocale / 2并创建额外的任务来执行它们的迭代。为什么我说“可能”？因为如果多个外循环任务同时运行，就会有多个内循环同时运行，每个内循环都在查询运行任务的个数，竞争创建dataParTasksPerLocale - here.runningTasks()额外的，因此有些可能会并行执行它们的内部循环，而另一些则使用单个任务串行执行。

当然，这种“内部循环可能被并行化”的行为甚至可能发生在比上述更现实的嵌套循环中，例如工作量可能在i和j的值之间发生显着变化的情况：

forall i in 1..m do
  forall j in 1..n do
    computeForPoint(i,j);  // imagine the amount of work here varies significantly based on i and j

在任何不平衡的循环中，一些外循环任务可能会先于其他任务完成，从而释放任务供后续内循环使用。在这种情况下，另一种选择是对外部循环使用动态迭代器，以更好地保持外部循环任务之间的工作平衡。请注意，即使在最平衡的循环中，也可能并非所有外循环任务都会同时完成，在这种情况下，最终的内循环实例可能会并行执行（这就是为什么我在最后使用“可能”描述我最初的平衡案例的句子）。

在本地情况下，如果我只想使循环嵌套的一个循环并行（并且任何一个都可以），我通常将其设置为外部循环，以最大限度地减少创建和销毁的任务数量。也就是说，我通常会选择：

forall i in 1..m do
  for j in 1..n do
    ...

超过：

for i in 1..m do
  forall j in 1..n do
    ...

因为前者创建 ~dataParTasksPerLocale任务，后者创建 ~ m * dataParTasksPerLocale。或者，我可以同时进行并行处理并依赖迭代器和运行时来避免创建过多的任务：

forall i in 1..m do
  forall j in 1..n do
    ...

但在许多情况下，“正确”的选择还取决于循环的行程计数、循环内的计算等。即，不一定有一个万能的答案。

现在，转向分布式数据结构上的循环：从 Chapel 版本 1.17 开始，对于标准数组分布，这些数据结构上的串行循环总是在遇到循环的任务当前正在执行的当前语言环境中计算。相比之下，forall分布式数据结构上的循环在每个目标语言环境上创建至少一个任务，并且可能dataParTasksPerLocale基于与上述本地情况相同的启发式方法创建每个目标语言环境。出于这个原因，分布式数据结构上的循环通常应该forall尽可能使用循环来优化局部性并提高创建可伸缩代码的机会。

chapel - 使用嵌套的“forall”循环有什么好处或坏处吗

问题描述

解决方案

推荐阅读