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

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

【共引文獻(xiàn)】

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

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

2 王海東;張海;;晶粒生長(zhǎng)的蒙特卡羅模擬研究進(jìn)展[J];材料導(dǎo)報(bào);2007年02期

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

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

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

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

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

8 姜璐;朱海;李松;;水下目標(biāo)反激光雷達(dá)探測(cè)隱蔽深度的蒙特卡羅計(jì)算[J];彈箭與制導(dǎo)學(xué)報(bào);2005年S6期

9 姜璐;朱海;于運(yùn)治;;基于蒙特卡羅方法的水下目標(biāo)光學(xué)隱蔽性影響因素分析[J];彈箭與制導(dǎo)學(xué)報(bào);2006年04期

10 高顯忠;趙偉;侯中喜;;粒子濾波改進(jìn)算法研究[J];彈箭與制導(dǎo)學(xué)報(bào);2009年03期

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

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

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

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

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

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

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

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

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

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

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

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

4 陳波;BaFX成像板的輻射探測(cè)特性及其在總α測(cè)量中的應(yīng)用[D];復(fù)旦大學(xué);2011年

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

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

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

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

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

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

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

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

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

3 楊佳音;反應(yīng)堆中子分布與屏蔽設(shè)計(jì)研究[D];哈爾濱工程大學(xué);2010年

4 史鵬;偏振光子的大氣傳輸及光子與腔—量子點(diǎn)的相互作用[D];中國(guó)海洋大學(xué);2010年

5 胡躍波;膠州灣溢油動(dòng)態(tài)預(yù)報(bào)模式及可視化研究[D];中國(guó)海洋大學(xué);2010年

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

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

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

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

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

，

本文編號(hào)：1634831