大規模機械学習のためのプログラミング手法、計算モデル、Xgboost および MXNet の事例

[[191977]]

現在、機械学習のトレンドは、従来の方法のシンプルなモデル + 少量データ (手動でラベル付けされたサンプル) から、シンプルなモデル + 大量データ (ロジスティック回帰に基づく広告クリック率予測など) へ、そして現在の複雑なモデル + 大量データ (ディープラーニング ImageNet 画像認識、DNN に基づく広告クリック率予測など) へと進化しています。

業界でよく使われる大規模機械学習のシナリオをまとめてみましょう。

この共有は次の 3 つの部分から始まります。

1. 並列コンピューティングプログラミング技術

ベクトル化
オープンmp
グラフィックプロセッサ
mpi

2. 並列計算モデル

BSPS の
エスエスピー
料金
パラメータサーバー

3. 並列コンピューティングの例

Xgboost の分散ライブラリ Rabit
Mxnet の分散ライブラリ ps-lite

並列コンピューティングプログラミング技術

まず、大規模機械学習の工学的基盤となる並列プログラミング技術について述べます。

ベクトル化

ベクトル化されたコンピューティングは、特殊なタイプの並列コンピューティングです。一度に 1 つの操作のみを実行する一般的なプログラムと比較すると、複数の操作を同時に実行できます。通常は、異なるデータに対して同じ命令または一連の命令を実行したり、配列/ベクトルに命令を適用したりします。

X86 アーキテクチャ CPU では、主なベクトル化プログラミングテクノロジは SSE と AVX です。 Intel のストリーミング SIMD 拡張 (SSE) テクノロジーは、CPU の浮動小数点計算機能を効果的に強化できます。現在主流のコンパイラである GCC と Visual Studio は、SSE 命令セットのプログラミングサポートを提供しており、ユーザーはアセンブリコードを記述せずに C++ コードで SSE 命令の機能を直接使用できます。 Intel SSE 命令セットでサポートされているプロセッサには 16 個の 128 ビットレジスタがあり、各レジスタには 4 個の (32 ビット) 単精度浮動小数点数を格納できます。 SSE は、浮動小数点数をこれらの 128 ビットレジスタにロードし、これらのレジスタ内の数値に対して算術演算と論理演算を実行し、結果をメモリに戻すことができる命令セットも提供します。 AVX は SSE に似ています。AVX は 16 個の 128 ビットレジスタすべてを 256 ビットレジスタに拡張し、256 ビットベクトル計算をサポートします。理想的には、AVX の浮動小数点パフォーマンスは SSE の最大 2 倍になります。 ARM アーキテクチャはモバイルデバイスで広く使用されています。ARM ベクトル命令 Neon は、16 ビットの長さと 128 ビットのベクトルレジスタを提供します。

簡単に言えば、SSE 命令セットは 4 倍の加速を実現し、AVX は 8 倍の加速を実現できます。

使い方もとても簡単です。

AVX命令セットのプログラミング例:

 (i=0; i<cntBlock; ++i)の場合
   {
       // [AVX] ロード
       yfsLoad = _mm256_load_ps(p);
       // [AVX] 単精度浮動小数点パック加算
       yfsSum = _mm256_add_ps(yfsSum、yfsLoad);
       //AVX命令は一度に8つの浮動小数点数を処理できます
       8 です
   }
   // マージします。
   q = (const float *)&yfsSum;
   s = q[0] + q[1] + q[2] + q[3] + q[4] + q[5] + q[6] + q[7];

これは配列を合計する高速化の例です。

現在、GCC などの主流のコンパイラがこれをサポートしています。

2 つ目は、誰もが最もよく知っているマルチスレッドプログラミングテクノロジです。

UNIX/Linux では pthread、Windows 環境では WinThread。しかし、並列機械学習と比較すると、一方では、マルチスレッドプログラミング技術の使用は開発コストが高く、同期や排他制御などの問題を適切に処理する必要があります。他方では、異なるプラットフォームで使用されるマルチスレッドプログラミングライブラリが異なるため、移植性の問題も発生します。

オープンmp

OpenMP は、共有メモリ並列設計をサポートするライブラリです。特に、マルチコア CPU での並列プログラミングに適しています。マルチスレッドプログラミングの難易度を大幅に軽減し、現在、機械学習の主流のマルチスレッドソリューションとなっています。

この例を見てみましょう。従来の for ループステートメントを高速化するのは簡単です。 OpenMP は MapReduce に似たコンピューティングパラダイムを実装することもできます。詳細については、openmp の公式ドキュメントを参照してください。

グラフィックプロセッサ

GPU プログラミングは現在、非常に人気のある並列コンピューティングソリューションです。

これが GPU と CPU の違いです。

GPU が高速なのはなぜですか?

CPU は主にシリアル命令向けに最適化されていますが、GPU は超並列操作向けに最適化されています。
CPU と比較すると、GPU は同じチップ領域上に多くのコンピューティングユニットを備えているため、GPU のコンピューティングパフォーマンスはより強力になります。一方、CPU にはより多くのキャッシュと関連する制御コンポーネントがあります。
GPU は CPU よりも帯域幅が広くなります。

CUDA は現在主流の GPU プログラミングです。

これも配列の合計の例です。 GPU プログラミングはそれほど難しくないことがわかります。従来のプログラミングとの違いは次のとおりです。

国際ピ

MPI はマルチマシン並列ソリューションです。その中核はメッセージの送受信であり、マルチレベル並列処理における通信の問題を解決します。

MPI プログラムの実行フローです。 MPI の学習難易度も比較的低いです。

MPI_Init(…); 環境を初期化する

MPI_Comm_size(…) プロセス数を取得する

MPI_Comm_rank(…) プロセス番号を取得する

MPI_Send(…) メッセージを送信

MPI_Recv(…) メッセージを受信

MPI_Finalize() 並列終了関数

これらが主な6つの機能です。

MPI 関数は多数ありますが、関数には主に 2 つのカテゴリがあります。

1つはデータを送信することです。

これはデータを受信するためのプロトコルです。これは一般的な MapReduce と非常によく似ています。

まとめると、ハードウェアの状態に基づいて適切な並列コンピューティングソリューションを選択できます。

ここで覚えておいていただきたいのは、GPU プログラミングを行い、CUDA テクノロジを使用する場合は、他のグラフィックカードは動作しないため、Nvidia グラフィックカードを購入する必要があるということです。

分散機械学習システムが解決する必要がある問題は 3 つあります。

複数のタスクをより効率的に分割する方法
サブタスクをスケジュールする方法
各ノードの負荷を分散する

並列コンピューティングモデル

BSPS の

これは、一般的な機械学習の問題のモデリングと最適化です。大規模機械学習の核となるのは、勾配計算の並列化です。 BSP は初期の並列コンピューティングモデルであり、現在主流の並列コンピューティングモデルの 1 つでもあります。

各ステップは詳細に分割されています。

計算のプロセスも、計算→同期→計算→同期……と比較的わかりやすいです。

BSP には次の利点があります。

プロセッサとルーターを分離し、コンピューティングタスクと通信タスクの分離を重視します。ルーターはポイントツーポイントのメッセージ伝送のみを完了し、結合、複製、ブロードキャストなどの機能を提供しません。これにより、特定の相互接続ネットワークトポロジが隠されるだけでなく、通信プロトコルも簡素化されます。
バリア同期を使用してハードウェアに実装されたグローバル同期は、制御可能な粗粒度レベルであり、プログラマに過度の負担をかけずに密に結合された同期並列アルゴリズムを効率的に実行する方法を提供します。

BSP モデルのこれらの特性により、BSP モデルは並列コンピューティングの主流モデルの 1 つとなっています。オープンソースの Mahout、Apache Huma、Spark mllib、Google Pregel、Graphlab、xgboost などの並列実装はすべて BSP モデルに基づいています。

BSP モデルでは、各ラウンドの結論の後に同期が必要であり、これによりバレル効果が発生しやすくなります。タスクの分割では各タスクの計算負荷が完全に均一ではなく、複雑な分散コンピューティング環境では各マシンのハードウェア条件も異なるため、BSP モデルの各ラウンドの反復の効率は、最も遅いコンピューティングタスクによって決まります。この現象を軽減するために、SSP モデルが提案されました。

エスエスピー

SSP モデル

SSP 内の各タスクプロセスをワーカーと呼びます。SSP モデルは、境界を設定することによって同期のタイミングを決定します。最も速いワーカーがこの制限を超えると、すべてのワーカーがパラメータを同期します。この境界は、反復回数またはパラメータ更新の差に基づいて決定できます。 SSP プロトコルの利点は、高速ワーカーでは古いパラメータバージョンの問題が発生するため、各反復でネットワーク通信が必要になるため、コンピューティングとネットワーク通信の時間のオーバーヘッドのバランスをとる効果が得られることです。

SSP モデルは収束することが数学的に証明されています。

その理由は、すべての道はローマに通じる、と説明できます。

機械学習プログラムの場合、中間結果のエラーは許容可能であり、最適に収束できるパスが複数存在するため、少量のエラーはランダムノイズに似たものになる可能性がありますが、最終的な収束結果には影響しません。各反復でエラーが発生する可能性がありますが、複数回の反復の後、平均エラーはゼロに近づきます。それぞれの解決パスが最適なものではないとしても、最終的には最適な解決につながる全体的なパスが見つかります。このパスは最速のパスではありませんが、通信の利点により、特にデータスケールとパラメータースケールが非常に大きく、マルチマシン並列環境の場合、全体的なソリューション速度は BSP よりも速くなります。

料金

ASP は完全に非同期なメソッドであり、BSP の同期リンクをキャンセルすることと同等です。

ASP はより高速に実行されますが、もちろん収束が保証されるわけではありません。

SSP プロトコルは、コンピューティングとネットワーク通信のオーバーヘッドを効果的にバランスさせることができます。

非凸問題の場合、BSP と SSP が収束する最適解は異なる場合があります。非凸最適化問題 (ニューラルネットワークなど) の場合、多数の局所最適解が存在し、確率的勾配降下法 (局所最適解からジャンプできる) はバッチ勾配降下法よりも効果的に機能します。

パラメータサーバー

パラメータサーバーは、最近、分散機械学習の分野で非常に人気のあるテクノロジーです。

パラメータサーバーパラメータサーバーでより重要な問題は、各コンピューティングノードのパラメータ同期です。

シーケンシャル: これは実際には同期タスクです。タスク間には順序があります。前のタスクが完了した場合にのみ、次のタスクを開始できます。これは同期方式です。イベンチュアル: シーケンシャルとは対照的に、すべてのタスク間に順序はなく、それぞれが独立して独自のタスクを完了します。これは非同期形式です。制限付き遅延: これはシーケンシャルとイベンチュアルの妥協案です。最も速いコンピューティングタスクが最も遅いコンピューティングタスクよりも一定のしきい値以上速い場合、または勾配に対するコンピューティングタスクの累積更新値が一定のしきい値より大きい場合に待機します。

次の 4 つのモードの利点と欠点をまとめます。

並列コンピューティングの例

Xgboost の分散ライブラリ Rabit

Xgboost は非常に強力な機械学習パッケージであり、その配布も非常に優れています。それでは、早速見ていきましょう。

Xgboost の分散実装には次の機能があります。

OpenMpはマルチコア並列処理をサポート
GPUアクセラレーションのためのCUDAサポート
Rabitは分散型をサポート

その中核は Rabit です。Xgboost は分散コア機能を抽象化します。Rabit は BSP モデルに基づいており、Broadcast と AllReduce という 2 つの基本プリミティブを通じて分散機能を実装します。 Broadcase と AllReduce は基本的に MPI と同じ機能を持っており、設計思想も似ているので、MPI を直接使用しないのはなぜでしょうか?その理由は、Rabit はこれに基づいてより優れたフォールトトレラント処理機能を提供し、MPI の欠点を補うためです。

従来の MapReduce モデルでは、機械学習の並列化がなぜそれほど制限されているのでしょうか?

上の図は従来のMRを示し、下の図はXGBOOSTの並列計算プロセスを示しています。

Rabit は 2 つの領域で最適化を行いました。1 つ目は、反復の各ラウンドの後に計算結果をストレージシステムに格納する必要がなく、メモリ内に直接保持されることです。2 つ目は、反復の各ラウンドの後にデータの再配分プロセスがなく、次の反復ラウンドが直接実行されるため、計算効率が大幅に向上します。

Xgboost の Rabit は分散操作を非常にうまくカプセル化しており、他のシステムに簡単に移植できます。 Rabit をベースに分散機械学習プログラムを開発できます。

 #include <rabit/rabit.h>
 Allreduce<op:: Sum >(&a[0], N);
 rabit::Broadcast(&s, 0);

Rabit は、プログラム開発を容易にする Allreduce と Broadcast という 2 つの基本操作を提供します。

MXNet の分散ライブラリ ps-lite

最後に、mxnet についてお話しましょう。

ps-lite は、パラメータサーバーモデルに基づく mxnet 分散現実の中核です。

Ps-lite は非常に使いやすく、既存の機械学習プログラムを分散型プログラムに簡単に変換できます。Ps-lite の中核は、データ交換用の分散型キー値ストレージを提供する KVStore です。主な機能は 2 つあります。

push: キーと値のペアをデバイスからストレージにプッシュします。これは、コンピューティングノードによって、更新されたパラメーター値をパラメーターサーバーにプッシュするために使用されます。
プル: ストレージからキーの値をプルし、コンピューティングノードがパラメータサーバーから関連するパラメータ値を取得できるようにします。

次の例では、単一マシンの勾配降下アルゴリズムを分散勾配降下アルゴリズムに変更します。単一マシン勾配降下アルゴリズム:

 ( int i = 0; i < max_iter; ++i)の場合{
   ネットワークを転送します。 
 
   ネットワーク.後方();
   ネットワークの重み -= η * ネットワークの勾配
}

ps-lite に基づく分散勾配降下法:

 KVStore kvstore( "myps " );
 kvstore.set_updater([](NDArrayの重み、NDArrayの勾配) {
    重み -= η * 勾配;
  });
 ( int i = 0; i < max_iter; ++i)の場合{
   kvstore.pull(ネットワークの重み);
   ネットワークを転送します。
   ネットワーク.後方();
   kvstore.push(ネットワークの勾配);
 }

これは、ps-lite 分散変換の最も一般的な例です。

これらのオープンソースの分散フレームワークを使用して、分散アプリケーションを簡単に構築できます。たとえば、職場では、ps-lite をベースにした word2vec と libffm のディストリビューションをすぐに実装しました。特に word2vec の場合、libffm の公式バージョンはマルチスレッド化されているため、変換が容易になります。

著者について

陳華清は、Meituan Hotel and Tourism 部門の上級技術専門家です。Meituan Hotel and Tourism のデータ構築およびその他の側面を担当しています。検索、データマイニング、機械学習プラットフォームの開発経験は 10 年あります。Alibaba ではデータマイニングに、360 では広告アルゴリズムに携わってきました。

<<: リー・ヤンがスマートシティ建設について語る：ハードウェアからプラットフォームまで、Terminusエコシステムが先導する

>>: TensorFlowはディープラーニングに基づく画像補完を実装する