はじめに
筆者はかつて「VHDL で書くマージソーター」という題で幾つか記事を書きました。マージソーターを実装する際に、ソーティングネットワークを VHDL で書く必要がありました。これらの詳細は以下の記事を参照してください。
- 「VHDL で書くマージソーター(はじめに)」
- 「VHDL で書くソーティングネットワーク(コアパッケージ)」
- 「VHDL で書くソーティングネットワーク(バイトニックマージソート)」
- 「VHDL で書くソーティングネットワーク(バッチャー奇偶マージソート)」
この記事は、上の記事のスピンオフ編で、「VHDL で書くソーティングネットワーク(コアパッケージ)」を使ってバブルソート回路を構成する方法を紹介します。
バブルソートとは
バブルソート(Bubble sort) は、隣り合う要素の大小を比較しながら整列させるソートアルゴリズムです。アルゴリズムが比較的単純で実装も容易ですが、最悪計算量がO(n**2)と遅いため、一般にはマージソートなどより最悪時間計算量の小さな方法が利用されます。(出典:https://wikipedia.org/wiki/Bubble_sort)。
以下に Python で記述したバブルソートの実装例を示します。
def bubble_sort(data):
for i in range(0,len(data)-1):
for j in reversed(range(i,len(data)-1)):
if data[j+1] > data[j]:
data[j],data[j+1] = data[j+1],data[j]
return data
これをそのままソーティングネットワークにすると次のようになります。
Fig.1 バブルソートのソーティングネットワーク例(最適化前)
ただし、このままだとステージ(ソーティングネットワークを並列処理可能な単位に分割したもの。上の図で網線に囲まれた部分が１ステージに相当する。この数が多いほど遅延が大きくなる)の数がコンパレーターの数と同じ数になってしまいます。具体的には、要素数n としてステージ数は (n×(n-1)÷2) となり、O(n**2)で増加します。
そこで次の図のように並列処理が可能なステージを一つにまとめてしまいます。これにより、バブルソートのソーティングネットワークのステージ数は 2n-3 (=(n-1)+(n-2)) になります。
Fig.2 バブルソートのソーティングネットワーク例(最適化後)
バブルソートの VHDL 記述
ソーティングネットワークの VHDL 記述
New_Network 関数
New_Network 関数は、バブルソートのソーティングネットワークに対応した Sorting_Network.Param_Type(「VHDL で書くソーティングネットワーク(コアパッケージ)」参照)を生成します。 New_Network 関数は Bubble_Sort_Network パッケージにて定義しています。
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
library Merge_Sorter;
use Merge_Sorter.Sorting_Network;
package Bubble_Sort_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 Bubble_Sort_Network;
package body Bubble_Sort_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);
bubble_sort(network, network.Stage_Lo, network.Lo, network.Hi);
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 Bubble_Sort_Network;
bubble_sort 関数
Bubble_Sort_Netowork パッケージボディに定義されたbubble_sort 関数は、前述の Python による実装でしめした bubble_sort に対応します。bubble_sort 関数を再帰的に呼び出しています。
package body Bubble_Sort_Network is
-- (前略) --
procedure bubble_sort(
variable NETWORK : inout Sorting_Network.Param_Type;
START_STAGE : in integer;
LO : in integer;
HI : in integer
) is
variable comp_stage : integer;
begin
if (HI - LO > 0) then
comp_stage := START_STAGE;
for net in HI-1 downto LO loop
Sorting_Network.Add_Comparator(NETWORK, comp_stage, net, net+1, TRUE);
if (NETWORK.Stage_Hi < comp_stage) then
NETWORK.Stage_Hi := comp_stage;
end if;
comp_stage := comp_stage + 1;
end loop;
NETWORK.Stage_Size := NETWORK.Stage_Hi - NETWORK.Stage_Lo + 1;
bubble_sort(NETWORK, START_STAGE + 2, LO + 1, HI);
end if;
end procedure;
-- (後略) --
end Bubble_Sort_Network;
バブルソートの VHDL 記述例
「VHDL で書くソーティングネットワーク(コアパッケージ)」で説明した Sorting_Network_Core に、前述で説明した New_Network関数で生成したソーティングネットワーク構成を示す定数を渡してバブルソート回路を構成した例を示します。
Entity
library ieee;
use ieee.std_logic_1164.all;
entity Bubble_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 Bubble_Sorter;
Architecture
「VHDL で書くマージソーター(ワードの定義)」で説明したパラメータを 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.Bubble_Sort_Network;
use Merge_Sorter.Core_Components.Sorting_Network_Core;
architecture RTL of Bubble_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 を前述の WARD_PARAM 定数で指定されたワード形式に変換します。
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;
前節で説明した Bubble_Sort_Network.New_Network 関数を使ってバブルソートのソーティングネットワークを構築して Sorting_Network_Core に渡します。これでバブルソートを行うソーティングネットワークが出来ます。
CORE: Sorting_Network_Core
generic map (
NETWORK_PARAM => Bubble_Sort_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;
まとめ
この記事では、バブルソートに基づいたソーティングネットワークを VHDL で記述する方法を紹介しました。バブルソートは、バイトニックマージソートやバッチャー奇遇マージソートなどのマージソートに比べて、メカニズムが単純で、かつソートする要素数が２のべき乗値に限定されない利点があります。しかしコンパレーターの数が要素数nに対して (n×(n-1)÷2) なので O(n**2) で増加し、またステージ数は (n-1)+(n-2)=2n-3 になるので、要素数が多くなるほどマージソートに比べて不利になります。
そこで次回は、マージソートの利点を残しつつ要素数が２のべき乗値に限定されない非対称マージソートについて紹介します。
参照
参考記事
- 「VHDL で書くマージソーター(はじめに)」
- 「VHDL で書くマージソーター(ワードの定義)」
- 「VHDL で書くソーティングネットワーク(コアパッケージ)」
- 「VHDL で書くソーティングネットワーク(バイトニックマージソート)」
- 「VHDL で書くソーティングネットワーク(バッチャー奇偶マージソート)」
- 「VHDL で書くソーティングネットワーク(非対称マージソート)」
ソースコード
- 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/bubble_sort_network.vhd
- https://github.com/ikwzm/Merge_Sorter/blob/1.4.1/src/main/vhdl/examples/bubble_sorter/bubble_sorter.vhd