復用器重構降低FPGA成本

--- 4.3 均衡

--- 壓縮通過轉換2:1復用器三聯，能夠減少實現復用器總線所需的4-LUT數量。但是，如果不進行復用器樹重構，有些結構是不可能得到最佳三聯分組的。例如，無法將圖10中所有的2:1復用器進行分組，這是因為每一種可能的分組都將會剩余一個2:1復用器而無法處理。

--- 均衡的目的在于通過最少的重構得到最佳的壓縮。對于圖10的例子，可以采用圖11所示的方法，得到兩組2:1復用器三聯。

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

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

圖10 復用器樹次優壓縮的例子

圖11 由均衡未完善壓縮


圖12 均衡算法

圖 13重構4個復用器實現均衡


圖14 重構5個復用器實現均衡

5. 算法總結

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

--- 復用器重構算法性能依賴于對較大復用器樹總線的識別。由于復用器重構算法在整個總線上分擔控制邏輯，因此，總線越寬，壓縮的效果就越明顯。優化會減小復用器樹間的相似性，從而減小所尋找的總線寬度，因此在復用器重構之前，應盡量避免優化。

--- 復用器重構以分解大的復用器為2:1復用器開始。設計中所有2:1復用器都用于形成4.1節所描述的復用器樹。結構相似的復用器樹然后合并形成4.1節中的總線結構。

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

6. 結果

--- 本文所闡述的算法已經集成到Altera Quartus II 4.2綜合軟件中。圖16顯示120個真實用戶設計中，Altera基準測試的面積減小結果。

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

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

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

7. 結論

--- 本文闡述了復用器重構算法，該算法能夠將設計中實現復用器所需的4-LUT數量平均減少17%。

--- 復用器重構算法的關鍵在于優化復用器總線。即使附加了控制邏輯，新優化算法仍能夠減小總線上每個比特位的面積。這是由于控制邏輯可以由總線共享，其面積代價可以抵消。

--- 壓縮將2:1復用器三聯轉換為有效的4:1復用器。盡管可能需要附加LUT對4:1復用器控制線進行重新編碼，這種代價可以通過采用復用器總線整體壓縮方法來抵消。此外，通過構建最大的復用器樹，可對大量的2:1復用器三聯進行轉換。

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