1.0 并行计算与计算机架构
2018-02-14 | CUDA ， Freshman | 0 |
Abstract: 本文从总体上给出了CUDA编程的Big picture，后续所有的文章都在本文的基础上详细展开。 Keywords: 并行计算，串行编程，并行编程，计算机架构，并行性，异构架构，CUDA
并行计算与计算机架构
听过电影里的一句台词，不是名人说的，但我觉得非常值得思考："慢就是稳，稳就是快"。我们的发展太快了，以至于出现了各种《21天精通C++》《10天学会机器学习》这类东西。 稳住吧，打好基础，才有机会去更好的环境。
Big Picture
我们学习CUDA主要参考《CUDA C编程权威指南》，我们的博客也基本按照书中的章节进行。
结构：
CUDA想要运行起来并不困难，但是想要写得好，真的需要研究一下。知乎上各路大牛给出的建议是看CUDA的官方文档，我之前也看过一遍文档，但是文档教会你更多的是如何写代码，而没有讲解详细的硬件结构（可能在别的文档中，我只看了编程指导）。我们学习编程应该同时理解语言、编程模型、硬件执行模型以及优化方法，单纯地学会写代码、能运行，这是培训班的模式。
还记得峰哥的话，知道编译原理和操作系统（软硬件），什么语言都一样。
读这个系列的文章需要以下知识：
- C/C++ 编程经验，这个不用说，如果C都没学会就要来CUDA，我觉得不理智，根基不稳，也是我一贯所反对的
- 本系列是Freshman，后面会有Junior，主要内容肯定有所不同。目前准备的是Freshman主要介绍基础知识，包括硬件基础、编程模型、基本性能方面的考察和简单的优化（包括内存等），以及项目实际中的一些技巧；Junior部分主要介绍更高级的性能优化技巧，比如PTX、更高级的内存处理等；优化空间最大的是并行算法的设计，当然不在本系列所讨论的范围内，那是另一个专题了。
并行计算
我们的计算机从最早的ENIAC到现在的各种超算，都是为了应用而产生的，软件和硬件相互刺激而相互进步，并行计算也是这样产生的。我们最早的计算机肯定不是并行的，但是可以做成多线程的，因为当时一个CPU只有一个核，所以不可能一个核同时执行两个计算。后来我们的应用逐步要求计算量越来越高，所以单核的计算速度也在逐步上升，再后来大规模并行应用出现了，我们迫切需要能够同时处理很多数据的机器，比如图像处理，以及处理大规模的同时访问的服务器后台。
并行计算其实涉及到两个不同的技术领域：
- 计算机架构（硬件）
- 并行程序设计（软件）
这两个很好理解，一个生产工具，一个用工具产生各种不同应用。
硬件主要的目标就是为软件提供更快的计算速度、更低的性能功耗比，硬件结构上支持更快的并行。
软件的主要目的是使用当前的硬件压榨出最高的性能，给应用提供更稳定快速的计算结果。
我们传统的计算机结构一般是哈佛体系结构，主要分成三部分：
- 内存（指令内存，数据内存）
- 中央处理单元（控制单元和算数逻辑单元）
- 输入、输出接口
后面的冯·诺依曼结构就把数据和指令都当做数据来处理了，这里就不再介绍了，再次推荐《深入理解计算机系统》这本书，里面可以找到相关知识。
编写并行程序和串行程序的最大区别就是，编写串行程序可能不需要学习不同的硬件平台，但是编写并行程序就需要对硬件有一定的了解了。
并行性
编写并行程序主要是分解任务，我们一般把一个程序看成是指令和数据的组合，当然并行也可以分为这两种：
- 指令并行
- 数据并行
我们的任务更加关注数据并行，所以我们的主要任务是分析数据的相关性，哪些可以并行，哪些不能并行。
如果你对并行不太了解，可以先去学习pThread和OpenMP，了解在多核CPU上是怎么并行的，比如用OpenMP把for循环并行化。
任务并行多出现在各种管理系统，比如我们天天用的支付系统，基本上每时每刻都有很多人在同时使用，这时候就需要后台的处理能够并行执行这些请求，不然全国人民排队，那就比春运还热闹了。
我们研究的是大规模数据计算，计算过程比较单一（不同的数据基本用相同的计算过程）但是数据非常多，所以我们主要关 注数据并行。分析好数据的相关性，决定我们的程序设计。
CUDA非常适合数据并行。
数据并行程序设计的第一步就是把数据按照线程进行划分：
- 块划分：把一整块数据切成小块，每个小块随机地分配给一个线程，每个块的执行顺序随机（关于线程的概念可以去看《深入理解计算机系统》）
| thread | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| block | 1 2 3 | 4 5 6 | 7 8 9 | 10 11 12 | 13 14 15 |
- 周期划分：线程按照顺序处理数据块，每个线程处理多个数据块，比如我们有五个线程，线程1执行块1，线程2执行块2…..线程5执行块5，然后线程1执行块6
| thread | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| block | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
下面是示意图，注意颜色相同的块使用同一个线程，从执行顺序上看如下：
下面是从数据集划分上看：
不同的数据划分严重影响程序性能，所以针对不同的问题和不同计算机结构，我们要通过理论和实验共同来决定最终最优的数据划分。
计算机架构
Flynn's Taxonomy
划分不同计算机结构的方法有很多，广泛使用的一种被称为弗林分类法（Flynn's Taxonomy），它根据指令和数据进入CPU的方式分类，分为以下四类：
分别以数据和指令进行分析：
- 单指令单数据SISD（传统串行计算机，386）
- 单指令多数据SIMD（并行架构，比如向量机，所有核心执行相同指令，但是处理不同数据，现在CPU基本都有这 类的向量指令）
- 多指令单数据MISD（少见，多个指令处理同一个数据）
- 多指令多数据MIMD（并行架构，多核心，多指令，并行处理多个数据流，从而实现空间上的并行，MIMD多数情况下包含SIMD，就是MIMD有很多计算核，计算核支持SIMD）
为了提高并行的计算能力，我们要从架构上实现下面这些性能提升：
- 降低延迟
- 提高带宽
- 提高吞吐量
延迟是指操作从开始到结束所需要的时间，一般用微秒计算，延迟越低越好。
带宽是单位时间内处理的数据量，一般用MB/s或者GB/s表示。
吞吐量是单位时间内成功处理的运算数量，一般用GFLOPS来表示（十亿次浮点计算）。吞吐量和延迟有一定关系，都是反映计算速度的，一个是时间除以运算次数，得到的是单位次数用的时间——延迟；一个是运算次数除以时间，得到的是单位时间执行次数——吞吐量。
根据内存划分
计算机架构也可以根据内存进行划分：
- 分布式内存的多节点系统
- 共享内存的多处理器系统
第一个更大，通常叫做集群，就是一个机房好多机箱，每个机箱都有内存处理器电源等一系列硬件，通过网络互联，这样组成的就是分布式。
第二个是单个主板有多个处理器，它们共享相同的主板上的内存，内存寻址空间相同，通过总线与内存交互。
多个处理器可以分为多片处理器和单片多核（众核many-core），也就是有些主板上挂了好多片处理器，也有的是一个主板上就一个处理器，但是这个处理器里面有几百个核。
GPU就属于众核系统。当然现在CPU也都是多核的了，但是它们还是有很大区别的：
- CPU适合执行复杂的逻辑，比如多分支，其核心比较重（复杂）
- GPU适合执行简单的逻辑，大量的数据计算，其吞吐量更高，但是核心比较轻（结构简单）
总结
本文主要介绍了计算机架构的划分和并行计算的基础知识，后面我们继续介绍异构和CUDA。