GHC.Prim.par

卒業研究
進捗発表
Lightweight Implementation of
Profile-Driven
Implicit Parallelization
for Haskell
H22-12-22
理学部情報科学科4年
新井淳也
概要:
Haskellで自動並列化
• 2段階かけて効率的な自動並列化を行う
1. プロファイリングによって並列化による性能向上が
見込める箇所を分析する
2. 実際にそこを並列化する
• 自動並列化コンパイラをGHCベースで実装中
• GHCに既存の機能を活用し簡易な実装を行う
背景:
「で、どこを
並列化すればいいの？」
• 「どうやって並列化するか」はよく研究されてきている
• しかし並列化には「並列化すべき箇所の発見」と「そこ
を並列化したプログラムの実装」の2段階がある
– 後者は楽になりつつあるが前者は手作業任せの研究が多かった
• 自力で探してね型
– Cilk, StackThreads, Concurrent ML, Eden, Concurrent Haskell,
Glasgow Parallel Haskell, …
• 自動で手当たり次第並列化型(特殊なアーキテクチャを対象とする)
– Id/pH, Guarded Horn Clauses, …
プロファイリングで
「どこ」を発見できるはず
• 並列計算にはオーバーヘッドがある
– 闇雲な並列化はプロセッサ間通信を増加させ逆に低速化を招く
• ある程度時間のかかる処理の塊を並列化するならオー
バーヘッドがあっても高速化に貢献し得る
• それをプロファイリングによって発見する
– データの依存関係やI/Oのため並列化できない箇所もあるが、そ
れは静的なコード解析で対処できるはず
• なのでこの自動並列化はプロファイリングと再コンパイ
ルの2段階を要する
この発想に基づくツールを
GHCを基に簡潔に実装
する手法を提案
• Haskellは純粋関数型言語であり並列化が容易
• Glasgow Haskell Compilerは既にプロファイリングと
並列化のための機能を備えている
• それらを活用し再発明のない簡潔な実装を与える
– 過去の研究は既存のツールや実行時ライブラリに大幅な変更を
加えるものが多かった
– 我々が独自手法の実装に専念できるということが主な利点
AbstractとIntroduction
Method
Haskellは遅延評価
• Haskellは遅延評価を行う言語
– 値は必要になるまで計算されない
– 「サンク(thunk)」に包み値が要求されるまで評価を遅らせる
• 引数を取らないクロージャのようなもの
• サンクの評価が一度行われると結果の値を記録し、次回
以降はそれを返す
– 基本的に評価は1回だけ
GHCでの
プロファイリング
はSCCプラグマの挿入で行う
• {-# SCC “name” #-} <expr>
をソースに挿入してビルドすることで<expr>の評価回
数や処理時間などを計測する実行ファイルが生成される
– 実行時オプションを与えることで結果をファイルに出力させる
ことができる
– SCC = Set Cost Centre
• 例 let a = {-# SCC “fib-30” #-} fib 30
b = {-# SCC “fib-31” #-} fib 31
in ...
GHCでの
並列化
はpar関数の挿入で行う
• par :: a -> b -> b
はGlasgow Parallel Haskell (Trinder, et al. 1998)で実
装された関数現在はGHCに取り込まれている
• 第1引数をSparkさせ第2引数はそのまま返す
– Spark: (ここでは)サンクの評価を並行に行わせること
– Sparkしたサンクはプールに入れられ手の空いたプロセッサに
より評価される
今回実装する機能の中核:
時間のかかる処理を
自動的にSparkさせる
• 手作業で並列化するときと考えることは同じ
– SCCを挿入して、時間はかかるが結果をすぐには使わない処理
をプロファイルの分析で探し出し、par関数を挿入してSpark
– これが自動化されればめでたく自動並列化！
• 「時間がかかる」とはSparkのオーバーヘッドを相殺で
きそうな程度の時間をいう
– 具体的な数値は実地でベンチマーク結果から決定
時間計測とSparkは
サンクごとに
• 普通にHaskellのソースをコンパイルすればサンクを生
成するようなコードを生成する
• このサンクごとに処理を行うのが最も自然で簡易
– Sparkはサンクを対象として行うもの
– SCCによる時間計測も内部的にはサンク単位
– 積極的にサンクの生成箇所を制御する手もあるが、基本的にサ
ンクの生成はコストが大きいので少ないほうが良い
• ではサンクになる箇所を知るにはどうするか？
Method
Implementation
GHCのコンパイルパイプライン
Parse
Rename
Typecheck
• Haskellの抽象構
文木へ
• シンボルに一意な
名前を与える
• 型検査
Desugar
Simplify
CoreTidy
• Core(中間言語)へ
• 最適化
• インターフェイス
(.hi)生成
CorePrep
Convert to
STG
Code
generation
• STGへ変換
• C or バイナリへ
• STG(中間言語)へ
の変換準備
GHCの中間言語
Core
System Fの一種・Haskellのサブセット
Rec {
fib_rdj :: GHC.Types.Int -> GHC.Types.Int
GblId
[Arity 1]
fib_rdj =
\ (ds_siE :: GHC.Types.Int) ->
case ds_siE of wild_siJ { GHC.Types.I# ds1_siH ->
case ds1_siH of _ {
__DEFAULT ->
let {
sat_siU :: GHC.Types.Int
LclId
• コンパイルオプションにより処
[]
理過程のコードをダンプ可能
sat_siU =
• Coreを読み込んでコンパイルす
ることは(今のところ)できない
SCCやparの表現は
Coreでもほぼ同じ
GHC.Num.+
@ GHC.Integer.Type.Integer
GHC.Num.$fNumInteger
(__scc {fibzm30 main:Main}
fib1_rlb (GHC.Integer.smallInteger 30))
(__scc {fibzm31 main:Main}
fib2_rld (GHC.Integer.smallInteger 31))
Main.main2 =
case GHC.Prim.par# @ GHC.Integer.Type.Integer Main.main_a
of _ {
__DEFAULT ->
• par#はparがインライン化されたもの
...
– par# :: a -> Int#
第1引数をSparkし1を返す
サンク生成箇所は
CorePrepで判明
• この時点のCoreでletにより束縛されているも
のが将来的にサンクになる
– 次の中間言語、STGにおいて引数0のクロージャがサンクとなる
(The GHC Commentaryより)
– “Convert to STG”パスのソースを読みCoreとSTGのクロージャ
生成の関係を調査し確認した
• 1つ例外があるが単純な条件なので判別可能
Coreでのコード変換で
SCCやparを挿入
let <binder> = __scc <body>
in <expr>
let <binder> = <body>
in <expr>
let <binder> = <body> in
case GHC.Conc.par# <binder>
of _ {
__DEFAULT -> <body>
• GHCに既存の機能のお陰でこんなにも簡単
– 現時点ではプロファイルの分析は実装できていないので、サンクを全
てSparkさせてしまう
• この変換処理を“CorePrep”の直後に挟んだ
GHCのコンパイルパイプライン
改造(1)
Parse
Rename
Typecheck
Desugar
•Haskellの抽象構
文木へ
•シンボルに一意な
名前を与える
•型検査
•Core(中間言語)へ
Simplify
CoreTidy
CorePrep
Parallelize
•最適化
•インターフェイス
(.hi)生成
•STG(中間言語)へ
の変換準備
•SCC/parの挿入
Convert to
STG
Code
generation
•STGへ変換
•C or バイナリへ
let sat_siR =
let sat_siS =
let sat_siT = GHC.Types.I# 2 in
GHC.Num.- @ GHC.Types.Int GHC.Num.$fNumInt
wild_siG sat_siT
in
fib_rdf sat_siS
in
...
変換
let sat_siR =
let sat_siS =
let sat_siT = GHC.Types.I# 2 in
case GHC.Prim.par# @ GHC.Types.Int sat_siT
of sat_sj8 {
__DEFAULT -> GHC.Num.- @ GHC.Types.Int GHC.Num.$fNumInt
wild_siG sat_siT
} in
case GHC.Prim.par# @ GHC.Types.Int sat_siS
of sat_sj9 {
__DEFAULT -> fib_rdf sat_siS
} in
case GHC.Prim.par# @ GHC.Types.Int sat_siR
of sat_sja {
__DEFAULT -> ...
最適化でサンクが減る
＝並列性減少のジレンマ
• 並列化は当然高速化のためにやるのであって、コンパイ
ラの最適化は有効にしたい
• しかしサンク生成は本来コスト源なので最適化でサンク
の数は削られる
• サンクが作られなければSparkする機会が減る
– 例えば(効率は良くないが) fib n = fib (n–1) + fib (n–2)
と書いた時、最適化無しなら fib (n-1) と fib (n-2) でサン
クが作られるが、最適化有りだと作られない
解決法1:
サンク数を減らす最適化
だけ無効にする
• 最適化処理の中身をよく調べれば分かる…？
• 正格性解析が内容的にそれらしい雰囲気
しかしコンパイル時に -O -fno-strictness を指定
してもサンク数は減った
• プロファイル解析の結果Sparkすることにしたサンク以
外はなくなってくれたほうが良いので、そもそもこの方
法は好ましくない。却下
解決法2:
変換を施した後
もう一度最適化をかける
• SCCやparがあるときGHCはそこをサンクにする
• なのでそれらが挿入された状態のCoreをSimplifyさせれ
ば並列性を維持しつつ適用可能な最適化が行われる？
• しかしCorePrepまで進まないとどこがサンクになるか
は分からない
Simplifyの前にCorePrep
までをゴッソリ挿入
してみたが…
• 最適化オプションを無効にした状態でSimplify
～CorePrepを走らせられればサンクが多いまま
のCoreを入手できる
• ならばSimplifyの前に全部入れてしまおう
– コンパイラの内部パラメタを弄ってこの間だけ最適
化を無効にする
GHCのコンパイルパイプライン
改造(2)
Parse
Rename
Typecheck
Desugar
Simplify’(最
適化Lv.0)
CoreTidy’
CorePrep’
Parallelize
Simplify
CoreTidy
CorePrep
Convert to
STG
Code
generation
問題点1:
最適化オプションの影響
を除けなかった
• コンパイルオプション –O 無しでも有りでもParallelize
パスへの入力は同じ…にできなかった
– 並列化には -O を指定しなかった時のCorePrepの出力が欲しい
– ここで得られた出力は既にサンクが減少したものだった
• 最適化の設定は予想より複雑で、Simplifier’直前で
ちょっと弄っても駄目
– コンパイルオプションを格納するレコードがあり、最適化レベ
ルは整数でそこに記録されている
– 内部では最適化レベルに応じて最適化フラグを入/切している
問題点1(続き):
…なので
何を調べるか
• 後にDesugarでも最適化オプションが影響すると判明
• パイプライン突入直前で強制的に最適化レベルを0に書
き換えておくとParallelへの入力は同じになった
– もしかするとParse前ではなくDesugar前などでも大丈夫かも？
• つまり最適化オプションが影響するより前の時点で介入
して書き換えてしまえばよい
– どこで書き換えるのがよいかについて調査中
問題点2:
コンパイル時にpanic
• -Oと-spark-thunksを同時に指定するとコンパ
イル時にpanic! -spark-thunks: parの挿入を指示する(自作)
• 直接の原因:
Simplifier内の関数名置換処理に漏れが発生
存在しない関数を参照するコードが発生
– Main.fibをMain.$wfibに途中で置換するが、
Main.fibの呼び出し箇所がMain.$wfibに変わらない
問題点2(続き):
考えられる原因
1. “問題点1”派生
– 最適化の有効無効を切り替える中で必要な情報が欠
落したのではないか
• Parse…Desugar : この範囲は –O
• Simplify’…Parallelize : この範囲は –O 無し
• Simplify…Code generation : この範囲は –O
2. その他
– 最終的にはその処理を行うコードを読むしか

Download Report