Bitonic Sorter Network を VHDL で記述

##はじめに

ソートアルゴリズムに Bitonic Sort と言うのがあるようです。
出典は[こちら(https://en.wikipedia.org/wiki/Bitonic_sorter)](https://en.wikipedia.org/wiki/Bitonic_sorter)です。
ちょっと面白そうなのでVHDLでこのネットワークを記述してみました。

ただし、ソートするアイテムの数(=n)が増えるとO(n*log(n)**2)のオーダーで回路規模が増えます。ここで紹介するVHDLでは、単にネットワークを作るだけなので、一度にソートできるアイテム数に限りがあります。もし大量のアイテムをソートする場合は、メモリを活用する等もっと工夫する必要があります。

あと、モジュールを再帰的にインスタンスしています。Xilinx社の Vivado ではシミュレーションと論理合成出来ることは確認していますが、他の処理系では上手くいかないかもしれません。


##Bitonic Sortのアルゴリズム

[こちら(https://en.wikipedia.org/wiki/Bitonic_sorter)](https://en.wikipedia.org/wiki/Bitonic_sorter)に、Python で記述された Bitonic Sort の Example code があります。このコードは簡潔で大変わかりやすく、さすが Python です。今回は、このコードを参考に VHDL で記述してみます。

````Python:bitonic_sort.py
def bitonic_sort(up, x):
    if len(x) <= 1:
        return x
    else: 
        first = bitonic_sort(True, x[:len(x) / 2])
        second = bitonic_sort(False, x[len(x) / 2:])
        return bitonic_merge(up, first + second)

def bitonic_merge(up, x): 
    # assume input x is bitonic, and sorted list is returned 
    if len(x) == 1:
        return x
    else:
        bitonic_compare(up, x)
        first = bitonic_merge(up, x[:len(x) / 2])
        second = bitonic_merge(up, x[len(x) / 2:])
        return first + second

def bitonic_compare(up, x):
    dist = len(x) / 2
    for i in range(dist):  
        if (x[i] > x[i + dist]) == up:
            x[i], x[i + dist] = x[i + dist], x[i] #swap
````

##ソースコード

オリジナルは[こちらhttps://github.com/ikwzm/bitonic_sorter](https://github.com/ikwzm/bitonic_sorter)にあります。
さすがに Python の様に簡潔ではありませんが、モジュールを再帰的にインスタンスしています。
なお、[こちらの記事(VHDLで下位ブロックを呼び出す2つの方法)](http://qiita.com/ikwzm/items/21bbcfe21f97cbd29b8a)でも解説しましたが、今回は再帰的にインスタンスすることもあって、component宣言を使ってるので、なおさら記述量が増えています。

###ライセンス

二条項BSDライセンス (2-clause BSD license) で公開しています。

###bitonic_sorter

````VHDL:bitonic_sorter.vhd
library ieee;
use     ieee.std_logic_1164.all;
entity  Bitonic_Sorter is
    generic (
        WORDS     :  integer :=  8;
        WORD_BITS :  integer := 64;
        COMP_HIGH :  integer := 63;
        COMP_LOW  :  integer := 32;
        INFO_BITS :  integer :=  4
    );
    port (
        CLK       :  in  std_logic;
        RST       :  in  std_logic;
        CLR       :  in  std_logic;
        I_SORT    :  in  std_logic;
        I_UP      :  in  std_logic;
        I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
        O_SORT    :  out std_logic;
        O_UP      :  out std_logic;
        O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
    );
end Bitonic_Sorter;
library ieee;
use     ieee.std_logic_1164.all;
architecture RTL of Bitonic_Sorter is
    component Bitonic_Sorter
        generic (
            WORDS     :  integer :=  1;
            WORD_BITS :  integer := 64;
            COMP_HIGH :  integer := 63;
            COMP_LOW  :  integer := 32;
            INFO_BITS :  integer :=  4
        );
        port (
            CLK       :  in  std_logic;
            RST       :  in  std_logic;
            CLR       :  in  std_logic;
            I_SORT    :  in  std_logic;
            I_UP      :  in  std_logic;
            I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
            O_SORT    :  out std_logic;
            O_UP      :  out std_logic;
            O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
        );
    end component;
    component Bitonic_Merge
        generic (
            WORDS     :  integer :=  1;
            WORD_BITS :  integer := 64;
            COMP_HIGH :  integer := 63;
            COMP_LOW  :  integer := 32;
            INFO_BITS :  integer :=  4
        );
        port (
            CLK       :  in  std_logic;
            RST       :  in  std_logic;
            CLR       :  in  std_logic;
            I_SORT    :  in  std_logic;
            I_UP      :  in  std_logic;
            I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
            O_SORT    :  out std_logic;
            O_UP      :  out std_logic;
            O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
        );
    end component;
begin
    ONE: if (WORDS <= 1) generate
        O_DATA <= I_DATA;
        O_INFO <= I_INFO;
        O_SORT <= I_SORT;
        O_UP   <= I_UP;
    end generate;
    ANY: if (WORDS > 1) generate
        constant UP_POS :  integer := I_INFO'high+1;
        signal   s_info :  std_logic_vector(    I_INFO'high+1 downto 0);
        signal   q_info :  std_logic_vector(    I_INFO'high+1 downto 0);
        signal   q_data :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        signal   q_sort :  std_logic;
    begin
        s_info(UP_POS      ) <= I_UP;
        s_info(I_INFO'range) <= I_INFO;
        FIRST : Bitonic_Sorter generic map (WORDS/2, WORD_BITS, COMP_HIGH, COMP_LOW, s_info'length)
            port map (
                CLK     => CLK,
                RST     => RST,
                CLR     => CLR,
                I_SORT  => I_SORT,
                I_UP    => '1',
                I_INFO  => s_info,
                I_DATA  => I_DATA(WORD_BITS*(WORDS/2)-1 downto WORD_BITS*0),
                O_SORT  => q_sort,
                O_UP    => open,
                O_INFO  => q_info,
                O_DATA  => q_data(WORD_BITS*(WORDS/2)-1 downto WORD_BITS*0)
            );
        SECOND: Bitonic_Sorter generic map (WORDS/2, WORD_BITS, COMP_HIGH, COMP_LOW, s_info'length)
            port map (
                CLK     => CLK,
                RST     => RST,
                CLR     => CLR,
                I_SORT  => I_SORT,
                I_UP    => '0',
                I_INFO  => s_info,
                I_DATA  => I_DATA(WORD_BITS*(WORDS)-1 downto WORD_BITS*(WORDS/2)),
                O_SORT  => open,
                O_UP    => open,
                O_INFO  => open,
                O_DATA  => q_data(WORD_BITS*(WORDS)-1 downto WORD_BITS*(WORDS/2))
            );
        MERGE : Bitonic_Merge  generic map (WORDS  , WORD_BITS, COMP_HIGH, COMP_LOW, INFO_BITS)
            port map (
                CLK     => CLK,
                RST     => RST,
                CLR     => CLR,
                I_SORT  => q_sort,
                I_UP    => q_info(UP_POS),
                I_INFO  => q_info(I_INFO'range),
                I_DATA  => q_data,
                O_SORT  => O_SORT,
                O_UP    => O_UP  ,
                O_INFO  => O_INFO,
                O_DATA  => O_DATA
            );
    end generate;
end RTL;
````
###bitonic_merge

````VHDL:bitonic_merge.vhd
library ieee;
use     ieee.std_logic_1164.all;
entity  Bitonic_Merge is
    generic (
        WORDS     :  integer :=  1;
        WORD_BITS :  integer := 64;
        COMP_HIGH :  integer := 63;
        COMP_LOW  :  integer := 32;
        INFO_BITS :  integer :=  4
    );
    port (
        CLK       :  in  std_logic;
        RST       :  in  std_logic;
        CLR       :  in  std_logic;
        I_SORT    :  in  std_logic;
        I_UP      :  in  std_logic;
        I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
        O_SORT    :  out std_logic;
        O_UP      :  out std_logic;
        O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
    );
end Bitonic_Merge;
library ieee;
use     ieee.std_logic_1164.all;
architecture RTL of Bitonic_Merge is
    component Bitonic_Merge
        generic (
            WORDS     :  integer :=  1;
            WORD_BITS :  integer := 64;
            COMP_HIGH :  integer := 63;
            COMP_LOW  :  integer := 32;
            INFO_BITS :  integer :=  4
        );
        port (
            CLK       :  in  std_logic;
            RST       :  in  std_logic;
            CLR       :  in  std_logic;
            I_SORT    :  in  std_logic;
            I_UP      :  in  std_logic;
            I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
            O_SORT    :  out std_logic;
            O_UP      :  out std_logic;
            O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
        );
    end component;
    component Bitonic_Exchange
        generic (
            WORD_BITS :  integer := 64;
            COMP_HIGH :  integer := 63;
            COMP_LOW  :  integer := 32
        );
        port (
            I_SORT    :  in  std_logic;
            I_UP      :  in  std_logic;
            I_A       :  in  std_logic_vector(WORD_BITS-1 downto 0);
            I_B       :  in  std_logic_vector(WORD_BITS-1 downto 0);
            O_A       :  out std_logic_vector(WORD_BITS-1 downto 0);
            O_B       :  out std_logic_vector(WORD_BITS-1 downto 0)
        );
    end component;
begin
    ONE: if (WORDS = 1) generate
        O_DATA <= I_DATA;
        O_INFO <= I_INFO;
        O_SORT <= I_SORT;
        O_UP   <= I_UP;
    end generate;
    ANY: if (WORDS > 1) generate
        constant DIST   :  integer := WORDS / 2;
        signal   s_data :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        signal   q_data :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        signal   q_info :  std_logic_vector(      INFO_BITS-1 downto 0);
        signal   q_sort :  std_logic;
        signal   q_up   :  std_logic;
    begin
        XCHG: for i in 0 to DIST-1 generate
            U: Bitonic_Exchange generic map(WORD_BITS, COMP_HIGH, COMP_LOW)
            port map (
                I_SORT  => I_SORT,
                I_UP    => I_UP  ,
                I_A     => I_DATA(WORD_BITS*(i     +1)-1 downto WORD_BITS*(i     )),
                I_B     => I_DATA(WORD_BITS*(i+DIST+1)-1 downto WORD_BITS*(i+DIST)),
                O_A     => s_data(WORD_BITS*(i     +1)-1 downto WORD_BITS*(i     )),
                O_B     => s_data(WORD_BITS*(i+DIST+1)-1 downto WORD_BITS*(i+DIST))
            );
        end generate;
        process (CLK, RST) begin
            if (RST = '1') then
                    q_data <= (others => '0');
                    q_info <= (others => '0');
                    q_sort <= '1';
                    q_up   <= '1';
            elsif (CLK'event and CLK = '1') then
                if (CLR = '1') then
                    q_data <= (others => '0');
                    q_info <= (others => '0');
                    q_sort <= '1';
                    q_up   <= '1';
                else
                    q_data <= s_data;
                    q_info <= I_INFO;
                    q_sort <= I_SORT;
                    q_up   <= I_UP;
                end if;
            end if;
        end process;
        FIRST : Bitonic_Merge generic map (WORDS/2, WORD_BITS, COMP_HIGH, COMP_LOW, INFO_BITS)
            port map (
                CLK     => CLK,
                RST     => RST,
                CLR     => CLR,
                I_SORT  => q_sort,
                I_UP    => q_up,
                I_INFO  => q_info,
                I_DATA  => q_data(WORD_BITS*(WORDS/2)-1 downto WORD_BITS*0),
                O_SORT  => O_SORT,
                O_UP    => O_UP,
                O_INFO  => O_INFO,
                O_DATA  => O_DATA(WORD_BITS*(WORDS/2)-1 downto WORD_BITS*0)
            );
        SECOND: Bitonic_Merge generic map (WORDS/2, WORD_BITS, COMP_HIGH, COMP_LOW, INFO_BITS)
            port map (
                CLK     => CLK,
                RST     => RST,
                CLR     => CLR,
                I_SORT  => q_sort,
                I_UP    => q_up,
                I_INFO  => q_info,
                I_DATA  => q_data(WORD_BITS*(WORDS)-1 downto WORD_BITS*(WORDS/2)),
                O_SORT  => open,
                O_UP    => open,
                O_INFO  => open,
                O_DATA  => O_DATA(WORD_BITS*(WORDS)-1 downto WORD_BITS*(WORDS/2))
            );
    end generate;
end RTL;
````
###bitonic_exchange

````VHDL:bitonic_exchange.vhd
library ieee;
use     ieee.std_logic_1164.all;
entity  Bitonic_Exchange is
    generic (
        WORD_BITS :  integer := 64;
        COMP_HIGH :  integer := 63;
        COMP_LOW  :  integer := 32
    );
    port (
        I_SORT    :  in  std_logic;
        I_UP      :  in  std_logic;
        I_A       :  in  std_logic_vector(WORD_BITS-1 downto 0);
        I_B       :  in  std_logic_vector(WORD_BITS-1 downto 0);
        O_A       :  out std_logic_vector(WORD_BITS-1 downto 0);
        O_B       :  out std_logic_vector(WORD_BITS-1 downto 0)
    );
end Bitonic_Exchange;
library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
architecture RTL of Bitonic_Exchange is  
begin
    process(I_SORT, I_UP, I_A, I_B)
        variable comp_a  :  unsigned(COMP_HIGH-COMP_LOW downto 0);
        variable comp_b  :  unsigned(COMP_HIGH-COMP_LOW downto 0);
        variable a_gt_b  :  boolean;
    begin
        comp_a := unsigned(I_A(COMP_HIGH downto COMP_LOW));
        comp_b := unsigned(I_B(COMP_HIGH downto COMP_LOW));
        a_gt_b := (comp_a > comp_b);
        if (I_SORT = '1' and I_UP = '1' and a_gt_b = TRUE ) or
           (I_SORT = '1' and I_UP = '0' and a_gt_b = FALSE) then
            O_A <= I_B;
            O_B <= I_A;
        else
            O_A <= I_A;
            O_B <= I_B;
        end if;
    end process;
end RTL;
````

##Vivado によるシミュレーション

###テストベンチ

非常に簡単ですが、次のようなテストベンチを用意しています。本来ならもっとちゃんとしたテストベンチが必要です。

````VHDL:test_bench_bsn.vhd
library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
use     std.textio.all;
-----------------------------------------------------------------------------------
--
-----------------------------------------------------------------------------------
entity  TEST_BENCH_BSN is
end     TEST_BENCH_BSN;
-----------------------------------------------------------------------------------
--
-----------------------------------------------------------------------------------
architecture MODEL of TEST_BENCH_BSN is
    -------------------------------------------------------------------------------
    -- 
    -------------------------------------------------------------------------------
    constant CLOCK_PERIOD    : time    := 10 ns;
    constant DELAY           : time    :=  1 ns;
    -------------------------------------------------------------------------------
    -- 
    -------------------------------------------------------------------------------
    constant WORDS           :  integer :=  8;
    constant WORD_BITS       :  integer :=  8;
    constant COMP_HIGH       :  integer :=  7;
    constant COMP_LOW        :  integer :=  0;
    constant INFO_BITS       :  integer :=  4;
    -------------------------------------------------------------------------------
    --
    -------------------------------------------------------------------------------
    signal   CLK             :  std_logic;
    signal   RST             :  std_logic;
    signal   CLR             :  std_logic;
    signal   I_SORT          :  std_logic;
    signal   I_UP            :  std_logic;
    signal   I_DATA          :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
    signal   I_INFO          :  std_logic_vector(      INFO_BITS-1 downto 0);
    signal   O_SORT          :  std_logic;
    signal   O_UP            :  std_logic;
    signal   O_DATA          :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
    signal   O_INFO          :  std_logic_vector(      INFO_BITS-1 downto 0);
    -------------------------------------------------------------------------------
    --
    -------------------------------------------------------------------------------
    component Bitonic_Sorter
        generic (
            WORDS     :  integer :=  1;
            WORD_BITS :  integer := 64;
            COMP_HIGH :  integer := 64;
            COMP_LOW  :  integer := 32;
            INFO_BITS :  integer :=  4
        );
        port (
            CLK       :  in  std_logic;
            RST       :  in  std_logic;
            CLR       :  in  std_logic;
            I_SORT    :  in  std_logic;
            I_UP      :  in  std_logic;
            I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
            O_SORT    :  out std_logic;
            O_UP      :  out std_logic;
            O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
        );
    end component;
begin
    -------------------------------------------------------------------------------
    --
    -------------------------------------------------------------------------------
    DUT: Bitonic_Sorter                 -- 
        generic map (                   -- 
            WORDS     => WORDS        , --
            WORD_BITS => WORD_BITS    , --
            COMP_HIGH => COMP_HIGH    , --
            COMP_LOW  => COMP_LOW     , --
            INFO_BITS => INFO_BITS      --
        )                               -- 
        port map (                      -- 
            CLK       => CLK          , -- In  :
            RST       => RST          , -- In  :
            CLR       => CLR          , -- In  :
            I_SORT    => I_SORT       , -- In  :
            I_UP      => I_UP         , -- In  :
            I_DATA    => I_DATA       , -- In  :
            I_INFO    => I_INFO       , -- In  :
            O_SORT    => O_SORT       , -- Out :
            O_UP      => O_UP         , -- Out :
            O_DATA    => O_DATA       , -- Out :
            O_INFO    => O_INFO         -- Out :
        );
    -------------------------------------------------------------------------------
    -- 
    -------------------------------------------------------------------------------
    process begin
        CLK <= '0';
        wait for CLOCK_PERIOD / 2;
        CLK <= '1';
        wait for CLOCK_PERIOD / 2;
    end process;
    -------------------------------------------------------------------------------
    -- 
    -------------------------------------------------------------------------------
    process
        type      INTEGER_VECTOR  is array(0 to WORDS-1) of integer;
        variable  src_vec         :  INTEGER_VECTOR;
        variable  exp_vec         :  INTEGER_VECTOR;
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        function  TO_DATA(IVEC:INTEGER_VECTOR) return std_logic_vector is
            variable     data :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
        begin
            for i in 0 to WORDS-1 loop
                data(WORD_BITS*(i+1)-1 downto WORD_BITS*i) := std_logic_vector(to_unsigned(IVEC(i), WORD_BITS));
            end loop;
            return data;
        end function;
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        function  TO_INTEGER_VECTOR(DATA:std_logic_vector) return INTEGER_VECTOR is
            variable     ivec :  INTEGER_VECTOR;
        begin
            for i in 0 to WORDS-1 loop
                ivec(i) := to_integer(unsigned(DATA(WORD_BITS*(i+1)-1 downto WORD_BITS*i)));
            end loop;
            return ivec;
        end function;
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        procedure WAIT_CLK(CNT:in integer) is
        begin
            for i in 1 to CNT loop 
                wait until (CLK'event and CLK = '1'); 
            end loop;
        end WAIT_CLK;
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        procedure TEST(SORT,UP:std_logic; SRC,EXP: INTEGER_VECTOR) is
            variable timeout :  boolean;
            variable result  :  INTEGER_VECTOR;
        begin
            I_DATA  <= TO_DATA(SRC);
            I_INFO  <= "1111";
            I_SORT  <= SORT;
            I_UP    <= UP;
            timeout := TRUE;
            
            MAIN_LOOP: for i in 1 to 1000 loop
                wait until (CLK'event and CLK = '1');
                I_INFO <= "0000";
                I_DATA <= (others => '0');
                I_SORT <= '0';
                I_UP   <= '0';
                if (O_INFO = "1111") then
                    timeout := FALSE;
                    exit MAIN_LOOP;
                end if;
            end loop;
            assert(timeout = FALSE) report "Timeout..."  severity FAILURE;
            result := TO_INTEGER_VECTOR(O_DATA);
            assert(result  = EXP  ) report "Mismatch..." severity FAILURE;
        end procedure;
    begin
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        assert(false) report "Run Start..." severity NOTE;
        RST    <= '1';
        CLR    <= '0';
        I_DATA <= (others => '0');
        I_INFO <= (others => '0');
        I_SORT <= '0';
        I_UP   <= '0';
        WAIT_CLK(10);
        RST    <= '0';
        WAIT_CLK(10);
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        src_vec := (0 => 8, 1 => 1, 2 => 0, 3 => 6, 4 => 1, 5 => 2, 6 => 9, 7 => 1);
        exp_vec := (0 => 8, 1 => 1, 2 => 0, 3 => 6, 4 => 1, 5 => 2, 6 => 9, 7 => 1);
        TEST('0', '0', src_vec, exp_vec);
        WAIT_CLK(1);

        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        src_vec := (0 => 8, 1 => 1, 2 => 0, 3 => 6, 4 => 1, 5 => 2, 6 => 9, 7 => 1);
        exp_vec := (0 => 9, 1 => 8, 2 => 6, 3 => 2, 4 => 1, 5 => 1, 6 => 1, 7 => 0);
        TEST('1', '0', src_vec, exp_vec);
        WAIT_CLK(1);
        
        ---------------------------------------------------------------------------
        --
        ---------------------------------------------------------------------------
        src_vec := (0 => 8, 1 => 1, 2 => 0, 3 => 6, 4 => 1, 5 => 2, 6 => 9, 7 => 1);
        exp_vec := (0 => 0, 1 => 1, 2 => 1, 3 => 1, 4 => 2, 5 => 6, 6 => 8, 7 => 9);
        TEST('1', '1', src_vec, exp_vec);

        WAIT_CLK(10);
        assert(false) report "Run complete..." severity FAILURE;
        wait;
    end process;
end MODEL;
````

###Vivadoのバージョン

- Xilinx Vivado 2015.4

###手順

####ダウンロード

````shell
shell% git clone git://github.com/ikwzm/bitonic_sorter.git
````
 
####Vivadoプロジェクトの作成

Vivado プロジェクトを作成するためのTclファイル(create_project.tcl)を用意しています。
Vivado のTclシェルを使う場合は次のようにします。

````Shell
Vivado% cd sim/vivado/bitonic_sorter
Vivado% vivado -mod batch -source create_project.tcl
````

Vivado の GUIを使う場合は次のメニューからTclファイルを実行してください。

````
Vivado > Open Project > sim/vivado/bitonic_sorter/bitonic_sorter.xpr
Flow Navigator > Run Simulation > Run Bihavioral Simulation 
````
####シミュレーションを実行

Vivado プロジェクトを開き、次のようにシミュレーションを実行してください。

````
Vivado > Open Project > sim/vivado/bitonic_sorter/bitonic_sorter.xpr
Flow Navigator > Run Simulation > Run Bihavioral Simulation 
````

##Vivado による論理合成＆インプリメンテーション

###開発ツールと対象デバイス

- Xilinx Vivado 2015.4
- Xilinx Zynq7020-1 (xc7z020clg400-1)

###ラッパー回路

bionic_sorter を最上位モジュールにすると I/O が足りなくなる上に、Vivado の問題なのか再帰的にインスタンスしていると階層構造をうまく認識出来ないようで bionic_sorterをトップレベルに設定できません。そこで次のようなラッパーモジュールを用意しています。
ソートするアイテム数(=WORDS)を4,8,16,32で合成してみました。

````bitonic_sorter_wrapper.vhd
library ieee;
use     ieee.std_logic_1164.all;
entity  Bitonic_Sorter_Wrapper is
    generic (
        WORDS     :  integer :=  8;
        WORD_BITS :  integer := 32;
        COMP_HIGH :  integer := 31;
        COMP_LOW  :  integer :=  0;
        INFO_BITS :  integer :=  4
    );
    port (
        CLK       :  in  std_logic;
        RST       :  in  std_logic;
        CLR       :  in  std_logic;
        I_SORT    :  in  std_logic;
        I_UP      :  in  std_logic;
        I_ADDR    :  in  integer range 0 to WORDS-1;
        I_DATA    :  in  std_logic_vector(WORD_BITS-1 downto 0);
        I_INFO    :  in  std_logic_vector(INFO_BITS-1 downto 0);
        O_ADDR    :  in  integer range 0 to WORDS-1;
        O_DATA    :  out std_logic_vector(WORD_BITS-1 downto 0);
        O_INFO    :  out std_logic_vector(INFO_BITS-1 downto 0)
    );
end Bitonic_Sorter_Wrapper;
library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
architecture RTL of Bitonic_Sorter_Wrapper is
    component Bitonic_Sorter
        generic (
            WORDS     :  integer :=  1;
            WORD_BITS :  integer := 64;
            COMP_HIGH :  integer := 64;
            COMP_LOW  :  integer := 32;
            INFO_BITS :  integer :=  4
        );
        port (
            CLK       :  in  std_logic;
            RST       :  in  std_logic;
            CLR       :  in  std_logic;
            I_SORT    :  in  std_logic;
            I_UP      :  in  std_logic;
            I_DATA    :  in  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            I_INFO    :  in  std_logic_vector(      INFO_BITS-1 downto 0);
            O_SORT    :  out std_logic;
            O_UP      :  out std_logic;
            O_DATA    :  out std_logic_vector(WORDS*WORD_BITS-1 downto 0);
            O_INFO    :  out std_logic_vector(      INFO_BITS-1 downto 0)
        );
    end component;
    signal  s_data    :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
    signal  q_data    :  std_logic_vector(WORDS*WORD_BITS-1 downto 0);
begin
    process(CLK, RST) begin
        if (RST = '1') then
                s_data <= (others => '0');
        elsif (CLK'event and CLK = '1') then
            if (CLR = '1') then
                s_data <= (others => '0');
            else
                for i in 0 to WORDS-1 loop
                    if (I_ADDR = i) then
                        s_data(WORD_BITS*(i+1)-1 downto WORD_BITS*i) <= I_DATA;
                    end if;
                end loop;
            end if;
        end if;
    end process;
    U: Bitonic_Sorter
        generic map (
            WORDS     => WORDS     , -- 
            WORD_BITS => WORD_BITS , -- 
            COMP_HIGH => COMP_HIGH , -- 
            COMP_LOW  => COMP_LOW  , -- 
            INFO_BITS => INFO_BITS   -- 
        )
        port map (
            CLK       => CLK       , -- 
            RST       => RST       , -- 
            CLR       => CLR       , -- 
            I_SORT    => I_SORT    , -- 
            I_UP      => I_UP      , -- 
            I_DATA    => s_data    , -- 
            I_INFO    => I_INFO    , -- 
            O_SORT    => open      , -- 
            O_UP      => open      , -- 
            O_DATA    => q_data    , -- 
            O_INFO    => O_INFO      -- 
        );
    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');
            else
                for i in 0 to WORDS-1 loop
                    if (O_ADDR = i) then
                        O_DATA <= q_data(WORD_BITS*(i+1)-1 downto WORD_BITS*i);
                    end if;
                end loop;
            end if;
        end if;
    end process;
end RTL;
````

###手順

####ダウンロード

````shell
shell% git clone git://github.com/ikwzm/bitonic_sorter.git
````
 
####Vivadoプロジェクトの作成

今回はちょっと手を抜いて、Vivadoシミュレーションのプロジェクトを間借りしています。
プロジェクトの作り方はそちらを参照してください。

####論理合成とインプリメンテーション

Vivadoを起動してプロジェクトを開き、インプリメンテーションを実行します。

````
Vivado > Open Project > sim/vivado/bitonic_sorter/bitonic_sorter.xpr
Flow Navigator > Run Implementation
````

###結果

|   WORDS   | Slice LUTs | Slice Registers | Slice |
|----------:|-----------:|----------------:|------:|
|         4 |        252 |              70 |    87 |
|         8 |       2061 |            1585 |   545 |
|        16 |       6658 |            5247 |  1746 |
|        32 |      19715 |           15684 |  5228 |

残念ながら、Zynq7020クラスだと、せいぜい32アイテムのソートしか出来ません。
ちなみに動作周波数は200MHzです。