12.1 并行算法设计的14准则

8-2定律；

选用合适的工具；

查找程序的热点可参考剖分软件的手册；

一般而言，并行性意味着不相关/独立，更详细地说，一些计算任务与另一些计算任务无关。

相比于自内而外，自外而内能够更早找出可并行化的部分，并且粒度通常也比较大，因此更适合多核并行，多进程和多线程。

在自外而内的方法中，首先对高层进行并行化，如果这一层没有并行性的话，看下一层能否并行化。

自内而外的方法首先要找到算法最内层的部分，然后在检查外部部分。自内而外的方法容易找到细粒度的并行，而向量化需要细粒度并行，因此对于向量化的任务，笔者推荐自内而外的方法。

计算通信比如果小到不能掩盖使用多个控制流所带来的控制流创建、调度和销毁的开销，就不应当并行化。在计算通信比将至1之后，在增加控制流的数目，程序的性能会越差。

评价并行程序的标准是控制流的最大计算复杂度和最大访存复杂度，而控制流的最大计算复杂度/最小计算复杂度和最大访存复杂度和最小访存复杂度反应了负载不均衡的程度。

隐式的多线程模型更易于编程和调试。因此在能满足功能需求的前提下，应尽量使用隐式模型(OpenMP)而将具体的线程建立、调度和销毁的实现交给编译器。显式的多线程模型(Pthread)能够提供更精确的控制，使用也更加自由。

如果程序的热点并行化能通过调用库函数来实现，那么就不要考虑调用自己手写的代码。一方面软件开发人员可能并没有库代码作者那么丰富的经验知识，另外库代码通常经过了非常丰富完备的测试，因此也更可靠。

可扩展性(scalability)用来衡量一个程序应对条件变化的能力，典型的变化有核心数量、内存大小、总线速度或数据量的增加等。

由于多线程执行顺序的不确定性(由操作系统的调度器决定)，不能准确预测多个线程的执行顺序，甚至在某个时刻那些线程会被调度到核心上执行也不能预测。这主要是为了隐藏程序运行时的延迟，特别是当线程数量多于核心的数量时。

顺序一致性的问题就是由这种执行顺序的不确定性引起的。

通信本身不属于计算任务，它只是为了确保程序的并行执行能得到正确的结果所产生的额外开销。尽可能把同步所产生的开销降低最最低，可以采用不同的通信方式达到。另外一个常用的方法是使用线程私有的存储空间或者局部变量来达到目的。

无须在线程间共享的临时变量和结果应由每个线程单独声明或分配。但是有些操作之间通信不可避免，此时尽量使通信比较少且在线程间分布均匀。通常使用锁、临界区、原子函数等协调对共享资源的访问。

在大量数据需要加锁的情况下，如果只用一个锁来保护数据，可能会造成严重的锁竞争从而导致性能瓶颈。因此可以使用多个锁来保护数据，每个所保护部分数据，提高了并行性，此时要尽量保证锁竞争数量相近。通常采用模余算法来确保锁保护的数据。

一旦数据结构设计好之后，算法的实现就基本很清楚了。

目前用于并行程序调试、差错的工具非常少，故最好边编程边验证。