VALID 信号と READY 信号によるデータフロー制御 (Join 編)

# はじめに


データフローマシンは、必要なデータが揃い次第演算を行う非ノイマン型の計算方式です。データフローで用いられるノードには、次の図の４種類あります。


![Fig.1 データフローノード](https://qiita-image-store.s3.amazonaws.com/0/24981/14b60c04-2eab-5177-2926-c2db610266bf.jpeg "Fig.1 データフローノード")



Fig.1 データフローノード

<br />



この記事ではデータフローノードの一つである Fork を VALID 信号と READY 信号を使って制御する方法について説明します。



VALID 信号と READY 信号のハンドシェイクに関しては以下の記事を参照してください。この記事で VALID-and-READY 、VALID-then-READY、READY-then-VALID の各種ハンドシェイク方法を説明しています。



* [VALID 信号と READY 信号によるハンドシェイクの注意点 @Qiita](http://qiita.com/ikwzm/items/9736b5547cb15309af5c)




# データフローの Join パターン


Join は一つの入力側ノードが複数の出力側ノードからデータを入力するパターンです。


![Fig.2 データフローの Join パターン](https://qiita-image-store.s3.amazonaws.com/0/24981/9d24a5fd-a7d3-f2ef-3b1f-b1cfe5265ace.jpeg "Fig.2 データフローの Join パターン")


Fig.2 データフローの Join パターン

<br />



Join パターンには幾つかあります。

上の図の左のように、もともと入力側ノードは一つのノードからのデータを受け取るように作られていて、データは複数のノードからの出力をマージするパターン。

上の図の右のように、入力側ノードが複数のノードからデータを受け取るように作られているパターン。例えば、複数の入力を受けて何か演算処理を行うノードの場合がこれに該当します。この場合、入力側ノード内にデータフロー制御回路があります。

この記事では、この両方を Join パターンとして扱います。




# VALID-then-READY プロトコルに基づいた制御


VALID-then-READY プロトコルのように、「出力側ノードは VALID 信号を High レベルにするために READY 信号が High レベルになるのを待ってはならないが、入力側ノードは READY 信号を High レベルにするために VALID 信号が High レベルになるのを待ってもかまわない」という規則がある場合、VALID 信号と READY 信号は次の図のように制御することができます。


![Fig.3 VALID-then-READY プロトコルに基づいたデータフロー(Join)制御回路](https://qiita-image-store.s3.amazonaws.com/0/24981/a81039ce-d80b-bc26-7f4f-fa295357d42b.jpeg "Fig.3 VALID-then-READY プロトコルに基づいたデータフロー(Join)制御回路")


Fig.3 VALID-then-READY プロトコルに基づいたデータフロー(Join)制御回路

<br />

この制御回路は次のように動作します。

* 出力側ノードからのすべての VALID 信号が High レベルになるまで、入力側ノードへの VALID 信号を Low レベルにします。
* 出力側ノードからのすべての VALID 信号が High レベルになるまで、(入力側ノードからの READY 信号の値に関係なく)出力側ノードへの READY 信号を Low レベルにします。
* 出力側ノードからのすべての VALID 信号が High レベルになったら、入力側ノードへの VALID 信号を High レベルにします。
* 出力側ノードからのすべての VALID 信号が High レベルになったら、入力側ノードからの READY 信号の値を出力側ノードへ伝達します。



「出力側ノードはVALID 信号を High レベルにするために READY 信号が High レベルになるのを待ってはならない」という規則があるので、このような簡単な回路で制御することができます。

また、この制御回路自体が、「出力側への READY 信号を High レベルにするために出力側からの VALID 信号が High レベルになるのを待っている」ので、「入力側(ここでは制御回路のこと)は READY 信号を High レベルにするために VALID 信号が High レベルになるのを待ってもかまわない」という規則が必要です。

# VALID-and-READY プロトコルに基づいた制御


VALID-and-READY プロトコルには、「入力側は READY 信号を High レベルにするために VALID 信号が High レベルになるのを待ってはならない」という規則があります。この規則があるため、VALID-then-READY プロトコルに基づいた制御で説明した簡易な制御回路は使えません。何故なら、あの簡易な制御回路を使うことで、この規則を守れなくなるからです。あの簡易な制御回路自体が、READY 信号を High レベルにするために VALID 信号が High レベルになるのを待っている論理になっているからです。

VALID-and-READY プロトコルの場合は、次図のような制御回路で制御することができます。


![Fig.4 VALID-and-READY プロトコルに基づいたデータフロー(Join)制御回路](https://qiita-image-store.s3.amazonaws.com/0/24981/516ff296-449a-f56c-d988-aad72dffa84a.jpeg "Fig.4 VALID-and-READY プロトコルに基づいたデータフロー(Join)制御回路")


Fig.4 VALID-and-READY プロトコルに基づいたデータフロー(Join)制御回路

<br />



この制御回路は次のように動作します。

* 出力側ノードからのすべての VALID 信号が High レベルになるまで、入力側ノードへの VALID 信号を Low レベルにします。
* 出力側ノードからの「対象ノード以外の」すべての VALID 信号が High レベルになるまで、(入力側ノードからの READY 信号の値に関係なく)対象の出力側ノードへの READY 信号を Low レベルにします。
* 出力側ノードからのすべての VALID 信号が High レベルになったら、入力側ノードへの VALID 信号を High レベルにします。
* 出力側ノードの「対象ノード以外の」すべての VALID 信号が High レベルになったら、入力側ノードからの READY 信号の値を対象の出力側ノードへ伝達します。



この制御回路は VALID-then-READY プロトコルでも使用することができます。



# READY-then-VALIDプロトコルに基づいた制御

## データフロー制御回路による制御

READY-then-VALID プロトコルのように、「出力側ノードは VALID 信号を High レベルにするために READY 信号が High レベルになるのを待ってもかまわない」という規則がある場合、前節、前前節で説明した簡易な制御回路は使えません。

もし出力側ノードのどれかが、「出力側ノードは VALID 信号を High レベルにするために READY 信号が High レベルになるのを待ってもかまわない」という規則に基づいて、VALID 信号を Low レベルにしたまま READY 信号が High レベルになるのを待っていた場合、前節の制御回路では永遠に READY 信号が High レベルにならず、デッドロック状態になります。

また、出力側ノードがミーリマシンだった場合、コンビネーションループが発生します。



したがって、READY-then-VALID プロトコルの場合は、次図のように制御する必要があります。


![Fig.5 READY-then-VALID プロトコルに基づいたデータフロー(Join)制御](https://qiita-image-store.s3.amazonaws.com/0/24981/d0664335-b6af-c45e-8af6-9148ae54e10a.jpeg "Fig.5 READY-then-VALID プロトコルに基づいたデータフロー(Join)制御")


Fig.5 READY-then-VALID プロトコルに基づいたデータフロー(Join)制御

<br />

READY-then-VALID プロトコルの場合、出力側ノードはREADY 信号が High レベルになるのを待っている可能性があるため、うかつに出力側ノードへの READY 信号を Low レベルにすることができません。出力側のノードへのREADY 信号を High レベルにしている時に出力側のノードが VALID 信号を High レベルにして有効なデータを出力すると、その時点でデータの転送が完了してしまいます。そのため、複数の出力側ノードからのデータ転送の完了が異なるタイミングで発生する可能性があります。入力側ノードへのデータ転送のタイミングを揃えるためには、各出力側ノード毎に転送されたデータの値を保持するレジスタが必要です。



Fig.5 の DataFlow_Join_Valve をVHDL で記述すると次のようになります。


```VHDL
library IEEE;
use     IEEE.std_logic_1164.all;
entity  DataFlow_Join_Valve is
    generic (
        WIDTH         : positive := 8;
        NUM           : positive := 2
    );
    port (
        CLOCK         : in  std_logic;
        RESET         : in  std_logic;
        I_DATA        : in  std_logic_vector(WIDTH-1 downto 0);
        I_VALID       : in  std_logic;
        I_READY       : out std_logic;
        O_DATA        : out std_logic_vector(WIDTH-1 downto 0);
        O_VALID       : out std_logic;
        O_READY       : in  std_logic;
        SYNC_O        : out std_logic;
        SYNC_I        : in  std_logic_vector(NUM  -1 downto 0)
    );
end DataFlow_Join_Valve;
 
architecture RTL of DataFlow_Join_Valve is
    type      STATE_TYPE  is (RUN_STATE, HOLD_STATE);
    signal    state      :  STATE_TYPE;
    signal    hold_data  :  std_logic_vector(WIDTH-1 downto 0);
    constant  SYNC_ALL   :  std_logic_vector(  NUM-1 downto 0) := (others => '1');
begin
    process(CLOCK, RESET) begin
        if (RESET = '1') then
            state     <= RUN_STATE;
            hold_data <= (others => '0');
        elsif (CLOCK'event and CLOCK = '1') then
            case state is
                when RUN_STATE   =>
                    if (I_VALID = '1' and O_READY = '1' and SYNC_I /= SYNC_ALL) then
                        state <= HOLD_STATE;
                    else
                        state <= RUN_STATE;
                    end if;
                    hold_data <= I_DATA;
                when HOLD_STATE =>
                    if (SYNC_I = SYNC_ALL) then
                        state <= RUN_STATE;
                    else
                        state <= HOLD_STATE;
                    end if;
                when others =>
                        state <= RUN_STATE;
            end case;
        end if;
    end process;
    SYNC_O  <= '1'        when (state  = RUN_STATE and I_VALID = '1') or
                               (state  = HOLD_STATE                 ) else '0';
    I_READY <= '1'        when (state  = RUN_STATE and O_READY = '1') else '0';
    O_VALID <= '1'        when (SYNC_I = SYNC_ALL                   ) else '0';
    O_DATA  <= hold_data  when (state  = HOLD_STATE                 ) else I_DATA;
end RTL;

```




DataFlow_Join_Valve の SYNC_I 信号と SYNC_O 信号は、複数の DataFlow_Join_Valve 間で同期をとるための信号です。



DataFlow_Join_Vavle を使った例として、２つのノードの出力を１つのノードに入力するためのアダプタを示します。


```VHDL
library IEEE;
use     IEEE.std_logic_1164.all;
entity  DataFlow_Join_x2 is
    port (
        CLOCK         : in  std_logic;
        RESET         : in  std_logic;
        I0_DATA       : in  std_logic_vector(3 downto 0);
        I0_VALID      : in  std_logic;
        I0_READY      : out std_logic;
        I1_DATA       : in  std_logic_vector(3 downto 0);
        I1_VALID      : in  std_logic;
        I1_READY      : out std_logic;
        O_DATA        : out std_logic_vector(7 downto 0);
        O_VALID       : out std_logic;
        O_READY       : in  std_logic
    );
end DataFlow_Join_x2;

architecture RTL of DataFlow_Join_x2 is
    component  DataFlow_Join_Valve
        generic (
            WIDTH         : positive := 8;
            NUM           : positive := 2
        );
        port (
            CLOCK         : in  std_logic;
            RESET         : in  std_logic;
            I_DATA        : in  std_logic_vector(WIDTH-1 downto 0);
            I_VALID       : in  std_logic;
            I_READY       : out std_logic;
            O_DATA        : out std_logic_vector(WIDTH-1 downto 0);
            O_VALID       : out std_logic;
            O_READY       : in  std_logic;
            SYNC_O        : out std_logic;
            SYNC_I        : in  std_logic_vector(NUM  -1 downto 0)
        );
    end component;
    signal  sync          :  std_logic_vector(1 downto 0);
begin
    VALVE0: DataFlow_Join_Valve                   -- 
        generic map(                              -- 
            WIDTH         => 4                  , -- 
            NUM           => 2                    -- 
        )                                         -- 
        port map (                                -- 
            CLOCK         => CLOCK              , -- In  :
            RESET         => RESET              , -- In  :
            I_DATA        => I0_DATA            , -- In  :
            I_VALID       => I0_VALID           , -- In  :
            I_READY       => I0_READY           , -- Out :
            O_DATA        => O_DATA(3 downto 0) , -- Out :
            O_VALID       => O_VALID            , -- Out :
            O_READY       => O_READY            , -- In  :
            SYNC_O        => sync(0)            , -- Out :
            SYNC_I        => sync                 -- In  :
        );                                        -- 
    VALVE1: DataFlow_Join_Valve                   -- 
        generic map(                              -- 
            WIDTH         => 4                  , -- 
            NUM           => 2                    -- 
        )                                         -- 
        port map (                                -- 
            CLOCK         => CLOCK              , -- In  :
            RESET         => RESET              , -- In  :
            I_DATA        => I1_DATA            , -- In  :
            I_VALID       => I1_VALID           , -- In  :
            I_READY       => I1_READY           , -- Out :
            O_DATA        => O_DATA(7 downto 4) , -- Out :
            O_VALID       => open               , -- Out :
            O_READY       => O_READY            , -- In  :
            SYNC_O        => sync(1)            , -- Out :
            SYNC_I        => sync                 -- In  :
        );                                        -- 
end RTL;

```

## QUEUE_REGISTER をアダプタとして使う方法


QUEUE_REGISTER は次の記事で紹介しています。



* [VALID 信号と READY 信号で制御するレジスタベースの簡易なキュー @Qiita](http://qiita.com/ikwzm/items/7cdfa0d22232d452c8e9)



この記事で紹介した通り、QUEUE_REGISTER は VALID-and-READY プロトコルに基づいており、入力側は VALID 信号の状態に関わりなくキューがデータを受け付ける状態になれば  READY 信号を H にし、出力側は READY 信号の状態に関わりなくキューにデータがある状態で VALID 信号を H にします。この性質を利用して、QUEUE_REGISTER を出力側のアダプタとして使うことで、「VALID-then-READY プロトコルに基づいた制御」で説明したような簡単な制御回路で制御することができます。


![Fig.6 QUEUE_REGISTERをアダプタとして使ったデータフロー(Join)制御回路](https://qiita-image-store.s3.amazonaws.com/0/24981/91451f6d-8474-a6e1-b2f1-13c83ecae2be.jpeg "Fig.6 QUEUE_REGISTERをアダプタとして使ったデータフロー(Join)制御回路")


Fig.6 QUEUE_REGISTERをアダプタとして使ったデータフロー(Join)制御回路

<br />