通常对一个标量串行软件进行并行化有两种方法：

部分并行化：适合热点比较集中、涉及代码较少、代码的模块化比较好的软件。大多数程序软件满足80%-20%定律。

整体并行化：适合热点分散且整体的并行性很好的软件。整体并行化需要了解软件的整体流程逻辑、逻辑架构、物理架构、数据分布、数据相关性和作用在数据上的处理。

在一些情况下，完成局部并行化后，原来没有并行化的部分成了瓶颈，为了性能，此时可能需转化成整体并行化。

10.1 找出软件的计算热点

1. 如何选择测试数据集大小

通常可以更改程序使用的数据集大小来更改程序允许时间。允许不同的数据集测得的热点并不相同，原因可能如下;

由于分析工具分析方式导致结果不准；

一些函数在数据量比较小的情况下运行时间刚好比分析工具的灵敏度要小；

在不同的数据集下，程序允许的路径不同。

2. 使用哪种分析工具

分析工具：gprof，valgrind和intel Vtune等。笔者优先使用gprof，不是因为准确，而是因为GCC自带。

如果笔者怀疑测时不准确，一般也会使用其他工具验证，在必要时，笔者也会手工插入测时代码。

10.2 判断是否并行化热点

找出热点之后，并不是要立即着手并行化，还需要知道两个问题的答案：

        热点是否能够并行化？

        并行化热点投资要多少，是否能收回投资？

1. 热点是否具有并行性

如果热点没有并行性，那么就需要考虑是否采用其他的具有并行性的算法或者是能够通过重构算法使其具有并行性。

        大多数并行性来自于循环(数据并行)或函数(任务并行)。如果循环操作的代码没有依赖，那么循环就应当并行；反之，则需要重构代码消除依赖。

        如果循环操作的数据有依赖，但是可以通过通信方式(如锁、原子函数等)并行，且通信的代价很小。

        如果多个函数作用在不同的数据之上，那么认为可以使用任务并行；

        如果多个函数作用在相同的数据之上，但是可以通过通信方式解决冲突且通信代价很小，也可以认为是并行的。

        是否具有并行性还和使用的软硬件环境有关，更确切地说是和环境使用的并行模式有关。数据，任务，流水线并行。

数据、任务、流水线并行是可以相互转换的。

// 数据并行
void func(const float* __restrict__ data, size_t len)
{
    for (int i = 0; i < len; i++)
        process(data[i]);
}

// 任务并行
void func(const float* __restrict__ data, size_t len)
{
    int start = len / 2;
    p(data, start);
    p(d + start, len - len / 2);
}

void p(const float* __restrict__ data, size_t len)
{
    for (int i = 0; i < len; i++)
        process(data[i]);
}

//流水线并行
void func(const float* __restrict__ data, size_t len)
{
    float prev = data[0];
    float cur;
    for (int i = 1; i < len; i++)
    {
        cur = data[i];
        process(prev);
        prev = cur;
    }
    process(prev);
}

2. 是否能够向量化热点

如果热点具有并行性，那么需要考虑是否能够向量化热点。如果能够向量化热点，就能获得更好的性能提升。另外，目前大多数向量化代码性能的稳定性比多线程代码要好，应当优先采用。

不同的向量多核处理器支持的向量指令类型不同且有限，因此需要考虑向量化热点代码的话，那么主要操作指令在目标平台上是否得到支持也应当考虑。

3. 并行代价和收益是否匹配

实际上软件开发的估价一直是个难题，无数个项目都是因为资金无以为继才不得不终止。

10.3 设计算法并实现

在设计算法时，需要选定软硬件开发平台，比如目标代码在哪种硬件平台上运行，使用什么编程环境。

10.3.1 选择何种工具进行向量化或并行化

如果热点代码的向量化并行很好，那么就应当考虑向量处理器；如果不好，只能多线程并行处理器的向量化性能就不应当考虑，而只考虑多线程性能好的处理器。

如果对运行平台有限制的话，比如运行在ARM。

如果应用对延迟要求不高，而对吞吐量要求很高的话，GPU是一个很好的选择。如果应用对延迟和吞吐量要求都很高的，FPGA可能会更好。

关于编程语言，现实情况是：几乎所有的向量化和并行程序都是用C或Fortan编写的，一些开发人员也尝试使用C++的高编码效率和代码的可扩展性。

笔者认为：向量化和并行开发人员需要有选择的使用C++的语言特性，且要尽量保证代码对C是兼容的。

对于遗留代码而言，最好的选择是编译制导语句类型的并行化方案。

10.3.2 重构热点代码

遗留代码通常不是并行化方式编写的，笔者更建议先将热点代码重构成容易并行化的模式，然后再并行化。

为了更好地利用并行计算硬件地强大地计算能力，再并行化可能需要改变原软件地数据组织方式和局部地计算逻辑，此时也可以先重构。

重构热点代码的主要目的在于使热点代码更易于并行化。

// 循环拆分前
for (int i = 0; i < n; i++)
{
    a[i + 1] = b[i] + c;
    d[i] = a[i] + e;
}

// 循环拆分后
for (int i = 0; i < n; i++)
    a[i + 1] = b[i] + c;

for (int i = 0; i < n; i++)
    d[i] = a[i] + e;

重构热点代码的次要目的在于使得并行化后的代码性能更好，因此重构后的代码要能够更好地映射到目标硬件上。

// 重构前
for (int i = 0; i < n; i++)
{
    short int r = rgb_buf[3 * i];
    short int g = rgb_buf[3 * i + 1];
    short int b = rgb_buf[3 * i + 2];    
}

// 重构后
for (int i = 0; i < n; i++)
{
    short int r = r_buf[i];
    short int g = g_buf[i];
    short int b = b_buf[i];    
}

10.3.3 依据硬件实现算法

为了发挥硬件的性能，软件开发人员还是需要使用硬件友好的方式来编写代码。

从硬件指令集实现来说：统一指令在不同的硬件上其吞吐量和延迟不同；即使是同一向量处理器实现同一功能的不同指令的延迟和吞吐量也不相同。

不但要考虑使用硬件的特点，还要考虑并行化软件和原有软件的接口。

10.4 将实现后的代码嵌入原软件

通常使用两种方法：混合编译和使用动态链接库

10.4.1 混合编译

混合编译适合同种语言实现，因为并行化后的代码和原软件使用同一种编译系统，只是并行化代码使用了更多的库。此时可以将并行后的代码单独编译成编译系统的中间语言或目标代码(如可重定位二进制或汇编代码)。然后在原软件编译中链接编译后的中间代码。

下面是一个混合编译使用MPI部分并行化的代码：

        mpicc -c xx.c

        g++ yy.c xx.o -lmpi -o yy

通常库的混合使用表现为以下几种情况：

        如果使用C++调用C编写的库函数，需要在声明被调用函数时增加extern "C"前缀，然后直接链接该库即可。

        如果使用C调用C++编写的库函数B，可另外编写一个函数A以代理对B的访问，函数A的声明和实现都增加extern "C"前缀。

        如果使用Fortan调用C，则更为简单，因为Fortan的名字毁坏机制就是在函数名后增加一个下划线。

        如果需要使用C调用Fortan中A函数，使用A_调用即可。

实际上混合编译最困难出问题的是数据类型，因为不同的编译器对数据类型的长度、对齐和大小端有不同的要求。

笔者曾经遇到一个问题是在一个C和C++的混合编程项目中，由于对一个结构体的声明忘记使用extern "C"修饰，导致调试半个月。对于面对对象语言C++来说，不同的编译器会以不同的方式组织对象的虚函数表，其混合编译的难度就更大了。

10.4.2 动态链接库

动态链接库更改时无需重新编译程序，只要编译动态链接库即可，甚至可以在运行时替换动态链接库。

Linux下动态链接库的后缀名是so，下面的没拿过来将dl.c文件编程成动态链接库libdl.so。其中-fPIC表示生成与位置无关的代码。

gcc -shared -fPIC -o libdl.so dl.c

Linux下的动态链接库名字必须以lib开始。使用链接库：

gcc -o man man.c -ldl.so -L

其中-l选项指定链接的动态库的名字，不包括前缀lib。-L指定动态链接库所在的目录。如果动态链接库所在目录在系统环境变量LD_LIBRARY_PATH中，则不用显示指定-L选项指定动态编译库所在的目录。

与混合编译类似，不同的语言在处理数据类型和函数名的时候采用了不同的规则，使用动态编译库时需要注意这一点。

10.6 本章小结

通常并行化遗留代码的基本步骤是：

        1. 找出软件的计算热点

        2. 判断热点是否可并行化；

        3. 设计算法并实现；

        4. 将实现后的算法嵌入原软件

        5. 重新测试

在找出软件的计算热点时，需要注意选择测试数据集的大小和使用何种分析工具；

判断热点是否可并行化需要注意：热点是否有足够的并行性，进而需要分析热点是否能够被向量化，还需要评估并行化的代价公司是否能够承担。

在设计算法实现时，需要注意选择合适的实现工具，在实现前要提前重构原始代码，最后要根据硬件来实现算法。

通常将实现后代码嵌入原软件的两种方法：混合编译和使用动态并行库。