新しい展開のアイデア | Minuet: GPU での 3D スパース畳み込みの高速化

この記事は、Heart of Autonomous Driving の公開アカウントから許可を得て転載したものです。転載については出典元にお問い合わせください。

元のタイトル: Minuet: GPU での 3D スパース畳み込みの高速化

論文リンク: https://arxiv.org/pdf/2401.06145.pdf

コードリンク: https://github.com/UofT-EcoSystem/Minuet

著者ユニット: トロント大学 Vector Institute Amazon Meta Samsung AI Centre Toronto CentML

カンファレンス: EuroSys'24

論文のアイデア:

スパース畳み込み (SC) は、本質的にスパースな 3D ポイント クラウドを処理するために広く使用されています。密な畳み込みとは異なり、SC は特定の場所への出力のみを許可することで、入力ポイント クラウドのスパース性を維持します。 SC を効率的に計算するために、既存の SC エンジンは、まずハッシュ テーブルを使用して、実行する必要がある一般行列乗算 (GEMM) 演算を格納するカーネル マップを構築し (マップ ステップ)、次に Gather-GEMM-Scatter プロセスを使用してこれらの GEMM 演算を実行します (GMaS ステップ)。この研究では、既存の最先端の SC エンジンの欠点を分析し、最新の GPU 向けにカスタマイズされた新しいメモリ効率の高い SC エンジンである Minuet を提案します。 Minuet は、(i) Map ステップで使用されるハッシュ テーブルを、GPU のオンチップ メモリ階層を最大限に活用する新しいセグメント ソートの二重走査バイナリ検索アルゴリズムに置き換えること、(ii) GMaS ステップの Gather および Scatter 操作でタイルのサイズを自動的に調整する軽量スキームを使用して、各 SC レイヤー、データセット、および GPU アーキテクチャの特定の特性に合わせて実行を適応させること、(iii) パディング効率の高い GEMM グループ化アプローチを採用して、メモリ パディングとカーネル起動のオーバーヘッドを削減することを提案しています。当社の評価では、エンドツーエンドのクラウド ネットワーク実行において、Minuet は従来の SC エンジンを大幅に上回り、平均 1.74 倍 (最大 2.22 倍) のパフォーマンス向上が見られました。この論文の新しいセグメントソート二重トラバーサルバイナリ検索アルゴリズムは、以前の SC エンジンと比較して、マップステップで平均 15.8 倍 (最大 26.8 倍) の高速化を実現します。

主な貢献:

この論文では、既存の SC エンジンの欠点を調査し、最新の GPU アーキテクチャ上で SC 実行を高速化するメモリ効率の高いエンジンである Minuet を提案します。

この論文では、SC でカーネル マッピングを構築するための新しいセグメント ソート デュアル トラバーサル バイナリ検索アルゴリズムを提案します。この論文で提案されたアルゴリズムは、GPU のオンチップ メモリ階層を最大限に活用します。この論文では、Gather および Scatter 操作で最適なパフォーマンスのタイルのサイズを動的に選択し、グループ化の前に GEMM 操作を並べ替えて、不要なデータ アクセスと計算を最小限に抑えます。

私たちは、さまざまな現実世界のデータセット、スパース 3D ネットワーク、GPU アーキテクチャを使用して Minuet を評価し、レイヤー単位およびエンドツーエンドのパフォーマンスの両方で従来の研究を大幅に上回ることを示しています。 Minuet は、SC の Map ステップでも優れた高速化を実現します。

論文の方法:

本研究では、様々なポイントクラウドネットワーク、実世界のデータセット、GPUアーキテクチャを使用して既存のSCエンジン[8、9、43]を特徴づけ、3つの重要な欠点があることを発見しました。まず、ハッシュテーブル（カッコウハッシュテーブル[1]など）を使用して、必要なGEMM操作を格納するカーネルマップを構築します。ただし、ハッシュ テーブルで多数のクエリを実行すると、不規則なデータ アクセスが発生し、そのほとんどは高価な GPU グローバル メモリによって処理されるため、データ アクセス コストが高くなります。次に、最先端の SC エンジンは、Gather および Scatter 操作で SC の複数の入力/出力機能チャネルをタイルで連続した機能チャネルのセットとして処理し、GPU メモリのスループットを向上させます。しかし、常に単一の固定タイル サイズが採用されており、パフォーマンスが低下することがわかります。図 4 では、最適なパフォーマンスを発揮するタイルのサイズは、ポイント クラウド ネットワークの各特定の SC レイヤー、実際のデータセット、および GPU アーキテクチャの特性によって異なることを示しています。 3 番目に、GMaS ステップでは、既存の SC エンジンがバッチ方式で複数の重みシフトに対応する GEMM 操作を実行します。つまり、GEMM オペランドにゼロ値を埋め込むことで複数の GEMM 操作を集約します。つまり、すべての GEMM オペランドに同じサイズを提供し、それらを単一のバッチ GEMM カーネルとして実行します。このようにして、GPUカーネルの起動オーバーヘッドを最小限に抑え、GPUハードウェアの使用率を向上させることができます[43]。しかし、従来の SC エンジンでは、GMaS ステップで GEMM 操作を Map ステップで生成された順序 (つまり、重みオフセットの順序) で集約していることがわかりました。このアプローチでは、パディングのオーバーヘッドが大きくなります (セクション 3)。つまり、多数のゼロ値が追加され、冗長なデータ アクセスと計算が多く発生します。

上記の問題に対処するために、本論文では、最新の GPU 向けにカスタマイズされた新しいメモリ効率の高い SC エンジンである Minuet を提案します。 Minuet は GPU のオンチップ メモリ階層を高度に活用して、SC 実行を入力データセットと GPU アーキテクチャの特性に適応させ、不要なデータ アクセスと計算を削減します。この論文では、マップステップにおいて、ハッシュテーブルベースの検索がGPU上のバイナリ検索よりも優れているという一般的な考えに異議を唱え[1, 2]、最新のGPUアーキテクチャ上のSCのマップステップでカーネルマップを構築するための革新的なバイナリ検索ベースのアルゴリズムを提案しています。この論文では、ソートクエリを実行する際にバイナリ検索が高いシステム効率を達成するという重要な観察を活用し、連続するソートクエリ間のデータ局所性を活用し、セグメント化されたソートの二重走査バイナリ検索アルゴリズムを提案します。

本論文で提案された SC アルゴリズムは、ハッシュ テーブル ベースの検索 (セクション 5.1.3) と同等の理論的な計算複雑度を達成し、大幅に高いメモリ効率を提供し、GPU オンチップ キャッシュのヒット率を向上させます (図 16b)。 GMaS 実行ステップでは、Minuet は 2 つの最適化を提供します。まず、各 Gather および Scatter 操作で複数の入力/出力機能チャネルをオンザフライで処理するためにタイルのサイズを調整します。この重要なテクノロジーにより、Minuet は、ポイント クラウド ネットワーク、実際のデータセット、GPU アーキテクチャ内の各 SC レイヤーの特定の特性に合わせて SC 実行を適応させることができ、Gather 操作と Scatter 操作の両方で高いシステム パフォーマンスを実現できます。次に、Minuet はパディング効率の高い GEMM 集約戦略を統合します。この戦略では、まず入力/出力特徴ベクトルのサイズに応じて GEMM 操作を並べ替え、次に GEMM 操作をバッチ化された GEMM カーネル起動に集約します。このようにして、Minuet は (i) ゼロ値のパディングの量を最適化し、GEMM カーネル内の不要なデータ アクセスと無駄なデータの計算を最小限に抑え、(ii) GEMM カーネルの起動オーバーヘッドを削減できます。

この論文では、さまざまな 3D ポイント クラウド ネットワーク、実際のデータセット、GPU アーキテクチャを使用して Minuet を徹底的に評価し、Minuet が以前の研究よりも大幅に優れていることを実証します。最先端の SC エンジンと比較すると、Minuet はエンドツーエンドのパフォーマンスが平均 1.74 倍 (最大 2.22 倍) 向上し、Map ステップでは平均 15.8 倍 (最大 26.8 倍) の高速化、GMaS ステップでは平均 1.39 倍 (最大 2.38 倍) の向上を実現します。

図 6. Minuet の概要。

図 1. 密畳み込みと疎畳み込み。

図 2. SC 実行は 2 つのステップに分けられます。簡潔にするために、この記事では 2 次元座標を使用して説明します。

図 5. SC で GEMM 操作を実行するさまざまな方法。青い四角と白い四角は、それぞれ実際の入力固有ベクトルとゼロで埋められた固有ベクトルを表します。 𝑥 と 𝑦 がそれぞれパディングされた特徴ベクトルと実際の入力特徴ベクトルの数であると仮定すると、パディングのオーバーヘッドは (𝑥/𝑦) と定義されます。

図 7. ランダム ウォーク クエリを実行するときに 4 つのクエリを実行するバイナリ検索の例 (つまり、ソートされていないクエリ (左) とソートされたクエリ アプローチ (右))。

図 8. 完全なクエリランキング (上) とセグメント化されたクエリランキング (下) の例。緑色の実線のボックスは、GPU グローバル メモリ内のマテリアライズされた配列を表します。緑の破線ボックスはメモリ内に実現されていない配列を表し、その値はオンザフライで計算されます。

図 9. 隣接する SC レイヤーにおける重みオフセットと出力座標のソート オーバーヘッドの最適化。

図 10. ソートされたソース配列 (バイナリ検索ツリーとして表される) 内のソートされたクエリ セグメントに対してバイナリ検索を実行するときに、逆バイナリ検索を使用してクエリ配列セグメント内のピボットの下限値を見つけ、比較回数を減らす例。

図 11. 二重走査バイナリ検索の実行手順。

実験結果:

要約:

Minuet は、GPU 上で 3D ポイント クラウド ネットワークを高速化する効率的な SC エンジンです。 Minuet は GPU オンチップ メモリ階層を高度に活用して、実行の並列性とメタデータ コストを改善し、SC 実行中の不要なデータ アクセスと計算を削減します。私たちの評価では、Minuet は、さまざまなスパース ポイント クラウド ネットワーク、データセット、GPU アーキテクチャにわたるエンドツーエンドの実行において、以前の最先端の SC エンジンを平均 1.74 倍大幅に上回るパフォーマンスを発揮することが示されています。私たちは、Minuet は最新の GPU 向けにカスタマイズされた、メモリ効率の高い新しい SC エンジンであると結論付けており、私たちの研究がポイント クラウド ネットワークやその他のスパース ディープラーニング ネットワークのさらなる包括的な研究と最適化戦略を促進することを期待しています。

オリジナルリンク: https://mp.weixin.qq.com/s/0K-LUMnQZ8fovouJiqkflw