摘 要： 本文介紹了一種新的復(fù)用器重構(gòu)算法，能夠降低FPGA實(shí)際設(shè)計(jì)20％的成本。該算法通過減少復(fù)用器所需查找表（LUT）的數(shù)量來實(shí)現(xiàn)。算法以效率更高的4:1復(fù)用器替代2:1復(fù)用器樹。算法性能的關(guān)鍵在于尋找總線上出現(xiàn)的復(fù)用器數(shù)量。新的優(yōu)化方法占用一定的邏輯，這些邏輯由總線進(jìn)行分擔(dān)，從而減少了總線上每個(gè)比特位所需的邏輯。 （本站編者：該算法已經(jīng)集成在QuartusII4.2軟件中，使用QuartusIi進(jìn)行綜合HDL語言時(shí)會(huì)自動(dòng)調(diào)用該算法進(jìn)行綜合，本文介紹該算法的詳情，本文適合希望深入了解算法的用戶閱讀）

關(guān)鍵詞： FPGA；復(fù)用器；重構(gòu)；重新編碼；總線；邏輯優(yōu)化；綜合

1. 引言

--- 復(fù)用器是數(shù)據(jù)通道常用的構(gòu)建模塊，被廣泛應(yīng)用在處理器[1]、處理器總線、網(wǎng)絡(luò)交換，甚至是資源共享的DSP設(shè)計(jì)中。據(jù)估計(jì)，復(fù)用器一般要占用一個(gè)FPGA設(shè)計(jì)[2] 25%以上的面積。因此，優(yōu)化FPGA設(shè)計(jì)的關(guān)鍵在于怎樣優(yōu)化復(fù)用器。

--- 本文介紹了一種新的復(fù)用器重構(gòu)算法，該算法減小了復(fù)用器在基于4輸入查找表（4-LUT）FPGA體系結(jié)構(gòu)中所占用的面積。基準(zhǔn)測試結(jié)果表明復(fù)用器平均減少了17%，在一些設(shè)計(jì)中，4-LUT整體減少20%。

--- 2.1節(jié)闡述了復(fù)用器是如何由行為級VHDL[4]或Verilog[5]代碼產(chǎn)生的，2.2和2.3節(jié)闡述復(fù)用器樹和復(fù)用器總線在設(shè)計(jì)中是怎樣生成的。2.4節(jié)說明這些結(jié)構(gòu)怎樣由4-LUT實(shí)現(xiàn)，闡述如何采用兩個(gè)4-LUT有效實(shí)現(xiàn)一個(gè)4:1二進(jìn)制復(fù)用器。

--- 第3節(jié)介紹了一種叫做壓縮的新技術(shù)，該技術(shù)附加一些控制邏輯，將多個(gè)2:1復(fù)用器重新組合為有效的4:1復(fù)用器，從而減少了為總線上每一個(gè)比特位實(shí)現(xiàn)復(fù)用器所需要的4-LUT數(shù)量，所附加的控制邏輯代價(jià)由整個(gè)總線來分擔(dān)。優(yōu)化復(fù)用器總線是復(fù)用器重構(gòu)算法的核心。

--- 4.1節(jié)闡述復(fù)用器重構(gòu)算法如何構(gòu)建設(shè)計(jì)中的復(fù)用器樹總線。4.2節(jié)的重構(gòu)方法用于執(zhí)行4.3節(jié)中定義的均衡算法。均衡增加了由壓縮生成的有效4:1復(fù)用器的數(shù)量。

--- 第5節(jié)總結(jié)了在Altera Quartus II集成綜合中運(yùn)行的整個(gè)算法。第6節(jié)列出了來自120個(gè)Altera真實(shí)用戶設(shè)計(jì)實(shí)例的基準(zhǔn)測試結(jié)果，測試表明面積減少超過20%，平均節(jié)省了4.2%。

2. 背景知識(shí)

--- 2.1 復(fù)用器在設(shè)計(jì)中是怎樣實(shí)現(xiàn)的

--- 行為級HDL設(shè)計(jì)中的任何條件代碼通常會(huì)綜合為復(fù)用器。本節(jié)闡述兩個(gè)最常用的復(fù)用器生成代碼實(shí)例。
--- 圖1是VHDL的case聲明及其2:1復(fù)用器樹的實(shí)現(xiàn)。采用Verilog case聲明的“parallel case”指令[5]可產(chǎn)生相似的結(jié)果。

圖1

--- 注意，并不是所有的case聲明都能將可能的事件描述清楚，需要依靠“default”或者“others”條件來進(jìn)一步說明。在這些情況下，可以繼續(xù)將case聲明表征為2:1復(fù)用器樹，但是這種樹結(jié)構(gòu)可能達(dá)不到平衡。

--- 圖2顯示了“if-then-else”聲明是怎樣產(chǎn)生一個(gè)2:1復(fù)用器鏈的。Verilog的“?:”和非平行cases可同樣產(chǎn)生相似的結(jié)構(gòu)。注意，復(fù)用器鏈確保如果第一個(gè)if條件為“真”，將選擇“a”數(shù)據(jù)輸入，而復(fù)用器其他部分將被忽略。

--- 本文闡述的復(fù)用器重構(gòu)算法應(yīng)用于2:1復(fù)用器。綜合工具由行為級代碼開始通常會(huì)生成較大的復(fù)用器。較大的復(fù)用器總是被分解為2:1復(fù)用器樹，如何實(shí)現(xiàn)這種分解已經(jīng)超出本文討論范圍。

圖2 if-then-else聲明生成的邏輯


圖3 HDL生成的復(fù)用器材


圖4 生成復(fù)用器總線

--- 2.2 復(fù)用器樹

--- 設(shè)計(jì)中復(fù)用器之間的饋入是常見的現(xiàn)象。例如，在一段HDL代碼中，如下面的圖3所示，if-then-else聲明中含有case聲明就會(huì)產(chǎn)生這種現(xiàn)象。
--- 在復(fù)用器重構(gòu)算法中，識(shí)別出較大的復(fù)用器樹對于盡可能減少面積是非常重要的。

--- 2.3 復(fù)用器總線

--- VHDL信號或Verilog線寬通常會(huì)超過一個(gè)比特位。當(dāng)采用if-then-else和case聲明時(shí)，將會(huì)生成大量具有不同數(shù)據(jù)輸入的相同復(fù)用器樹，圖4是一個(gè)實(shí)例。一組具有相同結(jié)構(gòu)的復(fù)用器稱為復(fù)用器樹總線。

--- 本文闡述的復(fù)用器重構(gòu)技術(shù)采用了新的對整個(gè)復(fù)用器總線進(jìn)行優(yōu)化的方法，它通過由4.1節(jié)中進(jìn)一步闡述的總線識(shí)別和形成技術(shù)來實(shí)現(xiàn)。

--- 2.4 復(fù)用器代價(jià)

--- 在許多情況下，每個(gè)2:1復(fù)用器都需要一個(gè)單獨(dú)的4-LUT。這樣，圖1和圖2中的復(fù)用器結(jié)構(gòu)都需要三個(gè)4-LUT。盡管這些結(jié)構(gòu)控制編碼不同，但是它們都具有4個(gè)不同的數(shù)據(jù)輸入，因此可以當(dāng)作4:1復(fù)用器。本節(jié)闡述如何實(shí)現(xiàn)只需要兩個(gè)4-LUT的4:1復(fù)用器。

--- 圖5是控制輸入S0低電平時(shí)，一個(gè)有效的4:1復(fù)用器是如何工作的。4:1復(fù)用器由兩個(gè)鏈接在一起的4-LUT（陰影框所示）構(gòu)成。每個(gè)4-LUT被設(shè)置為含有陰影框中的邏輯功能。如白框所示，復(fù)用器含有四個(gè)輸入——a、b、c和d，以及兩個(gè)控制輸入——S0和S1。

圖5

--- S0低電平時(shí)，低位控制比特S1在輸入c和d中進(jìn)行選擇，其結(jié)果通過第二個(gè)4-LUT，將a或者b輸入旁路。

圖6

--- 圖6是控制輸入S0高電平時(shí)，一個(gè)有效的4:1復(fù)用器是如何工作的。低位控制比特S1旁路c和d輸入，直接進(jìn)入第二個(gè)4-LUT，對a或者b輸入進(jìn)行選擇，其結(jié)果成為第二個(gè)4-LUT的輸出。

--- 第3節(jié)描述的壓縮算法采用這種有效的4:1復(fù)用器，重新實(shí)現(xiàn)復(fù)用器結(jié)構(gòu)，達(dá)到了減小面積的目的。

3. 壓縮

--- 壓縮是將低效的4:1復(fù)用器實(shí)現(xiàn)轉(zhuǎn)換為高效實(shí)現(xiàn)的過程。復(fù)用器重構(gòu)算法的面積節(jié)省由壓縮實(shí)現(xiàn)。但是，在不同的復(fù)用器表征中進(jìn)行轉(zhuǎn)換，通常需要附加控制邏輯。實(shí)際上，由于附加邏輯結(jié)構(gòu)抵消了使用高效復(fù)用器結(jié)構(gòu)的優(yōu)勢，這種轉(zhuǎn)換很少能夠產(chǎn)生真正的面積節(jié)省。而復(fù)用器重構(gòu)算法采用新穎的將整個(gè)復(fù)用器總線進(jìn)行轉(zhuǎn)換的方法，這樣，總線上的多個(gè)復(fù)用器可以共享控制邏輯，因此，改善后的復(fù)用器結(jié)構(gòu)優(yōu)勢可通過總線上的每個(gè)復(fù)用器來實(shí)現(xiàn)。

圖7

--- 圖7顯示了如何將三個(gè)2:1復(fù)用器組成的優(yōu)先級鏈轉(zhuǎn)換為一個(gè)4:1二進(jìn)制復(fù)用器。假設(shè)控制輸入由不相關(guān)的邏輯饋入，那么這種轉(zhuǎn)換至多需要兩個(gè)額外的4-LUT控制邏輯。如果最初的復(fù)用器至少占用三個(gè)4-LUT，而4:1復(fù)用器只需要兩個(gè)即可實(shí)現(xiàn)，那么這種轉(zhuǎn)換將節(jié)省3寬度或者更寬總線的面積。

圖8

--- 圖8顯示了如何將一組排列成樹的2:1復(fù)用器轉(zhuǎn)換為一個(gè)4:1復(fù)用器。在這種情況下，通過仔細(xì)為4:1復(fù)用器選擇編碼方式，使S0在（A、B）和（C、D）之間進(jìn)行選擇，限制附加控制邏輯，只加入最多一個(gè)4-LUT。此時(shí)，這種轉(zhuǎn)換將節(jié)省2寬度或者更寬總線的面積。

--- 一般來講，任何的三個(gè)2:1復(fù)用器組都可以通過圖7或圖8的方式轉(zhuǎn)換為一個(gè)4:1復(fù)用器。但是，這兩種轉(zhuǎn)換必須在寬度大于2的復(fù)用器總線上進(jìn)行，以減小所需4-LUT的數(shù)量，實(shí)際上，如果這兩種轉(zhuǎn)換不在總線上進(jìn)行，將沒有意義。

--- 總線上2:1復(fù)用器三聯(lián)重新編碼是復(fù)用器重構(gòu)算法的核心。 第4節(jié)將闡述形成數(shù)量最多三聯(lián)的新方法。

?

4. 復(fù)用器總線

4.1 “庫”的構(gòu)造

--- 壓縮減小了其所編碼的每一個(gè)2:1復(fù)用器三聯(lián)面積，因此，壓縮應(yīng)用在較大的復(fù)用器樹上最有效。本節(jié)闡述大型復(fù)用器樹是如何構(gòu)建的。設(shè)計(jì)中所有的總線都將被存儲(chǔ)在一種稱為“庫”的數(shù)據(jù)結(jié)構(gòu)中。

--- 復(fù)用器樹采用下面的方法構(gòu)建。設(shè)計(jì)中所有2:1復(fù)用器以反向深度順序排列。這意味著那些離寄存器或者輸出引腳最近的復(fù)用器將排在列表前面。然后從頭至尾掃描列表，尋找每一個(gè)2:1復(fù)用器，如果其輸出僅與另一個(gè)2:1復(fù)用器相連，則將該復(fù)用器和與其相連的復(fù)用器一起加到復(fù)用器樹中。否則，將此2:1復(fù)用器作為一個(gè)新復(fù)用器樹的首復(fù)用器。以此方式來構(gòu)建的復(fù)用器樹含有最大數(shù)量的復(fù)用器。

--- 如果復(fù)用器樹中復(fù)用器的所有數(shù)據(jù)輸入均不是由同一個(gè)樹中其他的2:1復(fù)用器饋入，則稱此復(fù)用器為初級輸入（對整個(gè)樹而言）。

--- 一旦所有的復(fù)用器樹已經(jīng)形成，則將其合并成總線。如果兩個(gè)復(fù)用器樹要并入同一個(gè)總線，它們必須具有相同的結(jié)構(gòu)，即2:1復(fù)用器的排列相同，并且都有完全一致的控制輸入。這可以通過根據(jù)復(fù)用器結(jié)構(gòu)，對所有復(fù)用器樹列表排序來實(shí)現(xiàn)，在列表中將結(jié)構(gòu)相同的樹靠近排列。總線可直接由結(jié)構(gòu)相同的樹構(gòu)成。

--- 通過規(guī)則選取來實(shí)現(xiàn)總線寬度最大化。寬總線可以將由壓縮引入的控制邏輯開銷降低到最小。

--- 4.2 重構(gòu)

--- 4.3節(jié)描述均衡方法，該方法能夠使壓縮得到的面積減小最大化。均衡建立在重構(gòu)的基礎(chǔ)上，其概念由本節(jié)給出。

--- 通過2:1復(fù)用器所饋入的一個(gè)2:1復(fù)用器，重構(gòu)移動(dòng)該復(fù)用器及其一個(gè)輸入。圖9顯示了陰影復(fù)用器與其“f”輸入的重構(gòu)。為保持原始復(fù)用器總線的功能，需要附加一些控制邏輯。這些控制邏輯同樣可以由總線上的每一個(gè)復(fù)用器樹來分擔(dān)。

圖9

--- 圖9中，重新編碼邏輯(c6 AND (NOT c3))必須確保當(dāng)c1、c3為“假”而c6為“真”時(shí)，選擇輸入“f”（與轉(zhuǎn)換前的情況一致）。同樣，當(dāng)c1、c3、c6為“假”時(shí)，選擇輸入“g”，即(c6 AND (NOT c3))也是“假”。
--- 重構(gòu)轉(zhuǎn)換將選中的復(fù)用器進(jìn)一步向復(fù)用器樹頂端移動(dòng)。因此，不斷重復(fù)重構(gòu)轉(zhuǎn)換，可以將任意位置的復(fù)用器向頂端移動(dòng)。

--- 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)得到最佳的壓縮。對于圖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ù)用器，甚至沒有剩余。

--- 均衡中的任何階段，都需要對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)算法性能依賴于對較大復(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ù)量），而且對電路速率影響不大，電路平均速率僅降低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對4:1復(fù)用器控制線進(jìn)行重新編碼，這種代價(jià)可以通過采用復(fù)用器總線整體壓縮方法來抵消。此外，通過構(gòu)建最大的復(fù)用器樹，可對大量的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）。可采用本文闡述的方法來進(jìn)一步減小這些體系結(jié)構(gòu)的面積。

參考文獻(xiàn)

1 A High Performance 32-bit ALU for Programmable Logic. P. Metzgen. Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field Programmable Gate Arrays. Pp 61-70. 2004.
2 Logic Optimization Techniques for Multiplexers. J. Stephenson and P. Metzgen. Mentor User2User Conference 2004, www.mentor.com\user2user
3 The Stratix Device Handbook (Vol 1). Altera Corporation, 2004.
4 1076(tm) IEEE Standard VHDL Language Reference Manual. IEEE Computer Society. IEEE Std 1076(tm)-2002.
5 IEEE Standard Verilog(r) Hardware Description Language. IEEE Computer Society. IEEE Std 1364-2001.