英语文献及翻译.docx

英语文献及翻译院 系 数学与统计学院 专 业 数学与应用数学（师范类） 年 级 2010级 学生学号 201006034105 学生姓名 刘笛 改进导数计算的顶点消除算法的性能M.tadjouddinea，F.bodmanb，J.D.pryceb和s.a.fortha摘要：我们研究的顶点消除算法计算雅可比矩阵的两个方面。首先，我们usedmarkowitzlike启发式旨在最大限度地减少浮点操作数找到消除序列然后生成的雅可比矩阵编码。第二，我们使用深度优先遍历算法调整报表的雅可比矩阵编码，以减少存储器访问的数目。RISC处理器，我们观察到的为缓存数据，浮点操作数给出了一个很好的估计的执行时间，而从缓存数据，执行时间的记忆为主的访问。我们还提出了一个基于排序函数语句重新排序方案，这将使该指令的开发这样的处理器级并行性和最大限度地提高性能。1引言许多科学应用程序需要的一阶导数（至少）的功能f : xRnyRm由计算机程序表示。这可以使用自动分化（AD） 8 。典型的，从程序，我们可以首先，建立的函数f的计算图为一个有向无环图G=(V,E), 其中V是顶点集，EVI，边的集合（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可以被看作是一个NN稀疏三角矩阵C=（CIJ）称为扩展雅可比。的雅可比矩阵J可以通过使用某种形式的一个相当大的线性系统得到解决高斯消去法由于中间顶点数p趋于甚至在中型应用是巨大的，的顶点消除算法的性能可降解填写。浮点运算（行触发器），和填写，以消除序列测定。一个可能的问题最喜欢的答案是“消除序列提供了最快的代码在一个特定的平台？“。作为一个独立于平台的逼近问题的一个可能会问，“这消除序列最小化数分别填写失败？“。填充的问题被证明是NP-完全在 17 ，我们怀疑对触发器的计数问题同样适用。因此，在实践中，一个接近最优序列必须被发现了启发式算法。我们的前提是，这样的序列允许我们生成的代码速度雅可比。Goedecker和Hoisie 7 报告说，在许多处理器的计算密集的代码的性能是一个额定峰值性能低百分比。CPU的性能增长之间有一个距离（约55%每年）和内存的性能增长（每年7%） 9 。为了提高性能，内存交通似乎需要克服的障碍。在本文中，我们研究的顶点消除算法两个方面。首先。我们研究如何的浮点操作数（FLOPS）中的雅可比矩阵编码涉及其性能在各种平台上。第二，我们研究如何重新排序的代码语句影响记忆的雅可比矩阵访问和寄存器的使用。 为了这个目的，我们产生的雅可比矩阵码以马科维茨像策略和语句重新排序并考察了不同的处理器和编译器，汇编器。我们研究了如何执行时间由数字触发器的影响，和内存的流量（加载和存储）。我们观察到的：重新排序的代码语句可以显著提高代码性能的雅可比矩阵当这减少了内存的流量百分比。在缓存数据，执行时间的浮点操作数为主浮点运算，减少了进一步的性能改进。从缓存数据，执行时间是由加载和存储操作数为主重新排序，减少这些存储器存取操作的代码的性能增强的雅可比矩阵。类似的行为是在数字代码的其他分析发现，例如见 7 。本文介绍了在一个数字代码的语义增强的上下文参数是计算机程序做广告。我们还描述了计划的工作来提高代码性能的雅可比矩阵，消除产生的顶点排序语句遵循标准的指令调度算法。2启发式算法在过去的四年里，几个启发式算法针对低填充生产消除排序已研究了。这些算法减少工作的预期效果。最广泛使用的是嵌套夹层 3，5 和最小程度。后者是Markowitz方法 11 在 1 研究为例。嵌套的夹层，递归算法，首先找到一个平衡的分离器。这是一组顶点，去除时，曲线分割成两个或多个组件组成的顶点，当消除，创造不填写任何其他组件。顶点的排序在每个组件和分离器中的顶点，最后。过程是在组件重复。另一方面，Markowitz算法，不像嵌套解剖，检查整个图在重新排序，进行局部的优化。在每一步消，他们选择一个顶点的最小在某些意义上的成本，消除它，寻找在新的图的最小成本的下一个顶点。我们应用各种消除序列，有名字了，相反，Markowitz，VLR，Markowitz【resp.VLR】前消除在 4，13 图获得使用语句级（SL）和代码列表（CL）分化 4，16 。我们研究了性能与没有施加语句重新排序第4节中描述的，看到 16 。3性能分析我们考虑两个在 4 中报道的试验问题：人类心脏偶极（HHD）从minpack2测试套件和Roe通量计算（ROE） 15 。这些例程被分化ADIFOR 2 和TAMC 6 和通过广告工具，ELIAD 4，16 利用启发式算法在2节中列出的。所有的雅可比矩阵码在不同的platformswithmaximumoptimisation编译和运行水平，多次仔细计算每个平台 4 。绩效评估，我们从不同的平台进行了汇编程序，计算负载的数量，商店和浮点运算。然后我们模拟的执行时间加载和存储条件和浮点运算。图1和图2显示我们的研究结果。图1和图2，Ultra10代表太阳超10处理器，440兆赫，32 kb的L1高速缓存，2 MB的L2高速缓存，并使用车间F906编译器；SGI的r12000处理器，300兆赫，64KB的L2高速缓存，8 MB的L2高速缓存，并利用F90 MIPS Pro 7.3编译器。在横坐标轴，范围14正向和反向顺序使用SL和CL分化；5的范围内8相同的启发式算法在用单一的继任者顶点预消除；9的范围内12启发式58后面通过语句重新排序；13的范围内使用SL和Cl的分化范围17201316之后的语句重新排序，范围2024分别手工编码，ADIFOR（向前），资产管理公司（前）和资产管理公司（反向）。所观察到的时间平均OBS时间是由一定数量的评估，得到的CPU时间跑，看到 4 的细节。如果是浮点操作数，B加载和存储的号码，K1，K2分别浮点运算和内存访问进行每周期的数目，我们计算以下参数：估计时间时间=max（A /K1，K2B/）周期时间，失败时间= A / K1 周期时间和LS时间= BK2 周期时间。超10处理器可以执行2浮点运算每循环4个周期的延迟和1负载或1商店2周期的延迟，和采用顺序执行指令的 10。该r12000可以执行2个浮点操作每个周期，1的内存访问（存取）都有2个周期的延迟，并采用乱序执行指令的 7，10。图1显示了执行时间的存储器存取时间的控制，这正好与估计时间。所观察到的时间的估计时间乘以延迟的近似存储器存取操作。此外，该语句重新排序进行更好的减少数内存访问。图2是从一个小的测试案例的结果，适合于L1高速缓存。虽然，我们观察到的内存访问中发挥了重要的作用，但更重要的是，减少了浮点操作影响了整体的执行时间和所观察到的时间是密切的floptime近似乘以浮点操作延迟。4语句重新排序方案生成的代码计算雅可比矩阵J，包括F的原代码，以及报表计算当地的衍生物，和C的nonzeros在消除。但它的大部分是消除报表，其中的造型和=cikckj或CIJ=需要+cikckj。语句可以重新以任何方式方面的依赖关系，即如果表S1 S2取决于声明，那么必须先于S1 S2。这个定义的雅可比矩阵编码的数据依赖图G=（V 0，V0，E0）在声明的集合。在 4，16 ，我们使用一个语句重新排序算法（SRA）使用深度优先遍历G0每个S1 2 V 0，试图将S2，S1的依赖，接近S1。这是希望这将速度了代码，让编译器执行更好的寄存器使用以来，在我们的测试情况下，高速缓存未命中了显示没有问题 16 。的好处是片状的，可能是因为没有考虑到的指令级并行性（ILP）现代基于缓存的机器和某些指令的潜伏期。在这项工作中，我们计划利用ILP的SRA优先的某些声明通过排序函数。编译器的优化工作的一个依赖图，其顶点的机器代码指令指令。我们不知道我们的工作指令G0。我们将使用相结合的寄存器和指令调度方法用于例如 12 和 10，14 排序函数的思想。我们的排名函数使用该操作的假设，它有更多的接班人，这是坐落在一个较长的路径应优先，有可能执行以最小的延迟和影响的其他更多的操作附表。顶点的S级2 V0是一个高度加权求和（S），最长路径的，和成功的（S）的接班人，我们计划实施这种重新排序方案和评估其影响数在计算雅可比矩阵的顶点消除算法的整体性能。5结论和进一步的工作我们提出了一个详细的性能分析的雅可比计算使用的顶点消除算法。我们已经表明，在高速缓存中的数据执行时间的浮点数相关操作而从高速缓存中的数据是与记忆相关的访问。我们指出，虽然顶点消除算法减少了浮点操作数，应该加上指令调度算法，使现代处理器的指令级并行性开发，减少存储器访问和最大化性能。我们描述了一个基于排序函数语句重新排序方案。我们计划实施和测试它使用中型问题上的RISC处理器。致谢这项工作是由格兰特GR / r21882 EPSRC和英国国防部的支持下。作者希望感谢教授J.K.瑞德启发的讨论和对工作的意见。参考文献 1 p. amestoy，T.戴维斯，达夫，I.。一个近似最小度排序算法。暹罗J.矩阵应用。，17（4）：886905，1996。2C. H.比肖夫，A.卡尔，该页，和A.莫尔。ADIFOR2：自动分化FORTRAN77个程序。计算科学与工程，3（3）：1832，1996。3C.伯恩斯坦，梅格斯，米勒和G.。并行和填写嵌套夹层之间的权衡。在SpaA 99。ACM，1999。 4 美国四，M. tadjouddine，J.普莱斯，J.瑞德。雅可比代码源转换生成顶点的消除可以手工编码的效率。ACM跨。数学上的。软，出现2004。 5 J.乔治和J.刘。一种自动嵌套夹层算法对不规则的有限元问题。暹罗的数值分析15:345杂志，363，1978。 6 卡明斯基R.捷林和T.。食谱伴随码的构造。acmtrans。onmath。软。，24（4）：437474，十二月1998。 7 美国goedecker hoisie和A.。数值型码的性能优化。暹罗费城，2001。8A. Griewank。评价衍生物：原理和算法分化技术。数19在前沿应用。数学。暹罗，费城，宾夕法尼亚大学，2000。 9 W.格洛普，D. Kaushik，D.凯斯，和B史密斯。提高稀疏矩阵向量的性能乘法阻断。技术报告，MCS划分，阿贡国家实验室。10C. hardnett，R.拉巴，K.帕莱姆和黄，W.。缓存敏感指令调度。技术报告crest-tr-01-003，git-cc-01-15，在嵌入式系统与技术研究中心，六月2001。 11 h. Markowitz。的逆淘汰形式及其应用。管理科学，3:257269，1957。 12 r.莫瓦尼，K.帕莱姆，诉萨卡，和美国reyen。结合寄存器分配和指令调度：（技术总结）。技术报告TR 698，报研究所，七月1995。 13 美国诺曼。高效的计算的雅可比矩阵的链规则优化的应用计算图。博士学位论文，德累斯顿技术大学，六月1999。 14 k.帕莱姆和B西蒙斯。调度时间关键指令RISC机器。ACMtoplas