并行与分布式计算(1)

课后作业

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简单示例

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

因此,图像数据几乎天生就适合使用并行计算来进行处理;使用并行计算来处理图像,最大的优势在于运算速度快。以上面举例的 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 MixAverage CPI
ALU47%6.7
Load19%7.9
Branch20%5.0
Store14%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\%$