现代体系结构的优化编译器

作　者：	Randy Allen Ken Kennedy 张兆庆张兆庆
出版社：	机械工业出版社
丛编项：	计算机科学丛书
版权说明：	本书为公共版权或经版权方授权，请支持正版图书
标　签：	暂缺

ISBN	出版时间	包装	开本	页数	字数
未知	暂无	暂无	未知	0	暂无

作者简介

　　Randy Allen以优异盛开获得Harvard大学化学专业学士学位，在Rice（赖斯）大学获得数学科学硕士和博士学位。成为Rice大学研究员之后，Allen博士参加了业界编译器构造的实践活动。他经历了在Ardent Computers、Sun Microsystems、Chronologic Simulation、Synopsys和CynApps等公司的研究、高级开发以及管理工作。他本人以及和他人合作在各种学术会议和杂志上发表了15篇关于计算机优化、编译器重构和硬件模拟等方面的论文。他出任Suppercomputing和Conference on Programming Language and Design Implementation等会议的程序委员会成员。目前，他是几家公司（包括IBM、Intermetrics、Microtes Research和Mentor Graphics）的优化编译器顾问，是Catalytic Compilers公司总裁和CEO。Ken Kenedy是Rice大学计算工程的Ann and John Doerr教授和高性能软件研究中心（主任）。他是电气和电子工程师学会（IEEE）、计算机协会（ACM）以及美国科学促进会协会（AAAS）的会士，自1990年起，他是美国工程院院士。从1997年到1999年，任的PITAC报告中的领导作用，获得计算研究协会杰出贡献奖和RCI Seymour Cray HPCC Industry Recognition奖。Kennedy教授发表了150多篇学术论文，并指导34篇有关高性能计算机系统程序设计支撑软件的博士论文。他对高性能计算软件方面的贡献得到了公认，1995年他获得W.Wallace Mcdowell奖，这是IEEE Computer Society的最高研究奖项。1999年他被提名为ACM SIGPLAN程序设计语言成就奖的第三位接受者。

内容简介

本书介绍对现代体系结构的编译器进行优化的方法，理论基础是基于循环依赖的。分析基于依赖的变换的正确性论述和依赖测试的详细过程。剖析怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书还讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构（例如，向量、多处理器、超标量）的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人熟知的应用，如硬件设计、数组语言实现以及消息传递系统的编译。设计具有高性能微处理器的现代计算机体系结构，能够极大地提高计算机在性能方面的潜在优势。然而其高度的复杂性使得产生有效代码和实现其全部优势变得愈加困难。这本出自两位学术权威的具有里程碑意义的教科书，重点阐述了编译器对于解决这个至关重要问题所起到的关键作用。数据依赖是在高性能微处理器和并行体系结构上优化程序的基本编译器分析工具。它能使所编写的编译器自动地将简单的串行程序转换成具有现代体系结构特征的程序。数据依赖支持许多变换策略，也应用于一些重要的优化问题，本书对此做了全面介绍，并对基于数据依赖的编译器优化的重要性和广泛应用性进行了论证，给出了理解和实现它们所需要的基础，同时还为手工转换程序提供了详细说明。书中介绍的方法是基于过去二十多年的研究成果．取材于在美国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. 8 先进编译技术

1. 8. 1 依赖

1. 8. 2 变换

1. 9 小结

1. 10 实例研究

1. 11 历史评述与参考文献

习题

第2章依赖：理论与实践

2. 1 引言

2. 2 依赖及其性质

2. 2. 1 存-取分类

2. 2. 2 循环内的依赖

2. 2. 3 依赖和变换

2. 2. 4 距离向量和方向向量

2. 2. 5 循环携带依赖和循环无关依赖

2. 3 简单的依赖测试

2. 4 并行化和向量化

2. 4. 1 并行化

2. 4. 2 向量化

2. 4. 3 一个先进的向量化算法

2. 5 小结

2. 6 实例研究

2. 7 历史评述与参考文献

习题

第3章依赖测试

3. 1 引言

3. 2 依赖测试概述

3. 2. 1 下标划分

3. 2. 2 合并方向向量

3. 3 单下标依赖测试

3. 3. 1 ZIV测试

3. 3. 2 SIV测试

3. 3. 3 多归纳变量测试

3. 4 耦合组中的测试

3. 4. 1 Delta测试

3. 4. 2 更强有力的多下标测试

3. 5 实验研究

3. 6 各种测试的集成

3. 7 小结

3. 8 实例研究

3. 9 历史评述与参考文献

习题

第4章初等变换

4. 1 引言

4. 2 信息需求

4. 3 循环正规化

4. 4 数据流分析

4. 4. 1 定义-使用链

4. 4. 2 死代码消除

4. 4. 3 常数传播

4. 4. 4 静态单赋值形式

4. 5 归纳变量暴露

4. 5. 1 前向表达式替换

4. 5. 2 归纳变量替换

4. 5. 3 驱动替换过程

4. 6 小结

4. 7 实例研究

4. 8 历史评述与参考文献

习题

第5章提高细粒度并行性

5. 1 引言

5. 2 循环交换

5. 2. 1 循环交换的安全性

5. 2. 2 循环交换的有利性

5. 2. 3 循环交换和向量化

5. 3 标量扩展

5. 4 标量和数组重命名

5. 5 节点分裂

5. 6 归约识别

5. 7 索引集分裂

5. 7. 1 阈值分析

5. 7. 2 循环剥离

5. 7. 3 基于区域的分裂

5. 8 运行时符号解析

5. 9 循环倾斜

5. 10 各种变换的集成

5. 11 实际机器的复杂性

5. 12 小结

5. 13 实例研究

5. 13. 1 PFC

5. 13. 2 ArdentTitan编译器

5. 13. 3 向量化的性能

5. 14 历史评述与参考文献

习题

第6章开发粗粒度并行性

6. 1 引言

6. 2 单循环的处理方法

6. 2. 1 私有化

6. 2. 2 循环分布

6. 2. 3 对齐

6. 2. 4 代码复制

6. 2. 5 循环合并

6. 3 紧嵌循环套

6. 3. 1 为并行化的循环交换

6. 3. 2 循环选择

6. 3. 3 循环反转

6. 3. 4 为并行化的循环倾斜

6. 3. 5 模变换

6. 3. 6 基于有利性的并行化方法

6. 4 非紧嵌循环套

6. 4. 1 多层循环合并

6. 4. 2 一个并行代码生成算法

6. 5 一个扩充的例子

6. 6 并行性的封装

6. 6. 1 循环分段

6. 6. 2 流水线并行性

6. 6. 3 调度并行任务

6. 6. 4 制导的自调度

6. 7 小结

6. 8 实例研究

6. 8. 1 PFC和ParaScope

6. 8. 2 ArdentTitan编译器

6. 9 历史评述与参考文献

习题

第7章处理控制流

7. 1 引言

7. 2 if换

7. 2. 1 定义

7. 2. 2 分支的分类

7. 2. 3 前向分支

7. 2. 4 出口分支

7. 2. 5 后向分支

7. 2. 6 完全前向分支消除

7. 2. 7 化简

7. 2. 8 迭代依赖

7. 2. 9 if重构

7. 3 控制依赖

7. 3. 1 构造控制依赖

7. 3. 2 循环中的控制依赖

7. 3. 3 控制依赖的一个执行模型

7. 3. 4 控制依赖在并行化中的应用

7. 4 小结

7. 5 实例研究

7. 6 历史评述与参考文献

习题

第8章改进寄存器的使用

8. 1 引言

8. 2 标量寄存器分配

8. 2. 1 面向寄存器重用的数据依赖

8. 2. 2 循环携带和循环无关的重用

8. 2. 3 寄存器分配的例子

8. 3 标量替换

8. 3. 1 依赖图剪枝

8. 3. 2 简单替换

8. 3. 3 处理循环携带依赖

8. 3. 4 跨越多个迭代的依赖

8. 3. 5 删除标量拷贝

8. 3. 6 缓解寄存器压力

8. 3. 7 标量替换算法

8. 3. 8 实验数据

8. 4 展开和压紧

8. 4. 1 展开和压紧的合法性

8. 4. 2 展开和压紧算法

8. 4. 3 展开和压紧的效果

8. 5 面向寄存器重用的循环交换

8. 5. 1 对循环交换的考虑

8. 5. 2 循环交换算法

8. 6 面向寄存器重用的循环合并

8. 6. 1 面向重用的有利的循环合并

8. 6. 2 面向合并的循环对齐

8. 6. 3 合并机制

8. 6. 4 加权循环合并算法

8. 6. 5 面向寄存器重用的多层循环合并

8. 7 改进寄存器使用的变换综合

8. 7. 1 决定变换的顺序

8. 7. 2 例子：矩阵乘法

8. 8 复杂的循环嵌套

8. 8. 1 包含if语句的循环

8. 8. 2 梯形循环

8. 9 小结

8. 10 实例研究

8. 11 历史评述与参考文献

习题

第9章管理高速缓存

9. 1 引言

9. 2 适合于空间局部性的循环交换

9. 3 分块

9. 3. 1 非对齐的数据

9. 3. 2 分块的合法性

9. 3. 3 分块的有利性

9. 3. 4 一个简单的分块算法

9. 3. 5 带倾斜的分块

9. 3. 6 循环合并和对齐

9. 3. 7 结合其他变换的分块

9. 3. 8 有效性

9. 4 复杂循环嵌套中的高速缓存管理

9. 4. 1 三角形的高速缓存分块

9. 4. 2 特殊用途的变换

9. 5 软件预取

9. 5. 1 一个软件预取算法

9. 5. 2 软件预取的有效性

9. 6 小结

9. 7 实例研究

9. 8 历史评述与参考文献

习题

第10章调度

10. 1 引言

10. 2 指令调度

10. 2. 1 机器模型

10. 2. 2 直线型代码的图调度

10. 2. 3 表调度

10. 2. 4 踪迹调度

10. 2. 5 循环内的调度

10. 3 向量部件调度

10. 3. 1 链接

10. 3. 2 协处理器

10. 4 小结

10. 5 实例研究

10. 6 历史评述与参考文献

习题

第11章过程间分析和优化

11. 1 引言

11. 2 过程间分析

11. 2. 1 过程间问题

11. 2. 2 过程间问题分类

11. 2. 3 流不敏感副作用分析

11. 2. 4 流不敏感别名分析

11. 2. 5 常数传播

11. 2. 6 注销分析

11. 2. 7 符号化分析

11. 2. 8 数组区域分析

11. 2. 9 调用图的构造

11. 3 过程间优化

11. 3. 1 内联替换

11. 3. 2 过程克隆

11. 3. 3 混合优化

11. 4 管理整个程序的编译

11. 5 小结

11. 6 实例研究

11. 7 历史评述与参考文献

习题

第12章 C语言和硬件设计中的依赖

12. 1 引言

12. 2 优化C语言

12. 2. 1 指针

12. 2. 2 命名和结构

12. 2. 3 循环

12. 2. 4 作用域和静态变量

12. 2. 5 方言

12. 2. 6 其他问题

12. 3 硬件设计

12. 3. 1 硬件描述语言

12. 3. 2 优化模拟

12. 3. 3 综合优化

12. 4 小结

12. 5 实例研究

12. 6 历史评述与参考文献

习题

第13章编译数组赋值

13. 1 引言

13. 2 简单的标量化

13. 3 标量化变换

13. 3. 1 循环反转

13. 3. 2 输入预取

13. 3. 3 循环分裂

13. 4 多维标量化

13. 4. 1 多维中的简单标量化

13. 4. 2 外层循环预取

13. 4. 3 用于标量化的循环交换

13. 4. 4 通用的多维标量化

13. 4. 5 一个标量化的例子

13. 5 对向量机器的考虑

13. 6 标量化后的循环交换和合并

13. 7 小结

13. 8 实例研究

13. 9 历史评述与参考文献

习题

第14章编译高性能Fortran

14. 1 引言

14. 2 HPF编译器概览

14. 3 基本循环的编译技术

14. 3. 1 分布信息的传播和分析

14. 3. 2 迭代的划分

14. 3. 3 通信生成

14. 4 优化

14. 4. 1 通信向量化

14. 4. 2 重叠通信和计算

14. 4. 3 对齐和复制

14. 4. 4 流水

14. 4. 5 一般依赖环的识别

14. 4. 6 存储管理

14. 4. 7 处理多个维

14. 5 HPF的过程间优化

14. 6 小结

14. 7 实例研究

14. 8 历史评述与参考文献

习题

附录 Fortran 90基础

参考文献

索引