现代体系结构的优化编译器
点击看大图基本信息
- 原书名： Optimizing Compilers for Modern Architectures,A Dependence-Based Approach
- 原出版社： Elsevier Science
- 作者： （美）Randy Allen,Ken Kennedy
- 译者： 张兆庆 乔如良 冯晓兵 吴承勇 连瑞琦 刘旸
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：7111141229
- 上架时间：2004-6-17
- 出版日期：2004 年7月
- 开本：16开
- 页码：573
- 版次：1-1
- 所属分类：
计算机 > 计算机组织与体系结构 > 综合
教材 > 研究生/本科/专科教材 > 工学 > 计算机
计算机 > 软件与程序设计 > 汇编语言/编译原理 > 编译原理
教材 > 计算机教材 > 本科/研究生 > 计算机专业教材 > 计算机专业课程 > 程序设计
内容简介回到顶部↑
书籍
计算机书籍
本书介绍对现代体系结构的编译器进行优化的方法，理论基础是基于循环依赖的。分析基于依赖的变换的正确性论述和依赖测试的详细过程。剖析怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书还讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构(例如，向量、多处理器、超标量)的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人熟知的应用，如硬件设计、数组语言实现以及消息传递系统的编译。
设计具有高性能微处理器的现代计算机体系结构，能够极大地提高计算机在性能方面的潜在优势。然而其高度的复杂性使得产生有效代码和实现其全部优势变得愈加困难。这本出自两位学术权威的具有里程碑意义的教科书，重点阐述了编译器对于解决这个至关重要问题所起到的关键作用。
数据依赖是在高性能微处理器和并行体系结构上优化程序的基本编译器分析工具。它能使所编写的编译器自动地将简单的串行程序转换成具有现代体系结构特征的程序。数据依赖支持许多变换策略，也应用于一些重要的优化问题，本书对此做了全面介绍，并对基于数据依赖的编译器优化的重要性和广泛应用性进行了论证，给出了理解和实现它们所需要的基础，同时还为手工转换程序提供了详细说明。
书中介绍的方法是基于过去二十多年的研究成果．取材于在美国rice大学的研究原型和几个有关的商业系统中实现的策略。致力于现代计算机体系结构设计和优化编译器的研究人员、业界专家和研究生都可以从本书中获益。
本书特点
●提供一种简单实用的算法和方法的指南，在高性能微处理器和并行系统中是最有效的
●用处理过的例子示范每个变换
●用实例分析编译器如何实现每一章中描述的理论和实践
●介绍存储层次结构问题的最完善的处理方法
●全书用依赖图来阐明排序关系
●涉及各种语言。包括fortran77、c、硬件定义语言、fortran 90和high performance fortran
计算机书籍
本书介绍对现代体系结构的编译器进行优化的方法，理论基础是基于循环依赖的。分析基于依赖的变换的正确性论述和依赖测试的详细过程。剖析怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书还讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构(例如，向量、多处理器、超标量)的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人熟知的应用，如硬件设计、数组语言实现以及消息传递系统的编译。
设计具有高性能微处理器的现代计算机体系结构，能够极大地提高计算机在性能方面的潜在优势。然而其高度的复杂性使得产生有效代码和实现其全部优势变得愈加困难。这本出自两位学术权威的具有里程碑意义的教科书，重点阐述了编译器对于解决这个至关重要问题所起到的关键作用。
数据依赖是在高性能微处理器和并行体系结构上优化程序的基本编译器分析工具。它能使所编写的编译器自动地将简单的串行程序转换成具有现代体系结构特征的程序。数据依赖支持许多变换策略，也应用于一些重要的优化问题，本书对此做了全面介绍，并对基于数据依赖的编译器优化的重要性和广泛应用性进行了论证，给出了理解和实现它们所需要的基础，同时还为手工转换程序提供了详细说明。
书中介绍的方法是基于过去二十多年的研究成果．取材于在美国rice大学的研究原型和几个有关的商业系统中实现的策略。致力于现代计算机体系结构设计和优化编译器的研究人员、业界专家和研究生都可以从本书中获益。
本书特点
●提供一种简单实用的算法和方法的指南，在高性能微处理器和并行系统中是最有效的
●用处理过的例子示范每个变换
●用实例分析编译器如何实现每一章中描述的理论和实践
●介绍存储层次结构问题的最完善的处理方法
●全书用依赖图来阐明排序关系
●涉及各种语言。包括fortran77、c、硬件定义语言、fortran 90和high performance fortran
目录回到顶部↑
第1章 高性能体系结构对编译器的挑战
1．1 概述和目标
1．2 流水线
1．2．1 流水线指令部件
1．2．2 流水线执行部件
1．2．3 并行功能部件
1．2．4 标量流水线编译
1．3 向量指令
1．3．1 向量硬件概述
1．3．2 向量流水线编译
1．4 超标量处理器和vliw处理器
1．4．1 多发射指令部件
1．4．2 多发射处理器的编译
1．5 处理器并行性
1．5．1 处理器并行性概述
1．5．2 异步并行性的编译
1．6 存储层次结构
1．6．1 存储系统概述
1．6．2 存储层次结构的编译
1．7 实例研究：矩阵乘法
1．1 概述和目标
1．2 流水线
1．2．1 流水线指令部件
1．2．2 流水线执行部件
1．2．3 并行功能部件
1．2．4 标量流水线编译
1．3 向量指令
1．3．1 向量硬件概述
1．3．2 向量流水线编译
1．4 超标量处理器和vliw处理器
1．4．1 多发射指令部件
1．4．2 多发射处理器的编译
1．5 处理器并行性
1．5．1 处理器并行性概述
1．5．2 异步并行性的编译
1．6 存储层次结构
1．6．1 存储系统概述
1．6．2 存储层次结构的编译
1．7 实例研究：矩阵乘法
译者序回到顶部↑
译者序
Intel公司David Kuck院士在评论Ken Kennedy和Randy Allen的新书“Optimizing Compilers for Modern Architectures：ADependence-Based Approach”时，这样写道：“编译程序是计算机科学与技术的皇后。编译器一直是应用与系统之间的桥梁。现在它们不仅决定应在新的硬件中实现哪些体系结构特色，而且说明对软件开发者而言，哪些新的语言特色将是有效的。”
Kuck院士和Kennedy教授都是并行优化编译理论与实践方面的最著名学者。Kuck将编译程序称为“计算机科学与技术的皇后”是十分恰当的。
自1958年ALGOL58问世后，20世纪60年代在程序设计语言理论、数据结构、算法设计与分析、可计算性理论等方面的研究，取得了令人惊叹的硕果，编译理论、技术和实验起了很大的推动作用。至今编译领域中仍有很多具有挑战性的问题，吸引广大计算科学与技术研究人员投身于此项事业。
现代计算机体系结构大都具有各种粒度的并行机制和分层存储结构，访存仍是当今各类计算机体系结构的瓶颈。优化编译器的主要任务可以说是：扬计算机结构之长一挖掘程序中的并行性，避其之短一挖掘程序的局部性(重用性)，实施有效的寄存器分配和Cache管理。
这正是Kennedy和Allen在书中讲述的主要内容。第5章(提高细粒度并行性)，第6章(开发粗粒度并行性)，第8章(改进寄存器的使用)，第9章(管理Cache)和第10章(调度)是优化的主要手段。第2、3、4章是全书的理论基础和基本的程序变换方法。为使程序分析和优化更精确和有效，第7章和第11章是必须的，但它们增加了编泽器的实现难度。最后三章可以看成是编译技术的特定应用。
Kuck院士在他的评论中接着写道：“作为该领域的创新者和研发者，作者依据丰富的经验写出了此书。该书对Cache管理、向量化、并行化等优化，做了非常好的综合。论题涉及到现代体系结构，这些题材确实可以应用于从台式计算机到世界上最快的超级计算机上。书中的例子是从Fortran中抽取出来的，但其理论可以应用到许多程序设计语言上。我认为该书将起到极好的教科书作用，并为软件开发者广泛地利用。”
正如Kuck院士所说，书中用大量的Fortran例子说明基本概念、理论、方法和优化的效果，使全书通俗易懂。每章的后面有一节实例研究，介绍作者在编译器的实践中的真实材料，以及有关策略有效性的实验论据。最后还有若干练习题。这些材料和习题无论是对学生，还是对学术界、工业界的软件开发者都大有益处。这里软件开发者不仅指编译器的设计与实现者，还包括应用软件开发者。他们可以从中学到如何写一个优化程序的许多概念、方法和规范，特别是应使用程序设计语言中那些有效的语言成分，摒弃那些使程序可读性、可维护性差和难以优化的语言成分。
我们希望此书的翻译出版，能对我国高校的软件教学与科研有所帮助。这是我们翻译此书的初衷。
本书的翻译组织工作由张兆庆研究员全面负责。作者介绍、前言、前四章和附录由张兆庆和乔如良研究员译校，第5、6章由刘畅博士翻译，第7、11、12章由连瑞琦副研究员翻译，第8、10章由吴承勇副研究员翻译，第9、13、14章由冯晓兵副研究员翻译。译者自知水平有限，译文中难免有不妥之处，敬请读者批评指正。
感谢机械工业出版社组织翻译这部巨著，感谢李伯民老师仔细阅读译稿，捉出许多宝贵意见，并对译稿做了大量编辑加工。
译者
2003年11月25日
Intel公司David Kuck院士在评论Ken Kennedy和Randy Allen的新书“Optimizing Compilers for Modern Architectures：ADependence-Based Approach”时，这样写道：“编译程序是计算机科学与技术的皇后。编译器一直是应用与系统之间的桥梁。现在它们不仅决定应在新的硬件中实现哪些体系结构特色，而且说明对软件开发者而言，哪些新的语言特色将是有效的。”
Kuck院士和Kennedy教授都是并行优化编译理论与实践方面的最著名学者。Kuck将编译程序称为“计算机科学与技术的皇后”是十分恰当的。
自1958年ALGOL58问世后，20世纪60年代在程序设计语言理论、数据结构、算法设计与分析、可计算性理论等方面的研究，取得了令人惊叹的硕果，编译理论、技术和实验起了很大的推动作用。至今编译领域中仍有很多具有挑战性的问题，吸引广大计算科学与技术研究人员投身于此项事业。
现代计算机体系结构大都具有各种粒度的并行机制和分层存储结构，访存仍是当今各类计算机体系结构的瓶颈。优化编译器的主要任务可以说是：扬计算机结构之长一挖掘程序中的并行性，避其之短一挖掘程序的局部性(重用性)，实施有效的寄存器分配和Cache管理。
这正是Kennedy和Allen在书中讲述的主要内容。第5章(提高细粒度并行性)，第6章(开发粗粒度并行性)，第8章(改进寄存器的使用)，第9章(管理Cache)和第10章(调度)是优化的主要手段。第2、3、4章是全书的理论基础和基本的程序变换方法。为使程序分析和优化更精确和有效，第7章和第11章是必须的，但它们增加了编泽器的实现难度。最后三章可以看成是编译技术的特定应用。
Kuck院士在他的评论中接着写道：“作为该领域的创新者和研发者，作者依据丰富的经验写出了此书。该书对Cache管理、向量化、并行化等优化，做了非常好的综合。论题涉及到现代体系结构，这些题材确实可以应用于从台式计算机到世界上最快的超级计算机上。书中的例子是从Fortran中抽取出来的，但其理论可以应用到许多程序设计语言上。我认为该书将起到极好的教科书作用，并为软件开发者广泛地利用。”
正如Kuck院士所说，书中用大量的Fortran例子说明基本概念、理论、方法和优化的效果，使全书通俗易懂。每章的后面有一节实例研究，介绍作者在编译器的实践中的真实材料，以及有关策略有效性的实验论据。最后还有若干练习题。这些材料和习题无论是对学生，还是对学术界、工业界的软件开发者都大有益处。这里软件开发者不仅指编译器的设计与实现者，还包括应用软件开发者。他们可以从中学到如何写一个优化程序的许多概念、方法和规范，特别是应使用程序设计语言中那些有效的语言成分，摒弃那些使程序可读性、可维护性差和难以优化的语言成分。
我们希望此书的翻译出版，能对我国高校的软件教学与科研有所帮助。这是我们翻译此书的初衷。
本书的翻译组织工作由张兆庆研究员全面负责。作者介绍、前言、前四章和附录由张兆庆和乔如良研究员译校，第5、6章由刘畅博士翻译，第7、11、12章由连瑞琦副研究员翻译，第8、10章由吴承勇副研究员翻译，第9、13、14章由冯晓兵副研究员翻译。译者自知水平有限，译文中难免有不妥之处，敬请读者批评指正。
感谢机械工业出版社组织翻译这部巨著，感谢李伯民老师仔细阅读译稿，捉出许多宝贵意见，并对译稿做了大量编辑加工。
译者
2003年11月25日
前言回到顶部↑
现代体系结构的编译器设计
影响人们对世界理解的主要方面之一是描述它的方法，人们往往借助于语言中的概念表述来传达他们的理解。在使用计算机语言时这更为明显。计算机科学家使用的语言影响着问题描述到最终实现的算法方法。LISP程序员解决问题的方法与IBM 370汇编程序员的方法就很不相同。
可见语言在应用设计中具有强烈影响，而高级语言具有内在的高效优点，语言研究的主要目标是开发人类更容易理解的计算机语言。尽管语言研究获得的成果使之更容易使用，但是在产品应用的开发中未被广泛采用。主要原因很简单：有效性——从这些语言写的代码产生的可执行程序对于产品使用太慢。而且，如果一个问题描述超出了计算机本机指令，将这些描述映射到指令集则变得更加困难。
如果我们曾经有过这样的实际语言，先进编译器技术将成为克服它们固有性能缺陷的基础工具。换句话说，编译器优化是使用高级语言的基本保证技术。数据依赖是基本的编译器分析工具，用来优化现代机器体系结构上的程序，因为它能使编译器对不同的代码段是否访问相同的或不同的存储单元进行推断。这样可以用它来确定一个给定的程序是否可以并行化，或者可以更加频繁地重用在寄存器和高速缓存中的数据。至今初级编译器课程中很少讲授依赖分析。这样，大多数大学生计算机科学主修课从不讲述。
本书的一个主要目标是集中在一册书里对数据依赖作广泛的介绍，它可以同样由从业人员和学生们用于学习关于数据依赖及其对重要优化问题的应用，如并行化和编译器的存储分层结构管理。虽然在20世纪60年代编译器早期研究人员就提出了数据依赖，大多数有说服力的依赖应用是在使用循环和数组的情况下。这些结构本质上是重复计算，而重复计算提供了最适宜的优化场所。扩充依赖到支持数组和循环是本书的关注点。
这本著作介绍的理论基础是基于循环依赖的。它包括基于依赖的变换的正确性论述和依赖测试的详细过程。说明怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书也讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构(例如，向量、多处理器、超标量)的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人们熟知的应用，包括硬件设计、数组语言的实现以及消息传递系统的编译。
除了基本理论，本书还应用依赖处理真实编译器优化中的实际问题。通过介绍一些有效的实现算法，以及我们从结合研究和商用实现的经验中获得的认识，达到上述目的。只要有可能我们就用例子来传授这些认识，经常用图形化的依赖关系描述来传授对讨论中的问题的直观理解。本书介绍的大多数算法是基于我们工作中已经构造的实现。设计的这些算法已达到很高的精度，不需要再花运行时间就可以将它们放在编译器中实际使用。最后，每章包含一些材料，按照我们自己的经验，讨论我们介绍的和已经付诸实现的东西之间的关系，包括
优点和缺点。
由于本书将理论与实践融合一体，既适合作为学校的教科书，又可以作为产业界从业人员的参考书。我们仅假定读者了解大学的初级编译器课程，以及具有Hennessy和Patterson的(Computer Organization and Design：The Hardware／Software Interface))水平的机器设计原理。过去几年，我们在Rice大学开设了一门一学期的研究生课程，内容涵盖本书的所有材料。然而我们相信这些材料也适宜包含在一门大学高年级课程中。本书是按指导风格写成的，使读者能获得足够的见解，容易去理解介绍的概念。另外，书中包含为了帮助学生更清楚地思考那些基本问题的讨论和设计的习题。
为了符合商用编译器作者的需要，书中包含对依赖测试和变换算法的详细介绍。这样做的主要理由是可以让实际编译器开发者避免过去20多年我们自己在实现中遇到过的陷阱。例如，第3章中的依赖测试的细节如果从首要的原理推导，那么往往很难精确地得到正确结果。因此在可能时，我们尽力介绍完整的算法。使用书中包含的材料，我们已帮助一些公司在商业产品中实现依赖测试、向量化和并行化。我们确信这些策略在实践中是有效的。
本书是在Rice大学一个为期20年的研究项目的产物，该项目为向量和并行计算机系统研发基础的编译技术。在1979年开始这个研究项目时，我们相信源—源翻译器对向量机的支持才是必要的，而不是基于依赖的编译器。理由是基于实验：依赖实现需要的编译时间对实用来说太长了，并且它们的输出通常可以通过简单的检查加以改善。我们认为在产品编译器中太长的编译时间需求是不能容忍的，但对只做一次的源—源翻译器来说是很好的。此外，可以让有经验的程序员调整源—源翻译器的输出，使之达到更佳的性能。我们研究的最令人满意的结果之一，在于发现我们最初的设想何等错误——依赖不仅对产品编译器是有效的，而且比起我们最初的猜想，它是更加强有力的工具和可用的理论。任何现代优化编译器已将依赖作为基本构件，并且优化的结果不仅应用于向量机(它们做得极为出色)，而且也应用于标量机，甚至应用到硬件设计中。
因为机器设计的不断进步，人们对几年前看起来似乎过时的论题(例如向量化)，现在重新发现了它们的重要性。向量化方法对改善VLIW和超标量机的性能还是有用的，办法是在最内层循环提供额外的指令级并行性。然而，由于更加重要的原因这本书是适时的。因为处理器和存储器性能之间的距离增加了，在现代体系结构上必须实施的多数优化与存储访问有关。依赖提供一个关于存储访问的合理框架，它将继续增加有用性。
虽然我们打算覆盖许多研究人员的重要工作，但是我们自然将注意力集中在过去二十几年里作者和同事们于Rice大学做过的工作上。总之，我们的目标是将我们从该领域的经历中获得的综合知识付印。因此不应该将本书看成是文献的详尽的综述，而是开发基于依赖的编译器的实用指南。为表达清楚；有时不得不牺牲一些技术细节。我们的总目标是给读者充分的直观知识，使其在编译技术这个引人入胜的领域中能有效地工作。
内容概述
本书由14章组成，它们的内容在下面各段中概述。材料的核心包含在前9章中；余下各章集中于基本材料的扩充和在不同的问题领域的应用。
第1章，高性能体系结构对编译器的挑战，是对现代计算机体系结构所做的综述和分类，并讨论对每一类体系结构提出的主要编译挑战。重要的主题包括流水线并行性，向量指令，异步处理器并行性，超标量指令和VLIW指令，以及存储层次结构管理。引入依赖概念作为保证并行性安全使用的机制。
第2章，依赖：理论与实践，讨论依赖的基本概念，以及它的若干性质，包括方向向量和距离向量。主要的目标是证明一些基本定理，它们确立维持依赖的变换的正确性，特别是在循环嵌套中。这一章以一个样例向量化算法结束，算法说明依赖的有用性，并用作后面讨论向量化和并行化的模型。
第3章，依赖测试，提供对引用偶之间测试依赖的系统介绍。包含对下标分类、单下标测试和耦合下标组中依赖测试的讨论。这部分材料强调在可能的地方彻底地消除一个依赖，并得到尽可能接近的依赖性质，如方向向量。
第4章，初等变换，覆盖精确依赖分析的基本变换，包括循环正规化，标量数据流分析，表达式传播和替换，归纳变量替换，以及标量重命名。
第5章，提高细粒度并行性，集中于需要支持向量指令和VLIW或超标量处理器的内循环并行性。这一章探讨对第2章中介绍的分层并行代码生成过程的变形和扩展。特别将重点放在循环交换、标量扩展、结点分裂，数组重命名和向量化过程中的循环倾斜。
影响人们对世界理解的主要方面之一是描述它的方法，人们往往借助于语言中的概念表述来传达他们的理解。在使用计算机语言时这更为明显。计算机科学家使用的语言影响着问题描述到最终实现的算法方法。LISP程序员解决问题的方法与IBM 370汇编程序员的方法就很不相同。
可见语言在应用设计中具有强烈影响，而高级语言具有内在的高效优点，语言研究的主要目标是开发人类更容易理解的计算机语言。尽管语言研究获得的成果使之更容易使用，但是在产品应用的开发中未被广泛采用。主要原因很简单：有效性——从这些语言写的代码产生的可执行程序对于产品使用太慢。而且，如果一个问题描述超出了计算机本机指令，将这些描述映射到指令集则变得更加困难。
如果我们曾经有过这样的实际语言，先进编译器技术将成为克服它们固有性能缺陷的基础工具。换句话说，编译器优化是使用高级语言的基本保证技术。数据依赖是基本的编译器分析工具，用来优化现代机器体系结构上的程序，因为它能使编译器对不同的代码段是否访问相同的或不同的存储单元进行推断。这样可以用它来确定一个给定的程序是否可以并行化，或者可以更加频繁地重用在寄存器和高速缓存中的数据。至今初级编译器课程中很少讲授依赖分析。这样，大多数大学生计算机科学主修课从不讲述。
本书的一个主要目标是集中在一册书里对数据依赖作广泛的介绍，它可以同样由从业人员和学生们用于学习关于数据依赖及其对重要优化问题的应用，如并行化和编译器的存储分层结构管理。虽然在20世纪60年代编译器早期研究人员就提出了数据依赖，大多数有说服力的依赖应用是在使用循环和数组的情况下。这些结构本质上是重复计算，而重复计算提供了最适宜的优化场所。扩充依赖到支持数组和循环是本书的关注点。
这本著作介绍的理论基础是基于循环依赖的。它包括基于依赖的变换的正确性论述和依赖测试的详细过程。说明怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书也讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构(例如，向量、多处理器、超标量)的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人们熟知的应用，包括硬件设计、数组语言的实现以及消息传递系统的编译。
除了基本理论，本书还应用依赖处理真实编译器优化中的实际问题。通过介绍一些有效的实现算法，以及我们从结合研究和商用实现的经验中获得的认识，达到上述目的。只要有可能我们就用例子来传授这些认识，经常用图形化的依赖关系描述来传授对讨论中的问题的直观理解。本书介绍的大多数算法是基于我们工作中已经构造的实现。设计的这些算法已达到很高的精度，不需要再花运行时间就可以将它们放在编译器中实际使用。最后，每章包含一些材料，按照我们自己的经验，讨论我们介绍的和已经付诸实现的东西之间的关系，包括
优点和缺点。
由于本书将理论与实践融合一体，既适合作为学校的教科书，又可以作为产业界从业人员的参考书。我们仅假定读者了解大学的初级编译器课程，以及具有Hennessy和Patterson的(Computer Organization and Design：The Hardware／Software Interface))水平的机器设计原理。过去几年，我们在Rice大学开设了一门一学期的研究生课程，内容涵盖本书的所有材料。然而我们相信这些材料也适宜包含在一门大学高年级课程中。本书是按指导风格写成的，使读者能获得足够的见解，容易去理解介绍的概念。另外，书中包含为了帮助学生更清楚地思考那些基本问题的讨论和设计的习题。
为了符合商用编译器作者的需要，书中包含对依赖测试和变换算法的详细介绍。这样做的主要理由是可以让实际编译器开发者避免过去20多年我们自己在实现中遇到过的陷阱。例如，第3章中的依赖测试的细节如果从首要的原理推导，那么往往很难精确地得到正确结果。因此在可能时，我们尽力介绍完整的算法。使用书中包含的材料，我们已帮助一些公司在商业产品中实现依赖测试、向量化和并行化。我们确信这些策略在实践中是有效的。
本书是在Rice大学一个为期20年的研究项目的产物，该项目为向量和并行计算机系统研发基础的编译技术。在1979年开始这个研究项目时，我们相信源—源翻译器对向量机的支持才是必要的，而不是基于依赖的编译器。理由是基于实验：依赖实现需要的编译时间对实用来说太长了，并且它们的输出通常可以通过简单的检查加以改善。我们认为在产品编译器中太长的编译时间需求是不能容忍的，但对只做一次的源—源翻译器来说是很好的。此外，可以让有经验的程序员调整源—源翻译器的输出，使之达到更佳的性能。我们研究的最令人满意的结果之一，在于发现我们最初的设想何等错误——依赖不仅对产品编译器是有效的，而且比起我们最初的猜想，它是更加强有力的工具和可用的理论。任何现代优化编译器已将依赖作为基本构件，并且优化的结果不仅应用于向量机(它们做得极为出色)，而且也应用于标量机，甚至应用到硬件设计中。
因为机器设计的不断进步，人们对几年前看起来似乎过时的论题(例如向量化)，现在重新发现了它们的重要性。向量化方法对改善VLIW和超标量机的性能还是有用的，办法是在最内层循环提供额外的指令级并行性。然而，由于更加重要的原因这本书是适时的。因为处理器和存储器性能之间的距离增加了，在现代体系结构上必须实施的多数优化与存储访问有关。依赖提供一个关于存储访问的合理框架，它将继续增加有用性。
虽然我们打算覆盖许多研究人员的重要工作，但是我们自然将注意力集中在过去二十几年里作者和同事们于Rice大学做过的工作上。总之，我们的目标是将我们从该领域的经历中获得的综合知识付印。因此不应该将本书看成是文献的详尽的综述，而是开发基于依赖的编译器的实用指南。为表达清楚；有时不得不牺牲一些技术细节。我们的总目标是给读者充分的直观知识，使其在编译技术这个引人入胜的领域中能有效地工作。
内容概述
本书由14章组成，它们的内容在下面各段中概述。材料的核心包含在前9章中；余下各章集中于基本材料的扩充和在不同的问题领域的应用。
第1章，高性能体系结构对编译器的挑战，是对现代计算机体系结构所做的综述和分类，并讨论对每一类体系结构提出的主要编译挑战。重要的主题包括流水线并行性，向量指令，异步处理器并行性，超标量指令和VLIW指令，以及存储层次结构管理。引入依赖概念作为保证并行性安全使用的机制。
第2章，依赖：理论与实践，讨论依赖的基本概念，以及它的若干性质，包括方向向量和距离向量。主要的目标是证明一些基本定理，它们确立维持依赖的变换的正确性，特别是在循环嵌套中。这一章以一个样例向量化算法结束，算法说明依赖的有用性，并用作后面讨论向量化和并行化的模型。
第3章，依赖测试，提供对引用偶之间测试依赖的系统介绍。包含对下标分类、单下标测试和耦合下标组中依赖测试的讨论。这部分材料强调在可能的地方彻底地消除一个依赖，并得到尽可能接近的依赖性质，如方向向量。
第4章，初等变换，覆盖精确依赖分析的基本变换，包括循环正规化，标量数据流分析，表达式传播和替换，归纳变量替换，以及标量重命名。
第5章，提高细粒度并行性，集中于需要支持向量指令和VLIW或超标量处理器的内循环并行性。这一章探讨对第2章中介绍的分层并行代码生成过程的变形和扩展。特别将重点放在循环交换、标量扩展、结点分裂，数组重命名和向量化过程中的循环倾斜。
序言回到顶部↑
Randy Allen和Ken Kennedy编写的“现代体系结构的优化编译器”一书是并行优化编译技术领域中一部权威性的著作。有幸由乔如良教授和张兆庆教授将全书译成中文，无疑对国内这一领域的教学、科研和工程的发展有着深远意义。
编译优化理论和技术是决定现代高性能计算机发展的十分关键的技术领域之一。优化编译技术的研究发展是和先进计算机结构——从微处理器到超级计算机——紧密相关联的。纵观优化编译技术最为超前的美国，各大学和科研机构中对这一领域的研究多是以电脑主流制造业的密切支持与合作研究为背景的。先进计算机体系结构和编译优化技术真可说是休戚与共、缺一不可。
本书的两位作者是长期从事优化编译技术研究的知名专家。特别是K．Kennedy教授更是学术界公认的泰斗。肯尼迪教授领导主持的一系列优化编译课题，既具有杰出的技术水平，又有着重大的学术影响。早在20世纪70年代末期，肯尼迪的研究工作对自动向量化编译技术的奠基和发展起过重大作用。80年代，肯尼迪和他在RICE大学的研究室对自动并行编译技术的贡献更为卓著。例如，他们在过程间优化的研究成果首创被商用编译器成功采用的先例。
基于他在学术上的成就和对计算机界的卓越贡献，肯尼迪教授先后被选为美国国家工程学院(National Academy of Engineering)院士，美国高科技协会(American Association for Advanced of Science)院士，IEEE院士和美国计算机学会(ACM)院土。肯尼迪教授在其三十多年的学术历程中，亲自指导了三十多名博士生。其中许多都是优化编译技术领域的精英，大多在知名大学任教或成为工业界的骨干。这本巨著中的许多内容正是作者和他的学生们多年经验的结晶。1997年，肯尼迪被美国总统任命为HPCC委员会两主席之一。
张、乔二教授是国内优化编译方面的资深专家和学术带头人。他们主持领导的中国科学院计算所先进编译技术试验室曾承担多项这一领域中重大长期研究项目，成果硕硕。近年来承担的Motorola和Intel等大公司委托的优化编译技术上的工程项目在国际上也颇具影响。由张、乔二教授和冯晓兵、吴承勇、连瑞琦、刘畅主持本书的翻译本出版是中国计算机学术界的一件大喜事，值得我们庆贺。
我有幸与Kennedy教授及张、乔、冯、吴等译者相识多年，这次能为这本书的中译本做序是我的荣幸。希望我的寥寥数言能有助于本书在国内计算机界广为推广。
美国特拉华大学(University of Delaware)电子与计算机工程系终身教授特拉华生物研究所生物信息中心主任
SUX excellence中心主任
CAPSL实验室主任和中国科学院计算技术研究所客座教授及联合实验室主任
编译优化理论和技术是决定现代高性能计算机发展的十分关键的技术领域之一。优化编译技术的研究发展是和先进计算机结构——从微处理器到超级计算机——紧密相关联的。纵观优化编译技术最为超前的美国，各大学和科研机构中对这一领域的研究多是以电脑主流制造业的密切支持与合作研究为背景的。先进计算机体系结构和编译优化技术真可说是休戚与共、缺一不可。
本书的两位作者是长期从事优化编译技术研究的知名专家。特别是K．Kennedy教授更是学术界公认的泰斗。肯尼迪教授领导主持的一系列优化编译课题，既具有杰出的技术水平，又有着重大的学术影响。早在20世纪70年代末期，肯尼迪的研究工作对自动向量化编译技术的奠基和发展起过重大作用。80年代，肯尼迪和他在RICE大学的研究室对自动并行编译技术的贡献更为卓著。例如，他们在过程间优化的研究成果首创被商用编译器成功采用的先例。
基于他在学术上的成就和对计算机界的卓越贡献，肯尼迪教授先后被选为美国国家工程学院(National Academy of Engineering)院士，美国高科技协会(American Association for Advanced of Science)院士，IEEE院士和美国计算机学会(ACM)院土。肯尼迪教授在其三十多年的学术历程中，亲自指导了三十多名博士生。其中许多都是优化编译技术领域的精英，大多在知名大学任教或成为工业界的骨干。这本巨著中的许多内容正是作者和他的学生们多年经验的结晶。1997年，肯尼迪被美国总统任命为HPCC委员会两主席之一。
张、乔二教授是国内优化编译方面的资深专家和学术带头人。他们主持领导的中国科学院计算所先进编译技术试验室曾承担多项这一领域中重大长期研究项目，成果硕硕。近年来承担的Motorola和Intel等大公司委托的优化编译技术上的工程项目在国际上也颇具影响。由张、乔二教授和冯晓兵、吴承勇、连瑞琦、刘畅主持本书的翻译本出版是中国计算机学术界的一件大喜事，值得我们庆贺。
我有幸与Kennedy教授及张、乔、冯、吴等译者相识多年，这次能为这本书的中译本做序是我的荣幸。希望我的寥寥数言能有助于本书在国内计算机界广为推广。
美国特拉华大学(University of Delaware)电子与计算机工程系终身教授特拉华生物研究所生物信息中心主任
SUX excellence中心主任
CAPSL实验室主任和中国科学院计算技术研究所客座教授及联合实验室主任
)
加载中...
