はじめに

ソートアルゴリズムに Bitonic Sort と言うのがあるようです。
出典はこちら(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)に、Python で記述された Bitonic Sort の Example code があります。このコードは簡潔で大変わかりやすく、さすが Python です。今回は、このコードを参考に VHDL で記述してみます。

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にあります。
さすがに Python の様に簡潔ではありませんが、モジュールを再帰的にインスタンスしています。
なお、こちらの記事(VHDLで下位ブロックを呼び出す2つの方法)でも解説しましたが、今回は再帰的にインスタンスすることもあって、component宣言を使ってるので、なおさら記述量が増えています。

ライセンス

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

bitonic_sorter

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

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

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 によるシミュレーション

テストベンチ

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

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% git clone git://github.com/ikwzm/bitonic_sorter.git

Vivadoプロジェクトの作成

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

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% 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です。