4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

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

Last updated at Posted at 2020-11-25

はじめに

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

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

ここでは 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
4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?