本文選題：蒙特卡羅計算　切入點：FPGA加速　出處：《國防科學技術(shù)大學》2013年博士論文　論文類型：學位論文

【摘要】：蒙特卡羅模擬是一種廣泛應用于分子物理學、金融工程學和生物醫(yī)學等領(lǐng)域求解科學計算問題的重要方法。隨著科學技術(shù)的發(fā)展,運用蒙特卡羅方法解決實際問題的復雜性不斷增大,導致對計算設備運算能力的需求也在不斷地增強。開發(fā)新的計算模式以實現(xiàn)對蒙特卡羅模擬進行加速已成為現(xiàn)代科學計算急需解決的重要問題。近年來,FPGA芯片以其可重構(gòu)、支持細粒度并行、高性能、低功耗等優(yōu)勢,已成為理想的計算加速平臺。然而,FPGA加速蒙特卡羅計算還面臨著算法特征多樣性、算法并行結(jié)構(gòu)設計困難、硬件結(jié)構(gòu)優(yōu)化復雜等挑戰(zhàn)。已有的蒙特卡羅加速結(jié)構(gòu)存在消耗FPGA資源過大、并行計算結(jié)構(gòu)具有局限性、計算結(jié)構(gòu)缺乏通用性等缺陷。為了應對這些問題與挑戰(zhàn),本文對蒙特卡羅計算的FPGA加速技術(shù)進行了深入地研究。集中解決了實現(xiàn)加速的幾項關(guān)鍵技術(shù),并在此基礎(chǔ)上實現(xiàn)了對金融衍生產(chǎn)品定價模型的計算加速。本文的主要工作和創(chuàng)新點如下:1.提出了基于FPGA的長周期均勻分布隨機數(shù)加速結(jié)構(gòu)。本文在學術(shù)界首次提出基于WELL算法的均勻分布隨機數(shù)FPGA加速結(jié)構(gòu)。該結(jié)構(gòu)能獲得1拍產(chǎn)生1個隨機數(shù)的吞吐率,并具有高質(zhì)量、長周期、高性能、低硬件消耗等特點。本文針對WELL算法的訪存特性,提出了一種6讀/2寫多端口RAM結(jié)構(gòu)。該RAM采用Register-BRAMs混合架構(gòu),在充分利用FPGA內(nèi)嵌BRAM存儲器特性的基礎(chǔ)上,僅需消耗1個32位寄存器和2個BRAMs即可支持6讀/2寫的并行訪問,打破了BRAM最多支持雙端口讀寫的限制,是整個系統(tǒng)獲得目標吞吐率的關(guān)鍵部件。實驗結(jié)果表明,本文所設計的隨機數(shù)加速結(jié)構(gòu)優(yōu)于相關(guān)工作和通用處理器的軟件實現(xiàn)。2.設計并實現(xiàn)了基于FPGA的浮點轉(zhuǎn)定點自動位寬優(yōu)化軟件工具SATRANS。SATRANS能夠?qū)⒚枋鏊惴ǖ母↑c程序轉(zhuǎn)換成定點程序并進行自動位寬優(yōu)化。采用模擬退火算法作為位寬搜索引擎,相對于傳統(tǒng)的貪心搜索算法能夠獲得更加優(yōu)化的搜索結(jié)果。并能夠獲得一系列滿足精度要求的位寬組合,使得設計者能夠在性能、面積開銷等設計因素間權(quán)衡,以選擇最合適的結(jié)果應用到系統(tǒng)設計中。為了彌補模擬退火搜索迭代次數(shù)多,速度慢的缺點,SATRANS以C語言的無符號長整型表示定點操作數(shù),并用相應的加減乘、移位、掩碼等基本操作來模擬定點運算。相對于gfix,fi等定點程序包獲得了巨大的性能提升。將SATRANS應用到IIR系統(tǒng)、高斯隨機數(shù)發(fā)生器以及金融工程加速系統(tǒng)的設計中,取得了較好的效果。3.提出了基于FPGA的長周期高斯分布隨機數(shù)發(fā)生框架。本文在充分研究各種高斯隨機數(shù)生成算法共性的基礎(chǔ)上,提出了基于FPGA的高斯隨機數(shù)發(fā)生器的通用設計流程,并基于該設計流程對Box Muller和Monty Python兩種高斯隨機數(shù)生成算法進行了FPGA設計。對于Box Muller算法,采用分段多項式擬合法對基本函數(shù)運算進行硬件擬合,并采用SATRANS對結(jié)構(gòu)進行位寬優(yōu)化。實驗結(jié)果表明,該結(jié)構(gòu)能獲得1拍產(chǎn)生2個隨機數(shù)的吞吐率,相對于通用處理獲得了12.5倍的性能提升,在周期、性能/面積消耗比等指標上均優(yōu)于相關(guān)工作。在性能和面積消耗上均優(yōu)于浮點實現(xiàn)。對于Monty Python算法,定制了一套高效的四段并行結(jié)構(gòu),能將處理高斯隨機數(shù)PDF中主路徑的全流水部件和處理Tail區(qū)域的專用迭代部件并行執(zhí)行,有效地隱藏了循環(huán)迭代對高斯系統(tǒng)性能的影響。實驗結(jié)果表明,該結(jié)構(gòu)能獲得接近1拍產(chǎn)生1個隨機數(shù)的吞吐率,相對于通用處理器獲得了24.8倍的性能提升,在周期和性能上優(yōu)于相關(guān)工作。在性能和面積消耗上均要優(yōu)于相應的浮點實現(xiàn)。4.提出了軟硬件協(xié)同的并行均勻分布隨機數(shù)生成框架。其中軟件部分基于Fast Jump Ahead技術(shù)產(chǎn)生各子路隨機數(shù)發(fā)生器的初始狀態(tài),以保證各子序列相互獨立。在軟件的支持下,硬件部分僅需簡單復制單隨機數(shù)發(fā)生器即可實現(xiàn)。為了提高軟件部分的計算效率,本文提出了一種高效的矩陣特征多項式計算算法,能夠快速計算出任意F2-Linear隨機數(shù)算法狀態(tài)矩陣的特征多項式。實驗結(jié)果表明,該并行隨機數(shù)發(fā)生框架能夠產(chǎn)生任意路相互獨立的均勻分布隨機數(shù)序列,并且吞吐率和資源消耗均隨著并行度的增加呈線性增長。以WELL19937算法為例在Virtex 5上實現(xiàn)并行框架,最多能集成149個隨機數(shù)發(fā)生器。相對于同等工藝的CPU和GPU,吞吐率分別提高了9.8倍和2.5倍,效能(吞吐率/功耗)分別獲得了194.9倍和21.1倍的提升。所產(chǎn)生的并行隨機數(shù)序列通過了標準統(tǒng)計測試集對其相關(guān)性的檢測,并成功應用到一個真實的蒙特卡羅模擬環(huán)境:π的蒙特卡羅模擬。本文還基于并行均勻分布隨機數(shù)發(fā)生框架,提出了并行高斯分布隨機數(shù)生成框架。該框架同樣能夠產(chǎn)生任意路相互獨立的高斯分布隨機數(shù)序列,具有很好的可擴展性,且在性能和效能上均優(yōu)于同等工藝的CPU和GPU實現(xiàn)。5.提出了金融衍生產(chǎn)品定價模型的并行FPGA加速結(jié)構(gòu)。本文在前幾項研究工作的基礎(chǔ)上,首次提出了基于Drageseth模型的并行CDS(信用違約互換)加速結(jié)構(gòu)。在該并行結(jié)構(gòu)中對軟硬件任務劃分,多計算核的任務劃分,多核的協(xié)同計算以及計算結(jié)果的整合等關(guān)鍵技術(shù)進行了詳細的定義。并通過通信延時隱藏等技術(shù)提高整個系統(tǒng)的性能/面積消耗比。實驗結(jié)果表明,該并行結(jié)構(gòu)能產(chǎn)生精確的計算結(jié)果,具有很好的可擴展性。相對于通用處理器的軟件實現(xiàn)獲得了約358倍的性能提升。
[Abstract]:......
【學位授予單位】：國防科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2013
【分類號】：O242.2;TN791

【共引文獻】

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

1 洪俊;芮筱亭;劉軍;陳濤;;散粒體發(fā)射藥床碰撞擠壓過程三維數(shù)值模擬研究[J];兵工學報;2007年03期

2 王海東;張海;;晶粒生長的蒙特卡羅模擬研究進展[J];材料導報;2007年02期

3 代志力;陳浩;黎明;;基于MCNP對CT系統(tǒng)中探測器材料性能的研究[J];CT理論與應用研究;2011年01期

4 楊乃恒,王繼常,劉玉岱;蒙特卡羅法計算渦輪分子泵葉列的傳輸幾率[J];東北工學院學報;1984年01期

5 賈文寶;王仲奇;張本愛;;隨機抽樣中的Alias算法及其改進[J];東北師大學報(自然科學版);2012年01期

6 劉德坤;張宏宇;張麗紅;谷德山;卜香云;董煥;;用MCNP模擬中子煤質(zhì)檢測時外水增加對低位熱值的影響[J];東北師大學報(自然科學版);2012年02期

7 姜世平;芮筱亭;洪俊;王國平;徐浩;;發(fā)射藥床自然堆積模擬[J];彈道學報;2011年02期

8 姜璐;朱海;李松;;水下目標反激光雷達探測隱蔽深度的蒙特卡羅計算[J];彈箭與制導學報;2005年S6期

9 姜璐;朱海;于運治;;基于蒙特卡羅方法的水下目標光學隱蔽性影響因素分析[J];彈箭與制導學報;2006年04期

10 高顯忠;趙偉;侯中喜;;粒子濾波改進算法研究[J];彈箭與制導學報;2009年03期

相關(guān)會議論文 前7條

1 章法強;楊建倫;李正宏;陳法新;;數(shù)值模擬高能中子照相[A];2006全國核材料學術(shù)交流會論文集[C];2006年

2 孫業(yè)勝;陳道南;關(guān)焯;;起重機減速器的可靠度計算[A];中國機械工程學會物料搬運專業(yè)學會第三屆年會論文集[C];1988年

3 鄒樹梁;王建;;鎢和鉛作為γ射線屏蔽材料的性能對比研究[A];中國核科學技術(shù)進展報告（第二卷）——中國核學會2011年學術(shù)年會論文集第5冊（輻射防護分卷、核化工分卷）[C];2011年

4 竇玉玲;王國保;張國光;豐樹強;趙瀟;王新光;;小型D-T中子發(fā)生器慢化體的蒙特卡羅模擬[A];中國核科學技術(shù)進展報告（第二卷）——中國核學會2011年學術(shù)年會論文集第9冊（核醫(yī)學分卷、核技術(shù)工業(yè)應用分卷）[C];2011年

5 許小明;賈向軍;甘霖;;含钚物料中子多重性測量技術(shù)研究[A];中國核學會核化工分會成立三十周年慶祝大會暨全國核化工學術(shù)交流年會會議論文集[C];2010年

6 唐楨;周四春;廖芹;李高峰;魏威;;伽馬射線輻射屏蔽效果實驗的應用研究[A];輻射防護分會2012年學術(shù)年會論文集[C];2012年

7 李虹軼;林源根;許偉;吳昌莉;;提高MCNP γ能譜模擬精度方法分析[A];中國核科學技術(shù)進展報告（第三卷）——中國核學會2013年學術(shù)年會論文集第7冊（核電子學與核探測技術(shù)分卷、脈沖功率技術(shù)及其應用分卷、核聚變與等離子體物理分卷）[C];2013年

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

1 師學明;聚變裂變混合能源堆包層中子學概念研究[D];中國工程物理研究院;2010年

2 馬麗珍;自由空間量子通信中偏振光子傳輸和操控的理論與模擬研究[D];中國海洋大學;2010年

3 劉洋;基于可視中國人體素數(shù)據(jù)的內(nèi)輻射劑量研究[D];華中科技大學;2011年

4 陳波;BaFX成像板的輻射探測特性及其在總α測量中的應用[D];復旦大學;2011年

5 申鳳君;X射線熒光測井關(guān)鍵技術(shù)研究[D];成都理工大學;2011年

6 李吉功;室外時變氣流環(huán)境下機器人氣味源定位[D];天津大學;2010年

7 周日峰;高能X射線工業(yè)CT氣固混合型電子倍增輻射探測器探索研究[D];重慶大學;2011年

8 谷曉忱;并行蒙特卡羅計算硬件加速器的關(guān)鍵技術(shù)研究[D];國防科學技術(shù)大學;2010年

9 龔春葉;面向異構(gòu)體系結(jié)構(gòu)的粒子輸運并行算法研究[D];國防科學技術(shù)大學;2011年

10 尹麗菊;基于GM-APD的光子計數(shù)成像技術(shù)研究[D];南京理工大學;2012年

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

1 余波;慣性約束聚變的中子半影成像診斷系統(tǒng)和非線性重建方法研究[D];中國工程物理研究院;2010年

2 張絢;雙軸閃光照相系統(tǒng)中的散射問題研究[D];中國工程物理研究院;2010年

3 楊佳音;反應堆中子分布與屏蔽設計研究[D];哈爾濱工程大學;2010年

4 史鵬;偏振光子的大氣傳輸及光子與腔—量子點的相互作用[D];中國海洋大學;2010年

5 胡躍波;膠州灣溢油動態(tài)預報模式及可視化研究[D];中國海洋大學;2010年

6 劉文靜;粒子濾波關(guān)鍵技術(shù)及其應用研究[D];河南理工大學;2010年

7 馬維云;鈦酸鍶鋇鐵電陶瓷的電性能研究及其薄膜制備[D];昆明理工大學;2010年

8 答元;MOS器件電離損傷的蒙特卡羅模擬研究[D];西安工業(yè)大學;2011年

9 向張衡;受限于同心圓柱套筒間的半剛性高分子鏈構(gòu)象行為[D];浙江大學;2011年

10 楊海芳;質(zhì)子打薄靶的角度和能量歧離的蒙特卡羅模擬[D];吉林大學;2011年

，

本文編號：1634831