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

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

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

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

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

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