一種高效高質(zhì)量的FPGA技術(shù)映射算法.pdf

1、技術(shù)映射的任務(wù)是將一個(gè)電路的門級網(wǎng)表轉(zhuǎn)換成采用FPGA芯片內(nèi)部LUT實(shí)現(xiàn)的LUT網(wǎng)表，它是FPGA CAD流程中的重要一環(huán)，包含邏輯優(yōu)化與結(jié)構(gòu)優(yōu)化兩個(gè)部分。邏輯優(yōu)化的主要目標(biāo)是對電路進(jìn)行分解，使得電路能夠滿足FPGA芯片內(nèi)部LUT k-輸入的要求；結(jié)構(gòu)優(yōu)化的主要目標(biāo)是將電路轉(zhuǎn)換為 LUT網(wǎng)絡(luò)。目前，現(xiàn)有的邏輯優(yōu)化算法運(yùn)行效率并不理想，而現(xiàn)有的結(jié)構(gòu)優(yōu)化算法在電路延時(shí)、面積以及算法運(yùn)行效率方面仍有提高的空間。
　　本文針對技術(shù)映射的兩

2、個(gè)部分，分別提出了相應(yīng)的改進(jìn)算法。邏輯優(yōu)化部分，本文以ROBDD為基礎(chǔ)，對規(guī)模不同的電路采用不同的ROBDD表示方法：對于大規(guī)模電路，為了減少內(nèi)存的開銷，保證算法正常執(zhí)行，選擇Local ROBDD對電路進(jìn)行描述，對于小規(guī)模電路，選擇Global ROBDD對電路進(jìn)行描述，提高邏輯優(yōu)化的效率。在電路表示完成后，利用ROBDD中的域節(jié)點(diǎn)以及域操作對電路進(jìn)行分解，使得電路能夠滿足FPGA內(nèi)部LUT k-輸入的要求。結(jié)構(gòu)優(yōu)化部分，提出了一種以

3、延時(shí)、面積和效率為優(yōu)化目標(biāo)的基于迭代的啟發(fā)式結(jié)構(gòu)優(yōu)化算法，主要包含三部分：劃分產(chǎn)生、劃分選擇和LUT覆蓋。劃分產(chǎn)生通過動(dòng)態(tài)規(guī)劃的思想，快速為電路中的每一個(gè)節(jié)點(diǎn)產(chǎn)生所有k-可行劃分，劃分的選擇是一個(gè)迭代的過程，它包含向前遍歷和向后遍歷，向前遍歷根據(jù)優(yōu)化目標(biāo)為每一個(gè)節(jié)點(diǎn)選擇最優(yōu)劃分，而向后遍歷則選擇合適的節(jié)點(diǎn)作為LUT的根節(jié)點(diǎn)，通過多次向前遍歷向與后遍歷的迭代，最終選出最優(yōu)的劃分集。LUT覆蓋則是采用劃分選擇的結(jié)果，利用FPGA芯片內(nèi)部的L