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







# はじめに


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

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

  * 「端数ワード処理」(この記事)
  * [「ストリーム入力」]
  * [「ストリームフィードバック」]



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




# マージソートコアの構成


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


![Fig.1 マージソートコアの構成](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/394fb644-39fd-fbb4-4e50-b30d8cbe6635.jpeg "Fig.1 マージソートコアの構成")

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

<br />




# 端数ワード処理とは



## Way 単位の端数ワード処理


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

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


![Fig.2 マージソートツリーのワード未入力によるフリーズ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/f9b7f6d1-7f6c-2e32-40a6-3ea1c99eed9f.jpeg "Fig.2 マージソートツリーのワード未入力によるフリーズ")

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

<br />



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


![Fig.3 マージソートツリーのダミーワード入力による端数処理](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/e028921c-e7d5-2ebc-41b9-70a0256f70b8.jpeg "Fig.3 マージソートツリーのダミーワード入力による端数処理")

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

<br />

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


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


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

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

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


![Fig.4 マルチワードマージソートの端数ワード処理の動作例(1)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/aedcfad5-ae90-2def-9af3-4da045b09ef7.jpeg "Fig.4 マルチワードマージソートの端数ワード処理の動作例(1)")

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

<br />


![Fig.5 マルチワードマージソートの端数ワード処理の動作例(2)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/d70a1b0a-24df-1906-c6e7-4b3915dc3a65.jpeg "Fig.5 マルチワードマージソートの端数ワード処理の動作例(2)")

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

<br />




![Fig.6 マルチワードマージソートの端数ワード処理の動作例(3)](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/3466330a-26fb-97f4-3eb9-47746ad098f0.jpeg "Fig.6 マルチワードマージソートの端数ワード処理の動作例(3)")

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

<br />


## Word_Drop_None


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

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


![Fig.7 Word_Drop_None の役割](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/24981/9121f0ce-0f70-b6ab-71dc-743a4fb89731.jpeg "Fig.7 Word_Drop_None の役割")

Fig.7 Word_Drop_None の役割

<br />


# 参照


* 目次: [「はじめに」]
* 次回: [「ストリーム入力」] 
* 前回: [「マージソート ツリー」]
* ソースコード:   
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

 


[「はじめに」]: https://qiita.com/ikwzm/items/6665b2ef44d878a5b85f "「VHDL で書くマージソーター(はじめに)」@Qiita"
[「ワードの定義」]: https://qiita.com/ikwzm/items/bdcd8876317b908ff492 "「VHDL で書くマージソーター(ワードの定義)」@Qiita"
[「ワード比較器」]: https://qiita.com/ikwzm/items/d5d1dd264b1670f33bd7 "「VHDL で書くマージソーター(ワード比較器)」@Qiita"
[「ソーティングネットワーク(コアパッケージ)」]: https://qiita.com/ikwzm/items/a1d06e47523759c726ae "「VHDL で書くソーティングネットワーク(コアパッケージ)」@Qiita"
[「ソーティングネットワーク(バイトニックマージソート)」]: https://qiita.com/ikwzm/items/366eacbf6a877994c955 "「VHDL で書くソーティングネットワーク(バイトニックマージソート)」@Qiita"
[「ソーティングネットワーク(バッチャー奇偶マージソート)」]: https://qiita.com/ikwzm/items/c21a53f21b87408a7805 "「VHDL で書くソーティングネットワーク(バッチャー奇偶マージソート)」@Qiita"
[「シングルワード マージソート ノード」]: https://qiita.com/ikwzm/items/7fd7ef9ffc4d9b314fee "「VHDL で書くマージソーター(シングルワード マージソート ノード)」@Qiita"
[「マルチワード マージソート ノード」]: https://qiita.com/ikwzm/items/ed96b7a44b83bcee4ba5 "「VHDL で書くマージソーター(マルチワード マージソート ノード)」@Qiita"
[「マージソート ツリー」]: https://qiita.com/ikwzm/items/1f76ae5cda95aaf92501 "「VHDL で書くマージソーター(マージソート ツリー)」@Qiita"
[「端数ワード処理」]: https://qiita.com/ikwzm/items/6b15340f1e05ef03f8d0 "「VHDL で書くマージソーター(端数ワード処理)」@Qiita"
[「ストリーム入力」]: https://qiita.com/ikwzm/items/56e22511021a082a2ccd "「VHDL で書くマージソーター(ストリーム入力)」@Qiita"
[「ストリームフィードバック」]: https://qiita.com/ikwzm/items/e8c59c0ec92956c9355f "「VHDL で書くマージソーター(ストリームフィードバック)」@Qiita"
[「ArgSort IP」]: https://qiita.com/ikwzm/items/89fc9542492fca74c9e3 "「VHDL で書くマージソーター(ArgSort IP)」@Qiita"
[「ArgSort-Ultra96」]: https://qiita.com/ikwzm/items/d58c9b77d038e23ac792 "「VHDL で書くマージソーター(ArgSort-Ultra96)」@Qiita"
[「ArgSort-Kv260」]: https://qiita.com/ikwzm/items/ec0f779534c44b35334a "「VHDL で書くマージソーター(ArgSort-Kv260)」@Qiita"
[ACRi]: https://www.acri.c.titech.ac.jp/wp "アダプティブコンピューティング研究推進体(ACRi)"
[アダプティブコンピューティング研究推進体(ACRi)]: https://www.acri.c.titech.ac.jp/wp "アダプティブコンピューティング研究推進体(ACRi)"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/132 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(2)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/501 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(2)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(3)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/2393 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(3)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(4)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/3888 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(4)」"
[「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(5)」]: https://www.acri.c.titech.ac.jp/wordpress/archives/4713 "「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(5)」"