この記事はKMC Advent Calendar 2018 - Adventarの2日目の記事です。

概要

理研に設置されているスーパーコンピューター、菖蒲(Shoubu)・菖蒲SystemBでPEZY Computing社のPEZY-SC/SC2を使わせてもらいました。

性能とか使いやすさについて感想とか知見を述べます。

PEZY-SC/SC2について

PEZY Computing社の開発したプロセッサで、メニーコアのMIMD(Multiple Instruction, Multiple Data)プロセッサであることが特徴です。

MIMDなので各コアで全く異なる命令を独立に実行できる点でGPUなどのSIMDプロセッサと異なります。

使えるようになるまで

理研に設置されているスーパーコンピューター、菖蒲(Shoubu)は一般の人でも申請して認められれば無料で使うことができます。（CUDAまたはOpenCLでの開発経験があったほうが良さそうですが）

http://accc.riken.jp/shoubu_info/application/

私は一昨年12月頃（ちょうどPEZY Computing社の社長（当時）が逮捕された頃です）に、並列オセロ終盤ソルバーの開発の名目で申請しました。

申請して通ったら書類にサインしたのをスキャンして送ったりsshの公開鍵を送ったりといった手続きをすればアカウントが作成されて使えるようになります。

また、申請して使えるようになるのはPEZY-SCを搭載した菖蒲ですが、PEZY-SC2でしか使えない機能（アトミックなど）を使いたい場合はPEZY-SC2を搭載した菖蒲SystemBを使わせてもらえるようです。

使ってみる

基本的な使い方はGPUと同じで、ホストとなるCPU側のコードとデバイス（アクセラレータ）側のコードの両方を書きます。

デバイス側のプログラムはclangに食わせるので普通のC++14が書けます（標準ライブラリは使えませんが）。この点は古いOpenCLで書かざるを得ない環境と比べるとだいぶ楽だと思います。

メモリ空間はホストとデバイスで別なので明示的に転送しないといけません（CUDAのUnified Memoryのようなことはいまのところできない）。

今回はサンプルとしてMIMDの恩恵が受けられるN-Queen問題を実装してみます。

問題

N*Nの盤面上にチェスのクイーンを互いに効きがないように置く方法は何通りあるか？チェスのクイーンは上下左右と斜めに動ける（飛車と角行を合わせたような動き）。

詳しくはエイト・クイーン - Wikipedia などを見てください。

この問題は各行についてどこに置けるかを試すバックトラックで解けることが知られています。また、駒の利きをビット列で管理することで、ビット演算を用いて高速に解けることも知られています。並列化は数行を全探索し、その結果を各スレッドに分配して計算させることでできます。

実装

#include "pzc_builtin.h"
#include "../solver.hpp"

uint64_t solve(int N, int depth, uint32_t left, uint32_t mid, uint32_t right) {
  if (depth == N) return 1;
  uint64_t sum = 0;
  for (uint32_t pos = (((uint32_t)1 << N) - 1) & ~(left | mid | right);
      pos; pos &= pos-1) {
    uint32_t bit = pos & -pos;
    sum += solve(N, depth+1, (left | bit) << 1, mid | bit, (right | bit) >> 1);
  }
  return sum;
}

void pzc_Solve(const Problem * const probs, uint64_t * const result, size_t count) {
  size_t offset = get_tid() + get_pid() * get_maxtid();
  result[offset] = 0;
  for (size_t index = offset; index < count; index += get_maxpid() * get_maxtid()) {
    const Problem &prob = probs[index];
    result[offset] += solve(prob.N, prob.depth, prob.left, prob.mid, prob.right);
  }
  flush();
}

GPUなどのSIMD アーキテクチャと違って、PEZYプロセッサでは分岐のペナルティーがとても小さいという特徴があるので、このように再帰の中で分岐をするコードを書いても素直かつ高速に動きます。一方、GPUで高速に動かそうとすると再帰をスタックを用いたループで書くなどコードを変形する必要があり、プログラミングが困難になります。

ホスト側では数行分の全探索をするコードとデバイス側のプログラムを呼び出すコードを書きます。デバイス側のプログラムを呼び出すのはOpenCLとほぼ同じです。

コード

CPU/GPU版はこちら。

github.com

GPU版は再帰をスタックを用いたループで書き直す最適化をしてあります(solve_nonrec関数)。詳しい最適化の内容については

プログラムを高速化する話Ⅱ 〜GPGPU編〜 from 京大マイコンクラブ

www.slideshare.net

を見てください（102ページ目から）。

PEZY-SC/SC2版はこちら。

github.com

結果

(2020/10/02 追記) N=18、CPUで予め展開する行数は最適なものを選択

マシン	時間(秒)
Core i7-6700K	78.857027
GeForce GTX 1080 OC	8.400348
Tesla V100 PCIe	3.936454
PEZY-SC	4.67289
PEZY-SC2	2.891

分岐ペナルティーの小ささなどからPEZY-SC2が最も高速という結果になりました。

さらなる最適化

GPU/PEZY-SC/SC2版ともに、タスク（計算する盤面）によって計算量が異なることにより、後半は遊んでしまうコアが出てきます。 GPUやPEZY-SC2ではアトミック命令が使えるので、アトミック命令を使うなどして動的にタスクを割り振ることでさらに高速化することができます。アトミック命令の使い方などはNDAを結ばないと教えてもらえませんが、ソースコードは公開OKなので、私の公開しているオセロソルバーのソースコード

github.com

などから類推することでおおよそはわかるのではないでしょうか。実際、PEZY-SC2上でアトミック命令を用いて最適化したところ、2.40199秒まで高速化されました。

GitHub - primenumber/PEZY-nqueen at sc2

オセロソルバーの実装

オセロソルバーとはあるオセロの局面が与えられたときにそこから両者が最善を尽くしたときの試合結果（何石差か）を求めるプログラムのことです。基本的にはαβ法という再帰的なアルゴリズムを用いて解きます。

すでにCPU/GPU版を実装していたので、簡単にPEZY-SC/SC2版も実装できると思っていました。

CPU版: github.com

GPU版: github.com

しかし、N-Queen問題と同じようにオセロソルバーも実装しようとしたのですが、空きマスが多くなると（=再帰の深さが深くなると）エラーが出て正しく動きませんでした。原因を探ってみると、どうやらスタックオーバーフローしているようです。実は、PEZY-SCにはローカルメモリが16KBあり、これを1コア内の8スレッドで分割してスタック領域として使います（ちなみに、スタック領域を縮小して余ったローカルメモリをコア内の共有メモリとして使うこともできます）。そのため、スタック領域は各スレッドにつき2KBしかありません。PEZY-SC2でローカルメモリが20KBになりましたが、それでもスレッドあたりは2.5KBです。 N-Queenより複雑なオセロソルバーではスタック領域が不足してしまっていたのです。（再帰で書いているのも一因ですが、スタック消費量を気にせずコードを吐くLLVM側も悪い気はします）

そこで、泣く泣くスタック領域を大量に消費する再帰で書くことを諦めて、自分で実装したスタックをグローバルメモリ上に置いてループで解くことにしました。これで解けるようにはなりましたが、プログラミングが非常に難解になってしまいました。このあたりのプログラミングの難しさが解消されるともっと良いと思うのですが…（スタック領域は基本グローバルメモリに置かれて、キャッシュで高速化するなど、難しそうではありますが）

何とかプログラミングの困難さを乗り越えて実装した結果が

github.com

です。根の1段だけFastest-First Heuristic（速さ優先探索）を行っています（複数段に適用しようとするとスタックが足りなかった）。また、PEZY-SC2向けに最適化を行ったものが

GitHub - primenumber/PEZY-Othello at sc2

にあります。最適化の内容は

速さ優先探索を複数段に適用
ビット演算命令を使用
アトミック命令を使用して動的なタスク割り振り
置換表の利用
葉の近くで速さ優先探索を適用していないところで隅を先に読む静的move ordering
NegaScout法の適用

になります（まだパラメータ調整をちゃんとしていなくて速度が出ない場面もありますが…）。これらの改良により、20石空きの局面を219万局読ませて、1ノード（8モジュール）で6時間弱で解けるようになりました（Tesla V100でも測るべきですが、クラウドで8GPUとかぶん回すと結構高いのでやってません、あとGPU版はいくつかの改良を取り入れてないです）。菖蒲SystemBでは最大1週間のジョブを投げられるので、22～23石空きまでは1ノードで読ませることができそうです（1石空きマスが増えるごとにだいたい3倍ぐらいかかる時間が増える）（ちなみにノード数を増やしてもゲーム木の大きい局面が律速になるのでそんなに高速化しない）。

今後は統計評価関数を利用したmove orderingを実装して更なる高速化を果たして、24石空き程度まで読ませたいと考えています。

感想

PEZY-SC/SC2はメニーコアのMIMDプロセッサという他にはあまりないアクセラレータです。今回は再帰の中で分岐するようなMIMDに有利なワークロードではPEZY-SC2がTesla V100を超えるパフォーマンスを出せることを示せました。次世代のPEZY-SC3も近いうちに登場するみたいなので楽しみですね。

一方で、スタック領域の制約にはかなり苦しめられました。せっかく再帰的なタスクに有利なので、たくさんスタック領域が使えるとプログラミングがしやすくてよいと思うので、この辺が改善されてほしいです。

最後に

KMCアドベントカレンダー 3日目の記事は id:nojima718 (KMC-ID: nojima) さんの「ぷよぷよのプレイ動画を解析して棋譜を生成する」です。お楽しみに！

adventar.org

prime's diary

そすうの日々を垂れ流しちゃうやつだよ

PEZY-SC/SC2を使った話【KMCアドベントカレンダー 2日目】

概要

PEZY-SC/SC2について

使えるようになるまで

使ってみる

問題

実装

コード

結果

さらなる最適化

オセロソルバーの実装

感想

最後に