README.md

# 并行规约求和算法

## 什么是规约

> A reduction operator can help break down a task into various partial tasks by calculating partial results which can be used to obtain a final result. ...... A reduction operator stores the result of the partial tasks into a private copy of the variable. These private copies are then merged into a shared copy at the end.

一个规约操作可以通过计算可用于计算最终结果的子结果来帮助一个任务划分为多个子任务。...... 一个规约操作将子任务的结果存储到到一个变量的私有拷贝，这些私有拷贝最终被合并到一个共享拷贝。

也就是说，规约做了两个事情：

1. 任务划分：将大任务划分为子任务
2. 任务结果合并：将子任务的结果合并后返回

🤔 Map 和 Reduce 是不是就是这样的思想？

## 为什么要规约

> It allows certain serial operations to be performed in parallel and the number of steps required for those operations to be reduced. 

它允许特定的串行操作以并行的方式执行且能降低所需的操作数。

总结为以下两个优点：

1. 可并行化：将原有的串行操作转变为并行操作，减少运行时间。
2. 减少运算次数：通过类似归并的操作降低运算次数，减少时间复杂度。

## 具体实现

### OpenMP

#### 未规约实验

尝试采用 `openmp` 实现 0～4 的 `for` 循环加法，首先先尝试未规约的并行循环加法。具体代码如下，

```c++
int main() {
    int sum = 0;
    std::cout << "Before: " << sum << std::endl;
    #pragma omp parallel for
    for (int i = 0; i < 5; ++i) {
        sum = sum + i;
        std::cout << sum << std::endl;
    }
    std::cout << "After: " << sum << std::endl;
    return 0;
}
```

执行后的输出为

```
Before: 0
0
4
3
5
1
After: 5
```

该过程可以理解如下，

![执行过程](https://pic.rmb.bdstatic.com/bjh/953964b2f0c1e0e68060586d607d5e54.png)

首先 4, 3, 1 的线程取到了 `sum` 的值 0，并对其进行了修改，但在将局部变量写回共享变量的时候产生了覆盖（并发一致性中的丢失修改问题），而 2 的线程恰好取到了 3 写回共享内存时的值，因此，最后在其写回共享内存的时候，最终得到的结果为 5。因此，在并行计算的过程中，如果不考虑规约操作，最终得到的可能是错误的结果。

不过有时也可以得到正确的结果，

```
Before: 0
4
4
7
8
10
After: 10
```

有时一个线程甚至会抢着其中一个线程输出 `sum` 和 换行符 `endl` 的过程去输出，导致两个数字在同一行。如下面例子的 `45`，

```
Before: 0
45
10
7

7
After: 10
```

为了测试该过程中能正确计算出多少次结果，我将该过程循环了 1,000,000 次，计算出了正确计算结果的比例。结果发现，结果具有一定随机性。以下为多次输出的结果

```
0.43192
0.205054
0.472103
0.503719
0.449613
0.632601
0.568709
0.459774
0.487565
0.796675
```

说明线程之间的资源争抢是随机的，不可预测的，所以有必要进行规约操作。

#### 规约实验

在原有的代码基础上加上了对 `sum` 的加法操作规约，

```c++
int paraSumRed() {
    int sum = 0;
    std::cout << "Before: " << sum << std::endl;
    #pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < 5; ++i) {
        sum = sum + i;
        std::cout << sum << std::endl;
    }
    std::cout << "After: " << sum << std::endl;
    return sum;
}
```

观察输出结果发现，虽然输出存在乱序，但最终结果都正确，同样尝试计算出 1,000,000 次下的概率，得到为 1。

说明并不会出现未规约下的结果错误的情况。

考虑一下前面提到的规约操作的两件事情，为了简化理解，我重新设置了 OpenMP 并行线程数 `OMP_NUM_THREADS` 为 2 (之前为4)，并对规约后的过程进行输出，可以发现都是 0,1,3,3,7 的组合，可见规约后的计算过程如下，

![规约后的双线程计算流程](https://pic.rmb.bdstatic.com/bjh/10de0e567bb7b86b94ece09dffa461fd.png)

确实是规约操作的思想，采用reduction之后，每个线程根据 `reduction(+: sum)` 的声明算出自己的 `sum`，然后再将每个线程的`sum` 加起来。

## 总结

规约操作通过将原始任务划分为多个子任务，并将子任务的结果合并以实现多线程下的并行计算，减少计算时间，避免并发一致性的问题。

## 附录

代码：

- [for.cpp](./for.cpp)