Liszt: A domain specific language for building portable mesh-based PDE solvers

paper

Zachary DeVito, Niels Joubert, Francisco Palacios, Stephen Oakley, Monserrat Medina, Mike Barrientos, Erich Elsen, Frank Ham, Alex Aiken, Karthik Duraisamy, Eric Darve, Juan Alonso, and Pat Hanrahan. Liszt: A domain specific language for building portable mesh-based PDE solvers. In 2011 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’11, Washington, DC, USA, 2011. IEEE Computer Society.

LisztはScala上のmesh-based偏微分方程式ソルバ用DSLであり、Lisztコンパイラは単一のLisztコードからMPI, CUDA, pthreadsのコードを吐ける。この論文では、

  • 言語デザイン
  • 並列性を抽出するためのプログラム解析
  • 目標プラットフォームごとのバックエンド
  • 様々なPDEに対する計算時間
    • オイラー方程式(空間:1次精度格子+時間:前進オイラーで離散化した有限体積法)
    • ナヴィエ-ストークス方程式(オイラー方程式の場合に加えて勾配も考慮)
    • 浅水波方程式(2次精度風上差分で離散化した有限体積法)
    • 3次元ラプラス方程式(6面体要素による有限要素法、連立一次方程式は共役勾配法で求解)

について述べている。

並列性を正しく見つけるために、Lisztはメモリアクセスのパターンを(静的に)把握していなければならない。このためLisztは以下の制限を課す。

  • 実行中メッシュトポロジーは不変
  • メッシュ要素には組み込みの関数を通してしかアクセスできない。例えばインデックスによるアクセスはできない
  • メッシュ要素・fieldの値はimmutable
  • fieldの値には対応するメッシュ要素を通してしかアクセスできない

Fieldはphaseと呼ばれる状態をもつ。phaseにはread-only, write-only, reduce-using-operator [op](fluxの計算のために用意された可換で結合的なreduction)の三種類がある。各Fieldはいつでもどれか一つのphaseにあり、あるfor-comprehensionの中では不変でなければならない。 この制限は依存関係を大きく制限でき、同期はphaseが変化するところでのみ取ればいいことになる。

具体的に並列性を見つける手段はメッシュ分割(分散メモリ環境用)とメッシュ彩色(共有メモリ環境用)が用意されている。…とだけ書けば大体の雰囲気は伝わると思う。バックエンドの話は省略。実験結果は、1000コアでもスケールしているらしいことは確認できる。ただ比較対象の"native C++ code"というのがどんなものなのかよく分からないので絶対的な速度についてはなんとも(そんなに遅いということはなさそう)。

感想。丁度PDEソルバの高レベルな並列化とScalaを用いたEDSLの両方に興味があったので面白く読んだ。が、手元の実物(http://liszt.stanford.edu/)、Liszt本体のビルドまでは出来たもののLisztプログラム例の実行まで行けてないので実際どうなのかはなんとも言いがたい。っていうか本体、Scala2.8.1だとコンパイルできて2.8.2だと失敗するのすごいな……

"Language Virtualization for Heterogenous Parallel Computing"の方もそのうち読みます。