サブロウ丸

サブロウ丸

主にプログラミングと数学

サーベイ: Automatic Graph Partitioning for Very Large-scale Deep Learning

Tanaka, Masahiro, et al. "Automatic graph partitioning for very large-scale deep learning." 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2021.
@inproceedings{tanaka2021automatic,
  title={Automatic graph partitioning for very large-scale deep learning},
  author={Tanaka, Masahiro and Taura, Kenjiro and Hanawa, Toshihiro and Torisawa, Kentaro},
  booktitle={2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)},
  pages={1004--1013},
  year={2021},
  organization={IEEE}
}

背景

  • モデルの巨大化が進んでおり、メモリの制約や計算時間の点からも分散処理が必要
  • 既存の(pytorch)などのフレームワークでほとんど自動でやってくれるのはdata-parallelくらいで、 モデル並列には人の手によるチューニングが必要

どんなもの?

  • モデル並列において、graph partitionをDPベースで行う
  • 計算グラフを計算+通信時間が均等になるように指定した個数kに分割し、同時にそれぞれのcomponentに何個のdeviceを割り当てるのかを求める

先行研究と比べてどこがすごい?

  • ユーザが指定する項目が少ない(使用するdevice数やそのメモリくらい)
    • meth-tensorflowなどは並列する次元を指定する必要がある
  • StreamItのGPU処理のための手法をDeepLearningに初めて適用した

技術や手法のキモはどこ?

  • 先行研究(Scalable framework for mapping streaming applications onto multi-GPU systems)の手法により計算グラフを分割したものをトポロジカルソートで一列に並べ、
  • その列をどこで分割してk個に分ければ良いかをDPで求める
  • その際に、分割したコンポーネントに何個deviceを割り当てるのかも同時に考えて、最終的に計算+通信量がなるべく均等な分割を目指す。

どうやって有効だと検証した?

  • BERTとResNetの巨大モデルを学習させ、スループットを比較
    • BERT, 129億パラメタ
    • ResNet
  • 比較対象は, Megatron-LM, GPipe-Hybrid, PipeDream-2BW
    • GPipe-HybridはPipeDream-2BWのデータパラレルと併用する実装を用いた
  • BERTの実験結果
    • GPipe-Hybridよりも高いスループット、Megatron-LMよりも5倍大きなモデルの学習に成功
    • PipeDream-2BWとは同程度(か少し劣る) (しかしpipedreamはparameter stalenessのせいで学習効率が落ちるという指摘がある)
  • ResNetの実験結果
    • 小さいResNetでの比較ではdata-parallelのスループットの半分くらい (好意的には半分に抑えられている)
    • 大きいResNetではdata-parallelではメモリ不足で、GPipeと比較して高いスループットを確認
    • 提案手法のGPUs=32とGPUs=8を比較すると8の方がスループットが高い(当然かもですが)

議論はある?

  • DPを実行するときに計算+通信時間のデータをプロファイルから取り出す必要があり、そのプロファイルの正確性によって分割の性能も変わる
  • 計算グラフ分割がbottle-up型の逐次的な貪欲法であり、最適解との差がどれほどあるのかが気になる。
  • deviceの階層構造を考慮できない (node間 or node内の通信スピードを考慮した分割(stage-level partitioning)はいまのところ考えられていない)

次に読むべき論文は?

  • Automatic graph partition系
    • (2018, 87 cited) Exploring Hidden Dimensions in Parallelizing Convolutional Neural Networks.
    • (2019, 242 cited) Beyond Data and Model Parallelism for Deep Neural Networks.
    • (2019, 79 cited) Supporting Very Large Models using Automatic Dataflow Graph Partitioning.
  • Graph partition algorithm系
    • (1996 14 cited) Parallel multilevel k-way partitioning scheme for irregular graphs.
    • (2012, 65 cited) Scalable framework for mapping streaming applications onto multi-GPU systems.

Appendix: Scalable framework for mapping streaming applications onto multi-gpu systems.について

やっつけDeepL翻訳を記載。

Abstract

GPUは,大規模な並列処理コアを利用して,グラフィックス・アプリケーションで頻繁に見られる特定のストリーミング計算パターンの性能を向上させることができる。残念ながら、他の多くの汎用アプリケーションは、必要なストリーミング動作を示す一方で、不利なデータレイアウトや低い計算対通信比率を持ち、GPUでの真っ当な実行に支障をきたしています。本論文では、汎用ストリーミングアプリケーションをマルチ GPUシステムにマッピングできる、効率的でスケーラブルなコード生成フレームワークについて説明します。このフレームワークは、マルチGPUシステムによって公開されるコアとメモリ階層全体に及びます。このフレームワークのいくつかの重要な特徴は、複雑なストリーミングアプリケーションに必要なスケーラビリティを保証することです。まず、与えられた共有メモリ制約の下で最高のパフォーマンスを達成するために複雑なアプリケーションを分割する、効率的なストリームグラフパーティショニングアルゴリズムを提案します。次に、得られたパーティションは、効率的なアーキテクチャ主導の戦略を用いて、複数のGPUマッピングされます。このマッピングでは、通信のオーバーヘッドを考慮しながら、作業負荷のバランスをとります。最後に、マルチGPUシステム上でパーティションを実行するために、非常に効果的なパイプライン実行が採用されます。このフレームワークは、プログラミング言語StreamItコンパイラのバックエンドとして実装されています。我々の包括的な実験により、このフレームワークのスケーラビリティと、従来の最先端ソリューションと比較した大幅な性能向上が示されました。

www.DeepL.com/Translator(無料版)で翻訳しました。

Conclusion

我々は、ほとんどのストリーム処理アプリケーションを自動的にGPUマッピングするスケーラブルなフレームワークを提案した。また、複雑なアプリケーションを複数のパーティションに分割する効率的なグラフ分割アルゴリズムを開発し、各パーティションが小さなオンチップSMメモリを有効に活用することで、良好なパフォーマンスを達成しました。本提案方式では、従来の単一パーティション方式を上回る性能を得ることができました。さらに、本提案手法では、最大4GPUまで性能を拡張することが可能です。また、CPUコアで実行することにより、ステートフルフィルタもサポートします。提案するコード生成方式は、個々のGPU内、複数のGPU間、およびGPUとCPUコアのデータ交換をオーケストレーションすることが可能です。その結果、複数のGPUを対象とした場合のスケーラビリティと改善効果が示されました。 ある種の厄介な並列アプリケーションは、大規模なマルチノード、マルチ GPU システムにうまくマッピングできる可能性があります。しかし、単一ノードでは、電力、インターコネクト、フォームファクタの問題から、ノードあたりのGPU数が現在の4個から大幅に増加することはないと思われます。本研究は、複雑でしばしば密結合するストリーミングアプリケーションを、複数のGPUに自動的に分割してマッピングできることを示した初めての例です。今後の課題として、StreamIt(またはその派生版)において、より大規模で複雑なアプリケーションをどのように指定し、マルチGPUノードの大規模クラスタ上で実行できるかを調査したいと思います。

www.DeepL.com/Translator(無料版)で翻訳しました。

StreamIt プログラミング言語 [8] は、同期データフローグラフ [18] をベースとしています。StreamIt はマルチコア [9], Cell [17], Raw [8], さらには FPGA [10] を含む無数のアーキテクチャ上でコンパイルされています。さらに、StreamIt の GPU プラットフォームへの粗視化マッピングに関する研究も行われています [23]。 GPUへのマッピングは通常、グローバルメモリを介して互いに通信するカーネルを含みます。そのため、このメモリにアクセスする際のレイテンシが大きく、全体のパフォーマンスが制限されます[24]。最近提案された方法 [11, 12] は、2 種類の専用スレッドを使用し て、メモリアクセス方式を改善しました。(1)グローバルメモリからSMメモリへのデータのロード/ストア、(2)SMメモリにプリロードされたデータを使用した計算。この2つの方式は、計算の組織化において対照的である。一方は,StreamItグラフノード[12]の粗視化されたタスク並列性を利用し,各ストリームグラフスケジュール実行時に重要なデータ並列最適化の機会を残しています.もう1つは,より細かいデータレベルの並列性を利用するもので,ストリームグラフスケジュールの1回の実行が複数のコムピューティングスレッドにまたがります[11].しかし、後者の方法は、ストリームグラフスケジュール全体を単一のパーティションマッピングしようとするため、大規模なアプリケーションにうまく対応できない。 複数のパーティションを利用する以外に、スケーラビリティの問題に対処する有望なソリューションとして、マルチ GPU システムの利用があります。このようなシステムは、大規模なデータセットのアプリケーションを処理するのに適しています[22]。マルチ GPU システムでの実行は、ロードバランシング [5]や投機的実行 [6]などのさまざまなランタイムスキームによって改善されてきました。これらのスキームの多くは、マルチ GPU システム上で実行されるアプリケーションの性能を、計算コストとさまざまな通信コストの特徴づけに基づいて推定する静的手法によって補完することができます[21]。GPU アーキテクチャの性能モデリングは、解析的・定量 的アプローチによって包括的に研究され [3、25]、計算とメ モリーアクセスの重要なバランス、および SM メモリの使 用に焦点を当てました。しかし、これらの研究は、アプリケーションの自動マッピングや、複数のGPU上でのストリーミング言語の実行モデルを統合的に提供することは試みられていません。 上記の課題を踏まえ、このマルチ GPU マッピング作業では、StreamIt アプリケーションをマッピングする前にパーティショニングすることで、ソリューション [11] のスケーラビリティにも取り組む予定です。これは、マルチGPUシステムのための最適なGPUカーネル生成、負荷分散マッピング、通信削減、パイプラインオーケストレーションを統合した最初のマッピングアットテンプトとなります。

www.DeepL.com/Translator(無料版)で翻訳しました。

BackGround

Mapping onto GPUs

ストリーミングマルチプロセッサ(SM)の処理コア数は、GPUの世代が新しくなるたびに増え続けています(S2050の32コア、S1070の16コアに対し、最新のnVidia GPUではSMあたり最大48コアに)。そのため、各SMでサポートされるスレッド数も比例して増加する。各SMのスレッドは、ワープと呼ばれる32個のスレッド群に分割される。ワープの実行は、少ない処理コアのハードウェアスケジューラによってインターリーブされる。同じワープに属するすべてのスレッドは、各タイムステップで同じ命令を実行し(ロックステップ実行、SIMDの一種)、発散したフローは直列化される。しかし、異なるワープに属するスレッドは、発散フローのペナルティとは無関係である。ハードウェアスケジューラは、実行するワープを選択し、選択されたワープから処理コアに命令をディスパッチする。命令が実行パイプラインを伝わっている間や、メモリオペランドを待っている間に、スケジューラはゼロオーバーヘッドで別のワープを実行するように切り替える。その結果、多数の並列スレッドを生成しても、実際にはプロセッシングコア上でスレッドの実行がインターリーブされる。 多数のスレッドをインスタンス化するもう一つの理由は、上記のインターリーブメカニズムによって、GPUグローバルメモリアクセスの長い遅延を隠蔽するためです。StreamIt アプリケーションを GPUマッピングする場合、細粒度のオペレータはメモリチャネルを介して互いに通信しなければならないため、グローバルメモリへのアクセスがより頻繁になります。SM メモリを使用してグローバルメモリからデータをプリフェッチしても、オペレータがチャネルから読み込んだデータを再利用することはほとんどないため、ボトルネックはまだ見えています。先行研究 [11] では、ストリーミング・アプリケーションのグローバル・メモリ・アクセスの負荷を軽減するスキームが説明されています。まず,複数のオペレータを同じ GPU カーネルで実行し,SM メモリを介して通信することができます.次に,メモリアクセス(M)スレッドとコンピュート(C)スレッドという 2 つの異なるクラスのスレッドをインスタンス化します.MスレッドはグローバルメモリからSMメモリへのデータのプリフェッチのみを担当し、CスレッドはMスレッドによってプリフェッチされたデータに対してのみ計算を実行する。CスレッドとMスレッドの数、およびそれらの実行スケジュールを決定するために、効率的なヒューリスティックが使用されます。ストリームグラフ内のデータレベルの並列性を解析し、ストリームグラフの実行全体をSM内の複数のCスレッドにマッピングする。この方式は、GPUをフルに活用するために、他のすべてのSMに複製されます。 このようなマッピングフローは、ストリームグラフの並列実行に必要なメモリ容量がSMのメモリ容量以下であれば実現可能である。大規模なデータセットや複雑なストリーミングアプリケーションによってメモリ要件が増加すると、サポートされる並列実行の数が減少することになります。本論文では、これらのアプリケーションのストリームグラフを、メモリ要件がSMメモリ制約と一致するような小さなパーティションに分割することを検討しています。さらにスケーラビリティを高めるために、これらのパーティションをマルチGPUプラットフォーム上にマッピングすることを検討します。以上により、ストリーミングアプリケーションをGPUマッピングするためのスケーラブルなマッピングフレームワークを提案します。フレームワークの概要は次のセクションで説明します。

www.DeepL.com/Translator(無料版)で翻訳しました。

Experimental Results

我々の自動化されたフレームワークのスケーラビリティと効率を示すために、いくつかのStreamItベンチマークマッピングして達成されたパフォーマンスを示す。これらのベンチマーク(表1)はStreamItベンチマーク群[2]の代表的なセットです。これらのベンチマークフレームワークによって自動的に処理され、複数のパーティションに対応するコードが生成されました。ベンチマークはパラメータNを用いてより大きなストリームグラフを作成するように変更された(例えば、N=40のDESのグラフは1047個のフィルタに達した)。ストリームグラフは、同じCPUホストに接続された1~4台のGPUマッピングされています。ベンチマークは、計算結果を検証するコードを含むソースフィルターとシンクフィルターで拡張されました。これらのフィルタは内部状態を保持するため、このようなフィルタに提供するサポートも検証されました。このフレームワークはStreamIt 2.1.1コンパイラのバックエンドとして実装されました。ベースラインのCPUタイミングは、2GHzで動作するIntel Xeon CPU E5405で、実行ファイルはStreamItのユニプロセッサのバックエンドで生成し、GCC 4.1.2の「-O3」オプションでコンパイルして得られました。実験では、新しい C2070 "Fermi" GPU プラットフォームをターゲットにしています。

www.DeepL.com/Translator(無料版)で翻訳しました。