別記事 「はじめに」 を参照してください。
この記事では、前々回説明した「ソーティングネットワーク(コアパッケージ)」を使ってバッチャー奇偶マージソート回路を構成する方法を紹介します。
バッチャー奇偶マージソート(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 バッチャー奇偶マージソートのソーティングネットワーク例
以下に再帰呼び出しを使って Python で記述したバッチャー奇偶マージソートの実装例を示します(出典:Wikipedia/Batcher_odd-even_mergesort)。
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)New_Network 関数は、バッチャーズ奇偶マージソートのソーティングネットワークに対応した Sorting_Network.Param_Type(「ソーティングネットワーク(コアパッケージ)」参照)を生成します。 New_Network 関数は OddEven_MergeSort_Network パッケージにて定義しています。
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;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 関数は、バッチャーズ奇偶マージソートネットワークのうちのマージの部分だけを取り出した Sorting_Network.Param_Type(「ソーティングネットワーク(コアパッケージ)」参照)を生成します。 New_Merge_Network 関数は OddEven_MergeSort_Network パッケージにて定義しています。
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;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_MergeSort_Netowork パッケージボディに定義されたoddeven_sort 関数は、前述の Python による実装でしめした oddeven_merge_sort_range に対応します。oddeven_sort 関数を再帰的に呼び出しています。
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_MergeSort_Netowork パッケージボディに定義されたoddeven_merge 関数は、前述の Python による実装でしめした oddeven_merge に対応します。oddeven_merge 関数を再帰的に呼び出しています。
また、Python のよる実装では compare_and_swap を呼び出して実際に値を比較して交換していますが、この OddEven_MergeSort_Network パッケージではソーティングネットワークを構築するのが目的なので、ソーティングネットワークにコンパレーターを挿入するための Add_Comparator 関数を呼び出します。
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;前回の「ソーティングネットワーク(コアパッケージ)」で説明した Sorting_Network_Core に、前述で説明した New_Network関数で生成したソーティングネットワーク構成を示す定数を渡してバッチャーズ奇偶ソートマージ回路を構成した例を示します。
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;
「ワードの定義」で説明したパラメータを WORD_PARAM 定数に設定します。
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 を「ワードの定義」で指定されたワード形式に変換します。
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 に渡します。これにでバッチャーズ奇偶マージソートを行うソーティングネットワークが出来ます。
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 に変換して出力します。
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