第1章
基于CUDA的异构并行计算
本章内容：
- 了解异构计算架构
- 认识并行程序设计的范例转换
- 掌握GPU程序设计的基本要素
- 了解CPU和GPU编程的区别
随着新科技和处理方法的普及，高性能计算（HPC）领域也在不断变化，而HPC的定义也随之产生了相应的变化。一般来说，它涉及多个处理器或计算机的使用，以高吞吐量和高效率来完成一个复杂的任务。HPC不仅可以认为是一个计算架构，还可以认为是包括硬件系统、软件工具、编程平台及并行编程范例的一组元素列表。
在过去的十几年中，高性能计算取得了极大的发展，尤其是GPU-CPU异构架构的出现，直接导致了在并行程序设计中一个基本的范例转变。将从本章开始学习异构并行程序设计。
1.1 并行计算
在过去的几十年间，人们对并行计算产生了越来越多的兴趣。并行计算的主要目标是提高运算速度。
从纯粹的计算视角来看，并行计算可以被定义为计算的一种形式，在这种形式下，计算机可以同时进行许多运算，计算原则是一个大的问题往往可以被划分为很多可以同时解决的小问题。
从程序员的角度来说，一个很自然的疑问，就是如何将并发计算映射到计算机上。假设你有许多计算资源，并行计算可以被定义为同时使用许多计算资源（核心或计算机）来执行并发计算，一个大的问题可以被分解成多个小问题，然后在不同的计算资源上并行处理这些小问题。并行计算的软件和硬件层面是紧密联系的。事实上，并行计算通常涉及两个不同的计算技术领域。
- 计算机架构（硬件方面）
- 并行程序设计（软件方面）
计算机架构关注的是在结构级别上支持并行性，而并行编程设计关注的是充分使用计算机架构的计算能力来并发地解决问题。为了在软件中实现并行执行，硬件必须提供一个支持并行执行多进程或多线程的平台。
大多数现代处理器都应用了哈佛体系结构（Harvard architecture），如图1-1所示，它主要由3个部分组成。
- 内存（指令内存和数据内存）
- 中央处理单元（控制单元和算术逻辑单元）
- 输入/输出接口
高性能计算的关键部分是中央处理单元（CPU），通常被称为计算机的核心。在早期的计算机中，一个芯片上只有一个CPU，这种结构被称为单核处理器。现在，芯片设计的趋势是将多个核心集成到一个单一的处理器上，以在体系结构级别支持并行性，这种形式通常被称为多核处理器。因此，并行程序设计可以看作是将一个问题的计算分配给可用的核心以实现并行的过程。
当实现一段串行算法时，你可能不需要为了编写一个程序而特意去理解计算机架构的细节。但是，当在多核计算机上执行算法时，对于程序员来说，了解基本的计算机架构的特点就显得非常重要了。要编写一个既正确又高效的并行程序需要对多核体系结构有一个基本的认识。
以下介绍了并行计算的一些基本概念，以及这些概念与CUDA编程设计的联系。
1.1.1 串行编程和并行编程
当用计算机程序解决一个问题时，我们会很自然地把这个问题划分成许多的运算块，每一个运算块执行一个指定的任务，如图1-2所示。这样的程序叫作串行程序。
有两种方法可以区分两个计算单元之间的关系：有些是有执行次序的，所以必须串行执行；其他的没有执行次序的约束，则可以并发执行。所有包含并发执行任务的程序都是并行程序。如图1-3所示，一个并行程序中可能会有一些串行部分。
从程序员的角度来看，一个程序应包含两个基本的组成部分：指令和数据。当一个计算问题被划分成许多小的计算单元后，每个计算单元都是一个任务。在一个任务中，单独的指令负责处理输入和调用一个函数并产生输出。当一个指令处理前一个指令产生的数据时，就有了数据相关性的概念。因此，你可以区分任何两个任务之间的依赖关系，如果一个任务处理的是另一个任务的输出，那么它们就是相关的，否则就是独立的。
在并行算法的实现中，分析数据的相关性是最基本的内容，因为相关性是限制并行性的一个主要因素，而且在现代编程环境下，为了提高应用程序的运行速度，理解这些是很有必要的。在大多数情况下，具有依赖关系的任务之间的独立的关系链为并行化提供了很好的机会。
1.1.2 并行性
如今，并行性的应用非常广泛，在编程领域，并行编程设计正在成为主流。多层次的并行性设计是架构设计的驱动力。在应用程序中有两种基本的并行类型。
- 任务并行
- 数据并行
当许多任务或函数可以独立地、大规模地并行执行时，这就是任务并行。任务并行的重点在于利用多核系统对任务进行分配。
当可以同时处理许多数据时，这就是数据并行。数据并行的重点在于利用多核系统对数据进行分配。
CUDA编程非常适合解决数据并行计算的问题。本书的重点便是如何使用CUDA编程解决数据并行问题。许多处理大数据集的应用可以使用数据并行模型来提高计算单元的速度。数据并行处理可以将数据映射给并行线程。
数据并行程序设计的第一步是把数据依据线程进行划分，以使每个线程处理一部分数据。通常来说，有两种方法可以对数据进行划分：块划分（block partitioning）和周期划分（cyclic partitioning）。在块划分中，一组连续的数据被分到一个块内。每个数据块以任意次序被安排给一个线程，线程通常在同一时间只处理一个数据块。在周期划分中，更少的数据被分到一个块内。相邻的线程处理相邻的数据块，每个线程可以处理多个数据块。为一个待处理的线程选择一个新的块，就意味着要跳过和现有线程一样多的数据块。
图1-4所示为对一维数据进行划分的两个例子。在块划分中，每个线程仅需处理数据的一部分，而在周期划分中，每个线程要处理数据的多个部分。图1-5所示为对二维数据进行划分的3个例子：沿y轴的块划分，沿x轴和y轴的块划分，以及沿x轴的周期划分。其余的划分方式为沿x轴的块划分，沿x轴和y轴的周期划分，以及沿y轴的周期划分留作练习。
通常，数据是在一维空间中存储的。即便是多维逻辑数据，仍然要被映射到一维物理地址空间中。如何在线程中分配数据不仅与数据的物理储存方式密切相关，并且与每个线程的执行次序也有很大关系。组织线程的方式对程序的性能有很大的影响。
1.1.3 计算机架构
有多种不同的方法可以对计算机架构进行分类。一个广泛使用的分类方法是弗林分类法（Flynn抯 Taxonomy），它根据指令和数据进入CPU的方式，将计算机架构分为4种不同的类型（如图1-6所示）。
- 单指令单数据（SISD）
- 单指令多数据（SIMD）
- 多指令单数据（MISD）
- 多指令多数据（MIMD）
SISD指的是传统计算机：一种串行架构。在这种计算机上只有一个核心。在任何时间点上只有一个指令流在处理一个数据流。
SIMD是一种并行架构类型。在这种计算机上有多个核心。在任何时间点上所有的核心只有一个指令流处理不同的数据流。向量机是一种典型的SIMD类型的计算机，现在大多数计算机都采用了SIMD架构。SIMD最大的优势或许就是，在CPU上编写代码时，程序员可以继续按串行逻辑思考但对并行数据操作实现并行加速，而其他细节则由编译器来负责。
MISD类架构比较少见，在这种架构中，每个核心通过使用多个指令流处理同一个数据流。
MIMD是一种并行架构，在这种架构中，多个核心使用多个指令流来异步处理多个数据流，从而实现空间上的并行性。许多MIMD架构还包括SIMD执行的子组件。
为了实现以下目的，在架构层次上已经取得了许多进展。
- 降低延迟
- 提高带宽
- 提高吞吐量
延迟是一个操作从开始到完成所需要的时间，常用微秒来表示。带宽是单位时间内可处理的数据量，通常表示为MB/s或GB/s。吞吐量是单位时间内成功处理的运算数量，通常表示为gflops（即每秒十亿次的浮点运算数量），特别是在重点使用浮点计算的科学计算领域经常用到。延迟用来衡量完成一次操作的时间，而吞吐量用来衡量在给定的单位时间内处理的操作量。
计算机架构也能根据内存组织方式进行进一步划分，一般可以分成下面两种类型。
- 分布式内存的多节点系统
- 共享内存的多处理器系统
在多节点系统中，大型计算引擎是由许多网络连接的处理器构成的。每个处理器有自己的本地内存，而且处理器之间可以通过网络进行通信。图1-7所示为一个典型的分布式内存的多节点系统，这种系统常被称作集群。
多处理器架构的大小通常是从双处理器到几十个或几百个处理器之间。这些处理器要么是与同一个物理内存相关联（如图1-8所示），要么共用一个低延迟的链路（如PCI-Express或PCIe）。尽管共享内存意味着共享地址空间，但并不意味着它就是一个独立的物理内存。这样的多处理器不仅包括由多个核心组成的单片机系统，即所谓的多核系统，而且还包括由多个芯片组成的计算机系统，其中每一个芯片都可能是多核的。目前，多核架构已经永久地取代了单核架构。
“众核”（many-core）通常是指有很多核心（几十或几百个）的多核架构。近年来，计算机架构正在从多核转向众核。
GPU代表了一种众核架构，几乎包括了前文描述的所有并行结构：多线程、MIMD（多指令多数据）、SIMD（单指令多数据），以及指令级并行。NVIDIA公司称这种架构为SIMT（单指令多线程）。
GPU和CPU的来源并不相同。历史上，GPU是图形加速器。直到最近，GPU才演化成一个强大的、多用途的、完全可编程的，以及任务和数据并行的处理器，它非常适合解决大规模的并行计算问题。