使用嵌套的"forall"循环有什么优点或缺点吗

  • 本文关键字:缺点 嵌套 forall 循环 chapel
  • 更新时间 :
  • 英文 :


我想知道使用嵌套的"forall"循环的优点和缺点。我理解的一件事是,"forall"将调用"standalone"或"leader"迭代器,这可能会也可能不会引起额外的并行性,即使在多个区域设置之间也是如此。然而,生成的任务数量默认限制为"here.maxTaskPar",因此我们只能获得如此多的并行性。如果两个"forall"循环都在分布式数据上,我可以看到支持使用嵌套"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;

并且使用串行CCD_ 4环路作为内部环路:

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

正如我所预料的那样,原因是外部forall循环将创建dataParTasksPerLocale任务,其中该值默认为here.numPUs()(当前区域设置或计算节点上的处理单元或核的数量)。然后,当每个内部循环开始运行时,如果默认情况下dataParIgnoreRunningTasksfalse,其迭代器将注意到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任务少于CCD_13,并创建额外的任务来执行它们的迭代。为什么我说"可能"?因为如果多个外循环任务同时运行,就会有多个同时的内循环,每个内循环都会查询正在运行的任务的数量,并竞争创建dataParTasksPerLocale - here.runningTasks()额外的任务,所以有些任务可以并行执行其内循环,而另一些任务则使用单个任务串行执行。

当然,这种"内部循环可以并行化"的行为甚至可以发生在比上述更现实的嵌套循环中,例如,在ij的值之间,工作量可能会发生巨大变化:

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任务,而后者创建~CCD16。或者,我可能会使两者并行,并依赖迭代器和运行时来避免创建过多的任务:

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

但在许多情况下,"正确"的选择也可能取决于回路的跳闸次数、回路内的计算等。也就是说,不一定有一个一刀切的答案。

现在,转移到分布式数据结构上的循环:从Chapel版本1.17开始,对于标准数组分布,这些数据结构的串行循环总是在遇到循环的任务当前执行的当前区域中计算的。相比之下,分布式数据结构上的forall循环在每个目标区域设置上创建至少一个任务,并且基于与上述本地情况相同的启发式,每个目标区域可能创建多达dataParTasksPerLocale的任务。因此,分布式数据结构上的循环通常应尽可能使用forall循环,以优化位置并提高创建可扩展代码的机会。

相关内容

  • 没有找到相关文章

最新更新