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

# はじめに


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


![Fig.1 データフローノード](https://qiita-image-store.s3.amazonaws.com/0/24981/e5943f61-bd59-8263-e3af-fe67ec43eebd.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)




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


Fork は出力側ノードが生成したデータを複製して複数の入力側ノードに同時に入力するパターンです。


![Fig.2 データフローの Fork パターン](https://qiita-image-store.s3.amazonaws.com/0/24981/7e5fa3d9-ec88-c6d0-fa98-0dc11202abb6.jpeg "Fig.2 データフローの Fork パターン")


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

<br />

例えば、画像処理で画素データをRGBで生成して、R/G/B 毎に別々の処理をする場合などに使います。

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


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


![Fig.3 READY-then-VALID プロトコルに基づいたデータフロー(Fork)制御回路](https://qiita-image-store.s3.amazonaws.com/0/24981/491455be-3557-ee8e-b6c4-c6392979940c.jpeg "Fig.3 READY-then-VALID プロトコルに基づいたデータフロー(Fork)制御回路")

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

<br />

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

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

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

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


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

VALID-and-READY プロトコルの場合も、VALID-then-READY プロトコルと同様の制御回路が必要です。



![Fig.4 VALID-and-READY プロトコルに基づいたデータフロー(Fork)制御回路](https://qiita-image-store.s3.amazonaws.com/0/24981/537db091-00fa-afe1-cd5e-15b25e3d4474.jpeg "Fig.4 VALID-and-READY プロトコルに基づいたデータフロー(Fork)制御回路")


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

<br />

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

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



この制御回路は READY-then-VALID プロトコルでも使えます。



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

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

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

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

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



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


![Fig.5 VALID-then-READY プロトコルに基づいたデータフロー(Fork)制御](https://qiita-image-store.s3.amazonaws.com/0/24981/f75e9a89-bfac-22b5-6e5a-1fd8014d4a65.jpeg "Fig.5 VALID-then-READY プロトコルに基づいたデータフロー(Fork)制御")


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

<br />



VHDL で記述すると次のようになります。


```VHDL
library IEEE;
use     IEEE.std_logic_1164.all;
entity  DataFlow_Fork_Control is
    generic (
        NUM           : positive := 8
    );
    port (
        CLOCK         : in  std_logic;
        RESET         : in  std_logic;
        I_VALID       : in  std_logic;
        I_READY       : out std_logic;
        O_VALID       : out std_logic_vector(NUM-1 downto 0);
        O_READY       : in  std_logic_vector(NUM-1 downto 0)
    );
end DataFlow_Fork_Control;
 
architecture RTL of DataFlow_Fork_Control is
    type      STATE_TYPE  is (RUN_STATE, PAUSE_STATE);
    signal    o_done      :  std_logic_vector(NUM-1 downto 0);
    constant  ALL_DONE    :  std_logic_vector(NUM-1 downto 0) := (others => '1');
begin
    CTRL: for i in 0 to NUM-1 generate
        signal    state   :  STATE_TYPE;
    begin
        process(CLOCK, RESET) begin
            if (RESET = '1') then
                state <= RUN_STATE;
            elsif (CLOCK'event and CLOCK = '1') then
                case state is
                    when RUN_STATE   =>
                        if (I_VALID = '1' and O_READY(i) = '1' and o_done /= ALL_DONE) then
                            state <= PAUSE_STATE;
                        else
                            state <= RUN_STATE;
                        end if;
                    when PAUSE_STATE =>
                        if (o_done = ALL_DONE) then
                            state <= RUN_STATE;
                        else
                            state <= PAUSE_STATE;
                        end if;
                    when others =>
                            state <= RUN_STATE;
                end case;
            end if;
        end process;
        O_VALID(i) <= '1' when (state = RUN_STATE and I_VALID    = '1') else '0';
        o_done(i)  <= '1' when (state = RUN_STATE and O_READY(i) = '1') or
                               (state = PAUSE_STATE                   ) else '0';
    end generate;
    I_READY <= '1' when (o_done = ALL_DONE) else '0';
end RTL;

```

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


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



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



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


![Fig.6 QUEUE_REGISTERをアダプタとして使ったデータフロー(Fork)制御回路](https://qiita-image-store.s3.amazonaws.com/0/24981/34b40bb0-5ac8-c623-f92a-cf320836f291.jpeg "Fig.6 QUEUE_REGISTERをアダプタとして使ったデータフロー(Fork)制御回路")


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

<br />