OpenMP 是啥？官方1如是说：

The OpenMP® API is a scalable model that gives parallel programmers a simple and flexible interface for developing portable parallel applications in C/C++ and Fortran.

OpenMP is suitable for a wide range of algorithms running on multicore nodes and chips, NUMA systems, GPUs, and other such devices attached to a CPU.

它的功能相当简单，就是单进程/共享内存并行计算；具体包括

  1. 并行化形如 for(int i=START; i<END; i++) 的循环/静态任务列表 (#pragma omp for/sections)
  2. 并行化动态任务 (#pragma omp task)

它的在 C 里的工作方式2类似于 Rust attribute-like macro：通过 #pragma omp XXX 来把对应代码块通过 openmp 魔改，生成可并行代码。不同于 Rust 允许自定义 proc-macro 来 hook ast 解析过程，openmp 需要编译器的原生支持；好在绝大多数的编译器都支持 openmp3。

对于 GCC，编译时需要 enable flag: -fopenmp

Hello, world

先来一个 Hello world

#include <omp.h>
#include <stdio.h>

int main() {
    #pragma omp parallel
    {
        int ID = omp_get_thread_num();
        printf("Hello world from thread %d\n", ID);
    }
    return 0;
}

输出：

Hello world from thread 20
Hello world from thread 30
Hello world from thread 0
Hello world from thread 3
...

这样这段代码就会被多个线程执行。

For 循环

openmp 里 for 循环可谓核心功能。用一段（不太对的）示例代码来看看

#include <omp.h>
#include <stdio.h>

int main() {
    int sum=0;
    #pragma omp parallel num_threads(4)
    {
        #pragma omp for
        for(int i=1; i<=10000; i++) {
            sum+=i;
        }
    }
    printf("Total sum: %d\n", sum);
    return 0;
}

Total sum: 9667961

一般我们用 #pragma omp parallel 声明一个 openmp 并行代码块，内部的代码每个线程都会执行一遍。 我们这里用 num_threads 选项指定了用 4 个线程（默认值是 num_procs*2）。

#pragma omp for 则会将迭代元素按一定规则分配给所有线程。如示例代码中，openmp 自动将 1..=10000 范围的数分配给了四个线程计算。

无痛获得四倍速度…等等这个答案好像不太对啊！不应该是 50005000 吗？这是因为——寄存器优化和数据竞争！

由于我们的 sum 是“热变量”，编译器会为它单独配备一个寄存器，这样累加过程中避免了 sum 的内存读写；要知道对于 0.2ns/op 的现代 cpu，内存高达 60ns 的延迟可是乱序执行都救不回来的；就算是利用 L3 cache 也会有 10ns 左右的延迟。 然而这导致每个线程算完自己的 sum 最后存回了内存，直接把其他线程结果覆盖了！这肯定不是我们期望的结果。

即使我们让 sum 成为 volatile 变量，也会遇到类似的数据竞争问题，只是覆盖发生在 L1/L2 写到 L3 而非寄存器写到 L3/内存的时候。

一种方法是引入 原子操作： 这会让任何内存读写前后插入内存屏障，让数据在 CPU 内部强制同步，防止覆盖：

#pragma omp atomic
sum+=i;

Total sum: 50005000

非常完美…

局部变量技巧

但是慢了好多！我们令求和范围为 1..=100000000，则有 0.768s real time；而不加 atomic 只有 0.231s real time； 单线程更是只有 0.054s。这四线程比单线程还慢！这是因为 sum 被线程共享了，为了正确地在线程间同步，不得不引入了巨大的内存读写开销。

正确做法是引入局部变量，这个变量只在线程内部使用，这样编译器可以做充分的寄存器优化，也避免了线程间同步的巨大开销。 然后在线程结束前再同步；这样每个线程只需要同步一次，竞争很少。

#include <omp.h>
#include <stdio.h>

int main() {
    long long sum=0;
    #pragma omp parallel num_threads(4)
    {
        long long local_sum = 0;
        #pragma omp for
        for(long long i=1; i<=100000000; i++) {
           
            local_sum+=i;
        }
        #pragma omp atomic
        sum+=local_sum;
    }
    printf("Total sum: %lld\n", sum);
    return 0;
}

real time 0.015s！确实获得了近乎四倍的性能提升！

当然 openmp 提供了简便写法 reduction(+:sum)：

long long sum=0;
#pragma omp parallel num_threads(4)
{
    #pragma omp for reduction(+:sum)
    for(long long i=1; i<=100000000; i++) {
        sum+=i;
    }
}

更多 Reduction 语法糖可以看 Reduction Clauses and Directives。 其他操作就手写吧。

同步

如果内存不同步就会发生数据竞争。除了上面介绍的 atomic，也可以使用临界区 critical 同步内存，尤其是当你写的数据不是基本类型， 不能在一句内解决时。

#pragma omp critical
{
    var.x=sum1;
    var.y=sum2;
}

它比 atomic 慢一些，因为线程可能会被内核锁定（pthread_mutex）；不过问题不大，因为好的程序内存同步不会太频繁。

另一方面，我们也可以通过 #pragma omp barrier 类似 pthread_barrier 地让线程之间在某位置同步（确保所有线程都执行到这一步后，才继续执行后续代码）； 不过感觉用的比较少，大概只有当神秘程序有玄学同步需求的时候会用吧。一般循环前后会被自动插入 barrier

调度

openmp 的核心就是并行任务的分割和调度：如何把 for range 内的任务均匀分配给线程，这是个难题。

openmp 有以下调度方式：

  • static: 真·平均分/指定批大小
  • dynamic: 一批一批任务来
  • guided: 一批一批任务来，但是先很大一批，后来批越来越小直到给定的 batch size

用法： #pragma omp for schedule(dynamic,4)（4 个一批） #pragma omp for schedule(static)

最好情况下，每个任务时间差不多，那 static 最为适合，因为它完全没有运行时任务分配和线程同步开销。这也是默认的。

每个任务时间参差很大，那就 guided/dynamic。

内存模型/闭包

这部分虽然很基础但是 openmp 处理得很符合直觉。只有碰到奇怪错误时需要考虑这部分。

在并行块内部会用到块外变量，这就需要捕获变量到闭包。openmp 有两种捕获方式：引用 (shared) 和克隆 (private)。

for loop 默认用 shared，task 默认用 private4。不过最佳实践还是注明所有捕获变量的捕获方式。（试试改改上面的代码？） shared 要注意竞争。

动态任务

通过 #pragma omp task 可以向 openmp 调度器动态添加任务，支持递归函数，支持嵌套。

int fib(int n) {
    if (n<2) return n;
    else {
        int i,j;
        #pragma omp task shared(i) 
        i=fib(n-1);

        #pragma omp task shared(j)
        j=fib(n-2);

        #pragma omp taskwait
        printf("Current int %d is on thread %d \n", i+j, omp_get_thread_num());
        return i+j;
    }
}

int main() {
    #pragma omp parallel
    #pragma omp single
    printf ("fib(10) = %d\n", fib(10));
    return 0;
}

注意 fib 调用要放在 single 内，否则会被运行好多遍；要放在 parallel 内，否则没有 omp 多线程环境，只能单线程。

注意到这里手动标了 shared(i)，因为 task 默认 private。

其他

还有一个蛮实用的功能：section

#pragma omp sections
{
    #pragma omp section
    {
        printf("section 0,threadid=%d\n",omp_get_thread_num());
        sleep(1);
    }
    #pragma omp section
    {
        printf("section 1,threadid=%d\n",omp_get_thread_num());
        //sleep(1);
    }
    #pragma omp section
    {
        printf("section 2,threadid=%d\n",omp_get_thread_num());
        sleep(1);
    }
}

这样每个 section 会被分配到不同线程上。如果一段代码可以分成无关的大部分，例如分别计算两个数组的和，就可以分别放到 section 里面。

注意，它并不是动态任务：它不支持递归调用和嵌套，调度规则也比较简单。它只适合运行时间较长的一块部分。它与 task 不可混淆。

乱写的

猜猜这段代码会输出什么：

#include <omp.h>
#include <iostream>
#include <vector>

template<class T>
void display_vec(const std::vector<T>& v) {
    std::cout<<'[';
    for(auto i=v.begin(); i<v.end(); i++) {
        std::cout<<*i;
        if (i<v.end()-1) std::cout<<", ";
    }
    std::cout<<']'<<std::endl;
}

int main() {
    std::vector<int> v;
    #pragma omp parallel private(v)
    {
        #pragma omp for
        for(int i=0; i<1000; i++) {
            v.push_back(i);
        }
        #pragma omp critical
        {
            std::cout<<"Thread "<<omp_get_thread_num()<<": ";
            display_vec(v);
        }
    }
    std::cout<<"Main thread: ";
    display_vec(v);
}
输出 
Thread 5: [160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191]
Thread 3: [96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127]
Thread 16: [504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534]
Thread 1: [32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63]
Thread 21: [659, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689]
Thread 20: [628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658]
Thread 19: [597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627]
Thread 2: [64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95]
Thread 7: [224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255]
Thread 22: [690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720]
Thread 4: [128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159]
Thread 18: [566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596]
Thread 23: [721, 722, 723, 724, 725, 726, 727, 728, 729, 730, 731, 732, 733, 734, 735, 736, 737, 738, 739, 740, 741, 742, 743, 744, 745, 746, 747, 748, 749, 750, 751]
Thread 17: [535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565]
Thread 0: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
Thread 25: [783, 784, 785, 786, 787, 788, 789, 790, 791, 792, 793, 794, 795, 796, 797, 798, 799, 800, 801, 802, 803, 804, 805, 806, 807, 808, 809, 810, 811, 812, 813]
Thread 13: [411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441]
Thread 9: [287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317]
Thread 11: [349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379]
Thread 15: [473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503]
Thread 14: [442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472]
Thread 27: [845, 846, 847, 848, 849, 850, 851, 852, 853, 854, 855, 856, 857, 858, 859, 860, 861, 862, 863, 864, 865, 866, 867, 868, 869, 870, 871, 872, 873, 874, 875]
Thread 30: [938, 939, 940, 941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956, 957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968]
Thread 29: [907, 908, 909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924, 925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937]
Thread 8: [256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286]
Thread 31: [969, 970, 971, 972, 973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999]
Thread 10: [318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348]
Thread 24: [752, 753, 754, 755, 756, 757, 758, 759, 760, 761, 762, 763, 764, 765, 766, 767, 768, 769, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 780, 781, 782]
Thread 12: [380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410]
Thread 26: [814, 815, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844]
Thread 6: [192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223]
Thread 28: [876, 877, 878, 879, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 890, 891, 892, 893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906]
Main thread: []

References

  1. https://www.openmp.org/resources/refguides/ ↩︎

  2. https://www.scss.tcd.ie/David.Gregg/cs3014/notes/lecture7-openmp-under-the-hood.pdf ↩︎

  3. https://www.openmp.org/resources/openmp-compilers-tools/ ↩︎

  4. Citation needed ↩︎