針對FPGA復(fù)雜可編程邏輯單元的快速布爾匹配方法研究.pdf

1、自上世紀(jì)80年代第一塊現(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)芯片問世以來，F(xiàn)PGA憑借其開發(fā)周期短、非重復(fù)性工程(Non-RecurringEngineering，NRE)費(fèi)用低等特點(diǎn)，在諸如產(chǎn)品原型設(shè)計(jì)、中低規(guī)模產(chǎn)量電路系統(tǒng)實(shí)現(xiàn)等應(yīng)用領(lǐng)域中，牢牢占據(jù)市場份額。進(jìn)入到21世紀(jì)，半導(dǎo)體工業(yè)遇到新的問題。一方面隨著工藝尺寸降低，芯片的生產(chǎn)制造成本持續(xù)上升，導(dǎo)致專用集成電路的開發(fā)成本居高不下；

2、另一方面功耗問題限制了電路頻率的提高，使得集成電路向多核結(jié)構(gòu)發(fā)展。在眾多解決方案中，F(xiàn)PGA具有天然的低開發(fā)成本、高度并行處理架構(gòu)的優(yōu)勢，因而受到越來越多的關(guān)注和青睞，開始進(jìn)入到通訊、網(wǎng)絡(luò)、高性能計(jì)算等應(yīng)用領(lǐng)域。
　　布爾匹配是現(xiàn)場可編程門陣列設(shè)計(jì)自動(dòng)化流程中的一個(gè)核心子問題，主要解決可編程邏輯單元結(jié)構(gòu)是否能夠?qū)崿F(xiàn)給定的布爾函數(shù)的問題，在工藝映射、邏輯再綜合及新型結(jié)構(gòu)評估等方面有著廣泛應(yīng)用。為了以較小的面積代價(jià)靈活地實(shí)現(xiàn)更多的邏輯

3、功能，可編程邏輯單元結(jié)構(gòu)經(jīng)歷了由簡單到復(fù)雜、由同質(zhì)向異質(zhì)結(jié)構(gòu)發(fā)展的過程。一個(gè)理想的針對可編程邏輯單元的布爾匹配方法需要兼顧靈活性、伸縮性、速度與空間開銷等多個(gè)方面。在目前現(xiàn)有的匹配方法中，基于布爾可滿足性問題的匹配方法具有最佳靈活性，但卻由于其高計(jì)算復(fù)雜度而難以應(yīng)用到復(fù)雜大規(guī)?？删幊踢壿媶卧小Ｔ诒菊撐闹?，在布爾可滿足性問題匹配方法的基礎(chǔ)上，提出兩種快速且不失靈活性的布爾匹配方法。
　　針對基于布爾可滿足性問題的匹配方法在可實(shí)現(xiàn)函

4、數(shù)與不可實(shí)現(xiàn)函數(shù)運(yùn)行時(shí)間上的巨大差異，本文提出通過構(gòu)建匹配查找表的方法在匹配初期階段快速排除大部分的不可實(shí)現(xiàn)函數(shù)，以提高匹配速度。主要貢獻(xiàn)在于：(1)利用不同電路中普遍存在的局部相似性，提出采用電路訓(xùn)練的方法來提取有效數(shù)據(jù)，減小數(shù)據(jù)挖掘工作量；(2)提出采用布隆過濾器(Bloom Filter)數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)構(gòu)建匹配查找表，以高效的方式保存經(jīng)過訓(xùn)練的匹配結(jié)果，使得查找表能夠安置于目前主流臺(tái)式電腦的內(nèi)存中；(3)提出兩種過濾策略，用戶可以

5、根據(jù)需要進(jìn)行匹配時(shí)間與匹配質(zhì)量兩方面的折衷。實(shí)驗(yàn)結(jié)果表明，應(yīng)用于電路邏輯再綜合，本文所提出的方法比最新的基于布爾可滿足性問題的匹配方法快80倍，而電路而積僅增加0.5％。
　　隨著云計(jì)算時(shí)代的來臨，軟件即服務(wù)(Software as a Service，SsaS)這種獨(dú)特的軟件開發(fā)模型給信息產(chǎn)業(yè)的各方面都帶來了深遠(yuǎn)的影響。本論文的第二部分，以針對復(fù)雜可編程邏輯單元的布爾匹配問題作為一個(gè)具體實(shí)例，分析SaaS給集成電路設(shè)計(jì)自動(dòng)化領(lǐng)域