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

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

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

流水線計(jì)算

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

B = A × imes× 2 + 1

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

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

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

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

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

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

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

從上表可以看到：

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

哇塞，好神奇!這簡(jiǎn)直就是：

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

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

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

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

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

分析定義可知：

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

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

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

分布式流水線計(jì)算

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

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

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

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

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

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

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

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

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

從上表可以看到：

等效地來看，相當(dāng)于每個(gè)時(shí)鐘周期，模塊都完成了一次"C = A × imes× 2 + B × imes× 3"的計(jì)算

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

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

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

計(jì)算所需的輸入?yún)?shù)不止一個(gè)

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

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

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

這里展示一個(gè)更加復(fù)雜的分布式流水線計(jì)算的案例：

交替計(jì)算

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

C = A + B

能用的計(jì)算單元為兩輸入加法器

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

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

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

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

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

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

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

在300MHz時(shí)鐘的驅(qū)動(dòng)下：

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

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

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

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

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

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

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

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

使用加法器，在clk100m_1的每個(gè)時(shí)鐘周期計(jì)算C1 = A1 + B1，其中，C1為寄存器。

使用加法器，在clk100m_2的每個(gè)時(shí)鐘周期計(jì)算C2 = A2 + B2，其中，C2為寄存器。

使用加法器，在clk100m_3的每個(gè)時(shí)鐘周期計(jì)算C3 = A3 + B3，其中，C3為寄存器。

在300MHz時(shí)鐘的驅(qū)動(dòng)下：

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

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

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

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

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

上述模塊的時(shí)序如下圖所示：

從上圖可以看到：

加法器都工作在100MHz的時(shí)鐘下

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

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

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

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

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

混合型并行計(jì)算

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

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

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

原文標(biāo)題：FPGA學(xué)習(xí)-FPGA中并行計(jì)算的常規(guī)方法

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

審核編輯：湯梓紅