VHDL で書くソーティングネットワーク(バッチャー奇偶マージソート)







# はじめに


別記事 [「はじめに」] を参照してください。

この記事では、前々回説明した[「ソーティングネットワーク(コアパッケージ)」]を使ってバッチャー奇偶マージソート回路を構成する方法を紹介します。




# バッチャー奇偶マージソートとは


バッチャー奇偶マージソート(Batcher's odd-even megesort) は Ken Batche(en: Ken Batcher) によって考案された、要素数ｎに対して、大きさO(n(log n)\*\*2) かつ深さO((log n)\*\*2)のソーティングネットワークです(出典:[Wikipedia/Batcher_odd-even_mergesort])。

次図に８入力のバッチャー奇偶マージソートのソーティングネットワークの例を示します。


![Fig.1 バッチャー奇偶マージソートのソーティングネットワーク例](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/a85f36cf-a3b3-0825-d1e3-1d976e9c618d.jpeg "Fig.1 バッチャー奇偶マージソートのソーティングネットワーク例")

Fig.1 バッチャー奇偶マージソートのソーティングネットワーク例

<br />



以下に再帰呼び出しを使って Python で記述したバッチャー奇偶マージソートの実装例を示します(出典:[Wikipedia/Batcher_odd-even_mergesort])。


```Python:oddeven_sort.py
def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]
 
def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)
 
def oddeven_merge_sort_range(x, lo, hi):
    if (hi - lo) >= 1:
        mid = lo + ((hi - lo) / 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)
 
def oddeven_merge_sort(x):
    oddeven_merge_sort_range(x, 0, len(x)-1)

```



# バッチャーズ奇偶マージソートの VHDL 記述



## ソーティングネットワークの VHDL 記述



### New_Network 関数


New_Network 関数は、バッチャーズ奇偶マージソートのソーティングネットワークに対応した Sorting_Network.Param_Type([「ソーティングネットワーク(コアパッケージ)」]参照)を生成します。 New_Network 関数は OddEven_MergeSort_Network パッケージにて定義しています。


```VHDL:src/main/vhdl/core/oddeven_mergesort_network.vhd
library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
library Merge_Sorter;
use     Merge_Sorter.Sorting_Network;
library Merge_Sorter;
package OddEven_MergeSort_Network is
    -- (前略) --
    function   New_Network(
                  LO          :  integer;
                  HI          :  integer;
                  ORDER       :  integer
    )             return         Sorting_Network.Param_Type;
    function   New_Network(
                  LO          :  integer;
                  HI          :  integer;
                  ORDER       :  integer;
                  QUEUE       :  Sorting_Network.Queue_Param_Type
    )             return         Sorting_Network.Param_Type;
    -- (後略) --
end OddEven_MergeSort_Network;
```





```VHDL:src/main/vhdl/core/oddeven_mergesort_network.vhd
package body OddEven_MergeSort_Network is
    -- (前略) --
    function   New_Network(
                  LO          :  integer;
                  HI          :  integer;
                  ORDER       :  integer
    )             return         Sorting_Network.Param_Type
    is
        variable  network     :  Sorting_Network.Param_Type;
    begin
        network := Sorting_Network.New_Network(LO,HI,ORDER);
        oddeven_sort(network, network.Stage_Lo, network.Lo, network.Hi);
        Sorting_Network.Reverse_Network_Stage(network);
        return network;
    end function;
    function   New_Network(
                  LO          :  integer;
                  HI          :  integer;
                  ORDER       :  integer;
                  QUEUE       :  Sorting_Network.Queue_Param_Type
    )             return         Sorting_Network.Param_Type
    is
        variable  network     :  Sorting_Network.Param_Type;
    begin
        network := New_Network(LO,HI,ORDER);
        Sorting_Network.Set_Queue_Param(network, QUEUE);
        return network;
    end function;
    -- (後略) --
end OddEven_MergeSort_Network;
```





### New_Merge_Network 関数


New_Merge_Network 関数は、バッチャーズ奇偶マージソートネットワークのうちのマージの部分だけを取り出した Sorting_Network.Param_Type([「ソーティングネットワーク(コアパッケージ)」]参照)を生成します。 New_Merge_Network 関数は OddEven_MergeSort_Network パッケージにて定義しています。


```VHDL:src/main/vhdl/core/oddeven_mergesort_network.vhd
library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
library Merge_Sorter;
use     Merge_Sorter.Sorting_Network;
package OddEven_MergeSort_Network is
    -- (前略) --
    function   New_Merge_Network(
                  LO          :  integer;
                  HI          :  integer;
                  ORDER       :  integer
    )             return         Sorting_Network.Param_Type;
    -- (後略) --
end OddEven_MergeSort_Network;
```



```VHDL:src/main/vhdl/core/oddeven_mergesort_network.vhd
package body OddEven_MergeSort_Network is
    -- (前略) --
    function   New_Merge_Network(
                  LO          :  integer;
                  HI          :  integer;
                  ORDER       :  integer
    )             return         Sorting_Network.Param_Type
    is
        variable  network     :  Sorting_Network.Param_Type;
    begin
        network := Sorting_Network.New_Network(LO,HI,ORDER);
        oddeven_merge(network, network.Stage_Lo, network.Lo, network.Hi, 1);
        Sorting_Network.Reverse_Network_Stage(network);
        return network;
    end function;
    -- (後略) --
end OddEven_MergeSort_Network;
```



### oddeven_sort 関数


OddEven_MergeSort_Netowork パッケージボディに定義されたoddeven_sort 関数は、前述の Python による実装でしめした oddeven_merge_sort_range に対応します。oddeven_sort 関数を再帰的に呼び出しています。


```VHDL:src/main/vhdl/core/oddeven_mergesort_network.vhd
package body OddEven_MergeSort_Network is
    -- (前略) --
    procedure oddeven_sort(
        variable  NETWORK     :  inout Sorting_Network.Param_Type;
                  START_STAGE :  in    integer;
                  LO          :  in    integer;
                  HI          :  in    integer
    ) is
        variable  mid         :        integer;
    begin
        if (HI - LO > 0) then
            mid := LO + ((HI - LO) / 2);
            oddeven_merge(NETWORK, START_STAGE         , LO   , HI , 1);
            oddeven_sort (NETWORK, NETWORK.Stage_HI + 1, LO   , mid   );
            oddeven_sort (NETWORK, NETWORK.Stage_HI + 1, mid+1, HI    );
        end if;
    end procedure;
    -- (後略) --
end OddEven_MergeSort_Network;
```





### oddeven_merge 関数


OddEven_MergeSort_Netowork パッケージボディに定義されたoddeven_merge 関数は、前述の Python による実装でしめした oddeven_merge に対応します。oddeven_merge 関数を再帰的に呼び出しています。

また、Python のよる実装では compare_and_swap を呼び出して実際に値を比較して交換していますが、この OddEven_MergeSort_Network パッケージではソーティングネットワークを構築するのが目的なので、ソーティングネットワークにコンパレーターを挿入するための Add_Comparator 関数を呼び出します。


```VHDL:src/main/vhdl/core/oddeven_mergesort_network.vhd
package body OddEven_MergeSort_Network is
    -- (前略) --
    procedure oddeven_merge(
        variable  NETWORK     :  inout Sorting_Network.Param_Type;
                  START_STAGE :  in    integer;
                  LO          :  in    integer;
                  HI          :  in    integer;
                  R           :  in    integer
    ) is
        variable  step        :        integer;
        variable  index       :        integer;
    begin
        step := R * 2;
        if (HI - LO > step) then
            oddeven_merge(NETWORK, START_STAGE + 1, LO    , HI, step);
            oddeven_merge(NETWORK, START_STAGE + 1, LO + R, HI, step);
            index  := LO + R;
            while (index <= HI - R) loop
                Sorting_Network.Add_Comparator(NETWORK, START_STAGE, index, index + R, TRUE);
                index := index + step;
            end loop;
        else
            Sorting_Network.Add_Comparator(NETWORK, START_STAGE, LO, LO + R, TRUE);
        end if;
        if (START_STAGE > NETWORK.Stage_Hi) then
            NETWORK.Stage_Hi   := START_STAGE;
            NETWORK.Stage_Size := NETWORK.Stage_Hi - NETWORK.Stage_Lo + 1;
        end if;
    end procedure;
    -- (後略) --
end OddEven_MergeSort_Network;
```



## バッチャーズ奇偶マージソートの VHDL 記述例


前回の[「ソーティングネットワーク(コアパッケージ)」]で説明した Sorting_Network_Core に、前述で説明した New_Network関数で生成したソーティングネットワーク構成を示す定数を渡してバッチャーズ奇偶ソートマージ回路を構成した例を示します。


### Entity 



```VHDL:src/main/vhdl/examples/oddeven_sorter/oddeven_sorter.vhd
library ieee;
use     ieee.std_logic_1164.all;
entity  OddEven_Sorter is
    generic (
        WORDS           :  integer :=  4;
        DATA_BITS       :  integer := 32;
        COMP_HIGH       :  integer := 32;
        COMP_LOW        :  integer :=  0;
        COMP_SIGN       :  boolean := FALSE;
        SORT_ORDER      :  integer :=  0;
        ATRB_BITS       :  integer :=  4;
        INFO_BITS       :  integer :=  1;
        QUEUE_SIZE      :  integer :=  0
    );
    port (
        CLK             :  in  std_logic;
        RST             :  in  std_logic;
        CLR             :  in  std_logic;
        I_DATA          :  in  std_logic_vector(WORDS*DATA_BITS-1 downto 0);
        I_ATRB          :  in  std_logic_vector(WORDS*ATRB_BITS-1 downto 0) := (others => '0');
        I_INFO          :  in  std_logic_vector(      INFO_BITS-1 downto 0) := (others => '0');
        I_VALID         :  in  std_logic;
        I_READY         :  out std_logic;
        O_DATA          :  out std_logic_vector(WORDS*DATA_BITS-1 downto 0);
        O_ATRB          :  out std_logic_vector(WORDS*ATRB_BITS-1 downto 0);
        O_INFO          :  out std_logic_vector(      INFO_BITS-1 downto 0);
        O_VALID         :  out std_logic;
        O_READY         :  in  std_logic;
        BUSY            :  out std_logic
    );
end OddEven_Sorter;

```



### Architecture


[「ワードの定義」]で説明したパラメータを WORD_PARAM 定数に設定します。


```VHDL:src/main/vhdl/examples/oddeven_sorter/oddeven_sorter.vhd
library ieee;
use     ieee.std_logic_1164.all;
library Merge_Sorter;
use     Merge_Sorter.Word;
use     Merge_Sorter.Sorting_Network;
use     Merge_Sorter.OddEven_MergeSort_Network;
use     Merge_Sorter.Core_Components.Sorting_Network_Core;
architecture RTL of OddEven_Sorter is
    constant  WORD_PARAM    :  Word.Param_Type := Word.New_Param(DATA_BITS, COMP_LOW, COMP_HIGH, COMP_SIGN);
    signal    i_word        :  std_logic_vector(WORDS*WORD_PARAM.BITS-1 downto 0);
    signal    o_word        :  std_logic_vector(WORDS*WORD_PARAM.BITS-1 downto 0);
begin

```




入力された I_DATA と I_ATRB を[「ワードの定義」]で指定されたワード形式に変換します。


```VHDL:src/main/vhdl/examples/oddeven_sorter/oddeven_sorter.vhd
    process (I_DATA, I_ATRB)
        variable   data     :  std_logic_vector(DATA_BITS-1 downto 0);
        variable   atrb     :  std_logic_vector(ATRB_BITS-1 downto 0);
        variable   word     :  std_logic_vector(WORD_PARAM.BITS-1 downto 0);
    begin
        for i in 0 to WORDS-1 loop
            data := I_DATA((i+1)*DATA_BITS-1 downto i*DATA_BITS);
            atrb := I_ATRB((i+1)*ATRB_BITS-1 downto i*ATRB_BITS);
            word(WORD_PARAM.DATA_HI downto WORD_PARAM.DATA_LO) := data;
            word(WORD_PARAM.ATRB_NONE_POS    ) := atrb(0);
            word(WORD_PARAM.ATRB_PRIORITY_POS) := atrb(1);
            word(WORD_PARAM.ATRB_POSTPEND_POS) := atrb(2);
            i_word((i+1)*WORD_PARAM.BITS-1 downto i*WORD_PARAM.BITS) <= word;
        end loop;
    end process;

```




前節で説明した New_Bitonic_Sorter_Network 関数を使ってバッチャーズ奇偶マージソートのソーティングネットワークを構築して[「ソーティングネットワーク(コアパッケージ)」]で説明した Sorting_Network_Core に渡します。これにでバッチャーズ奇偶マージソートを行うソーティングネットワークが出来ます。


```VHDL:src/main/vhdl/examples/oddeven_sorter/oddeven_sorter.vhd
    CORE: Sorting_Network_Core
        generic map (
            NETWORK_PARAM   => OddEven_MergeSort_Network.New_Network(
                                   LO    => 0,
                                   HI    => WORDS-1,
                                   ORDER => SORT_ORDER,
                                   QUEUE => Sorting_Network.Constant_Queue_Size(QUEUE_SIZE)
                               ),
            WORD_PARAM      => WORD_PARAM      , -- 
            INFO_BITS       => INFO_BITS         -- 
        )                                        -- 
        port map (                               -- 
            CLK             => CLK             , -- In  :
            RST             => RST             , -- In  :
            CLR             => CLR             , -- In  :
            I_WORD          => i_word          , -- In  :
            I_INFO          => I_INFO          , -- In  :
            I_VALID         => I_VALID         , -- In  :
            I_READY         => I_READY         , -- Out :
            O_WORD          => o_word          , -- Out :
            O_INFO          => O_INFO          , -- Out :
            O_VALID         => O_VALID         , -- Out :
            O_READY         => O_READY         , -- In  :
            BUSY            => BUSY              -- Out :
        );

```




最後にソート結果を O_WORD と O_ATRB に変換して出力します。


```VHDL:src/main/vhdl/examples/oddeven_sorter/oddeven_sorter.vhd
    process (o_word)
        variable   data     :  std_logic_vector(DATA_BITS-1 downto 0);
        variable   atrb     :  std_logic_vector(ATRB_BITS-1 downto 0);
        variable   word     :  std_logic_vector(WORD_PARAM.BITS-1 downto 0);
    begin
        for i in 0 to WORDS-1 loop
            word := o_word((i+1)*WORD_PARAM.BITS-1 downto i*WORD_PARAM.BITS);
            data := word(WORD_PARAM.DATA_HI downto WORD_PARAM.DATA_LO);
            atrb    := (others => '0');
            atrb(0) := word(WORD_PARAM.ATRB_NONE_POS    );
            atrb(1) := word(WORD_PARAM.ATRB_PRIORITY_POS);
            atrb(2) := word(WORD_PARAM.ATRB_POSTPEND_POS);
            O_DATA((i+1)*DATA_BITS-1 downto i*DATA_BITS) <= data;
            O_ATRB((i+1)*ATRB_BITS-1 downto i*ATRB_BITS) <= atrb;
        end loop;
    end process;
end RTL;

```





# 参照


* 目次: [「はじめに」]
* 次回: [「シングルワード マージソート ノード」]
* 前回: [「ソーティングネットワーク(バイトニックマージソート)」]
* ソースコード:   
https://github.com/ikwzm/Merge_Sorter/blob/1.4.1/src/main/vhdl/core/sorting_network.vhd   
https://github.com/ikwzm/Merge_Sorter/blob/1.4.1/src/main/vhdl/core/oddeven_mergesort_network.vhd   
https://github.com/ikwzm/Merge_Sorter/blob/1.4.1/src/main/vhdl/examples/oddeven_sorter/oddeven_sorter.vhd
* 出典: [Wikipedia/Batcher_odd-even_mergesort]


[Wikipedia/Batcher_odd-even_mergesort]: https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%83%81%E3%83%A3%E3%83%BC%E5%A5%87%E5%81%B6%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88 "Wikipedia/Batcher_odd-even_mergesort"
[「はじめに」]: https://qiita.com/ikwzm/items/6665b2ef44d878a5b85f "「VHDL で書くマージソーター(はじめに)」@Qiita"
[「ワードの定義」]: https://qiita.com/ikwzm/items/bdcd8876317b908ff492 "「VHDL で書くマージソーター(ワードの定義)」@Qiita"
[「ワード比較器」]: https://qiita.com/ikwzm/items/d5d1dd264b1670f33bd7 "「VHDL で書くマージソーター(ワード比較器)」@Qiita"
[「ソーティングネットワーク(コアパッケージ)」]: https://qiita.com/ikwzm/items/a1d06e47523759c726ae "「VHDL で書くソーティングネットワーク(コアパッケージ)」@Qiita"
[「ソーティングネットワーク(バイトニックマージソート)」]: https://qiita.com/ikwzm/items/366eacbf6a877994c955 "「VHDL で書くソーティングネットワーク(バイトニックマージソート)」@Qiita"
[「ソーティングネットワーク(バッチャー奇偶マージソート)」]: https://qiita.com/ikwzm/items/c21a53f21b87408a7805 "「VHDL で書くソーティングネットワーク(バッチャー奇偶マージソート)」@Qiita"
[「シングルワード マージソート ノード」]: https://qiita.com/ikwzm/items/7fd7ef9ffc4d9b314fee "「VHDL で書くマージソーター(シングルワード マージソート ノード)」@Qiita"
[「マルチワード マージソート ノード」]: https://qiita.com/ikwzm/items/ed96b7a44b83bcee4ba5 "「VHDL で書くマージソーター(マルチワード マージソート ノード)」@Qiita"
[「マージソート ツリー」]: https://qiita.com/ikwzm/items/1f76ae5cda95aaf92501 "「VHDL で書くマージソーター(マージソート ツリー)」@Qiita"
[「端数ワード処理」]: https://qiita.com/ikwzm/items/6b15340f1e05ef03f8d0 "「VHDL で書くマージソーター(端数ワード処理)」@Qiita"
[「ストリーム入力」]: https://qiita.com/ikwzm/items/56e22511021a082a2ccd "「VHDL で書くマージソーター(ストリーム入力)」@Qiita"
[「ストリームフィードバック」]: https://qiita.com/ikwzm/items/e8c59c0ec92956c9355f "「VHDL で書くマージソーター(ストリームフィードバック)」@Qiita"
[「ArgSort IP」]: https://qiita.com/ikwzm/items/89fc9542492fca74c9e3 "「VHDL で書くマージソーター(ArgSort IP)」@Qiita"
[「ArgSort-Ultra96」]: https://qiita.com/ikwzm/items/d58c9b77d038e23ac792 "「VHDL で書くマージソーター(ArgSort-Ultra96)」@Qiita"
[「ArgSort-Kv260」]: https://qiita.com/ikwzm/items/ec0f779534c44b35334a "「VHDL で書くマージソーター(ArgSort-Kv260)」@Qiita"
[ACRi]: https://www.acri.c.titech.ac.jp/wp "アダプティブコンピューティング研究推進体(ACRi)"
[アダプティブコンピューティング研究推進体(ACRi)]: https://www.acri.c.titech.ac.jp/wp "アダプティブコンピューティング研究推進体(ACRi)"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/132 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(2)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/501 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(2)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(3)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/2393 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(3)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(4)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/3888 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(4)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(5)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/4713 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(5)」"