本书介绍如何在多核处理器的共享内存模型中实现算法。本书包含许多示例程序，有助于将串行代码转换为并行代码，还介绍了如何避免一些常见的错误。

为什么要读本书
　　多核处理器在问世之初就展示出了强大的威力。由于发热量以及能耗的增加，处理器的时钟频率无法再像过去30 年那样每18 个月翻一番。为了保证下一代处理器运算能力的持续增加，处理器生产商开始在芯片内部设计多个处理器核。虽然多核处理器的运行速度有所降低，但与时钟频率翻番的单核处理器核相比，它们产生的热量更少，并且能耗也更低。
　　然而，如何来充分发挥多核的强大运算能力？我们可以每次运行多个程序，并且为每个程序专门分配一个处理器核来运行。这就实现了真正意义上的并行执行。然而，在这种情况下能够同时运行的程序数量也只能是等于处理器核的数量。如果这些程序并非是计算密集型的程序，那么可能会浪费计算周期。
　　另一种方式是，在编写程序时，将需要执行大量计算并且在计算之间彼此独立的代码放在另外的处理器核上执行。编写这种程序的过程就称为并发编程。与任何一种编程语言或者方法一样，在设计和实现并发程序中同样存在着许多技术、窍门、误区以及工具。我始终觉得这种编程还是一种“艺术”，留有足够大的自由发挥空间，而并非像一门“科学”那样有着严格的步骤可供遵循。因此，本书将介绍并发编程中的一些基础知识和少量的“内幕技术”。
　　在过去，并行和并发编程只是少数程序员的专有技术，他们的研究领域通常与科学计算等方面相关。然而，从现在开始，并发编程正在逐步成为一种主流技术。并行编程最终将成为“编程”的同义词。现在，你要着手开始学习并发编程，或者至少要跟上并发编程的发展趋势。
本书的目标读者
　　本书适合各类程序员阅读。
　　在我工作的计算机技术公司中，团队里只有我一个人拥有计算机科学学位。当我提到想通过一个确定型下推自动机（Deterministic Pushdown Automata ）来解析LR(1) 语法时，在办公室里也只有另一个人能明白我的意思。因此，计算机专业的学生只是本书目标读者的一部分。在本书中，我尽可能少地使用计算机专业的特定知识。我假设本书的读者已经在数据结构、算法以及算法复杂度等方面具备了一定的基础知识，这些知识通常会在计算机科学专业的本科课程中教授。对于我所介绍的其他内容，我都会尽力给出足够详细的解释来使读者了解其中的思想。如果你有着一年以上的编码经验，那么理解起来就不成问题。
　　我用C语言编写了所有代码。这并不意味着不尊重其他语言，而是我发现C语言是支持线程并且得到最多认同的编程语言之一。其他语言，如Java 和C# 等，同样支持线程，但如果我在书中用这些语言来编写代码，而你又没有使用过这些语言，那么就不会阅读本书。我认为，大多数能够编写并发程序的程序员至少都能够“读懂”C代码。理解在代码中使用的各种并发方法要比用某种特定语言来编写代码的能力更为重要。你同样可以在C# 或者Java 中实现这些思想。
　　我假设你至少已经读过了一本介绍多线程编程的书。市面上已经有许多这类的书，因此我不会在本书中详细介绍多线程编程的各种机制（因为这些内容至少要占到一两本书的篇幅）。在本书中我同样不会只使用一种编程模式，因为许多编程模式的功能在很大程度上都是重叠的。在本书的后半部分，我将给出如何在各种算法中使用线程化方法。在一些情况中，如果某种方法与其他方法在使用上存在较大的差异，那么在书中将指出这些差异。
　　对于在本书中使用的各种线程化编程方法，我都给出了简要的回顾，这样你能够重新回想起它们，或者了解那些还没有使用过的方法。但我的本意并非是说你需要知道所有编写多线程程序的方式。只要了解其中一种就足够了。不过，如果你换了一份工作或者发现你所掌握的多线程编程方法不能很好地解决你所遇到的问题，那么了解其他多线程编程方法就是有用的—— 这将帮助你很快地学习和使用某种新方法。
本书的内容
　　第1章，“并行让程序运行得更快”，介绍了一些在并发编程中常见的问题以及相应的答案。本章介绍了“并行（Parallel ）”与“并发（Concurrent ）”这两个术语的区别，并给出了线程化方法中的4个步骤。本章最后介绍了关于并发编程的一些背景知识，以及在分布式内存模型和共享内存模型之间的一些差异和相似性。
　　第2章，“是否采用并发”，介绍了如何根据串行算法来设计并发算法。本章详细阐述了两种并发设计模型—— 任务分解与数据分解。本章还给出了一些无法并行化的串行代码示例。在一些可以并行化的示例中，我给出了相应的提示和技巧来将串行代码修改为更易于并行化的形式。
　　第3章，“算法正确性证明与性能衡量”，首先介绍了如何证明在并发算法中不包含一些常见的线程化错误，并且指出了你所可能遇到的问题（这样就可以修复这些问题）。本章的第2部分介绍了如何判断并发代码相对于最初串行代码的性能提升程度。本章最后简单回顾了硬件从过去一直到当前多核处理器的发展历程，因为我觉得似乎只有在这个地方才合适介绍这些内容。
　　第4章，“多线程程序设计中的8条简单规则”，介绍的内容在本章标题中已经说得很清楚了。本书中的许多地方都将提到这些简单的规则。
　　第5章，“线程化库”，介绍了OpenMP 、Intel Threading Building Block 、POSIX 线程以及Windows 线程库等。本章最后还介绍了在一些特定领域使用的库。
　　第6章，“并行求和与前缀求和”，详细介绍了两种并发算法。本章同样还介绍了并发选择算法，并且在实现并发选择算法时分别使用了并行求和与前缀求和。
　　第7章，“映射归约”，介绍了映射归约算法框架；如何实现一个完全并发的归约运算；并且最后介绍了如何通过映射归约算法框架来找出互为友好的数值。
　　第8章，“排序”，介绍了并发的冒泡排序、奇偶移项排序、希尔排序、快速排序以及两种基数排序。
　　第9章，“搜索”，介绍了对已排序数据和未排序数据进行并发搜索的算法。
　　第10 章，“图算法”，分析了深度优先搜索算法和宽度优先搜索算法。同时还讨论了如何并发地计算两节点之间最短路径以及最小生成树。
　　第11 章，“线程化工具”，介绍了一些软件工具来帮助找出并发程序中线程化错误和性能瓶颈。当并发代码变得越来越复杂时，你将发现这些工具的强大之处，它们能够在几分钟之内诊断出问题，而不是花数天或者数个星期。
排版约定
斜体字（Italic）
　　表示新的术语、URL 、电子邮件地址、文件名、文件扩展名、路径名、目录以及UNIX 工具。
等宽（Constant width）
　　表示命令、选项、分支、变量、标签、键、函数、类型、类、命名空间、方法、模块、属性、参数、值、对象、事件、事件处理器、XML 标识、HTML 标记、宏、文件内容以及命令的输出。
等宽加粗（Constant width bold）
　　显示需用户输入的命令行或其他文本。也用于强调某段代码示例。
等宽斜体（Constant width italic）
　　用来显示需要用户提供值来代替的文本。
联系方法
　　如果您对本书的意见和问题，请联系出版社：
美国：
　　O,Reilly Media, Inc.
　　1005 Gravenstein Highway North
　　Sebastopol, CA 95472
中国：
　　北京市西城区西直门南大街2号成铭大厦C座807 室（100035）
　　奥莱利技术咨询（北京）有限公司
　　我们对本书有专门的网页来提供额外的代码和更多的附加信息，你可以访问这个页面地址：
　　http://www.oreilly.com/catalog/9780596521530 （英文版）
　　http://www.oreilly.com.cn/book.php bn=978-7-111-30938-3 （中文版）
　　提错或者有问题请发邮件到：
　　bookquestions@oreilly.com 。
　　关于我们的书籍、会议、资源中心、O’Reilly 网络的更多信息，请访问我们的站点：
　　http://www.oreilly.com
　　http://www.oreilly.com.cn
致谢
　　我想感谢以下对我的职业生涯有着重要影响并且支持我写本书的人们。如果没有他们的帮助和支持，也就不会有这本书，而我的生活也不会像现在这么美妙。
　　感谢Joseph Sargent 和Stanley Chase 出品的电影《Colossus:The Forbin Project 》（1970 ）。这部电影对早期的我产生了非常大的影响，它使我对计算机编程产生了浓厚的兴趣，并且充满了好奇心要找出计算机能够实现的各种奇妙功能。
　　感谢Roger Wink 点燃了我对计算机的兴趣，我们之间有着30 多年的友谊。他教会了我用Cobol 语言编写冒泡排序，每次我们见面时，他总是能够带来一些新鲜有趣的东西。
　　感谢Bill Magro 和Tom Cortese ，他们分别是我在Intel 公司的第一位经理和Intel Parallel Application Center 的第一位同事。在PAC 的工作经历中，我有幸参与编写了各种不同的
　　并行代码，与来自不同技术领域和商业领域的客户进行沟通，并且学到了许多新的方法和新的线程化库。这对我来说就是一种梦想中的工作。
　　感谢我在Intel 公司的同事Jerry Baugh 、Bob Chesebrough 、Jeff Gallagher 、Ravi Manohar 、Mike Pearce 、Michael Wrinn 和Hua (Selwyn) ，感谢你们对本书中技术内容的审阅和建议。他们每个人的技术知识都给了我很大的帮助；感谢他们对我的项目和目标的支持、有见地的建议，以及多年在Intel 公司的友谊。
　　感谢编辑Mike Loukides ，以及O’Reilly 公司参与本书编撰的其他工作人员。如果没有他们的帮助和建议，我将完成不了本书。
　　感谢Gergana Slavova 作为我的“目标读者”，她帮我一遍又一遍地审阅本书的内容。她帮助我用简洁的语言来阐述一些复杂的思想，并且当我在单个段落中放入过多的细节时增加一些示例，除此之外，她的幽默注释使得本书的修改过程不再乏味无趣。
　　感谢Henry Gabb 在并行编程和多线程编程方面的知识，他说服我申请PAC 的职位，并且在2000 年重新回到Intel 与他一起工作，感谢他对SEC Football 和Chicago Cubs 的热爱。我们彼此之间相互了解已经有大约15 年了。我们在许多不同的项目上共事过，并且相互讨论技术问题。他不仅是本书的技术审稿人，而且多年来帮我审阅了多篇文章，这些都帮助我将写作技术提高了一个层次。
　　最后，感谢我深爱的妻子Lorna ，现在她的丈夫又回到了她身边。

这是一本非常棒的书，从它的名字就可以看出来。虽然你教的可能并不是艺术，但你可以让学生们了解一下专家们的思维和方法。我在超级计算公司工作过30余年的时间，并在现在在学术界从事研究也有将近10年的时间了，因此我可以肯定地告诉各位读者，本书的内容绝对值得一读。
Tom Murphy，Contra Costa大学，计算机科学委员会主席
　　　　　　　　　　　　　　　　

终于出现了一本专门介绍并发性的书。书中介绍了大量实用的重要算法，并且采用多种方式对算法进行分析，重点讲解了如何通过各种并行编程技术来提升程序的性能。

Mike Pearce，Intel Software Network网站，并行计算负责人

如果你希望通过并发编程来充分发挥多核处理器的强大功能，那么本书将为你提供所需的理论知识和实际经验。《并发的艺术》是为数不多的几本介绍如何在多核处理器的共享内存模型中实现算法的书籍之一，它并非仅仅介绍一些理论模型或者分布式内存架构。本书详细分析了各种示例程序，这些内容非常有助于你将串行代码转换为并行代码，此外还介绍了如何避免一些常见的错误。
本书的作者是Intel公司的一位资深工程师，他从事并发编程已经有20多年的时间，本书将帮助你：
- 分析在共享内存模型与在分布式内存模型之间的编程差异。
- 学习如何设计多线程程序，包括对程序的测试和调优。
- 了解如何最有效地使用各种不同的线程化机制，包括Windows线程，POSIX线程，OpenMP以及Intel Threading Building Blocks。
- 掌握如何实现各种并发算法，包括排序，搜索，图以及其他一些使用的计算。

《并发的艺术》还介绍了如何在算法中实现高可伸缩性，使得算法能够充分发挥将来包含更多核处理器的强大功能。对于开发并行代码算法的程序员来说，本书是必不可少的。

Clay Breshears博士，目前是一位课程设计师，主要从事多核与多线程方面的编程和培训。

Clay Breshears 著：暂无简介

聂雪军 等译：暂无简介

多核处理器的出现，使得程序开发人员开始关注并发编程技术，然而要掌握并合理使用并发技术却并不容易。对于长期编写串行程序的开发人员来说，转向并发编程并不仅仅意味在代码中增加一些同步对象，或者调用某个第三方并行库的API ，而是要在程序架构设计、编程模型选择、代码测试以及调优等方面做出整体改变。与其他任何一种技术一样，程序员在学习并发编程时应该采取一种循序渐进的、由理论到实践的方法，而这也是本书为读者给出的学习方式。
　　本书的前面部分给出了一个完备的并发程序开发框架，包括并发的基础理论知识、不同并发模型的选择与适用环境、编写并发程序的基本步骤，并发算法的正确性证明与性能评价，以及在编写并发程序时遵循的一些指导原则等。这些内容使读者能够对并发编程有基本的了解，在开始动手编写并发代码之前首先作出全面的思考，这样不仅可以提高编码的效率，而且可以减少代码中的错误以及后续的修改/维护工作。
　　之后，书中对一些典型算法的并行化过程进行了详细分析，这些算法包括并行求和与前缀求和、映射归约、排序、搜索以及图算法等。在对算法并行化时采取的讲解方式是：首先给出算法的串行实现，然后对算法中的并发性进行分析并选择合理的技术来实现这些并发性，最后从效率、简单性、可移植性以及可伸缩性等4个方面对并发算法衡量。
　　这些分析也是本书中最具价值的部分，读者在阅读这些内容时要反复思考和琢磨，做到融会贯通，举一反三。这些算法虽然简单，但我们都知道复杂算法通常是由多个简单算法组成的，因此只要掌握了这些简单并发算法的设计，更复杂的算法也就会迎刃而解。
　　总体来说，本书是一本更侧重于实践的书，书中提到的许多技术都可以直接应用到日常工作中，并且书中的代码只需要稍加修改就可以直接使用。本书适合所有程序员阅读，只需具备一些基础的数据结构和算法知识，就不难理解本书的内容。
　　参与本书翻译工作的还有李杨、吴汉平、徐光景、童胜汉、陈军、胡凯、刘红、张玮、陈红、李斌、李勇涛、王海涛、周云波、彭敏才、张世锋等。由于译者的时间和水平有限，翻译中的疏漏在所难免，还望读者和同行不吝指正。

前言............................................................................ 1
第1章并行让程序运行得更快....................................... 7
你可能会想到的一些问题...................................................................................8
采用线程化方法的4个步骤...............................................................................13
并行算法的背景知识.........................................................................................18
共享内存编程与分布式内存编程的比较...........................................................21
本书采用的并发编程方法.................................................................................24
第2章是否采用并发................................................... 27
并发算法的设计模型.........................................................................................28
哪些算法不能并行.............................................................................................47
第3章算法正确性证明与性能衡量.............................. 53
并行算法的验证................................................................................................54
示例：临界区问题.............................................................................................56
性能测试（程序的执行情况如何）.................................................................69
硬件并行性的发展历史.....................................................................................75
第4章多线程程序设计中的8条简单规则...................... 77
规则1：找出真正独立的运算............................................................................78
规则2：在尽可能高的层次上实现并发.............................................................78
规则3：尽早考虑通过增加处理器核的数量来获得可伸缩性...........................79
规则4：尽可能使用线程安全的库....................................................................80
规则5：使用正确的多线程模型........................................................................81
规则6：永远不要假设程序会按照某种特定的顺序执行...................................81
规则7：尽可能使用线程局部存储或者与特定数据相关的锁...........................82
规则8：要敢于对代码进行修改以获得更好的并发性......................................83
小结.............................83
第5章线程化库......................................................... 85
隐式线程化........................................................................................................86
显式线程化........................................................................................................92
其他主题...........................................................................................................96
特定领域的库....................................................................................................96
第6章并行求和与前缀求和........................................ 99
并行求和.........................................................................................................100
前缀求和.........................................................................................................106
选择.......................................... 115
最后的思考.................................................126
第7章映射归约....................................................... 127
并发映射运算..................................................................................................129
并发归约运算..................................................................................................131
映射归约的应用..............................................................................................139
映射归约作为一般性并发...............................................................................144
第8章排序.............................................................. 145
冒泡排序.........................................................................................................146
奇偶换位排序..................................................................................................153
希尔排序.........................................................................................................162
快速排序.........................................................................................................168
基数排序.........................................................................................................180
第9章搜索.............................................................. 197
未排序的数据序列...........................................................................................198
二分搜索.........................................................................................................206
第10 章图算法......................................................... 215
深度优先搜索..................................................................................................218
最短路径问题..................................................................................................233
最小生成树......................................................................................................238
第11 章线程化工具.................................................. 249
调试器.....................................................................250
性能工具.........................................................................252
其他主题...................................................................................254
再接再厉....................................................................................255
术语表.................................................................... 257
照片说明................................................................. 267