FPGA中并行計算的流水線計算和交替計算

用過FPGA的人應(yīng)該都知道，在FPGA中，邏輯是并行地運行的，各個狀態(tài)機同時都在工作，狀態(tài)機之間可能會有信號交互，也可能毫無關(guān)系、各管各地工作。

這就給了我們一個靈感：如果我們要做的計算(例如級數(shù)求和)的規(guī)模很大，按順序一步一步算的話，其時間開銷是我們所無法忍受的，那么，我們是否可以想辦法利用FPGA的并行特性，通過讓計算并行地執(zhí)行，來減小時間開銷(或者說提高計算速度)呢?

基于這個靈感，就讓我們看看，F(xiàn)PGA中并行計算的常規(guī)方法吧。

流水線計算

現(xiàn)在，我們要在FPGA中做這樣一個計算：

B = A × imes× 2 + 1

能用的計算單元為兩輸入加法器和兩輸入乘法器

為了保證時序，一個時鐘周期內(nèi)加法器只能執(zhí)行一次加法

為了保證時序，一個時鐘周期內(nèi)乘法器只能執(zhí)行一次乘法

對于上述要求完成的計算，看上去，在一個時鐘周期內(nèi)既完成乘法又完成加法是不可能的了。然而，如果我們這么做呢：

1.設(shè)計一個模塊，模塊的輸入為時鐘和參數(shù)A，輸出為結(jié)果B。

2.該模塊在每個時鐘周期同時做"C=A×2"的計算和"B=C+1"的計算，其中，C為寄存器。

仿真該模塊，就可以發(fā)現(xiàn)：

從上表可以看到：

雖然從輸入A到輸出B，相差了兩個時鐘周期，但是，每個時鐘周期輸出的B，都和兩個時鐘周期前輸入的A相對應(yīng)。即：等效地來看，相當于每個時鐘周期，模塊都完成了一次"B = A × imes× 2 + 1"的計算!

哇塞，好神奇!這簡直就是：

明明一次性無法完成的計算，不知怎么搞的，卻等效地"被一次性地完成了"

嗯，這種搞法，就是傳說中的"流水線計算"，這里為其給出了一個不拘泥于FPGA中的情形的、更加普適的定義：

將一個計算拆分成N級(N ≥ geq≥ 2)，每一級的平均數(shù)據(jù)吞吐速率都相同，前(N-1)級的計算結(jié)果在輸入下一級之前都經(jīng)過了緩存，這種方法稱為"流水線計算"

注："平均數(shù)據(jù)吞吐速率"指的是：在單位時間內(nèi)，參數(shù)平均能夠輸入多少次，以及計算結(jié)果平均能夠輸出多少次。

流水線計算的結(jié)構(gòu)如下圖所示("一條龍"式的結(jié)構(gòu))：

分析定義可知：

正是由于"每一級的平均數(shù)據(jù)吞吐速率都相同"，使得整個計算的平均數(shù)據(jù)吞吐速率相同，才讓輸出的結(jié)果看上去"像是被一次性地完成的"。

級間緩存在流水線計算中是必不可少的，它們起到了兩級間隔離的作用，使得"當?shù)?n+1)級在處理第i ii個輸入對應(yīng)的計算時，第n級已經(jīng)在處理第( i + 1 ) (i+1)(i+1)個輸入對應(yīng)的計算了"這種情況成為可能。增大級間緩存的延遲時間，會造成整個計算的延遲時間(即輸出和輸入之間的延遲時間)的加長。

總的來說，流水線計算是個好東西，不過，實際使用時，如果不留心的話，容易為級間緩存分配過長的延遲時間，從而出現(xiàn)"整個計算的延遲時間長"的問題，這一點需要注意。

分布式流水線計算

現(xiàn)在，我們要在FPGA中做這樣一個計算：

C = A × imes× 2 + B × imes× 3

能用的計算單元為兩輸入加法器和兩輸入乘法器

為了保證時序，一個時鐘周期內(nèi)加法器只能執(zhí)行一次加法

為了保證時序，一個時鐘周期內(nèi)乘法器只能執(zhí)行一次乘法

對于上述要求完成的計算，看上去，在一個時鐘周期內(nèi)既完成乘法又完成加法是不可能的了。然而，如果我們這么做呢：

1.設(shè)計一個模塊，模塊的輸入為時鐘和參數(shù)A、參數(shù)B，輸出為結(jié)果C。

2.該模塊在每個時鐘周期同時做"D=A×2"的計算、"E=B×3"的計算和"C=D+E"的計算，其中，D、E為寄存器。

仿真該模塊，就可以發(fā)現(xiàn)：

從上表可以看到：

等效地來看，相當于每個時鐘周期，模塊都完成了一次"C = A × imes× 2 + B × imes× 3"的計算

這種做法明顯蘊含了"流水線計算"，不過又跟流水線計算的"一條龍"結(jié)構(gòu)似乎不同，這種做法的結(jié)構(gòu)是"樹形"的：

對于輸入的參數(shù)A和B，先是"你算你的，我算我的"，分別輸出并緩存D和E。然后拿D和E計算得到結(jié)果C。

對于這種做法，我稱之為"分布式流水線計算"，這個名稱借鑒了計算機網(wǎng)絡(luò)領(lǐng)域的術(shù)語"分布式計算"。使用分布式流水線計算的必要前提是：

計算所需的輸入?yún)?shù)不止一個

分布式流水線計算可以看成是"在輸入?yún)?shù)不止一個的情況下，展露出計算細節(jié)的流水線計算"，或者說，從本質(zhì)上來講，分布式流水線計算屬于流水線計算，不要因為看上去是樹形結(jié)構(gòu)就幫它"自立門戶"了。不信?沒事，我將上面的"計算C = A × imes× 2 + B × imes× 3"的模塊的結(jié)構(gòu)重新畫一下你就信了：

既然說"分布式流水線計算屬于流水線計算"，那為什么還要專門在這里講分布式流水線計算呢?原因是這樣的：分布式流水線計算展露了計算細節(jié)，更加有助于邏輯開發(fā)人員弄清楚計算過程中的延時情況，防止在不知不覺間，增大了整個計算的延遲時間。比如，對于上面的"C = A × imes× 2 + B × imes× 3"，如果不加注意的話，可能會變成這樣：

從上圖就能看出來，明明兩級就能完成的計算，一不留神就變成了三級，整個計算的延遲時間變長了。不過需要說明的是，"整個計算的延遲時間"并不是衡量"一個并行計算結(jié)構(gòu)的優(yōu)劣"的標準。比如，在做并行卷積計算時，采取流水線的結(jié)構(gòu)可以節(jié)省計算資源(但是整個計算的延遲時間長)，而采取多相的結(jié)構(gòu)可以縮短整個計算的延遲時間(但是消耗更多的計算資源，雖然其實也多不了太多)。

這里展示一個更加復雜的分布式流水線計算的案例：

交替計算

現(xiàn)在，我們要在FPGA中做這樣一個計算：

C = A + B

能用的計算單元為兩輸入加法器

為了保證時序，一個時鐘周期內(nèi)加法器只能執(zhí)行一次加法，時鐘頻率最高為100MHz

可以用寄存器來存儲數(shù)據(jù)

為了保證時序，寄存器最高只能工作在300MHz的時鐘頻率下

乍一看，這情況讓人有點迷茫：表達式都簡單成這樣了，還需要玩并行計算?別急，我們的問題是這樣的：

A和B都是在300MHz時鐘的驅(qū)動下刷新的，在這種情況下，如何才能完成"C = A + B"的計算?

呵呵，加法器最高工作頻率為100MHz，而數(shù)據(jù)的刷新頻率都飆到300MHz去了，沒法玩了好吧!咳咳，其實還是可以玩的?？紤]一下這么做：

設(shè)計一個模塊，模塊的輸入為300MHz時鐘和參數(shù)A、參數(shù)B，輸出為結(jié)果C(C為寄存器)。

在300MHz時鐘的驅(qū)動下：

在第(i+1)個時鐘周期將A、B的值分別賦給A1、B1寄存器，

在第(i+2)個時鐘周期將A、B的值分別賦給A2、B2寄存器，

在第(i+3)個時鐘周期將A、B的值分別賦給A3、B3寄存器，

在第(i+4)個時鐘周期將A、B的值分別賦給A1、B1寄存器，

在第(i+5)個時鐘周期將A、B的值分別賦給A2、B2寄存器，

模塊中，將300MHz的時鐘三分頻后得到100MHz時鐘：clk100m_1，clk100m_2，clk100m_3。

三個100MHz時鐘之間的相位都相差(360°/3=)120°。

在100MHz時鐘的驅(qū)動下(假定分配的100MHz時鐘都能滿足所需的建立保持時間需求)：

使用加法器，在clk100m_1的每個時鐘周期計算C1 = A1 + B1，其中，C1為寄存器。

使用加法器，在clk100m_2的每個時鐘周期計算C2 = A2 + B2，其中，C2為寄存器。

使用加法器，在clk100m_3的每個時鐘周期計算C3 = A3 + B3，其中，C3為寄存器。

在300MHz時鐘的驅(qū)動下：

在第(k+1)個時鐘周期將C1的值賦給C，(其中，k=i+4)

在第(k+2)個時鐘周期將C2的值賦給C，

在第(k+3)個時鐘周期將C3的值賦給C，

在第(k+4)個時鐘周期將C1的值賦給C，

在第(k+5)個時鐘周期將C2的值賦給C，

上述模塊的時序如下圖所示：

從上圖可以看到：

加法器都工作在100MHz的時鐘下

A、B、C的刷新頻率都是300MHz

可見，我們利用3個最高工作頻率100MHz的加法器，等效地實現(xiàn)了1個最高工作頻率300MHz的加法器。

這里所采用的方法通常被稱為是"乒乓計算"(或者"乒乓操作")，不過，竊以為這個名稱不夠形象，因此，為這種方法取了個新名稱：“交替計算”。交替計算的基本思想是：

將計算單元復制若干份，交替地將輸入的參數(shù)分配給各個計算單元，并且交替地將各個計算單元的計算結(jié)果輸出，從而實現(xiàn)"以N倍的計算單元換取N倍的計算速度"。

交替計算的基本結(jié)構(gòu)如下圖所示：

混合型并行計算

在實際的FPGA并行計算中，常常將流水線計算、交替計算混合使用，來滿足計算需求。嗯，這就是所謂的"混合型并行計算"，沒毛病。

用一句話將本論述歸納總結(jié)一下，那就是：

FPGA中并行計算的基本常規(guī)方法為：流水線計算和交替計算。

原文標題：FPGA學習-FPGA中并行計算的常規(guī)方法

文章出處：【微信公眾號：FPGA設(shè)計論壇】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

審核編輯：湯梓紅