第11回：OpenACCを使ったICCG法の高速化

OpenACCの基本的な考え方や使い方については、前回まででおおよそ説明しきってしまいました。

​それでは習うより慣れろということで、今までの総仕上げとして、ICCG法プログラムのOpenACC実装についてご紹介します。

OpenACCを使ったICCG法の高速化

さて、OpenACCの学習は習うより慣れよ、が基本です。
​OpenACCの指示文の細かい使い方については、ソフテックさんのOpenACCサイト（2021年1月よりプロメテック・ソフトウェア/GDEPソリューションズ 共同運営のHPCWORLDへ移管）にかなり詳しく記載されていますから、そちらにお任せするとして、この記事では実際のアプリケーションへの実装を通じてOpenACCの使用感をつかんでいただくことを目標としてます。

今回OpenACC化するアプリケーションは、東大情報基盤センターの講習会、「OpenMPによるマルチコア・メニィコア並列プログラミング入門」より、有限体積法コードの中で用いられている、ICCGソルバーです。

​プログラムの詳細はリンクをご覧いただくとして、ICCG法のアルゴリズムを図１に示します。
ICCG法は共役勾配法（CG）法の一種で、前処理に不完全修正コレスキー分解（IC: Incomplete Cholesky Factorization）を使ったものです。

連立一次方程式A_x=b （Aは行列、x,b はベクトル）の解を求める際によく使われるアルゴリズムですが、どうやってOpenACC化を進めたらよいか考えてみましょう。

図１のアルゴリズムを見ると、2行目から始まるループがまず目につくと思います。
ICCGでは、A _x = b となる _x を求めるために、r₀=b - A _x0 の計算から初めて、r_i が限りなくゼロに近づくまで x_i を徐々に更新してくことで解ベクトル _x を求めますが、その更新ループが2行目から始まるループです。

図1：ICCGソルバーのアルゴリズム
​（OpenMPによるマルチコア・メニィコア並列プログラミング入門より）

OpenACC化をする上で、こういったループを見た際に考えたいのは2つ、

1. このループはOpenACCで並列化できるのかどうか
2. 並列化できないとしたら、CPU-GPU間のデータ転送をこのループの外側にどれだけ追い出せるか

です。​ループを見たときには常にこれを考えるというのがOpenACC化の方針です。

まず1ですが、このループは r_i の更新のために r_i-1 を使っているため、データ依存性のあるループであると言えます。

つまりはOpenACCで並列化できないことになります。

ということで 2のデータ移動について考えます。
何度も言及している通り、CPU-GPU間のデータ転送は非常に時間がかかるので、ループの中で繰り返しデータ転送するのは、深刻な性能低下を招きます。
​​
ループの外側にデータ転送を追い出すためには、ループ内でのCPUによる処理、特に配列アクセスを伴う処理を如何に減らせるかにかかっています。

​ループの中身を詳細に見ていきましょう。

図2：図1の3行目、solve [M]_z^(i-1)=_r^(i-1) 部分のプログラム

図2は、不完全修正コレスキー分解を行うコードです。

まず4行目から始まるループは、データ独立なループであると言えますから、簡単にOpenACC化できますね。

問題は、7行目から始まる三重ループと、16行目から始まる三重ループです。
これらはどうでしょうか。

まずは一番内側のループ(10, 19行目)から考えてみましょう。
これらは、OpenACCで並列化可能なリダクションループですから、並列化可能です。

それでは、i のループ(8, 17行目)はどうでしょうか。
少なくともこのループをGPUで実行できないと、13, 22行目の配列アクセスをCPU側で行わなければならなくなってしまいますが、並列化はできるのでしょうか。

…実はこのループ、
図2を見ただけでは並列化できるかどうかはわかりません！

その理由は、11, 20行目に現れる間接参照(W[Z][itemL[j]-1])です。
このitemL[j]-1の値が仮にi-1になるのであれば、W[Z][i-1]の値を使ってW[Z][i]の値を計算することになり、典型的なデータ依存のあるループになってしまいます。

そんなわけで、OpenACC化を行うためには、時にプログラムの内容の理解が求められます。

このプログラムの場合には、多色順序付け（マルチカラーリング）と呼ばれる並列化技法（図3）が使われていて、現在更新しようとしている色(W[Z][i])と参照しようとしている色（W[Z][itemL[j]-1]）は異なるように作られており、従って8, 17行目はデータ独立なループと見なすことができ、並列化可能です。

一方で、7, 16行目は色の切り替えループであり、並列化できません。
​カラーリングの仕組みから、例えば図3のピンクのデータを更新するためには、緑のデータが更新済みでなければならないわけですが、これは結局、X[i]を更新するためにはX[i-1]が更新済みでなくてはならないという、データ依存の関係と同じなのです。

図3：カラーリングによる並列化
​（OpenMPによるマルチコア・メニィコア並列プログラミング入門より）

これらを考慮した上で、OpenACCの指示文を挿入したのが、図4になります。

こんな感じで、一つ一つのループについて並列化できるのかできないのか考えながら、徐々にOpenACC化を進めていきます。
OpenACC化ができた範囲についてはdata指示文で囲むことができます。
​
​このようにして、OpenACC化を進めてはdata指示文の範囲を拡大していき、最終的にデータ転送をループの外側に追い出すわけです。

図4：図1の3行目、solve [M]_z^(i-1)=_r^(i-1) 部分のプログラムのOpenACC化

---

＜ １ヵ月間有効のスパコンお試しアカウント ＞
東京大学情報基盤センターでは、教育の一環として、制限はあるものの一ヵ月の間有効なスパコンアカウントを提供しています。
現在3つのスパコンが運用されていますが、そのうちReedbushと呼ばれるスパコンには、一世代前のものではありますがGPUが搭載されていて、OpenACCを使える環境も整っています。
自分でどんどん自習したい場合は、ご利用を考えてみてください。

トライアルアカウント申し込みページ
https://www.cc.u-tokyo.ac.jp/guide/trial/free_trial.php

＜ 過去の講習会の資料やプログラム公開中 ＞
東大センターが行った過去のOpenACCに関する講習会の資料やプログラムも公開されていますので、自習する場合にはぜひご利用ください。

講習会ページ　※オンライン講習会 定期開催中！
https://www.cc.u-tokyo.ac.jp/events/lectures/

講習会で用いているプログラム
https://www.dropbox.com/s/z4fmc4ibdggdi0y/openacc_samples.tar.gz?dl=0​