避免分支化表现
note
本文介绍一个并行计算中最常见的典型情况，并行分化(线程束分化的等价问题)，以及规约问题，以及其初步优化。
有时，控制流依赖于线程索引。线程束中的条件执行可能引起线程束分化，这会导致内核性能变差。通过重新组织数据的获取模式，可以减少或避免线程束分化。
下面我们用一个例子来学习避免并行分化的基本方法。
并行归约问题
并行归约是一个常见的问题，我们可以通过一个例子来学习并行归约的基本方法。假设我们要对有N个元素的整数数组求和。我们可以使用下面的代码来实现这个功能。
int sum = 0;
for (int i = 0; i < N; i++)
{
sum += a[i];
}
这段代码是串行的，我们可以使用并行的方法来加速这段代码的执行。我们可以将数组分成多个部分，然后每个线程计算一个部分的和，最后将所有线程计算的和相加就可以得到整个数组的和。之所以可以这样进行优化是因为加法满足交换律和结合律。
并行归约的常用方法是使用迭代成对实现。具体来说，我们首先将数组分成两个部分，然后每个线程计算一个部分的和，最后将所有线程计算的和相加就可以得到整个数组的和。然后我们将数组分成四个部分，然后每个线程计算一个部分的和，最后将所有线程计算的和相加就可以得到整个数组的和。然后我们将数组分成八个部分，然后每个线程计算一个部分的和，最后将所有线程计算的和相加就可以得到整个数组的和。以此类推，直到数组被分成的部分的个数等于线程束中线程的个数。
根据每次迭代后输出元素就地存储的位置，成对的并行求和实现可以被进一步分为以下两种类型：
- 相邻配对：元素与它们直接相邻的元素配对
- 交错配对：根据给定的跨度配对元素