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"の方もそのうち読みます。

Ubuntu 11.10にxmonadを入れた記録

Linux

Ubuntu 11.10に移行したのでまずxmonadを入れる。sudo apt-get install xmonadしたら次のように設定する。

[LennMars ~]$ cat /usr/share/xsessions/xmonad-gnome.desktop
[Desktop Entry]
Name=xmonad/GNOME
Comment=benri
TryExec=/usr/bin/gnome-session
Exec=gnome-session --session=xmonad
Type=XSession

[LennMars ~]$ cat /usr/share/gnome-session/sessions/xmonad.session
[GNOME Session]
Name=xmonad/GNOME
RequiredComponents=gnome-settings-daemon;
RequiredProviders=windowmanager;panel;
DefaultProvider-windowmanager=xmonad
DefaultProvider-panel=unity-2d-panel

[LennMars ~]$ cat /etc/lightdm/lightdm.conf
[SeatDefaults]
greeter-session=unity-greeter
user-session=xmonad-gnome

[LennMars ~] $ cat .xmonad/xmonad.hs
import qualified Data.Map as M
import XMonad
import XMonad.Core
import XMonad.Hooks.ManageDocks
import XMonad.Util.Run(spawnPipe)
import XMonad.Config.Gnome
import qualified XMonad.StackSet as W
import System.Exit
import Graphics.X11.Xlib

myManageHook = composeAll (
        [ manageHook gnomeConfig
        , className =? "Unity-2d-panel" --> doIgnore
        ])

main = xmonad gnomeConfig
        { manageHook = myManageHook
        , logHook = logHook gnomeConfig
        , modMask = mod4Mask
        , keys = keys'
        , borderWidth = 3
        }

keys' :: XConfig Layout -> M.Map (KeyMask, KeySym) (X ())
keys' conf@(XConfig {XMonad.modMask = modMask}) = (後略)

[LennMars ~] $ xmonad --recompile && xmonad --restart

Unityについてはpanelはともかくlauncherはどう考えても要らないので切った。欲しければxmonadのRequiredProvidersにlauncher;を、末尾にDefaultProvider-launcher=unity-2d-launcherを付け加えればよい。(後略)部分はキーバインドの設定であり、デフォルト値http://xmonad.org/xmonad-docs/xmonad/src/XMonad-Config.htmlをコピペして適当に改造した。mod-bがコメントアウトされているのはxmonadの現在のバージョンではエラーになるからである。modifyGap〜の代わりにsendMessage ToggleStrutsとすればよいらしい。ちなみにmod-pで呼ばれるdmenuを含むパッケージ名はUbuntu 11.10では"suckless-tools"である。

core-107.01のconfigureがmktempでエラーを出す問題への対処

OCaml memo

Jane StreetのOCamlの代替標準ライブラリであるCoreの現バージョンcore-107.01をconfigureするとき、
I: Running command 'lib/discover.sh lib/config.mlh lib/config.h -DLINUX_EXT'
のあとに
mktemp: too few X's in template `./discover_src.XXXXXXX.c'
と出てこけることがある。これはGNU coreutils 7.4に含まれるmktempで発生する現象で、lib/discover.sh中の当該部分のXを増やしても解決しない。mktemp単独をhttp://www.gratisoft.us/mktemp/index.htmlから拾ってきてインストールする。

Jane Street OSS群のインストール順

OCaml memo

Jane Streetは多くの有用なOSSを公開しているが地味に依存関係がめんどくさいのでインストール順の一例をメモしておく。
(OUnit)->(res)->Type-conv->Variantslib->Sexplib->Bin_prot->Fieldslib->Core->Async->Core_extended->Patdiff

OCamlでProject Eulerをいくらか解いた副産物

algorithm OCaml

https://gist.github.com/2185169
Project Eulerを50問くらい解いていたら数論系のアルゴリズムのOCaml実装が結構溜まってきたので公開する。LennMars/algorithms_in_OCaml · GitHubに依存しているがlet sob = string_of_big_intみたいなことを平気でしているのでそっちには統合しない。使わないし。いや……それを言ったらalgorithm_in_OCamlに入ってる殆どのアルゴリズムも……

木の分散並列処理のためのHadoop MapReduceプログラムを公開しました

Scala Hadoop

LennMars/TreeReduction · GitHub

一般にプログラムの分散並列化は非常に困難な作業であるのはよく知られたことです。比較的容易な分散並列化手段を提供するための手法の一つとして、あるパターンに属する計算のみを対象とし、ユーザには計算の具体的な内容を決定する関数を書いてもらい、並列化に関してはライブラリが面倒を見る、というアプローチが挙げられます。MapReduceはこのアプローチに基づいて一定の成功を収めているプログラミングモデルであり、この記事で紹介するプログラムは、MapReduceが(改行で区切られたテキストといった形の)リスト構造に関する並列化手法であるのに対し、木構造に関するそれの実装であると大雑把には言えます。

木はリストよりも複雑なデータ構造で、木に対する計算をたった一つのパターンにまとめるというのは非現実的です。複数の計算パターンを、最終的に行いたい計算からそれらへのマップが容易であり、かつ効率のよい並列化が可能なように選ばなければなりません。CiteSeerX — Parallel Implementation of Tree Skeletonsはそのような(木スケルトンと呼ばれる)計算パターンの定義と共有メモリ型並列計算機向けの実装を与えた初期の研究です。分散版の初期の研究で日本語で読みやすい文献としてはhttp://takeichi.dyndns.org/attachments/4E-1.pdf(PDF)などを。本プログラムは木スケルトンのうちreduceのみを実装しています。どのような実装をしているかはREADMEに載せた参考文献を眺めれば大体感じがつかめるでしょう。

型treeと関数reduce(の逐次版)はOCamlで書くと次のようなものです。

type 'a tree = Node of 'a * 'a tree list

let rec reduce f ( + ) ( * ) eta (Node(x,tn)) = (* ( * ) is associative operator and eta is its identity *)
    match tn with
          | [] -> f x
          | _ ->
            let children = List.map (reduce f ( + ) ( * ) eta) tn in
            x + (List.fold_left ( * ) eta children)

Nodeの第一の要素はノードの値、第二の要素は子のリストです。reduceはこの再帰的なデータ構造に対するある種の「自然な」再帰関数と言えます。

実際にreduceを使って何が出来るのか見てみましょう。ここでは各ノードに整数が与えられた木について「任意の葉を選んで根からその葉までのパスに現れる値を全て足しあわせて得られる値のうち最も大きいもの」を計算することを考えます(回りくどい表現になっているのはパスを計算するわけではないことを強調するためですが、パスも計算するようにユーザプログラムを書き換えるのは容易です)。この計算をMaxPathSumと呼びましょう。MaxPathSumの結果は全てのノードの値に依存するためその並列プログラムは自明ではありませんが、reduceに属していることに気付くと、

let maxPathSum = reduce identity ( + ) max min_int

と書くことができます。これを今回のHadoopプログラム用に書きなおしたのがhttps://github.com/LennMars/TreeReduction/blob/master/main/src/main/scala/reduce/MaxPathSumReduce.scalaです。ユーザは同様にAbstractReduceを継承したクラスを書くことにより容易に目的の並列プログラムを得ることができます。これは極めて簡単な例ですが、例えば木スケルトンでXPathが実現できることは既に示されているhttp://takeichi.dyndns.org/attachments/05075.pdf(PDF)、と言えば応用範囲の広さが分かるでしょう(そこまで実装するのにはまだ結構かかりますし性能が出るかも未知数ですが)。

ちなみに実装はすべてScalaを使っています。Javaでやっていたら途中で気力が尽きていたと思います。Scalaよく出来てますね。パフォーマンスについては、データが手元にないのですが人にやってもらった実験では1GB程度の小さな入力でも100台で50倍程度の速度向上が出たそうです。計算の内容によりますが現実に扱いたくなる規模の入力であればもっとよくスケールするでしょう。Hadoopよく出来てますね。

The case for open computer programs

Paper

Darrel C. Ince,Leslie Hatton & John Graham-Cumming. The case for open computer programs. Nature 482, 485–488 (23 February 2012). doi:10.1038/nature10836.

http://www.nature.com/nature/journal/v482/n7386/full/nature10836.html

プログラムを使用した研究におけるソースコードの公開についての記事。コンピュータを用いた実験結果の再現性の重要度はコンピュータ科学の発展と共に高まっており、実験のコードは原則公開すべきであり、またそれを支援する環境の整備を急ぐべきだと論じている。Inceらは再現性をdirectなものとindirectなものに分けて説明し、コードの公開は妥当性の追試や不正な研究の防止に役立つだけでなくこれらの再現性を推進するための最も重要な手段だとしている。
Inceらはまた、自然言語によるプログラムの説明はどんなに詳細なものでも不十分であることを例を交えて主張するとともに、コードや実験条件の詳述が公開されたとしても条件の微妙な違いにより完全な再現性の確保は不可能であるがだからといってコードを公開しない理由にはならない(やらないより遥かにまし)とも言っている。
その後はコード公開の原則化にあたっての考えられる障害(適切なツールやリポジトリの不足、理論と実装の乖離への不理解、プロプライエタリなプログラムを含む場合があることなど)と提案(研究支援機関がコードを研究成果の公表手段に統合するためのツールやリポジトリを提供するとかジャーナルがコード公開の度合いの基準を設けるとかレビューにコードを用いた追試を含めるとか)が続く。
ここまで書いておいてなんだけど特にハッとするようなことは言ってないな。要は業績と見做されないし忙しいからみんなやらないということなんだろうけど、コードが公開されていないことで無意味に研究が埋もれていき車輪の再生産をしている事例地味に沢山ありそうだし、なんとももったいないことだなあと常々思っている。というわけで、研究で書いたコードを下の記事で公開してみる。