一種高效高質量的FPGA技術映射算法.pdf

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

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

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