Papers/2014/toma-master: paper/chapter1.tex comparison

comparison paper/chapter1.tex @ 39:a7981a22f12e

describe the eval monad

author	Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
date	Tue, 04 Feb 2014 02:26:58 +0900
parents	8d934599d0c5
children	ff15fb78a3ae

comparison

equal deleted inserted replaced

-:8d934599d0c5
+:a7981a22f12e
 $ ./par +RTS -N2
 \end{lstlisting}
 当然これだけでは並列に動かず、並列に実行できるようにプログラムを書く必要がある。
-Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。
+Control.Parallel.Strategies モジュールにある、
-普段は気にする必要はないが、並列実行ではどのように評価されるか意識する必要がある。
+Eval モナドを用いた並列化について説明する。
-並列に動くように処理を分割したとしても、値が必要になるまで評価されない。
+Eval モナドは並列処理を行うためのモナドである。
-この問題は、Control.DeepSeq モジュールにある deepseq 関数を使用し、式を即時評価することで解決できる。
+Eval モナドで並列処理を行う使用例を示す。
-Haskellの並列化手法はいくつかあるが、その中で最もシンプルなのは Eval モナドを利用することである。
-Control.Parallel.Strategies モジュールをインポートすることで使用できる。
+%% 完全に動くプログラム
+\begin{lstlisting}[caption=Evalモナドの使用例]
+import Control.Parallel.Strategies
+main = print (runEval test)
+num :: Integer
+num = 1000000
+test :: Eval (Integer, Integer)
+test = do
+a <- rpar (sum' 0 num)
+b <- rpar (sum' num (num*2))
+return (a,b)
+sum' :: Integer -> Integer -> Integer
+sum' begin end = if begin < end
+then begin + (sum' (begin + 1) end)
+else begin
+\end{lstlisting}
+まず、Eval モナドが定義された、Control.Parallel.Strategies をロードし、Eval モナドを利用できるようにしている。
+Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される。
+今回は、print (runEval test)が実行される。
 \begin{lstlisting}[label=eval, caption=Eval モナド]
 data Eval a
 instance Monad Eval
 runEval :: Eval a -> a
 rpar :: a -> Eval a
-rseq :: a -> Eval a
+\end{lstlisting}
-\end{lstlisting}
+並列処理を行うには、rpar を使う。
-rpar は、引数が並列処理可能であることを示す。
+rpar で挟んだ関数は並列に実行される。
-rseq は、引数を評価し、結果を待つように示す。
+Eval モナドの関数の型をみると、rpar は、a を モナドに包み、逆にrunEval はモナドから a を取り出している。
-どちらも式が完全に即時評価されるわけではないので、出力を挟んだり、deepseq 関数をうまく活用する必要がある。
+rpar で並列化可能計算を示したあと、runEvalで実行する。
-runEval は、評価を実行し結果を返す操作である。
-実際の利用方法として２つのパターンを紹介する。
+test の = のすぐ後にあるdoはモナドのためのシンタックスシュガーであり、do 構文と呼ばれる。
+Haskell では、モナドを単一のモナドとするために、do構文を使う。
+$>>$= (bind)を使ってまとめることもできるが、do 構文を使うことでbindの入れ子構造を手続き言語のような書き方で書くことができる。
-\begin{lstlisting}[label=rpar/rpar, caption=rpar/rpar]
+do 構文を用いない場合、以下の様な式になる。
-runEval $ do
-a <- rpar (f x)
+\begin{lstlisting}[caption=do構文を使わない場合]
-b <- rpar (f y)
+test :: Eval (Integer, Integer)
-return (a,b)
+test = rpar (sum' 0 num) >>= (\a ->
-\end{lstlisting}
+rpar (sum' num (num*2)) >>= (\b ->
+return (a,b)))
-rpar/rpar パターンは即座に return される（図\ref{fig:rpar}）。
+\end{lstlisting}
-単純に並列に動かしたい時に利用する。
+sum' は2つの引数をとって、開始点から終了点までの値をすべて足し合わせる関数である。
-\begin{figure}[!htbp]
+並列処理に負荷を与えるために使う。
-\begin{center}
+ifで、開始点が終了点を超えてないか調べ、超えてなければ再帰的に呼び出して足し合わせを行う。
-\includegraphics[scale=0.6]{./images/rpar_rpar.pdf}
-\end{center}
+test で返ってくる型は、Eval (Integer, Integer)で、その後 runEval 関数を適用することで、(Integer, Integer)となる。
-\caption{rpar/rpar パターン}
+そして最後にprint で出力される。
-\label{fig:rpar}
-\end{figure}
+Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。
+今回の場合、最後のprintがなければそもそも計算が行われない。
-\begin{lstlisting}[label=rpar/rseq/rseq, caption=rpar/rseq/rseq]
-runEval $ do
+並列に動くように処理を分割した後は、Haskell の遅延評価に気をつける必要がある。
-a <- rpar (f x)
+値が必要となるprintなどを行えば、並列に実行可能な部分が並列に実行される。
-b <- rseq (f y)
-rseq a
+rpar を使用する際に気をつけるのは、別の計算の値に依存する計算がある場合、その2つの計算は並列実行できないということである。
+例えば、以下のような場合は並列実行ができない。
+\begin{lstlisting}[caption=前の計算に依存した計算]
+test2 :: Eval (Integer, Integer)
+test2 = do
+a <- rpar (sum' 0 num)
+b <- rpar (sum' num (if a < num then a else (num*2)))
 return (a,b)
 \end{lstlisting}
-rpar/rseq/rseq パターンは、f x および f y の結果を待ってから return する（図\ref{fig:rseq}）。
-他の処理が結果を必要としている時に利用する。
-\begin{figure}[!htbp]
-\begin{center}
-\includegraphics[scale=0.6]{./images/rpar_rseq.pdf}
-\end{center}
-\caption{rpar/rseq/rseq パターン}
-\label{fig:rseq}
-\end{figure}
-rparは非常にコストが低いため、リストに対してmapするといった適用の仕方でも充分な並列性が出る。
-そのための関数 parMap も、 Control.Parallel.Strategies モジュールには用意されている。

Mercurial > hg > Papers > 2014 > toma-master

comparison paper/chapter1.tex @ 39:a7981a22f12e