如何在不需要特殊庫(kù)或類(lèi)的情況下實(shí)現(xiàn)C代碼并行性?

提取實(shí)現(xiàn)任務(wù)級(jí) (task_level) 的硬件并行算法是設(shè)計(jì)高效的HLS IP內(nèi)核的關(guān)鍵。

在本文中，我們將重點(diǎn)放在如何能夠在不需要特殊的庫(kù)或類(lèi)的情況下修改代碼風(fēng)格以實(shí)現(xiàn)C代碼實(shí)現(xiàn)并行性。Xilinx HLS 編譯器的顯著特征是能夠?qū)⑷蝿?wù)級(jí)別的并行性和流水線(xiàn)與可尋址的存儲(chǔ)器 PIPO或 FIFO相結(jié)合。本文首先概述可以獲取任務(wù)并行的前提條件，然后以DAG(directedacyclic graph) 代碼為例，挖掘其中使用 fork-join 并行性，并結(jié)合使用 ping- pong buffer 啟用了一種基于握手的任務(wù)級(jí)粗粒度的流水線(xiàn)形式。

我們理解任務(wù)級(jí)并行的時(shí)候可以想象成這樣一個(gè)場(chǎng)景，每一個(gè)計(jì)算任務(wù)都是時(shí)間軸上向前奔跑的馬車(chē)，馬車(chē)與馬車(chē)之間傳輸?shù)呢浳锞拖袷怯?jì)算數(shù)據(jù)，他們需要管道去連接即 FIFO 和 PIPO ,FIFO 是一個(gè)先進(jìn)先出存儲(chǔ)器也就是說(shuō)使用這樣的管道傳輸數(shù)據(jù)的時(shí)候，數(shù)據(jù)進(jìn)出的順序不可以改變。而 PIPO 就是一個(gè)可尋址的存儲(chǔ)器管道，數(shù)據(jù)在任務(wù)之間進(jìn)出的順序可以改變。

最糟糕的狀態(tài)是什么？馬車(chē)在時(shí)間線(xiàn)上順序出發(fā)，A 馬車(chē)到達(dá)終點(diǎn)后 B 再出發(fā)以此類(lèi)推，就像是 CPU 中的單進(jìn)程順序執(zhí)行模式一樣，而FPGA中有可供并行化執(zhí)行的數(shù)據(jù)傳輸管道，更多的資源就像是跑道一樣，所以這個(gè)狀態(tài)效率是最低的。

那么先做一點(diǎn)點(diǎn)改進(jìn)，我們分析發(fā)現(xiàn) B 和 C 馬車(chē)不享有任何公用的數(shù)據(jù)或存儲(chǔ)計(jì)算資源，也就是他們完全可以在 A 結(jié)束后并行執(zhí)行，最后再執(zhí)行 D，這種并行情況中含有順序和并行兩種模式，我們稱(chēng)之為交叉并行 (fork-joinparallelism)。但是下一次進(jìn)程仍然是順序執(zhí)行的。

繼續(xù)深入可以發(fā)現(xiàn)，四輛馬車(chē)在跑完各自的任務(wù)后都有一段的閑置時(shí)間，提高吞吐量和資源重復(fù)利用也很明顯是息息相關(guān)的。實(shí)現(xiàn)了進(jìn)程之間的流水線(xiàn)執(zhí)行的結(jié)果就如下圖，每一輛馬車(chē)在不同的進(jìn)程中連續(xù)執(zhí)行任務(wù)，向前奔跑，重復(fù)利用資源的同時(shí)它提升了吞吐量進(jìn)而極大的減小了完成多個(gè)進(jìn)程后的延遲。

最理想的狀態(tài)時(shí)什么？就是馬車(chē)盡可能的一個(gè)挨著一個(gè)一起出發(fā)，并行奔跑，大家先后到達(dá)終點(diǎn)完成計(jì)算，在奔跑的過(guò)程中數(shù)據(jù)通過(guò)管道也完成了遷移，最終計(jì)算完的數(shù)據(jù)在最后一輛馬車(chē)到達(dá)終點(diǎn)的時(shí)候產(chǎn)出。下圖我們可以看到 B 和 C 開(kāi)始執(zhí)行的時(shí)間提前了，并沒(méi)有等到A完全執(zhí)行完畢，這和數(shù)據(jù)依賴(lài)息息相關(guān)，也就是說(shuō)我們進(jìn)一步挖掘并行性的路上發(fā)現(xiàn)：ABC 三輛馬車(chē)都可以在增加馬車(chē)數(shù)量 (擴(kuò)增資源) ，建立數(shù)據(jù)管道的并行執(zhí)行的前提下實(shí)現(xiàn)了。我們用資源換取了更大的并行性，這就是繼續(xù)挖掘并行性上需要付出的代價(jià)。

奔跑的馬車(chē)帶著我們理解了任務(wù)級(jí)流水線(xiàn)的優(yōu)化之路，下面我們結(jié)合代碼看一看HLS工具會(huì)在哪些情況下阻止 dataflow 的實(shí)現(xiàn)。

在我們談及 dataflow 的優(yōu)化之前，我們先去了解在 HLS 提醒你報(bào)錯(cuò)的方式，其中修改屬性config_dataflow-strict_mode (off | error | warning) 指令可以控制報(bào)錯(cuò)指令的級(jí)別，一般情況下默認(rèn)是 warning 級(jí)別的報(bào)錯(cuò)，主要看我們的并行性需求。

以下是阻止任務(wù)級(jí)別并行性的常見(jiàn)情況：

1. 單產(chǎn)出單消耗模型違例（Single-producer-consumerviolations）

為了使 VitisHLS 執(zhí)行 DATAFLOW 優(yōu)化，任務(wù)之間傳遞的所有元素都必須遵循單產(chǎn)出單消耗模型。每個(gè)變量必須從單個(gè)任務(wù)驅(qū)動(dòng)，并且只能由單個(gè)任務(wù)使用。在下面的代碼示例中是典型的單產(chǎn)出單消耗模型違例，單一的數(shù)據(jù)流 temp1 同時(shí)被 Loop2 和 Loop3 消耗。要解決這個(gè)問(wèn)題很容易，就是將兩個(gè)任務(wù)都要消耗的數(shù)據(jù)流復(fù)制成兩個(gè)，如右圖的 Split 函數(shù)。當(dāng) temp1數(shù)據(jù)流被復(fù)制為 temp2 和 temp3 后，LOOP1，2，3 就可以實(shí)現(xiàn)任務(wù)級(jí)流水線(xiàn)了。

void foo(int data_in[N], int scale, int data_out1[N], int data_out2[N]) {

int temp1[N];

Loop1: for(int i = 0; i < N; i++) {

temp1[i] = data_in[i] * scale;

}

Loop2: for(int j = 0; j < N; j++) {

data_out1[j] = temp1[j] * 123;

}

Loop3: for(int k = 0; k < N; k++) {

data_out2[k] = temp1[k] * 456;

}

}

void Split (in[N], out1[N], out2[N]) {

// Duplicated data

L1:for(int i=1;i

out1[i] = in[i];

out2[i] = in[i];

}

}

void foo(int data_in[N], int scale, int data_out1[N], int data_out2[N]) {

int temp1[N], temp2[N]. temp3[N];

Loop1: for(int i = 0; i < N; i++) {

temp1[i] = data_in[i] * scale;

}

Split(temp1, temp2, temp3);

Loop2: for(int j = 0; j < N; j++) {

data_out1[j] = temp2[j] * 123;

}

Loop3: for(int k = 0; k < N; k++) {

data_out2[k] = temp3[k] * 456;

}

}

2. 旁路任務(wù) Bypassing Tasks

正常情況下我們期望流水線(xiàn)任務(wù)是一個(gè)接著一個(gè)的產(chǎn)出并消耗，然而像下面這個(gè)例子中，Loop1 產(chǎn)生了 Temp1和Temp2 兩個(gè)數(shù)據(jù)流，但是在下一個(gè)任務(wù) Loop2 中只有 temp1 參與了運(yùn)算，而 temp2 就被旁支了。Loop3 任務(wù)的執(zhí)行依賴(lài) Loop2 任務(wù)產(chǎn)生的 temp3 數(shù)據(jù)，所以 Loop2 和 Loop3 因?yàn)閿?shù)據(jù)依賴(lài)的關(guān)系無(wú)法并行執(zhí)行。

void foo(int data_in[N], int scale, int data_out1[N], int data_out2[N]) {

int temp1[N], temp2[N]. temp3[N];

Loop1: for(int i = 0; i < N; i++) {?

temp1[i] = data_in[i] * scale;

temp2[i] = data_in[i] >> scale;

}

Loop2: for(int j = 0; j < N; j++) {?

temp3[j] = temp1[j] + 123;

}

Loop3: for(int k = 0; k < N; k++) {?

data_out[k] = temp2[k] + temp3[k];

}

}

3. 任務(wù)間雙向反饋 Feedbackbetween Tasks

假如說(shuō)當(dāng)前任務(wù)的結(jié)果，需要作為之前一個(gè)任務(wù)的輸入的話(huà)，就形成了任務(wù)之間的數(shù)據(jù)反饋，它打亂了流水線(xiàn)從上級(jí)一直往下級(jí)輸送數(shù)據(jù)流的規(guī)則。這時(shí)候HLS就會(huì)給出警告或者報(bào)錯(cuò)，有可能完成不了dataflow優(yōu)化了。有一種特例是支持的：使用hls::stream格式的數(shù)據(jù)流反饋。

我們分析以下代碼的內(nèi)容：

當(dāng)?shù)谝粋€(gè)程序 firstProc 執(zhí)行的時(shí)候，hls::stream 格式的數(shù)據(jù)流 forwardOUT 被寫(xiě)入了初始化為10的數(shù)值 fromSecond 。由于 hls::stream 格式的數(shù)據(jù)本身不支持初始化操作，所以這樣的操作避免了違反單產(chǎn)出單消耗原則。之后的迭代里，firstProc 通過(guò) backwardIN 接口從 hls :: stream 讀取數(shù)值寫(xiě)入 forwardOUT 中。

在第二個(gè)程序 secondProc 執(zhí)行的時(shí)候，secondProc 讀取 forwardIN 上的值，將其加1，然后通過(guò)按執(zhí)行順序倒退的反饋流將其發(fā)送回 FirstProc。從第二次執(zhí)行開(kāi)始，firstProc 將使用從流中讀取的值進(jìn)行計(jì)算，并且兩個(gè)過(guò)程可以使用第一次執(zhí)行的初始值，通過(guò)正向和反饋通信永遠(yuǎn)保持下去。這種交互式的反饋中，包含數(shù)據(jù)流的雙向反饋機(jī)制，但是它就像貨物一直在從左手倒到右手再?gòu)挠沂值沟阶笫忠粯樱梢圆贿`反 Dataflow 的規(guī)范，一直進(jìn)行下去。

#include "ap_axi_sdata.h"

#include "hls_stream.h"

void firstProc(hls::stream &forwardOUT, hls::stream &backwardIN) {

static bool first = true;

int fromSecond;

//Initialize stream

if (first)

fromSecond = 10; // Initial stream value

else

//Read from stream

fromSecond = backwardIN.read(); //Feedback value

first = false;

//Write to stream

forwardOUT.write(fromSecond*2);

}

void secondProc(hls::stream &forwardIN, hls::stream &backwardOUT)

{

backwardOUT.write(forwardIN.read() + 1);

}

void top(...) {

#pragma HLS dataflow

hls::stream forward, backward;

firstProc(forward, backward);

secondProc(forward, backward);

}

4. 含有條件判斷的任務(wù)流水

DATAFLOW 優(yōu)化不會(huì)優(yōu)化有條件執(zhí)行的任務(wù)。下面的示例展現(xiàn)了這個(gè)違例。在此示例中，有條件地執(zhí)行 Loop1 和 Loop2 會(huì)阻止 Vitis HLS 優(yōu)化這些循環(huán)之間的數(shù)據(jù)流，因?yàn)?sel 條件直接控制了任務(wù)中的數(shù)據(jù)有可能不會(huì)從一個(gè)循環(huán)流到下一個(gè)循環(huán)。

void foo(int data_in1[N], int data_out[N], int sel) {

int temp1[N], temp2[N];

if (sel) {

Loop1: for(int i = 0; i < N; i++) {

temp1[i] = data_in[i] * 123;

temp2[i] = data_in[i];

}

} else {

Loop2: for(int j = 0; j < N; j++) {

temp1[j] = data_in[j] * 321;

temp2[j] = data_in[j];

}

}

Loop3: for(int k = 0; k < N; k++) {

data_out[k] = temp1[k] * temp2[k];

}

}

但是我們都知道，其實(shí)這些任務(wù)之間存在條件判斷和選擇是非常常見(jiàn)的情況，只需要稍微改變代碼風(fēng)格就可以既保留條件判斷，又完成任務(wù)流水。為了確保在所有情況下都執(zhí)行每個(gè)循環(huán)，我們將條件語(yǔ)句下變化的 Temp1 移入第一個(gè)循環(huán)。這兩個(gè)循環(huán)始終執(zhí)行，并且數(shù)據(jù)始終從一個(gè)循環(huán)流向下一個(gè)循環(huán)。

void foo(int data_in[N], int data_out[N], int sel) {

int temp1[N], temp2[N];

Loop1: for(int i = 0; i < N; i++) {

if (sel) {

temp1[i] = data_in[i] * 123;

} else {

temp1[i] = data_in[i] * 321;

}

}

Loop2: for(int j = 0; j < N; j++) {

temp2[j] = data_in[j];

}

Loop3: for(int k = 0; k < N; k++) {

data_out[k] = temp1[k] * temp2[k];

}

}

5. 有多種退出機(jī)制的循環(huán)

含有多種退出機(jī)制的循環(huán)不能被包含在流水線(xiàn)區(qū)域內(nèi)，我們來(lái)數(shù)一數(shù) Loop2 一共有多少種循環(huán)退出條件：

1. 由 for 循環(huán)定義的 K>N 的情況；

2. 由 switch 條件定義的 default 情況；

3. 由 switch 條件定義的 continue 情況

由于循環(huán)的退出條件始終由循環(huán)邊界定義，因此使用 break 或 continue 語(yǔ)句將禁止在DATAFLOW 區(qū)域中使用循環(huán)。

void multi_exit(din_t data_in[N], dsc_t scale, dsel_t select, dout_t

data_out[N]) {

dout_t temp1[N], temp2[N];

int i,k;

Loop1:

for(i = 0; i < N; i++) {

temp1[i] = data_in[i] * scale;

temp2[i] = data_in[i] >> scale;

}

Loop2:

for(k = 0; k < N; k++) {

switch(select) {

case 0: data_out[k] = temp1[k] + temp2[k];

case 1: continue;

default: break;

}

}

}

我們理解了可能阻止任務(wù)流水線(xiàn)的 5 種經(jīng)典情況后，我們最后推出適用于 Vitis HLS 的Dataflow 優(yōu)化的兩種規(guī)范形式 (canonical forms) ，一種直接應(yīng)用于函數(shù)，一種應(yīng)用于 for循環(huán)。我們可以發(fā)現(xiàn)規(guī)范形式嚴(yán)格遵守了單產(chǎn)出單消耗的規(guī)則。

1. 適用于子程序沒(méi)有被內(nèi)聯(lián) (inline) 的規(guī)范形式

void dataflow(Input0, Input1, Output0, Output1)

{

#pragma HLS dataflow

UserDataType C0, C1, C2;

func1(read Input0, read Input1, write C0, write C1);

func2(read C0, read C1, write C2);

func3(read C2, write Output0, write Output1);

}

2. 適用于循環(huán)體內(nèi)的任務(wù)流水的規(guī)范形式：

對(duì)于 for 循環(huán) (其中沒(méi)有內(nèi)聯(lián)函數(shù)的地方)，循環(huán)變量應(yīng)具有：

a. 在 for 循環(huán)的標(biāo)題中聲明初始值，并設(shè)置為 0。

b. 循環(huán)條件N是一個(gè)正數(shù)值常數(shù)或常數(shù)函數(shù)參數(shù)。

c. 循環(huán)的遞增量為1。

d. Dataflow 指令必須位于循環(huán)內(nèi)部。

void dataflow(Input0, Input1, Output0, Output1)

{

for (int i = 0; i < N; i++)

{

#pragma HLS dataflow

UserDataType C0, C1, C2;

func1(read Input0, read Input1, write C0, write C1);

func2(read C0, read C0, read C1, write C2);

func3(read C2, write Output0, write Output1);

}

}

原文標(biāo)題：Dataflow | 粗粒度并行優(yōu)化的任務(wù)級(jí)流水

文章出處：【微信公眾號(hào)：FPGA開(kāi)發(fā)圈】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq