英语文献及翻译

《英语文献及翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、英语文献及翻译院系数学与统计学院专业数学与应用数学（师范类）年级2010级学生学号201006034105学生姓名刘笛改进导数计算的顶点消除算法的性能M. tadjouddinea，F. bodmanb，J.D. pryceb和s.a.fortha摘要：我们研究的顶点消除算法计算雅可比矩阵的两个方面。首先，我们usedmarkowitzlike启发式旨在最大限度地减少浮点操作数找到消除序列然后生成的雅可比矩阵编码。第二，我们使用深度优先遍历算法调整报表的雅可比矩阵编码，以减少存储器访问的数目。RISC处理器，我们观察到的为缓存

2、数据，浮点操作数给出了一个很好的估计的执行时间，而从缓存数据，执行时间的记忆为主的访问。我们还提出了一个基于排序函数语句重新排序方案，这将使该指令的开发这样的处理器级并行性和最大限度地提高性能。1引言许多科学应用程序需要的一阶导数（至少）的功能f:x∈Rn→y∈Rm由计算机程序表示。这可以使用自动分化（AD）[8]。典型的，从程序，我们可以首先，建立的函数f的计算图为一个有向无环图G=(V,E),其中V是顶点集，E VI，边的集合（VJ，VI）。一个顶点vi代表一个指令的原代码；边缘（VJ，VI）∈E，数据依赖关系从vj到vi

3、,vi取决于意义在vj,我们有

4、 V 

5、 = N +P +M = N，N，P，M分别输入数字，中间和输出顶点。第二，我们通过将其线性化G边缘与当地的偏导数。最后，我们消除，在一些命令，所有中间的顶点的ASG呈现二部。我们称这个过程为顶点的消除的方法，可以在[4，8，13]。在[4，8]详细，图G可以被看作是一个N×N稀疏三角矩阵C =（CIJ）称为扩展雅可比。的雅可比矩阵J可以通过使用某种形式的一个相当大的线性系统得到解决高斯消去法由于中间顶点数p趋于甚至在中型应用是巨大的，的顶点消除算法的性能可降解填写。浮点运算（行触发器）

6、，和填写，以消除序列测定。一个可能的问题最喜欢的答案是“消除序列提供了最快的代码在一个特定的平台？“。作为一个独立于平台的逼近问题的一个可能会问，“这消除序列最小化[数]分别填写失败？“。填充的问题被证明是NP-完全在[17]，我们怀疑对触发器的计数问题同样适用。因此，在实践中，一个接近最优序列必须被发现了启发式算法。我们的前提是，这样的序列允许我们生成的代码速度雅可比。Goedecker和Hoisie [7]报告说，在许多处理器的计算密集的代码的性能是一个额定峰值性能低百分比。CPU的性能增长之间有一个距离（约55%每年）和

7、内存的性能增长（每年7%）[9]。为了提高性能，内存交通似乎需要克服的障碍。在本文中，我们研究的顶点消除算法两个方面。首先。我们研究如何的浮点操作数（FLOPS）中的雅可比矩阵编码涉及其性能在各种平台上。第二，我们研究如何重新排序的代码语句影响记忆的雅可比矩阵访问和寄存器的使用。为了这个目的，我们产生的雅可比矩阵码以马科维茨像策略和语句重新排序并考察了不同的处理器和编译器，汇编器。我们研究了如何执行时间由数字触发器的影响，和内存的流量（加载和存储）。我们观察到的：•重新排序的代码语句可以显著提高代码性能的雅可比矩阵当这减少了内

8、存的流量百分比。•在缓存数据，执行时间的浮点操作数为主浮点运算，减少了进一步的性能改进。•从缓存数据，执行时间是由加载和存储操作数为主重新排序，减少这些存储器存取操作的代码的性能增强的雅可比矩阵。类似的行为是在数字代码的其他分析发现，例如见[7]。本文介绍了在一个数字代码的语义增强的上下文参数是计算机程序做广告。我们还描述了计划的工作来提高代码性能的雅可比矩阵，消除产生的顶点排序语句遵循标准的指令调度算法。2启发式算法在过去的四年里，几个启发式算法针对低填充生产消除排序已研究了。这些算法减少工作的预期效果。最广泛使用的是嵌套夹

9、层[3，5]和最小程度。后者是Markowitz方法[11]在[1]研究为例。嵌套的夹层，递归算法，首先找到一个平衡的分离器。这是一组顶点，去除时，曲线分割成两个或多个组件组成的顶点，当消除，创造不填写任何其他组件。顶点的排序在每个组件和分离器中的顶点，最后。过程是在组件重复。另一方面，Markowitz算法，不像嵌套解剖，检查整个图在重新排序，进行局部的优化。在每一步消，他们选择一个顶点的最小在某些意义上的成本，消除它，寻找在新的图的最小成本的下一个顶点。我们应用各种消除序列，有名字了，相反，Markowitz，VLR，Ma

10、rkowitz【resp.VLR 】前消除在[4，13]图获得使用语句级（SL）和代码列表（CL）分化[4，16]。我们研究了性能与没有施加语句重新排序第4节中描述的，看到[16]。3性能分析我们考虑两个在[4]中报道的试验问题：人类心脏偶极（HHD）从minpack 2测试