はじめに

筆者はかつて「VHDL で書くマージソーター」という題で幾つか記事を書きました。マージソーターを実装する際に、ソーティングネットワークを VHDL で書く必要がありました。これらの詳細は以下の記事を参照してください。

この記事は、上の記事のスピンオフ編で、「VHDL で書くソーティングネットワーク(コアパッケージ)」を使ってバブルソート回路を構成する方法を紹介します。

バブルソートとは

バブルソート(Bubble sort) は、隣り合う要素の大小を比較しながら整列させるソートアルゴリズムです。アルゴリズムが比較的単純で実装も容易ですが、最悪計算量がO(n**2)と遅いため、一般にはマージソートなどより最悪時間計算量の小さな方法が利用されます。(出典:https://wikipedia.org/wiki/Bubble_sort)。

以下に Python で記述したバブルソートの実装例を示します。

bubble_sort.py

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 パッケージにて定義しています。

src/main/vhdl/core/bubble_sort_network.vhd

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;

src/main/vhdl/core/bubble_sort_network.vhd

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 関数を再帰的に呼び出しています。

src/main/vhdl/core/bubble_sort_network.vhd

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関数で生成したソーティングネットワーク構成を示す定数を渡してバブルソート回路を構成した例を示します。