英語文獻(xiàn)及翻譯.docx

英語文獻(xiàn)及翻譯院 系 數(shù)學(xué)與統(tǒng)計學(xué)院 專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué)（師范類） 年 級 2010級 學(xué)生學(xué)號 201006034105 學(xué)生姓名 劉笛 改進導(dǎo)數(shù)計算的頂點消除算法的性能M.tadjouddinea，F(xiàn).bodmanb，J.D.pryceb和s.a.fortha摘要：我們研究的頂點消除算法計算雅可比矩陣的兩個方面。首先，我們usedmarkowitzlike啟發(fā)式旨在最大限度地減少浮點操作數(shù)找到消除序列然后生成的雅可比矩陣編碼。第二，我們使用深度優(yōu)先遍歷算法調(diào)整報表的雅可比矩陣編碼，以減少存儲器訪問的數(shù)目。RISC處理器，我們觀察到的為緩存數(shù)據(jù)，浮點操作數(shù)給出了一個很好的估計的執(zhí)行時間，而從緩存數(shù)據(jù)，執(zhí)行時間的記憶為主的訪問。我們還提出了一個基于排序函數(shù)語句重新排序方案，這將使該指令的開發(fā)這樣的處理器級并行性和最大限度地提高性能。1引言許多科學(xué)應(yīng)用程序需要的一階導(dǎo)數(shù)（至少）的功能f : xRnyRm由計算機程序表示。這可以使用自動分化（AD） 8 。典型的，從程序，我們可以首先，建立的函數(shù)f的計算圖為一個有向無環(huán)圖G=(V,E), 其中V是頂點集，EVI，邊的集合（VJ，VI）。一個頂點vi代表一個指令的原代碼；邊緣（VJ，VI） E，數(shù)據(jù)依賴關(guān)系從vj 到 vi, vi取決于意義在vj, 我們有|V|=N+ P+ M=N，N，P，M分別輸入數(shù)字，中間和輸出頂點。第二，我們通過將其線性化G邊緣與當(dāng)?shù)氐钠珜?dǎo)數(shù)。最后，我們消除，在一些命令，所有中間的頂點的ASG呈現(xiàn)二部。我們稱這個過程為頂點的消除的方法，可以在 4，8，13 。在 4，8 詳細(xì)，圖G可以被看作是一個NN稀疏三角矩陣C=（CIJ）稱為擴展雅可比。的雅可比矩陣J可以通過使用某種形式的一個相當(dāng)大的線性系統(tǒng)得到解決高斯消去法由于中間頂點數(shù)p趨于甚至在中型應(yīng)用是巨大的，的頂點消除算法的性能可降解填寫。浮點運算（行觸發(fā)器），和填寫，以消除序列測定。一個可能的問題最喜歡的答案是“消除序列提供了最快的代碼在一個特定的平臺？“。作為一個獨立于平臺的逼近問題的一個可能會問，“這消除序列最小化數(shù)分別填寫失??？“。填充的問題被證明是NP-完全在 17 ，我們懷疑對觸發(fā)器的計數(shù)問題同樣適用。因此，在實踐中，一個接近最優(yōu)序列必須被發(fā)現(xiàn)了啟發(fā)式算法。我們的前提是，這樣的序列允許我們生成的代碼速度雅可比。Goedecker和Hoisie 7 報告說，在許多處理器的計算密集的代碼的性能是一個額定峰值性能低百分比。CPU的性能增長之間有一個距離（約55%每年）和內(nèi)存的性能增長（每年7%） 9 。為了提高性能，內(nèi)存交通似乎需要克服的障礙。在本文中，我們研究的頂點消除算法兩個方面。首先。我們研究如何的浮點操作數(shù)（FLOPS）中的雅可比矩陣編碼涉及其性能在各種平臺上。第二，我們研究如何重新排序的代碼語句影響記憶的雅可比矩陣訪問和寄存器的使用。 為了這個目的，我們產(chǎn)生的雅可比矩陣碼以馬科維茨像策略和語句重新排序并考察了不同的處理器和編譯器，匯編器。我們研究了如何執(zhí)行時間由數(shù)字觸發(fā)器的影響，和內(nèi)存的流量（加載和存儲）。我們觀察到的：重新排序的代碼語句可以顯著提高代碼性能的雅可比矩陣當(dāng)這減少了內(nèi)存的流量百分比。在緩存數(shù)據(jù)，執(zhí)行時間的浮點操作數(shù)為主浮點運算，減少了進一步的性能改進。從緩存數(shù)據(jù)，執(zhí)行時間是由加載和存儲操作數(shù)為主重新排序，減少這些存儲器存取操作的代碼的性能增強的雅可比矩陣。類似的行為是在數(shù)字代碼的其他分析發(fā)現(xiàn)，例如見 7 。本文介紹了在一個數(shù)字代碼的語義增強的上下文參數(shù)是計算機程序做廣告。我們還描述了計劃的工作來提高代碼性能的雅可比矩陣，消除產(chǎn)生的頂點排序語句遵循標(biāo)準(zhǔn)的指令調(diào)度算法。2啟發(fā)式算法在過去的四年里，幾個啟發(fā)式算法針對低填充生產(chǎn)消除排序已研究了。這些算法減少工作的預(yù)期效果。最廣泛使用的是嵌套夾層 3，5 和最小程度。后者是Markowitz方法 11 在 1 研究為例。嵌套的夾層，遞歸算法，首先找到一個平衡的分離器。這是一組頂點，去除時，曲線分割成兩個或多個組件組成的頂點，當(dāng)消除，創(chuàng)造不填寫任何其他組件。頂點的排序在每個組件和分離器中的頂點，最后。過程是在組件重復(fù)。另一方面，Markowitz算法，不像嵌套解剖，檢查整個圖在重新排序，進行局部的優(yōu)化。在每一步消，他們選擇一個頂點的最小在某些意義上的成本，消除它，尋找在新的圖的最小成本的下一個頂點。我們應(yīng)用各種消除序列，有名字了，相反，Markowitz，VLR，Markowitz【resp.VLR】前消除在 4，13 圖獲得使用語句級（SL）和代碼列表（CL）分化 4，16 。我們研究了性能與沒有施加語句重新排序第4節(jié)中描述的，看到 16 。3性能分析我們考慮兩個在 4 中報道的試驗問題：人類心臟偶極（HHD）從minpack2測試套件和Roe通量計算（ROE） 15 。這些例程被分化ADIFOR 2 和TAMC 6 和通過廣告工具，ELIAD 4，16 利用啟發(fā)式算法在2節(jié)中列出的。所有的雅可比矩陣碼在不同的platformswithmaximumoptimisation編譯和運行水平，多次仔細(xì)計算每個平臺 4 。績效評估，我們從不同的平臺進行了匯編程序，計算負(fù)載的數(shù)量，商店和浮點運算。然后我們模擬的執(zhí)行時間加載和存儲條件和浮點運算。圖1和圖2顯示我們的研究結(jié)果。圖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編譯器。在橫坐標(biāo)軸，范圍14正向和反向順序使用SL和CL分化；5的范圍內(nèi)8相同的啟發(fā)式算法在用單一的繼任者頂點預(yù)消除；9的范圍內(nèi)12啟發(fā)式58后面通過語句重新排序；13的范圍內(nèi)使用SL和Cl的分化范圍17201316之后的語句重新排序，范圍2024分別手工編碼，ADIFOR（向前），資產(chǎn)管理公司（前）和資產(chǎn)管理公司（反向）。所觀察到的時間平均OBS時間是由一定數(shù)量的評估，得到的CPU時間跑，看到 4 的細(xì)節(jié)。如果是浮點操作數(shù)，B加載和存儲的號碼，K1，K2分別浮點運算和內(nèi)存訪問進行每周期的數(shù)目，我們計算以下參數(shù)：估計時間時間=max（A /K1，K2B/）周期時間，失敗時間= A / K1 周期時間和LS時間= BK2 周期時間。超10處理器可以執(zhí)行2浮點運算每循環(huán)4個周期的延遲和1負(fù)載或1商店2周期的延遲，和采用順序執(zhí)行指令的 10。該r12000可以執(zhí)行2個浮點操作每個周期，1的內(nèi)存訪問（存?。┒加?個周期的延遲，并采用亂序執(zhí)行指令的 7，10。圖1顯示了執(zhí)行時間的存儲器存取時間的控制，這正好與估計時間。所觀察到的時間的估計時間乘以延遲的近似存儲器存取操作。此外，該語句重新排序進行更好的減少數(shù)內(nèi)存訪問。圖2是從一個小的測試案例的結(jié)果，適合于L1高速緩存。雖然，我們觀察到的內(nèi)存訪問中發(fā)揮了重要的作用，但更重要的是，減少了浮點操作影響了整體的執(zhí)行時間和所觀察到的時間是密切的floptime近似乘以浮點操作延遲。4語句重新排序方案生成的代碼計算雅可比矩陣J，包括F的原代碼，以及報表計算當(dāng)?shù)氐难苌?，和C的nonzeros在消除。但它的大部分是消除報表，其中的造型和=cikckj或CIJ=需要+cikckj。語句可以重新以任何方式方面的依賴關(guān)系，即如果表S1 S2取決于聲明，那么必須先于S1 S2。這個定義的雅可比矩陣編碼的數(shù)據(jù)依賴圖G=（V 0，V0，E0）在聲明的集合。在 4，16 ，我們使用一個語句重新排序算法（SRA）使用深度優(yōu)先遍歷G0每個S1 2 V 0，試圖將S2，S1的依賴，接近S1。這是希望這將速度了代碼，讓編譯器執(zhí)行更好的寄存器使用以來，在我們的測試情況下，高速緩存未命中了顯示沒有問題 16 。的好處是片狀的，可能是因為沒有考慮到的指令級并行性（ILP）現(xiàn)代基于緩存的機器和某些指令的潛伏期。在這項工作中，我們計劃利用ILP的SRA優(yōu)先的某些聲明通過排序函數(shù)。編譯器的優(yōu)化工作的一個依賴圖，其頂點的機器代碼指令指令。我們不知道我們的工作指令G0。我們將使用相結(jié)合的寄存器和指令調(diào)度方法用于例如 12 和 10，14 排序函數(shù)的思想。我們的排名函數(shù)使用該操作的假設(shè)，它有更多的接班人，這是坐落在一個較長的路徑應(yīng)優(yōu)先，有可能執(zhí)行以最小的延遲和影響的其他更多的操作附表。頂點的S級2 V0是一個高度加權(quán)求和（S），最長路徑的，和成功的（S）的接班人，我們計劃實施這種重新排序方案和評估其影響數(shù)在計算雅可比矩陣的頂點消除算法的整體性能。5結(jié)論和進一步的工作我們提出了一個詳細(xì)的性能分析的雅可比計算使用的頂點消除算法。我們已經(jīng)表明，在高速緩存中的數(shù)據(jù)執(zhí)行時間的浮點數(shù)相關(guān)操作而從高速緩存中的數(shù)據(jù)是與記憶相關(guān)的訪問。我們指出，雖然頂點消除算法減少了浮點操作數(shù)，應(yīng)該加上指令調(diào)度算法，使現(xiàn)代處理器的指令級并行性開發(fā)，減少存儲器訪問和最大化性能。我們描述了一個基于排序函數(shù)語句重新排序方案。我們計劃實施和測試它使用中型問題上的RISC處理器。致謝這項工作是由格蘭特GR / r21882 EPSRC和英國國防部的支持下。作者希望感謝教授J.K.瑞德啟發(fā)的討論和對工作的意見。參考文獻(xiàn) 1 p. amestoy，T.戴維斯，達(dá)夫，I.。一個近似最小度排序算法。暹羅J.矩陣應(yīng)用。，17（4）：886905，1996。2C. H.比肖夫，A.卡爾，該頁，和A.莫爾。ADIFOR2：自動分化FORTRAN77個程序。計算科學(xué)與工程，3（3）：1832，1996。3C.伯恩斯坦，梅格斯，米勒和G.。并行和填寫嵌套夾層之間的權(quán)衡。在SpaA 99。ACM，1999。 4 美國四，M. tadjouddine，J.普萊斯，J.瑞德。雅可比代碼源轉(zhuǎn)換生成頂點的消除可以手工編碼的效率。ACM跨。數(shù)學(xué)上的。軟，出現(xiàn)2004。 5 J.喬治和J.劉。一種自動嵌套夾層算法對不規(guī)則的有限元問題。暹羅的數(shù)值分析15:345雜志，363，1978。 6 卡明斯基R.捷林和T.。食譜伴隨碼的構(gòu)造。acmtrans。onmath。軟。，24（4）：437474，十二月1998。 7 美國goedecker hoisie和A.。數(shù)值型碼的性能優(yōu)化。暹羅費城，2001。8A. Griewank。評價衍生物：原理和算法分化技術(shù)。數(shù)19在前沿應(yīng)用。數(shù)學(xué)。暹羅，費城，賓夕法尼亞大學(xué)，2000。 9 W.格洛普，D. Kaushik，D.凱斯，和B史密斯。提高稀疏矩陣向量的性能乘法阻斷。技術(shù)報告，MCS劃分，阿貢國家實驗室。10C. hardnett，R.拉巴，K.帕萊姆和黃，W.。緩存敏感指令調(diào)度。技術(shù)報告crest-tr-01-003，git-cc-01-15，在嵌入式系統(tǒng)與技術(shù)研究中心，六月2001。 11 h. Markowitz。的逆淘汰形式及其應(yīng)用。管理科學(xué)，3:257269，1957。 12 r.莫瓦尼，K.帕萊姆，訴薩卡，和美國reyen。結(jié)合寄存器分配和指令調(diào)度：（技術(shù)總結(jié)）。技術(shù)報告TR 698，報研究所，七月1995。 13 美國諾曼。高效的計算的雅可比矩陣的鏈規(guī)則優(yōu)化的應(yīng)用計算圖。博士學(xué)位論文，德累斯頓技術(shù)大學(xué)，六月1999。 14 k.帕萊姆和B西蒙斯。調(diào)度時間關(guān)鍵指令RISC機器。ACMtoplas