はじめに

別記事「はじめに」を参照してください。

この記事では、マージソーター内部で使用するソーティングネットワーク(Sorting_Network) のコアパッケージについて説明します。

ソーティングネットワークとは

ソーティングネットワークとは、数列をソートするネットワークで、ワイヤとコンパレータで構成されています。ワイヤは値を伝えます。コンパレーターは入出力に二本のワイヤをとり、二つの値が入力されると、指定された属性に従って出力をスルーしたりスワップしたりします。

コンパレーターには Up/Down という方向が設定されています。下図では矢印で示しています。

ソーティングネットワークの場合は、昇順と降順があります。昇順は値を小さい方から大きい方にソートするため、コンパレーターは値の小さい方を矢印の方に出力します。

Fig.1 コンパレーター (昇順)

逆に降順は値を大きい方から小さい方にソートするため、コンパレーターは値の大きい方を矢印の方に出力します。

Fig.2 コンパレーター (降順)

以下に、単純な昇順のソーティングネットワークの動作を示します。

Fig.3 ソーティングネットワークの動作例 (4入力昇順)

ソーティングネットワークの VHDL 記述

ソーティングネットワークのステージ

ソーティングネットワークを VHDL で記述するにあたり、ステージという概念を導入します。ステージとは、ソーティングネットワークを並列処理可能な単位で分割したものです。前述の４入力昇順ソーティングネットワークの場合は、次のように３ステージに分割することが出来ます。

Fig.4 ソーティングネットワークのステージ

ステージを分割することによって、ステージ間にレジスタを挿入することでパイプライン処理が可能になります。

ソーティングネットワーク構成の VHDL 記述

Param_Type

ソーティングネットワークを VHDL で記述するにあたり、まずはソーティングネットワークの構成を Sorting_Network.Param_Type という record タイプで定義します。これらの定義は Sorting_Network パッケージで定義しています。

Param_Type は、ネットワークのサイズ(入力ワード数)を保持する Size、ステージのサイズを保持する Stage_Size、ステージごとの各種情報を保持する Stage_Listで構成されています。

src/main/vhdl/core/sorting_network.vhd

library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
library Merge_Sorter;
use     Merge_Sorter.Word;
package Sorting_Network is
    constant  Max_Network_Size      :  integer := 128;
    constant  Max_Stage_Size        :  integer := 256;
    -- (中略) --
    type      Param_Type            is record
                  Stage_List        :  Stage_Vector( 1 to Max_Stage_Size);
                  Stage_Size        :  integer range 0 to Max_Stage_Size;
                  Stage_Lo          :  integer range 0 to Max_Stage_Size;
                  Stage_Hi          :  integer range 0 to Max_Stage_Size;
                  Stage_Ctrl_Lo     :  integer range 0 to Max_Stage_Size*Stage_Queue_Ctrl_Bits;
                  Stage_Ctrl_Hi     :  integer range 0 to Max_Stage_Size*Stage_Queue_Ctrl_Bits;
                  Sort_Order        :  integer;
                  Size              :  integer range 0 to Max_Network_Size;
                  Lo                :  integer range 0 to Max_Network_Size-1;
                  Hi                :  integer range 0 to Max_Network_Size-1;
    end record;
    -- (後略) --
end Sorting_Network;

Stage_Type

Stage_Type およびその配列型である Stage_Vector は Sorting_Network パッケージにて次のように定義されています。

Stage_Type は、ネットワーク毎のコンパレーター等のオペレーターの情報を保持する Operator_List と、パイプラインレジスタのキューのサイズを保持する Queue_Sizeで構成されています。

src/main/vhdl/core/sorting_network.vhd

library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
library Merge_Sorter;
use     Merge_Sorter.Word;
package Sorting_Network is
     -- (前略) --
    constant  Max_Stage_Queue_Size  :  integer := 2;
    type      Stage_Type            is record
                  Operator_List     :  Operator_Vector(0 to Max_Network_Size-1);
                  Queue_Size        :  integer range 0 to Max_Stage_Queue_Size;
    end record;
    constant  Stage_Null            :  Stage_Type := (
                  Operator_List     => (others => Operator_None),
                  Queue_Size        => 0
              );
    type      Stage_Vector          is array (integer range <>) of Stage_Type;
    -- (後略) --
end Sorting_Network;

Operator_Type

Operator_Type およびその配列型である Operator_Vector は Sorting_Network パッケージにて次のように定義されています。

Operator_Type は、オペレーターの種類(OP_NONE、OP_PASS、OP_COMP_UP 、OP_COMP_DOWN) を保持する OP、およびオペレーターを接続する対となるネットワークの相対位置を示す STEP で構成されています。

src/main/vhdl/core/sorting_network.vhd

library ieee;
use     ieee.std_logic_1164.all;
use     ieee.numeric_std.all;
library Merge_Sorter;
use     Merge_Sorter.Word;
package Sorting_Network is
     -- (前略) --
    type      Operator              is (OP_NONE, OP_PASS, OP_COMP_UP, OP_COMP_DOWN);
    type      Operator_Type         is record
                  STEP              :  integer;
                  OP                :  Operator;
    end record;
    constant  Operator_None         :  Operator_Type := (
                  STEP              => 0,
                  OP                => OP_NONE
              );
    type      Operator_Vector       is array (integer range <>) of Operator_Type;
     -- (後略) --
end Sorting_Network;

構成例

以下に４入力昇順ソーティングネットワーク(Fig.4参照)の構成を VHDL で記述した例を示します。

Fig.5 ソーティングネットワーク構成の VHDL 記述例

Fig.6 ソーティングネットワーク構成の VHDL 記述例 (Stage 1)

Fig.7 ソーティングネットワーク構成の VHDL 記述例 (Stage 2)

Fig.8 ソーティングネットワーク構成の VHDL 記述例 (Stage 3)

ソーティングネットワークコアの VHDL 記述

ソーティングネットワークコアは、前節で定義したソーティングネットワーク構成(Sorting_Network.Param_Type) に基づき、ソーティングネットワークを構築した回路です。

構造

ソーティングネットワークコアの構造は次のようになっています。

Fig.9 ソーティングネットワークコアの構成

Entity

ジェネリック変数の NETWORK_PARAM でソーティングネットワークの構成を指定します。WORD_PARAM で「ワードの定義」を指定します。INFO_BITS はソーティングネットワークを通すその他の情報のビット数を指定します。

I_WORD はソーティングネットワークに入力するネットワーク毎のワードで、O_WORD はソートされたネットワーク毎のワードです。I_WORD および O_WORD はネットワーク毎のワードを一次元のビット配列(std_logic_vector)にしたものです。

I_INFO はその他の情報を入力し、O_INFO から内部のパイプライン分だけ遅延されて出力されます。