はじめに

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

前回の記事で紹介した「マージソートツリー」だけでも基本的なソートは行えますが、そのままでは使い勝手がよくありません。そこで「マージソートツリー」の周りに幾つかの回路を追加してもう少し使い勝手を良くしたマージソートコアを作りました。マージソートコアは具体的には次の機能を「マージソートツリー」に追加します。

この記事では端数ワード処理に関して説明します。

マージソートコアの構成

マージソートコアは次の図のように「マージソートツリー」の入力側にストリーム入力回路(Core_Stream_Intake) と入力FIFO(Core_Intake_Fifo)、出力側にWord_Drop_None 回路を追加した構成になっています。

Fig.1 マージソートコアの構成

端数ワード処理とは

Way 単位の端数ワード処理

「マージソートツリー」内部の「マージソートノード」は、その構造上、必ずワードが入力される必要があります。入力されるワードが無いと「マージソートノード」は入力待ち状態のまま終了しません。

しかし、ソートするワード群のワード数が、必ず Way 単位であるとは限りません。ソートするワード数の都合上、「マージソートツリー」のすべての入力にワードが供給できなくなる場合があり得ます。

Fig.2 マージソートツリーのワード未入力によるフリーズ

そこでマージソートツリーコアでは、「ワードの定義」で説明した NONE 属性と POSTPEND 属性を付加したダミーのワードを「マージソートツリー」に入力することにより、「マージソートツリー」のソート処理を正常に終了させます。

Fig.3 マージソートツリーのダミーワード入力による端数処理

なお、NONE属性を持つワードは後段 Word_Drop_None 回路にて出力時に削除されます。また、NONE 属性と共に POSTPEND 属性を持っているので、「マージソートツリー」によるソート結果出力時には最も遅く出力されます。

マルチワードマージソートノードの端数ワード処理

[「マルチワードマージソート」]は、同時に処理するワードを複数ワードにすることで、単位時間あたりに出力するワード数を増やします。その結果、マージソートをワード数倍に高速化することが出来ます。

しかし、ソートするワード群のワード数が[「マルチワードマージソート」]が同時に処理するワード数で割り切れるとは限りません。そこでマージソートツリーコアでは、「ワードの定義」で説明した NONE 属性と POSTPEND 属性を付加したダミーのワードを「マージソートツリー」に入力します。

Fig.4 マルチワードマージソートの端数ワード処理の動作例(1)

Fig.5 マルチワードマージソートの端数ワード処理の動作例(2)

Fig.6 マルチワードマージソートの端数ワード処理の動作例(3)

Word_Drop_None

Word_Drop_None 回路は、「マージソートツリー」が出力したソート結果から NONE 属性の付いたワードを削除するフィルターの役割をします。

Word_Drop_None 回路によって、マージソートコアが便宜上追加したダミーワード(NONE属性+POSTPEND属性付きのワード)がマージソートコアから出力されずに捨てられます。

Fig.7 Word_Drop_None の役割

参照

目次: 「はじめに」
次回: 「ストリーム入力」
前回: 「マージソートツリー」
ソースコード:
https://github.com/ikwzm/Merge_Sorter/blob/1.4.1/src/main/vhdl/core/merge_sorter_core.vhd
https://github.com/ikwzm/Merge_Sorter/blob/1.4.1/src/main/vhdl/core/word_drop_none.vhd

VHDL で書くマージソーター(端数ワード処理)