VALID 信号と READY 信号によるパイプライン制御

# はじめに


パイプライン処理とは、まあ言ってみれば次の図のように生産工場での流れ作業のようなものです。全工程を複数の工程に分けて、ベルトコンベヤー上で分担します。各工程担当は、次の工程に出来たものを渡すと同時に、前の工程から出来たものを受け取って作業を行います。こうすることでスループット(時間あたりの生産量)を上げるのが目的です。


![Fig.1 生産工場でのパイプライン処理](https://qiita-image-store.s3.amazonaws.com/0/24981/546786b1-f5a1-5c80-e18c-f14d66913fda.jpeg "Fig.1 生産工場でのパイプライン処理")

Fig.1 生産工場でのパイプライン処理

<br />



論理回路で処理を行う場合も、このようなパイプライン処理を行うことがあります。例えば、次の図の(b)のように複雑な処理を、動作周波数を上げてスループットを上げるために、(a)のように複数の処理に分割してパイプライン処理を行います。


![Fig.2 論理回路のパイプライン処理](https://qiita-image-store.s3.amazonaws.com/0/24981/7bc274e9-2f09-6bbc-9265-19159cea5345.jpeg "Fig.2 論理回路のパイプライン処理")

Fig.2 論理回路のパイプライン処理

<br />



上の図のような単純なパイプライン処理の場合、データは入力側から出力側に順番に流れるだけですが、もしこのパイプライン処理を途中で止めたり再開したりしたい場合は、もう一工夫必要です。この記事では、このパイプライン処理の中断と再開を VALID 信号と READY 信号で行う方法を示します。




# VALID 信号と READY 信号でパイプライン処理の中断と再開を行わない方法


パイプライン処理の中断と再開を VALID 信号と READY 信号で行う方法を示す前に、まずはこれらの信号を使わずに中断と再開を行う方法を参考までに紹介します。




## 入力データの供給で制御する方法


パイプライン処理の中断と再開を行う最も簡単な方法は、入力データの供給を制御することです。入力データを止めることでパイプライン処理を中断し、入力データを再び供給することでパイプライン処理を再開します。

具体的には次の図のように入力データが有効であることを示すフラグ(VALID)を各ステージに伝搬させます。出力側のVALIDフラグがセットされていれば、有効な出力データであることを示します。


![Fig.3 VALID 信号の伝搬による停止と再開](https://qiita-image-store.s3.amazonaws.com/0/24981/80b29973-811f-bda6-7c60-0428f2551dfe.jpeg "Fig.3 VALID 信号の伝搬による停止と再開")

Fig.3 VALID 信号の伝搬による停止と再開

<br />



しかし、この方法には課題があります。それはレスポンスです。入力データの供給を止めたとしても、パイプライン上にはすでに供給されたデータの処理をしており、これらがすべて処理を終えるまでパイプライン処理は終わりません。単純に入力データの供給を制御する方法では、このレスポンスの課題を解決しておく必要があります。



例えば次の図のように、入力を止めてもすでにパイプライン上には４個分の材料があるため、この製品４個が出来るまで待たされます。また場合によってはこの４個の製品を溜めるためのスペースが必要になることもあります。


![Fig.4 入力データの供給を停止した場合、止まるのに４サイクル遅れる](https://qiita-image-store.s3.amazonaws.com/0/24981/ea3bac96-0e2f-ed42-e3fb-9db6f7f16d71.jpeg "Fig.4 入力データの供給を停止した場合、止まるのに４サイクル遅れる")

Fig.4 入力データの供給を停止した場合、止まるのに４サイクル遅れる

<br />



入力データの供給を再開した場合も、実際に製品が出てくるのに４サイクルの遅れが生じます。




![Fig.5 入力データの供給を再開した場合、新たに製品が出てくるのに４サイクル遅れる](https://qiita-image-store.s3.amazonaws.com/0/24981/ab8e5e22-4925-c5a4-7096-ac759bf9167b.jpeg "Fig.5 入力データの供給を再開した場合、新たに製品が出てくるのに４サイクル遅れる")

Fig.5 入力データの供給を再開した場合、新たに製品が出てくるのに４サイクル遅れる

<br />








## 一斉に各工程(ステージ)の中断と再開する方法


この方法は各工程にストッパーを設け、中断の指令が来たら一斉にストッパーを下げて次の工程への供給を停止し、再開の指令が来たら一斉にストッパーを解除して次の工程への供給を再開します。


![Fig.6 一斉にストッパーを下げる方法](https://qiita-image-store.s3.amazonaws.com/0/24981/850312bd-16e8-d16e-4631-7bfde58276e8.jpeg "Fig.6 一斉にストッパーを下げる方法")

Fig.6 一斉にストッパーを下げる方法

<br />



具体的にこのストッパーを論理回路で実装する場合、次の図のように各ステージのレジスタに処理結果をロードするか現在のレジスタの値を保持するかを選択するためのセレクタを設けます。例えば次の図では、セレクタへの選択信号(RUN信号)が'1'の場合は処理結果をロード、'0'の場合は現在のレジスタの値を保持としています。この場合、RUN 信号を'0'にすることでパイプライン処理を中断し、'1'にすることで再開します。


![Fig.7 RUN信号による停止と再開](https://qiita-image-store.s3.amazonaws.com/0/24981/acbc69a5-9cd6-f377-16ca-997f2642e07a.jpeg "Fig.7 RUN信号による停止と再開")

Fig.7 RUN信号による停止と再開

<br />




# VALID 信号と READY 信号でパイプライン処理の中断と再開を行う方法


パイプライン処理の各工程(ステージ)をデータフローのノードと見なすことで、次の記事で説明したように VALID 信号と READY 信号で制御します。

  * [VALID 信号と READY 信号によるハンドシェイクの注意点 @Qiita](http://qiita.com/ikwzm/items/9736b5547cb15309af5c)
  * [VALID 信号と READY 信号によるデータフロー制御(Fork編) @Qiita](http://qiita.com/ikwzm/items/e4ec2290e08326f5e06c)
  * [VALID 信号と READY 信号によるデータフロー制御(Join編) @Qiita](http://qiita.com/ikwzm/items/f34961239aa352c58794)


![Fig.8 データフローによるパイプライン処理](https://qiita-image-store.s3.amazonaws.com/0/24981/c31b9dad-8a08-c435-b501-dbdeeddb77cf.jpeg "Fig.8 データフローによるパイプライン処理")


Fig.8 データフローによるパイプライン処理

<br />



各ノードは、各ステージ毎に処理の異なる Logic と、それらLogic の結果を保持するための Pipeline Register で構成されます。

Pipeline Register は VALID-and-READY プロトコルに基づいたデータフロー制御を行います。具体的には次のような制御を行います。

* Pipeline Register に演算結果を用意できたら O_VALID 信号を'1'にして次のステージにデータが用意できたことを通知します。
* データを受け入れる準備が整ったことを前のステージに対して I_READY 信号を'1' にすることで通知します。データを受け入れる準備が整う条件は次のうちのいずれかです。

  * Pipeline Register に有効なデータが入っていない(O_VALID='0')時。
  * Pipeline Registerに有効なデータが入っている(O_VALID='1')が、次のステージがデータ受け入れ可能(O_READY='1')になっていて、このデータは次のステージに移動することが確定している時。

* 前のステージに有効なデータが入っていて(I_VALID='1')、かつデータの受け入れ準備が整っている(I_READY='1')時、PipeLine Register  の内容を Logic の演算結果に更新します。

* Pipeline Register に有効な値が入っているか否かを示す O_VALID 信号の値は次のように決まります。

  * Pipeline Register に有効な値が入っていない(O_VALID='0')時、前のステージに有効なデータが入っている(I_VALID='1')ならば、 Pipeline Register の内容を Logic の演算結果を更新してO_VALID 信号を '1' にします。
  * Pipeline Register に有効な値が入っている(O_VALID='1')時、次のステージがデータを受け入れ可能(O_READY='1')かつ前のステージに有効なデータが入っていない(I_VALID='0')時は O_VALID 信号を '0' にします。それ以外は O_VALID 信号を '1' にします。

参考までに Pipeline Register の VHDL のソースコードを以下に示します。

```VHDL:pipeline_register.vhd
library ieee;
use     ieee.std_logic_1164.all;
entity  PIPELINE_REGISTER is
    port (
        CLK         : in  std_logic; 
        RST         : in  std_logic;
        CLR         : in  std_logic;
        I_DATA      : in  std_logic_vector(7 downto 0);
        I_VALID     : in  std_logic;
        I_READY     : out std_logic;
        O_DATA      : out std_logic_vector(7 downto 0);
        O_VALID     : out std_logic;
        O_READY     : in  std_logic
    );
end PIPELINE_REGISTER; 
architecture RTL of PIPELINE_REGISTER is
    signal   reg_valid  : std_logic;
    signal   reg_load   : std_logic;
    signal   in_ready   : std_logic;
begin
    O_VALID  <= reg_valid;
    I_READY  <= in_ready;
    in_ready <= '1' when (reg_valid = '0') or
                         (reg_valid = '1' and O_READY  = '1') else '0';
    reg_load <= '1' when (I_VALID   = '1' and in_ready = '1') else '0';
    process (CLK, RST) begin
        if    (RST = '1') then
                   reg_valid <= '0';
        elsif (CLK'event and CLK = '1') then
           if (CLR = '1') then
                   reg_valid <= '0';
           elsif (reg_valid = '0') then
               if (I_VALID = '1') then
                   reg_valid <= '1';
               else
                   reg_valid <= '0';
               end if;
           else
               if (I_VALID = '0' and O_READY = '1') then
                   reg_valid <= '0';
               else
                   reg_valid <= '1';
               end if;
           end if;
        end if;
    end process;
    process (CLK, RST) begin
        if    (RST = '1') then
               O_DATA <= (others => '0');
        elsif (CLK'event and CLK = '1') then
           if (CLR = '1') then
               O_DATA <= (others => '0');
           elsif (reg_load = '1') then
               O_DATA <= I_DATA;
           end if;
        end if;
    end process;
end RTL;
```

このPipeline Register を使う場合、ミーリマシンになっていることに注意してください。O_READY 信号の入力がレジスタを通さずにI_READY信号の生成に使われています。そのため、長いパイプライン処理をこの Pipeline Register で構成した場合、O_READY 信号の入力が多段の論理回路を通して I_READY 信号として出力されるため、このパスがクリティカルパスとなり動作周波数が上がらない可能性があります。


![Fig.9 Pipeline Register のクリティカルパス](https://qiita-image-store.s3.amazonaws.com/0/24981/c91f1c8a-33e2-e751-0c97-a1510aed7f5a.jpeg "Fig.9 Pipeline Register のクリティカルパス")

Fig.9 Pipeline Register のクリティカルパス

<br />



このようにクリティカルパスが問題になる場合、Pipeline Register の一部を[『VALID 信号と READY 信号で制御するレジスタベースの簡単なキュー @Qiita』](http://qiita.com/ikwzm/items/7cdfa0d22232d452c8e9)で紹介したQUEUE_REGISTER に置き換えることで解消できます。QUEUE_REGISTER のI_READY 出力信号はレジスタ出力になっています。そのためクリティカルパスがレジスタで分割されるので動作周波数を向上させる事が出来ます。QUEUE_REGISTER を使う場合は、QUEUE_REGISTER のジェネリック変数 QUEUE_SIZE に２以上の値を設定してください。 


![Fig.10 QUEUE_REGISTERを使った時のクリティカルパス](https://qiita-image-store.s3.amazonaws.com/0/24981/1d8de1d0-5236-6d34-c8d0-701bd8be3701.jpeg "Fig.10 QUEUE_REGISTERを使った時のクリティカルパス")

Fig.10 QUEUE_REGISTERを使った時のクリティカルパス

<br />