chapel - 使用嵌套的“forall”循环是否有任何利弊？

Question

我想知道使用嵌套“ forall”循环的优缺点。我确实了解的一件事是，“ forall”将调用“独立”或“ leader”迭代器，即使在多个语言环境中，也可能会或可能不会导致额外的并行性。但是，默认情况下，产生的任务数量限制为“ here.maxTaskPar”，因此我们只能获得如此多的并行性。如果两个“ forall”循环都遍历分布式数据，那么我可以看到赞成使用嵌套“ forall”语句的参数，但是当它们都在本地时又如何呢？当其中一个是本地的而另一个不在时？

Answer 1

如您所述，此问题的简短答案是“取决于”，因为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

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

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

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

过度：

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

因为前者创建~~ cc>任务，而后者创建〜 dataParTasksPerLocale。另外，我可能会同时进行并行处理，并依靠迭代器和运行时来避免创建过多的任务：

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

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

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