算法导论第三版新增27章中文版

计算机科学与技术

多线程算法（完整版）

——算法导论第 3 版新增第 27 章

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Ste

in

邓辉 译

原文： /sites/products/documentation/cilk/boo

k_chapter.pdf

本书中的主要算法都是顺序算法 ，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法 ，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。

并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器 桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些 PC 级的电脑）组成的集群，通过专用的网络连接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。