如何在 NUMA CPU 上实现 OpenMP 中的数据本地生成或任务调度？
How can I realize data local spawning or scheduling of tasks in OpenMP on NUMA CPUs?
我有一个非常基本的 2 维模板应用程序的简单独立示例，它在动态数组上使用 OpenMP 任务来表示我遇到的问题，这不是玩具问题。
有 2 个更新步骤，其中对于数组中的每个点，从相应位置以及上下相邻位置的另一个数组添加 3 个值。该程序在 NUMA CPU 上执行，每个 NUMA 节点上有 8 个内核和 2 个硬件线程。数组初始化是并行的，并使用环境变量 OMP_PLACES=threads 和 OMP_PROC_BIND=spread 将数据均匀分布在节点的内存中。为了避免数据竞争，我设置了依赖关系，以便对于第二次更新的每个部分，只有在执行了第一个更新步骤的部分的相关任务时才能安排任务。计算正确但不支持 NUMA。 affinity 子句似乎不足以更改调度，因为它只是一个提示。我也不确定使用 single 创建任务是否有效，但我所知道的是这是使所有任务同级任务并因此适用依赖项的唯一方法。
在 OpenMP 中有没有一种方法可以在这些约束下并行创建任务或引导运行时系统进行更 NUMA 感知的任务调度？如果没有，也没关系，我只是想看看是否有可用的选项以预期的方式使用 OpenMP 而不是试图破坏它。我已经有了一个只使用工作共享循环的版本。这是为了研究。
NUMA 节点 0 pus {0-7,16-23}
NUMA 节点 1 pus {8-15,24-31}
环境变量
export OMP_PLACES=threads
export OMP_PROC_BIND=spread
#define _GNU_SOURCE // sched_getcpu(3) is glibc-specific (see the man page)
#include <sched.h>
#include <iostream>
#include <omp.h>
#include <math.h>
#include <vector>
#include <string>
typedef double value_type;
int main(int argc, char * argv[]){
std::size_t rows = 8192;
std::size_t cols = 8192;
std::size_t part_rows = 32;
std::size_t num_threads = 16;
std::size_t parts = ceil(float(rows)/part_rows);
value_type * A = (value_type *) malloc(sizeof(value_type)*rows*cols);
value_type * B = (value_type *) malloc(sizeof(value_type)*rows*cols);
value_type * C = (value_type *) malloc(sizeof(value_type)*rows*cols);
#pragma omp parallel for schedule(static)
for (int i = 0; i < rows; ++i)
for(int j = 0; j<cols; ++j){
A[i*cols+j] = 1;
B[i*cols+j] = 1;
C[i*cols+j] = 0;
}
std::vector<std::vector<std::size_t>> putasks(32, std::vector<std::size_t>(2,0));
std::cout << std::endl;
#pragma omp parallel num_threads(num_threads)
#pragma omp single
{
for(int part=0; part<parts; part++){
std::size_t row = part * part_rows;
std::size_t current_first_loc = row * cols;
//first index of the upper part in the array
std::size_t upper_part_first_loc = part != 0 ? (part-1)*part_rows*cols : current_first_loc;
//first index of the lower part in the array
std::size_t lower_part_first_loc = part != parts-1 ? (part+1)*part_rows * cols : current_first_loc;
std::size_t start = row;
std::size_t end = part == parts-1 ? rows-1 : start+part_rows;
if(part==0) start = 1;
#pragma omp task depend(in: A[current_first_loc], A[upper_part_first_loc], A[lower_part_first_loc])\
depend(out: B[current_first_loc]) affinity(A[current_first_loc], B[current_first_loc])
{
if(end <= ceil(rows/2.0))
putasks[sched_getcpu()][0]++;
else putasks[sched_getcpu()][1]++;
for(std::size_t i=start; i<end; ++i){
for(std::size_t j = 0; j < cols; ++j)
B[i*cols+j] += A[i*cols+j] + A[(i-1)*cols+j] + A[(i+1)*cols+j];
}
}
}
for(int part=0; part<parts; part++){
std::size_t row = part * part_rows;
std::size_t current_first_loc = row * cols;
std::size_t upper_part_first_loc = part != 0 ? (part-1)*part_rows*cols : current_first_loc;
std::size_t lower_part_first_loc = part != parts-1 ? (part+1)*part_rows * cols : current_first_loc;
std::size_t start = row;
std::size_t end = part == parts-1 ? rows-1 : start+part_rows;
if(part==0) start = 1;
#pragma omp task depend(in: B[current_first_loc], B[upper_part_first_loc], B[lower_part_first_loc])\
depend(out: C[current_first_loc]) affinity(B[current_first_loc], C[current_first_loc])
{
if(end <= ceil(rows/2.0))
putasks[sched_getcpu()][0]++;
else putasks[sched_getcpu()][1]++;
for(std::size_t i=start; i<end; ++i){
for(std::size_t j = 0; j < cols; ++j)
C[i*cols+j] += B[i*cols+j] + B[(i-1)*cols+j] + B[(i+1)*cols+j];
}
}
}
}
if(rows <= 16 & cols <= 16)
for(std::size_t i = 0; i < rows; ++i){
for(std::size_t j = 0; j < cols; ++j){
std::cout << C[i*cols+j] << " ";
}
std::cout << std::endl;
}
for(std::size_t i = 0; i<putasks.size(); ++i){
if(putasks[i][0]!=0 && putasks[i][1]!=0){
for(std::size_t node = 0; node < putasks[i].size(); ++node){
std::cout << "pu: " << i << " worked on ";
std::cout << putasks[i][node]<< " NODE " << node << " tasks" << std::endl;
}
std::cout << std::endl;
}
}
return 0;
}
任务分配输出摘录
pu: 1 worked on 26 NODE 0 tasks
pu: 1 worked on 12 NODE 1 tasks
pu: 2 worked on 27 NODE 0 tasks
pu: 2 worked on 13 NODE 1 tasks
...
pu: 7 worked on 26 NODE 0 tasks
pu: 7 worked on 13 NODE 1 tasks
pu: 8 worked on 10 NODE 0 tasks
pu: 8 worked on 11 NODE 1 tasks
pu: 9 worked on 8 NODE 0 tasks
pu: 9 worked on 14 NODE 1 tasks
...
pu: 15 worked on 8 NODE 0 tasks
pu: 15 worked on 12 NODE 1 tasks
首先，NUMA 系统上的 OpenMP 任务调度状态在实践中远非理想。过去它一直是许多研究项目的主题，并且他们仍在进行中的项目。一些研究运行时适当地考虑亲和性提示并安排有关 in/out/inout 依赖项的 NUMA 节点的任务。但是，AFAIK 主流运行时并不能很好地在 NUMA 系统上安排任务，尤其是当您从一个唯一的 NUMA 节点创建所有任务时。实际上，AFAIK GOMP（GCC）只是忽略了这一点，实际上表现出一种使其在 NUMA 系统上效率低下的行为（例如，当任务太多时，任务的创建会暂时停止，并且任务会在所有 NUMA 节点上执行，而忽略source/target NUMA 节点）。 IOMP (Clang/ICC) 考虑了局部性，但 AFAIK 在您的情况下，调度不应该很好。任务的关联提示是 not available upstream yet。因此，在您的情况下，GOMP 和 IOMP 显然不会表现良好，因为不同步骤的任务通常会以产生 许多远程 NUMA 节点访问 的方式分布，这些访问已知是低效的。事实上，这对您的情况很重要，因为模板通常 内存限制 。
如果您使用 IOMP，请注意其任务调度程序倾向于在创建任务的同一 NUMA 节点上执行任务。因此，一个好的解决方案是并行创建任务。可以在绑定到 NUMA 节点的许多线程中创建任务。调度程序将首先尝试在相同的线程上执行任务。同一 NUMA 节点上的工作线程将尝试 窃取 同一 NUMA 节点中线程的任务，如果没有足够的任务，则从任何线程。虽然这种 work stealing 策略在实践中效果相对较好，但存在一个巨大的陷阱：不同父任务的任务不能共享依赖关系。当前 OpenMP 规范的这种限制对于模板代码（至少是那些创建在不同时间步长上工作的任务的代码）来说是一个大问题。另一种解决方案是从一个线程创建具有依赖关系的任务，并从这些任务创建较小的任务，但由于大任务的调度通常很糟糕，这种方法在 NUMA 系统上的实践中通常效率低下。实际上，在主流运行时，基本 statically-scheduled 循环在 NUMA 系统上的模板表现相对较好，尽管对于大型模板显然是 sub-optimal。这是可悲的，我希望这种情况在当前十年内会有所改善。
请注意，数据初始化在 NUMA 系统上非常重要，因为许多平台实际上在执行 首次接触 的 NUMA 节点上分配页面。因此初始化必须是并行的（否则所有页面可能位于同一个 NUMA 节点上，导致该节点在模板步骤期间饱和）。默认策略在所有平台上都不相同，有些可以在 NUMA 节点之间根据其使用移动页面。您可以使用 numactl 调整行为。您还可以从 hw-loc 工具中获取非常有用的信息。我强烈建议您使用 OMP_PROC_BIND=True 和 OMP_PLACES="{0},{1},...,{n}" 手动定位所有 OpenMP 线程，其中 OMP_PLACES 字符串集可以从 hw-loc 生成关于实际平台。
更多信息你可以阅读this research paper (disclaimer: I am one of the authors). You can certainly find other similar research paper on the IWOMP conference and the Super-Computing conference too. You could try to use research runtime though most of them are not designed to be used in production (eg. KOMP which is not actively developed anymore, StarPU which mainly focus on GPUs and optimizing the critical path, OmpSS which is not fully compatible with OpenMP but try to extend it, PaRSEC，它主要是为线性代数应用而设计的）。
我有一个非常基本的 2 维模板应用程序的简单独立示例，它在动态数组上使用 OpenMP 任务来表示我遇到的问题，这不是玩具问题。
有 2 个更新步骤，其中对于数组中的每个点，从相应位置以及上下相邻位置的另一个数组添加 3 个值。该程序在 NUMA CPU 上执行，每个 NUMA 节点上有 8 个内核和 2 个硬件线程。数组初始化是并行的，并使用环境变量 OMP_PLACES=threads 和 OMP_PROC_BIND=spread 将数据均匀分布在节点的内存中。为了避免数据竞争，我设置了依赖关系，以便对于第二次更新的每个部分，只有在执行了第一个更新步骤的部分的相关任务时才能安排任务。计算正确但不支持 NUMA。 affinity 子句似乎不足以更改调度，因为它只是一个提示。我也不确定使用 single 创建任务是否有效，但我所知道的是这是使所有任务同级任务并因此适用依赖项的唯一方法。
在 OpenMP 中有没有一种方法可以在这些约束下并行创建任务或引导运行时系统进行更 NUMA 感知的任务调度？如果没有，也没关系，我只是想看看是否有可用的选项以预期的方式使用 OpenMP 而不是试图破坏它。我已经有了一个只使用工作共享循环的版本。这是为了研究。
NUMA 节点 0 pus {0-7,16-23} NUMA 节点 1 pus {8-15,24-31}
环境变量
export OMP_PLACES=threads
export OMP_PROC_BIND=spread
#define _GNU_SOURCE // sched_getcpu(3) is glibc-specific (see the man page)
#include <sched.h>
#include <iostream>
#include <omp.h>
#include <math.h>
#include <vector>
#include <string>
typedef double value_type;
int main(int argc, char * argv[]){
std::size_t rows = 8192;
std::size_t cols = 8192;
std::size_t part_rows = 32;
std::size_t num_threads = 16;
std::size_t parts = ceil(float(rows)/part_rows);
value_type * A = (value_type *) malloc(sizeof(value_type)*rows*cols);
value_type * B = (value_type *) malloc(sizeof(value_type)*rows*cols);
value_type * C = (value_type *) malloc(sizeof(value_type)*rows*cols);
#pragma omp parallel for schedule(static)
for (int i = 0; i < rows; ++i)
for(int j = 0; j<cols; ++j){
A[i*cols+j] = 1;
B[i*cols+j] = 1;
C[i*cols+j] = 0;
}
std::vector<std::vector<std::size_t>> putasks(32, std::vector<std::size_t>(2,0));
std::cout << std::endl;
#pragma omp parallel num_threads(num_threads)
#pragma omp single
{
for(int part=0; part<parts; part++){
std::size_t row = part * part_rows;
std::size_t current_first_loc = row * cols;
//first index of the upper part in the array
std::size_t upper_part_first_loc = part != 0 ? (part-1)*part_rows*cols : current_first_loc;
//first index of the lower part in the array
std::size_t lower_part_first_loc = part != parts-1 ? (part+1)*part_rows * cols : current_first_loc;
std::size_t start = row;
std::size_t end = part == parts-1 ? rows-1 : start+part_rows;
if(part==0) start = 1;
#pragma omp task depend(in: A[current_first_loc], A[upper_part_first_loc], A[lower_part_first_loc])\
depend(out: B[current_first_loc]) affinity(A[current_first_loc], B[current_first_loc])
{
if(end <= ceil(rows/2.0))
putasks[sched_getcpu()][0]++;
else putasks[sched_getcpu()][1]++;
for(std::size_t i=start; i<end; ++i){
for(std::size_t j = 0; j < cols; ++j)
B[i*cols+j] += A[i*cols+j] + A[(i-1)*cols+j] + A[(i+1)*cols+j];
}
}
}
for(int part=0; part<parts; part++){
std::size_t row = part * part_rows;
std::size_t current_first_loc = row * cols;
std::size_t upper_part_first_loc = part != 0 ? (part-1)*part_rows*cols : current_first_loc;
std::size_t lower_part_first_loc = part != parts-1 ? (part+1)*part_rows * cols : current_first_loc;
std::size_t start = row;
std::size_t end = part == parts-1 ? rows-1 : start+part_rows;
if(part==0) start = 1;
#pragma omp task depend(in: B[current_first_loc], B[upper_part_first_loc], B[lower_part_first_loc])\
depend(out: C[current_first_loc]) affinity(B[current_first_loc], C[current_first_loc])
{
if(end <= ceil(rows/2.0))
putasks[sched_getcpu()][0]++;
else putasks[sched_getcpu()][1]++;
for(std::size_t i=start; i<end; ++i){
for(std::size_t j = 0; j < cols; ++j)
C[i*cols+j] += B[i*cols+j] + B[(i-1)*cols+j] + B[(i+1)*cols+j];
}
}
}
}
if(rows <= 16 & cols <= 16)
for(std::size_t i = 0; i < rows; ++i){
for(std::size_t j = 0; j < cols; ++j){
std::cout << C[i*cols+j] << " ";
}
std::cout << std::endl;
}
for(std::size_t i = 0; i<putasks.size(); ++i){
if(putasks[i][0]!=0 && putasks[i][1]!=0){
for(std::size_t node = 0; node < putasks[i].size(); ++node){
std::cout << "pu: " << i << " worked on ";
std::cout << putasks[i][node]<< " NODE " << node << " tasks" << std::endl;
}
std::cout << std::endl;
}
}
return 0;
}
任务分配输出摘录
pu: 1 worked on 26 NODE 0 tasks
pu: 1 worked on 12 NODE 1 tasks
pu: 2 worked on 27 NODE 0 tasks
pu: 2 worked on 13 NODE 1 tasks
...
pu: 7 worked on 26 NODE 0 tasks
pu: 7 worked on 13 NODE 1 tasks
pu: 8 worked on 10 NODE 0 tasks
pu: 8 worked on 11 NODE 1 tasks
pu: 9 worked on 8 NODE 0 tasks
pu: 9 worked on 14 NODE 1 tasks
...
pu: 15 worked on 8 NODE 0 tasks
pu: 15 worked on 12 NODE 1 tasks
首先，NUMA 系统上的 OpenMP 任务调度状态在实践中远非理想。过去它一直是许多研究项目的主题，并且他们仍在进行中的项目。一些研究运行时适当地考虑亲和性提示并安排有关 in/out/inout 依赖项的 NUMA 节点的任务。但是，AFAIK 主流运行时并不能很好地在 NUMA 系统上安排任务，尤其是当您从一个唯一的 NUMA 节点创建所有任务时。实际上，AFAIK GOMP（GCC）只是忽略了这一点，实际上表现出一种使其在 NUMA 系统上效率低下的行为（例如，当任务太多时，任务的创建会暂时停止，并且任务会在所有 NUMA 节点上执行，而忽略source/target NUMA 节点）。 IOMP (Clang/ICC) 考虑了局部性，但 AFAIK 在您的情况下，调度不应该很好。任务的关联提示是 not available upstream yet。因此，在您的情况下，GOMP 和 IOMP 显然不会表现良好，因为不同步骤的任务通常会以产生 许多远程 NUMA 节点访问 的方式分布，这些访问已知是低效的。事实上，这对您的情况很重要，因为模板通常 内存限制 。
如果您使用 IOMP，请注意其任务调度程序倾向于在创建任务的同一 NUMA 节点上执行任务。因此，一个好的解决方案是并行创建任务。可以在绑定到 NUMA 节点的许多线程中创建任务。调度程序将首先尝试在相同的线程上执行任务。同一 NUMA 节点上的工作线程将尝试 窃取 同一 NUMA 节点中线程的任务，如果没有足够的任务，则从任何线程。虽然这种 work stealing 策略在实践中效果相对较好，但存在一个巨大的陷阱：不同父任务的任务不能共享依赖关系。当前 OpenMP 规范的这种限制对于模板代码（至少是那些创建在不同时间步长上工作的任务的代码）来说是一个大问题。另一种解决方案是从一个线程创建具有依赖关系的任务，并从这些任务创建较小的任务，但由于大任务的调度通常很糟糕，这种方法在 NUMA 系统上的实践中通常效率低下。实际上，在主流运行时，基本 statically-scheduled 循环在 NUMA 系统上的模板表现相对较好，尽管对于大型模板显然是 sub-optimal。这是可悲的，我希望这种情况在当前十年内会有所改善。
请注意，数据初始化在 NUMA 系统上非常重要，因为许多平台实际上在执行 首次接触 的 NUMA 节点上分配页面。因此初始化必须是并行的（否则所有页面可能位于同一个 NUMA 节点上，导致该节点在模板步骤期间饱和）。默认策略在所有平台上都不相同，有些可以在 NUMA 节点之间根据其使用移动页面。您可以使用 numactl 调整行为。您还可以从 hw-loc 工具中获取非常有用的信息。我强烈建议您使用 OMP_PROC_BIND=True 和 OMP_PLACES="{0},{1},...,{n}" 手动定位所有 OpenMP 线程，其中 OMP_PLACES 字符串集可以从 hw-loc 生成关于实际平台。
更多信息你可以阅读this research paper (disclaimer: I am one of the authors). You can certainly find other similar research paper on the IWOMP conference and the Super-Computing conference too. You could try to use research runtime though most of them are not designed to be used in production (eg. KOMP which is not actively developed anymore, StarPU which mainly focus on GPUs and optimizing the critical path, OmpSS which is not fully compatible with OpenMP but try to extend it, PaRSEC，它主要是为线性代数应用而设计的）。