卒業研究 進捗発表 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. その他 – 最終的にはその処理を行うコードを読むしか
© Copyright 2024 ExpyDoc