復(fù)用器重構(gòu)降低FPGA成本

--- 4.3 均衡

--- 壓縮通過轉(zhuǎn)換2:1復(fù)用器三聯(lián)，能夠減少實(shí)現(xiàn)復(fù)用器總線所需的4-LUT數(shù)量。但是，如果不進(jìn)行復(fù)用器樹重構(gòu)，有些結(jié)構(gòu)是不可能得到最佳三聯(lián)分組的。例如，無法將圖10中所有的2:1復(fù)用器進(jìn)行分組，這是因?yàn)槊恳环N可能的分組都將會(huì)剩余一個(gè)2:1復(fù)用器而無法處理。

--- 均衡的目的在于通過最少的重構(gòu)得到最佳的壓縮。對(duì)于圖10的例子，可以采用圖11所示的方法，得到兩組2:1復(fù)用器三聯(lián)。

--- 均衡算法由圖12的遞歸定義。由首復(fù)用器開始，算法首先均衡復(fù)用器樹左面和右面數(shù)據(jù)輸入。均衡返回還沒有連接為三聯(lián)的2:1復(fù)用器的數(shù)量。均衡確保形成盡可能多的三聯(lián)，這樣只會(huì)剩余一個(gè)或者兩個(gè)2:1復(fù)用器，甚至沒有剩余。

--- 均衡中的任何階段，都需要對(duì)1～5個(gè)2:1復(fù)用器進(jìn)行均衡（從左側(cè)分支開始最多兩個(gè)，從右側(cè)分支開始為兩個(gè)，還要算上當(dāng)前的2:1復(fù)用器本身）。1或2個(gè)復(fù)用器不會(huì)形成更多的三聯(lián)，而3個(gè)復(fù)用器總是能夠形成三聯(lián)。4或5個(gè)復(fù)用器則需要進(jìn)行重構(gòu)，以免剩余無法處理的復(fù)用器，這種重構(gòu)方法在圖13和圖14中示出。

圖10 復(fù)用器樹次優(yōu)壓縮的例子

圖11 由均衡未完善壓縮


圖12 均衡算法

圖 13重構(gòu)4個(gè)復(fù)用器實(shí)現(xiàn)均衡


圖14 重構(gòu)5個(gè)復(fù)用器實(shí)現(xiàn)均衡

5. 算法總結(jié)

--- 本文引入了復(fù)用器樹總線概念，描述了可用來提高壓縮性能的均衡方法，壓縮以效率更高的4:1復(fù)用器來替代2:1復(fù)用器三聯(lián)。圖15顯示了全部復(fù)用器重構(gòu)算法。

--- 復(fù)用器重構(gòu)算法性能依賴于對(duì)較大復(fù)用器樹總線的識(shí)別。由于復(fù)用器重構(gòu)算法在整個(gè)總線上分擔(dān)控制邏輯，因此，總線越寬，壓縮的效果就越明顯。優(yōu)化會(huì)減小復(fù)用器樹間的相似性，從而減小所尋找的總線寬度，因此在復(fù)用器重構(gòu)之前，應(yīng)盡量避免優(yōu)化。

--- 復(fù)用器重構(gòu)以分解大的復(fù)用器為2:1復(fù)用器開始。設(shè)計(jì)中所有2:1復(fù)用器都用于形成4.1節(jié)所描述的復(fù)用器樹。結(jié)構(gòu)相似的復(fù)用器樹然后合并形成4.1節(jié)中的總線結(jié)構(gòu)。

--- 算法的主要部分依次優(yōu)化每一個(gè)總線。均衡將2:1復(fù)用器重新排列為三聯(lián)，這樣在壓縮階段，每個(gè)三聯(lián)能夠重新編碼為效率更高的4:1復(fù)用器。

6. 結(jié)果

--- 本文所闡述的算法已經(jīng)集成到Altera Quartus II 4.2綜合軟件中。圖16顯示120個(gè)真實(shí)用戶設(shè)計(jì)中，Altera基準(zhǔn)測試的面積減小結(jié)果。

--- 結(jié)果表明，一小部分設(shè)計(jì)所需的LUT數(shù)量減小了20%，超過四成的設(shè)計(jì)面積減小了5%以上。所有設(shè)計(jì)面積平均減小了4.2%。

--- 據(jù)估算，面積減少平均4.2%意味著復(fù)用器平均減少了17%。

--- 復(fù)用器重構(gòu)主要集中在減小面積上（例如，減少所需4-LUT的數(shù)量），而且對(duì)電路速率影響不大，電路平均速率僅降低1%。

7. 結(jié)論

--- 本文闡述了復(fù)用器重構(gòu)算法，該算法能夠?qū)⒃O(shè)計(jì)中實(shí)現(xiàn)復(fù)用器所需的4-LUT數(shù)量平均減少17%。

--- 復(fù)用器重構(gòu)算法的關(guān)鍵在于優(yōu)化復(fù)用器總線。即使附加了控制邏輯，新優(yōu)化算法仍能夠減小總線上每個(gè)比特位的面積。這是由于控制邏輯可以由總線共享，其面積代價(jià)可以抵消。

--- 壓縮將2:1復(fù)用器三聯(lián)轉(zhuǎn)換為有效的4:1復(fù)用器。盡管可能需要附加LUT對(duì)4:1復(fù)用器控制線進(jìn)行重新編碼，這種代價(jià)可以通過采用復(fù)用器總線整體壓縮方法來抵消。此外，通過構(gòu)建最大的復(fù)用器樹，可對(duì)大量的2:1復(fù)用器三聯(lián)進(jìn)行轉(zhuǎn)換。

--- 本文還引入了能夠提高壓縮算法效率的均衡方法。本文描述了面向基于4-LUT的FPGA算法，例如Altera Stratix I和Cyclone器件。新的FPGA體系結(jié)構(gòu)可使用不同大小的查找表（如Stratix II體系結(jié)構(gòu)能夠采用4、5、6輸入LUT）?？刹捎帽疚年U述的方法來進(jìn)一步減小這些體系結(jié)構(gòu)的面積。