并行计算和计算机集群/理论
人们用计算机集群做什么？
- 网络
- 搜索引擎索引
- 数据库
- 科学和工程工作
- 天气建模和预测
- 分子建模
- 产品设计和模拟
一般来说，实现并行架构有两种方法。它们可以分别使用，也可以将这两种方法组合起来使用。共享内存模型是一种所有处理器共享内存和地址空间的模型。架构中的所有处理器都可以访问所有连接的主内存。消息传递模型是一种将信息打包到消息中的模型。这些信息的离散单元可以传递给架构中的各个 CPU。这两种架构都有各自的优缺点。
共享内存模型是所有 CPU 都可以寻址机器主内存的模型。通常，主内存可以通过总线访问。这使得所有 CPU 都可以使用内存地址，并且地址可以在不同的 CPU 之间传递。让所有 CPU 都通过总线访问内存会引入一些问题。比如总线的带宽，如果总线很小，而 CPU 的数量很多，那么 CPU 使用率的优化将难以实现。通常，总线通信会使用本地缓存来增强。处理器的 L1 和 L2 缓存，然后就会引入缓存一致性的挑战。如何确保主内存和缓存中的数据足够更新，以便所有 CPU 都能看到正确的数据。这里有几种策略可以实现正确和优化的操作。
消息传递系统具有与 CPU 不直接连接的内存，甚至可能分布在各个地理位置。这会导致发送和接收系统，其中数据被打包成消息，并通过网络发送到网络中的其他机器。
Hadoop 的核心是两个开源框架的组合：MapReduce 和 HDFS。两者都是基于谷歌发布的同名白皮书的开源实现。MapReduce 是一个基于谷歌同名框架的处理框架。MapReduce 会获取存储在 HDFS 中的数据，并在集群中的每个节点上进行处理。MapReduce 由程序员定义两个过程：Map 和 Reduce。Mapper 以键值对的形式获取数据。Mapper 也会输出键值对。Reducer 的输入格式是一个键和一个向量，其中包含由 Mapper 输出的该键的所有值。HDFS 是 Hadoop 文件系统。HDFS 是谷歌分布式文件系统的实现。HDFS 是一个软件实现，它将文件的存储分布到集群中的多个节点。默认复制因子为 3，以确保以极高的概率不会丢失任何数据。
并行处理是在多个处理器上同时执行相同的任务（分割并专门调整），以便获得更快的结果。并行性可以来自具有多个处理器的单台机器，也可以来自连接在一起形成集群的多台机器。
阿姆达尔定律是 边际收益递减定律 的一个证明：虽然可以将计算机的某个部分加速一百倍甚至更多，但如果改进只影响总体任务的 12%，那么最好的 加速 可能只能达到 倍更快。
更准确地说，该定律关注的是对计算进行改进后可以实现的 加速，改进影响了计算的 P 比例，改进的加速为 S。（例如，如果一项改进可以加速 30% 的计算，P 将为 0.3；如果改进使受影响的部分速度提高一倍，S 将为 2。）阿姆达尔定律指出，应用改进后整体加速将为
- .
为了理解该公式的推导过程，假设旧计算的运行时间为 1，以某个时间单位计量。新计算的运行时间将是未改进部分所花费的时间（即 1 − P）加上改进部分所花费的时间。改进部分的运行时间是其原运行时间除以加速比，因此改进部分的运行时间为 P/S。最终的加速比是通过将旧运行时间除以新运行时间计算得出，这正是上面公式所做的操作。
在并行化的特殊情况下，阿姆达尔定律指出，如果 F 是计算中无法并行化的部分（即顺序执行的部分）的比例，(1 − F) 是可以并行化的部分的比例，那么使用 N 个处理器所能达到的最大加速比为：
- .
当 N 趋近于无穷大时，最大加速比趋近于 1/F。在实际应用中，当 (1 − F)/N 比 F 小很多时，性价比会随着 N 的增加而迅速下降。
例如，如果 F 仅为 10%，无论 N 的值有多大，问题最多只能加速 10 倍。因此，并行计算 仅适用于少量处理器，或者 F 值非常低的所谓简单并行问题。并行编程 的一大技巧就是尝试将 F 降低到尽可能小的值。