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

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

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

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

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

--- 本文闡述的復(fù)用器重構(gòu)技術(shù)采用了新的對(duì)整個(gè)復(fù)用器總線進(jìn)行優(yōu)化的方法，它通過(guò)由4.1節(jié)中進(jìn)一步闡述的總線識(shí)別和形成技術(shù)來(lái)實(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é)果通過(guò)第二個(gè)4-LUT，將a或者b輸入旁路。

圖6

--- 圖6是控制輸入S0高電平時(shí)，一個(gè)有效的4:1復(fù)用器是如何工作的。低位控制比特S1旁路c和d輸入，直接進(jìn)入第二個(gè)4-LUT，對(duì)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)的過(guò)程。復(fù)用器重構(gòu)算法的面積節(jié)省由壓縮實(shí)現(xiàn)。但是，在不同的復(fù)用器表征中進(jìn)行轉(zhuǎn)換，通常需要附加控制邏輯。實(shí)際上，由于附加邏輯結(jié)構(gòu)抵消了使用高效復(fù)用器結(jié)構(gòu)的優(yōu)勢(shì)，這種轉(zhuǎn)換很少能夠產(chǎn)生真正的面積節(jié)省。而復(fù)用器重構(gòu)算法采用新穎的將整個(gè)復(fù)用器總線進(jìn)行轉(zhuǎn)換的方法，這樣，總線上的多個(gè)復(fù)用器可以共享控制邏輯，因此，改善后的復(fù)用器結(jié)構(gòu)優(yōu)勢(shì)可通過(guò)總線上的每個(gè)復(fù)用器來(lái)實(shí)現(xiàn)。

圖7

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

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

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

4. 復(fù)用器總線

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

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

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

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

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

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

--- 4.2 重構(gòu)

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

--- 通過(guò)2:1復(fù)用器所饋入的一個(gè)2:1復(fù)用器，重構(gòu)移動(dòng)該復(fù)用器及其一個(gè)輸入。圖9顯示了陰影復(fù)用器與其“f”輸入的重構(gòu)。為保持原始復(fù)用器總線的功能，需要附加一些控制邏輯。這些控制邏輯同樣可以由總線上的每一個(gè)復(fù)用器樹(shù)來(lái)分擔(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ù)用器樹(shù)頂端移動(dòng)。因此，不斷重復(fù)重構(gòu)轉(zhuǎn)換，可以將任意位置的復(fù)用器向頂端移動(dòng)。