《高级语言程序中的数据结构优化概要》由会员分享，可在线阅读，更多相关《高级语言程序中的数据结构优化概要（15页珍藏版）》请在金锄头文库上搜索。
1、中南大学本科生毕业论文（设计）论文翻译 题 目 数据结构可视化实验平台 学生姓名 祝 杰 指导教师 余 腊 生 学 院 信息科学与工程学院 专业班级 计科0902班 完成时间 2013年4月 14高级语言程序中的数据结构优化基于分级的可扩展编译器新方向Tiark Rompf Arvind K.Sujeeth Nada AminKevin J. Browny Vojin Jovanovic HyoukJoong Leey Manohar Jonnalagedda Kunle Olukotuny Martin Odersky瑞士洛桑理工大学: first.lastepfl.chOracle实验室斯
2、坦福大学: asujeeth, kjbrown, hyouklee, kunlestanford.edu摘要高层次的数据结构是现代编程的基石，同时也阻碍了编译器优化。为了解释用户或库定义的数据结构，编译器需要具备可扩展性。扩展编译器的通用机制分为两类。前端宏，分级或部分评估系统，可用于在程序进入编译器前以编程的方式删除抽象，进行相应的具象化。此外，有些编译器通过在编译过程中添加新的变型或增加新的中间表示（IR）类型来扩展编译内部的运作。这两者单独都不足以处理高层次的数据结构所带来的挑战。本文展示了一种新颖的方式将两者结合起来，这种方式所产生效益远远大于两者效益之和。分段技术不仅可以用于前端，我
3、们在内部编译器变型中也可以使用分段。这些内部类型通过程序的执行来创建变型IR。总所周知，分段可以简化程序的生成，并可以通过同样的方式简化程序的转换。把转化定义为阶段IR解释器比在IR转化器上实现低级的IR要来得简单。通过自定义IR节点，很多被表示为从IR节点到分级程序片段的重写的优化可以被整合成一个变型，以缓和无序问题。推理性的重写可以在循环结构周围保持乐观的判断。我们演示了几个使用了这种架构而且功能特别强大的程序优化方式，它们面向以下数据结构：一个新的循环融合和砍伐森林算法，结构数组到数组的结构之间的转换，面向多样并行设备的对象扁平化和代码生成。我们通过一些展现出巨大加速的不平凡的案例研究来
4、验证我们的方法。分类和主题描述D.3.4编程语言：处理器-代码生成，优化，运行时环境；D.1.3编程技术：并发程序设计-并行程序设计通用术语设计，语言，性能关键词分级，代码生成，数据结构，可扩充编译程序/ 向量object Vector def fromArrayT:Numeric(a: ArrayT) =new Vector val data = a def zerosT:Numeric(n: Int) =Vector.fromArray(Array.fill(n)(i = zeroT)abstract class VectorT:Numeric val data: ArrayTdef +(
5、that: VectorT) =Vector.fromArray(data.zipWith(that.data)(_ + _) ./ 矩阵abstract class MatrixT:Numeric . / 复数case class Complex(re: Double, im: Double) def +(that: Complex) = Complex(re + that.re, im + that.im)def *(that: Complex) = .图 1. 高等级的Scala线性代数包的框架1. 引言将高级语言程序编译成低级语言程序是很难的，特别是因为这样的程序，使用了高层次的抽象和
6、定义。编译器无法看穿这些抽象和定义（“抽象代价”），它不能推理出领域特有的属性（“通用瓶颈”）。数据结构和操作集是其中最重要的抽象，也是目前被认为最难使用到优化编译程序中的。让我们考虑在Scala中的高级语言编程实例。我们要实现一个稠密线性代数包。图1显示了一个通过Array扩展而来的Vector和Matrix的框架，框架内部使用了高级操作集（fill，zipWith）。Vector和Matrix包含数值类型（模板类Numeric）。我们同时定义复数为一个新的数字类型。有了这些定义，我们可以像这样编写程序：def diag(k:Int) = k * Matrix.identity(n)val
7、m1 = (v1+v2).transpose * (v1+v2)val m2 = diag(l)if (scale) println(m1*m2) / = m1*(k*id) = k*m1*id = k*m1else println(m1) / 不需要计算 m2这样的代码优雅而高级，展示了Scala如何将注意力集中在抽象和归纳发展生产力的提高。不幸的是，代码将运行得很慢，比已经调整过只使用数组和while循环的低级实现方式慢一到两个数量级（见第5部分）。到底是什么回事？部分原因是：1）无论是Scala编译器还是JVM中的及时编译器都无法将诸如公共子表达式或冗余代码消除（CSE，DCE），通用优
8、化成非平凡的矩阵或矢量计算。2) 编译器对于像m*id = m（其中m是一个矩阵, id是单位矩阵）这样可以进行优化的特定领域的规则没有任何概念。3) 在函数式编程风格中，编程过程中会产生很多中间对象。4) 统一的JVM堆分配的对象无法表示复数。为了使编译器能够理解高级语言的抽象和定义，我们需要一种机制来扩展编译器以便于它能够处理这些抽象。有两个常见的方法。第一种是在程序编译前进行翻译，这样编译器就不需要知道这些抽象和定义。这是宏系统和分段的原理。部分求值（PE）也可以在程序编译前对其进行详细说明。第二种选择是教会编译器领域相关的规则。通常，编译器的可扩展性被理解为增加新的阶段的一种手段。一些
9、可扩展的编译器还允许添加新的IR类型，但新的节点与现有的通用的优化互相之间如何影响一般都没有明确。然而，两种方法都不足以单独解决高级数据结构与抽象定义带来的挑战。回到我们的例子，如果我们只有阶段或宏，表达m * id，也就是m，在到达编译器前就会被扩展为循环，所以我们无法对m进行化简。在一般情况下，有限的形式化简可以添加（见C+ expression templates51）如果想要添加进来的化简生效，所有的通用的编译器优化（CSE，常数传递，等）也会需要被复制。在另一方面，如果我们已经能够添加新的编译器关口，我们可以添加一个把m * id优化为m的关口，但是我们需要另一个把矩阵乘法扩展成循环
10、的关口。这些关口需要被实现成低级IR到IR的转换，这比仅仅使用普通的（多级）的计算表达来表达目标代码的宏观或分段的方法难多了。把优化实现为单独的关口的方式在许多优化被独立添加时会引起关口排序的问题。我们认为，我们真正需要的是最好的两个世界：一方面，我们想要将操作符号化以便于他们能够适应于转换规则。另一方面，我们也要使用分段来以编程方式定义转换的结果。此外，在使用优化时我们需要一种方法来定义转换的独立性以避免阶段排序问题。贡献在本文中，我们提出了一个可扩展编译器的框架，解决了这一挑战，同时尽量降低表达优化和转换的编码量。通过采用分段技术的中间语言以及一种不会产生阶段排序问题的方法整合独立的指定优
11、化，我们融合了操作集，改变了数据布局，对高级对象进行了深度优化，我们的方法极大地提升了高级程序的速度。为了说明我们的系统在较高的水平下如何工作，我们再来考虑线性代数的例子。通过分期我们从最初的程序中获得一个中间表达式。为了避免采用纯分期或宏观的方法，我们在不同的层次应用优化，我们将尽可能多的优化放在同一个关口以避免诸多传统的阶段排序问题。线性代数库的作者，通过重写将符号表达式重写为分段的程序片段的规则来实现线性代数优化。该系统通过积极假设，当事实证明中间转换不准确时则回滚，来进行重写。这种策略消除了由于一个优化模块不得不对另外一个模块的结果进行悲观假设而引起的阶段排序问题。一旦在线性代数的层面
12、无法进行更深的优化，我们就只能考虑由数组和循环组成的低级表达方式。我们把这种“昏暗的”转换实现成了中间程序的分段解释器。由于解释器也使用分段，它创建了新的程序，看起来似乎像是程序转化器。默认情况下，解释器会将每个表达式映射到一个在结构上相当的表达式。该库的作者将线性代数运算映射到它的低级表示。在这一水平上，该系统在组合关口，重新应用全局优化方面应用另一套优化，来更好的利用改变表达式带来的新机会。这个过程可以重复进行任意次。特别是，我们做出了如下贡献： 我们使用分段构建可扩展多关口的编译器同时可以有效地把模块化的优化整合成单一关口：分段IR解释器作为IR转换和推理重写允许将独立指定优化进行整合的
13、同时保持乐观的假设。 我们使用基于图的中间表示可能包含结构化的复合表达式。拆分和合并复合表达式使我们能够重用现有的优化（例如，DCE删除数据结构中未使用的部分）。这种方法扩展了强大的数据格式转换（例如，阵列结构到结构数组）。 我们提出了一种新的能够统一处理水平和垂直融合和非对称结构的遍历（flatMap，groupBy）的数据并行循环融合算法。 我们通过一些不平凡的案例演示了该编译器架构如何解决与数据结构相关的棘手的优化问题。我们初期的工作建立在Lightweight Modular Staging(LMS) 39之上，并且会随着工作的进行标注与之相似的和不同的工作。推理重写的方法是基于Len
14、er，Grove和Chambers的工作29。2. 背景 许多计算可以自然地根据执行的频率和信息的可用性来分成不同的阶段。Taha和Sheard46建立了多级编程（简称MSP），他们将阶段分得十分明确，允许程序员在下一个阶段求表达式的值（也叫表达式分段）。现阶段作为一个高效的代码生成器，在运行时产生下一个阶段的程序。分段和部分求值20密切相关，它将程序分成输入确定的一些部分。基于本文的目的，我们可以把部分求值（尤其是绑定时间分析（BTA）当成自动分级，把分级当成程序员控制的部分求值。一个关键的区别是，部分求值严格地使程序专门化，通常有着健全的保障。然而，在像MetaOCaml7这样的MSP语言
15、中添加分级注释使得分段的阶段划分时更加自由但是需要一定的注意以保证不改变计算的结果。大部分关于分段和部分求值的研究都是为了简化编译器的开发。例如，把解释器专门化成一个特定的程序能够产生一个去除了解释器（第一个Futamura投影15）的已编译程序。自适应的部分求值器可以通过解释器和编译器生成器来生成编译器。本文的论述中使用Scala和轻量级模块化分段（LMS）39，一种理论上的分段方法。与基于准引号的专用MSP语言相反，LMS只使用类型来区分计算阶段。属于第二阶段的表达式在第一阶段中有类型RepT，当在第二阶段时，会得到类型为T的运算。普通类型T的表达式将在第一阶段求值，在第二阶段中则变成了常数。普通的Scala类型系统传播关于哪些表达式分段了的信息，从而作为本地
