はじめに
ソートアルゴリズムに 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です。