---------------------------离散数学及其应用(原书第8版)---------------------------
本书是根据我多年来讲授离散数学的经验和兴趣写成的。对学生而言,我的目的是为他们提供内容准确且可读性强的教材,清晰地介绍并展示离散数学中的概念和技术。对于那些爱怀疑的学生,我的目标是展示离散数学的相关性和实用性。对于计算机科学专业的学生,我希望为他们将来的学习提供一切必需的数学基础。而对于数学专业的学生,我希望帮助他们理解重要的数学概念,并且意识到为什么这些概念对应用来说很重要。最重要的是,希望本书既能达到这些目标,又不含太多的水分。
对教师而言,我的目的是利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具:只要有本书在手,教师就能迅速地从中筛选内容,以最适合特定学生的方式有效地开展离散数学的教学工作。希望我已经实现了这些目标。
在过去的30年中,本书取得了极大的成功,被世界各地超过100万名学生使用,并被翻译成多种语言,对此我感到非常欣慰。此次第8版所做的许多改进,正是得益于大量读者的反馈和建议。在这些读者中,既有来自北美600多所学校的师生,又有来自全球各地众多高校的读者,他们都曾将本书成功用作教材。由于所收到的这些反馈,以及在不断更新中所投入的大量精力,我才能够在每次升级时显著提高本书的吸引力和有效性。
本教材是为一学期或两学期的离散数学入门课程而设计的,适用于数学、计算机科学、工程等各类专业的学生。大学代数是唯一要求的先修课程,不过,要想真正学好离散数学,还是需要有一定的数学素养。本书的设计目标是满足各种类型离散数学入门课程的需求,内容高度灵活且非常全面。我希望本书不仅是一本成功的教科书,而且成为学生在日后的学习和职业生涯中可以参考的有价值的资源。
离散数学课程的目标
离散数学课程有多个目标。学生应该学会一系列特定的数学知识并知道怎样应用它们,更重要的是,这门课应教会学生怎样运用数学逻辑思维。为了达到这些目标,本教材特别强调数学推理以及问题求解的不同方法。本书中,五个重要主题将交织在一起:数学推理,组合分析,离散结构,算法思维,以及应用与建模。一门成功的离散数学课程应该小心谨慎地融合并平衡所有五个主题。
●数学推理。学生必须理解数学推理以便阅读、领会并构造数学论证。本书开篇即讨论数理逻辑,这为后续讨论证明方法打下了基础。本书描述了构造证明的方法与技巧两个方面。本书特别强调数学归纳法,不仅给出了这种证明技术的许多不同类型的实例,还详细地解释了数学归纳法为什么是一种有效的证明技术。
●组合分析。一个重要的解题技巧就是计数或枚举对象。本书中关于枚举的讨论从计数的基本技术着手。重点是运用组合分析方法来解决计数问题并分析算法,而不是简单地应用公式。
●离散结构。离散数学课程应该教会学生如何处理离散结构,即表示离散对象以及对象之间关系的抽象数学结构。这些离散结构包括集合、置换、关系、图、树和有限状态机等。
●算法思维。有些类型的问题可以通过算法的规范说明来求解。当一个算法被清楚地描述后,就可以编写计算机程序来实现之。该活动涉及的数学部分包括该算法的规范说明、正确性的验证,以及执行算法所需要的计算机内存和时间分析等,这些在本书中均有阐述。算法将采用自然语言原书采用英语,而中译版则采用汉语。——译者注和一种易于理解的伪代码形式来描述。
●应用与建模。离散数学在几乎每个可以想到的研究领域中都有应用。许多应用涉及本书提到的计算机科学和数据网络,还有一些应用涉及更为广泛的领域,如化学、生物学、语言学、地理学、商业和互联网等。这些是离散数学的自然而又重要的应用,而非人为编造的。用离散数学来建模是一项十分重要的问题求解技巧,学生可通过一些练习来自己构造模型,从而掌握这一技巧。
第8版中的变化
虽然第7版已经是一本极具影响力的教材,但许多教师还是提出了一些修改请求,以使本书更适于教学。我花了大量的时间和精力来满足这些请求,努力以自己的方式改进本书并使之紧跟最新发展。
第8版的修改基于20多位正式审稿人的意见、学生和教师的反馈以及我自己的见解,希望新版本能成为一个更加有效的教学工具。第8版中所做的大量更新是为了帮助学生更好地学习这些内容。我增加了额外的解释和例子以便阐述那些学生经常感到困难的内容,增加了知识性的和富有挑战性的新练习,还增加了一些与Internet、计算机科学以及数学生物学等密切相关的应用。在开发人员的努力下,本书配套网站现在提供了很多工具,可以帮助学生掌握关键概念并探索离散数学世界。此外,还提供了有效和全面的学习和评估工具,以作为教科书的补充。
. 我希望教师能仔细阅读新版,以了解如何满足自己的教学需求。要列出所有更新是不切实际的,不过,我将给出概要性的描述,包括一些关键更新及其所带来的好处,这对读者来说或许是有益的。
本书新版对许多内容进行了完善、更新、补充和润色,所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。之前使用过本教材的教师会发现这次更新遍及全书,其中最值得注意的修订如下。
全书范围的更新
●对内容编排的完善贯穿全书,重点是使之更清晰,以便帮助学生阅读和理解概念。
●通过增加细节和解释来改进证明,同时提醒读者注意所采用的证明方法。
●新增例题,用于满足审稿人提出的需求,或是对新内容进行解释。有些例题可以在书中找到,有些例题则只在配套网站上提供。
●新增练习,有知识性的也有富有挑战性的,用于满足教师提出的需求或配合新内容。同时,还有些练习是为了完善或拓宽已有的练习。
●引入了更多的小标题以便将章节划分成更小的部分。
●极大地扩展了在线资源,以为教师和学生提供广泛的支持。后面会给出关于这些资源的详细描述。
主题方面的更新
●逻辑。引入了若干逻辑谜题。一道新例题解释了如何将n皇后问题建模为可满足性问题,这是一个简明易懂的例子。
●集合论。在正文中引入了多重集的概念(之前是在练习中引入的)。
●算法。新版讨论了字符串匹配算法,这是一个应用很广的重要算法,可用于拼写检查、关键字搜索、字符串匹配以及计算生物学。此外,还给出了求解字符串匹配练习的蛮力算法。
●数论。新版包含有关素数及其猜想的最新数值发现和理论发现。在正文中论述了扩展欧几里得算法和一遍(one-pass)算法(之前是在练习中介绍的)。
●密码学。由于在云计算中的重要性,新版涵盖了同态加密的概念。
●数学归纳法。扩展了数学归纳法证明的模板,并将其放在数学归纳法证明的例题之前。
●计数方法。扩充了用于计数的除法法则的讨论。
●数据挖掘。在n元关系一节讨论了数据挖掘中的一个关键概念——关联规则。另外,在练习中还引入了雅卡尔指数,可用于计算两个集合之间的距离。
●图论应用。添加了一道新例题,解释语义网络是如何工作的。这是人工智能中的一个重要结构,可以用图来建模。
●人物传记。新的人物传记包括怀尔斯、婆什迦罗、瓦列·普金、阿达马、张益唐和金特里。原有的传记也做了一些扩展和更新。这次更新是多方面的,包括具有历史意义的东方数学家、19世纪和20世纪的主要研究人员,以及目前活跃的21世纪的数学家和计算机科学家。
本书特色
易理解性。实践证明,本书对于初学者来说是易读易懂的。书中绝大部分内容不需要比大学代数更多的数学预备知识,需要额外帮助的学生可以在配套网站找到相应工具,以将数学素养提升到本书要求的水准。书中少数几处需要用到微积分知识的地方都已注明。大多数学生应该很容易理解用于表示算法的伪代码,无论是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易于理解和易于领会的水平开始。一旦详细介绍了基本数学概念,就会给出稍难一些的内容以及在其他研究领域中的应用。
灵活性。为了便于灵活使用,本书做了精心的设计。各章对之前章节的依赖程度都被降到最低。每章分成长度大致相等的若干节,每节又根据内容划分成若干小节以方便教学。教师可以利用章节划分灵活地安排讲课进度。
写作风格。本书的写作风格是直接而又实用的。书中使用准确的数学语言,但没有采用过多的形式化与抽象,在数学命题中的记号和词语表达间做了精心的平衡。
数学严谨性和准确性。书中所有定义和定理的陈述都十分谨慎,这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则是先由动机引入,然后再慢慢展开,并且所有步骤都经过了详细论证。证明中用到的公理及其所导出的基本性质在附录中均有描述,这呈现给学生一个清晰的概念,即在证明中他们能够做出何种假设。本书解释并大量使用了递归定义。
例题。全书共有超过800道例题,用来阐述概念、建立不同主题之间的关联以及介绍应用。在大部分例题中,首先提出问题,然后再以适量的细节给出解法。
应用。本书中的应用展示了离散数学在解决现实世界中的问题时的实用性。这些应用涉及广泛的领域,包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和互联网。
算法。离散数学的结论常常要用算法来表述,故书中多数章节都介绍了一些关键算法。这些算法采用文字叙述,同时也采用一种易于理解的结构化伪代码来描述。关于伪代码的描述和说明在附录C中给出。对于本书中的所有算法,都简要分析了其计算复杂度。
历史资料。书中对许多主题的背景做了简要介绍,并给出了89位数学家和计算机科学家的简短传记。这些科学家为离散数学做出过重要贡献,传记中介绍了他们的生活、事业和成就,同时配有照片(如果有的话)。
此外,我们还提供了一些历史资料,作为对正文中历史资料的补充。我们做了大量努力以使得本书能够反映新的发现。
关键术语和结论。每章最后列出关键术语和结论。关键术语只列出学生必须学会的那些,而非该章中定义的每个术语。
练习。书中包含4200多道练习题,涵盖大量不同类型的问题。不仅提供了足够多的简单练习用于培养基本技能,还提供了大量中等难度的练习和许多具有挑战性的练习。练习的叙述清晰而无歧义,并按难易程度进行了分级。练习中还包含一些特殊的讨论来展开正文中没有涉及的新概念,使得学生能够通过自己的努力来发现新的想法。
那些比平均难度稍难的练习用一个星号(*)标记,而那些更具挑战性的练习则用两个星号(**)来标记。需要用微积分知识求解的练习会明确指出。有些练习的结果要在正文中用到,我们用符号来标识这类题目。本书最后给出了所有奇数编号练习的答案或解题纲要。答案中大部分证明的步骤都十分清晰。
复习题。每章后面都有一组复习题。设计这些问题是为了帮助学生重点学习该章最重要的概念和技术。要回答这些复习题,学生必须写出较长的答案,而不是仅做一些计算或给出简答。
补充练习。每章后面都有一组丰富多样的补充练习。这些练习通常比每节后面的练习难度更大。补充练习旨在强化该章中的概念,并把不同主题更有效地综合起来。
计算机课题。每章后面还有一组计算机课题。全书共有大约150道计算机课题,用于将学生在计算和离散数学中所学到的内容联系起来。对于那些从数学角度或程序设计角度来看难度超过平均水平的计算机课题,我们用一个星号(*)标记,而那些非常具有挑战性的题目则用两个星号(**)标记。
计算和探索。每章后面都有一组计算和探索性的问题,共有大约120道。完成这些练习需要借助现有的软件工具,诸如学生或教师自己编写的程序,或像Maple或Mathematica这样的数学计算软件包。这些练习大多为学生提供了通过计算来发现一些新事实或想法的机会。(其中一些练习在配套的在线练习册《探索离散数学》(Exploring Discrete Mathematics)中也有讨论。)
写作课题。每章后面都有一组写作课题,要完成这类题目,学生需要参考数学方面的文献。有些题目本质上是关于历史知识的,需要学生查找原始资料;其他题目则将带领学生通往新内容和新思想。这些练习旨在向学生展示正文中没有深入探讨的想法,通过把数学概念和写作过程结合起来,帮助学生面对未来可能的研究领域。(在网络版或印刷版的《学生解题指南》(Student’s Solutions Guide)中可以找到为这些题目准备的参考文献。)
附录。本书有三个附录。附录A介绍实数和正整数的公理,并解释如何利用这些公理直接证明事实。附录B介绍指数函数和对数函数,复习课程中常用的一些基本内容。附录C则介绍正文中用来描述算法的伪代码。
推荐读物。在附录后还提供了一份针对全书及各章的推荐读物。这些推荐读物包括难度不超过本书的书籍、更难些的书籍、阐述性的文章以及发表离散数学新发现的原始文章。其中一些是多年前出版的经典读物,而另一些是在最近几年才出版的。本书的网站中包含许多有价值资源的链接,可以作为对这些推荐读物的补充。
怎样使用本书
本书经过了精心写作和编排,以支持不同层次以及侧重点不同的离散数学课程。下表列出了核心章节和可选章节。为大学二年级学生开设一学期的离散数学入门课程可以以本书核心章节为基础,其他章节可由教师取舍。两学期的入门课程可以在核心章节上外加所有可选的数学章节。强调计算机科学的课程则可以涵盖部分或全部计算机科学章节。教师可以在本书网站上的《教师资源手册》(Instructor’s Resource Guide)中找到离散数学课程教学大纲样本,以及针对本书章节的教学建议。
章节 核心章节 计算机科学可选章节 数学可选章节
1 1.1~1.8(视需要)
2 2.1~2.4,2.6(视需要) 2.5
3 3.1~3.3(视需要)
4 4.1~4.4(视需要) 4.5,4.6
(续)
章节 核心章节 计算机科学可选章节 数学可选章节
5 5.1~5.3 5.4,5.5
6 6.1~6.3 6.6 6.4,6.5
7 7.1 7.4 7.2,7.3
8 8.1,8.5 8.3 8.2,8.4,8.6
9 9.1,9.3,9.5 9.2 9.4,9.6
10 10.1~10.5 10.6~10.8
11 11.1 11.2,11.3 11.4,11.5
12 12.1~12.4
13 13.1~13.5
使用本书的教师可以选用或略去每节最后有挑战性的例题及练习来调整课程的难度。右侧的各章依赖图展示的是强依赖性。星号表示该章只有部分相关小节是学习后续章节所必需的。弱依赖关系不再列出。更多详细信息可以在《教师资源手册》中找到。
教辅资源
关于本书教辅资源,只有使用本书作为教材的教师才可以申请,需要的教师可向麦格劳·希尔教育出版公司北京代表处申请,电话010-57997618/7600,传真010-59575582,电子邮件instructorchina@mheducation.com。——编辑注
《学生解题指南》。这本可以单独购买的学生手册包含所有奇数编号练习的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这种方法管用。对于有些问题,还给出了一两种其他可能的解法,以说明一个问题可以用多种不同方法来求解。指南的内容还包括:为每章后面的写作课题推荐的参考文献;关于如何撰写证明的指南;在离散数学学习中学生常犯的各类错误;为每章提供的考试样例及解答,以帮助学生准备考试。
《教师资料手册》。本手册在网站上提供,教师也可以申请印刷版,手册中包含书中所有偶数编号练习的完整解答。手册的内容还包括:关于如何讲授本书每章内容的建议,包括每节中应强调的重点以及如何组织内容;为每章提供的考试样例,以及一个包含1500多道考试题目的可选试题库,对于所有考试样例及试题库中的题目都给出了解答;针对不同的侧重点以及不同学生能力水平的课程教学大纲样本。
致谢
感谢所有将本书用作教材的教师和学生,他们来自不同的学校,并向我提供了很多有价值的反馈和有益的建议。正是有了他们的反馈,才使本书变得更为出色。特别感谢Jerrold Grossman和Dan Jordan,作为第8版的技术评审,他们以“鹰眼”般敏锐的目光确保了本书的准确性。在本书出版过程中的各个阶段,他们两位多次审阅了本书的每个角落,帮助消除了之前勘误表中的错误,并防止出现新的错误。
感谢Dan Jordan为《学生解题指南》和《教师资源手册》做出的贡献。他在更新这些教辅资源方面完成了令人钦佩的工作。感谢Jerrold Grossman,他是本书前7版教辅资源的作者,并为Dan提供了非常有价值的帮助。还要感谢许许多多曾经为本书创建并维护在线资源的人。特别感谢Dan Jordan和Rochus Boerner,他们所做的大量工作解决了配套网站的诸多问题(后面会介绍这个网站)。
感谢第8版以及所有之前版本的审稿人。他们给予我许多有益的批评和鼓励,希望这一版不会辜负他们的期望。自从本书第1版出版以来,已经有超过200位审稿人,其中有许多来自美国以外的国家。近期审稿人列表如下。
近期审稿人
感谢阅读过本书的学生,他们提供了很多建议并报告了一些勘误。在蒙茅斯大学时,曾经上过我的离散数学课程的学生,包括本科生和研究生,从方方面面帮助我改进了书中内容。
还要感谢麦格劳-希尔高等教育(本书的出版商)的工作人员,以及Aptara的生产人员。我还想感谢兰登书屋原来的编辑Wayne Yuhasz,以及本书之前的许多编辑,他们的见解和技巧是本书成功的有力保障。
我想对产品经理Nora Devlin表示深深的谢意,她所完成的工作已远远超出了既定的职责。她不仅能力出众,而且责任心强,努力解决了新版本开发过程中出现的各种问题。
还要感谢Peggy Selle,作为内容产品经理,她管理着本书的生产过程。她全程跟踪本书的流程,并帮助解决生产过程中出现的许多问题。感谢Aptara的高级产品经理Sarita Yadav和她的同事,他们的努力工作确保了本书的生产质量。
我还要对麦格劳-希尔高等教育的科学、工程和数学(SEM)部门的同仁表示感谢,他们对新版本以及相关的媒体内容给予了大力支持,包括:
●Mike Ryan,高等教育副总裁,负责作品统筹和学习内容管理
●Kathleen McMahon,数学与物理科学部门常务主管
●Caroline Celano,数学部门主管
●Alison Frederick,市场经理
●Robin Reed,首席产品开发师
●Sandy Ludovissey,采购人
●Egzon Shaqiri,设计师
●Tammy Juran,评估内容项目经理
●Cynthia Northrup,数字内容部门主管
●Ruth Czarnecki-Lichstein,业务产品经理
●Megan Platt,编辑协调人
●Lora Neyens和Jolynn Kilburg,项目经理
●Lorraine Buczek,内容授权专家
Kenneth H. Rosen
---------------------------计算机组成与设计:硬件/软件接口(原书第5版)---------------------------
我们能体验的最美好的事物是神秘,它是所有真正的艺术和科学的源泉。
——阿尔伯特·爱因斯坦,《我的信仰》,1930
关于本书
在学习计算机科学与工程时,除了掌握计算的基本原理外,还应该了解该领域的最新进展。各种计算领域中的读者应有机会学习计算机系统的组成理论,因为这是决定计算机系统的功能、性能甚至成功与否的关键。
现代计算机技术需要各种计算方面的专家,他们应对硬件和软件都有深入的理解。硬件和软件在多个层次上的相互关系成为理解计算基本原理的框架。无论你的主要兴趣是硬件还是软件,是计算机科学还是电气工程,计算机组成与设计的基本思想都是相同的。因此,本书着重展示硬件与软件的关系,并重点介绍当今计算机中的基础概念。
近年来,处理器已经由单核发展为多核,这也印证了本书自第1版就预测的发展趋势。有些程序员忽略了这一发展趋势,他们希望计算机体系结构专家、编译器设计者和芯片工程师能够帮助他们,让程序不做任何修改就可以更快或更高效地在新型处理器上运行。但是,这样的时代已经一去不返了。为了使程序运行得更快,必须将其并行化。然而,许多研究者的目标是希望程序员在编写程序时不需要考虑硬件的并行特征,这一目标要很多年才能实现。至少在下一个十年里,大多数程序员必须理解硬件/软件接口,才能编写出能在并行计算机上高效运行的程序。
本书适合以下读者:在汇编语言或逻辑设计方面只有少许经验,需要理解基本计算机组成的读者;具有汇编语言或逻辑设计的基础,需要学习如何设计计算机,或者要进一步理解计算机系统如何工作的读者。
与本书相关的另一本书
有些读者可能已经熟悉作者的另一本书《Computer Architecture:A Quantitative Approach》。该书已广为流传,经常以作者姓名命名,称为“Hennessy and Patterson”(本书则常称为“Patterson and Hennessy”)。我们写该书的目的是要用坚实的工程基础和量化的性价比权衡来描述计算机体系结构的原理。我们以商用系统为例,用测量的方法来描述实际的设计经验。我们的目标是用量化的方法而不是用描述的方法学习计算机体系结构,希望这一方法有助于培养能精确理解计算机的专业人才。
机械工业出版社已出版了本书的第3版、第4版和第5版影印书,书名为《计算机体系结构:量化研究方法》。——编辑注
本书的大多数读者并不一定要成为计算机体系结构的设计者。但是,未来软件设计人员对与软件系统协同工作的基本硬件技术的理解程度,将直接影响软件系统的性能和能效。因此,编译器设计者、操作系统设计者、数据库程序员以及其他大多数软件工程师对本书的原理必须有充分的了解。同样,硬件设计者也必须清楚地理解他们的工作对软件的相应影响。
所以,本书的内容远多于“Hennessy and Patterson”,而且进行了大量修订,以适应不同专业的读者。我们对再版“Hennessy and Patterson”时删除的大量介绍性材料的效果感到满意,这使得新版与第1版内容的重叠大大降低,本书亦如此。
第5版的变化
第5版有6个主要的目标:使用运行例子的方法论证理解硬件的重要性;对前面已经提到的重要技术采用黑体的方式进行强调;对例子进行了更新,以反映从PC时代到后PC时代的发展;将I/O吞吐率方面的材料贯穿在整本书中,而不是集中在一章中;对技术内容进行了更新,以反映自2009年第4版出版以来工业界的变化;将附录和可选章节(目录中带有图标的章节)的内容放在互联网上(booksite.elsevier.com/9780124077263/index.php),而不是放在CD上,降低了本书的成本,也使该版本变成了一部电子书。
在详细介绍第5版的修订目标之前,首先看下表。该表给出了本书的主要内容,并为关注硬件和关注软件的两种读者分别进行了导读。其中,第1、4、5和6章对两种读者同等重要。第1章讨论了能耗的重要性和由其引发的处理器从单核向多核的转变,并介绍了计算机设计中的8个伟大思想。第2章对于硬件读者来说很可能是复习性材料,而对于软件读者来说则是重要的阅读材料,特别是希望深入学习编译器和面向对象编程语言的读者。第3章适合对定点运算或者浮点运算感兴趣的读者,有些读者可能不需要学习第3章。然而,我们将在本章介绍矩阵乘法运行的例子,展示如何采用子字并行方法将性能提高4倍,因此不要跳过3.6~3.8节。第4章介绍了流水线处理器。其中,4.1、4.5和4.10节给出了流水线概述,4.12节给出了进一步提高矩阵乘法运算性能的方法,这些小节对于软件设计者来说比较重要。对于硬件设计者,第4章是核心内容。另外,根据读者知识背景的不同,可以选择是否首先阅读附录C中的逻辑设计部分。最后一章是多核、多处理器和集群系统,这一章是全新的内容,因此所有读者都应该阅读。本版的重要组织结构是使许多思想的引入更加自然,例如GPU、仓储式计算机和集群系统中的关键——网络接口卡的软硬件接口。
章/附录 节 关注软件 关注硬件
第1章计算机概要与技术1.1~1.111.12(历史)
第2章指令:计算机的语言2.1~2.142.15(编译器和Java)2.16~2.202.21(历史)
附录ERISC指令集体系结构E.1~E.17
第3章计算机的算术运算3.1~3.53.6~3.8(子字并行)3.9~3.10(谬误)3.11(历史)
附录B逻辑设计基础B.1~B.13
第4章处理器4.1(引言)4.2(逻辑设计惯例)4.3~4.4(简单实现)4.5(流水线概述)4.6(流水线数据通路)4.7~4.9(冒险和异常)4.10~4.12(并行和实例)4.13(Verilog流水线控制)4.14~4.15(谬误)4.16(历史)
(续)章/附录节关注软件关注硬件
附录D控制通路的硬件实现D.1~D.6
第5章大容量和高速度:开发存储器层次结构5.1~5.105.11(廉价冗余磁盘阵列) 5.12(Verilog cache控制器)5.13~5.165.17(历史)
第6章从客户端到云的并行处理器6.1~6.86.9(网络)6.10~6.146.15(历史)
附录A汇编器、链接器和SPIM仿真器A.1~A.11
附录C图形处理单元C.1~C.13仔细阅读有时间阅读作为参考回顾或阅读拓展阅读
第5版的第一个目标是使用一个例子来论证理解硬件对提高性能和能效的重要性。正如前面所述,在第3章,我们采用子字并行将矩阵乘法加速4倍,在第4章通过循环展开将性能翻倍,证明了指令集并行的价值。第5章通过分块技术对cache进行优化,再次将性能翻倍。第6章通过在16个处理器上的线程级并行获得了14倍的加速比。这4种优化技术仅仅在原始的矩阵乘法例子中的C代码上增加了24行。
第二个目标是通过提早介绍计算机体系结构设计中的8个伟大思想并在整本书中明确指出它们的应用之处来帮助读者理解计算机设计的精髓。我们采用黑体文字的方式向读者提醒这8个思想的应用情况,在书中大约有100次引用。每一章中至少有7处应用这些思想的例子,并且每个思想至少被引用5次。通过并行提高性能、流水线和预测技术是引用次数最多的3个思想,紧接着是摩尔定律。第4章讲述处理器,是例子最多的一章,也是最吸引计算机设计者的一章。每一章都能找到的伟大思想是通过并行提高性能,这是近年来计算机领域中的一个重要发展方向。
第三个目标是通过例子和材料来识别计算技术从PC时代进入后PC时代的变化。因此,第1章直接介绍了平板电脑而没有介绍PC,第6章介绍了云计算的基础设施。另外,在指令集方面,我们介绍了后PC时代中个人移动设备里使用的ARM指令集,以及在PC时代和云计算中占主导地位的x86指令集。
第四个目标是将I/O吞吐率方面的材料贯穿在整本书中,而不是集中在一章中,这与第4版中将并行性贯穿全书一样,因此,本版可在1.4、4.9、5.2、5.5、5.11和6.9节中找到I/O相关的材料。我们的想法是如果不把这些内容集中在一章,则读者(和教师)能更好地学习与掌握I/O。
计算机是一个快速发展的领域,对于本书新的版本也是如此,编写新版的一个重要目的是更新技术内容。实际的例子就是反映后PC时代特点的ARM Cortex A8和Intel Core i7,其他的亮点包括新的ARMv8 64位指令集、讲解GPU特有术语的教程、组成云的仓储式计算机的内涵以及对10G以太网卡的深入理解。
为了保持纸质书的厚度及其与电子书的兼容性,我们一改以前版本的做法,将可选内容由随书CD改为网络在线的形式。
最后,我们更新了本书的所有练习题。
在对内容进行修订的同时,我们保留了以往版本中有用的元素。为使本书更好地作为参考书,我们还在新术语第一次出现时给出了定义。书中标题为“理解程序性能”部分的内容有助于读者理解程序的性能,以及如何提高性能,就像书中“硬件/软件接口”部分会帮助读者理解有关接口的权衡问题一样。“重点”部分仍然存在,以使读者看到整个“森林”而不是每一棵“树”。每章最后提供“小测验”部分的答案,帮助读者在第一时间加强对内容的理解。本版同样提供了MIPS参考数据(这是从IBM System/360“绿卡”得到的灵感),并对数据进行了更新,在编写MIPS汇编语言程序时,这应该是一个很好的参考。
教学支持爱思唯尔(ELS):关于本书教辅资源,使用教材的老师需通过爱思唯尔的教材网站(www.textbooks.elsevier.com)注册并通过审批后才能获取相关资源。具体方法如下:在www.textbooks.elsevier.com教材网站查找到该书后,点击“instructor manual”便可申请查看该教师手册。有任何问题,请致电010-85208853。——编辑注
我们收集了大量材料供教师授课使用,包括题解、图表、幻灯片等,可从出版商处获得。如需更多信息,请访问网址:textbooks.elsevier.com/9780124077263。
结语
从下面的致谢中,你可以发现我们花费了大量精力去修改本书的错误。由于本书印刷了多次,因此我们有机会做更多的校正。如果你发现有遗留的错误,请通过电子邮件与出版社联系:cod5bugs@mkp.com。
本版标志着Hennessy和Patterson自1989年以来长期合作的第二次中止。由于要管理一所世界知名的大学,Hennessy校长将不能继续承担新版本的实际编写工作。留下Patterson一人感觉自己像个总是和伙伴们一起演出的演员,突然被推到前台独自表演。所以,在致谢名单中列出的人和Berkeley的同行们在本书的撰写过程中甚至起了更大的作用。
第5版致谢
在本书的每一版中,我们都非常幸运地得到了来自许多读者、评审者和其他人员的帮助。每个人的帮助都使本书更加完美。
由于第6章做了巨大的修改,因此我们对其思想和内容进行了单独的评审,并基于每位评审人的反馈意见做了修改。感谢Stanford大学的Christos Kozyrakis,他建议在集群中使用网络接口来论证I/O的软硬件接口,并对该章的组织提出了意见。还要感谢Stanford大学的Mario Flagsilk,他提供了NetFPGA NIC的细节、表格以及性能评估。另外,以下人员对本章提出了修改建议:Northeastern大学的David Kaeli、HP实验室的Partha Ranganathan、Wisconsin大学的David Wood以及Berkeley大学的同事Siamak Faridani、Shoaib Kamil、Yunsup Lee、Zhangxi Tan和Andrew Waterman。
我们要对UC Berkeley的Rimas Avizenis表示特别的感谢,他开发了不同版本的矩阵乘法程序,并提供了相应的性能数据。当我在UCLA读研究生时,我与他的父亲一起工作,能够与他一起在UCB共事是一件美好的事情。
我也要对我的长期合作伙伴——UC Berkeley的Randy Katz表示感谢。我们共同讲授研究生的计算机体系结构课程,他在开发计算机体系结构的伟大思想方面提供了很大的帮助。
感谢David Kirk、John Nickolls和他们在 NVIDIA的同事们(Michael Garland、John Montrym、Doug Voorhies、Lars Nyland、Erik Lindholm、Paulius Micikevicius、Massimiliano Fatica、Stuart Oberman、Vasily Volkov)提供了第一个深入介绍GPU的附录。再次感谢Jim Larus,他现在是EPFL计算机与通信科学学院的院长,为本书发挥了在汇编语言方面的专长,欢迎本书读者使用他所开发和维护的模拟器。
非常感谢South Carolina大学的Jason Bakos,他在第4版的基础上对本版的练习题进行了更新。第4版的练习题由以下人员编写:Perry Alexander(Kansas 大学)、Javier Bruguera(de Santiago de Compostela大学)、Matthew Farrens(California大学Davis分校)、David Kaeli(Northeastern大学)、Nicole Kaiyan(Adelaide大学)、John Oliver(Cal Poly,San Luis Obispo)、Milos Prvulovic(Georgia理工大学)和HP的Jichuan Chang、Jacob Leverich、Kevin Lim、Partha Ranganathan。
感谢Jason Bakos开发了新的幻灯片。
感谢许多教师的贡献,他们回答出版商的调查问卷、评审我们的提议、出席小组会议,并对本版的计划进行分析和反馈。他们是:
2012焦点小组:Bruce Barton(Suffolk County Community学院),Jeff Braun(Montana理工大学),Ed Gehringer(North Carolina State),Michael Goldweber(Xavier大学),Ed Harcourt(St.Lawrence大学),Mark Hill(Wisconsin大学Madison分校),Patrick Homer(Arizona大学),Norm Jouppi(HP实验室),Dave Kaeli(Northeastern大学),Christos Kozyrakis(Stanford大学),Zachary Kurmas(Grand Valley州立大学),Jae C.Oh(Syracuse大学),Lu Peng(Louisiana州立大学),Milos Prvulovic(Georgia理工),Partha Ranganathan(HP实验室),David Wood(Wisconsin大学),Craig Zilles(Illinois大学香槟分校)。
参考调查和审阅的学者:Mahmoud Abou-Nasr(Wayne州立大学),Perry Alexander(Kansas大学),Hakan Aydin(George Mason大学),Hussein Badr(New York州立大学Stony Brook分校),Mac Baker(Virginia Military学院),Ron Barnes(George Mason大学),Douglas Blough(Georgia理工),Kevin Bolding(Seattle Pacific大学),Miodrag Bolic(Ottawa大学),John Bonomo(Westminster学院),Jeff Braun(Montana理工大学),Tom Briggs(Shippensburg大学),Scott Burgess(Humboldt州立大学),Fazli Can(Bilkent大学),Warren R.Carithers(Rochester理工学院),Bruce Carlton(Mesa Community学院),Nicholas Carter(Illinois大学香槟分校),Anthony Cocchi(New York城市大学),Don Cooley(Utah州立大学),Robert D.Cupper(Allegheny学院),Edward W.Davis(North Carolina州立大学),Nathaniel J.Davis(Air Force理工学院),Molisa Derk(Oklahoma 城市大学),Derek Eager(Saskatchewan大学),Ernest Ferguson(Northwest Missouri州立大学),Rhonda Kay Gaede(Alabama大学),Etienne M.Gagnon(UQAM),Costa Gerousis(Christopher Newport大学),Paul Gillard(Newfoundland纪念大学),Michael Goldweber(Xavier大学),Georgia Grant(San Mateo学院),Merrill Hall(The Master’s 学院),Tyson Hall(Southern Adventist大学),Ed Harcourt(St.Lawrence大学),Justin E.Harlow(South Florida大学),Paul F.Hemler(Hampden-Sydney学院),Martin Herbordt(Boston大学),Steve J.Hodges(Cabrillo学院),Kenneth Hopkinson(Cornell大学),Dalton Hunkins(St.Bonaventure大学),Baback Izadi(New York州立大学New Paltz分校),Reza Jafari,Robert W.Johnson(Colorado Technical大学),Bharat Joshi(North Carolina大学Charlotte分校),Nagarajan Kandasamy(Drexel大学),Rajiv Kapadia,Ryan Kastner(California大学Santa Barbara分校),E.J.Kim(Texas A&M大学),Jihong Kim(Seoul国立大学),Jim Kirk(Union大学),Geoffrey S.Knauth(Lycoming学院),Manish M.Kochhal(Wayne州立大学),Suzan Koknar-Tezel(Saint Joseph大学),Angkul Kongmunvattana(Columbus州立大学),April Kontostathis(Ursinus学院),Christos Kozyrakis(Stanford大学),Danny Krizanc(Wesleyan 大学),Ashok Kumar,S.Kumar(Texas 大学),Zachary Kurmas(Grand Valley州立大学),Robert N.Lea(Houston大学),Baoxin Li(Arizona州立大学),Li Liao(Delaware大学),Gary Livingston(Massachusetts大学),Michael Lyle,Douglas W.Lynn(Oregon理工学院),Yashwant K Malaiya(Colorado州立大学),Bill Mark(Texas大学Austin分校),Ananda Mondal(Claflin大学),Alvin Moser(Seattle大学),Walid Najjar(California大学Riverside分校),Danial J.Neebel(Loras学院),John Nestor(Lafayette学院),Jae C.Oh(Syracuse大学),Joe Oldham(Centre学院),Timour Paltashev,James Parkerson(Arkansas大学),Shaunak Pawagi(SUNY Stony Brook分校),Steve Pearce,Ted Pedersen(Minnesota大学),Lu Peng(Louisiana州立大学),Gregory D Peterson(Tennessee大学),Milos Prvulovic(Georgia理工),Partha Ranganathan(HP实验室),Dejan Raskovic(Alaska大学Fairbanks分校),Brad Richards(Puget Sound大学),Roman Rozanov,Louis Rubinfield(Villanova大学),Md Abdus Salam(Southern大学),Augustine Samba(Kent州立大学),Robert Schaefer(Daniel Webster学院),Carolyn J.C.Schauble(Colorado州立大学),Keith Schubert(CSU San Bernardino分校),William L.Schultz,Kelly Shaw(Richmond大学),Shahram Shirani(McMaster大学),Scott Sigman(Drury大学),Bruce Smith,David Smith,Jeff W.Smith(Georgia大学,Athens),Mark Smotherman(Clemson大学),Philip Snyder(Johns Hopkins大学),Alex Sprintson(Texas A&M),Timothy D.Stanley(Brigham Young大学),Dean Stevens(Morningside学院),Nozar Tabrizi(Kettering大学),Yuval Tamir(UCLA),Alexander Taubin(Boston大学),Will Thacker(Winthrop大学),Mithuna Thottethodi(Purdue大学),Manghui Tu(Southern Utah大学),Dean Tullsen(UC San Diego分校),Rama Viswanathan(Beloit学院),Ken Vollmar(Missouri州立大学),Guoping Wang(Indiana-Purdue大学),Patricia Wenner(Bucknell大学),Kent Wilken(California大学Davis分校),David Wolfe(Gustavus Adolphus学院),David Wood(Wisconsin大学Madison分校),Ki Hwan Yum(Texas大学San Antonio分校),Mohamed Zahran(New York城市学院),Gerald D.Zarnett(Ryerson大学),Nian Zhang(South Dakota School of Mines & Technology),Jiling Zhong(Troy大学),Huiyang Zhou(Central Florida大学),Weiyu Zhu(Illinois Wesleyan大学)。
特别感谢Mark Smotherman一遍又一遍地查找本书中的技术错误和写作错误,他的工作显著地改进了这一版的质量。
还要感谢Morgan Kaufmann公司同意在Todd Green和Nate McFadden的领导下对本书进行再版,没有他们的工作,我不可能完成本书。我们还要感谢Lisa Jones和Russell Purdy,她们分别负责管理出版过程和封面设计。新封面将本版中后PC时代的内容和第1版的封面呼应了起来。
以上提到的近150名人士为本版提供了大量帮助,使之成为我们希望的最好的书。
David A.Patterson