课后作业

Write an essay describing a research problem in your major that would benefit from the use of parallel computing. Provide a rough outline of how parallelism would be used. Would you use task- or data-parallelism?

一组数据是否适合使用并行计算，主要有三条判断标准：

1. 能否将工作分解成为方便同时处理的离散成分；
2. 能否随时并且及时的执行多个程序指令；
3. 多处理单元解决该问题的耗时小于单处理单元。

满足上述三个条件，就可以使用并行计算，也就是说，在并行计算系统中，需要将一个应用分解成多个子任务，分配给不同的处理单元，各个处理单元之间相互协同，并行地执行子任务，从而达到加速的目的。

我想到的是在图像处理领域的应用。有个日本技术宅在 GitHub 上开源了一个项目nagadomi/waifu2x，获得了 13k+的 Stars；它使用卷积神经网络对动漫风格的图片进行放大操作（也支持照片），可以在官方网站进行简单的体验，对于二次元图片来说，扩图降噪一次搞定，效果非常之好，可谓是神器了。原理是基于人工智能神经网络运算，作者将一堆 gal 的图片缩小再把他们的原图放到一起，让 waifu 去学习如何放大拉伸，所以一般 waifu 下来都有一个 model 文件夹，这东西就是他的训练集，相当于人的大脑。

每一幅图像，都可以理解为是一个或多个矩阵，而矩阵数据元素之间，从存储和处理上来看，本身就十分整齐，有很高的相关性，非常方便线程模型对其进行批量存取和处理；图像处理算法对于其中的像素点来说往往有较强的规律性，如果算法本身不是有很强的先后时序或逻辑上的先后依赖性，大多易于拆解为能够并行处理的若干单元，处理方法相同而只是像素数据不同；当要处理的点很多时，多处理单元的耗时往往远远小于单处理单元。

因此，图像数据几乎天生就适合使用并行计算来进行处理；使用并行计算来处理图像，最大的优势在于运算速度快。以上面举例的 waifu2x 算法为例，它同时有针对 NVIDIA CUDA 并行优化的版本和针对 CPU 的串行版本。理想情况下，假设现在 CPU 处理一个点的平均时间是 1ms，而 GPU 每个线程处理一个点平均需要 100ms。对于一个大小为$10\times 10$个点的任务，CPU 依次处理完这些点需要 100ms，GPU 同时处理这 100 个点也需要 100ms 的时间，这时候，两者的区别不大。而当我们把任务换成$100\times 100$大小的时候，CPU 需要 10000ms 来处理，而 GPU 依然是 100ms，此时，GPU 的优势就体现出来了。如果是大小为$1000\times 1000$的点，GPU 的运算速度将比 CPU 快若干个数量级。实际情况下也是如此，我在自己的机器上测试，使用 waifu2x 的并行算法将一张图片拉到 4k 只需要几秒，而 CPU 跑了快五分钟。

当然，这并不是说所有图像并行计算速度都比串行计算快，由于受到处理器核心速度、缓存大小和单元间通信等条件影响，串行计算硬件的运算速度，往往要快于并行计算单个处理单元或处理线程的平均速度。对于要进行相同计算的点数量较少的图像，串行计算的速度或许具有一定优势，但是，当图像中需要处理的点超过一定数量时，并行计算的优势就体现出来了。可以说，要处理的点越多，并行计算的速度优势就越明显。

需要注意的是，这里所说的「点」并不一定是特指图像中的像素，也有可能是同样一套图像处理算法在某个位置的运算过程和结果。通常，在图像处理领域中更多使用的是数据并行。

Assume that you have the followiog mix of instructions with average CPIs:

	% of Mix	Average CPI
ALU	47%	6.7
Load	19%	7.9
Branch	20%	5.0
Store	14%	7.1

The dock rate for this machine is 1 GHz.

You want to improve the performance of this machine, and are considering redesigning your multiplier to reduce the average CPI of multiply instructions. (Digress - why do multiplies take longer than adds?) If you make this change, the CPI of multiply instructions would drop to 6 (from 8). The percentage of ALU instructions that are multiply instructions is 23%. How much will perlormance improve by?

乘法器慢于加法器，是因为乘法电路是由更基本加法电路组成的。

ALU 除了乘法之外部分的平均 CPI：$(6.7-8\times 23\%)/77\%\approx 6.3$

优化乘法之后 ALU 的平均 CPI：$6.3\times 77\%+6\times 23\%\approx 6.24$

原先的平均 CPI：$6.7\times 47\%+7.9\times 19\%+5.0\times 20\%+7.1\times 14\%=6.644$

优化乘法之后的平均 CPI：$6.24\times 47\%+7.9\times 19\%+5.0\times 20\%+7.1\times 14\%=6.4278$

因此性能被优化了$(6.644-6.4278)/6.644\approx 3.25\%$