ウエハースケールエンジン向けSimulated Annealingを複数タイルによる並列化で実装しました

皆さんこんにちは！

本記事では、Cerebras Wafer Scale Engine (WSE)にSimulated Annealing(SA)を並列分散で実装する方法を紹介します。

本記事の内容はこれらの記事の続きとなります。

1. ウエハースケール計算エンジンWSE-2においてSimulated-Annealingを実装しました
2. ウエハースケールエンジンにSimulated Annealingを分散並列実装しCS-2実機で動作確認しました

簡単なおさらい

Cerebras ウエハースケールエンジンとは

Cerebras ウエハースケールエンジンとは、Cerebras Systems社が開発したウエハ一枚を一つのチップとして使い切るプロセッサです。 その巨大さとデータフローアーキテクチャから、唯一無二のプロセッサとして機械学習やHPCなどのワークロードで使用されています。

チップ上にコアが２次元メッシュをなす形で分散しており、チップ内でも事実上の分散並列コンピューティングを行うことが出来ます。 各コア(PE)は演算ユニットや通信ユニットを備えているほか、独立したメモリ空間を持つ小さなスクラッチパッドメモリを持っています。

Simulated Annealingとは

SAとは、NP困難 である組合せ最適化問題に対して、ヒューリスティックに近似解を求めるアルゴリズムです。

SAは様々な組合せ最適化問題を解く可能性を秘めています。 前回に引き続き、今回もスピン変数を0,1で表現したQUBOモデルを対象として実装を行うことにしました。

QUBOモデルは次のような形で定義されます。

\[f(s)=-\sum_{i\le j}Q_{ij}s_{i}s_{j}\]

ここで、\(Q\)はパラメータ行列、\(s\)は0か1の値を持つバイナリ変数です。

この\(f(s)\)が最も小さくなる\(s\)の組み合わせを探索して見つけることが、SAの目的となります。

これまでの実装

ウエハースケールエンジンにSimulated Annealingを分散並列実装しCS-2実機で動作確認しました までの実装で、一つの大きな行列Qに対して並列分散グループ（この記事ではタイルと呼びます）を構築し、並列分散によるSAを行いました。

この並列化により、一つのPEに収まり切らない大きな\(Q\)について並列化を行うことが出来るようになりました。

前回の記事での並列化方法の問題点

前回の記事では、一つのPEに収まり切らない大きな\(Q\)を並列化しました。 しかし大きいといえど、最適化問題はたかだか数十PE分で収まる\(Q\)がほとんどで、WSE上にある数万のPEをすべて必要とするような大きな問題は稀です。

実機でこのような数十PE分で収まる\(Q\)の問題を解く場合、使っていない残りのPEに関しては余っている状態になり、WSEの膨大な計算資源を活かすことが出来ません。

そこで本記事では、WSEの計算資源を活かすために、比較的小さな\(Q\)をWSE上で複数同時に解く実装を紹介します。

今回の並列化方針と実装内容について

\(Q\)を複数タイルで解く並列化の概略

実は、最初の記事 の段階では、複数のPEが同じ\(Q\)について別の乱数シードを用いて解くことが出来ていました。

しかし、前の記事 において、一旦複数のPEが同じ\(Q\)に関して並列化して解く形に変更しました。

そこで、今回はこの2つの方法を組み合わせたような方針を取ります。

前の記事 の場合のように\(Q\)を分散させたタイルを、複数用意します。

各タイルでは異なる乱数シードにより独立して探索を行うことで、より効率の良い解の探索が出来る可能性を高めます。

ここから、3×3のサイズのタイルを2×2で並べた図で説明していきます。

タイルを複数用意してSAを行う

図に示すように、同じ\(Q\)を持つタイルを複数用意します。 この複数のタイルが同じ\(Q\)について問題を異なる乱数シードで解くようにします。

各タイル内で行われている処理については、前の記事 と同一ですので参考にしてください。

この実装に変える際に、以下の二つの新しい実装が必要になります。

1. スタート時に、すべてのタイルに同じ\(Q\)をブロードキャストする処理
2. 終了時に、すべてのタイルの中から最も低いエネルギーとその時の\(s\)の組み合わせの回収をする処理

順に説明していきます。

すべてのタイルに同じ\(Q\)をブロードキャストする処理

図に示すように、ホストからデータを各タイルに渡します。 この処理は、ブロードキャストにより行います。 WSE上のすべてのPEに同一の\(Q\)のデータを流していき、流れてきたデータがもし自分の担当する\(Q\)のデータ領域ならPE内のメモリに保存します。

各PEが担当する\(Q\)のデータが集まり次第、SAのイテレーションを開始します。

だんだん分散並列らしくなってきましたね。

すべてのタイルの中から最も低いエネルギーとその時の\(s\)の組み合わせの回収をする処理

SAが規定のイテレーションを終えた後、複数のタイルがそれぞれ異なるエネルギー状態を持っている異なります。

この中で、最も小さいエネルギーを持つ組み合わせ\(s\)が、SAにより求めた値であるとします。

最も小さいエネルギーを持つ組み合わせ\(s\)を複数タイルから回収する方針は二つ考えられます。

1. すべてのタイルからエネルギーと組み合わせ\(s\)をホスト側に送り、ホスト側で判断する
2. まずタイル同士で比較を行い、最も小さいエネルギーを持つタイルからホストに組み合わせを送る

どちらも善し悪しがあります。WSEとホスト間の通信にはコストがかかるので、タイルの数が多い場合は2．の方が良さそうです。

今回は、せっかくなのでWSEの中で行う 2.による実装になります。

図に、最大イテレーション回の計算が終了した時のPEの状態を示します。

各タイルの左上のPEは、そのタイルにおいて計算した最小エネルギーを持っている状態になっています。また、最上行のPEはその時の組み合わせを分散して持っています。

まず、すべてのタイルの左上PE同士のエネルギーを比較します。

各タイルの左上PEのエネルギーとそのPEの位置を示す構造データを、WSEの左上のPEに集めます。まずは左に比較しながら送り、そのあと上に比較しながら送ります。

これにより、WSEの左上PEに最小エネルギーとその出どころとなるタイルの位置の情報を集めることが出来ました。これをホスト側に送ります。

最後に、最小エネルギーの出どころとなるタイルの最上行から、組み合わせ状態\(s\)を転送します。

これにより、ホストは最終的な値を得ることが出来ます。

評価

挙動の確認

評価は解の良さなどではなく、コードの挙動に関してを見るために実機で行います。

今回実装したコードは前回同様GitHubにて公開するので、ご覧ください。

まず、PEを3×3に並べたタイルをさらに3×3に並べた場合の、各PEのタイムラインを示します。

実行時間のプロファイルには各PEでの経過時間を測定するために、測定担当のPEをタイル上部に追加することで行います。プロファイル方法についてはまた後の記事で紹介します。

大きい画像なので、右クリックして別タブで開いて拡大するのをおすすめします。

このタイムラインでは、3×3のタイルの左上に位置するPEがボトルネックとなっていることがわかります。

前回の記事でもふれたように、乱数を計算しフリップする位置を決める処理をタイル内の左上だけが行うためです。

この図より、ひとまず複数のタイルが用意できていることがわかります。また、それぞれが独立したSAが行われています。

タイル数と実行時間の変化

まず気になるのは、タイル数を変えると実行時間がどのように変化するのかです。

WSEでは750×994までPEが使えるため、3×3のPEを詰め込んでいくと最大で250×331のタイルを並べることが出来ます。

タイル数を変化させた場合の実行時間の変化を図に示します。

どうも、タイル数を変化させるとWSEの起動にかかる時間が変化するようです。 タイル数が多いほど複数のPEにデータを流す必要があるからだと考えられます。

起動時間を除いた場合の実行時間の変化は次のようになります。

各タイルが行う処理は並列で行われるので、時間はほぼ変化していません。

イテレーション数と実行時間の変化

次に、イテレーション数を変化させた場合の実行時間の変化見てみましょう。 タイルのサイズは3×3で、そのタイルを3×3で用意した場合にイテレーション数を変化させると実行時間がどのように変化するのかを示します。

イテレーション数を変化させた場合の実行時間の変化を図に示します。 縦軸が指数時間になっていることに注意する必要があります。

実機においてプログラムを実行する場合、ジョブ投入から起動までに80秒ほど時間がかかるため、イテレーション数が小さい場合はほとんどその時間がすべてです。

そのため、かなり大きいイテレーション数を行わないと起動時間以上の計算を行うことが出来ません。

起動時間を除いてどこの部分に時間がかかっているのかを図に示します。

起動時間を除くと、ウエハ内でデータを転送している時間が大きな割合を占めます。 イテレーション数が大きくなるにつれて、データ転送時間に比べて計算している時間が長くなります。

おわりに

今回の記事では、タイルを複数用意することで並列にSAを解く実装について述べました。

また、実機で動作確認を行い、複数のタイルで同じ問題を異なる乱数シードで解きました。

これにより、大きな\(Q\)の問題を解くだけでなく、小さな\(Q\)についてもWSEのポテンシャルを活かしてSAをすることが出来そうです。

今後の展望としては、プロファイラを作った部分についての紹介や、マルチテンパリングの実装などに取り組む予定です。 これらもコードの公開と共にブログ上で説明していく予定なので、ぜひ楽しみにしていてください！

謝辞

今回CS-2実機を東京エレクトロンデバイス様より貸与いただきました。

この場を借りてお礼申し上げます。

開発に関わったメンバー (アルファベット順)

このプロジェクトは計算機好きな有志が自己研鑽の一部として、業務時間外（たまに時間内）で好き勝手に開発しています。

• Hikaru Takayashiki
• Hiroki Nishimoto
• Keisuke Kimura
• Naoki Yoshifuji
• Toru Fukaya
• Yoshiki Imaizumi
• Yuki Ito

また、株式会社フィックスターズでは一緒に働く仲間を募集しています。 WSEのみならず様々なプロセッサでのプログラミング・高速化に興味がある方は、ぜひ採用ページよりご応募ください。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。