如何决定如何在 GPU 上并行化嵌套循环

计算科学 并行计算 表现 显卡
2021-12-28 03:05:39

假设我有一个要在 GPU 上实现的算法。该算法由一个主循环组成,循环的所有迭代都可以并行运行。此外,循环的每次迭代都有一个内部循环,其迭代可以并行运行。假设我需要N主循环的M迭代和内循环的迭代(每次主循环迭代),并且我的 GPU 有L内核。

如果N+N*M <= L,我可以并行运行所有内容。但如果不是这种情况,我需要决定按顺序运行什么。我应该如何做出这个决定?例如,如果N=10, M=5, L = 20, 我应该什么时候选择这些选项(或任何其他选项)?:

  1. 并行运行所有主迭代,并按顺序运行所有内部循环。
  2. 依次运行所有主迭代,并并行运行所有内部循环。
  3. 并行运行所有主要迭代,其中两个并行运行,其余的按顺序运行。
  4. 并行运行三个主迭代,并行运行它们的每个内部循环,依次运行其余的主迭代及其内部循环。
1个回答

如果我们假设 CUDA,答案确实很简单:并行运行所有内容问题规模大于计算单元的数量并不重要,实际上充分利用GPU是非常可取和必要的。有关执行模型的详细信息,请参阅CUDA 编程指南

为了使答案更笼统,我认为处理数量或可并行任务接近计算单元数量的问题是没有意义的:如果是,您还没有发现足够的并行性,或者问题是太小。如果有足够的并行度,假设所有任务都需要大约相同的时间来处理,那么“尾部效应”可以忽略不计。对于 CPU,其内核数量与 GPU 相比要少得多,一般策略是将问题拆分为固定大小的小块(例如,n*m) 然后并行处理块——这样可以保留数据局部性并避免需要决定应该沿着哪个轴并行化问题。对于分布式系统,首先将任务拆分成与节点数相等的大块,然后像以前一样将每个块拆分成更小的块。对于其他 GPU 框架,您可能需要适应它们的执行模型,但我认为总会有一些块结构。