--- 2.2 復用器樹

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

--- 2.3 復用器總線

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

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

--- 2.4 復用器代價

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

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

圖5

--- S0低電平時，低位控制比特S1在輸入c和d中進行選擇，其結果通過第二個4-LUT，將a或者b輸入旁路。

圖6

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

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

3. 壓縮

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

圖7

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

圖8

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

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

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

4. 復用器總線

4.1 “庫”的構造

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

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

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

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

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

--- 4.2 重構

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

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

圖9

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