引言

大規模的整數加法在數字信號處理和圖像視頻處理領域應用很多，其對資源消耗很多，如何能依據FPGA物理結構特點來有效降低加法樹的資源和改善其時序特徵是非常有意義的。本篇論文是基於altera公司的FPGA，利用其LUT特點，探索設計最大程度利用LUT以及改善時序的compressor樹的結構。

01

半加器和全加器

半加器是兩個輸入bit相加，輸出結果S和進位C。表達式為：

全加器是三個bit相加，有進位參與，表達式為：

Compressor樹就是在全加器的基礎上建立的，通過全加器的S和C結果相互連接形成多層樹狀結構，其相比於普通的進位加法樹消耗更少資源。普通進位加法樹是用兩個或者三個加法模塊連接成樹，形成多層結構來計算多輸入加法。放一張wallace樹的經典文獻中的圖片來大致瞭解一下compressor樹的結構。

圖1.1 compressor樹結構

02

Compressor樹

Compressor樹就是在圖1.1中carry propagating adder以上的部分，其目的就是為了減少被加數個數，上圖中降低到S和C兩個後送到進位鏈加法器完成最後求和。這樣就可以降低加法對資源的消耗。假設有如下加數：

Compressor樹的結果就是：

Compressor樹就是由以上的全加器構成的。全加器構成一個基本的並行計數器，並行計數器（Generalized parallel counters）GPC可以用一個元組表示：

其中Ki表示的是輸入的被加數中處於同一位置的bit個數，如果用點來代表bit，那麼下圖中的bit0的個數有1，而bit1有2，bit2有3，…。假設一個GPC允許的最大輸入bit數為M，這個條件是考慮到FPGA中LUT的結構，比如在altera的stratix等器件中，LUT是6輸入的，為了更好的利用LUT資源，需要適配LUT輸入。那麼根據這個條件，可以得到以下的約束：

圖2.1 (1, 4, 1, 5; 5)

第一個約束條件是所有列的bit數被限制在M以內，第二個條件是所能實現的最大數據範圍。後邊會根據這兩個條件提出一個在FPGA上優化compressor樹的演算法。

用GPC來實現元組(1, 4, 1, 5; 5)為下圖：

圖2.2 實現元組(1, 4, 1, 5; 5)的GPC結構

從圖中看出其延時包括一個FA的延時和4個進位鏈產生的延時。在FPGA中提供了高速的進位鏈，所以GPC很適合在FPGA中實現。因此在FPGA上利用好GPC可以降低加法樹的級數。比如舉個例子，如圖2.3所示，計算兩列數據和，如果使用華萊士樹的方式，會採用兩級電路，第一級用兩個全加器，將三行數據降低到兩行數據，最後再用一個進位鏈加法器實現最後數據相加。而如果使用GPC（3, 3; 4）僅僅用一級電路就能實現這三行數據的相加。

圖2.3 compressor樹構建方式：a)用連個全加器和進位鏈加法器 b)用一個（3, 3; 4）GPC

現在結合altera的器件結構來分析如何能更好的利用LUT來搭建一個GPC。Stratix器件中的adaptive logic module（ALM）包含兩個6-LUT，這兩個LUT共享輸入，因此一個ALM模塊可以實現6-2的功能。通過圖2.4可以看出，如果將6輸入3輸出進行映射，會有一個LUT空置，利用率為75%。如果將6輸入4輸出映射到LUT，那麼利用率為100%。如果將2個6輸入3輸出映射到2個ALM，這個無法實現，因為ALM中兩個LUT共享輸入則無法綜合。

圖2.4 （a）一個6-3GPC映射，只有75%利用率（b）6-4GPC映射，利用率100%（c）2個6-3映射到2個ALM不可實現

03

高效映射演算法

為了提高LUT利用率，降低器件中邏輯使用面積，論文基於以上的兩個約束以及altera LUT結構特點提出了GPC選擇的演算法。

首先我們定義兩個概念，primitive GPC是滿足以上約束的所有GPC集。比如對於M=6，n=3，一共有12個GPC。Covering GPC是指可以不被其它GPC實現的，即其實現是唯一的。比如（2, 2; 3）就不是一個covering GPC，因為其利用（2, 3; 3）GPC同樣可以實現，只要將bit0對應的一個數置為0就行了。比如對於6-3GPC的covering GPC有{(0, 6; 3), (1, 5; 3), (2, 3; 3)}。而(3, 1; 3)是一個不夠高效的GPC，因為其bit0隻有一個bit有數，其可以繞過GPC直接輸出。compressor ratio是輸入對輸出的比率，比如（2, 3; 3）的比率是5/3=1.66。

演算法步驟如下：

1） 首先依據M和n生成covering GPC；

2） 產生一些列primitive GPC，compressor樹將會由這些GPC來構建，但是最後將由對應的covering GPC來替代；

3） 計算每個primitive GPC的compressor ratio並分類；

接下來的4-6步是一個不斷迭代過程，每一次迭代生成一級GPC，直到達到k行和kbit每列的限制條件。

4） 首先從所有求和列中選擇一個bit數最多的列作為基準，然後再同時向前和向後進行搜索，比較前後兩個列的compressor ratio，選擇最大的作為將要用於GPC映射的列。不斷重複這個過程直到所有列都完成搜索。

比如圖3.1展示的是一個6-3GPC建立過程。

第一個GPC是有6個bit的列，可以用（0, 6; 3）GPC來表示；

第二個最高列是有5bit，可以用（1, 5; 3）表示，附帶上旁邊的一個bit；

第三個高列有4bit，可以用（1, 4; 3）GPC實現；

…。

這樣共實現了4個GPC，餘下的沒有實現的bit使用GPC實現不能有效提高LUT利用率，直接傳遞到下一級。

圖3.1 GPC生成過程

5） 對步驟4生成的新bit重複步驟4，進行提取新的GPC；

6） 當最終生成的bit行數小於k或者列數bit數小於k，迭代過程結束，這時上一級沒有被分配GPC的bit傳遞到本級，通過一個進位鏈加法器將所有結果相加；

04

結果

論文比較了GPC和另外兩種加法器實現方式的邏輯面積和資源對比，這另種加法器分別為：

1 ADD：由一個三輸入加法器作為基本結構構建的加法樹；

2 3GD：採用carry-save 加法器來實現，這種結構沒有利用ALM中的進位鏈；

延時、邏輯面積、資源利用對比如下圖所示：

圖4.1 不同加法器實現方式的對比結果

總結

論文探索了利用FPGA的LUT和進位鏈結構來實現GPC，相比於ADD和3GD有更低的延時，而資源使用和ADD相差不大，比3GD小很多。這主要是源於ADD和GPC都使用了進位鏈。

文獻

1 Hadi Parandeh-Afshar, P.B.a.P.I., Efficient Synthesis of Compressor Trees on FPGAs. IEEE Asia and South Pacific Design Automation Conference, 2008.

往期回顧

1 用LUT來搭建乘法器

2 可變位寬的大規模矩陣乘法方法

推薦閱讀：

相關文章