3.1 设计并行算法
为了在并行任务中获得成功，从一开始将并行的问题列出来是至关重要的。在里，我们将接触一些技术方面的解决方案。
1. 分治技术
当我们面对一个复杂的问题时，首先应该分解问题以便确定哪些部分可以独立的被处理。一般说来，在一个解决方案中，可并行的部分可以被不同的workers分开或者是分布式的执行。分治技术涉及到将一个完整的问题递归的分为不可再分的可被解决的小问题。排序算法，例如归并排序和快排都可以使用这种方法解决。
2. 使用数据分解
数据分解也可以解决并行化问题。想象一下有这么一个场景，在这个场景中我们要以标量4乘以一个2x2矩阵(这个矩阵被称为矩阵A).在一个顺序执行系统中，我们将一个接一个的执行每个乘法的操作，最后生成所有指令的最终结果。根据矩阵A的大小，这个问题的顺序解决方案可能是旷日持久的。然而，当数据分解被应用的时候，我们可以想象矩阵A被分解为一个一个小的部分，这些分片数据被相关的workers以并行的方式接受并处理。下图以一个2x2矩阵乘以一个标量值的案例说明了数据分解应用的概念：
上图中出现的矩阵相乘的问题有一定的对称性，每个必要的操作的结果是由一个单独的worker执行的，而且每个worker执行同样数量的操作来解决问题。然而，在现实世界中，worker的数量和已分解的数据数量的关系是不对称的，这将直接影响解决方案的性能。最后，每个worker所产生的结果必须整合起来以便使程序最终输出意义结果。为了进行这种整合，workers之间需要进行信息交换或是共享状态。
数据分解的粒度选择将会影响一个解决方案的性能。
3. 用管道分解任务
管道将大型的任务分割成独立并行的小任务。管道模型可以类比成汽车工厂的装配线，只不过输入代替底盘称为加工的原始材料。原料经过不同的生产阶段，几个worker一个接一个执行不同的操作直到产生最终结束。这个模型和顺序范式的开发类似，任务一个接一个的作用于数据上，正常情况下，一个任务以上一个任务的结果为输入。那么这个模型和顺序技术的区别是什么呢？管道技术中的每个阶段都拥有自己的workers，并且这些workers是以并行的方式执行的。
比如我们需要批量处理一些图片,并将抽取出的数据存入数据库的系统。我们将有以下实际的顺序：
- 接受输入的图像并且以对这些图片以并行的方式进行排列，这些图片将在第二阶段进行处理
- 解析图像，并且有用的信息将会被送到第三阶段
- 在第三阶段，过滤器被并行的应用在图像上
- 来自第三阶段的数据结果被保存在数据库中
每个阶段的管道技术都用自己
4. 处理和映射
workers的数量并不足以在一个单一的步骤里解决一个特定的问题。同时，分解技术不应该被随意使用，有些因素也会影响解决方案的性能。在数据或者任务分解之后，我们应该问这么一个问题：“我们应该在workers中如何划分进程的负载来获得比较好的性能？”这不是一个很好回答的问题，因为这取决于正在研究的问题。
基本上，我们在定义过程映射时可以提到3个重要的步骤：
识别独立的任务
在系统中识别独立的任务将允许我们在不同的workers之间分配任务，因为这些任务不需要持续的通信。因为不需要一个数据单元，所以任务可以在不同的workers间执行而不会影响其它任务的执行。
识别需要数据交换的任务
将需要相互通讯的任务组合起来放到单个worker中可以提高性能。当有大的通信负载的时候的时候这个真的可以提高性能，因为它能减少任务间信息交换的开销。
平衡负载
在并行解决方案中一个典型的问题是如何为不同的工作单元分配计算资源。我们越是将任务分配给不同的workers处理，我们将是需要越多的通信。另一方面，我们越是将任务组合起来分配給一个worker，与通信相关的开销越小。然而，我们也会浪费了计算的能力。
此外，越是将数据聚合在一个worker中,越会减少通过简单的添加更多的设备而增加计算能力的可扩展的灵活性。在一个基于通信的架构（轻微的数据聚合）中，为集群或者网格简单的增加机器从而提升处理性能甚至不需要中断正在运行的系统。
5. 应用于爬取之中
爬虫是由一个个浏览网页并从页面获取信息的程序组成。被分析的场景是一个问题，在这个问题中，一个顺序执行的爬虫会需要提供一组可变数量的 url 为参数。假设输入的链接数量相当大，我们可以在以下方法中寻找并行性的解决方案：
- 将所有的URLs分成组组合到一个数据结构中。
- 把这些URLs分配給多个任务，这样写任务会爬取每个URL中的包含信息。
- 将这些任务分派给多个并行的workers来执行。
- 由于前一阶段的结果必须传给下一个阶段，这将会改进未加工的存储的数据，因此保存它们关联它们到原始的URLs。
正如我们在上面编号的步骤中观察到的为了一个提出的解决方案，可以与以下两个方法结合：
- 数据分解：这发生在我们划分和关联URLs到任务上。
- 用管道进行任务分解：这包含三个阶段的管道，这发生在我们链接接收、存储以及组织爬取的结果的任务。