Dataflow | 粗粒度并行優(yōu)化的任務(wù)級流水

本文轉(zhuǎn)載自：XILINX開發(fā)者社區(qū)微信公眾號

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 旁路任務(wù) Bypassing Tasks  
正常情況下我們期望流水線任務(wù)是一個接著一個的產(chǎn)出并消耗，然而像下面這個例子中，Loop1 產(chǎn)生了 Temp1和Temp2 兩個數(shù)據(jù)流，但是在下一個任務(wù) Loop2 中只有 temp1 參與了運算，而 temp2 就被旁支了。Loop3 任務(wù)的執(zhí)行依賴 Loop2 任務(wù)產(chǎn)生的 temp3 數(shù)據(jù)，所以 Loop2 和 Loop3 因為數(shù)據(jù)依賴的關(guān)系無法并行執(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 

3. 任務(wù)間雙向反饋 Feedbackbetween Tasks
假如說當(dāng)前任務(wù)的結(jié)果，需要作為之前一個任務(wù)的輸入的話，就形成了任務(wù)之間的數(shù)據(jù)反饋，它打亂了流水線從上級一直往下級輸送數(shù)據(jù)流的規(guī)則。這時候 HLS 就會給出警告或者報錯，有可能完成不了 dataflow 優(yōu)化了。有一種特例是支持的：使用 hls::stream 格式的數(shù)據(jù)流反饋。
我們分析以下代碼的內(nèi)容：
當(dāng)?shù)谝粋€程序 firstProc 執(zhí)行的時候，hls::stream 格式的數(shù)據(jù)流 forwardOUT 被寫入了初始化為10的數(shù)值 fromSecond 。由于 hls::stream 格式的數(shù)據(jù)本身不支持初始化操作，所以這樣的操作避免了違反單產(chǎn)出單消耗原則。之后的迭代里，firstProc 通過 backwardIN 接口從 hls :: stream 讀取數(shù)值寫入 forwardOUT 中。
在第二個程序 secondProc 執(zhí)行的時候，secondProc 讀取 forwardIN 上的值，將其加1，然后通過按執(zhí)行順序倒退的反饋流將其發(fā)送回 FirstProc。從第二次執(zhí)行開始，firstProc 將使用從流中讀取的值進行計算，并且兩個過程可以使用第一次執(zhí)行的初始值，通過正向和反饋通信永遠(yuǎn)保持下去。這種交互式的反饋中，包含數(shù)據(jù)流的雙向反饋機制，但是它就像貨物一直在從左手倒到右手再從右手倒到左手一樣，可以不違反 Dataflow 的規(guī)范，一直進行下去。
#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)化不會優(yōu)化有條件執(zhí)行的任務(wù)。下面的示例展現(xiàn)了這個違例。在此示例中，有條件地執(zhí)行 Loop1 和 Loop2 會阻止 Vitis HLS 優(yōu)化這些循環(huán)之間的數(shù)據(jù)流，因為 sel 條件直接控制了任務(wù)中的數(shù)據(jù)有可能不會從一個循環(huán)流到下一個循環(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];

    }

}

但是我們都知道，其實這些任務(wù)之間存在條件判斷和選擇是非常常見的情況，只需要稍微改變代碼風(fēng)格就可以既保留條件判斷，又完成任務(wù)流水。為了確保在所有情況下都執(zhí)行每個循環(huán)，我們將條件語句下變化的 Temp1 移入第一個循環(huán)。這兩個循環(huán)始終執(zhí)行，并且數(shù)據(jù)始終從一個循環(huán)流向下一個循環(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. 有多種退出機制的循環(huán)
含有多種退出機制的循環(huán)不能被包含在流水線區(qū)域內(nèi)，我們來數(shù)一數(shù) Loop2 一共有多少種循環(huán)退出條件：
    1. 由 for 循環(huán)定義的 K>N 的情況；
    2. 由 switch 條件定義的 default 情況；
    3. 由 switch 條件定義的 continue 情況
由于循環(huán)的退出條件始終由循環(huán)邊界定義，因此使用 break 或 continue 語句將禁止在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ù)流水線的 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. 適用于子程序沒有被內(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ī)范形式：
對于 for 循環(huán) (其中沒有內(nèi)聯(lián)函數(shù)的地方)，循環(huán)變量應(yīng)具有：
a. 在 for 循環(huán)的標(biāo)題中聲明初始值，并設(shè)置為 0。
b. 循環(huán)條件N是一個正數(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);

    }

 }

有關(guān) Dataflow 指令的原理，設(shè)計準(zhǔn)則和規(guī)范形式都在本文講解給大家了，更多設(shè)計例程可以參考Github（https://github.com/Xilinx/HLS-Tiny-Tutorials/tree/master/coding_dataflow... ），如有疑問歡迎交流！