没有合适的资源?快使用搜索试试~ 我知道了~
首页《高级后端代码优化》——前沿编译技术解析
《高级后端代码优化》——前沿编译技术解析
需积分: 10 23 下载量 151 浏览量
更新于2024-07-21
收藏 5.28MB PDF 举报
"Advanced Backend Optimization" 是一本由 Sid Touati 和 Benoit Dupont de Dinechin 合著的专业书籍,于2014年由 Wiley 出版。这本书总结了作者们在后台优化领域超过十年的研究成果,主要面向教授和研究人员,涵盖了该领域的最新基础研究成果。 书中的内容独特,讨论了一些其他书籍尚未涉及的主题,例如优化编译中的阶段排序、指令级并行中的寄存器饱和度、软件流水线的代码大小减少以及内存层次结构对指令级并行的影响。此外,书中还更新了一些已知主题的最新研究,如寄存器需求、软件流水线和周期性寄存器分配等。 "Advanced Backend Code Optimization" 作为计算机工程系列的一部分,旨在深入探讨后台代码优化的各个方面。作者向读者展示了如何通过精细的优化技术提升程序性能,降低代码复杂性和资源消耗,同时充分利用现代处理器的并行性。 书的前言部分,作者 Sid Touati 向他的父母表达了敬意,感谢他们给予他深厚的人生基础。这本书的出版由 ISTE Ltd 和 John Wiley & Sons, Inc. 联合完成,并遵循版权法相关规定,任何复制、存储或传播都需要得到出版社的书面许可。 "Advanced Backend Optimization" 是一本深入探讨后台优化策略和技术的专业书籍,对于那些希望深入理解并改进软件性能,特别是针对处理器并行性的优化的学者和工程师来说,是一份宝贵的参考资料。书中包含的先进理论和实践案例将帮助读者掌握如何在实际项目中实施高效的后台优化。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/9115835/bg10.jpg)
Introduction xv
The practice is not very attractive. It is not rare to have a code transformation
implemented at frontend optimizing for a backend objective: for instance, cache
optimization at a loop nest can be done at frontend because the high-level program
structure (loops) has yet to be destroyed. Inversely, it is possible to have a high-level
analysis implemented at assembly or as binary code, such as data dependence and
interprocedural analysis. Compilers are very complex pieces of software that are
maintained for a long period of time, and the frontiers between high and low levels
can sometimes be difficult to define formally. Nevertheless, the notion of frontend
and backend optimization is not fundamental. It is a technical decomposition of
compilation mainly for easing the development of the compiler software.
We are interested in backend code optimization mainly due to a personal
inclination towards hardware/software frontiers. Even this barrier starts to leak with
the development of reconfigurable and programmable architectures, where compilers
are asked to generate a part of the instruction set. In this book, we have tried to be as
abstract as possible in order to have general results applicable to wide processor
families (superscalar, VLIW, Explicitly Parallel Instruction Computing (EPIC), etc.).
When the micro-architectural features are too complex to model, we provide
technical solutions for practical situations.
I.1. Inside this book
This book is the outcome of a long period of research activity in academia and
industry. We write fundamental results in terms of lemmas, definitions, theorems and
corollaries, and in terms of algorithms and heuristics. We also provide an appendix
that contains some experimental results. For future reproducibility, we have released
most of our experimental results in terms of documented software and numerical data.
Although we did not include all of our mature research results in this book, we
think that we have succeeded in summarizing most of our efforts on backend code
optimization. In the following, we briefly describe the organization of this book.
Section I.3, on basic recalls on instruction-level parallelism (ILP) in processor
architectures, starts with explaining the difference between superscalar and VLIW
architectures. ILP processor architectures are widely covered in other books, so this
section will be a brief summary.
Part 1: introduction to optimizing compilation
Chapter 1 is entitled “On the Decidability of Phase Ordering in Optimizing
Compilation”: we have had long and sometimes painful experiences with code
optimization of large and complex applications. The obtained speedups, in practice,
www.it-ebooks.info
![](https://csdnimg.cn/release/download_crawler_static/9115835/bg11.jpg)
xvi Advanced Backend Code Optimization
are not always satisfactory when using usual compilation flags. When iterative
compilation started to become a new trend in our field, we asked ourselves whether
such methodologies may outperform static compilation: static compilation is
designed for all possible data inputs, while iterative compilation chooses a data input
and therefore, it seems to simplify the problem. We studied the decidability of phase
ordering from the theoretical point of view in the context of iterative
compilation.
Part 2: instruction scheduling
This part of the book covers instruction scheduling in ILP. The chapters of this part
(Chapters 2–6) use the same notations, which are different from the notations used
in the following part. The reason why the formal notations in this part are slightly
different from the notations of Part 3 is that the instruction scheduling problems are
strongly related to the theory of machine scheduling. In this area of research, there are
some common and usual notations that we use in this part but not in Part 3.
Chapter 2, entitled “Instruction Scheduling Problems and Overview”, is a
reminder of scheduling problems for ILP, and their relationship with register
optimization. Special attention is given to cyclic scheduling problems because they
are of importance for optimizing the performance of loops.
Chapter 3, entitled “Applications of Machine Scheduling to Instruction
Scheduling”, is an interesting chapter that discusses the relationship between
theoretical scheduling problems and practical instruction scheduling problems.
Indeed, although instruction scheduling is a mature discipline, its relationship with
the field of machine scheduling is often ignored. In this chapter, we show how the
theory of machine scheduling can be applied to instruction scheduling.
Chapter 4, entitled “Instruction Scheduling before Register Allocation”, provides
a formal method and a practical implementation for cyclic instruction scheduling
under resource constraints. The presented scheduling method is still sensitive to
register pressure.
Chapter 5, entitled “Instruction Scheduling after Register Allocation”, presents a
postpass register allocation method. After an instruction scheduling, register allocation
may introduce spill code and may require making some instruction rescheduling. This
chapter presents a faster technique suitable for just-in-time compilation.
Chapter 6, entitled “Dealing in Practice with Memory Hierarchy Effects and
Instruction-Level Parallelism”, studies the complex micro-architectural features from
www.it-ebooks.info
![](https://csdnimg.cn/release/download_crawler_static/9115835/bg12.jpg)
Introduction xvii
a practical point of view. First, we highlight the problem with memory
disambiguation mechanisms in out-of-order processors. This problem exists in most
of the micro-architectures and creates false dependences between independent
instructions during execution, limiting ILP. Second, we show how to use insert
instructions for data preloading and prefetching in the context of embedded VLIW.
Part 3: register optimization
This part of the book discusses register pressure in ILP, which can be read
independently from Part 2. In order to understand all the formal information and
notations of this part, we advise the readers not to neglect the formal model and
notations presented in section 7.1.
Chapter 7, entitled “The Register Need of a Fixed Instruction Schedule”, deals with
register allocation. This is a wide research topic, where multiple distinct problems
coexist, some notions are similarly named but do not have the same mathematical
definition. Typically, the notion of the register need may have distinct significations.
We formally define this quantity in two contexts: the context of acyclic scheduling
(basic block and superblock) and the context of cyclic scheduling (software pipelining
of a loop). While the acyclic register need is a well-understood notion, we provide new
formal knowledge on the register need in cyclic scheduling.
Chapter 8 is entitled “The Register Saturation”: our approach here for tackling
register constraints is radically different from the usual point of view in register
allocation. Indeed, we study the problem of register need maximization, not
minimization. We explain the differences between the two problems and provide an
efficient greedy heuristic. Register maximization allows us to decouple register
constraints from instruction scheduling: if we detect that the maximal register need is
below the processor capacity, we can neglect register constraints.
Chapter 9, entitled “Spill Code Reduction”, mainly discusses schedule
independent register allocation (SIRA) framework: this approach handles register
constraints before instruction scheduling by adding edges to the data dependence
graph (DDG). It guarantees the absence of spilling for all valid instruction schedules.
This approach takes care not to alter the ILP if possible. We present the theoretical
graph approach, called SIRA, and we show its applications in multiple contexts:
multiple register file architectures, rotating register files and buffers. We present
SIRALINA, an efficient and effective heuristic that allows satisfactory spill code
reduction in practice while saving the ILP.
Chapter 10, entitled “Exploiting the Register Access Delays before Instruction
Scheduling”, discusses a certain problem and provides a solution: until now, the
www.it-ebooks.info
![](https://csdnimg.cn/release/download_crawler_static/9115835/bg13.jpg)
xviii Advanced Backend Code Optimization
literature has not formally tackled one of the real problems that arises when register
optimization is handled before instruction scheduling. Indeed, when the processor
has explicit register access delays (such as in VLIW, explicitly parallel instruction
computing (EPIC) and digital signal processing (DSP)), bounding or minimizing the
register requirement before fixing an instruction schedule may create a deadlock in
theory when resource constraints are considered afterward. The nature of this
problem and a solution in the context of SIRA are the main subject of this chapter.
Chapter 11 is entitled “Loop Unrolling Degree Minimization for Periodic
Register Allocation”: the SIRA framework proves to be an interesting relationship
between the number of allocated registers in a loop, the critical circuit of the DDG
and the loop unrolling factor. For the purpose of code size compaction, we show how
can we minimize the unrolling degree with the guarantee of neither generating spill
code nor altering the ILP. The problem is based on the minimization of a least
common multiple, using the set of remaining registers.
Part 4: Epilog
Chapter 12, entitled “Statistical Performance Analysis: The Speedup-Test
Protocol”, tends to improve the reproducibility of the experimental results in our
community. We tackle the problem of code performance variation in practical
observations. We describe the protocol called the Speedup-Test; it uses well-known
statistical tests to declare, with a proved risk level, whether an average or a median
execution time has been improved or not. We clearly explain what the hypotheses
that must be checked for each statistical test are.
Finally, the Conclusion describes some open problems in optimizing compilation
in general. These open problems are known but do not yet have satisfactory solutions
in the literature. Here, we conclude with a general summary.
I.2. Other contributors
This book is the outcome of long-term fundamental, experimental and technical
research using graph theory, scheduling theory, linear programming, complexity
theory, compilation, etc. We had great pleasure and honor collaborating with many
talented people with high-quality backgrounds in computer science, computer
engineering and mathematics. Table I.1 provides a list of collaborators for each
chapter, whom we would like to thank very much.
www.it-ebooks.info
![](https://csdnimg.cn/release/download_crawler_static/9115835/bg14.jpg)
Introduction xix
Chapter Contributor Nature of the contribution
Chapter 1 Pr Denis BARTHOU Formal proofs and modeling of phase ordering
problems
Chapter 6 Dr Christophe LEMIET PhD work, implementation, experiments,
performance analysis of memory disambiguation
mechanisms.
Dr Samir AMMENOUCHE PhD work, implementation, experiments,
performance analysis of instruction scheduling
under cache effects on VLIW processors.
Pr William JALBY PhD direction
Chapter 9 Dr Christine EISENBEIS Initial intuition and formal description of the
SIRA framework, PhD direction
Dr Karine DESCHINKEL SIRALINA heuristic proposal, software
implementation
Dr Sébastien BRIAIS Software implementation of SIRALINA,
experiments
Mr Frederic BRAULT Integration of SIRA framework inside an
industrial compiler for VLIW processors,
experiments and performance analysis
Chapter 10 Dr Karine DESCHINKEL Iterative method for eliminating non-positive
circuits in data dependence graphs
Dr Sébastien BRIAIS Formal proofs and algorithms, implementation
and experiments
Chapter 11 Dr Mounira BACHIR PhD work, formal proofs, implementation and
experiments
Dr Albert COHEN PhD direction
Dr David GREGG Contribution on algorithms
Mr Frederic BRAULT Experimental study with an industrial compiler for
VLIW processors
Chapter 12 Dr Julien WORMS Parametric statistics, statistical testing
Dr Sébastien BRIAIS Speedup-Test implementation
Dr Abdelhafid MAZOUZ Experimental study of program performance
variability
Table I.1. Other contributors to the results presented in this book
I.3. Basics on instruction-level parallelism processor architectures
Today’s microprocessors are the powerful descendants of the Von Neumann
computer [SIL 99]. Although various computer architectures have been considerably
changed and rapidly developed over the last 20 years, the basic principles in Von
Neumann computational model are still the foundation of today’s most widely used
computer architectures as well as high-level programming languages. The Von
Neumann computational model was proposed by Von Neumann and his colleagues in
www.it-ebooks.info
剩余384页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/a85f9b5ddf8441b8b4d02a19e1ce0d8e_vanridin.jpg!1)
vanridin
- 粉丝: 108
- 资源: 1188
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)