みなさん今日も楽しく線形方程式を解いてますか？
スパコンアドカレを見る皆さんなのでもう毎日1式は解いてるんだと思います。
かくいう私は最近違うことをやってるんですが…。
さて、ここではポエムを書いて良いということなので、HPCGについて思っていることを書き連ねます。
技術的に間違ってることを書くつもりはありませんが、論文ではなくあくまでポエムということで、多分に主観的表現が入っていることにご注意ください。
結論
- HPCGは別に実用ベンチマークではないよ
- 高速化のレギュレーションがふわっとしてるので、ソフトウェア勝負なところあるよ
HPCGとの出会い（せめてものポエム分）
時は2015年夏。某並列チップが第1世代で、Yさんがまだ同じ会社にいた頃です。
YさんがTwitterで「ゴードンベルとりてー」と叫び、それに反応したM先生によって、某チップでなにか高速化してSCに出そうという案件を弊社にいただくことになりました（※もちろん実際は競争入札なのでこの時点で確定していたわけではない）。
それで何を高速化するか？というネタを最初の打ち合わせ時に決める場に私も運良く同席させてもらって、その場で出たのがHPCGでした。
日頃から半陰解法型粒子法(MPS)を取り扱っている私は、共役勾配法のことはある馴染みがあったんですが、実はベンチマークがあるというのを初めて知ったのはこのタイミングでした。
今調べたら2015年夏というのは、HPCGが始まってからまだ3回目だったんですね（2014 Junが最初）。
そんなわけで、なにはともあれHPCGを某並列チップで高速化することになりました。
某チップは、当時は、2,3とかがきちんとロードマップが引かれており、数年後にはこれがこうなると世界n位だね！みたいなことを目指してたわけです。
実際の体制としては、Yさんは他の案件とかけもちでプロジェクトリーダー＆レビュアーだったんですが（とても助かりました）、私は運良く案件が終わったので半年ぐらいはずっとHPCGのコードを書く作業者をやることができました。
残念ながら（？）ゴードンベル賞を取るどころか論文落ちましたが（もっとできることはあった、と今にしては思う）、ワークショップには出せて、現地でM先生のゴードンベル肉をいただいたり、普通にバッファロー肉を食べたりして思い出深いSCになりました。
（アドカレ予告に「思い出話」って書いたので入れましたが面白くなかったので大幅に削ってポエムはここまで）
HPCGってなに
そんな感じで、HPCGをよく書きよく学んだ健全な経験を積んだわけですので、私視点からのHPCGに関する「良くある間違い」を書こうというのがこの記事です。
さて、そもそも、読者の皆さんのなかでHPCG自体をちゃんと書いたことある、もしくは中のアルゴリズムがどうなってるか把握してる方はどれぐらいいるのでしょうか？
もし知らない方がいたら、ぜひ覚えて帰ってほしいです。
HPCGとは、ディレクレ境界条件の1自由度熱拡散方程式を3次元正規格子上で中心差分法で離散化した時に得られる線形方程式を、緩和法に対称ガウス＝ザイデル法を用いた4段Vサイクル多重格子法前処理付き共役勾配法で解いた時の処理時間を計測するベンチマークです。
この1文に今日の結論（の根拠）がすべて詰まっています。
ぜひ暗唱できるようになってください。
実用ベンチマークなのか？
1文の前半はまず、どんな問題を想定してるのかという模擬対象の模型の話をしています。各単語を知らない方はぐぐってもらえれば分かると思うんですが、重要なことは、これが「とてもとても単純な形である」というところです。
これを線形方程式の係数行列$A$に落とすと、i行目には
- 対角項($A_{ii}$)=26
- 隣接頂点の非対角項($A_{ij}$)=-1
といういわゆる27点ステンシル形になるので、行列をspyplotとかするときれいに斜めに線が入ったような形になります。
ですが、CAE等の実用で出てくる問題で、ここまできれいな形になることはまずありません。もっとぐちゃぐちゃになります。
なので、これだけからHPCGは実用的な問題を解いているわけではないということがまず分かりますね。
HPCGが実用と呼ばれる裏の意味として、Top500(HPL)が非実用的だという批判の意図が含まれています。
しかし、この程度のモデルで「実用的だ」と言うのであれば、HPLだってちゃんと模型があって解いているわけなので、両方とも実用的だと言うべきです（それならそれで理解できます）。
HPCGも実用的ではないと言うならじゃあ何が良いのか？については、SC18で開催された"Pros and Cons of HPCx benchmarks"（通称スパコンまるで分からんBoF）に詳しいので安藤さんの解説記事などをご覧ください。
ちょっと詳しい方なら、実用性は模型ではなくて計算パターンにあると言う人もいるでしょう。
確かに、このような簡単なパターンであることを利用した高速化（演算省略など）はレギュレーションで禁止されています。
なので、確かに行列が簡単だからといってただちに非実用的であるとは言えません。
しかし、この辺りのレギュレーションはちょっと曖昧で「一般的に精度が良くない微妙な手法だけどHPCGに適用してみたら偶然この行列の形だと問題なかったよ」みたいなノリは認められているんです。
実際に某有名スパコンはそんなことをやっている（いた）そうで、これを現地で中の人に聞いた時、真面目にそれを回避して余計な処理をいれていた私は「はー？そんなんありなん？」ってグレました。
ソフトウェア屋である私としては腕の見せ所ではあって楽しいとは言えば楽しいんですが、HPCGはハードウェア性能を測っているだけではなく、実装されたアルゴリズムにもかなり依存することを知っておいてください（まぁHPLだって柱分解の周りが重要といえばそれはそうなんですけれども）。
であるからして、スパコンの性能指標として本当にこれで良い（実用アプリケーションの性能に相関する性能測定になっている）のかと言うと私はかなり懐疑的です。
詳しくは次に書きますが、この辺り「HPCGはなぜソフトウェア勝負なのか」は、↑の1文の前半の模型ではなく、後半部分の求解法が関わってきます。
HPCGとSpMVとSymGS（本題）
HPCGの概要は知ってる人ならHPCGはメモリ帯域が良ければ良い性能になるという話を聞いたことがある方も多いと思います。
その理由としてHPCGは結局SpMV（疎行列ベクトル積）が一番重い処理だからというところまで聞いている人もいるかもしれません。
このSpMVとは具体的には以下のような計算を指しています（$\mathbf{y}=A\mathbf{x}$を想定）。
for(i = 0; i < n; ++i)
{
y[i] = 0;
for(idx = 0; idx < nonzero[i]; ++idx)
{
a_ij = A[i][idx];
j = column[i][idx];
y[i] += a_ij*x[j];
}
}
ご覧の通り、
- よく見る密行列行列積と違って2重ループであり、行列の値Aは使いまわしできず
- 密行列ベクトル積と違って、ベクトルxもランダムアクセスになって使いまわしできない
という特徴から、SpMVが支配的なHPCGは「メモリ帯域（シーケンシャルもランダムも）が必要」と見られているわけですね。
でも私は、それは8割ぐらい嘘だと思っています。
8割という理由は、実際に実行してみるとSpMVじゃなくてだいたい8割ぐらいがSymGSが占めるからなんですよね。
このSymGSというのは、手法のところにある緩和法である対称ガウス＝ザイデル法のことを指します。
ガウス＝ザイデル法は一般的な工学系なら大学学部の数値計算の授業とかで習うと思うんですが、線形方程式$A\mathbf{x}=\mathbf{b}$を解く一般的な手法で、擬似コードは以下のような計算になります。
for(i = 0; i < n; ++i)
{
x[i] = b[i];
for(idx = 0; idx < nonzero[i]; ++idx)
{
j = column[i][idx];
if(i != j)
{
a_ij = A[i][idx];
x[i] -= a_ij*x[j];
}
}
x[i] /= a[i][i]
}
あ、これをぱっと見た人が言いたいことは分かります。
「似たようなループでアクセスパターンだから、つまりやっぱりSpMV系が重要なんやろ？」ってことですよね。
それは残念ながら大外れです。ここで注目すべきはSymGSはx_iの計算にx_jを使うところ、つまりiループに依存性があることです。
ここまで真面目に読まれた賢明な読者の皆様なら分かると思いますが、ガウス＝ザイデル法は並列化が困難な解法なんです。
SpMVはiループが独立しているので、並列数nで実行できます。しかし、ガウス＝ザイデル法は素直に並列化できません。
多数の演算器を積んで並列処理をするコアが当然のこの時代に、並列化困難なアルゴリズムを使ったベンチマーク、それがHPCGの正体です。
特に近年ではGPUを始めとする超並列コア（アクセラレーター）をいかにうまく使うがが重要なわけですから、その方向とは真っ向から対立しています。
じゃあ並列化できないからどうしようもないのか？というと流石にそんなことはありません。
x_iの計算にx_jの値を使うと言いましたが、jが飛び飛びの値であることを考えれば、あるx_iの値に必要なx_jの集合は決まってきます。
同様に、それぞれのx_jの計算に必要な値は…と考えると、iを0...nではなくて、うまく並び替えて依存しない部分は並列化できそうですよね？
そういうことが可能なように、HPCGのレギュレーションでは行列の並び替えは許可されているのです。
しかし、問題はこのレギュレーションが非常に曖昧であるという点です。
曖昧さの根本原因は、この行列の並び替えに「厳密に元の計算順を守る手法」という以外に「収束性が落ちて反復回数が増えるけど緩い手法」という選択肢があることです。
詳しくは述べませんが、具体的に言えば、前者はCuthillMcKee法が代表例で、後者は赤黒などの多色順序付け法（マルチカラー法）が挙げられます。
どちらを選ぶのかという点でもそうですが、後者の場合「何色で塗り分けるのか」や「そもそもどうやって依存性がないものを見つけるのか」という工夫で、処理時間は反復回数を劇的に改善する余地があります。
工夫というと良いことに聞こえますが、言い方悪く言えば、HPCGの行列だとたまたま速くて精度も劣化しないアルゴリズムを選ぶという裏技が使えるのです（そして実際に使われてるそうです）。
先述の通り、これは本来のHPCGの趣旨からすると嬉しくありません。なぜなら
- HPCGの行列形式に特化した最適化であり、他の実用的な問題に適用できて良い結果になるとは必ずしも言えない
- ハードウェアの性能ではなく、ソフトウェアのアルゴリズムや実装方法に依存してしまう
ということだからです。ここに「HPCGは実用ではない」「ソフトウェア勝負である」という主張の根拠があります。
また、そのようなソフトウェア的裏技で性能を上下させられるなら、「HPCGはハードウェアのメモリ帯域を測っているのだ」という主張も成り立たなくなりますね。
そもそも並び替えることで（ベクトルxを）キャッシュヒットさせて再利用率を上げられるわけですから。
じゃあどうしたらいいのか
じゃあHPCGがどうしたらいいか？と聞かれたら、もしそれが書けるならそれで論文書いてますよって返していいでしょうか。
上記の問題があるからHPCGがまるっきり有用性がないかというと、もちろんそんなこともありません。
ある観点から見れば有用性があります。
そもそもTop500を見て分かる通り、スパコンのベンチマークには「同じ設定でずっとスパコンを評価し続ける」ことにこそ価値があるとも言われます。
その辺りまで含めると、スパコンまるで分からんBoFでも先生らが議論されていた通り、どういうベンチマークのどんな価値があるのかは、非常に難しい問題なわけです。
ただ1つ、HPCGにもし提案できるならガウス＝ザイデル法をやめてと言いたいです。
ガウス＝ザイデル法は、先述の通り非常に並列化困難であって、現代（およびしばらくの将来）のスパコンを評価するのに向いている手法とは言えません。
ですので例えば
- ガウス＝ザイデル法の代わりに、ヤコビ法など並列性が自明な（並び替えで収束性が変わらない）手法にする
- もしくは、そもそも緩和法の指定をやめて自由選択にする
のどちらかが良いんじゃないでしょうか。
後者の場合は余計にソフトウェア勝負になってきますが、あるハードウェアに向いている緩和法を選ぶことは、ある緩和法が良い性能になるハードウェアを作って、結果的に線形方程式を解く多くの問題に恩恵を与えられるということの裏返しでもあるので、悪いことばかりでもないと思います。
その場合、問題をもうちょっと複雑に（せめて非構造格子に）するとかはあっても良いと思いますが。
この辺り、ちゃんと突き詰めたいなぁ…（とは思いつつ、生きていくためにはお金が必要なので、なにもないと進まないわけでして）
まとめ
というわけで、
- HPCGは実用ベンチマークだ
- HPCGではハードウェアのメモリ帯域を測れるんだ
というよくある誤解を正したいという記事でした。
また若干思い出話に戻ると、結局某チップは色々あって使いにくくなって案件は普通に終わって、以降はHPCGを触る機会もなくなって、今では半年に1回のHPCG順位を遠くから眺める存在になってしまいました。
しかしこういう案件は面白かったので、ぜひまたやりたいところです。
ここまでガッツリな話はあまり需要がないのはそうかもですが、「Xという計算機でYを動かして高速化したい」という課題はぼちぼち世の中にあるようです。
そういうのは、いつやっても面白いので、もしそんな悩みでお困りの方がいらっしゃったら、ぜひご連絡ください。
と、業務時間中（半分休憩中）にもこの記事を触ったので、最後に一応宣伝を入れておいて終わりにします。