數(shù)據(jù)流式編程在硬件設(shè)計(jì)中的應(yīng)用

01、數(shù)據(jù)流式編程的思想

數(shù)據(jù)流式編程思想簡(jiǎn)介

數(shù)據(jù)流式編程（Dataflow Programming）是一種存在已久的程序設(shè)計(jì)范式，可以追溯到19世紀(jì)60年代，由MIT的Jack Dennis教授開(kāi)創(chuàng)。

圖1 信號(hào)處理領(lǐng)域的數(shù)據(jù)流框圖

數(shù)據(jù)流的前身是信號(hào)流，如上圖1所示，在信號(hào)與系統(tǒng)相關(guān)的領(lǐng)域中，使用信號(hào)流框圖來(lái)表示模擬信號(hào)在一個(gè)系統(tǒng)中的處理過(guò)程。隨著計(jì)算機(jī)技術(shù)的發(fā)展，越來(lái)越多的模擬系統(tǒng)被數(shù)字系統(tǒng)所取代，連續(xù)的信號(hào)也變?yōu)榱穗x散的數(shù)據(jù)。

軟件開(kāi)發(fā)中的數(shù)據(jù)流式編程思想

在介紹硬件中的數(shù)據(jù)流式編程思想之前，先來(lái)看一下軟件中的數(shù)據(jù)流式編程，并了解數(shù)據(jù)流式編程中的幾個(gè)基本元素的概念。

圖2 一段LabView編寫的流式數(shù)據(jù)處理軟件程序

在軟件開(kāi)發(fā)領(lǐng)域，數(shù)據(jù)流式程序的開(kāi)發(fā)已經(jīng)得到了廣泛的應(yīng)用。其中頗具代表性的是NI公司的LabView軟件以及Mathworks公司的Simulink。如上圖2所示，該圖為L(zhǎng)abView可視化開(kāi)發(fā)環(huán)境中，采用圖形化編程的方式編寫的一個(gè)簡(jiǎn)易數(shù)據(jù)處理程序。觀察圖2，可以得到數(shù)據(jù)流式程序具有的一些要素：

• Node：數(shù)據(jù)處理節(jié)點(diǎn)，代表著實(shí)際的數(shù)據(jù)處理步驟（如上圖中骰子節(jié)點(diǎn)、節(jié)拍器節(jié)點(diǎn)、4輸入加法器節(jié)點(diǎn)、除法節(jié)點(diǎn)等）
  • Port：分為In和Out兩種類型，一個(gè)Node可以具有多個(gè)In和Out端口（如除法器就是2輸入1輸出）
• Source：數(shù)據(jù)源，待處理輸入通過(guò)數(shù)據(jù)源進(jìn)入到程序中（例如上述的骰子節(jié)點(diǎn)，會(huì)生成隨機(jī)數(shù)輸出，即為一個(gè)可以輸出動(dòng)態(tài)數(shù)據(jù)的Source，而圖中藍(lán)色的500、綠色的布爾節(jié)點(diǎn)則可以視為產(chǎn)生靜態(tài)常量的Source）。
• Sink：數(shù)據(jù)出口，經(jīng)過(guò)處理的數(shù)據(jù)經(jīng)過(guò)出口輸出（例如上述節(jié)拍器節(jié)點(diǎn)、右下角的紅色停止條件節(jié)點(diǎn)，它們都只有輸入沒(méi)有輸出，即接收最終數(shù)據(jù)結(jié)果）。
• Edge：連接Port與Port的邊，代表數(shù)據(jù)流通的管道

同樣，通過(guò)觀察圖2，還可以發(fā)現(xiàn)流式程序的執(zhí)行一些特點(diǎn)：

• 當(dāng)一個(gè)Node的In端口滿足觸發(fā)條件（例如任意輸入端口有數(shù)據(jù)，或所有端口都有數(shù)據(jù)），并且其Out端口不阻塞時(shí)（下游Node可以可以接收數(shù)據(jù)），該Node開(kāi)始執(zhí)行自己的處理邏輯，并將輸出數(shù)據(jù)投遞到對(duì)應(yīng)的輸出端口。
• 反壓的思想貫穿了整個(gè)程序的執(zhí)行流程，當(dāng)下游節(jié)點(diǎn)無(wú)法處理新數(shù)據(jù)時(shí)，上游節(jié)點(diǎn)的處理過(guò)程將被阻塞。
• 并發(fā)性：每個(gè)Node獨(dú)立處理自己的邏輯，Node之間是并發(fā)的
• 層次性：可以將多個(gè)Node組成的子系統(tǒng)看做一個(gè)黑箱，子系統(tǒng)的Sink和Source作為該黑箱的Port，這樣就可以把子系統(tǒng)看做上層系統(tǒng)的一個(gè)Node，從而形成層級(jí)結(jié)構(gòu)。

圖3 帶有循環(huán)、條件分支結(jié)構(gòu)的數(shù)據(jù)流式程序

近些年以來(lái)，為了實(shí)現(xiàn)敏捷化開(kāi)發(fā)而逐步流行的圖形化拖拽編程、低代碼編程等敏捷開(kāi)發(fā)方式中，通常都可以看到數(shù)據(jù)流式編程的影子。與DSP領(lǐng)域中的簡(jiǎn)單數(shù)據(jù)流思想不同，在軟件開(kāi)發(fā)領(lǐng)域的數(shù)據(jù)流程序中，通?？梢钥吹綏l件分支結(jié)構(gòu)和循環(huán)執(zhí)行結(jié)構(gòu)。因此，數(shù)據(jù)流的編程模式是圖靈完備的，不僅可以用于表示簡(jiǎn)單的數(shù)據(jù)計(jì)算流程，還可以表達(dá)復(fù)雜的控制流。

如上圖3所示即為一款兒童編程軟件的示意圖，讀者可以嘗試在上面的圖中找出Source、Sink、Node、Port、Edge這些概念。

軟件數(shù)據(jù)流 vs 硬件數(shù)據(jù)流

軟件實(shí)現(xiàn)：

數(shù)據(jù)流系統(tǒng)都需要一套調(diào)度框架，所有節(jié)點(diǎn)之間的并行執(zhí)行都是軟件虛擬出來(lái)的，節(jié)點(diǎn)是否可以激活的判斷需要框架進(jìn)行額外的計(jì)算，因此性能開(kāi)銷不能忽略。

硬件實(shí)現(xiàn):

硬件天然具有并發(fā)的特性。端口、連線、層級(jí)結(jié)構(gòu)、反壓、并發(fā)執(zhí)行這些概念與硬件設(shè)計(jì)有著完美的對(duì)應(yīng)關(guān)系。事實(shí)上，Verilog、VHDL等語(yǔ)言本身也可以被算作是和LabView、Simulink一樣的數(shù)據(jù)流式程序的開(kāi)發(fā)語(yǔ)言[1]。

數(shù)據(jù)流思想與狀態(tài)機(jī)思想的對(duì)比

在很多場(chǎng)景下，如果使用狀態(tài)機(jī)的思想對(duì)硬件行為進(jìn)行建模，則需要考慮很多狀態(tài)之間的轉(zhuǎn)換關(guān)系，容易造成狀態(tài)爆炸。而是用數(shù)據(jù)流的編程思想，只需要考慮數(shù)據(jù)在兩個(gè)節(jié)點(diǎn)之間的傳輸關(guān)系以及各個(gè)節(jié)點(diǎn)自己要做的事情，每個(gè)節(jié)點(diǎn)各司其職，可以有效降低程序的復(fù)雜度。

下面以AXI4協(xié)議的寫通道握手為例，寫地址通道和寫數(shù)據(jù)通道之間沒(méi)有明確的先后依賴順序。

圖4 AXI握手協(xié)議的順序關(guān)系

圖5 一個(gè)最簡(jiǎn)單的狀態(tài)機(jī)握手模型，忽略了其他狀態(tài)

如果以狀態(tài)機(jī)的思路來(lái)實(shí)現(xiàn)，是上述圖5這樣的，它是一種順序化執(zhí)行的思維模式，依次進(jìn)行各個(gè)通道上的握手，難以描述并行發(fā)生的事件。如果強(qiáng)行使用狀態(tài)機(jī)來(lái)描述并發(fā)場(chǎng)景下各種可能的先后順序，則容易導(dǎo)致?tīng)顟B(tài)爆炸，維護(hù)成本高，不夠敏捷。

圖6 基于數(shù)據(jù)流思想的握手模型

如果以數(shù)據(jù)流的思想來(lái)實(shí)現(xiàn)，則如上述圖6所示，4個(gè)環(huán)節(jié)之間各自獨(dú)立運(yùn)行，各司其職，兩個(gè)輸入通道以及一個(gè)輸出通道是獨(dú)立模塊，各自可以并行的完成自己的握手，模塊與模塊之間通過(guò)Skid Buf(FIFO)進(jìn)行解耦?？梢造`活應(yīng)對(duì)各種握手信號(hào)到達(dá)的先后順序，可以寫出易于維護(hù)且吞吐量高的代碼。

02、Bluespec語(yǔ)言及其流式編程框架PAClib

Bluespec SystemVerilog(BSV)和PAClib簡(jiǎn)介

Bluespec SystemVerilog是一種高級(jí)的函數(shù)式硬件描述語(yǔ)言，由MIT的Arvind教授開(kāi)發(fā)，最初以商業(yè)授權(quán)形式發(fā)布，并于2020年正式開(kāi)源。

該語(yǔ)言將硬件行為抽象成多個(gè)可以并發(fā)運(yùn)行的Rule，Rule由觸發(fā)邏輯來(lái)控制其運(yùn)行時(shí)機(jī)，Rule之間、Module之間可以通過(guò)FIFO進(jìn)行通信建模，編譯器會(huì)自動(dòng)生成Module之間的握手和反壓信號(hào)（即Rule的觸發(fā)邏輯），從而降低了描述復(fù)雜并行系統(tǒng)的難度,使得它非常適合使用數(shù)據(jù)流的思想進(jìn)行開(kāi)發(fā)。

PAClib是Pipelined Architecture Composers library的縮寫，是BSV提供的一個(gè)官方庫(kù)，可以方便的開(kāi)發(fā)出基于數(shù)據(jù)流思想設(shè)計(jì)的硬件邏輯。

與DSP領(lǐng)域的流式處理相比，PAClib提供了諸如If-Else-Then、While Loop、For Loop、Fork、Join等操作，因此PAClib所提供的數(shù)據(jù)流式編程框架是圖靈完備的，不僅可以用于對(duì)復(fù)雜數(shù)據(jù)流邏輯的描述，也可以用于對(duì)復(fù)雜控制流的描述。

PAClib中的基礎(chǔ)開(kāi)發(fā)組件

PACLib中的基礎(chǔ)組件可以看做是流式編程中的各個(gè)節(jié)點(diǎn)，為了使用流式編程，需要首先了解各個(gè)節(jié)點(diǎn)的功能，然后才能將這些節(jié)點(diǎn)連接起來(lái)，從而形成完整的程序。下面首先介紹這些節(jié)點(diǎn)的通用形式，即PAClib中定義的PipeOut接口以及Pipe類型，其定義如下：

interface PipeOut #(type a); 
    method a first ();
    method Action deq ();
    method Bool notEmpty (); 
endinterface


typedef (function Module #(PipeOut #(b)) mkPipeComponent (PipeOut #(a) ifc)) 
    Pipe#(type a, type b);

上述PipeOut接口的形式類似于一個(gè)FIFO，即為一條數(shù)據(jù)通道的出口端。Pipe類型本質(zhì)是一個(gè)函數(shù)，用來(lái)把一個(gè)PipeOut類型的輸入轉(zhuǎn)換為另一個(gè)PipeOut類型的輸出模塊，因此Pipe類型表示了一個(gè)連接并轉(zhuǎn)換的概念。

圖7 Pipe類型的圖形化示意

上述圖7可以幫助大家更形象的理解Pipe類型和PipeOut接口，其中整個(gè)節(jié)點(diǎn)可以看做是一個(gè)Pipe，數(shù)據(jù)從左側(cè)流入，從右側(cè)流出，并在流經(jīng)節(jié)點(diǎn)的過(guò)程中被處理（處理的過(guò)程在下文介紹）。其中右側(cè)突出的部分是用于和下一個(gè)節(jié)點(diǎn)（也就是下一段Pipe）連接的接口，即PipeOut。Pipe和PipeOut類型提供了數(shù)據(jù)流程序中各個(gè)節(jié)點(diǎn)的統(tǒng)一接口規(guī)范，所有基于PAClib開(kāi)發(fā)的處理邏輯都要用這兩個(gè)概念進(jìn)行包裝，從而使得各個(gè)節(jié)點(diǎn)之間具有一定的互換性，為架構(gòu)提供了很強(qiáng)的靈活性。

將函數(shù)包裝為Pipe

Pipe類型只是定義了數(shù)據(jù)流經(jīng)過(guò)一個(gè)節(jié)點(diǎn)前后的數(shù)據(jù)類型，因此還需要具體的邏輯來(lái)實(shí)現(xiàn)從類型A到類型B的轉(zhuǎn)換。由于函數(shù)的本質(zhì)就是做映射，因此使用函數(shù)來(lái)表達(dá)對(duì)數(shù)據(jù)的加工過(guò)程再合適不過(guò)了。mkFn_to_Pipe_buffered是一個(gè)工具函數(shù)，提供了將一個(gè)函數(shù)封裝為一個(gè)Pipe的能力，其定義如下：

function Pipe #(ta, tb) mkFn_to_Pipe_buffered (Bool paramPre, 
                                               tb fn (ta x), 
                                               Bool paramPost);

圖8 mkFn_to_Pipe_buffered工具函數(shù)所生成的Pipe節(jié)點(diǎn)示意圖

這里的用法也體現(xiàn)出了BSV函數(shù)式編程語(yǔ)言的特性，函數(shù)是語(yǔ)言中的一等公民。事實(shí)上，PAClib中對(duì)數(shù)據(jù)流模式中各個(gè)節(jié)點(diǎn)之間的“連線”也是通過(guò)高階函數(shù)的嵌套來(lái)實(shí)現(xiàn)的。

兩個(gè)Bool類型的參數(shù)可以選擇是否在函數(shù)的前后加入FIFO隊(duì)列進(jìn)行緩沖。如果前后兩個(gè)FIFO都不開(kāi)啟，則該節(jié)點(diǎn)表現(xiàn)出組合邏輯的性質(zhì)。開(kāi)啟FIFO后，則表現(xiàn)出了流水線的性質(zhì)。通過(guò)FIFO實(shí)現(xiàn)前后級(jí)節(jié)點(diǎn)之間的反壓邏輯，自動(dòng)適應(yīng)不同的數(shù)據(jù)流速。

Map操作

map是函數(shù)式編程中必不可少的一個(gè)功能，PAClib中也提供了不同形式的map功能：

• mkMap用于將Vector中的每一個(gè)元素并行地進(jìn)行處理。
• mkMap_indexed則在mkMap的基礎(chǔ)之上，額外提供了元素對(duì)應(yīng)的索引信息，從而使得用于map的函數(shù)可以獲得關(guān)于被處理數(shù)據(jù)的位置信息。這兩個(gè)函數(shù)的定義如下：

function Pipe #(Vector #(n, a),
                Vector #(n, b)) 
         mkMap (Pipe #(a, b) mkP);


function Pipe #(Vector #(n, a),
                Vector #(n, b))
         mkMap_indexed (Pipe #(Tuple2 #(a, UInt #(logn)), b) mkP);

圖9 mkMap節(jié)點(diǎn)的圖形化示意

如上圖9所示，展示了mkMap節(jié)點(diǎn)的示意圖，可以看到圖中用深淺兩種顏色表示了嵌套的Pipe類型，圖中不同Pipe類型的嵌套表示了Node之間的層級(jí)關(guān)系，本質(zhì)上是通過(guò)高階函數(shù)實(shí)現(xiàn)了簡(jiǎn)單邏輯的組合。

由于BSV靜態(tài)展開(kāi)的原因，如果Vector長(zhǎng)度較大，則會(huì)產(chǎn)生出很多個(gè)mkP的實(shí)例（mkP實(shí)例的數(shù)量與輸入向量的長(zhǎng)度相同），占用大量面積。為了減少面積占同，用時(shí)間換空間，則可以使用接下來(lái)要介紹的節(jié)點(diǎn)。

分批Map操作

PAClib中提供了mkMap_with_funnel_indexed函數(shù)來(lái)創(chuàng)建支持分批Map操作的處理節(jié)點(diǎn)，從而可以在面積和吞吐率之間進(jìn)行取舍，其定定義如下：

function Pipe #(Vector #(nm, a),
                Vector #(nm, b))
         mkMap_with_funnel_indexed (UInt #(m) dummy_m,
                                    Pipe #(Tuple2 #(a, UInt #(lognm)), b) mkP,
                                    Bool param_buf_unfunnel)
         provisos (...);

圖10 mkMap_with_funnel_indexed工具函數(shù)所創(chuàng)建的處理流程

mkMap_with_funnel_indexed函數(shù)實(shí)際上是一個(gè)工具函數(shù)，該工具函數(shù)幫助用戶創(chuàng)建了3個(gè)Pipe的組合，其中mkMap節(jié)點(diǎn)已經(jīng)介紹過(guò)了，另外兩個(gè)節(jié)點(diǎn)分別是mkFunnel_Indexed和mkUnfunnel，其定義如下：

function Pipe #(Vector #(nm, a),
                Vector #(m, Tuple2 #(a, UInt #(lognm))))
         mkFunnel_Indexed
         provisos (...);

function Pipe #(Vector #(m, a),
                Vector #(nm, a)) 
         mkUnfunnel (Bool state_if_k_is_1)
         provisos (...);

上述兩個(gè)節(jié)點(diǎn)的作用，第一個(gè)是將一個(gè)較長(zhǎng)的向量輸入以指定的長(zhǎng)度進(jìn)行切分，從而產(chǎn)生多個(gè)批次的輸出。而第二個(gè)是接收多個(gè)批次較短的輸入，然后產(chǎn)生一個(gè)較長(zhǎng)的輸出，即把之前切分的批次重新拼接回來(lái)。mkMap_with_funnel_indexed函數(shù)通過(guò)上述3個(gè)節(jié)點(diǎn)的組合，其實(shí)現(xiàn)的最終功能為：

• 指定一個(gè)參數(shù)m，輸入的Vector會(huì)被自動(dòng)切分為多段，每段的長(zhǎng)度為m，然后以m長(zhǎng)度的切片為單位進(jìn)行map操作。
• 在實(shí)際設(shè)計(jì)中，只需要調(diào)整參數(shù)m的值就可以很方便的在面積和吞吐率之間進(jìn)行平衡。串并轉(zhuǎn)換功能由框架自動(dòng)完成，開(kāi)發(fā)者只需要把精力放在核心的mkP 節(jié)點(diǎn)即可。

節(jié)點(diǎn)的串聯(lián)

上述的mkMap_with_funnel_indexed函數(shù)將3個(gè)特定的節(jié)點(diǎn)進(jìn)行了串聯(lián)，從而實(shí)現(xiàn)了更加復(fù)雜的邏輯。將簡(jiǎn)單節(jié)點(diǎn)進(jìn)行串聯(lián)是流式編程中必不可少的操作，為了將任意節(jié)點(diǎn)進(jìn)行串聯(lián)，可以使用mkCompose和mkLinearPipe這兩個(gè)函數(shù)實(shí)現(xiàn)，其定義如下：

function Pipe #(a, c) mkCompose (Pipe #(a, b) mkP, 
                                 Pipe #(b, c) mkQ);

圖11 mkCompose節(jié)點(diǎn)示意圖

function Pipe #(a, a)
         mkLinearPipe_S (Integer n,
                         function Pipe #(a,a) mkStage (UInt #(logn) j));

圖12 mkLinearPipe節(jié)點(diǎn)示意圖

可以看到，mkCompose的作用是將兩個(gè)不同的Pipe進(jìn)行串接，多個(gè)mkCompose嵌套使用則可以實(shí)現(xiàn)多級(jí)的串接。而mkLinearPipe_S是將同一個(gè)函數(shù)進(jìn)行多次調(diào)用，但每次調(diào)用時(shí)會(huì)傳入不同的參數(shù)，從而使得這個(gè)函數(shù)可以在不同的調(diào)用位置上表現(xiàn)出不同的行為。

Fork和Join操作

上述介紹的節(jié)點(diǎn)都是對(duì)數(shù)據(jù)進(jìn)行線性操作的節(jié)點(diǎn)，如果只有這樣的節(jié)點(diǎn)是無(wú)法實(shí)現(xiàn)圖靈完備的數(shù)據(jù)流式程序的，接下來(lái)介紹的幾個(gè)非線性操作節(jié)點(diǎn)可以使得程序變得圖靈完備。下面從mkFork和mkJoin兩個(gè)函數(shù)開(kāi)始介紹：

module mkFork #(function Tuple2 #(b, c) fork_fn (a va),
                PipeOut #(a) poa)
       (Tuple2 #(PipeOut #(b), PipeOut #(c)));
       

module mkJoin #(function c join_fn (a va, b vb),
                PipeOut #(a)       poa,
                PipeOut #(b)       pob )
       (PipeOut #(c));

圖13 mkFork與mkJoin節(jié)點(diǎn)的示意圖

mkFork和mkJoin可以創(chuàng)建簡(jiǎn)單的并行結(jié)構(gòu)，通過(guò)用戶自己提供的函數(shù)fork_fn和join_fn，由用戶決定如何將一個(gè)輸入數(shù)據(jù)流拆分成2個(gè)輸出數(shù)據(jù)流，以及如何把兩個(gè)輸入數(shù)據(jù)流合并為一個(gè)輸出數(shù)據(jù)流。

對(duì)于Join操作而言，要求兩個(gè)輸入端口上均存在數(shù)據(jù)時(shí)，該Node才可以執(zhí)行操作，如果兩條路徑上處理數(shù)據(jù)所需的時(shí)鐘周期數(shù)不一致，則Join節(jié)點(diǎn)會(huì)進(jìn)行等待，直到兩個(gè)輸入都有數(shù)據(jù)為止。此外，PAClib中還提供了多種Fork節(jié)點(diǎn)的變種實(shí)現(xiàn)，可以自行了解。

條件分支操作

使用mkIfThenElse可以創(chuàng)建條件分支，其定義及示意圖如下：

module [Module] mkIfThenElse #(Integer                        latency,
                               Pipe #(a,b)                    pipeT,
                               Pipe #(a,b)                    pipeF,
                               PipeOut #(Tuple2 #(a, Bool))   poa)
                (PipeOut #(b));

圖14 mkIfThenElse節(jié)點(diǎn)示意圖

mkIfThenElse可以實(shí)現(xiàn)分支邏輯。輸入數(shù)據(jù)是一個(gè)Tuple2#(a, Bool)類型，該節(jié)點(diǎn)會(huì)根據(jù)Bool類型的取值將數(shù)據(jù)包路由到pipeT或者pipeF子節(jié)點(diǎn)。其內(nèi)部具有一個(gè)FIFO結(jié)構(gòu)用于存儲(chǔ)Token，從而實(shí)現(xiàn)在pipeT和pipeF兩個(gè)節(jié)點(diǎn)所需處理周期不一致時(shí)起到保序的作用。

此外，PAClib中還提供了mkIfThenElse_unordered變種實(shí)現(xiàn)，當(dāng)對(duì)輸入和輸出之間的數(shù)據(jù)沒(méi)有嚴(yán)格的順序要求時(shí)，可以使用這個(gè)變種來(lái)簡(jiǎn)化設(shè)計(jì)。For循環(huán) 使用mkForLoop可以創(chuàng)建條件分支，其定義及示意圖如下：

module [Module] mkForLoop #(Integer                            n_iters,
                            Pipe #(Tuple2 #(a, UInt #(wj)),
                                   Tuple2 #(a, UInt #(wj)))    mkLoopBody,
                            Pipe #(a,b)                        mkFinal,
                            PipeOut #(a)                       po_in)
                (PipeOut #(b))
                provisos (Bits #(a, sa));

圖15 mkForLoop節(jié)點(diǎn)示意圖

mkForLoop需要通過(guò)n_iters參數(shù)傳入循環(huán)次數(shù)。在實(shí)現(xiàn)邏輯上，Loop Control Logic內(nèi)部有一個(gè)共享隊(duì)列，外部進(jìn)入的新數(shù)據(jù)和經(jīng)過(guò)循環(huán)體執(zhí)行過(guò)一次處理的數(shù)據(jù)，都會(huì)被放到這個(gè)隊(duì)列中。

每個(gè)新進(jìn)入的數(shù)據(jù)都會(huì)被打上一個(gè)Tag，Tag的值為循環(huán)次數(shù)，這個(gè)Tag伴隨著數(shù)據(jù)在循環(huán)中流動(dòng)，每流動(dòng)一次，Tag減一，Loop Control Logic在從共享隊(duì)列中取出數(shù)據(jù)時(shí)，會(huì)根據(jù)Tag的計(jì)數(shù)值決定將其送入mkLoopBody節(jié)點(diǎn)還是mkFinal節(jié)點(diǎn)。內(nèi)部有兩條Rule，分別獨(dú)立負(fù)責(zé)把新數(shù)據(jù)和正在循環(huán)的數(shù)據(jù)放入FIFO中，為循環(huán)提供了內(nèi)在動(dòng)力（圖中Pump標(biāo)注路徑）。

注意，由于mkLoopBody也可能是一個(gè)需要多拍才能完成的節(jié)點(diǎn)，因此可以有多個(gè)數(shù)據(jù)包同時(shí)在流水線中進(jìn)行循環(huán)。

While循環(huán)

在理解了For循環(huán)的實(shí)現(xiàn)原理之后，理解While循環(huán)的實(shí)現(xiàn)就沒(méi)有太大困難了。其定義和示意圖如下：

module [Module] mkWhileLoop #(Pipe #(a,Tuple2 #(b, Bool))  mkPreTest,
                              Pipe #(b,a)                  mkPostTest,
                              Pipe #(b,c)                  mkFinal,
                              PipeOut #(a) po_in)
                (PipeOut #(c))
        provisos (Bits #(a, sa));

圖16 mkWhileLoop節(jié)點(diǎn)示意圖

while循環(huán)的實(shí)現(xiàn)需要用戶提供3個(gè)處理節(jié)點(diǎn)：

• mkPreTest子節(jié)點(diǎn)用于執(zhí)行循環(huán)終止條件的判斷
• mkPostTest子節(jié)點(diǎn)是循環(huán)體要做的處理邏輯
• mkFinal子節(jié)點(diǎn)是循環(huán)體退出前對(duì)數(shù)據(jù)再進(jìn)行一次修改的機(jī)會(huì) 其實(shí)現(xiàn)邏輯與For循環(huán)類似，都是通過(guò)內(nèi)部共享一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)的，同時(shí)通過(guò)兩條Rule來(lái)為循環(huán)提供動(dòng)力。

03、IFFT應(yīng)用實(shí)例

需求背景

圖17 一個(gè)IFFT數(shù)據(jù)處理流程

以上述圖17中的IFFT變換為例，該流程中有很多平鋪重復(fù)的結(jié)構(gòu)，對(duì)于不同的應(yīng)用場(chǎng)景，需要在面積、吞吐量之間進(jìn)行平衡，例如：

• 組合邏輯實(shí)現(xiàn)？還是流水線實(shí)現(xiàn)？
• 幾個(gè)不同的stage之間是否可以fold以減少面積？
• 每個(gè)stage內(nèi)部的f_radix4實(shí)例是否可以減少？

代碼實(shí)現(xiàn)

使用PAClib提供的數(shù)據(jù)流式開(kāi)發(fā)框架，只需要調(diào)整少量參數(shù)就可以快速調(diào)整系統(tǒng)的計(jì)算結(jié)構(gòu)。下面先給出整體代碼，再對(duì)其中的各個(gè)部分進(jìn)行解析，可以看到，整體框架的代碼量小于40行（僅包含用于調(diào)度數(shù)據(jù)流的框架代碼，不包含具體的運(yùn)算邏輯以及注釋）：

module [Module] mkIFFT (Server#(IFFTData, IFFTData));
    Bool param_linear_not_looped = False;
    Integer jmax = 2;
    FIFO#(IFFTData) tf < - mkFIFO;

    function Tuple2#(IFFTData, UInt#(6)) stage_d(Tuple2#(IFFTData, UInt#(6)) a);
        return a;
    endfunction

    let mkStage_D = mkFn_to_Pipe (stage_d);

    let s < - mkPipe_to_Server
                ( param_linear_not_looped
                    ? mkLinearPipe_S (3, mkStage_S)
                    : mkForLoop (jmax, mkStage_D, mkFn_to_Pipe (id)));
    return s;
endmodule

function Pipe #(IFFTData, IFFTData) mkStage_S (UInt#(2) stagenum);
    UInt#(1) param_dummy_m = ?;
    Bool param_buf_permuter_output = True;
    Bool param_buf_unfunnel = True;

    function f_radix4(UInt#(2) stagenum, 
                                    Tuple2#(Vector#(4, ComplexSample), UInt#(4)) element);
        return tpl_1(element);
    endfunction

    // ---- Group 64-vector into 16-vector of 4-vectors
    let grouper = mkFn_to_Pipe (group);
    // ---- Map f_radix4 over the 16-vec
    let mapper = mkMap_fn_with_funnel_indexed ( param_dummy_m,
                                                f_radix4 (stagenum),
                                                param_buf_unfunnel);
    // ---- Ungroup 16-vector of 4-vectors into a 64-vector
    let ungrouper = mkFn_to_Pipe (ungroup);
    // ---- Permute it
    let permuter = mkFn_to_Pipe_Buffered (False, f_permute,
                                            param_buf_permuter_output);
    return mkCompose (grouper,
                        mkCompose (mapper,
                                    mkCompose (ungrouper, permuter)));
endfunction

下面來(lái)依次解析代碼，首先下面看這一段：

let s < - mkPipe_to_Server
                ( param_linear_not_looped
                    ? mkLinearPipe_S (3, mkStage_S)
                    : mkForLoop (jmax, mkStage_D, mkFn_to_Pipe (id)));

圖18 平鋪結(jié)構(gòu)的IFFT計(jì)算架構(gòu)

圖19 折疊結(jié)構(gòu)的IFFT計(jì)算架構(gòu)

如上圖18和19所示，只需要修改代碼中的param_linear_not_looped變量，即可以在兩種截然不同的計(jì)算架構(gòu)之間進(jìn)行切換。通過(guò)選擇mkLinerPipe_S或者mkForLoop來(lái)選擇stage之間是流水線平鋪的方式來(lái)實(shí)現(xiàn)，還是通過(guò)Fold的方式來(lái)實(shí)現(xiàn)。

let mapper = mkMap_fn_with_funnel_indexed ( param_dummy_m,
                                                f_radix4 (stagenum),
                                                param_buf_unfunnel);

圖20 通過(guò)參數(shù)調(diào)整計(jì)算的并發(fā)度

如上述代碼片段和圖20所示，通過(guò)mkMap_fn_with_funnel_indexed函數(shù)的第一個(gè)參數(shù)來(lái)決定實(shí)例化多少個(gè)f_radix4計(jì)算單元，從而改變計(jì)算的并行度。

let permuter = mkFn_to_Pipe_Buffered (False, f_permute,
                                            param_buf_permuter_output);

圖21 在不同位置插入流水線寄存器

如上述代碼片段和圖21所示，通過(guò)mkFn_to_Pipe_Buffered函數(shù)的兩個(gè)輸入?yún)?shù)來(lái)控制是否加入FIFO，從而實(shí)現(xiàn)在流水線或組合邏輯之間的切換，使得程序可以在時(shí)序上做出簡(jiǎn)單的調(diào)整。

return mkCompose (grouper,
                        mkCompose (mapper,
                                    mkCompose (ungrouper, permuter)));

圖22 節(jié)點(diǎn)的串聯(lián)

如上述代碼片段和圖22所示，通過(guò)mkCompose可以實(shí)現(xiàn)多個(gè)Node之間的順序連接。

最終效果

圖23 使用PAClib實(shí)現(xiàn)的各種IFFT計(jì)算架構(gòu)

在最終效果部分，直接引用Bluespec原始介紹PPT[2]中的一個(gè)頁(yè)面來(lái)進(jìn)行說(shuō)明，使用不超過(guò)100行代碼，僅需要調(diào)整4個(gè)參數(shù)，即可實(shí)現(xiàn)在24種不同的計(jì)算架構(gòu)之間進(jìn)行切換，這24中計(jì)算架構(gòu)在面積和功耗上的差異可以達(dá)到10倍以上，用戶可以根據(jù)自己的使用場(chǎng)景靈活的選擇實(shí)現(xiàn)方案。

04、寫在最后

從上述示例可以看到數(shù)據(jù)流式的編程思想可以為硬件設(shè)計(jì)引入極大的靈活性和可維護(hù)性。同時(shí)，由于分支節(jié)點(diǎn)、條件節(jié)點(diǎn)、循環(huán)節(jié)點(diǎn)的存在，這種數(shù)據(jù)流式的編程模式是圖靈完備的，因此數(shù)據(jù)流的開(kāi)發(fā)思想可以用于簡(jiǎn)化復(fù)雜的控制通路設(shè)計(jì)。