小小博客
0%

基础优化

发表于

循环优化

循环优化整体策略为循环展开、循环合并与循环顺序的交换：

循环展开

通过减少循环迭代次数来降低循环控制开销，将多个迭代步骤合并执行： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 优化前
while(i < count){
  a[i] = i;
  i++;
}

// 优化后
while(i < count - 1){
  a[i] = i;
  a[i+1] = i+1;
  i += 2;
}
if(i == count-1){
  a[count-1] = count-1;
}

循环合并

对于计数器相同的多个循环，将其合并为一个循环，避免多次轮询： 

1
2
3
4
5
6
7
8
9
10
11
12
13
// 优化前
for(i = 0; i < index; i++){
  do_type_a_work(i);
}
for(i = 0; i < index; i++){
  do_type_b_work(i);
}

// 优化后
for(i = 0; i < index; i++){
  do_type_a_work(i);
  do_type_b_work(i);
}

循环顺序交换

计算外提

将循环内不变的计算提取到循环外部，减少无效计算：

1
2
3
4
5
6
// 优化前
for(int i = 0; i < get_max_index(); i++){}

// 优化后
int max_index = get_max_index();
for(int i = 0; i < max_index; i++){}

多级寻址外提

将循环内的多级指针寻址提取到外部，避免反复寻址跳转：

1
2
3
4
5
6
7
8
9
10
11
12
// 优化前
for(int i = 0; i < max_index; i++){
  ainfo->bconfig.cset[i].index = index;
  ainfo->bconfig.cset[i].flag = flag;
}

// 优化后
set = ainfo->bconfig.cset;
for(int i = 0; i < max_index; i++){
  set[i].index = index;
  set[i].flag = flag;
}

判断外提

将循环内固定不变的条件判断提取到外部，减少比较次数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 优化前
for(i = 0; i < index; i++) {
  if (type == TYPE_A) {
    do_type_a_work(i);
  } else {
    do_type_b_work(i);
  }
}

// 优化后
if (type == TYPE_A) {
  for(i = 0; i < index; i++) {
    do_type_a_work(i);
  }
} else {
  for(i = 0; i < index; i++) {
    do_type_b_work(i);
  }
}

循环嵌套顺序调整

将最繁忙的循环放在最内层，提高缓存利用率：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 优化前
for (column = 0; column < 100; column++) {
  for (row = 0; row < 5; row++) {
    sum += table[row][column];
  }
}

// 优化后
for (row = 0; row < 5; row++) {
  for (column = 0; column < 100; column++) {
    sum += table[row][column];
  }
}
  • 充分分解小的循环：要充分利用CPU的指令缓存，就要充分分解小的循环。特别是当循环体本身很小的时候，分解循环可以提高性能。注意：很多编译器并不能自动分解循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
// 优化前（3D矢量与4x4矩阵相乘）
for (i = 0; i < 4; i++) {
  r[i] = 0；
  for (j = 0； j < 4； j++) {
    r[i] += M[j][i] * V[j]；
  }
}

// 优化后
r[0] = M[0][0]*V[0] + M[1][0]*V[1] + M[2][0]*V[2] + M[3][0]*V[3]；
r[1] = M[0][1]*V[0] + M[1][1]*V[1] + M[2][1]*V[2] + M[3][1]*V[3]；
r[2] = M[0][2]*V[0] + M[1][2]*V[1] + M[2][2]*V[2] + M[3][2]*V[3]；
r[3] = M[0][3]*V[0] + M[1][3]*V[1] + M[2][3]*V[2] + M[3][3]*v[3]；
  • 提取公共部分：对于一些不需要循环变量参加运算的任务可以把它们放到循环外面，这里的任务包括表达式、函数的调用、指针运算、数组访问等，应该将没有必要执行多次的操作全部集合在一起，放到一个init的初始化程序中进行。

OpenMP 并行优化策略

  1. for 循环之前直接加：#pragma omp parallel for 即可自动并行；
  2. 没有 for 循环，还想让代码并行一起干活就用 sections、section：
1
2
3
4
5
6
7
8
#pragma omp parallel sections{ 
    #pragma omp parallel section 
    //第一个人干点啥 
    #pragma omp parallel section 
    //第二个人干点啥 
    ...
    //可以无限套娃
}

但是这样做有个缺点：如果想让每个人干的活差不多，我们得学怎么分任务，太麻烦也不好实现，很容易划分不佳；并且还有一个问题：同一个 sections 内部，不同的 section 之间变量会不会相互干预？我们一定能找到变量相互干预的情况，也一定能找到变量相互不干预的情况。为了区别不同并行区域之间变量是自己使用，还是给大家共享使用，我们定义不同的类型：

  • 私有不干预：private，将变量声明为私有，并行完成后消失，不干预并行区域外的同名变量。
  • 继承不干预：firstprivate，并行之前就有这个变量存在，并行完成后区域内消失，外面的变量保持原值。
  • 私有干预：lastprivate，并行区域内生成，并行完成后保存在并行外部。
  • 复制不干预：threadprivate，共享版 private。

private 子句

1
2
3
4
5
6
int k = 100;
#pragma omp parallel for private(k)
for ( k=0; k < 10; k++){
    printf("k=%d\n", k);
}
printf("last k=%d\n", k);

输出结果是：首先是 0-9 的乱序输出（并行没有顺序），其次就是 last k=100，内外不干预，内部 k 虽然不断变化，但外面的 k 仍然保持 100。

firstprivate 子句

private 虽好，但是它不能继承来自外面的同名变量的值，也就是内外不相联系。firstprivate 可以继承外面变量值用以内部使用，但是对外面变量不会有影响：

1
2
3
4
5
6
7
int k = 100;
#pragma omp parallel for firstprivate(k)
for ( i=0; i < 4; i++){
    k+=i;
    printf("k=%d\n",k);
}
printf("last k=%d\n", k);

打印结果是：k=100-103 之间乱序输出，last k=100。

lastprivate 子句

firstprivate 虽然能从外面继承，但是不能干预外部，只能自娱自乐。lastprivate 能干预外部。

1
2
3
4
5
6
7
int k = 100;
#pragma omp parallel for firstprivate(k),lastprivate(k)
for ( i=0; i < 4; i++){
    k+=i;
    printf("k=%d\n",k);
}
printf("last k=%d\n", k);

打印结果是：k=100-103 之间乱序输出，last k=103。

threadprivate 子句

threadprivate 子句用来指定全局的对象被各个线程各自复制了一个私有的拷贝，即各个线程具有各自私有的全局对象，通常用来做计数器，

1
2
3
4
5
6
int counter = 0; 
#pragma omp threadprivate(counter) 
int increment_counter() {
    counter++;
    return(counter); 
}

threadprivate 和 private 的区别在于：前者声明的变量通常是全局范围内有效，而 private 只在自己的并行区域内有效。threadprivate 对应只能用于 copyin、copyprivate、schedule、num_threads 和 if 子句中。

default/shared 子句

如果我们想让不同的 section 共同编辑一个变量，就要用 default(shared) 声明， 如果是 default(none)，则线程中用到的变量必须指明是私有的还是共享的，毕竟如果不说明参数，很容易造成误会。

reduction 规约子句

这个就是我们在 MPI 中用到的规约子句：

1
2
3
4
5
6
int i, sum = 100;
#pragma omp parallel for reduction(+: sum) {
for ( i = 0; i < 1000; i++ ){
    sum += i;
}
printf( "sum = %ld\n", sum);

上面的程序为每个线程执行规约加法操作，其中 + 为规约操作类型，sum 为规约变量（reduction 操作类型与 reduction 变量）。