はじめに

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

この記事は、前々回の「シングルワードマージソートノード」および前回の「マルチワードマージソートノード」の続きで、これらのマージソートノードをツリー上に構成したマージソートツリーに関して説明します。

マージソートツリーとは

マージソートツリーは、原則 2-way であるマージソートノードをツリー上に構成することにより3-way以上のマージソートを行います。

マージソートノードは２ワードの入力を受け付けて(2-way)、「ワード比較器」の比較結果をもとにどちらかのワードを出力します。「FPGAを使って基本的なアルゴリズムのソーティングを劇的に高速化(1)」ではマージロジック回路として紹介されていますが、これと同じものです。

Fig.1 マージソートノードと 4-way マージソートツリー

マージソートツリーは具体的には次の図のような構成になっています。マージソートツリーを再帰的に配置することによってをツリーを構成しています。

Fig.2 マージソートツリーの構成例(8-way)

「ワードの定義」で説明したパラメータをジェネリック変数 WORD_PARAM に設定します。

同時に処理するワード数をジェネリック変数WORDS に設定します。

Way 数をジェネリック変数 WAYS に設定します。

ジェネリック変数 SORT_ORDER は昇順か降順かを指定します。