## 1.1

设总共$n$个数待求和，总共有$P$个核

对于编号为$p(0 \le p \lt P)$的核

$my\_first\_i = p * \lfloor \frac{n}{P} \rfloor$

$my\_last\_i=\begin{cases}
        n & p = P-1
        \\
        (p+1) * \lfloor \frac{n}{P} \rfloor & else
    \end{cases}$

## 1.6

a. 需执行接收和加法各$P-1$次

b. 需执行接收和加法各$\lceil \log_2 P \rceil$次

(这是因为b的次数满足$f(P)=\begin{cases}
        0 & P=1
        \\
        f(\lceil \frac{P}{2} \rceil) + 1 & else
    \end{cases}$）

表格如下：
| P | a | b |
| ------ | ------ | ------ |
| 2 | 1 | 1 |
| 4 | 3 | 2 |
| 8 | 7 | 3 |
| 16 | 15 | 4 |
| 32 | 31 | 5 |
| 64 | 63 | 6 |
| 128 | 127 | 7 |
| 256 | 255 | 8 |
| 512 | 511 | 9 |
| 1024 | 1023 | 10 |

## 1.7

我认为这二者的成分都有。可以认为总共有$\lceil \log_2 P\rceil + 1$种任务(分别对应参与$0, 1, ..., \lceil \log_2 P \rceil$次接受/求和)，分配给$P$个核心来处理，所以存在执行相同任务而数据不同的核心，也存在执行不同任务的核心。


## 1.9

我曾经在计算机图形学代码中使用并行计算，具体来说是利用多线程加速光线追踪。大致伪代码可以表述如下
```
func trace(ray) {
  iterate over scene, find hit point, compute radiance, do reflect/refract and continue
}
```
每个线程负责确定一定范围内的像素的颜色，它向这些像素的位置发射光线并调用trace；除了中途输出进度之外，不需要任何同步机制；所有线程的计算任务完成后即可输出图像，不需要额外的数据整合过程。

我使用了线程库(Rust，C++)和OpenMp(C++)两种方式，二者的效率没有明显差距。

除此之外，我还尝试了使用GPU来加速运算。GPU的核心数目远远多于CPU，而且此问题本身特别适合GPU并行执行，所以可以很容易的得到更好的效果。

最后，在我的硬件配置(CPU：R7-2700，GPU：GTX 1060)上渲染smallpt的场景(只是场景相同，代码基本上没有任何关系，我自己还进行了很多优化；图片参数为1024px * 1024 px，10000spp)，CPU单核大概耗时25min，CPU并行大概耗时2min40s，GPU并行大概耗时8s。

我认为这是典型的数据并行，因为它是在一列数据(像素点位置)上并行执行相同的算法(trace)。