並列探索ライブラリの提案 美添 樹 (Kazuki Yoshizoe) 基盤 (S) 離散構造処理系プロジェクトセミナー 2017 年 2 21

5 3 3 3 6 7 5 4 6 5 5 6 6 5 5 5 並列探索ライブラリの提案 美添 樹 (Kazuki Yoshizoe) 基盤 (S) 離散構造処理系プロジェクトセミナー 2017 年 2 21

2 紹介 過去にはコンピュータ囲碁の研究に取り組む 今は主に並列探索アルゴリズムの研究に取り組む 過去の研究 探索いろいろ (AND-OR 探索 MCTS など ) 並列計算 ( キャッシュ同期プロトコルによる投機実 ) 情報セキュリティ ( 静脈認証の脆弱性評価 ) デジタル無線通信 (Adaptive Array Antenna 等 ) 1 1 付けで理研 AIP センター @ 本橋に 探索と並列計算ユニット のリーダーに着任 研究以外に計算機の選定なども担当

並列探索の概要 ルールで 成されるグラフ 組合せ最適化 SAT NCSP 数値制約充 問題 ゲームパズル 頻出パターンマイニング 探索の ( 我々の ) ターゲット 探索 探索グラフはかなり Unbalanced なので単純な並列化は困難 1, 同期オーバーヘッド正確に計算時間をそろえる ( 困難 ) は 同期アルゴリズムに変形する 各種オーバーヘッドを低く保つ並列化 法が必要 トレードオフ 3, 通信オーバーヘッド送信や受信にかかる時間 2, 探索オーバーヘッド閾値などの情報の伝達が遅れ 枝刈りが遅れるオーバーヘッド

並列化 法の種別と既存の成果 深さ優先探索 (DFS) stack を使う様に変形し work stealing を う ハッシュ表を使う探索例 IDA*, モンテカルロ 探索 Distributed Hash Table を いる Priority Queue を使う探索例 Dijkstra, A* 探索 Hash distributed queue を使う ( 今のところ SAT ソルバは対象外 ) SAT ソルバやや特殊 数値制約充 問題 900 コアで約 750 倍 [Ishii, Yoshizoe, Suzumura. 2014] 統計的パターンマイニング 1,200 コア 1,175 倍 [Yoshizoe, Terada, Tsuda. 2017?] work stealing に少し 夫を追加 ハッシュ関数を いて節点を分散 都合の良い ハッシュ関数と通信の集中を回避する 夫が必要 並列モンテカルロ 探索 4,800コアで約 3,200 倍 [Yoshizoe, Kishimoto, Kaneko, Yoshimoto, Ishikawa 2011] Portfolio 式が主流

5 並列探索ライブラリの 標 並列探索の難しさの回避 ハードウェアに適したアルゴリズムの作成 デバッグ きな 標 シングルコアの探索を実装できる なら並列版も実装できるように 分散メモリ環境で動作させる できるだけ 般的なツールを いる c++ と MPI ライブラリ まだ未完成 今後数年の研究 標 まず 番簡単な深さ優先探索 (DFS) について説明

並列 DFS 応 例 遺伝データから統計的に有意な変異の組合せを発 する (P-Value が さい組合せを全列挙 ) アルツハイマー / 本 概要 元は lattice な探索空間 reverse search で に変換 P-value の枝刈りを いて 閾値付き深さ優先探索に 低遅延閾値伝播 +work stealing ( 細かいテクニックはいくつかあり ) 1,200 コアを いて 最 1,175 倍 速化 ( 東 TSUBAME CPU のみ ) [ 美添, 寺, 津 ] arxiv:1510.07787 [cs.dc] Genome Wide Association Studies 10 4 10 3 10 2 10 1 変異 (SNP) が 各 が被験者 GTCTAAAACATGATT 0 GTCTGAATCATGATT 1 GTCTGAAACATGATT 0 GTCTGAATCATCATT 1 頻出パターンマイニングの並列化でもある cf. ビールおむつ問題 pos. neg. 数万 数 万の組合せナイーブにやると 2 数 万通り Time (s) time (s) speedup 48285 1200 1100 1000 900 800 700 600 500 400 300 200 100 0 200 400 600 800 10001200 0 Nu. Process 41.1 Speedup

NCSP 数値制約充 問題に適 不等式制約で記述される 実数領域を求める問題 p0 Initial domain B&P nb boxes... p1...... B&P B&P...... 6......... p0 p2 p1... p3 4 (精度保証付き) 数値計算 領域分割 ( 探索) 2 0 0 2 4 P1 6 600コアを いて 最 約500倍 速化 特徴 x2 P2 応 例: ロボットの可動範囲 x1 不平衡な探索 の分散 不規則かつ 頻度な負荷分散 短時間 (数秒以下) の求解でも 速化 閾値無し DFS

8 深さ優先探索 Depth First Search Back tracking DFS DFS() { Recur(r) Recur(node n) { foreach (child c of n) { // do something for c Recur(c) f の節点を全て辿る単純な動作 d g a e h k r b i l j c m n o 再帰呼び出しで 然と back tracking を実装可能 経路上の節点だけ覚えれば良いメモリ消費 O(d)

9 閾値付き Depth First Search DFS with threshold DFS() { Recur(r) Recur(node n) { foreach (child c of n) { // do something for c if (c is within threshold) Recur(c) UpdateThreshold() f d g a e h r b i k l j c m n o 閾値を動的に更新して枝刈り実 例が多い 探索の本体は 字の部分 節点の作り によって頻出パターンマイニングにも統計的パターンマイニングにも数値制約充 問題にもなる

並列 DFS の準備 再帰呼び出しをスタック + ループに変換 10 DFS() { Recur(r) Recur(node n) { foreach (child c of n) { // do something for c if (c is within threshold) Recur(c) UpdateThreshold() 利点 :O(d) メモリ 点 : 並列化が困難 r StackDFS() { push(r) Loop() Loop() { while(stack not empty) { pop n from stack foreach (child c of n) { // do something for c if (c is within threshold) push(c) UpdateThreshold() d a e b i j c n o 点 :O(d b) メモリ利点 : 並列化可能 f g h k l m 深さ d, 分岐数 b の とすると

DFS() { Recur(r) Recur(node n) { foreach (child c of n) { // do something for c if (c is within threshold) Recur(c) UpdateThreshold() 再帰呼び出しをスタック + ループに変換 11 StackDFS() { push(r) Loop() Loop() { while(stack not empty) { foreach in pop n from stack reverse order foreach (child c of n) { // do something for c if (c is within threshold) push(c) UpdateThreshold() d a e r b i r j r c n o c b a c b a c b e d c b e d c b e g f 逆順にスタックに積むとほぼ同じ探索順序 c b e g f c b e g c b e c b h c b h f g h k l m 注意 : キュー (FIFO) にするとメモリ消費が激増する

あとは Work Stealing をすれば並列化完了 12 request request give reject Work stealing スタックが空になったプロセスがジョブを持つプロセスを探し request する (receiver initiated) ユーザから以下を隠蔽 request 対象の選択 法実際にはネットワークの能 に応じた 法が必要通信の集中を避ける 正しい終了検知全てのスタックが空になった保証があって 初めて終了する Distributed Termination Detection (DTD) は意外と難しい

13 並列 DFS ライブラリ Back tracking DFS この変換はユーザにやってもらう Stack DFS DFS() { Recur(r) Recur(node n) { foreach (child c of n) { // do something for c if (c is within threshold) Recur(c) UpdateThreshold() StackDFS() { push(r) Loop() Loop() { while(stack not empty) { pop n from stack foreach (child c of n) { // do something for c if (c is within threshold) push(c) UpdateThreshold()

14 並列 DFS with stack ParallelDFS() { if (proc_id == 0) stack.push(r) Loop() Loop() { while(not AllStackIsEmpty()) { if (stack.count() > 0) { stack.process() Probe() send one steal REQUEST Probe() Probe() { while (message received) { switch (message:type) { case REQUEST: if (stack not enough) send REJECT else stack.split() and send GIVE case REJECT: Send one steal REQUEST case GIVE:received_stack stack.merge() if (proc_id == 0) Start DTD ( 後で説明 ) 以下の関数を持つ stack があれば良い process が探索の本体 process / split / merge / count

15 抽象クラスを継承して実装 class DFSStack { public: virtual void Process() = 0; virtual DFSStack * Split() = 0; virtual void Merge(int *, int) = 0; virtual int Count() = 0; 前の stack を作れば ( 閾値無しの ) 深さ優先探索が動く 参考 : 並列 語 X10 を いた類似の実装が存在 [Zhang,Tardieu, Grove, Herta, Kamada, Saraswat, Takeuchi 2014] class MyStack : public DFSStack { public: virtual void Process() { 探索の本体通常は節点を pop し 節点を push する virtual MyStack * Split() { stack を半分に分割し 配列に置いてポインタを返す virtual void Merge(MyStack *) { 送られてきた stack をマージ virtual int Count() { 要素の数を返す

16 まず 指すもの 以下の 順で並列化可能なライブラリ ユーザが Process / Split / Merge 等を持つ stack クラスを実装 実際に stack かどうかはどうでも良い split した結果が連続メモリ領域にある必要あり そうでないと send しにくい 逐次 stack DFS で stack のデバッグ stack の情報だけを元に探索する ( 逐次では無意味だが )split と merge も使う 逐次で動くならそのまま並列でも動くように ここが難しいかもしれない

17 さらに閾値伝播を追加 Spanning Tree 上で通信 終了検知と同時にやる ユーザの実装が必要な物 reduce 関数 / bcast 関数がある threshold クラス 実体は何でも良い 何らかの reduce 関数 探索は stack と threshold のみで動作する必要 ParallelDFS() { if (proc_id == 0) push(r) Loop() Loop() { while(not AllStackIsEmpty()) { if (stack.count() > 0) { stack.process() Probe() send one steal REQUEST Probe()

分散アルゴリズムでは意外な事が難しい 終了検知 Distributed Termination Detection 18 スタックが全て空なら終了で良いのでは? スタックが空でも通信の途中かもしれない send と recv の総数を数えて 致していれば良いのでは? 数えるタイミングによっては send と recv を1 個ずつ (N 個ずつ ) 逃すかも さらに数えている途中に recv したら数え直すようにする これで正しく検知可能 ring を 2 周する : Dijkstra Scholten アルゴリズム ( 有名 ) ring 1 周で良い改良 : 4 counter algorithm など Spanning tree 上で集計 : [Mattern 1990] 決定版 速 ( 何故か知られていない ) これと同時に閾値伝播を う

19 メッセージ種類追加で実現 ParallelDFS() { if (proc_id == 0) push(r) Loop() Loop() { while(not AllStackIsEmpty()) { if (stack.count() > 0) { stack.process() Probe() send one steal REQUEST Probe() ユーザ定義による任意のメッセージを追加しても良いが Probe() { while (message received) { switch (message:type) { case REQUEST: if (stack not enough) send REJECT else split and send GIVE case REJECT: Send one steal REQUEST case GIVE: merge to local queue case BROADCAST: UpdateThreshold() send BROADCAST to neighbor or send REDUCE to parent case REDUCE: if (at root) send BROADCAST else send REDUCE if needed if (proc_id == 0) Start DTD

20 ユーザから隠蔽したい物 MPI ライブラリの難しさ MPIメジャーなライブラリだがワナは 々 特に数値計算以外の使い をすると難しい 通信パターンの問題 通信パターンに気を遣わないと何が起きるか 終了検知 分散メモリ環境での正しい終了検知

MPI Library (Message Passing Interface) 番メジャーな並列プログラムツール MPI 規格にそった実装が多数存在 各プロセスは rank (0,,N-1) を持つ Process 0 main() { int buffer1[100], buffer2[100]; if (rank==0) { MPI_Send(buffer1, 100, MPI_INT,1,...); MPI_Recv(buffer2, 100, MPI_INT,1,...); else { // rank==1 MPI_Recv(buffer2, 100, MPI_INT,0,...); MPI_Send(buffer1, 100, MPI_INT,0,...); MPI はプロセス ( ランク ) 単位で動作 rank 0 MPI_Send MPI_Recv rank 1 Process 1 main() { int buffer1[100], buffer2[100]; if (rank==0) { MPI_Send(buffer1, 100, MPI_INT,1,...); MPI_Recv(buffer2, 100, MPI_INT,1,...); else { // rank==1 MPI_Recv(buffer2, 100, MPI_INT,0,...); MPI_Send(buffer1, 100, MPI_INT,0,...); 21 冗 なメモリコピーを許容すれば共有メモリ環境でも普通に動作する ( 単に通信をメモリコピーに置き換える )

22 MPI 初 者の良くやるミス このコードはデッドロック Process 0 main() { int buffer1[100], buffer2[100]; if (rank==0) { MPI_Send(buffer1, 100, MPI_INT,1,...); MPI_Recv(buffer2, 100, MPI_INT,1,...); else { // rank==1 MPI_Send(buffer1, 100, MPI_INT,0,...); MPI_Recv(buffer2, 100, MPI_INT,0,...); Process 1 main() { int buffer1[100], buffer2[100]; if (rank==0) { MPI_Send(buffer1, 100, MPI_INT,1,...); MPI_Recv(buffer2, 100, MPI_INT,1,...); else { // rank==1 MPI_Send(buffer1, 100, MPI_INT,0,...); MPI_Recv(buffer2, 100, MPI_INT,0,...); MPI_Send は MPI_Recv されるまで待つ MPI_Send, MPI_Recv はブロッキング通信なのでこの書き をするとそこでデッドロックする 実は Send / Recv は何種類かあって適切な物を選ぶ必要 Send, Isend, Bsend, IBsend

23 探索での定 とワナ Loop() { while(not AllStackIsEmpty()) { // do work stealing Probe() Probe() { while (MPI_Iprobe()) { MPI_Recv( ) switch (message_tag) { // ここでメッセージに応じた処理 探索ではメッセージのタイミング サイズ 送り先の全てが不定 こういう 儀の悪いアプリは MPI はあまり想定していない以下を使うのが 応の定 MPI_Iprobe: メッセージが届いていたら true を返す 次の MPI_Recv はブロックしない MPI_Bsend: バッファを いた Send 1 回バッファにコピーしてから送信 MPI の動作は何らかの MPI 関数が呼ばれないと進まない ( 実際は実装依存だが いくつか試したが実際 まる ) 良くあるミス無駄なポーリングを避けようとして途中で まる

24 刺さる プロ 語? 何かが何かに刺さって不具合が起きる良く原因が分からない場合に いる 例 したら刺さって 40 秒固まったぞ 類義語 秘孔を突く 普通のプログラム動かないのはほぼ 100% 分のせい 規模並列 分のせいと えない不具合は 常茶飯事 並列プログラムは気をつけないと良く刺さる うっかり何かを 刺さない うっかり 秘孔を突かない

25 良くある 刺さり 前のプロセスがうまく終了せず 後続のプロセスが影響を受けて死ぬ 分かりやすいケースプロセスの未終了 ゾンビ化 原因が良く分からないケースも多い ( プロにも良く分からないことも ) 全く動かない ( これは良い死に ) 死に いろいろ 最初から遅い ( これもまだ良い ) 通信がときどき数秒 10 秒程度 まる しばらくすると遅くなる ( こういうのが困る ) しかも数時間待ったら勝 に治る ( ことも )

簡単なツバメの刺し 26 1, ランダムな相 と通信 ( 数秒以上 ) 2, 特定の 1 ノードから残り全てへ通信 3, もう 1 回 特定の 1 ノードから残り全てへ通信

簡単なツバメの刺し 27 1, ランダムな相 と通信 ( 数秒以上 ) 2, 特定の 1 ノードから残り全てへ通信 3, もう 1 回 特定の 1 ノードから残り全てへ通信

簡単なツバメの刺し 28 1, ランダムな相 と通信 ( 数秒以上 ) 2, 特定の 1 ノードから残り全てへ通信 ここで まる数秒 10 秒 3, もう 1 回 特定の 1 ノードから残り全てへ通信 これには数ミリ秒 ざっぱな回避策としては 通信の集中を避けること send/recv ペアに枝を張って作るグラフが 最 次数が低く 直径が さく hot-spot がない betweenness centrality が い場所がない

通信が まる現象 現象としては MPI_Iprobe が数秒ブロックする ( 通常は 2 3 マイクロ秒で終了する ) さらに同時に malloc がブロックすることも HPC 分野の専 家もあまり知らないそもそも MPI_Iprobe を 分で呼ぶ が少ない普通は MPI_Recv などの内部で使われている 29 推測される原因と背景 Infiniband の RDMA (Remote Direct Memory Access) に伴う何らかの thrashing と推測される RDMA のために Infiniband カードは独 のメモリ変換テーブルを持つ 実体はホストメモリ上にあるまた malloc も独 の物に置き換える 詳細はドライバを読む? 専 家に協 を依頼中

分散ハッシュを利 する 法もライブラリ化したい 今後の課題 30 ハッシュ関数で分散 ハッシュ関数は問題依存 性能のためにはここに介 したい DFS ほど 由がない DFS では work stealing の対象は 由 Hash distributed A* などではそうは かない 理想的には 適切なハッシュ関数の 動 成 動的な変更 しかしこれはかなりチャレンジング アイデア 刺さない ために余分な通信を うなど 2-hop, 3-hop しても良いことにするなど

より 規模に ある程度は成功 DFS 1,175 倍 (1,200 コア ) MCTS 3,200 倍 (4,800 コア ) ただし まだ 規模 ネットワークが速い (full bisection) 普通の CPU (Xeon) 実際のトポロジを無視し 通信パターンのグラフだけ 夫すれば 分な規模 HPC の専 家の知 が求められる より 規模な探索問題を解く物性科学や 命科学の組合せ最適化例 熱伝導率最 化 / RNA 構造発 数値制約充 問題による精度保証求解 より 規模な環境を 指す 3D torus, TOFU ( 京 ) 等 Many-core アーキテクチャ ハードウェア ミドルウェアに負担をかけないアルゴリズム たとえば 実際のトポロジに即した通信パターンを 動的に 成 アルゴリズムに都合が良く実現可能なトポロジの提案 ( ランダムエッジを少数追加など ) 耐故障性のある探索

32 おまけ : 並列探索ハッカソン 並列統計的パターンマイニングを github で公開中 MP-LAMP https://github.com/tsudalab/mp-lamp これを元に並列 DFS をやるための解説会 & ハッカソン的なことをやりたいと思っています 以下の様な 歓迎 頻出パターンマイニング界の 探索の 私のメリット 意 収集 参加者の に提供できるメリット 並列探索の理解?