英语文献及翻译.docx

英语文献及翻译院系数学与统计学院专业数学与应用数学(师范类)年级2010级学生学号201006034105学生姓名刘笛改进导数计算的顶点消除算法的性能M. tadjouddinea,F. bodmanb,. :我们研究的顶点消除算法计算雅可比矩阵的两个方面。首先,我们usedmarkowitzlike启发式旨在最大限度地减少浮点操作数找到消除序列然后生成的雅可比矩阵编码。第二,我们使用深度优先遍历算法调整报表的雅可比矩阵编码,以减少存储器访问的数目。RISC处理器,我们观察到的为缓存数据,浮点操作数给出了一个很好的估计的执行时间,而从缓存数据,执行时间的记忆为主的访问。我们还提出了一个基于排序函数语句重新排序方案,这将使该指令的开发这样的处理器级并行性和最大限度地提高性能。1引言许多科学应用程序需要的一阶导数(至少)的功能f:x∈Rn→y∈Rm由计算机程序表示。这可以使用自动分化(AD)[8]。典型的,从程序,我们可以首先,建立的函数f的计算图为一个有向无环图G=(V,E),其中V是顶点集,E VI,边的集合(VJ,VI)。一个顶点vi代表一个指令的原代码;边缘(VJ,VI)∈E,数据依赖关系从vj到vi,vi取决于意义在vj,我们有| V | = N +P +M = N,N,P,M分别输入数字,中间和输出顶点。第二,我们通过将其线性化G边缘与当地的偏导数。最后,我们消除,在一些命令,所有中间的顶点的ASG呈现二部。我们称这个过程为顶点的消除的方法,可以在[4,8,13]。在[4,8]详细,图G可以被看作是一个N×N稀疏三角矩阵C =(CIJ)称为扩展雅可比。的雅可比矩阵J可以通过使用某种形式的一个相当大的线性系统得到解决高斯消去法由于中间顶点数p趋于甚至在中型应用是巨大的,的顶点消除算法的性能可降解填写。浮点运算(行触发器),和填写,以消除序列测定。一个可能的问题最喜欢的答案是“消除序列提供了最快的代码在一个特定的平台?“。作为一个独立于平台的逼近问题的一个可能会问,“这消除序列最小化[数]分别填写失败?“。填充的问题被证明是NP-完全在[17],我们怀疑对触发器的计数问题同样适用。因此,在实践中,一个接近最优序列必须被发现了启发式算法。我们的前提是,这样的序列允许我们生成的代码速度雅可比。Goedecker和Hoisie [7]报告说,在许多处理器的计算密集的代码的性能是一个额定峰值性能低百分比。CPU的性能增长之间有一个距离(约55%每年)和内存的性能增长(每年7%)[9]。为了提高性能,内存交通似乎需要克服的障碍。在本文中,我们研究的顶点消除算法两个方面。首先。我们研究如何的浮点操作数(FLOPS)中的雅可比矩阵编码涉及其性能在各种平台上。第二,我们研究如何重新排序的代码语句影响记忆的雅可比矩阵访问和寄存器的使用。为了这个目的,我们产生的雅可比矩阵码以马科维茨像策略和语句重新排序并考察了不同的处理器和编译器,汇编器。我们研究了如何执行时间由数字触发器的影响,和内存的流量(加载和存储)。我们观察到的:•重新排序的代码语句可以显著提高代码性能的雅可比矩阵当这减少了内存的流量百分比。•在缓存数据,执行时间的浮点操作数为主浮点运算,减少了进一步的性能改进。•从缓存数据,执行时间是由加载和存储操作数为主重新排