基于LUT結(jié)構(gòu)的FPGA的工藝映射算法的研究.pdf

1、隨著我國(guó)的信息產(chǎn)業(yè)的發(fā)展，設(shè)計(jì)開發(fā)具有自主知識(shí)產(chǎn)權(quán)的集成電路成為一項(xiàng)基礎(chǔ)性的工作。FPGA在電子設(shè)計(jì)領(lǐng)域占有越來(lái)越重要的作用，但我國(guó)目前采用的FPGA芯片大多從國(guó)外進(jìn)口。設(shè)計(jì)開發(fā)具有自主知識(shí)產(chǎn)權(quán)的FPGA芯片具有及其重要的意義?；贚UT結(jié)構(gòu)的FPGA的工藝映射算法在EDA開發(fā)環(huán)境的設(shè)計(jì)中占有很重要的位置。 本論文正是針對(duì)上述的問題，以基于LUT結(jié)構(gòu)的FPGA的工藝映射算法為研究對(duì)象，全面介紹了邏輯分解、深度優(yōu)化算法、面積優(yōu)化算

2、法等，對(duì)諸多方面作了創(chuàng)新性和探索性研究。主要內(nèi)容為： 1.詳細(xì)介紹了工藝映射算法及其技術(shù)。詳細(xì)介紹了布爾函數(shù)的邏輯分解的一般分解原理，詳細(xì)介紹了面積優(yōu)化、深度優(yōu)化、面積和深度同時(shí)優(yōu)化以及功率優(yōu)化的基本模型和技術(shù)。 2.給出了面積優(yōu)化算法的NP完全性更為簡(jiǎn)潔的證明。原有的證明是利用3-SAT問題規(guī)約到面積優(yōu)化問題，但是要分別對(duì)K≥5、K=4和K=3的情況分別討論，證明過程比較復(fù)雜。本論文利用最小頂點(diǎn)覆蓋問題規(guī)約到面積優(yōu)化問

3、題，只需討論K≥3一種情況，證明過程很簡(jiǎn)略。 3.將現(xiàn)代組合優(yōu)化算法模擬退火算法應(yīng)用于面積優(yōu)化算法中，取得了較好的效果。本論文利用點(diǎn)可見方法對(duì)映射方案進(jìn)行編碼，利用局部的點(diǎn)反轉(zhuǎn)技術(shù)進(jìn)行降溫過程中的平衡處理，獲得時(shí)間復(fù)雜度較小的情況下比較好的映射效果。 4.自主實(shí)現(xiàn)了FlowMap算法，利用布爾網(wǎng)絡(luò)的特點(diǎn)，采用新的標(biāo)號(hào)法求得網(wǎng)絡(luò)的最大流。本論文利用標(biāo)號(hào)法尋求起始點(diǎn)到終點(diǎn)的通路的方法，來(lái)求得布爾網(wǎng)絡(luò)的最大流，使得圖的變換減少

4、，時(shí)間復(fù)雜度也隨之減少。 5.將遺傳算法應(yīng)用于深度和面積同時(shí)優(yōu)化的算法中，取得了較好的效果。在本論文中，深度和面積優(yōu)化的平衡，在計(jì)算適應(yīng)度時(shí)用加權(quán)因子予以反映。利用遺傳算法，深度和面積優(yōu)化可以在一個(gè)階段中同時(shí)考慮，實(shí)驗(yàn)結(jié)果表明效果較好。 6.研究了深度優(yōu)化算法的并行性，提出了深度優(yōu)化的并行算法。節(jié)點(diǎn)標(biāo)號(hào)的計(jì)算是具有局部性的，因此如果節(jié)點(diǎn)沒有前驅(qū)后繼關(guān)系，標(biāo)號(hào)計(jì)算是相互不影響的。所以，可以利用這一特性進(jìn)行節(jié)點(diǎn)標(biāo)號(hào)的并行計(jì)算