この記事では、私たちが国際会議 FCCM 2017 (論文 [1]) で提案したマージロジック回路のアーキテクチャ、動作例、特徴を解説します。マージロジック回路は2つのソートされた系列を1つの系列にマージします。これまでに提案された FPGA で動作させるソーティングアクセラレータの基本的な構成要素です。マージロジック回路の役割は1回目の記事、提案アーキテクチャのベースラインと基本的なアイデアは2回目の記事で説明されています。
フィードバックレジスタの最適化
これまでに説明した E レコードのマージロジック回路 (各クロックサイクルに E 個のレコードを出力できるマージロジック回路) は E 個のフィードバックレジスタを持ちます。しかし、私たちは E-1 個のフィードバックレジスタのみで十分であることを発見しました。
証明の詳細は省略しますが (論文 [1] をご参照ください)、基本的なアイデアは、各クロックサイクルに2つの入力 FIFO バッファ (FIFOA, FIFOB) から読み出されたレコードのうち、E-1 個のみがまだ読み出されていないレコードより大きい可能性があるからです。そのため、これらの E-1 個のレコードを保持 (フィードバック) し、次のクロックサイクルに FIFO から読み出されるレコードと比較する必要があります。ここで、下図の4レコードのマージロジック回路の動作例を用いて正しくマージすることを示します。
この例では、前回の記事の例のように、1, 3, 5, 7, 9, … というソートされた奇数の系列と、2, 4, 6, 8, 10, … というソートされた偶数の系列をマージして、1つのソートされた系列 1, 2, 3, 4, 5, 6, … を作ります。0を最小のレコードとするので、3個のフィードバックレジスタを0で初期化します。
サイクル1では、FIFOA と FIFOB の最小のレコードはそれぞれ1と2です。1は2より小さいため、 FIFOA から4個のレコード (1, 3, 5, 7) が読み出されます。1番目 (左端) のソートロジックはこれらのレコードとフィードバックレジスタに格納されているレコード (0) をソートして (0, 1, 3, 5, 7) を得ます。その中の小さい4個のレコード (0, 1, 3, 5) を2番目のソートロジックに出力し、最大のレコード (7) をフィードバックレジスタに書き戻します。同様に、2番目のソートロジックは4個のレコード (0, 0, 1, 3) を3番目のソートロジックに出力、1個のレコード (5) をフィードバックします。このように、最終的に4個のレコード (0, 0, 0, 1) が出力されます。(0, 0, 0) は2つの入力系列のレコードではなく最初にフィードバックレジスタに入っていたものなので出力系列から除外します。
サイクル2では、FIFOA と FIFOB の最小のレコードはそれぞれ9と2です。2は9より小さいため、 FIFOB から4個のレコード (2, 4, 6, 8) が読み出されます。1番目のソートロジックはこれらのレコードとフィードバックレジスタに格納されているレコード (7) をソートして (2, 4, 6, 7, 8) を得ます。その中の小さい4個のレコード (2, 4, 6, 7) を2番目のソートロジックに出力、最大のレコード (8) をフィードバックレジスタに書き戻します。このように、最終的に4個のレコード (2, 3, 4, 5) が出力されます。
同様に、サイクル3では、FIFOA から4個のレコード (9, 11, 13, 15) が読み出され、最終的に4個のレコード (6, 7, 8, 9) が出力、3個のレコード (15, 13, 11) がフィードバックレジスタに書き戻されます。
このように、入力の2つの系列がクロックサイクルあたり4個の出力レコードのスループットで正しくマージされます。
パイプライン処理によるクリティカルパスの短縮
図2のマージロジック回路の処理はパイプライン化できます。これにより、クリティカルパスが短縮され、回路の性能が大幅に向上されます。次の図はパイプライン化されたマージロジック回路の動作例を示します。
各ソートロジックの入力側に4個の (オレンジ色で示した) パイプラインレジスタを挿入します。これらのパイプラインレジスタは、フィードバックレジスタのように最小のレコード (この例では0) で初期化します。
具体的な動作例を説明します。この例の入力系列は図2と同じです。
サイクル1では、FIFOA の最小レコード1が FIFOB の最小レコード2より小さいため、FIFOA から4個のレコード (1, 3, 5, 7) が読み出され、1番目のソートロジックの入力側のパイプラインレジスタに書き込まれます。このサイクルでは、すべてのソートロジックでパイプラインレジスタから4個のレコード (0, 0, 0, 0) とフィードバックレジスタから1個のレコード (0) をソートして (0, 0, 0, 0, 0) を得ます。そのため、すべてのフィードバックレジスタは0で更新され、マージロジック回路の出力は (0, 0, 0, 0) です。これらは2つの入力系列からのレコードではないため出力系列から除外します。
サイクル2では、FIFOB の最小レコード2が FIFOA の最小レコード9より小さいため、FIFOB から4個のレコード (2, 4, 6, 8) が読み出されます。1番目のソートロジックはパイプラインレジスタからの4個のレコード (1, 3, 5, 7) とフィードバックレジスタから1個のレコード (0) をソートして (0, 1, 3, 5, 7) を得ます。その中の小さい4個のレコード (0, 1, 3, 5) を2番目のソートロジックとの間のパイプラインレジスタに出力し、最大のレコード (7) をフィードバックレジスタに書き戻します。2番目と3番目のソートロジックの入出力はサイクル1と同じです。出力されるレコード (0, 0, 0, 0) は2つの入力系列からのレコードではないので出力系列から除外します。
サイクル3では、FIFOA の最小レコード9が FIFOB の最小レコード10より小さいため、FIFOA から4個のレコード (9, 11, 13, 15) が読み出されます。1番目のソートロジックはパイプラインレジスタからの4個のレコード (2, 4, 6, 8) とフィードバックレジスタからの1個のレコード (7) をソートして (2, 4, 6, 7, 8) を得ます。その中の小さい4個のレコード (2, 4, 6, 7) を2番目のソートロジックとの間のパイプラインレジスタに出力し、最大のレコード (8) をフィードバックレジスタに書き戻します。同様に、2番目のソートロジックは4個のレコード (0, 0, 1, 3) を3番目のソートロジックとの間のパイプラインレジスタに出力し、1個のレコード (5) をフィードバックします。3番目のソートロジックの入出力はサイクル1とサイクル2と同じです。同様に、このサイクルの出力レコード (0, 0, 0, 0) も出力系列から除外します。
サイクル4では、FIFOB の最小レコード10が FIFOA の最小レコード17より小さいため、FIFOB から4個のレコード (10, 12, 14, 16) が読み出されます。1番目のソートロジックはパイプラインレジスタからの4個のレコード (9, 11, 13, 15) とフィードバックレジスタからの1個のレコード (8) をソートして (8, 9, 11, 13, 15) を得ます。その中の小さい4個のレコード (8, 9, 11, 13) を2番目のソートロジックとの間のパイプラインレジスタに出力、最大のレコード (15) をフィードバックレジスタに書き戻します。同様に、2番目のソートロジックは4個のレコード (2, 4, 5, 6) を3番目のソートロジックとの間のパイプラインレジスタに出力し、1個のレコード (7) をフィードバックします。3番目のソートロジックは4個のレコード (0, 0, 0, 1) を出力し、1個のレコード (3) をフィードバックします。この出力は、図2の cycle 1 の出力と同じです。(0, 0, 0) も出力系列から除外します。
サイクル5では、FIFOA の最小レコード17が FIFOB の最小レコード18より小さいため、FIFOA から4個のレコード (17, 19, 21, 23) が読み出されます。1番目のソートロジックは4個のレコード (10, 12, 14, 15) を2番目のソートロジックとの間のパイプラインレジスタに出力し、最大のレコード (16) をフィードバックレジスタに書き戻します。2番目のソートロジックは4個のレコード (7, 8, 9, 11) を3番目のソートロジックとの間のパイプラインレジスタに出力し、1個のレコード (13) をフィードバックします。3番目のソートロジックは4個のレコード (2, 3, 4, 5) を出力、1個のレコード (6) をフィードバックします。この出力 (2, 3, 4, 5) は、図2の cycle 2 の出力と同じです。
このように、図2の動作例のように、2つの入力系列がクロックサイクルあたり4個の出力レコードのスループットで正しくマージされます。
パイプラインレジスタを挿入することにより、マージロジック回路全体のクリティカルパスはソートロジック内のパスになります。次の図はそのようなクリティカルパスを赤色でハイライトしています。
図中に示した例は図3の cycle 5 の1番目（左端）のソートロジックの状態です。ソートロジック内のソートオペレーションは、ソートされている入力系列 (b1, b2, b3, b4) にフィードバックレジスタに格納されているレコード f を適切な場所に挿入することです。これは、上の図に示すように、4個のコンパレータ ( 丸で＜を囲んだ記入したシンボルで表現)、2個の2入力マルチプレクサ 、3個の３入力マルチプレクサで実現できます。マルチプレクサは楕円で囲んだMuxで表現しています。一般的に、E レコードのマージロジック回路のソートロジックは、E 個のコンパレータ、2個の2入力マルチプレクサ、E-1 個の３入力マルチプレクサで実現できます。
- 最小のレコード (c1) を出力するマルチプレクサの入力: b1, f
- ci (2 ≤ i ≤ E) を出力するマルチプレクサの入力: bi-1, bi, f
- フィードバックレジスタに出力するマルチプレクサの入力: bE, f
ソートロジック内の処理をパイプライン化することにより、クリティカルパスのゲート段数を更に削減できます。次の図は2段パイプラインのソートロジックを示します。
1番目のステージ (左側のステージ) はフィードバックレジスタに格納されているレコードと各入力レコードを比較し、最大のレコードをフィードバックレジスタに書き戻します。2番目のステージ (右側のステージ) は1番目のステージの比較結果を用いてマルチプレクサの出力を決定します。
このように、マージロジック回路全体のクリティカルパスは、図5に赤色でハイライトした、1個のコンパレータと1個の2入力マルチプレクサだけになります。
提案したマージロジック回路の特徴
提案したマージロジック回路の最も重要な特徴は、1サイクルあたりの出力レコード数 (E) を増やしてもクリティカルパスは1個のコンパレータと1個の2入力マルチプレクサの一定で変わらないことです。次の図は E=8 の場合のソートロジックアーキテクチャを示します。
図5に示した E=4 の場合のソートロジックアーキテクチャに比べて、コンパレータとマルチプレクサの数が増えますが、クリティカルパスは1個のコンパレータと1個の2入力マルチプレクサのままです。
前回の記事で説明したように、マージロジック回路の性能は1サイクルあたりの出力レコード数 (E) と動作周波数 (F) の両方に比例します。従来のマージロジック回路では、E を増やすと、クリティカルパスのゲート段数が増加するため F が大幅に低下します。一方、提案したマージロジック回路では、E を増やしても、クリティカルパスのゲート段数が一定で変わらないので高い F 維持できます。これにより、非常に高いソーティング性能を達成できます。
まとめ
今回は、私たちが論文 [1] で提案したマージロジック回路のアーキテクチャ、動作例、特徴を説明しました。これを使って、当時の最速の FPGA ソーティングアクセラレータと比較して、3倍を超える高い性能を達成しました。詳しくは次回の記事で解説します。
東工大 Thiem Van Chu
参考文献
- Susumu Mashimo, Thiem Van Chu, and Kenji Kise, “High-Performance Hardware Merge Sorter,” The 25th IEEE International Symposium On Field-Programmable Custom Computing Machines (FCCM), May 2017.