多GPU環(huán)境下三點相關(guān)函數(shù)算法研究.pdf

1、多GPU環(huán)境下三點相關(guān)函數(shù)環(huán)境下三點相關(guān)函數(shù)算法研究算法研究ResearchofThreePointCrelationFunctionAlgithminmultiGPUEnvironment學科專業(yè)：計算機科學與技術(shù)研究生：楊沐津指導教師：孫濟洲教授天津大學計算機科學與技術(shù)學院二零一二年十一月摘要N點相關(guān)函數(shù)在星系分布的研究上有重要的意義，是宇宙學模擬中的基本問題。但是樸素解法的計算復雜度卻隨著點集的擴大而呈點相關(guān)數(shù)的次方增長，雖然有基

2、于KDTree等的相關(guān)優(yōu)化算法，但是其復雜度也與點集中的點數(shù)相關(guān)，處理大規(guī)模點集時性能也難以滿足要求。一種基于遞歸卷積的優(yōu)化算法，可以求得近似解，而為了取得較高的計算精度，則要擴大計算矩陣的規(guī)模，這同樣需要解決相應(yīng)的性能問題。本文對解決遞歸卷積算法在解三點相關(guān)函數(shù)所存在的性能問題、計算精度問題、以及二者之間的折衷問題進行研究和分析。本文首先使用宇宙學模擬中的真實數(shù)據(jù)分析原始算法在不同的矩陣規(guī)模下的計算性能問題和計算精度問題。以此入手，提

3、出相應(yīng)的解決方案，即通過擴大矩陣規(guī)模提升相應(yīng)的計算精度，而另一方面利用多GPU解決隨之帶來的性能問題。對于算法并行優(yōu)化，首先將算法簡單遷移到單顆GPU上運行，分析對比不同參數(shù)下的性能變化。其次，分析改進后的GPU算法的程序結(jié)構(gòu)，對GPU下的快速傅立葉變換的特性進行分析，調(diào)整快速傅立葉的變換維度和變換尺寸，以此獲得進一步性能優(yōu)化。最后分析多GPU程序運行特點，將優(yōu)化過的單GPU算法進行調(diào)整，設(shè)計并實現(xiàn)出多GPU環(huán)境下的算法，使算法在多GP