VHDL で書くマージソーター(はじめに)







# はじめに


[アダプティブコンピューティング研究推進体(ACRi)] にて「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化」という記事が投稿されています。

*  [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」] 
*  [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(2)」] 
*  [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(3)」] 
*  [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(4)」] 
*  [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(5)」] 



筆者はここに書かれているアイデアやアルゴリズムに興味を持ち、勝手ながらVHDL で実装して Ultra96-V2で実行してみました。VHDL のソースコードおよび Ultra96-V2 で動作する FPGA ビットストリームファイルとテストプログラムは GitHub にて公開しています。

*  https://github.com/ikwzm/Merge_Sorter
*  https://github.com/ikwzm/ArgSort-Ultra96
*  https://github.com/ikwzm/ArgSort-Kv260



ここでは VHDL でどのように実装したかを、いくつかにわけて紹介します。



なお、あくまでもこれらの基本的なアイデアは 「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化」を元にしたものです。これらのアイデアを記事として公開してくださった方々に感謝します。




# お品書き


1. はじめに (この記事)
2. [ワードの定義]
3. [ワード比較器]
4. [ソーティングネットワーク(コアパッケージ)]
5. [ソーティングネットワーク(バイトニックマージソート)]
6. [ソーティングネットワーク(バッチャー奇偶マージソート)]
7. [シングルワード マージソート ノード]
8. [マルチワード マージソート ノード]
9. [マージソート ツリー]
10. [端数ワード処理]
11. [ストリーム入力]
12. [ストリームフィードバック]
13. [ArgSort]
14. [ArgSort-Ultra96]
15. [ArgSort-Kv260]


# 参照



## ACRi


1. [アダプティブコンピューティング研究推進体(ACRi)]
2. [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」] 
3. [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(2)」] 
4. [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(3)」] 
5. [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(4)」] 
6. [「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(5)」] 


## GitHub


7. https://github.com/ikwzm/Merge_Sorter
8. https://github.com/ikwzm/ArgSort-Ultra96
9. https://github.com/ikwzm/ArgSort-Kv260
10. https://github.com/ikwzm/ZynqMP-FPGA-Linux
11. https://github.com/ikwzm/ZynqMP-FPGA-Ubuntu20.04


[はじめに]: 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]: 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)」"