【摘要】：蒙特卡羅計算在計算物理學(如粒子輸運計算、量子熱力學計算、空氣動力學計算等)、金融工程學以及宏觀經(jīng)濟學等領(lǐng)域都有重要的應(yīng)用。但是,隨著計算模型的日益復(fù)雜以及計算精度的日益提高,蒙特卡羅計算需要完成的計算量也在與日俱增。在金融學等對實時性要求比較高的應(yīng)用中,對蒙特卡羅計算進行加速已經(jīng)成為急需解決的重要問題。 相對于其他計算加速方式,基于FPGA的蒙特卡羅計算加速在加速效果、功耗以及成本等各方面都具有更出色的性能表現(xiàn)和發(fā)展前景。目前,相關(guān)課題組對這方面的研究大都局限于某些特定算法的硬件實現(xiàn)過程,對于許多基礎(chǔ)性的關(guān)鍵技術(shù)問題并沒有做深入的研究。本文的工作以提高硬件設(shè)計的可重構(gòu)性、減少硬件資源消耗、提高硬件計算的并行性和加速性能為研究目標,對隨機數(shù)產(chǎn)生、硬件加速器的并行化設(shè)計以及操作數(shù)位寬的選取等關(guān)鍵技術(shù)進行了深入的研究,主要取得了以下幾方面的研究成果: 1、為解決基于FPGA的均勻分布隨機數(shù)產(chǎn)生問題,提出了CTRNG(Combined Tausworthe Random Number Generator)硬件結(jié)構(gòu)。相對于其他基于FPGA的均勻分布隨機數(shù)生成器,CTRNG在工作速度、硬件資源消耗以及硬件資源利用率等方面都具有更好的性能表現(xiàn)。更重要的是,CTRNG所產(chǎn)生隨機數(shù)的周期和位寬具有可重構(gòu)性。在硬件設(shè)計時,可以根據(jù)蒙特卡羅計算硬件加速器在采樣次數(shù)以及計算精度等方面的實際需求,對硬件設(shè)計結(jié)果進行設(shè)計重構(gòu),以達到進一步提高其加速性能的目的; 2、為解決基于FPGA的高斯隨機數(shù)產(chǎn)生問題,提出了BMGRNG(Box Muller Gaussian Random Number Generator)硬件結(jié)構(gòu)及其設(shè)計流程。與已有研究不同的是,本文的研究基于對邊沿效應(yīng)和操作數(shù)位寬的分析結(jié)果,建立了蒙特卡羅采樣次數(shù)、均勻分布隨機數(shù)位寬、高斯隨機數(shù)的數(shù)值輸出范圍、高斯隨機數(shù)精度以及BMGRMG中各操作數(shù)位寬之間的相互約束關(guān)系。根據(jù)這些約束關(guān)系,可以運用蒙特卡羅采樣次數(shù)以及計算精度等加速器整體設(shè)計指標對BMGRNG的硬件設(shè)計進行優(yōu)化,從而使得BMGRNG的硬件設(shè)計結(jié)果可以更緊密地與硬件加速器的整體設(shè)計需求相結(jié)合,以達到進一步完善硬件設(shè)計、提升計算性能的目的; 3、為解決基于FPGA的并行隨機數(shù)產(chǎn)生問題,提出了MPRNG(Massively Parallel Random Number Generator)硬件結(jié)構(gòu)。MPRNG結(jié)構(gòu)將參數(shù)配置法和跳變法的優(yōu)勢結(jié)合到一起,可以滿足蒙特卡羅計算對大規(guī)模并行隨機數(shù)產(chǎn)生的需求。相對于其他并行隨機數(shù)生成器,MPRNG在硬件資源消耗、工作速度以及并行化程度等方面都具有更好的性能表現(xiàn)。而且,MPRNG所產(chǎn)生隨機數(shù)的周期和位寬也具有可重構(gòu)性,可以根據(jù)蒙特卡羅計算硬件加速器在并行路數(shù)、采樣次數(shù)以及計算精度等方面的實際需求,對硬件設(shè)計進行重新配置,以達到進一步提高其加速性能的目的; 4、為解決操作數(shù)位寬選擇的問題,提出了“最值分析法”和“完備的誤差分析法”來確定操作數(shù)的整數(shù)部分和小數(shù)部分位寬。這兩種方法通過對硬件結(jié)構(gòu)的進一步劃分,運用貪心算法的思想,采用逐級分析的方式,將多個操作數(shù)的位寬組合優(yōu)化問題轉(zhuǎn)化為2個以下操作數(shù)的位寬優(yōu)化問題。從而,可以通過簡單的窮舉方式計算出最優(yōu)位寬結(jié)果,避免了復(fù)雜的組合最優(yōu)化算法的計算過程,降低了操作數(shù)位寬選取過程的復(fù)雜程度和實現(xiàn)難度,加速了硬件加速器的設(shè)計進程; 5、為滿足金融學領(lǐng)域?qū)τ嬎慵铀俚男枨?提出了一種并行蒙特卡羅金融計算硬件加速器的實現(xiàn)架構(gòu)。在該架構(gòu)中對多個蒙特卡羅計算模塊的組織、數(shù)據(jù)傳輸、控制過程以及軟/硬件部分的任務(wù)劃分等方面都進行了詳細的定義。對其中的計算結(jié)果預(yù)處理部件,提出了一種全新的設(shè)計結(jié)構(gòu),解決了并行計算所引入的大規(guī)模計算結(jié)果的處理問題。結(jié)合上述的關(guān)鍵技術(shù)解決辦法,并以Black Scholes和GARCH算法為實例,應(yīng)用該并行架構(gòu)在MAXWELL可重構(gòu)超級計算機上實現(xiàn)了320個硬件模塊的并行計算,獲得了很好的加速效果。 實驗表明,本文提出的關(guān)鍵技術(shù)解決辦法在并行蒙特卡羅計算硬件加速器的設(shè)計中發(fā)揮了重要的作用。本文的研究結(jié)果為基于FPGA的蒙特卡羅計算硬件加速器的發(fā)展奠定了基礎(chǔ)。
【學位授予單位】：國防科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2010
【分類號】：O242.2;TP303
【圖文】：

圖 1. 4 FPGA 的結(jié)構(gòu)組成計算加速的主要優(yōu)勢有：算所獲得的計算加速比高：相對于 CPU現(xiàn)的單個硬件計算模塊所獲得的計算加速倍。這是基于 FPGA 的計算加速方式優(yōu)于的最大特點�；诙� CPU 的計算是以指特卡羅這種計算來說，它不可能做到每個時就是說，完成一次蒙特卡羅采樣計算，需要行時間。而 GPU 中的計算單元 SP 雖然采次上的任務(wù)分配仍然采用的是指令流的形式期給出一個蒙特卡羅采樣計算結(jié)果。但是 形式，硬件實現(xiàn)結(jié)果可以保證每個時鐘周果。所以，雖然 FPGA 上硬件的運行周期但是其單個硬核的計算加速比卻是單個 C；

國防科學技術(shù)大學研究生院博士學位論文1 所示硬件結(jié)構(gòu)中所有操作數(shù)的小數(shù)部分位寬。.6 均勻分布隨機數(shù)位寬 L 的選取——邊沿效是指由于算法本身的局限性導(dǎo)致小概率事件無法出現(xiàn)法來說，在均勻分布隨機數(shù)位寬確定的情況下，其產(chǎn)生固定的。在前面使用最值分析法選取操作數(shù)整數(shù)部分： √ 。這就是說，當均勻分布隨機數(shù)位高斯隨機數(shù)的樣本個數(shù)是多少，Box Muller 算法，√ ）內(nèi)產(chǎn)生高斯隨機數(shù)。那么，邊沿不利的影響，或者說什么情況下才回對計算結(jié)果產(chǎn)生問題，首先需要分析清楚高斯分布的概率密度函數(shù)。

第 85 頁圖 4. 6 不同 L 對應(yīng)的高斯分布隨機數(shù)的 PDF從圖 4. 6 中的實驗結(jié)果可見，當位寬 L 比較小時，所得到的 PDF 曲線基接受的。當 L 逐漸增加時，所得到的 PDF 曲線也就越來越接近理論結(jié)果L 決定了均勻分布隨機數(shù)可能取到的樣本值，如果可能取到的樣本值過少之對應(yīng)的高斯分布隨機數(shù)的樣本值也會越少，從而導(dǎo)致所產(chǎn)生的隨機數(shù)高斯分布的特性。因此，通過上述分析以及圖 4. 6 中的實驗結(jié)果可以得在設(shè)計高斯隨機數(shù)生成器時，一定要將均勻分布隨機數(shù)的位寬 L 作為設(shè)一來約束設(shè)計過程。不同的 L 對應(yīng)的邊沿效應(yīng)情況以下實驗的目的是為了驗證 4.6 小節(jié)中所提出的公式 4.56 的有效性和正確驗中，選取了 L=8，L=16 和 L=32 三種位寬情況，采樣次數(shù) N 選取了 N=1

【引證文獻】

相關(guān)期刊論文 前2條

1 石琳琦;趙辛宇;吳望塵;;基于FPGA的并行蒙特卡洛計算加速器的設(shè)計與實現(xiàn)[J];數(shù)字技術(shù)與應(yīng)用;2013年05期

2 秦帆;李建波;林皋;朱秀云;;核電樓層譜不確定性分析的并行算法研究[J];水電能源科學;2014年09期

相關(guān)博士學位論文 前1條

1 韓靜茹;三維蒙特卡羅—離散縱標雙向耦合屏蔽計算方法研究[D];華北電力大學;2012年

相關(guān)碩士學位論文 前3條

1 伍盛菲;面向蒙特卡羅計算的隨機數(shù)生成FPGA加速器的研究與實現(xiàn)[D];上海交通大學;2013年

2 徐新才;基于FPGA的高斯隨機數(shù)發(fā)生器的設(shè)計與實現(xiàn)[D];華南理工大學;2013年

3 章駿;DPM程序并行化及在調(diào)強放射治療計劃系統(tǒng)應(yīng)用研究[D];中國科學技術(shù)大學;2014年

本文編號：2795912