本书意图呈现利用当今的计算机解决问题的技术, 包括顺序算法和并行算法. 举个例子, 你或许想要寻找到咖啡馆的最短路径 (不限于固定的店家, 追求的是路径最短). 我们关心的是正确性 (给出的路径的确是所有可能路径中最短的), 效率 (消耗的能量相对较少), 以及性能 (用时尽可能短).
本书涵盖了利用计算机解决问题的一些方面, 诸如
我们既关心并行算法也关心顺序算法. 然而, 这两种算法并没有那么不同.
术语并行
指的是同时运行多个计算或者说任务的能力. 如今一切计算机系统都拥有并行性, 并以多种不同的层次呈现.
并行何以重要. 首先, 直接的理由是并行计算比顺序计算更快. 速度一直是计算机科学及其应用的重要主题. 例如, 搜索引擎应该要以交互速度
完成任务, 一般来说是100毫秒以内. 其次, 就能量使用而言, 并行计算的效率更高. 根据基本物理, 主频达到原本的两倍的话, 功耗将是原本的八倍. 但是, 通过并行, (理想情况下)我们可以在不消耗更多能量的情况下以更快的速度完成任务. 概括一下, 其实也就是性能问题和效率问题.
假设我们有两台并行的电脑和一台顺序的电脑, 并且它们每台的速度和功耗相同. 如果我们将一个任务划分成两个相当的子任务, 分别让这两台并行的电脑计算, 最终合并它们的结果. 那么, 最终我们可以用一台顺序电脑所消耗的时间的一半完成相同的任务, 但是总耗能没有发生改变.
这完全是理论上的理想情况, 因为划分任务和合并结果都有开销. 这将导致耗时和耗能的增加. 有的时候, 当并行规模增长时, 这些开销可以变得渐渐能够忽略不计, 但并不总是如此.
我们以做菜打比方, 例如若要准备三道菜, 可以一个人按顺序做三道, 也可以三个人同时做, 每个人负责一道. 可能的开销是显然的 (例如需要分配谁做哪道菜), 而且在某种意义上还需要更多的资源, 比如说三个人同时做需要三口锅.
本节描述了两种度量, work和span.
本章回顾了描述, 问题, 实现的基本概念.