大規(guī)模的整數(shù)加法在數(shù)字信號(hào)處理和圖像視頻處理領(lǐng)域應(yīng)用很多，其對(duì)資源消耗很多，如何能依據(jù)FPGA物理結(jié)構(gòu)特點(diǎn)來有效降低加法樹的資源和改善其時(shí)序特征是非常有意義的。本篇論文是基于altera公司的FPGA，利用其LUT特點(diǎn)，探索設(shè)計(jì)最大程度利用LUT以及改善時(shí)序的compressor樹的結(jié)構(gòu)。

01

半加器和全加器

半加器是兩個(gè)輸入bit相加，輸出結(jié)果S和進(jìn)位C。表達(dá)式為：

全加器是三個(gè)bit相加，有進(jìn)位參與，表達(dá)式為：

Compressor樹就是在全加器的基礎(chǔ)上建立的，通過全加器的S和C結(jié)果相互連接形成多層樹狀結(jié)構(gòu)，其相比于普通的進(jìn)位加法樹消耗更少資源。普通進(jìn)位加法樹是用兩個(gè)或者三個(gè)加法模塊連接成樹，形成多層結(jié)構(gòu)來計(jì)算多輸入加法。放一張wallace樹的經(jīng)典文獻(xiàn)中的圖片來大致了解一下compressor樹的結(jié)構(gòu)。

圖1.1 compressor樹結(jié)構(gòu)

02

Compressor樹

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

Compressor樹的結(jié)果就是：

Compressor樹就是由以上的全加器構(gòu)成的。全加器構(gòu)成一個(gè)基本的并行計(jì)數(shù)器，并行計(jì)數(shù)器（Generalized parallel counters）GPC可以用一個(gè)元組表示：

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

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

第一個(gè)約束條件是所有列的bit數(shù)被限制在M以內(nèi)，第二個(gè)條件是所能實(shí)現(xiàn)的最大數(shù)據(jù)范圍。后邊會(huì)根據(jù)這兩個(gè)條件提出一個(gè)在FPGA上優(yōu)化compressor樹的算法。

用GPC來實(shí)現(xiàn)元組(1, 4, 1, 5; 5)為下圖：

圖2.2 實(shí)現(xiàn)元組(1, 4, 1, 5; 5)的GPC結(jié)構(gòu)

從圖中看出其延時(shí)包括一個(gè)FA的延時(shí)和4個(gè)進(jìn)位鏈產(chǎn)生的延時(shí)。在FPGA中提供了高速的進(jìn)位鏈，所以GPC很適合在FPGA中實(shí)現(xiàn)。因此在FPGA上利用好GPC可以降低加法樹的級(jí)數(shù)。

比如舉個(gè)例子，如圖2.3所示，計(jì)算兩列數(shù)據(jù)和，如果使用華萊士樹的方式，會(huì)采用兩級(jí)電路，第一級(jí)用兩個(gè)全加器，將三行數(shù)據(jù)降低到兩行數(shù)據(jù)，最后再用一個(gè)進(jìn)位鏈加法器實(shí)現(xiàn)最后數(shù)據(jù)相加。而如果使用GPC（3, 3; 4）僅僅用一級(jí)電路就能實(shí)現(xiàn)這三行數(shù)據(jù)的相加。

圖2.3 compressor樹構(gòu)建方式：a)用連個(gè)全加器和進(jìn)位鏈加法器 b)用一個(gè)（3, 3; 4）GPC

現(xiàn)在結(jié)合altera的器件結(jié)構(gòu)來分析如何能更好的利用LUT來搭建一個(gè)GPC。Stratix器件中的adaptive logic module（ALM）包含兩個(gè)6-LUT，這兩個(gè)LUT共享輸入，因此一個(gè)ALM模塊可以實(shí)現(xiàn)6-2的功能。

通過圖2.4可以看出，如果將6輸入3輸出進(jìn)行映射，會(huì)有一個(gè)LUT空置，利用率為75%。如果將6輸入4輸出映射到LUT，那么利用率為100%。如果將2個(gè)6輸入3輸出映射到2個(gè)ALM，這個(gè)無法實(shí)現(xiàn)，因?yàn)锳LM中兩個(gè)LUT共享輸入則無法綜合。

圖2.4 （a）一個(gè)6-3GPC映射，只有75%利用率（b）6-4GPC映射，利用率100%（c）2個(gè)6-3映射到2個(gè)ALM不可實(shí)現(xiàn)

03

高效映射算法

為了提高LUT利用率，降低器件中邏輯使用面積，論文基于以上的兩個(gè)約束以及altera LUT結(jié)構(gòu)特點(diǎn)提出了GPC選擇的算法。

首先我們定義兩個(gè)概念，primitive GPC是滿足以上約束的所有GPC集。比如對(duì)于M=6，n=3，一共有12個(gè)GPC。Covering GPC是指可以不被其它GPC實(shí)現(xiàn)的，即其實(shí)現(xiàn)是唯一的。比如（2, 2; 3）就不是一個(gè)covering GPC，因?yàn)槠淅茫?, 3; 3）GPC同樣可以實(shí)現(xiàn)，只要將bit0對(duì)應(yīng)的一個(gè)數(shù)置為0就行了。比如對(duì)于6-3GPC的covering GPC有{(0, 6; 3), (1, 5; 3), (2, 3; 3)}。而(3, 1; 3)是一個(gè)不夠高效的GPC，因?yàn)槠鋌it0只有一個(gè)bit有數(shù)，其可以繞過GPC直接輸出。compressor ratio是輸入對(duì)輸出的比率，比如（2, 3; 3）的比率是5/3=1.66。

算法步驟如下：

1） 首先依據(jù)M和n生成covering GPC；

2） 產(chǎn)生一些列primitive GPC，compressor樹將會(huì)由這些GPC來構(gòu)建，但是最后將由對(duì)應(yīng)的covering GPC來替代；

3） 計(jì)算每個(gè)primitive GPC的compressor ratio并分類；

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

4） 首先從所有求和列中選擇一個(gè)bit數(shù)最多的列作為基準(zhǔn)，然后再同時(shí)向前和向后進(jìn)行搜索，比較前后兩個(gè)列的compressor ratio，選擇最大的作為將要用于GPC映射的列。不斷重復(fù)這個(gè)過程直到所有列都完成搜索。

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

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

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

第三個(gè)高列有4bit，可以用（1, 4; 3）GPC實(shí)現(xiàn)；

…。

這樣共實(shí)現(xiàn)了4個(gè)GPC，余下的沒有實(shí)現(xiàn)的bit使用GPC實(shí)現(xiàn)不能有效提高LUT利用率，直接傳遞到下一級(jí)。

圖3.1 GPC生成過程

5） 對(duì)步驟4生成的新bit重復(fù)步驟4，進(jìn)行提取新的GPC；

6） 當(dāng)最終生成的bit行數(shù)小于k或者列數(shù)bit數(shù)小于k，迭代過程結(jié)束，這時(shí)上一級(jí)沒有被分配GPC的bit傳遞到本級(jí)，通過一個(gè)進(jìn)位鏈加法器將所有結(jié)果相加；

04

結(jié)果

論文比較了GPC和另外兩種加法器實(shí)現(xiàn)方式的邏輯面積和資源對(duì)比，這另種加法器分別為：

1 ADD：由一個(gè)三輸入加法器作為基本結(jié)構(gòu)構(gòu)建的加法樹；

2 3GD：采用carry-save 加法器來實(shí)現(xiàn)，這種結(jié)構(gòu)沒有利用ALM中的進(jìn)位鏈；

延時(shí)、邏輯面積、資源利用對(duì)比如下圖所示：

圖4.1 不同加法器實(shí)現(xiàn)方式的對(duì)比結(jié)果

總結(jié)

論文探索了利用FPGA的LUT和進(jìn)位鏈結(jié)構(gòu)來實(shí)現(xiàn)GPC，相比于ADD和3GD有更低的延時(shí)，而資源使用和ADD相差不大，比3GD小很多。這主要是源于ADD和GPC都使用了進(jìn)位鏈。

審核編輯：劉清