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

1. https://github.com/ikwzm/Merge_Sorter
2. https://github.com/ikwzm/ArgSort-Ultra96
3. https://github.com/ikwzm/ArgSort-Kv260
4. https://github.com/ikwzm/ZynqMP-FPGA-Linux
5. https://github.com/ikwzm/ZynqMP-FPGA-Ubuntu20.04