Mercurial > hg > Papers > 2014 > toma-master
changeset 47:e32c9a53310c
fix
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 06 Feb 2014 21:12:49 +0900 |
| parents | 6fbc1771d2be |
| children | 88b11a3afb93 |
| files | paper/abstract.tex paper/appendix1.tex paper/chapter1.tex paper/chapter2.tex paper/chapter3.tex paper/chapter4.tex paper/conclusion.tex paper/images/concurrent_edit.graffle paper/introduciton.tex paper/master_paper.pdf paper/thanx.tex slides/images/concurrent_edit.png slides/images/jungle_type.graffle slides/images/jungle_type.png |
| diffstat | 14 files changed, 4623 insertions(+), 576 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/abstract.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/abstract.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,19 +1,17 @@ \begin{abstract} -Haskellは純粋関数型プログラミング言語である。 -モダンな型システムを持ち、型推論と型安全により信頼性の高いプログラムを書くことが可能である\cite{types}。 -Haskellは純粋であるため、関数は引数が同じならば必ず同じ値を返すことが保証されている。 +Haskellは純粋関数型プログラミング言語である. +モダンな型システムを持ち, 型推論と型安全により信頼性の高いプログラムを書くことが可能である\cite{types}. + +本研究では, Haskell を用いて並列に読み書き可能なデータベースの実装を行う. +並列にデータへアクセスする手法として, 元となる木構造を変更することなく編集できる非破壊的木構造を用いる. +非破壊的木構造は, 破壊的代入が存在しない Haskell と相性がよい. -本研究では、Haskell を用いて並列に読み書き可能なデータベースの実装を行う。 -並列にデータへアクセスする手法として、元となる木構造を変更することなく編集できる非破壊的木構造を用いる。 -非破壊的木構造は、破壊的代入が存在しない Haskell と相性がよい。 +実装した並列データベースの読み込みと書き込みについて性能を計測し, +読み込みに関して 12 コアで実行した場合, 1 コアで実行した場合と比較して, 10.77 倍 という性能向上率が確認でき, +マルチコアプロセッサの性能を引き出すことができた. -実装した並列データベースの読み込みと書き込みについて性能を計測し、 -読み込みに関して 12 コアで実行した場合、 1 コアで実行した場合と比較して、10.77 倍 という性能向上率が確認でき、 -マルチコアプロセッサの性能を引き出すことができた。 - -また、実用的な用途で利用できるか示すために、Web 掲示板サービスを開発した。 -既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない、読み込みで 1.87 倍、書き込みで 2.3 倍の性能が確認できた。 +また, 実用的な用途で利用できるか示すために, Web 掲示板サービスを開発した. +既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 1.87 倍, 書き込みで 2.3 倍の性能が確認できた. \end{abstract} -
--- a/paper/appendix1.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/appendix1.tex Thu Feb 06 21:12:49 2014 +0900 @@ -3,48 +3,48 @@ \appendix \def\thesection{付録\Alph{section}} \section{計測環境の構築} -ウェブアプリケーションのベンチマークを行う際、サーバの設定に注意を払う必要がある。 -適切に設定を行わないと、サーバがボトルネックとなってしまい正しい結果が得られない。 -ウェブアプリケーションのベンチマークを行う際の注意点について述べる。 +ウェブアプリケーションのベンチマークを行う際, サーバの設定に注意を払う必要がある. +適切に設定を行わないと, サーバがボトルネックとなってしまい正しい結果が得られない. +ウェブアプリケーションのベンチマークを行う際の注意点について述べる. -データを受信したり送信したりするのは OS カーネルである。 -多くの TCP パケットを要求し、各パケットのサイズが1500バイトといった大きなファイルを提供する場合、 -ウェブアプリケーションというよりOSカーネルのテストになってしまう。 +データを受信したり送信したりするのは OS カーネルである. +多くの TCP パケットを要求し, 各パケットのサイズが1500バイトといった大きなファイルを提供する場合, +ウェブアプリケーションというよりOSカーネルのテストになってしまう. -接続には、HTTP Keep-Alivesを利用する。 -新しい TCP 接続を確立するのはとても遅く、OS カーネルによって行われる。 -毎秒多くの新しい接続を作成するようなベンチマークを行うと、OSカーネルのテストとなってしまう。 +接続には, HTTP Keep-Alivesを利用する. +新しい TCP 接続を確立するのはとても遅く, OS カーネルによって行われる. +毎秒多くの新しい接続を作成するようなベンチマークを行うと, OSカーネルのテストとなってしまう. -アプリケーションやOSカーネルが完全にハードウェアを使用できるようにするためにいくつか調整を行う必要がある。 -最初の問題は、ファイル記述子の欠如である。 -デフォルトはプロセスあたり、1,024 files で非常に貧弱な結果しか得られない。 -ファイル記述子の現在のリミットは以下のコマンドで取得できる。 +アプリケーションやOSカーネルが完全にハードウェアを使用できるようにするためにいくつか調整を行う必要がある. +最初の問題は, ファイル記述子の欠如である. +デフォルトはプロセスあたり, 1,024 files で非常に貧弱な結果しか得られない. +ファイル記述子の現在のリミットは以下のコマンドで取得できる. \begin{lstlisting}[caption=ファイル記述子のリミットの取得] $ ulimit -aH \end{lstlisting} -リミットを変更するには、以下のコマンドを実行する。 +リミットを変更するには, 以下のコマンドを実行する. \begin{lstlisting}[caption=ファイル記述子のリミットの設定] $ sudo sh -c ulimit -HSn 200000 \end{lstlisting} -再起動後も有効にするためには、システムファイルの編集を行う。 +再起動後も有効にするためには, システムファイルの編集を行う. -/etc/security/limits.conf へ以下の記述を追加する。 +/etc/security/limits.conf へ以下の記述を追加する. \begin{lstlisting}[caption=リミットの設定の追加] * soft nofile 200000 * hard nofile 200000 \end{lstlisting} -次に問題となるのは listenキューの制限である。 -listen キューとは、保留中のコネクションが繋がれるキューのことである。 -このキューの長さの制限が小さいと、同時にたくさんのコネクション要求がきた場合、制限を超えた要求を拒否する。 -listen キューや、その他の設定も含めてベンチマーク用にサーバの設定を変更する。 +次に問題となるのは listenキューの制限である. +listen キューとは, 保留中のコネクションが繋がれるキューのことである. +このキューの長さの制限が小さいと, 同時にたくさんのコネクション要求がきた場合, 制限を超えた要求を拒否する. +listen キューや, その他の設定も含めてベンチマーク用にサーバの設定を変更する. -/etc/sysctl.conf に以下の記述を追加する。 +/etc/sysctl.conf に以下の記述を追加する. \begin{lstlisting}[caption=システム設定の変更] fs.file-max = 5000000 @@ -72,31 +72,31 @@ net.ipv4.tcp_tw_recycle = 1 \end{lstlisting} -ファイルを保存後、設定を反映させるには以下のコマンドを実行する。 +ファイルを保存後, 設定を反映させるには以下のコマンドを実行する. \begin{lstlisting}[caption=設定の反映] $ sudo sysctl -p /etc/sysctl.conf \end{lstlisting} -ベンチマークを行う際、小さなテストでは妥当性が低くなってしまうので注意する。 -TCP/IPのスタックは保守的な方法で動作し、ダウンロード速度に合わせて徐々に速度を増大させるためである。 +ベンチマークを行う際, 小さなテストでは妥当性が低くなってしまうので注意する. +TCP/IPのスタックは保守的な方法で動作し, ダウンロード速度に合わせて徐々に速度を増大させるためである. -また、テストするサーバより遅いベンチマーククライアントを用いると正しい結果は得られない。 -シングルスレッドで稼働したり、Ruby や Python といった低速なベンチマークツールでテストを行うと、 -すべてのテストする対象が同じようなパフォーマンスを持っているように見えてしまう。 +また, テストするサーバより遅いベンチマーククライアントを用いると正しい結果は得られない. +シングルスレッドで稼働したり, Ruby や Python といった低速なベンチマークツールでテストを行うと, +すべてのテストする対象が同じようなパフォーマンスを持っているように見えてしまう. \subsubsection{weighttp} -ウェブアプリケーションの性能測定には、weighttpを用いる。 -weighttpはWebサーバの性能測定ツールで、マルチコアCPUを使ってテストできる\cite{weighttp}。 -また、livev を使うことで、モダンなポール・システムコールを利用し、測定性能を向上できるといった特徴を持つ。 -同様の性能測定ツールには、Apache Benchやhttprefが存在するが非力であり、ボトルネックとなってしまうため使用しない。 +ウェブアプリケーションの性能測定には, weighttpを用いる. +weighttpはWebサーバの性能測定ツールで, マルチコアCPUを使ってテストできる\cite{weighttp}. +また, livev を使うことで, モダンなポール・システムコールを利用し, 測定性能を向上できるといった特徴を持つ. +同様の性能測定ツールには, Apache Benchやhttprefが存在するが非力であり, ボトルネックとなってしまうため使用しない. -weighttp を起動するには、以下の様にコマンドを入力する。 +weighttp を起動するには, 以下の様にコマンドを入力する. \begin{lstlisting}[caption=weighttpの起動] $ weighttp -n 1000000 -c 1000 -t 10 -k "http://bldsv12.cr.ie.u-ryukyu.ac.jp:3000" \end{lstlisting} -起動時には対象のサーバの URL を記述する他に、いくつかのオプションを指定できる。 +起動時には対象のサーバの URL を記述する他に, いくつかのオプションを指定できる. \begin{itemize} \item n ... HTTP リクエストの総数 \item c ... 同時に接続するコネクションの数 @@ -107,49 +107,49 @@ \clearpage \section{Warp を用いたウェブアプリケーションの構築} -Warp は、軽量・高速な HTTP サーバである\cite{warp}。 -Haskell の軽量スレッドを活かして書かれている。 -Haskell のウェブフレームワークである Yesod のバックエンドとして用いられており、現在も開発が続けられている。 +Warp は, 軽量・高速な HTTP サーバである\cite{warp}. +Haskell の軽量スレッドを活かして書かれている. +Haskell のウェブフレームワークである Yesod のバックエンドとして用いられており, 現在も開発が続けられている. -Warp を用いてウェブアプリケーションを構築する方法について説明する。 +Warp を用いてウェブアプリケーションを構築する方法について説明する. % Source Codeは実行可能な状態でsrcに置いてある -% firstline, lastlineで、どの範囲を表示するか指定できる +% firstline, lastlineで, どの範囲を表示するか指定できる \lstinputlisting[label=warp_sample, caption=Warpを用いたウェブアプリケーションの例, firstline=9]{src/warp.hs} -ソースコード \ref{warp_sample}は、URLによって出力する結果を変更するウェブアプリケーションである。 -/hello/worldへアクセスがあった場合は、インクリメントされる counter が表示される。 +ソースコード \ref{warp_sample}は, URLによって出力する結果を変更するウェブアプリケーションである. +/hello/worldへアクセスがあった場合は, インクリメントされる counter が表示される. \paragraph*{main} -HTTP サーバを起動するには、Warp の run 関数を利用する。 -run 関数は、利用する Port 番号と、application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る。 +HTTP サーバを起動するには, Warp の run 関数を利用する. +run 関数は, 利用する Port 番号と, application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る. -関数型言語では、関数を第一級オブジェクトとして扱える。 -また、今回は Haskell のカリー化された関数の特性を利用し、main 内で作成した IORef 型の counter を部分適用させている。 +関数型言語では, 関数を第一級オブジェクトとして扱える. +また, 今回は Haskell のカリー化された関数の特性を利用し, main 内で作成した IORef 型の counter を部分適用させている. -IORef を用いることで、Haskell で更新可能な変数を扱うことができる。 -参照透過性を失うようにみえるが、Haskell は IO モナドを利用することで純粋性を保っている。 -IORef 自体が入出力を行うわけではなく、単なる入出力操作の指示にすぎない。 -IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理を行う。 +IORef を用いることで, Haskell で更新可能な変数を扱うことができる. +参照透過性を失うようにみえるが, Haskell は IO モナドを利用することで純粋性を保っている. +IORef 自体が入出力を行うわけではなく, 単なる入出力操作の指示にすぎない. +IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理を行う. \paragraph*{application 及び routes , findRoute} -application の実装では、routes という関数を独自に定義して、URL によって出力を変更している。 -application に渡されるリクエストはデータ型で様々な情報が含まれている。 -その中のひとつに pathInfo という、URL から hostname/port と、クエリを取り除いたリストがある。 -この情報を routes という関数に渡すことで、routeSetting というリストから一致する URL がないか調べる。 -routeSetting は、URL のリストとレスポンスを返す関数のタプルのリストである。 +application の実装では, routes という関数を独自に定義して, URL によって出力を変更している. +application に渡されるリクエストはデータ型で様々な情報が含まれている. +その中のひとつに pathInfo という, URL から hostname/port と, クエリを取り除いたリストがある. +この情報を routes という関数に渡すことで, routeSetting というリストから一致する URL がないか調べる. +routeSetting は, URL のリストとレスポンスを返す関数のタプルのリストである. \paragraph*{notFound 及び hello} -レスポンスを返す関数は、いくつか定義されている。 -その中で利用されている responseLBS は文字列からレスポンスを構築するためのコンストラクタである。 +レスポンスを返す関数は, いくつか定義されている. +その中で利用されている responseLBS は文字列からレスポンスを構築するためのコンストラクタである. \paragraph*{world 及び incCount} -world は、インクリメントされる counter を表示するための関数である。 -IORef 内のデータは直接触ることができないため、incCount 内で atomicModifyIORef を利用してデータの更新を行なっている。 -atomicModifyIORef は、データの更新をスレッドセーフに行うことができる。 -また、responseLBSで構築したレスポンスは、Resource Tというリーソスの解放を安全に行うために使われるモナドに包まれている。 -lift 関数を用いて、incCountの型を持ち上げ調整している。 +world は, インクリメントされる counter を表示するための関数である. +IORef 内のデータは直接触ることができないため, incCount 内で atomicModifyIORef を利用してデータの更新を行なっている. +atomicModifyIORef は, データの更新をスレッドセーフに行うことができる. +また, responseLBSで構築したレスポンスは, Resource Tというリーソスの解放を安全に行うために使われるモナドに包まれている. +lift 関数を用いて, incCountの型を持ち上げ調整している. -プログラムを例にして説明したが、Warp は容易にプログラムに組み込むことができる。 -本研究では、非破壊的木構造データベース Jungle と Warp を組み合わせて、掲示板ウェブアプリケーションを開発した。 +プログラムを例にして説明したが, Warp は容易にプログラムに組み込むことができる. +本研究では, 非破壊的木構造データベース Jungle と Warp を組み合わせて, 掲示板ウェブアプリケーションを開発した.
--- a/paper/chapter1.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/chapter1.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,13 +1,13 @@ \chapter{Haskellとは} \label{ch:haskell} -Haskell とは純粋関数型プログラミング言語である。 + Haskell とは純粋関数型プログラミング言語である. \section{純粋関数型プログラミング} -関数とは、一つの引数を取り一つの結果を返す変換器のことである。 -関数型プログラミング言語では、関数を引数に適用させていくことで計算を行う。 +関数とは, 一つの引数を取り一つの結果を返す変換器のことである. +関数型プログラミング言語では, 関数を引数に適用させていくことで計算を行う. -既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。 -例えば、Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する。 -Haskell は、関数を引数を適用するという考えに基づいて、抽象的なプログラミングを可能とする。 +既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する. +例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する. +Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする. \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] fib :: Int -> Int @@ -16,142 +16,167 @@ fib n = fib (n-2) + fib (n-1) \end{lstlisting} -fib :: Int -$>$ Int は、関数の型宣言である。この-$>$は左結合である。 -この関数は、Int を受け取って Int を返す関数ということを示す。 -フィボナッチ数列の関数が三行に渡って書かれているが、これは Haskell のパターンマッチを活用している。 -引数が、0 ならば 2 行目の fib が呼び出される。 -引数が、1 ならば 3 行目の fib が呼び出される。 -上から順に引数と一致する行がないか調べていき、引数が 0 でも 1 でもなければ引数は n に束縛される。 +fib :: Int -$>$ Int は, 関数の型宣言である. +この関数は, Int を受け取って Int を返す関数ということを示す. +フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. +引数が 0 ならば 2 行目の fib が呼び出される. +引数が 1 ならば 3 行目の fib が呼び出される. +上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛される. -フィボナッチ数列の関数は、自分自身を使って再帰的に定義している。 -再帰は、関数型プログラミング言語において必要不可欠な要素である。 -手続き型言語では、配列とループを主に用いてプログラミングを行うが、Haskell ではリスト構造と再帰を用いる。 +フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. +再帰は, 関数型プログラミング言語において必要不可欠な要素である. +手続き型言語では, 配列とループを主に用いてプログラミングを行うが, Haskell ではリスト構造と再帰を用いる. -純粋関数型プログラミングでは、変数の代入は一度のみで後から書き換えることはできない。 -フィボナッチ数列の関数でも、一度引数を束縛した n を書き換えることはできない。 +純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない. +フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない. +関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. +この性質は関数の理解を容易にし, プログラムの証明を可能にする. +正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである. + +関数型プログラミング言語は, 関数を変数の値にすることができる. +つまりこれは, 関数を第一級オブジェクトとして扱うことができるということである. +Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. -関数にできることは、何かを計算してその結果を返すことだけであり、引数が同じならば関数は必ず同じ値を返すことが保証されている。 -この性質は関数の理解を容易にし、プログラムの証明を可能にする。 -正しいと分かる単純な関数を組み合わせて、より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである。 +高階関数の例として Haskell のカリー化が挙げられる. +Haskell では, 全ての関数は一度に一つの引数だけを取る. +2 つのInt を受け取り, 大きい方を返す max の型はソースコード\ref{src:max}のように定義できる. + +\begin{lstlisting}[label=src:max, caption=max関数] +max :: Int -> Int -> Int +\end{lstlisting} + +この関数定義に現れる-$>$は左結合である. +複数の引数を取るようにみえる関数は, 実際には１つの引数を取り, その次の引数を受け取る関数を返す（ソースコード\ref{src:max_curry}）. -関数型プログラミング言語は、関数を変数の値にすることができる。 -つまりこれは、関数を第一級オブジェクトとして扱うことができるということである。 -Haskell は、引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる。 +\begin{lstlisting}[label=src:max_curry, caption=max関数のカリー化] +max :: Int -> (Int -> Int) +\end{lstlisting} -高階関数の例として Haskell のカリー化が挙げられる。 -Haskell では、全ての関数は一度に一つの引数だけを取る。 -複数の引数を取るようにみえる関数は、実際には１つの引数を取り、その次の引数を受け取る関数を返す。 -このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という。 -カリー化によって、関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる。 +このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という. +カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる（ソースコード\ref{src:partial}）. + +\begin{lstlisting}[label=src:partial, caption=関数の部分適用] +x = max 3 +x 4 -- max 3 4 の結果として 4 が返される +\end{lstlisting} \section{型} -Haskell では、すべての式、すべての関数に型がある。 -値の型は、その値が同じ型の別の値と何らかの性質を共有していることを示す。 -例えば、数値は加算できる、文字列は表示できるといった性質である。 +Haskell では, すべての式, すべての関数に型がある. +値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す. +例えば, 数値は加算できる, 文字列は表示できるといった性質である. -型はプログラムに抽象をもたらす。 -抽象を導入することで、低水準の詳細を気にせずプログラミングが可能になる。 -例えば、値の型が文字列ならば、どのように実装されているかという細かいことは気にせず、 -その文字列が他の文字列と同じように振る舞うとみなすことができる。 +型はプログラムに抽象をもたらす. +型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. +例えば, 値の型が文字列ならば, どのように実装されているかという細かいことは気にせず, +その文字列が他の文字列と同じように振る舞うとみなすことができる. -Haskell は静的型検査によりエラーを検出することができる。 -Haskell では、評価の際に型に起因するエラーが起きないことを保証している。 -引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない。 -Haskell は、すべての式、すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる。 +Haskell は静的型検査によりエラーを検出することができる. +Haskell では, 評価の際に型に起因するエラーが起きないことを保証している. +引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. +Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる. -エラーの検出の例として、Haskell で最もよく使われるデータ構造リストで確認を行う。 -また、リストの定義とあわせてデータ型の定義についても説明する。 +エラーの検出の例として, Haskell で最もよく使われるデータ構造, リストで確認を行う. +また, リストの定義とあわせてデータ型の定義についても説明する. -リストとは、角括弧で包まれた同じ型の要素の並びである。[1,2,3] などと表現する。 -リストは以下のように定義されている。 +リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する. +リストはソースコード\ref{src:list}のように定義されている. \begin{lstlisting}[label=src:list, caption=Haskellのリスト定義] data [] a = [] | a : [a] \end{lstlisting} -data というのは新しい型を定義する際に利用するキーワードである。 -[] というのが型名である。 +data というのは新しい型を定義する際に利用するキーワードである. +[] というのが型名である. -型名の右に a というのがあるが、これは多相型を表すのに使う型変数である。 -リストは、Intのリスト、Floatのリストといった様々な型のリストを作ることができ、型変数を用いてそれを実現する。 -型変数が何の型になるのかという情報は実行時には決まっており、Haskell の型安全を保つ。 - -= の右側が、新しい型の定義である。 -$|$ は、もしくはという意味である。 -つまりリストは、[] もしくは、a : [a] という値になることが分かる。 -[] は空リストを表す。型名と同じであるが、型とは名前領域が異なるため問題ない。 -型名はプログラム中では注釈としてしか使われないためである。 +型名の右に a というのがあるが, これは多相型を表すのに使う型変数である. +型変数は様々な型を取ることができる. +リストは, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. +型変数が何の型になるのかという情報は実行時には決まっており, Haskell の型安全を保つ. -a : [a] は再帰的なデータ構造である。 -何らかの型の値 a を、: で繋げて、再度リストの定義を呼んでいる。 += の右側が, 新しい型の定義である. +$|$ は, もしくはという意味である. +つまりリストは, [] もしくは a : [a] という値になることが分かる. +[] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. +型名はプログラム中では注釈としてしか使われないためである. + +a : [a] は再帰的なデータ構造である. +何らかの型の値 a を : で繋げて, 再度リストの定義を呼んでいる. -リストは無限に繋げることができ、リストの終端は空のリスト、つまり [] で終わる。 -[1,2,3]という様にリストを表すが、これは単なるシンタックスシュガーであり、 -内部では 1 : 2 : 3 : [] のように表現される。 +リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. +[1,2,3]という様にリストを表すが, これは単なるシンタックスシュガーであり, +内部では 1 : 2 : 3 : [] のように表現される. -リストは、: を使うことで新しい要素を加えることができるが、型変数は1つであり、全ての要素は同じ型の要素である必要がある。 -違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す。 -例えば、Int のリスト [3,4] に、文字である 'b' を付け加えようとした場合以下の様なエラーが発生する。 +リストは : を使うことで新しい要素を加えることができるが, 型変数は1つであり, 全ての要素は同じ型の要素である必要がある. +違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. +例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する（ソースコード\ref{src:error}）. -\begin{lstlisting}[caption=Haskellのコンパイル時エラー] +\begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー] <interactive>:3:7: Couldn't match type `Int' with `Char' Expected type: [Char] Actual type: [Int] \end{lstlisting} -型検査でも捕まえられないエラーは存在する。 -例えば、式 "1 `div` 0" は、型エラーではないが、0 での除算は定義されていないので評価時にエラーとなる。 +型検査でも捕まえられないエラーは存在する. +例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる. \subsubsection{型推論} -Haskell は型推論を持つ。 -型推論のない静的型付け言語は、プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない。 - -例として、開発したデータベースで実装した関数に対して型推論を行ってみる。 -関数の詳細な動作はデータベースの実装で述べるが、getChildrenという、関数がある。 +Haskell は型推論を持つ. +型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. +型推論のない静的型付け言語は, プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない. -\begin{lstlisting}[caption=getChildren関数] -getChildren node path = elems map - where - target = getNode node path - map = children target +例として, 開発したデータベースで実装した getChildren という関数に対して型推論を行ってみる（ソースコード\ref{src:getchildren}）. + +\begin{lstlisting}[label=src:getchildren, caption=getChildren関数] +getChildren node path = elems (children (getNode node path)) \end{lstlisting} -型の注釈なしに関数を定義し、Haskell の対話環境である GHCi で型情報を取得してみる。 -型情報を取得するには、:type の後ろに関数名を入力する。 +型の注釈なしに関数を定義し, Haskell の対話環境である GHCi で型情報を取得してみる. +型情報を取得するには, :type の後ろに関数名を入力する（ソースコード\ref{src:type}）. -\begin{lstlisting}[caption=型情報の取得] +\begin{lstlisting}[label=src:type, caption=型情報の取得] *Jungle> :type getChildren getChildren :: Node -> [Int] -> [Node] \end{lstlisting} -そうすると、推論された型情報 Node -$>$ [Int] -$>$ [Node]が得られる。 -この型情報は期待する型の定義と一致する。 -Haskell では、プログラマが型の宣言を行わずとも、型を推論し型安全を保つ。 +そうすると, 推論された型情報 Node -$>$ [Int] -$>$ [Node]が得られる. +この型情報は期待する型の定義と一致する. + +この情報はgetChildrenに含まれるいくつかの関数の型を確認することで導き出すことができる（ソースコード\ref{src:type2}）. -しかしながら、明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。 +\begin{lstlisting}[label=src:type2, caption=getChildrenに含まれる関数の型] +getNode :: Node -> Path -> Node +elems :: Map k a -> [a] +children :: Node -> Map Int Node +\end{lstlisting} + +例えば, getChildrenの引数である, node と path は getNode に渡されているため, getNode の型である Node 型と Path 型であることが分かる. +返り値となる型は, elemsの[a]となる. このaは, elemsが受け取るMapの2つ目の型と一致するため, childrenの返り値であるMap Int Node より, [Node]ということが分かる. + +Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. +しかしながら, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である. \section{モナド} -Haskell では、さまざまな目的にモナドを使う。 -I/O 処理を行うためには IO モナドを使う必要がある。 -プログラミングを行うにあたり、I/O 処理は欠かせないため、モナドの説明を行う。 +Haskell では, さまざまな目的にモナドを使う. +I/O 処理を行うためには IO モナドを使う必要がある. +プログラミングを行うにあたり, I/O 処理は欠かせないため, モナドの説明を行う. -モナドとは、型クラスの 1 つである。 -型クラスは型の振る舞いを定義するものである。 -ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 -これは、それらの関数がその型ではどのような意味になるのか定義するということである。 +モナドとは, 型クラスの 1 つである. +型クラスは型の振る舞いを定義するものである. +ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. +これは, それらの関数がその型ではどのような意味になるのか定義するということである. -モナドとなる型は、型変数として具体型をただ１つ取る。 -これにより何かしらのコンテナに包まれた値を実現する。 -モナドの振る舞いは型クラスとして実装し、関数として return および $>>$= (bind) を定義する。 +モナドとなる型は, 型変数として具体型をただ１つ取る. +これにより何かしらのコンテナに包まれた値を実現する. +モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する（ソースコード\ref{monad}）. -\begin{lstlisting}[label=monad, caption=モナドに属する関数] +\begin{lstlisting}[label=monad, caption=モナドに属する関数の型] return :: Monad m => a -> m a (>>=) :: Monad m => m a -> (a -> m b) -> m b \end{lstlisting} -return は値を持ち上げてコンテナに包む機能を実装する（図\ref{fig:monad_return}）。 +return は値を持ち上げてコンテナに包む機能を実装する（図\ref{fig:monad_return}）. \begin{figure}[!htbp] \begin{center} @@ -161,8 +186,8 @@ \label{fig:monad_return} \end{figure} -bind は、「コンテナに包まれた値」と、「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり、コンテナに包まれた値をその関数に適用する（図\ref{fig:monad_bind}）。 -適用する際、前のコンテナの結果に依存して、後のコンテナの振る舞いを変えられる。 +bind は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用する（図\ref{fig:monad_bind}）. +適用する際, 前のコンテナの結果に依存して, 後のコンテナの振る舞いを変えられる. \begin{figure}[!htbp] \begin{center} @@ -172,46 +197,51 @@ \label{fig:monad_bind} \end{figure} -この2つの関数を利用することにより、文脈を保ったまま関数を繋いでいくことができる。 -Haskell の遅延評価は記述した順序で実行することを保証しないが、モナドの bind は実行順序の指定も可能で、IO モナドを bind で繋いだものは記述順に実行することができる。 +この2つの関数を利用することにより, 文脈を保ったまま関数を繋いでいくことができる. +Haskell の遅延評価は記述した順序で実行することを保証しないが, モナドの bind は実行順序の指定も可能で, IO モナドを bind で繋いだものは記述順に実行することができる. \subsubsection{Maybe モナド} -文脈を保ったまま関数を繋いでいくとはどういうことなのか、具体例を用いて説明する。 +文脈を保ったまま関数を繋いでいくとはどういうことなのか, 具体例を用いて説明する. -Maybe 型は失敗する可能性を扱うデータ型である。 +Maybe 型は失敗する可能性を扱うデータ型である（ソースコード\ref{src:maybe}）. -\begin{lstlisting}[ caption=Maybe型の定義] +\begin{lstlisting}[label=src:maybe,caption=Maybe型の定義] data Maybe a = Nothing | Just a \end{lstlisting} -失敗したことを表す Nothing、もしくは成功したことを表す Just a のいずれかの値を取る。 -Maybe 型が使われている例として、Data.Map の lookup 関数がある。 -Data.Map は Key と Value を保持する辞書型のデータ構造である。 -何らかの Key を渡して、Data.Map から値を取得しようとした時、返される値は Maybe 型である。 -何かしらの値が取得できた場合は、Just a として値に Just がついて返される。 -取得できなければ、Nothing が返る。 +失敗したことを表す Nothing, もしくは成功したことを表す Just a のいずれかの値を取る. -Maybe モナドを使いたい場面は、失敗するかもしれないという計算を繋いでいく時である。 -Maybe モナドの定義をみていく。 +Maybe 型が使われている例として, Data.Map の lookup 関数がある. +Data.Map は Key と Value を保持する辞書型のデータ構造である. +何らかの Key を渡して, Data.Map から値を取得しようとした時, 返される値は Maybe Value 型である. +何かしらの値が取得できた場合は, Just a として Value に Just がついて返される. +取得できなければ, Nothing が返る. -\begin{lstlisting}[caption=Maybeモナドの定義] +Maybe モナドを使いたい場面は, 失敗するかもしれないという計算を繋いでいく時である. +Maybe モナドの定義をみていく（ソースコード\ref{src:maybe_monad}）. + +\begin{lstlisting}[label=src:maybe_monad, caption=Maybeモナドの定義] instance Monad Maybe where return x = Just x Nothing >>= f = Nothing Just x >>= f = f x \end{lstlisting} -Maybe モナドの return は、値をJustで包む。 -これがコンテナに包む機能という意味である。 -$>>$= (bind) は、「コンテナに包まれた値」と、「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり、コンテナに包まれた値をその関数に適用すると説明した。 -Maybe モナドの場合、コンテナが Nothing なら、そのまま Nothing を返す。 -コンテナがJustならば、Just に包まれた値を取り出し、「普通の値を取りコンテナに包まれた値を返す関数」に適用する。 +instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である. +その後実装すべき関数である return と $>>$= (bind) を定義していく. + +Maybe モナドの return は, 値をJustで包む. +これがコンテナに包む機能という意味である. -失敗するかもしれない計算を繋いでいくとはどういうことなのか。 -単純な関数を定義して更に説明していく。 +$>>$= (bind) は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用すると説明した. +Maybe モナドの場合, コンテナが Nothing なら, そのまま Nothing を返す. +コンテナがJustならば, Just に包まれた値を取り出し, 「普通の値を取りコンテナに包まれた値を返す関数」に適用する. -\begin{lstlisting}[caption=up関数とdown関数] +失敗するかもしれない計算を繋いでいくとはどういうことなのか. +単純な関数を定義して説明する（ソースコード\ref{src:updown}）. + +\begin{lstlisting}[label=src:updown, caption=up関数とdown関数] up 4 = Nothing up n = Just (n + 1) @@ -219,17 +249,13 @@ down n = Just (n - 1) \end{lstlisting} -関数 up と down を定義した。 -4以上はこれ以上、上がれないため失敗、 -0以下はこれ以上、下がれないため失敗と考える。 +関数 up と down を定義した. +up の場合, 引数として4が渡された場合, 上がれないため失敗, +down の場合, 引数として0が渡された場合, 下がれないため失敗と考える. -3 という値にdown, down, up、up 繰り返していく時、モナドを使わない場合以下のように定義することになる。 -case 式は、caseとofの間の式を評価し、その値によっ評価を分岐させることができる。 -case を受け取る $->$ の左の部分はパターンマッチを行うこともできる。 -また、case は式のため、$->$ の右の部分の全ての型は一意である必要がある。 -Haskell では分岐によって返ってくる値の型が異なるということはできない。 +3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. -\begin{lstlisting}[caption=Maybeモナドを使わずにupとdownを行う] +\begin{lstlisting}[label=src:up_without_monad, caption=Maybeモナドを使わずにupとdownを行う] updown :: Maybe Int updown = case down 3 of Nothing -> Nothing @@ -241,49 +267,57 @@ \end{lstlisting} -毎回、失敗したか成功したか確認するために非常に煩雑なコードとなってしまった。 -これを文脈を保ったまま、関数を繋げられる モナドを使えば以下のように記述できる。 +case 式は, caseとofの間の式を評価し, その値によっ評価を分岐させることができる. +case を受け取る $->$ の左の部分はパターンマッチを行うこともできる. +また, case は式のため, $->$ の右の部分の全ての型は一意である必要がある. +Haskell では分岐によって返ってくる値の型が異なるということはできない. -\begin{lstlisting}[caption=Maybeモナドを用いてupとdownを行う] +毎回, 失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. +これを文脈を保ったまま, 関数を繋げられる モナドを使えばソースコード\ref{src:upmonad}のように記述できる. + +\begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う] return 3 >>= down >>= down >>= up >>= up \end{lstlisting} -Maybe モナドを使うことで、この計算は失敗しているかもしれないという文脈を扱うことができる。 +Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を扱うことができる. \subsubsection{IO モナド} -Haskellで副作用を持つ処理を実行するには、IO モナドを利用する。 -IO モナド自体は単なる命令書であり、命令ではない。 -bind を使って、小さな命令書を合成して大きな命令書を作成できる。 -最終的に、mainという名前をつけることで初めてランタイムにより実行される。 +Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. +IO モナド自体は単なる命令書であり, 命令ではない. +bind を使って, 小さな命令書を合成して大きな命令書を作成できる. +最終的に, mainという名前をつけることで初めてランタイムにより実行される（ソースコード\ref{src:iomonad}）. -Haskell の関数には副作用がないと述べたが、IO モナドを返す関数にも副作用は存在しない。 +\begin{lstlisting}[label=src:iomonad, caption=Hello Worldと出力] +main :: IO () +main = putStrLn "Hello, World!" +\end{lstlisting} -例えば、Jungle には getRootNode というIOを返す関数がある。 -呼び出した状況によって、返ってくるノードが違うため副作用があるようにみえる。 -しかし、実際にこの関数が返すのは、「ノードを取得する」という命令書である。 -どんな状況においても同じ命令書を返すため、副作用はない。 +Haskell の関数には副作用がないと述べたが, IO モナドを返す関数にも副作用は存在しない. + +例えば, Jungle には getRootNode というIOを返す関数がある. +呼び出した状況によって, 返ってくるノードが違うため副作用があるようにみえる. +しかし, 実際にこの関数が返すのは, 「ノードを取得する」という命令書である. +どんな状況においても同じ命令書を返すため, 副作用はない. \clearpage \section{並列実行} -Haskellはデフォルトではシングルスレッドで走る。 -並列に実行したい場合は、-threaded 付きでコンパイルし、RTS の -N オプションを付けて実行する。 --N オプションで指定された数だけ、OSのスレッドが立ち上がり実行される。 +Haskellはデフォルトではシングルスレッドで走る. +並列に実行したい場合は, -threaded 付きでコンパイルし, RTS の -N オプションを付けて実行する. +-N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される. \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子] $ ghc -O2 par.hs -threaded $ ./par +RTS -N2 \end{lstlisting} -当然これだけでは並列に動かず、並列に実行できるようにプログラムを書く必要がある。 +当然これだけでは並列に動かず, 並列に実行できるようにプログラムを書く必要がある. -Control.Parallel.Strategies モジュールにある、 -Eval モナドを用いた並列化について説明する。 -Eval モナドは並列処理を行うためのモナドである。 - -Eval モナドで並列処理を行う使用例を示す。 +Control.Parallel.Strategies モジュールにある, +Eval モナドを用いた並列化について説明する. +Eval モナドは並列処理を行うためのモナドである. Eval モナドで並列処理を行う使用例を示す（ソースコード\ref{src:evalmonad}）. %% 完全に動くプログラム -\begin{lstlisting}[caption=Evalモナドの使用例] +\begin{lstlisting}[label=src:evalmonad, caption=Evalモナドの使用例] import Control.Parallel.Strategies main = print (runEval test) @@ -291,12 +325,11 @@ num :: Integer num = 1000000 + test :: Eval (Integer, Integer) -test = do - a <- rpar (sum' 0 num) - b <- rpar (sum' num (num*2)) - return (a,b) - +test = rpar (sum' 0 num) >>= (\a -> + rpar (sum' num (num*2)) >>= (\b -> + return (a,b))) sum' :: Integer -> Integer -> Integer sum' begin end = if begin < end @@ -304,10 +337,10 @@ else begin \end{lstlisting} -まず、Eval モナドが定義された、Control.Parallel.Strategies をロードし、Eval モナドを利用できるようにしている。 +まず, Eval モナドが定義された, Control.Parallel.Strategies をロードし, Eval モナドを利用できるようにしている. -Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される。 -今回は、print (runEval test)が実行される。 +Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される. +今回は, print (runEval test)が実行される. \begin{lstlisting}[label=eval, caption=Eval モナド] data Eval a @@ -317,40 +350,52 @@ rpar :: a -> Eval a \end{lstlisting} -並列処理を行うには、rpar を使う。 -rpar で挟んだ関数は並列に実行される。 -Eval モナドの関数の型をみると、rpar は、a を モナドに包み、逆にrunEval はモナドから a を取り出している。 -rpar で並列化可能計算を示したあと、runEvalで実行する。 +並列処理を行いたい箇所には, rpar を使う. +rpar の引数とした関数は並列に実行可能であることを示すことができる. +Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している. +rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. -test の = のすぐ後にあるdoはモナドのためのシンタックスシュガーであり、do 構文と呼ばれる。 -Haskell では、モナドを単一のモナドとするために、do構文を使う。 -$>>$= (bind)を使ってまとめることもできるが、do 構文を使うことでbindの入れ子構造を手続き言語のような書き方で書くことができる。 -do 構文を用いない場合、以下の様な式になる。 +rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている. +Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる. +do 構文を使うことでbindの入れ子構造を簡潔に書ける. -\begin{lstlisting}[caption=do構文を使わない場合] +\begin{lstlisting}[label=src:do, caption=do構文] test :: Eval (Integer, Integer) -test = rpar (sum' 0 num) >>= (\a -> - rpar (sum' num (num*2)) >>= (\b -> - return (a,b))) +test = do + a <- rpar (sum' 0 num) + b <- rpar (sum' num (num*2)) + return (a,b) \end{lstlisting} -sum' は2つの引数をとって、開始点から終了点までの値をすべて足し合わせる関数である。 -並列処理に負荷を与えるために使う。 -ifで、開始点が終了点を超えてないか調べ、超えてなければ再帰的に呼び出して足し合わせを行う。 +sum' は2つの引数をとって, 開始点から終了点までの値をすべて足し合わせる関数である. +並列処理に負荷を与えるために使う. +ifで, 開始点が終了点を超えてないか調べ, 超えてなければ再帰的に呼び出して足し合わせを行う. + +test で返ってくる型は, Eval (Integer, Integer)で, その後 runEval 関数を適用することで, (Integer, Integer)となる. +そして最後にprint で出力される. -test で返ってくる型は、Eval (Integer, Integer)で、その後 runEval 関数を適用することで、(Integer, Integer)となる。 -そして最後にprint で出力される。 +Haskell は遅延評価を行うため, 必要となるまで式の評価が遅延される. +今回の場合, mainのprintがなければそもそも計算が行われない（ソースコード\ref{src:donteval}）. + +\begin{lstlisting}[label=src:donteval, caption=計算が行われない例] +main = return (runEval test) +\end{lstlisting} -Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。 -今回の場合、最後のprintがなければそもそも計算が行われない。 +出力することで, 値が必要となるため計算される. +また, testで返される2つの計算を1つだけ出力するようにした場合, 1つのみ計算され並列実行は行われない（ソースコード\ref{src:donteval2}）. +fst は, (a,b)とあったとき aを取得する関数である. + +\begin{lstlisting}[label=src:donteval2, caption=並列実行されない例] +main = print (fst (runEval test)) +\end{lstlisting} -並列に動くように処理を分割した後は、Haskell の遅延評価に気をつける必要がある。 -値が必要となるprintなどを行えば、並列に実行可能な部分が並列に実行される。 +Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. +値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. -rpar を使用する際に気をつけるのは、別の計算の値に依存する計算がある場合、その2つの計算は並列実行できないということである。 -例えば、以下のような場合は並列実行ができない。 +また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. +例えば, ソースコード\ref{src:rpar}のような場合は並列実行ができない. -\begin{lstlisting}[caption=前の計算に依存した計算] +\begin{lstlisting}[label=src:rpar, caption=前の計算に依存した計算] test2 :: Eval (Integer, Integer) test2 = do a <- rpar (sum' 0 num)
--- a/paper/chapter2.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/chapter2.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,32 +1,32 @@ \chapter{Haskellによる\\並列データベースの設計}\label{ch:design} \section{マルチコアプロセッサで十分な性能を得るためには} -現在、CPU はマルチコア化が進んでいる。 -マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保つ必要がある。 -アムダールの法則\cite{amdahl}によると、並列度が80 \% の場合、どんなにコア数を増やしても性能向上率は5倍にしかならない。 +現在, CPU はマルチコア化が進んでいる. +マルチコアプロセッサで線形に性能向上をするためには, 処理全体で高い並列度を保つ必要がある. +アムダールの法則\cite{amdahl}によると, 並列度が80 \% の場合, どんなにコア数を増やしても性能向上率は5倍にしかならない. -% ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。 -% 利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。 -% スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。 -% 一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。 +% ウェブサービスでは, ニーズの変化に柔軟に対応できる能力が求められる. +% 利用者や負荷の増大に対し, CPU のコア数に応じてパフォーマンスを線形に向上できる能力, すなわちスケーラビリティが必要となる. +% スケーラビリティが線形的であれば, リソースの追加に比例したパフォーマンスを得ることが可能である. +% 一方, スケーラビリティが線形的でないと, いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる. -CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできるようにし、並列度を高める必要がある。 -通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。 +CPU コア数に応じて, データベースを線形に性能向上させたい場合, 別々の CPU コアから同時にデータベースへアクセスできるようにし, 並列度を高める必要がある. +通常は, 同一のデータへアクセスする場合, 競合が発生してしまい処理性能に限界が生じる. -本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。 -競合を発生させないためには、既にあるデータを変更しなければよい。 -非破壊的木構造は、変更元となる木構造を変更しない。 -そのため、別々の CPU コアから並列にアクセスが可能であり、スケーラビリティを実現できる。 +本研究では, 非破壊的木構造という手法を用いて競合が発生する問題を解決する. +競合を発生させないためには, 既にあるデータを変更しなければよい. +非破壊的木構造は, 変更元となる木構造を変更しない. +そのため, 別々の CPU コアから並列にアクセスが可能であり, スケーラビリティを実現できる. \newpage \section{非破壊的木構造} -非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。 -既にあるデータを変更しないため、データの競合状態が発生せず、並列に読み書きが行える。 +非破壊的木構造は, 木構造を書き換えることなく編集を行う手法である. +既にあるデータを変更しないため, データの競合状態が発生せず, 並列に読み書きが行える. -また、元の木構造は破壊されることがないため、自由にコピーを行うことができる。 -コピーを複数作成することでアクセスを分散させることも可能である。 +また, 元の木構造は破壊されることがないため, 自由にコピーを行うことができる. +コピーを複数作成することでアクセスを分散させることも可能である. -図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。 +図\ref{fig:nondestructive_tree_modification}では, ノード 6 をノード A へ書き換える処理を行なっている. \begin{figure}[!htbp] \begin{center} @@ -36,10 +36,10 @@ \label{fig:nondestructive_tree_modification} \end{figure} -この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。 -閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。 -排他制御をせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用である。 -元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。 +この編集方法を用いた場合, 閲覧者が木構造を参照してる間に, 木の変更を行っても問題がない. +閲覧者は木が変更されたとしても, 保持しているルートノードから整合性を崩さずに参照が可能である. +排他制御をせずに並列に読み書きが可能であるため, スケーラブルなシステムに有用である. +元の木構造は破壊されることがないため, 自由にコピーを作成しても構わない. したがってアクセスの負荷の分散も可能である. \begin{figure}[!htbp] \begin{center} @@ -52,10 +52,10 @@ \newpage \section{ルートノード} -非破壊的木構造では、ルートノードの管理が重要である。 -ルートノードは、木の最新の状態を更新・参照するのに使う。 -ルートノードの情報は、全てのスレッドで共有する必要があり、スレッドセーフに取り扱う必要がある。 -一度ルートノードの情報を取得すれば、その後は排他制御なしに木構造へアクセスできる（図\ref{fig:rootnode}）。 +非破壊的木構造では, ルートノードの管理が重要である. +ルートノードは, 木の最新の状態を更新・参照するのに使う. +ルートノードの情報は, 全てのスレッドで共有する必要があり, スレッドセーフに取り扱う必要がある. +一度ルートノードの情報を取得すれば, その後は排他制御なしに木構造へアクセスできる（図\ref{fig:rootnode}）. \begin{figure}[!htbp] \begin{center} @@ -65,23 +65,23 @@ \label{fig:rootnode} \end{figure} -ルートノードはスレッド間で共有する状態を持つため、Haskell では IO モナドを用いる必要がある。 -これには、Haskell のソフトウェア・トランザクショナル・メモリ（STM）を利用する。 -STM は排他制御を行わず、スレッドセーフに状態を扱うことができる。 -STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。 -STM は、STM モナドという特殊なモナドの中でのみ変更できる。 -STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する。（atomically コンビネータを用いることで IO モナドとして返される）。 -いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。 -こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。 -トランザクションから出る時に、以下のことが１つだけ起こる。 +ルートノードはスレッド間で共有する状態を持つため, Haskell では IO モナドを用いる必要がある. +これには, Haskell のソフトウェア・トランザクショナル・メモリ（STM）を利用する. +STM は排他制御を行わず, スレッドセーフに状態を扱うことができる. +STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. +STM は, STM モナドという特殊なモナドの中でのみ変更できる. +STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する. （atomically コンビネータを用いることで IO モナドとして返される）. +いったんブロック内に入るとそこから出るまでは, そのブロック内の変更は他のスレッドから見ることはできない. +こちら側のスレッドからも他のスレッドによる変更はみることはできず, 実行は完全に孤立して行われる. +トランザクションから出る時に, 以下のことが１つだけ起こる. \begin{itemize} - \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。 - \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。 + \item 同じデータを平行して変更したスレッドが他になければ, 加えた変更が他のスレッドから見えるようになる. + \item そうでなければ, 変更を実際に実行せずに破棄し, アクションのブロックを再度実行する. \end{itemize} -STM は排他制御を行わないため、簡単に扱うことができる。 -ルートノードの情報の取得だけならば、並列に取得できる。 -ルートノードの情報の更新の場合は、他から変更があれば再度やり直すということが自動的に行われる。 +STM は排他制御を行わないため, 簡単に扱うことができる. +ルートノードの情報の取得だけならば, 並列に取得できる. +ルートノードの情報の更新の場合は, 他から変更があれば再度やり直すということが自動的に行われる. -以前の実装では、ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}。 -しかしながら、非破壊的木構造全体をSTMで管理すると並列実行時に性能が出ないため、ルートノードのみの管理に変更を行った。 +以前の実装では, ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}. +しかしながら, 非破壊的木構造全体をSTMで管理すると並列実行時に性能が出ないため, ルートノードのみの管理に変更を行った.
--- a/paper/chapter3.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/chapter3.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,65 +1,65 @@ \chapter{Haskellによる\\並列データベースの実装}\label{ch:impl} -本章では、並列データベース Jungle の実装について述べる。 +本章では, 並列データベース Jungle の実装について述べる. \section{木構造データベース Jungle} -非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。 -非破壊的木構造の方法に則った関数を提供する。 +非破壊的木構造データベース Jungle は, Haskell で実装された並列データベースである. +非破壊的木構造の方法に則った関数を提供する. -% 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。 -Jungle の基本的な使い方の手順について説明する。 +% 本研究では, HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが, 他のシステムに組み込むことも可能である. +Jungle の基本的な使い方の手順について説明する. \begin{enumerate} \item{木構造を保持する Jungle を作成する} \item{Jungle 内に新しい木を名前をつけて作成する} - \item{木の名前を用いて、ルートノードの取得を行い、データを参照する} - \item{もしくは、木の名前を用いて、ルートノードの更新を行う} + \item{木の名前を用いて, ルートノードの取得を行い, データを参照する} + \item{もしくは, 木の名前を用いて, ルートノードの更新を行う} \end{enumerate} \subsubsection{Jungle が持つデータ型} -Jungle が持つのデータ型を表\ref{tab:components}に表す。 -木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。 -Node は子と属性を任意の数持てる。 -データ型として定義することで、データ内部の型の整合性が保たれ、また型検査でエラーがないか検出することができる。 -Jungle のデータ型について、ひとつずつ説明する。 +Jungle が持つのデータ型を表\ref{tab:components}に表す. +木構造の集まりを表現する Jungle, 単体の木構造を表現する Tree がある. +Node は子と属性を任意の数持てる. +データ型として定義することで, データ内部の型の整合性が保たれ, また型検査でエラーがないか検出することができる. +Jungle のデータ型について, ひとつずつ説明する. \begin{table}[!htbp] \label{tab:components} \begin{center} \begin{tabular}{|c||c|} \hline 型名 & 概要 \\ \hline -Jungle & 木の作成・取得を担当する。 \\ \hline -Tree & 木の名前とルートノードの情報を保持している。 \\ \hline -Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline +Jungle & 木の作成・取得を担当する. \\ \hline +Tree & 木の名前とルートノードの情報を保持している. \\ \hline +Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline \end{tabular} \end{center} \caption{Jungle が持つデータ型} \end{table} \subsection{Jungle} -Jungle は木構造の集まりを表現する。 -木には名前がついており、Tree の情報と一緒に保持している。 +Jungle は木構造の集まりを表現する. +木には名前がついており, Tree の情報と一緒に保持している. \begin{lstlisting}[caption=Jungleのデータ型の定義] data Jungle = Jungle { getJungleMap :: (TVar (Map String Tree)) } \end{lstlisting} -Jungle のデータ構造は、Jungle (TVar (Map String Tree)) である。 -getJungleMap :: というのは、Haskell のレコード構文である。 +Jungle のデータ構造は, Jungle (TVar (Map String Tree)) である. +getJungleMap :: というのは, Haskell のレコード構文である. -レコード構文は、データ構造へのアクセサを提供する。 -getJungleMap は関数で、以下のような型を持つ。 -これは、Jungleを受け取って、TVar (Map String Tree)を返す関数である。 +レコード構文は, データ構造へのアクセサを提供する. +getJungleMap は関数で, 以下のような型を持つ. +これは, Jungleを受け取って, TVar (Map String Tree)を返す関数である. -レコード構文はデータ型を受け取って、:: の右側の型の値を取り出せる関数を作成すると思えば良い。 +レコード構文はデータ型を受け取って, :: の右側の型の値を取り出せる関数を作成すると思えば良い. \begin{lstlisting}[caption=getJungleMap] getJungleMap :: Jungle -> TVar (Map String Tree) \end{lstlisting} -Jungle の木の取り扱いには、Haskell の Data.Map を利用している。 -型名は、Map である。 -Map は、連想配列を扱うことのできるデータ構造である。 -平衡木を用いて、挿入や参照が O (log n)で済むように設計されている。 -Data.Mapを理解するためにはリストで考えると分かりやすい。 +Jungle の木の取り扱いには, Haskell の Data.Map を利用している. +型名は, Map である. +Map は, 連想配列を扱うことのできるデータ構造である. +平衡木を用いて, 挿入や参照が O (log n)で済むように設計されている. +Data.Mapを理解するためにはリストで考えると分かりやすい. \begin{lstlisting}[caption=getJungleMap] data Map k a = Map [(k,a)] @@ -77,23 +77,23 @@ test = Map [("key","value"),("fizz","buzz")] \end{lstlisting} -Map は、キーと値のペアのリストだと考えることができる。 -キーが一致する値を探す場合、lookup'を用いる。 -Maybe モナドを用いて、データがなければ Nothing、データがあれば Just に包んで返す。 -$=>$ の前にある、Eq kは、型クラスの制約である。 -内部で k と k' の同値性をテストしているため、k は同値性をチェックできる型クラス Eq に属している型である必要がある。 +Map は, キーと値のペアのリストだと考えることができる. +キーが一致する値を探す場合, lookup'を用いる. +Maybe モナドを用いて, データがなければ Nothing, データがあれば Just に包んで返す. +$=>$ の前にある, Eq kは, 型クラスの制約である. +内部で k と k' の同値性をテストしているため, k は同値性をチェックできる型クラス Eq に属している型である必要がある. -新たにキーと値のペアを、Mapに追加するには insertを用いる。 -Haskell では、受け取った引数を変更することができないため、ペアを追加した新しい Map を返す。 +新たにキーと値のペアを, Mapに追加するには insertを用いる. +Haskell では, 受け取った引数を変更することができないため, ペアを追加した新しい Map を返す. -木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。 -これは、各スレッドから木構造を新たに作成できるようにするためである。 -STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。 -Jungle のデータ構造の Map の前に付いている TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。 +木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ, スレッド間で共有できるようにしてある. +これは, 各スレッドから木構造を新たに作成できるようにするためである. +STM は, スレッド間でデータを共有するためのツールである. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. +Jungle のデータ構造の Map の前に付いている TVar というのは, Transactional variablesの略で, STM で管理する変数に対して利用する. \subsubsection{Jungle と木の作成} -Jungle は、Mapで木を管理しているため、複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）。 +Jungle は, Mapで木を管理しているため, 複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）. \begin{figure}[!htbp] \begin{center} @@ -103,11 +103,11 @@ \label{fig:jungle} \end{figure} -木構造の識別、つまり Map の キー にはString を利用する。 -String は Haskell の文字列の型で、Char のリスト [Char] の別名である。 +木構造の識別, つまり Map の キー にはString を利用する. +String は Haskell の文字列の型で, Char のリスト [Char] の別名である. -Jungle を作成するには、createJungle を用いる。 -empty は空のMapを作成する関数である。 +Jungle を作成するには, createJungle を用いる. +empty は空のMapを作成する関数である. \begin{lstlisting}[caption=createJungle] createJungle :: IO Jungle @@ -124,13 +124,13 @@ atomically :: STM a -> IO a \end{lstlisting} -createJungleは、新たにSTMの変数を作成する newTVar を実行する。 -newTVar などの STM の操作は STM モナド内で行う。 -最後にatomicallyを行うことで、do 構文内がトランザクションとして実行される。 +createJungleは, 新たにSTMの変数を作成する newTVar を実行する. +newTVar などの STM の操作は STM モナド内で行う. +最後にatomicallyを行うことで, do 構文内がトランザクションとして実行される. -atomically の隣にある \$ は関数適用演算子である。 -\$ 関数は最も低い優先順位を持っており、右結合である。 -括弧を減らすのに使う。\$ を使わない場合は以下の様に記述することになる。 +atomically の隣にある \$ は関数適用演算子である. +\$ 関数は最も低い優先順位を持っており, 右結合である. +括弧を減らすのに使う. \$ を使わない場合は以下の様に記述することになる. \begin{lstlisting}[caption=STMの関数] createJungle :: IO Jungle @@ -139,15 +139,15 @@ return (Jungle map)) \end{lstlisting} -createJungle は、IOを返すため使う際には main に関連付ける必要がある。 +createJungle は, IOを返すため使う際には main に関連付ける必要がある. \subsection{Tree} -Jungleが保持する木の情報は、内部的には Tree というデータ型で保持している。 -Tree は木の名前と、ルートノードの情報を持っている。 -実際にユーザがJungleを利用する際は、Jungle と木の名前を使ってルートノードを取ってくるため、Tree という構造は見えない。 +Jungleが保持する木の情報は, 内部的には Tree というデータ型で保持している. +Tree は木の名前と, ルートノードの情報を持っている. +実際にユーザがJungleを利用する際は, Jungle と木の名前を使ってルートノードを取ってくるため, Tree という構造は見えない. -ルートノードの情報はスレッド間で状態を共有する必要がある。 -スレッドセーフに取り扱う必要があるため、この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。 +ルートノードの情報はスレッド間で状態を共有する必要がある. +スレッドセーフに取り扱う必要があるため, この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している. \begin{lstlisting}[caption=Treeのデータ型の定義] data Tree = Tree @@ -155,8 +155,8 @@ , treeName :: String } \end{lstlisting} -新たな非破壊的木構造を作るには、createTree を用いる。 -createTree は、createJungleで作成した Jungle と木の名前を String で受け取る。 +新たな非破壊的木構造を作るには, createTree を用いる. +createTree は, createJungleで作成した Jungle と木の名前を String で受け取る. \begin{lstlisting}[caption=createTree] createTree :: Jungle -> String -> IO () @@ -174,12 +174,12 @@ emptyNode = Node (empty) (empty) \end{lstlisting} -createJungleも STM を操作するため IOを返す。 -Jungle の持つ、tmapをreadTVarで取得し、複数の木構造を管理するためのMapを取得する。 -STM の変数をもった Tree を作成し、Map に insert する。 -writeTVar は更新する先の変数と、更新内容の2つを受け取る STM の関数である。 +createJungleも STM を操作するため IOを返す. +Jungle の持つ, tmapをreadTVarで取得し, 複数の木構造を管理するためのMapを取得する. +STM の変数をもった Tree を作成し, Map に insert する. +writeTVar は更新する先の変数と, 更新内容の2つを受け取る STM の関数である. -実際にcreateJungleとcreateTreeを使う時は以下のように記述する。 +実際にcreateJungleとcreateTreeを使う時は以下のように記述する. \begin{lstlisting}[caption=データベースと木の作成] main = do @@ -189,8 +189,8 @@ \subsubsection{ルートノード} -非破壊的木構造データベース Jungle では、木の最新の状態を更新・参照するのにルートノードを使う。 -ルートノードは、最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）。 +非破壊的木構造データベース Jungle では, 木の最新の状態を更新・参照するのにルートノードを使う. +ルートノードは, 最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）. \begin{figure}[!htbp] \begin{center} @@ -200,11 +200,11 @@ \label{fig:getrootnode} \end{figure} -ルートノードに関する関数を説明する。 +ルートノードに関する関数を説明する. -getRootNode は、最新のルートノードを取得できる。 -データベースと木の名前を渡すことで利用できる。 -例えば、図\ref{fig:getrootnode}の状態の時は、B というルートノードが取得できる。 +getRootNode は, 最新のルートノードを取得できる. +データベースと木の名前を渡すことで利用できる. +例えば, 図\ref{fig:getrootnode}の状態の時は, B というルートノードが取得できる. \begin{lstlisting}[caption=最新のルートノードの取得] getRootNode :: Jungle -> String -> IO Node @@ -216,17 +216,17 @@ Just x -> rootNode x \end{lstlisting} -まず、readTVarでJungleが持つmapを参照する。 -Haskell の where キーワードは、計算の中間結果に名前をつけるために用いられる。 -今回は、root\_node という map を受け取る関数を定義している。 -root\_node map では、Jungle が持つ Map をみて取得しようとしている名前の木構造があるかどうか調べている。 -木構造があった場合、rootNodeというTreeに定義されているレコード構文のアクセサ関数を使って、(TVar Node)を取得する。 -最後に、(TVar Node)に対して、readTVarを行うことで最新のルートノードが取得できる。 +まず, readTVarでJungleが持つmapを参照する. +Haskell の where キーワードは, 計算の中間結果に名前をつけるために用いられる. +今回は, root\_node という map を受け取る関数を定義している. +root\_node map では, Jungle が持つ Map をみて取得しようとしている名前の木構造があるかどうか調べている. +木構造があった場合, rootNodeというTreeに定義されているレコード構文のアクセサ関数を使って, (TVar Node)を取得する. +最後に, (TVar Node)に対して, readTVarを行うことで最新のルートノードが取得できる. -木構造を編集する関数は全て Node を受け取って Node を返す。 -その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。 -updateRootNode は、データベースと木の名前、変更して返ってきた木構造の 3 つを渡す。 -updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。 +木構造を編集する関数は全て Node を受け取って Node を返す. +その返ってきた Node をルートノードとして登録することで, 木構造の最新のルートノードが更新される. +updateRootNode は, データベースと木の名前, 変更して返ってきた木構造の 3 つを渡す. +updateRootNodeをした後は, getRootNodeで取得できるルートノードが更新された状態になっている. \begin{lstlisting}[caption=ルートノードの更新] updateRootNode :: Jungle -> String -> Node -> IO () @@ -239,9 +239,9 @@ Just x -> rootNode x \end{lstlisting} -updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。 -ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。(Node $->$ Node) がそれにあたる。 -このupdateRootNodeWithを利用することで、getRootNodeをした後に編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。 +updateRootNodeWithは, ノードを更新する関数とデータベース, 木の名前を渡して利用する. +ノードを更新する関数とは, ノードを受け取ってノードを返す関数である. (Node $->$ Node) がそれにあたる. +このupdateRootNodeWithを利用することで, getRootNodeをした後に編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される. \begin{lstlisting}[caption=ルートノードの更新] updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO () @@ -255,16 +255,16 @@ Just x -> rootNode x \end{lstlisting} -並列データベース Jungle で他のスレッドと状態を共有する操作は、 -createJungle、createTree、getRootNode、updateRootNode、updateRootNodeWith -で全てである。 -並列データベース Jungle では、なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する。 -ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの、読み込みに関してはロックなしで高速に読み込める。 +並列データベース Jungle で他のスレッドと状態を共有する操作は, +createJungle, createTree, getRootNode, updateRootNode, updateRootNodeWith +で全てである. +並列データベース Jungle では, なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する. +ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの, 読み込みに関してはロックなしで高速に読み込める. \subsection{Node} -Node は木構造を表現するデータ構造である。 -再帰的に定義されている。 -各ノードは children として子ノードを複数持つことができる（図\ref{fig:node_components}）。 +Node は木構造を表現するデータ構造である. +再帰的に定義されている. +各ノードは children として子ノードを複数持つことができる（図\ref{fig:node_components}）. \begin{figure}[!htbp] \begin{center} @@ -274,7 +274,7 @@ \label{fig:node_components} \end{figure} -children および attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。 +children および attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）. \begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義] data Node = Node @@ -283,14 +283,14 @@ \end{lstlisting} \subsubsection{木の編集} -木の編集には、Node を使う。 -木の編集に用いる関数は全て Node を受け取って Node を返す。 -非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。 -これらの編集のための関数は、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。 +木の編集には, Node を使う. +木の編集に用いる関数は全て Node を受け取って Node を返す. +非破壊的木構造を利用しているため, getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照, 編集できる. +これらの編集のための関数は, 編集後updateRootNodeするか, ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる. -編集対象のノードを指定するには、NodePath を利用する。 -NodePath は、ルートノードからスタートし、ノードの子どもの場所を次々に指定したものである。 -Haskell の基本データ構造であるリストを利用している。 +編集対象のノードを指定するには, NodePath を利用する. +NodePath は, ルートノードからスタートし, ノードの子どもの場所を次々に指定したものである. +Haskell の基本データ構造であるリストを利用している. \begin{figure}[!htbp] \begin{center} @@ -300,7 +300,7 @@ \label{fig:nodepath} \end{figure} -木の編集を行う関数を紹介する。 +木の編集を行う関数を紹介する. \begin{lstlisting}[caption=木の編集を行う関数] addNewChildAt :: Node -> Path -> Node @@ -309,22 +309,22 @@ deleteAttribute :: Node -> Path -> String -> Node \end{lstlisting} -addNewChildAt で、ノードに新しい子を追加できる。 -Node と NodePath を渡す必要がある。 -子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 +addNewChildAt で, ノードに新しい子を追加できる. +Node と NodePath を渡す必要がある. +子には Position という場所の情報があるが, インクリメントしながら自動的に指定される. -deleteChildAt で、ノードの子を削除できる。 -Node と NodePath、削除したい子のPositionを指定する。 +deleteChildAt で, ノードの子を削除できる. +Node と NodePath, 削除したい子のPositionを指定する. -putAttribute で、ノードに属性を追加できる。 -Node と NodePath、キー、値を渡す。 -キーは String、値は、ByteString である。 +putAttribute で, ノードに属性を追加できる. +Node と NodePath, キー, 値を渡す. +キーは String, 値は, ByteString である. -deleteAttribute で、ノードの属性を削除できる。 -Node と NodePath、キーを渡す。 +deleteAttribute で, ノードの属性を削除できる. +Node と NodePath, キーを渡す. -これらの関数は、ほぼ同一の関数で定義できる。 -addNewChildAtを用いて説明する。 +これらの関数は, ほぼ同一の関数で定義できる. +addNewChildAtを用いて説明する. \begin{lstlisting}[caption=木の編集を行う関数] addNewChildAt :: Node -> Path -> Node @@ -351,21 +351,21 @@ attr = attributes node \end{lstlisting} -非破壊的木構造の編集は再帰で定義できる。 -左結合となる\$を使い、対象のノードに到達するまで、addChildを繰り返す。 -addChildは、引数として子となるノードが必要である。 -そのため、下の階層から徐々に上に作られていく。 +非破壊的木構造の編集は再帰で定義できる. +左結合となる\$を使い, 対象のノードに到達するまで, addChildを繰り返す. +addChildは, 引数として子となるノードが必要である. +そのため, 下の階層から徐々に上に作られていく. -addNewChildAt、deleteChildAt、putAttribute、deleteAttributeといった、 -非破壊的木構造の編集は、対象のノードに対する操作以外は全て同じである。 -Pathのリストが空になる、すなわち対象のノードに到達した時の操作だけが異なる。 -新しい子を追加するのが addNewChildAt、指定されたポジションの子を削除するのが deleteChildAt、 -指定されたキーと値を追加するのが putAttribute、指定されたキーの値を削除するのが deleteAttributeである。 +addNewChildAt, deleteChildAt, putAttribute, deleteAttributeといった, +非破壊的木構造の編集は, 対象のノードに対する操作以外は全て同じである. +Pathのリストが空になる, すなわち対象のノードに到達した時の操作だけが異なる. +新しい子を追加するのが addNewChildAt, 指定されたポジションの子を削除するのが deleteChildAt, +指定されたキーと値を追加するのが putAttribute, 指定されたキーの値を削除するのが deleteAttributeである. \subsubsection{木の参照} -木の参照にも Node を用いる。 -様々な参照の関数があるため、ひとつずつ紹介していく。 +木の参照にも Node を用いる. +様々な参照の関数があるため, ひとつずつ紹介していく. \begin{lstlisting}[caption=属性の取得] getAttributes :: Node -> Path -> String -> Maybe ByteString @@ -406,34 +406,34 @@ pos = size map \end{lstlisting} -elems、assocs、sizeなどはData.Mapの関数である。 +elems, assocs, sizeなどはData.Mapの関数である. -getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 +getAttributes は, 対象の Path に存在する属性を Key を用いて参照できる. -getChildren は、対象の Node が持つ全ての子を Node のリストとして返す。 -あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 +getChildren は, 対象の Node が持つ全ての子を Node のリストとして返す. +あるNodeに存在する全ての子に対して, 参照を行いたい場合に利用する. -assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 -あるNodeに存在する全ての子に対して、子のPositionを取得しながら参照を行いたい場合に利用する。 +assocsChildren は, 対象の Node が持つ全ての子を Position とのタプルにし, そのタプルのリストを返す. +あるNodeに存在する全ての子に対して, 子のPositionを取得しながら参照を行いたい場合に利用する. -assocsAttribute は、対象の Node が持つ全ての属性を、キーと値のペアとし、そのペアのリストを返す。 -あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。 +assocsAttribute は, 対象の Node が持つ全ての属性を, キーと値のペアとし, そのペアのリストを返す. +あるNodeに存在する全ての属性に対して, 参照を行いたい場合に利用する. -numOfChild では、対象の Node が持つ子どもの数を取得できる。 +numOfChild では, 対象の Node が持つ子どもの数を取得できる. -currentChild では、対象の Node が持つ最新の子を取得できる。 +currentChild では, 対象の Node が持つ最新の子を取得できる. \subsubsection{並列実行} -木構造データベース Jungle は、並列に実行することができる。 -アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。 -利用方法も、シングルスレッドで実行する場合と同じである。 +木構造データベース Jungle は, 並列に実行することができる. +アプリケーション側で, データベースを参照や変更する際に各スレッドから呼び出しても問題ない. +利用方法も, シングルスレッドで実行する場合と同じである. \section{Haskell の生産性} -Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。 +Java を用いた Jungle の実装と比較して, コード行数が約 3000 行から約 300 行へと短くなった. -Haskell では、独自のデータ型を作成することができる。 -再帰的なデータ構造の定義も容易である。 -また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。 +Haskell では, 独自のデータ型を作成することができる. +再帰的なデータ構造の定義も容易である. +また, Haskellは参照透過性を持つため, コードの再利用が行い易く, 関数同士の結合も簡単である. -同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。 +同じような機能を実装する場合でも, Java と比較してコード行数が短くなり生産性が向上する.
--- a/paper/chapter4.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/chapter4.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,15 +1,15 @@ \chapter{性能評価}\label{ch:bench} -本章では、非破壊的木構造データベース Jungle がマルチコアプロセッサで性能向上を果たせるのか確認する。 -また、実用的なWebサービスが提供できるのか確認するために Web 掲示板サービスを開発し、Java との比較を行う。 +本章では, 非破壊的木構造データベース Jungle がマルチコアプロセッサで性能向上を果たせるのか確認する. +また, 実用的なWebサービスが提供できるのか確認するために Web 掲示板サービスを開発し, Java との比較を行う. \section{計測環境} -マルチコアプロセッサでの性能を確認するためコア数の多いサーバを用いる。 -本研究では、学科が提供するブレードサーバを用いて、計測環境を構築する。 -ブレードサーバの仕様を表\ref{tab:server_spec}に示す。 +マルチコアプロセッサでの性能を確認するためコア数の多いサーバを用いる. +本研究では, 学科が提供するブレードサーバを用いて, 計測環境を構築する. +ブレードサーバの仕様を表\ref{tab:server_spec}に示す. -論理コアは、Intel のハイパースレッディング機能のことである。 -ハイパースレッディングは、１つのプロセッサをあたかも２つのプロセッサであるかのように扱う技術であり、 -同時に演算器などを利用することはできないため性能が２倍になるわけではないが、概ね20 \%程度クロックあたりの性能が向上すると言われている。 +論理コアは, Intel のハイパースレッディング機能のことである. +ハイパースレッディングは, １つのプロセッサをあたかも２つのプロセッサであるかのように扱う技術であり, +同時に演算器などを利用することはできないため性能が２倍になるわけではないが, 概ね20 \%程度クロックあたりの性能が向上すると言われている. \begin{table}[!htbp] \begin{center} @@ -26,16 +26,16 @@ \label{tab:server_spec} \end{table} -非破壊的木構造データベース Jungle の並列読み込みと並列書き込みの性能の計測には１台、 -Web 掲示板 サービスを用いた Java との性能比較には２台のブレードサーバを利用する。 -2 台使用するのは、サーバと負荷をかけるクライアントを別々に実行するためである。 +非破壊的木構造データベース Jungle の並列読み込みと並列書き込みの性能の計測には１台, +Web 掲示板 サービスを用いた Java との性能比較には２台のブレードサーバを利用する. +2 台使用するのは, サーバと負荷をかけるクライアントを別々に実行するためである. \subsubsection{Haskell および Java のバージョン} -Haskell のコンパイラには The Glasgow Haskell Compiler（GHC）を使用する。 -GHC は、Haskell で最も広く使われているコンパイラである\cite{ghc}。 -ソフトウェア・トランザクショナル・メモリをサポートするなど、並列プログラミングのためのHaskellの拡張が行われている。 +Haskell のコンパイラには The Glasgow Haskell Compiler（GHC）を使用する. +GHC は, Haskell で最も広く使われているコンパイラである\cite{ghc}. +ソフトウェア・トランザクショナル・メモリをサポートするなど, 並列プログラミングのためのHaskellの拡張が行われている. -Haskell および Java のバージョンを表\ref{tab:compiler}に示す。 +Haskell および Java のバージョンを表\ref{tab:compiler}に示す. \begin{table}[!ht] \begin{center} @@ -49,28 +49,28 @@ \label{tab:compiler} \end{table} -計測環境の構築方法については付録に記載する。 +計測環境の構築方法については付録に記載する. \section{読み込みの性能計測} -非破壊的木構造データベース Jungle を用いて、マルチコアプロセッサ上で並列に読み込みを行い、線形に性能向上ができるか調査する。 +非破壊的木構造データベース Jungle を用いて, マルチコアプロセッサ上で並列に読み込みを行い, 線形に性能向上ができるか調査する. \subsubsection{計測方法} -ブレードサーバ上で、Jungle で作成した木構造を並列に読み込んで性能計測を行う。 -まず、Jungle を利用して木構造を作成する。 -並列に実行する際に、読み込みに負荷がかかるように木構造はある程度の大きさとする。 -今回は木の深さが 8、ノードの数が約 80 万の大きさの木構造を使用する。 +ブレードサーバ上で, Jungle で作成した木構造を並列に読み込んで性能計測を行う. +まず, Jungle を利用して木構造を作成する. +並列に実行する際に, 読み込みに負荷がかかるように木構造はある程度の大きさとする. +今回は木の深さが 8, ノードの数が約 80 万の大きさの木構造を使用する. -木構造を読み込み、ノードの数を数えるタスクを 1,000 個作成し並列実行する。 -非破壊的木構造は、木構造に変更を加えても他の読み込みのタスクに影響を与えない。 -そのことを確認するために、木構造は各タスクに渡す前に無作為にノードを追加する。 +木構造を読み込み, ノードの数を数えるタスクを 1,000 個作成し並列実行する. +非破壊的木構造は, 木構造に変更を加えても他の読み込みのタスクに影響を与えない. +そのことを確認するために, 木構造は各タスクに渡す前に無作為にノードを追加する. \subsubsection{計測結果} -非破壊的木構造データベース Jungle の読み込みの計測結果を表\ref{tab:par_read}に示す。 +非破壊的木構造データベース Jungle の読み込みの計測結果を表\ref{tab:par_read}に示す. -CPUコア数を増やしていくと、実行時間が短くなっていることが分かる。 -シングルスレッドで実行した場合と比較して、2 スレッドで 1.79 倍、12 スレッドで 10.77 倍の性能向上が見られる。 -実際の計測では、13 スレッド以上は、12スレッドより速くなることもあるが、遅くなる場合もあるなど安定しない結果となっている。 +CPUコア数を増やしていくと, 実行時間が短くなっていることが分かる. +シングルスレッドで実行した場合と比較して, 2 スレッドで 1.79 倍, 12 スレッドで 10.77 倍の性能向上が見られる. +実際の計測では, 13 スレッド以上は, 12スレッドより速くなることもあるが, 遅くなる場合もあるなど安定しない結果となっている. \begin{table}[!htbp] \begin{center} @@ -90,9 +90,9 @@ \label{tab:par_read} \end{table} -性能向上率のグラフを図\ref{fig:benchmark_read}に示す。 -線形に近い形で性能が向上していることが分かる。 -非破壊的木構造データベース Jungle は読み込みにおいてスケールするデータベースであることが分かる。 +性能向上率のグラフを図\ref{fig:benchmark_read}に示す. +線形に近い形で性能が向上していることが分かる. +非破壊的木構造データベース Jungle は読み込みにおいてスケールするデータベースであることが分かる. \begin{figure}[!htbp] \begin{center} @@ -104,22 +104,22 @@ \clearpage \section{書き込みの性能計測} -非破壊的木構造データベース Jungle を用いて、マルチコアプロセッサ上で並列に書き込みを行い、線形に性能向上ができるか調査する。 +非破壊的木構造データベース Jungle を用いて, マルチコアプロセッサ上で並列に書き込みを行い, 線形に性能向上ができるか調査する. \subsubsection{計測方法} -ブレードサーバ上で、Jungle に木構造を並列に書き込んで性能計測を行う。 -木の深さが 6、ノードの数が約 1 万の大きさの木構造を作成しJungle に登録するタスクを 1,000 個作成し、並列に実行する。 -書き込んだ木構造はノードの数が整合しているかどうか確認する。その後正確に書き込まれてるタスクの数を出力する。 -Haskell は遅延評価のため、出力などを挟むことで評価が行われるようにしなければならない。 +ブレードサーバ上で, Jungle に木構造を並列に書き込んで性能計測を行う. +木の深さが 6, ノードの数が約 1 万の大きさの木構造を作成しJungle に登録するタスクを 1,000 個作成し, 並列に実行する. +書き込んだ木構造はノードの数が整合しているかどうか確認する. その後正確に書き込まれてるタスクの数を出力する. +Haskell は遅延評価のため, 出力などを挟むことで評価が行われるようにしなければならない. \subsubsection{計測結果} -非破壊的木構造データベース Jungle の書き込みの計測結果を表\ref{tab:par_write}に示す。 +非破壊的木構造データベース Jungle の書き込みの計測結果を表\ref{tab:par_write}に示す. -CPUコア数を増やしていくと、実行時間が短くなっていることが分かる。 -シングルスレッドで実行した場合と比較して、2 スレッドで 1.55 倍、12 スレッドで 3.86 倍の性能向上が見られる。 -読み込みと比べ、書き込みはJungleへの登録作業があるため並列化率が下がり、性能向上率が低いことが分かる。 +CPUコア数を増やしていくと, 実行時間が短くなっていることが分かる. +シングルスレッドで実行した場合と比較して, 2 スレッドで 1.55 倍, 12 スレッドで 3.86 倍の性能向上が見られる. +読み込みと比べ, 書き込みはJungleへの登録作業があるため並列化率が下がり, 性能向上率が低いことが分かる. -ハイパースレッディングは効果がなく、13 スレッド以上では実行時間が遅くなっている。 +ハイパースレッディングは効果がなく, 13 スレッド以上では実行時間が遅くなっている. \begin{table}[!htbp] @@ -140,8 +140,8 @@ \label{tab:par_write} \end{table} -性能向上率のグラフを図\ref{fig:benchmark_write}に示す。 -書き込みは性能向上率が低いことが分かる。 +性能向上率のグラフを図\ref{fig:benchmark_write}に示す. +書き込みは性能向上率が低いことが分かる. \newpage \begin{figure}[!htbp] @@ -152,29 +152,29 @@ \label{fig:benchmark_write} \end{figure} -Jungle へ木の登録する際に他のスレッドから登録があった場合、ソフトウェア・トランザクショナル・メモリが処理をやり直すため、並列度が下がっていると思われる。 -また、GHC の問題も考えられる。 -GHC の IO マネージャーは、マルチスレッドでうまくスケールしないという問題があり、並列度が下がってしまう。 -GHCの次期バージョンではIO マネージャーが改善され、スケールするようになる見込みである\cite{iomanager}。 +Jungle へ木の登録する際に他のスレッドから登録があった場合, ソフトウェア・トランザクショナル・メモリが処理をやり直すため, 並列度が下がっていると思われる. +また, GHC の問題も考えられる. +GHC の IO マネージャーは, マルチスレッドでうまくスケールしないという問題があり, 並列度が下がってしまう. +GHCの次期バージョンではIO マネージャーが改善され, スケールするようになる見込みである\cite{iomanager}. -非破壊的木構造データベース Jungle は、書き込みは並列化率が低くなってしまっている。 -読み込みが高速なため、書き込みより読み込みが多用されるシステムに向いているといえる。 +非破壊的木構造データベース Jungle は, 書き込みは並列化率が低くなってしまっている. +読み込みが高速なため, 書き込みより読み込みが多用されるシステムに向いているといえる. \clearpage \section{Web サービスに組み込んでの性能評価} -並列データベース Jungle が実用的なWeb サービスを提供できるのか調査する。 -Web掲示板サービスに組み込んで、性能測定を行った。 +並列データベース Jungle が実用的なWeb サービスを提供できるのか調査する. +Web掲示板サービスに組み込んで, 性能測定を行った. \subsection{Web 掲示板サービスの実装} -木構造データベース Jungle と Haskell の HTTP サーバ Warp\cite{warp} を用いて Web 掲示板サービスを開発する。 -Warp を用いたWeb サービスの構築法については付録に記載する。 -Warp は、ハイパースレッディングの効果がなくハイパースレッディング利用時に遅くなるため、12 スレッドまでの計測とする。 +木構造データベース Jungle と Haskell の HTTP サーバ Warp\cite{warp} を用いて Web 掲示板サービスを開発する. +Warp を用いたWeb サービスの構築法については付録に記載する. +Warp は, ハイパースレッディングの効果がなくハイパースレッディング利用時に遅くなるため, 12 スレッドまでの計測とする. -Warp は並列に実行可能であり、並列に実行している Warp に対して、Jungle を繋げるだけで Jungle を並列に動かすことができる。 -掲示板におけるデータベースへの書き込みは、板の作成と、板への書き込みがある。 -Jungle において、板の作成は新しい木構造の作成、板への書き込みは木構造へのノードの追加で表現する。 -掲示板へ実装した機能を表\ref{tab:bbs_func}に示す。 +Warp は並列に実行可能であり, 並列に実行している Warp に対して, Jungle を繋げるだけで Jungle を並列に動かすことができる. +掲示板におけるデータベースへの書き込みは, 板の作成と, 板への書き込みがある. +Jungle において, 板の作成は新しい木構造の作成, 板への書き込みは木構造へのノードの追加で表現する. +掲示板へ実装した機能を表\ref{tab:bbs_func}に示す. \begin{table}[!htbp] \begin{center} @@ -202,24 +202,24 @@ \subsection{読み込み} \subsubsection{計測方法} -掲示板に対して読み込みを行い、負荷をかける。 -掲示板を立ち上げるサーバと、性能測定ツール weighttp\cite{weighttp} を用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。 +掲示板に対して読み込みを行い, 負荷をかける. +掲示板を立ち上げるサーバと, 性能測定ツール weighttp\cite{weighttp} を用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った. -weighttpの設定は、リクエストの総数 100 万、同時に接続するコネクションの数 1,000、実行時のスレッド数 10、HTTP Keep-Alivesを有効とする。 +weighttpの設定は, リクエストの総数 100 万, 同時に接続するコネクションの数 1,000, 実行時のスレッド数 10, HTTP Keep-Alivesを有効とする. \subsubsection{計測結果} -掲示板の読み込みの計測結果を表\ref{tab:bbs_read}に示す。 +掲示板の読み込みの計測結果を表\ref{tab:bbs_read}に示す. -並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。 -シングルスレッドで実行した場合と比較して、12 スレッドで 2.14 倍の性能向上が見られる。 -これは HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる。 +並列で実行した場合, 実行時間が短くなっているが性能向上率が低いことが分かる. +シングルスレッドで実行した場合と比較して, 12 スレッドで 2.14 倍の性能向上が見られる. +これは HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる. -Warp のボトルネックがどれぐらいあるのか調査するために、アクセスした際に "hello, world" という文字列を返すだけのプログラムを作成し測定する。 -結果を表\ref{tab:warp}に示す。 -1 スレッドで実行した場合は、Jungle と組み合わせた掲示板より速い。 -しかしながら、スレッド数が増えていくと掲示板の読み込みとあまり結果が変わらなくなってしまう。 -Warp は現状あまり並列化効果がでていない。 +Warp のボトルネックがどれぐらいあるのか調査するために, アクセスした際に "hello, world" という文字列を返すだけのプログラムを作成し測定する. +結果を表\ref{tab:warp}に示す. +1 スレッドで実行した場合は, Jungle と組み合わせた掲示板より速い. +しかしながら, スレッド数が増えていくと掲示板の読み込みとあまり結果が変わらなくなってしまう. +Warp は現状あまり並列化効果がでていない. \begin{table}[!htbp] \begin{center} @@ -251,22 +251,22 @@ \label{tab:warp} \end{table} -Web サービスを用いて実験する場合、データベースだけがボトルネックとなるように負荷をかけるのは難しい。 -ただ単にデータを大きくするだけでは、文字列をHTMLに変換するコストが大きくなってしまうためである。 +Web サービスを用いて実験する場合, データベースだけがボトルネックとなるように負荷をかけるのは難しい. +ただ単にデータを大きくするだけでは, 文字列をHTMLに変換するコストが大きくなってしまうためである. \subsection{書き込み} \subsubsection{計測方法} -掲示板に対して書き込みを行い、負荷をかける。 -掲示板を立ち上げるサーバと、weighttpを用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。 +掲示板に対して書き込みを行い, 負荷をかける. +掲示板を立ち上げるサーバと, weighttpを用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った. -weighttpでは、GET しかできないためURLのクエリ文字列でデータを書き込めるようにWeb掲示板サービスを変更した。 -weighttp起動時のオプションは、読み込みと同じである。 +weighttpでは, GET しかできないためURLのクエリ文字列でデータを書き込めるようにWeb掲示板サービスを変更した. +weighttp起動時のオプションは, 読み込みと同じである. \subsubsection{計測結果} -掲示板の書き込みの計測結果を表\ref{tab:bbs_write}に示す。 -並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。 -シングルスレッドで実行した場合と比較して、12 スレッドで 1.65 倍の性能向上が見られる。 -読み込みに比べて、書き込みのほうが全体的に遅くなっている。 +掲示板の書き込みの計測結果を表\ref{tab:bbs_write}に示す. +並列で実行した場合, 実行時間が短くなっているが性能向上率が低いことが分かる. +シングルスレッドで実行した場合と比較して, 12 スレッドで 1.65 倍の性能向上が見られる. +読み込みに比べて, 書き込みのほうが全体的に遅くなっている. \begin{table}[!htbp] \begin{center} @@ -285,14 +285,14 @@ \end{table} \subsection{Javaを用いた非破壊的木構造データベースとの比較} -非破壊的木構造データベースは、Haskell 版と Java 版の2つ存在する。 -Web 掲示板サービスを両方の言語で実装し、比較を行う。 -Haskell ではフロントエンドとして Warp を利用したが、Java では Jetty を利用する。 -Jetty のバージョンは 6.1.26 を用いる。 +非破壊的木構造データベースは, Haskell 版と Java 版の2つ存在する. +Web 掲示板サービスを両方の言語で実装し, 比較を行う. +Haskell ではフロントエンドとして Warp を利用したが, Java では Jetty を利用する. +Jetty のバージョンは 6.1.26 を用いる. -Haskell 版と Java 版の Web 掲示板サービスをブレードサーバ上で実行し、 -weightttpで負荷をかけ100万リクエストを処理するのにかかる時間を計測する。 -Haskell と Java の測定結果を表\ref{tab:compare}に示す。 +Haskell 版と Java 版の Web 掲示板サービスをブレードサーバ上で実行し, +weightttpで負荷をかけ100万リクエストを処理するのにかかる時間を計測する. +Haskell と Java の測定結果を表\ref{tab:compare}に示す. \begin{table}[!htbp] \begin{center} @@ -306,20 +306,20 @@ \label{tab:compare} \end{table} -Haskell 版は、Java 版と比較して読み込みで 1.87 倍、書き込みで 2.3 倍の性能差が出ている。 +Haskell 版は, Java 版と比較して読み込みで 1.87 倍, 書き込みで 2.3 倍の性能差が出ている. -書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる。 -Haskell では書き込みを行う際、完全に評価せず thunk として積み上げていく。 -thunkとは、未評価の式を追跡するのに使われるものである。 -遅延評価は、グラフ簡約があるため先行評価より簡約ステップ数が増えることはない。 -また、不要な計算が省かれるので簡約ステップ数が少なくなることもある。 -しかしながら、計算の所用領域が増えてしまうのが難点で、 -ハードウェアが効率的に利用できるメモリの範囲内に収まらなければ即時評価より実行時間が遅くなってしまうことがあるので注意が必要である。 -本実験では、潤沢にメモリを割り当てているためそういった問題は起きない。 +書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる. +Haskell では書き込みを行う際, 完全に評価せず thunk として積み上げていく. +thunkとは, 未評価の式を追跡するのに使われるものである. +遅延評価は, グラフ簡約があるため先行評価より簡約ステップ数が増えることはない. +また, 不要な計算が省かれるので簡約ステップ数が少なくなることもある. +しかしながら, 計算の所用領域が増えてしまうのが難点で, +ハードウェアが効率的に利用できるメモリの範囲内に収まらなければ即時評価より実行時間が遅くなってしまうことがあるので注意が必要である. +本実験では, 潤沢にメモリを割り当てているためそういった問題は起きない. \subsection{書き込みごとに読み込みを行った場合} -書き込みごとに毎回読み込みを挟むことで、遅延評価ではなく即時評価させる。 -計測結果を表\ref{tab:write_read}に示す。 +書き込みごとに毎回読み込みを挟むことで, 遅延評価ではなく即時評価させる. +計測結果を表\ref{tab:write_read}に示す. \begin{table}[!htbp] \begin{center} @@ -336,6 +336,6 @@ \label{tab:write_read} \end{table} -結果が明らかに遅くなっている。 -12 スレッドで実行した際、 Java との書き込みの性能差は、1.30 倍である。 -シングルスレッドで実行した場合と比較した場合、12 スレッドで 2.40 倍の性能向上が見られる。 +結果が明らかに遅くなっている. +12 スレッドで実行した際, Java との書き込みの性能差は, 1.30 倍である. +シングルスレッドで実行した場合と比較した場合, 12 スレッドで 2.40 倍の性能向上が見られる.
--- a/paper/conclusion.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/conclusion.tex Thu Feb 06 21:12:49 2014 +0900 @@ -2,33 +2,33 @@ \section{まとめ} % 並列環境で動くことを示せた -本研究では、関数型言語 Haskell を用いて並列データベースの実装をおこなった。 +本研究では, 関数型言語 Haskell を用いて並列データベースの実装をおこなった. -Haskell は、型推論と型安全により信頼性の高いプログラムを書くことができる。 -実装において、Haskellの表現力とコンパイル時に多くのエラーを捕まえるという特徴は、開発期間およびコード行数の短縮に繋がった。 -また、型安全により実行時に型エラーによってプログラムが終了するといったことがない。 +Haskell は, 型推論と型安全により信頼性の高いプログラムを書くことができる. +実装において, Haskellの表現力とコンパイル時に多くのエラーを捕まえるという特徴は, 開発期間およびコード行数の短縮に繋がった. +また, 型安全により実行時に型エラーによってプログラムが終了するといったことがない. -読み込みに関して 12 コアで実行した場合、1 コアで実行した場合と比較して、10.77 倍 という性能向上率が確認でき、マルチコアプロセッサの性能を引き出すことができた。 -また、Web 掲示板サービスを開発し、 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない、読み込みで 1.87 倍、書き込みで 2.3 倍の性能が確認できた。 +読み込みに関して 12 コアで実行した場合, 1 コアで実行した場合と比較して, 10.77 倍 という性能向上率が確認でき, マルチコアプロセッサの性能を引き出すことができた. +また, Web 掲示板サービスを開発し, 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 1.87 倍, 書き込みで 2.3 倍の性能が確認できた. \section{今後の課題} -非破壊的木構造データベース Jungle の今後の課題について述べる。 +非破壊的木構造データベース Jungle の今後の課題について述べる. \subsubsection{書き込み処理の性能向上率の上昇} -データベースへの書き込み処理において、12 スレッド時で 3.86 倍の性能向上しか達成できていない。 -はじめに、プログラムの変更をせずに、GHC の IO マネージャーの改善によりどの程度並列度が向上するのかを調査する必要がある。 -GHC の IO マネージャーの影響度を計測した後、変更処理の改善方法に調査する。 -現在ソフトウェア・トランザクショナル・メモリを用いているが、他のスレッドセーフな参照型を用いて性能改善が行えないか確認する。 -Haskell では、様々なスレッドセーフな参照型が用意されている。 -ロックが制限的だが、高速なIORef、ロックの使えるMVarなどである。 +データベースへの書き込み処理において, 12 スレッド時で 3.86 倍の性能向上しか達成できていない. +はじめに, プログラムの変更をせずに, GHC の IO マネージャーの改善によりどの程度並列度が向上するのかを調査する必要がある. +GHC の IO マネージャーの影響度を計測した後, 変更処理の改善方法に調査する. +現在ソフトウェア・トランザクショナル・メモリを用いているが, 他のスレッドセーフな参照型を用いて性能改善が行えないか確認する. +Haskell では, 様々なスレッドセーフな参照型が用意されている. +ロックが制限的だが, 高速なIORef, ロックの使えるMVarなどである. \subsubsection{分散データベースとしての実装} -現在、並列環境で実行できるが、今後は分散データベースとして実行できるようにしたい。 -トポロジーの形成機能や、サーバ間でのデータアクセスの仕組みを実装する必要がある。 -サーバ間で木構造の変更を共有するには、木構造を何らかの情報に基づいて、マージする仕組みを導入する必要がある。 +現在, 並列環境で実行できるが, 今後は分散データベースとして実行できるようにしたい. +トポロジーの形成機能や, サーバ間でのデータアクセスの仕組みを実装する必要がある. +サーバ間で木構造の変更を共有するには, 木構造を何らかの情報に基づいて, マージする仕組みを導入する必要がある. \subsubsection{永続性の実装} -非破壊的木構造データベース Jungle は、オンメモリ上で動作するデータベースである。 -並列性を損なわない形で、ディスクへの書き出しを実現したい。 -実装としては、書き出しを担当するスレッドを作成するといったことが考えられる。 +非破壊的木構造データベース Jungle は, オンメモリ上で動作するデータベースである. +並列性を損なわない形で, ディスクへの書き出しを実現したい. +実装としては, 書き出しを担当するスレッドを作成するといったことが考えられる.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/concurrent_edit.graffle Thu Feb 06 21:12:49 2014 +0900 @@ -0,0 +1,2135 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> +<plist version="1.0"> +<dict> + <key>ActiveLayerIndex</key> + <integer>0</integer> + <key>ApplicationVersion</key> + <array> + <string>com.omnigroup.OmniGrafflePro</string> + <string>139.17.0.185490</string> + </array> + <key>AutoAdjust</key> + <true/> + <key>BackgroundGraphic</key> + <dict> + <key>Bounds</key> + <string>{{0, 0}, {559, 783}}</string> + <key>Class</key> + <string>SolidGraphic</string> + <key>ID</key> + <integer>2</integer> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + </dict> + <key>BaseZoom</key> + <integer>0</integer> + <key>CanvasOrigin</key> + <string>{0, 0}</string> + <key>ColumnAlign</key> + <integer>1</integer> + <key>ColumnSpacing</key> + <real>36</real> + <key>CreationDate</key> + <string>2013-01-21 09:07:04 +0000</string> + <key>Creator</key> + <string>shoshi</string> + <key>DisplayScale</key> + <string>1 0/72 in = 1.0000 in</string> + <key>ExportShapes</key> + <array> + <dict> + <key>InspectorGroup</key> + <real>255</real> + <key>ShapeImageRect</key> + <string>{{2, 2}, {22, 22}}</string> + <key>ShapeName</key> + <string>7B2DAC72-B741-4CB4-A074-F89FBACDB271-12200-0000ED5F513B10D4</string> + <key>ShouldExport</key> + <string>YES</string> + <key>StrokePath</key> + <dict> + <key>elements</key> + <array> + <dict> + <key>element</key> + <string>MOVETO</string> + <key>point</key> + <string>{-0.46272600000000003, 0.5}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.46272600000000003, 0.5}</string> + <key>control2</key> + <string>{-0.45961800000000003, 0.36988399999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.42235400000000001, 0.35172700000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.39130199999999998, 0.34265000000000001}</string> + <key>control2</key> + <string>{-0.33851700000000001, 0.31541999999999998}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.32919799999999999, 0.309367}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.31987500000000002, 0.303313}</string> + <key>control2</key> + <string>{-0.31988499999999997, 0.27305299999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.31988499999999997, 0.27607900000000002}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.31988499999999997, 0.27910299999999999}</string> + <key>control2</key> + <string>{-0.38820500000000002, 0.34567599999999998}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.43477700000000002, 0.34567599999999998}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.33539999999999998, 0.26095000000000002}</string> + <key>control2</key> + <string>{-0.35093400000000002, 0.23371600000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.35093400000000002, 0.23371600000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.35093400000000002, 0.23371600000000001}</string> + <key>control2</key> + <string>{-0.43167699999999998, 0.297261}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.45031500000000002, 0.291209}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.36646899999999999, 0.215559}</string> + <key>control2</key> + <string>{-0.35403800000000002, 0.17924799999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.35403800000000002, 0.17924799999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.35403800000000002, 0.17924799999999999}</string> + <key>control2</key> + <string>{-0.45961800000000003, 0.23371600000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.5, 0.212533}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.40371800000000002, 0.18530099999999999}</string> + <key>control2</key> + <string>{-0.37887900000000002, -0.0325685}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.37887900000000002, -0.0325685}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.37887900000000002, -0.0325685}</string> + <key>control2</key> + <string>{-0.35714899999999999, -0.23228299999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.341615, -0.26859499999999997}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.33539999999999998, -0.30187900000000001}</string> + <key>control2</key> + <string>{-0.27328999999999998, -0.53487899999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.0031004000000000001, -0.49554199999999998}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.27949499999999999, -0.456204}</string> + <key>control2</key> + <string>{0.23912900000000001, -0.10519199999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.23912900000000001, -0.096113400000000002}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.23912900000000001, -0.087035699999999994}</string> + <key>control2</key> + <string>{0.24533199999999999, -0.099139900000000003}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.24533199999999999, -0.071906300000000006}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.24533199999999999, -0.044672999999999997}</string> + <key>control2</key> + <string>{0.23291100000000001, -0.0325685}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.23291100000000001, -0.0325685}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.23291100000000001, -0.0325685}</string> + <key>control2</key> + <string>{0.245337, -0.0023083700000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.245337, 0.049132099999999998}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.23601800000000001, 0.040054600000000003}</string> + <key>control2</key> + <string>{0.23291100000000001, 0.0249243}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.22670199999999999, 0.0340021}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.22360099999999999, 0.070313200000000006}</string> + <key>control2</key> + <string>{0.21428900000000001, 0.061235699999999997}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.19564999999999999, 0.130832}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.19253799999999999, 0.16714499999999999}</string> + <key>control2</key> + <string>{0.23601800000000001, 0.194378}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.25153999999999999, 0.194378}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.22048999999999999, 0.206482}</string> + <key>control2</key> + <string>{0.27017200000000002, 0.215559}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.27017200000000002, 0.215559}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.27017200000000002, 0.215559}</string> + <key>control2</key> + <string>{0.37575199999999997, 0.23068900000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.41302699999999998, 0.25489800000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.45029400000000003, 0.27910600000000002}</string> + <key>control2</key> + <string>{0.49689, 0.418298}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.49999199999999999, 0.493948}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.50309899999999996, 0.49999900000000003}</string> + <key>control2</key> + <string>{-0.46272600000000003, 0.5}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.46272600000000003, 0.5}</string> + </dict> + <dict> + <key>element</key> + <string>CLOSE</string> + </dict> + <dict> + <key>element</key> + <string>MOVETO</string> + <key>point</key> + <string>{-0.46272600000000003, 0.5}</string> + </dict> + </array> + </dict> + <key>TextBounds</key> + <string>{{0, 0}, {1, 1}}</string> + </dict> + <dict> + <key>InspectorGroup</key> + <real>255</real> + <key>ShapeImageRect</key> + <string>{{2, 2}, {22, 22}}</string> + <key>ShapeName</key> + <string>942FA1E8-AE78-4EC5-8961-54CCE45B0B1D-12200-0000EC2DD7328E8E</string> + <key>ShouldExport</key> + <string>YES</string> + <key>StrokePath</key> + <dict> + <key>elements</key> + <array> + <dict> + <key>element</key> + <string>MOVETO</string> + <key>point</key> + <string>{0.0091743499999999995, -0.49918099999999999}</string> + </dict> + <dict> + <key>element</key> + <string>LINETO</string> + <key>point</key> + <string>{0.0091743499999999995, -0.5}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.0061063799999999998, -0.500004}</string> + <key>control2</key> + <string>{0.0030479399999999999, -0.49993500000000002}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{4.7683700000000004e-06, -0.49979800000000002}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.00304127, -0.49993500000000002}</string> + <key>control2</key> + <string>{-0.0061025599999999999, -0.500004}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.0091743499999999995, -0.5}</string> + </dict> + <dict> + <key>element</key> + <string>LINETO</string> + <key>point</key> + <string>{-0.0091743499999999995, -0.49918099999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.067775699999999994, -0.49395299999999998}</string> + <key>control2</key> + <string>{-0.118363, -0.46512700000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.118363, -0.45407799999999998}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.13653100000000001, -0.43477199999999999}</string> + <key>control2</key> + <string>{-0.15471799999999999, -0.42954700000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.163799, -0.39275599999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.20923700000000001, -0.36822100000000002}</string> + <key>control2</key> + <string>{-0.191057, -0.22103999999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.191057, -0.22103999999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.191057, -0.22103999999999999}</string> + <key>control2</key> + <string>{-0.18196999999999999, -0.147449}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.191057, -0.147449}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.20014999999999999, -0.147449}</string> + <key>control2</key> + <string>{-0.20361099999999999, -0.14329}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.20642099999999999, -0.11810900000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.20642099999999999, -0.099533300000000005}</string> + <key>control2</key> + <string>{-0.19724800000000001, -0.0623825}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.19724800000000001, -0.0623825}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.19724800000000001, -0.0623825}</string> + <key>control2</key> + <string>{-0.18807199999999999, -0.0189216}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.18807199999999999, -0.0066552199999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.18807199999999999, 0.01192}</string> + <key>control2</key> + <string>{-0.18339, 0.0181119}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.17431099999999999, 0.0181119}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.16972400000000001, 0.0181119}</string> + <key>control2</key> + <string>{-0.15596199999999999, 0.01192}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.15471699999999999, 0.0119951}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.160549, 0.030495600000000001}</string> + <key>control2</key> + <string>{-0.12745999999999999, 0.12238}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.136546, 0.14691100000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.14562800000000001, 0.17144200000000001}</string> + <key>control2</key> + <string>{-0.17289199999999999, 0.208236}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.209231, 0.208236}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.24557499999999999, 0.208236}</string> + <key>control2</key> + <string>{-0.44547399999999998, 0.316023}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.46365099999999998, 0.34315200000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{-0.48182000000000003, 0.37027199999999999}</string> + <key>control2</key> + <string>{-0.5, 0.5}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{-0.5, 0.5}</string> + </dict> + <dict> + <key>element</key> + <string>LINETO</string> + <key>point</key> + <string>{1.52588e-05, 0.49343300000000001}</string> + </dict> + <dict> + <key>element</key> + <string>LINETO</string> + <key>point</key> + <string>{0.5, 0.5}</string> + </dict> + <dict> + <key>element</key> + <string>LINETO</string> + <key>point</key> + <string>{0.5, 0.49999900000000003}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.49995699999999998, 0.49968699999999999}</string> + <key>control2</key> + <string>{0.481798, 0.37023899999999998}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.46365200000000001, 0.34315200000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.44547599999999998, 0.316023}</string> + <key>control2</key> + <string>{0.24557599999999999, 0.208236}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.209232, 0.208236}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.17289299999999999, 0.208236}</string> + <key>control2</key> + <string>{0.14562900000000001, 0.17144200000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.136547, 0.14691100000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.12745999999999999, 0.12238}</string> + <key>control2</key> + <string>{0.16055, 0.030495399999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.15471799999999999, 0.0119948}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.15596299999999999, 0.01192}</string> + <key>control2</key> + <string>{0.16972400000000001, 0.018111700000000001}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.17431199999999999, 0.018111700000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.183391, 0.018111700000000001}</string> + <key>control2</key> + <string>{0.18807299999999999, 0.01192}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.18807299999999999, -0.0066554500000000003}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.18807299999999999, -0.0189216}</string> + <key>control2</key> + <string>{0.19724800000000001, -0.0623825}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.19724800000000001, -0.0623825}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.19724800000000001, -0.0623825}</string> + <key>control2</key> + <string>{0.20642199999999999, -0.0995336}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.20642199999999999, -0.11810900000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.20361199999999999, -0.14329}</string> + <key>control2</key> + <string>{0.20014999999999999, -0.147449}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.19105800000000001, -0.147449}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.18197099999999999, -0.147449}</string> + <key>control2</key> + <string>{0.19105800000000001, -0.22104099999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.19105800000000001, -0.22104099999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.19105800000000001, -0.22104099999999999}</string> + <key>control2</key> + <string>{0.20923800000000001, -0.36822100000000002}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.163799, -0.39275599999999999}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.154719, -0.42954700000000001}</string> + <key>control2</key> + <string>{0.13653199999999999, -0.43477199999999999}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.118364, -0.45407900000000001}</string> + </dict> + <dict> + <key>control1</key> + <string>{0.118364, -0.46512700000000001}</string> + <key>control2</key> + <string>{0.067776699999999995, -0.49395299999999998}</string> + <key>element</key> + <string>CURVETO</string> + <key>point</key> + <string>{0.0091743499999999995, -0.49918099999999999}</string> + </dict> + <dict> + <key>element</key> + <string>CLOSE</string> + </dict> + <dict> + <key>element</key> + <string>MOVETO</string> + <key>point</key> + <string>{0.0091743499999999995, -0.49918099999999999}</string> + </dict> + </array> + </dict> + <key>TextBounds</key> + <string>{{0, 0}, {1, 1}}</string> + </dict> + </array> + <key>GraphDocumentVersion</key> + <integer>8</integer> + <key>GraphicsList</key> + <array> + <dict> + <key>Bounds</key> + <string>{{54, 370.5}, {308, 21}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>3036</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Pad</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 \'96\'d8\'8d\'5c\'91\'a2\'82\'f0\'93\'c7\'82\'dd\'8d\'9e\'82\'f1\'82\'c5\'82\'a2\'82\'e9\'8a\'d4\'82\'c9\'91\'bc\'82\'cc\'90\'6c\'82\'aa\'95\'d2\'8f\'57\'82\'c5\'82\'ab\'82\'e9}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{72, 47.913749694824219}, {112, 21}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>3035</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Pad</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 \'96\'d8\'8d\'5c\'91\'a2\'82\'f0\'93\'c7\'82\'dd\'8d\'9e\'82\'de}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{256, 47.913749694824219}, {112, 21}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>3034</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Pad</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 \'96\'d8\'8d\'5c\'91\'a2\'82\'f0\'8d\'58\'90\'56\'82\'b7\'82\'e9}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>3033</integer> + <key>Points</key> + <array> + <string>{311.5, 106.76429595947263}</string> + <string>{311.5, 76.364295959472656}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>FilledArrow</string> + <key>Width</key> + <real>4</real> + </dict> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>ID</key> + <integer>3031</integer> + <key>Points</key> + <array> + <string>{127.5, 106.76429748535156}</string> + <string>{127.5, 76.364297485351585}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>FilledArrow</string> + <key>Width</key> + <real>4</real> + </dict> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{377, 76.364297546386695}, {97.102099999999993, 71.936800000000005}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3027</integer> + <key>Shape</key> + <string>942FA1E8-AE78-4EC5-8961-54CCE45B0B1D-12200-0000EC2DD7328E8E</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0.4</string> + <key>g</key> + <string>0.4</string> + <key>r</key> + <string>0.4</string> + </dict> + <key>FillType</key> + <integer>2</integer> + <key>GradientAngle</key> + <real>70</real> + <key>GradientColor</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>MiddleColor</key> + <dict> + <key>b</key> + <string>0.8</string> + <key>g</key> + <string>0.2</string> + <key>r</key> + <string>0.2</string> + </dict> + <key>MiddleFraction</key> + <real>0.18253970146179199</real> + <key>TrippleBlend</key> + <string>YES</string> + </dict> + <key>shadow</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0.425743</string> + <key>g</key> + <string>0.425743</string> + <key>r</key> + <string>0.425743</string> + </dict> + <key>Draws</key> + <string>NO</string> + <key>ShadowVector</key> + <string>{0, -5}</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{4.3960967163085911, 74.750543212890648}, {72.603899999999996, 75.164299999999997}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3012</integer> + <key>Shape</key> + <string>7B2DAC72-B741-4CB4-A074-F89FBACDB271-12200-0000ED5F513B10D4</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0.4</string> + <key>g</key> + <string>0.4</string> + <key>r</key> + <string>0.4</string> + </dict> + <key>FillType</key> + <integer>2</integer> + <key>GradientAngle</key> + <real>70</real> + <key>GradientColor</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>MiddleColor</key> + <dict> + <key>b</key> + <string>0.6</string> + <key>g</key> + <string>0.8</string> + <key>r</key> + <string>1</string> + </dict> + <key>MiddleFraction</key> + <real>0.18253970146179199</real> + <key>TrippleBlend</key> + <string>YES</string> + </dict> + <key>shadow</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0.425743</string> + <key>g</key> + <string>0.425743</string> + <key>r</key> + <string>0.425743</string> + </dict> + <key>Draws</key> + <string>NO</string> + <key>ShadowVector</key> + <string>{0, -5}</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>41</integer> + </dict> + <key>ID</key> + <integer>50</integer> + <key>Points</key> + <array> + <string>{321.71411767104161, 166.30247471367076}</string> + <string>{331.28588232895839, 193.69752528632924}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>40</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>33</integer> + </dict> + <key>ID</key> + <integer>46</integer> + <key>Points</key> + <array> + <string>{324.00502986417524, 245.40817832666872}</string> + <string>{298.99497013582476, 280.59182167333125}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>41</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>40</integer> + </dict> + <key>ID</key> + <integer>43</integer> + <key>Points</key> + <array> + <string>{117.79280840805944, 211.76907682786847}</string> + <string>{284.8037492251284, 148.76040370142883}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{314, 194}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>41</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>GapRatio</key> + <real>0.5</real> + <key>Width</key> + <real>4</real> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 B}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{285, 111}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>40</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>GapRatio</key> + <real>0.5</real> + <key>Width</key> + <real>4</real> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 1}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + <key>ID</key> + <integer>37</integer> + <key>Points</key> + <array> + <string>{195.54113276587935, 154.36004672212511}</string> + <string>{115.20030398453299, 206.45605288502941}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>31</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>33</integer> + </dict> + <key>ID</key> + <integer>35</integer> + <key>Points</key> + <array> + <string>{266.18487404934751, 249.80602275399343}</string> + <string>{273.81512595065249, 276.19397724600651}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>32</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>32</integer> + </dict> + <key>ID</key> + <integer>34</integer> + <key>Points</key> + <array> + <string>{232.24639300736237, 165.24870051608096}</string> + <string>{245.75360699263763, 194.75129948391904}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>31</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{255, 277}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>33</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>GapRatio</key> + <real>0.5</real> + <key>Width</key> + <real>4</real> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;\red255\green0\blue0;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf2 A}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{231, 194}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>32</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>GapRatio</key> + <real>0.5</real> + <key>Width</key> + <real>4</real> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;\red255\green0\blue0;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf2 3}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{193, 111}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>31</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>1</string> + </dict> + <key>GapRatio</key> + <real>0.5</real> + <key>Width</key> + <real>4</real> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;\red255\green0\blue0;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf2 1}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>22</integer> + </dict> + <key>ID</key> + <integer>27</integer> + <key>Points</key> + <array> + <string>{185.32166410581175, 247.46054911461746}</string> + <string>{197.67833589418819, 278.53945088538251}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>19</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>19</integer> + </dict> + <key>ID</key> + <integer>26</integer> + <key>Points</key> + <array> + <string>{141.73921309874385, 162.76286568501573}</string> + <string>{161.26078690125615, 197.23713431498427}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>17</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>21</integer> + </dict> + <key>ID</key> + <integer>25</integer> + <key>Points</key> + <array> + <string>{104.59852247767745, 246.39708013445784}</string> + <string>{121.40147752232251, 279.60291986554216}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>18</integer> + </dict> + <key>ID</key> + <integer>24</integer> + <key>Points</key> + <array> + <string>{81.948838145119652, 247.57020106109587}</string> + <string>{70.051161854880363, 278.42979893890401}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>Head</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + <key>ID</key> + <integer>23</integer> + <key>Points</key> + <array> + <string>{116.88761375265869, 164.12022384803691}</string> + <string>{103.11238624734132, 195.87977615196309}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>1.0142860412597656</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>17</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{181, 277}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>22</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 6}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{107, 277}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>21</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 5}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{65, 194}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>20</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 2}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{148, 194}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>19</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 3}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{33, 277}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>18</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 4}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{101, 111}, {54, 55}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FontInfo</key> + <dict> + <key>Font</key> + <string>Helvetica</string> + <key>Size</key> + <real>22</real> + </dict> + <key>ID</key> + <integer>17</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs46 \cf0 1}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + </array> + <key>GridInfo</key> + <dict/> + <key>GuidesLocked</key> + <string>NO</string> + <key>GuidesVisible</key> + <string>YES</string> + <key>HPages</key> + <integer>1</integer> + <key>ImageCounter</key> + <integer>1</integer> + <key>KeepToScale</key> + <false/> + <key>Layers</key> + <array> + <dict> + <key>Lock</key> + <string>NO</string> + <key>Name</key> + <string>レイヤー 1</string> + <key>Print</key> + <string>YES</string> + <key>View</key> + <string>YES</string> + </dict> + </array> + <key>LayoutInfo</key> + <dict> + <key>Animate</key> + <string>NO</string> + <key>circoMinDist</key> + <real>18</real> + <key>circoSeparation</key> + <real>0.0</real> + <key>layoutEngine</key> + <string>dot</string> + <key>neatoSeparation</key> + <real>0.0</real> + <key>twopiSeparation</key> + <real>0.0</real> + </dict> + <key>LinksVisible</key> + <string>NO</string> + <key>MagnetsVisible</key> + <string>NO</string> + <key>MasterSheets</key> + <array/> + <key>ModificationDate</key> + <string>2014-02-04 03:37:26 +0000</string> + <key>Modifier</key> + <string>Daichi TOMA</string> + <key>NotesVisible</key> + <string>NO</string> + <key>Orientation</key> + <integer>2</integer> + <key>OriginVisible</key> + <string>NO</string> + <key>PageBreaks</key> + <string>YES</string> + <key>PrintInfo</key> + <dict> + <key>NSBottomMargin</key> + <array> + <string>float</string> + <string>41</string> + </array> + <key>NSHorizonalPagination</key> + <array> + <string>coded</string> + <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG</string> + </array> + <key>NSLeftMargin</key> + <array> + <string>float</string> + <string>18</string> + </array> + <key>NSPaperSize</key> + <array> + <string>size</string> + <string>{595, 842}</string> + </array> + <key>NSPrintReverseOrientation</key> + <array> + <string>int</string> + <string>0</string> + </array> + <key>NSRightMargin</key> + <array> + <string>float</string> + <string>18</string> + </array> + <key>NSTopMargin</key> + <array> + <string>float</string> + <string>18</string> + </array> + </dict> + <key>PrintOnePage</key> + <false/> + <key>ReadOnly</key> + <string>NO</string> + <key>RowAlign</key> + <integer>1</integer> + <key>RowSpacing</key> + <real>36</real> + <key>SheetTitle</key> + <string>キャンバス 1</string> + <key>SmartAlignmentGuidesActive</key> + <string>YES</string> + <key>SmartDistanceGuidesActive</key> + <string>YES</string> + <key>UniqueID</key> + <integer>1</integer> + <key>UseEntirePage</key> + <false/> + <key>VPages</key> + <integer>1</integer> + <key>WindowInfo</key> + <dict> + <key>CurrentSheet</key> + <integer>0</integer> + <key>ExpandedCanvases</key> + <array/> + <key>Frame</key> + <string>{{973, 306}, {1121, 998}}</string> + <key>ListView</key> + <true/> + <key>OutlineWidth</key> + <integer>142</integer> + <key>RightSidebar</key> + <false/> + <key>ShowRuler</key> + <true/> + <key>Sidebar</key> + <true/> + <key>SidebarWidth</key> + <integer>120</integer> + <key>VisibleRegion</key> + <string>{{-214, -38}, {986, 859}}</string> + <key>Zoom</key> + <real>1</real> + <key>ZoomValues</key> + <array> + <array> + <string>キャンバス 1</string> + <real>1</real> + <real>1</real> + </array> + </array> + </dict> +</dict> +</plist>
--- a/paper/introduciton.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/introduciton.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,20 +1,20 @@ \chapter{研究背景と目的} \label{ch:introduction} \pagenumbering{arabic} -Web サービスの脆弱性狙った攻撃が頻繁に発生している。 -脆弱性を悪用されると、Web サービス運営者は賠償など多大な損害を受ける可能性がある。 -純粋関数型プログラミング言語 Haskell は、バッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを事前の型検査で防ぐことができる。 -つまり、Haskell を用いることで信頼性の高い Web サービスを開発できると言える。 + Web サービスの脆弱性狙った攻撃が頻繁に発生している. +脆弱性を悪用されると, Web サービス運営者は賠償など多大な損害を受ける可能性がある. +純粋関数型プログラミング言語 Haskell は, バッファオーバーフローや, クロスサイトスクリプティング, SQL インジェクションを事前の型検査で防ぐことができる. +つまり, Haskell を用いることで信頼性の高い Web サービスを開発できると言える. -本研究の目標は、Haskell を用いて信頼性の高い Web サービスおよびデータベースの開発である。 -また、並列実行で性能が線形に向上するスケーラビリティの達成を目指す。 -Web サービス のスケーラビリティを実現するための難点の一つはデータベースであり、データベースは並列にデータにアクセスできる設計が必要となる。 +本研究の目標は, Haskell を用いて信頼性の高い Web サービスおよびデータベースの開発である. +また, 並列実行で性能が線形に向上するスケーラビリティの達成を目指す. +Web サービス のスケーラビリティを実現するための難点の一つはデータベースであり, データベースは並列にデータにアクセスできる設計が必要となる. -本研究では並列にデータへアクセスする手法として、非破壊的木構造を利用する。 -非破壊的木構造では、排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる\cite{shoshi:2010a}\cite{shoshi:2011a}\cite{shoshi:2011b}。 +本研究では並列にデータへアクセスする手法として, 非破壊的木構造を利用する. +非破壊的木構造では, 排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる\cite{shoshi:2010a}\cite{shoshi:2011a}\cite{shoshi:2011b}. -実装した並列データベースの読み込みと書き込みについて性能を計測し、 -読み込みに関して 12 コアで実行した場合、 1 コアで実行した場合と比較して、10.77 倍 という性能向上率が確認でき、 -マルチコアプロセッサの性能を引き出すことができた。 +実装した並列データベースの読み込みと書き込みについて性能を計測し, +読み込みに関して 12 コアで実行した場合, 1 コアで実行した場合と比較して, 10.77 倍 という性能向上率が確認でき, +マルチコアプロセッサの性能を引き出すことができた. -また、Web 掲示板サービスを開発し、 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない、読み込みで 1.87 倍、書き込みで 2.3 倍の性能が確認できた。 +また, Web 掲示板サービスを開発し, 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 1.87 倍, 書き込みで 2.3 倍の性能が確認できた.
--- a/paper/thanx.tex Tue Feb 04 13:50:33 2014 +0900 +++ b/paper/thanx.tex Thu Feb 06 21:12:49 2014 +0900 @@ -1,9 +1,9 @@ \chapter*{謝辞} \addcontentsline{toc}{chapter}{謝辞} -本研究を行うにあたり、日頃より多くの助言、ご指導いただきました河野真治助教授に心より感謝申し上げます。 +本研究を行うにあたり, 日頃より多くの助言, ご指導いただきました河野真治助教授に心より感謝申し上げます. -本研究は、JST/CREST 研究領域「実用化を目指した組み込みシステム用ディペンダブル・ オペレーティングシステム」\cite{deos} D-ADD 研究チームとして実施しました。 -研究の機会を与えてくださった、株式会社 Symphony の永山辰巳さんに感謝します。 +本研究は, JST/CREST 研究領域「実用化を目指した組み込みシステム用ディペンダブル・ オペレーティングシステム」\cite{deos} D-ADD 研究チームとして実施しました. +研究の機会を与えてくださった, 株式会社 Symphony の永山辰巳さんに感謝します. -また、データベースの実装にあたり、多くの議論にお付き合い頂いた大城信康さん、並列信頼研究室の全てのメンバーに感謝いたします. +また, データベースの実装にあたり, 多くの議論にお付き合い頂いた大城信康さん, 並列信頼研究室の全てのメンバーに感謝いたします.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slides/images/jungle_type.graffle Thu Feb 06 21:12:49 2014 +0900 @@ -0,0 +1,1869 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> +<plist version="1.0"> +<dict> + <key>ActiveLayerIndex</key> + <integer>0</integer> + <key>ApplicationVersion</key> + <array> + <string>com.omnigroup.OmniGrafflePro</string> + <string>139.17.0.185490</string> + </array> + <key>AutoAdjust</key> + <false/> + <key>BackgroundGraphic</key> + <dict> + <key>Bounds</key> + <string>{{0, 0}, {559, 783}}</string> + <key>Class</key> + <string>SolidGraphic</string> + <key>ID</key> + <integer>2</integer> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + </dict> + <key>BaseZoom</key> + <integer>0</integer> + <key>CanvasOrigin</key> + <string>{0, 0}</string> + <key>ColumnAlign</key> + <integer>1</integer> + <key>ColumnSpacing</key> + <real>36</real> + <key>CreationDate</key> + <string>2014-02-04 03:47:22 +0000</string> + <key>Creator</key> + <string>Daichi TOMA</string> + <key>DisplayScale</key> + <string>1.000 cm = 1.000 m</string> + <key>GraphDocumentVersion</key> + <integer>8</integer> + <key>GraphicsList</key> + <array> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3216</integer> + </dict> + <key>ID</key> + <integer>3211</integer> + <key>Points</key> + <array> + <string>{356.34543606030172, 308.53288281512982}</string> + <string>{358.52334639036911, 313.24965650249055}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3219</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3219</integer> + </dict> + <key>ID</key> + <integer>3212</integer> + <key>Points</key> + <array> + <string>{348.56431748888383, 291.18476239489189}</string> + <string>{351.2055864906597, 296.22711532547004}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3221</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3217</integer> + </dict> + <key>ID</key> + <integer>3213</integer> + <key>Points</key> + <array> + <string>{340.76540016591923, 308.41125988727646}</string> + <string>{343.24722775843708, 313.34292542658341}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3220</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3218</integer> + </dict> + <key>ID</key> + <integer>3214</integer> + <key>Points</key> + <array> + <string>{334.93249456109351, 308.48751652142602}</string> + <string>{332.62748807512872, 313.31633510986131}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3220</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3220</integer> + </dict> + <key>ID</key> + <integer>3215</integer> + <key>Points</key> + <array> + <string>{342.54606680190636, 291.25997668236658}</string> + <string>{340.08455024886598, 296.19744896567033}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3221</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{355.13675213675219, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3216</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;\f1\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'8c\'8b\'89\'ca\'82\'aa\'96\'be\'82\'e7\'82\'a9\'82\'c9\'92\'78\'82\'ad\'82\'c8\'82\'c1\'82\'c4\'82\'a2\'82\'e9\'81\'42 +\f1 \ +12 +\f0 \'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5\'8e\'c0\'8d\'73\'82\'b5\'82\'bd\'8d\'db\'81\'41 +\f1 Java +\f0 \'82\'c6\'82\'cc\'8f\'91\'82\'ab\'8d\'9e\'82\'dd\'82\'cc\'90\'ab\'94\'5c\'8d\'b7\'82\'cd\'81\'41 +\f1 1.30 +\f0 \'94\'7b\'82\'c5\'82\'a0\'82\'e9\'81\'42 +\f1 \ + +\f0 \'83\'56\'83\'93\'83\'4f\'83\'8b\'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5\'8e\'c0\'8d\'73\'82\'b5\'82\'bd\'8f\'ea\'8d\'87\'82\'c6\'94\'e4\'8a\'72\'82\'b5\'82\'bd\'8f\'ea\'8d\'87\'81\'41 +\f1 12 +\f0 \'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5 +\f1 2.40 +\f0 \'94\'7b\'82\'cc\'90\'ab\'94\'5c\'8c\'fc\'8f\'e3\'82\'aa\'8c\'a9\'82\'e7\'82\'ea\'82\'e9\'81\'42 +\f1 \ +}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{340.06837606837598, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3217</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{325, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3218</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{348.12820512820514, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3219</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{332.35897435897425, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3220</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{340.06837606837598, 279}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3221</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + </array> + <key>ID</key> + <integer>3210</integer> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3204</integer> + </dict> + <key>ID</key> + <integer>3199</integer> + <key>Points</key> + <array> + <string>{108.92071964681287, 308.76955730605567}</string> + <string>{110.75770821265492, 313.64784567215463}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3207</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3207</integer> + </dict> + <key>ID</key> + <integer>3200</integer> + <key>Points</key> + <array> + <string>{101.18795344995119, 291.42641204129848}</string> + <string>{103.49350731612593, 296.65142060307079}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3209</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3205</integer> + </dict> + <key>ID</key> + <integer>3201</integer> + <key>Points</key> + <array> + <string>{93.372756742502119, 308.65229707031142}</string> + <string>{95.516430047433317, 313.7598515598155}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3208</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3206</integer> + </dict> + <key>ID</key> + <integer>3202</integer> + <key>Points</key> + <array> + <string>{88.042933650729921, 308.55602605513161}</string> + <string>{85.836936530128312, 313.41818275579402}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3208</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3208</integer> + </dict> + <key>ID</key> + <integer>3203</integer> + <key>Points</key> + <array> + <string>{95.661140987977674, 291.33448960867088}</string> + <string>{93.306346998937101, 296.31116295515108}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3209</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{108.13675213675219, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3204</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;\f1\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'8c\'8b\'89\'ca\'82\'aa\'96\'be\'82\'e7\'82\'a9\'82\'c9\'92\'78\'82\'ad\'82\'c8\'82\'c1\'82\'c4\'82\'a2\'82\'e9\'81\'42 +\f1 \ +12 +\f0 \'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5\'8e\'c0\'8d\'73\'82\'b5\'82\'bd\'8d\'db\'81\'41 +\f1 Java +\f0 \'82\'c6\'82\'cc\'8f\'91\'82\'ab\'8d\'9e\'82\'dd\'82\'cc\'90\'ab\'94\'5c\'8d\'b7\'82\'cd\'81\'41 +\f1 1.30 +\f0 \'94\'7b\'82\'c5\'82\'a0\'82\'e9\'81\'42 +\f1 \ + +\f0 \'83\'56\'83\'93\'83\'4f\'83\'8b\'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5\'8e\'c0\'8d\'73\'82\'b5\'82\'bd\'8f\'ea\'8d\'87\'82\'c6\'94\'e4\'8a\'72\'82\'b5\'82\'bd\'8f\'ea\'8d\'87\'81\'41 +\f1 12 +\f0 \'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5 +\f1 2.40 +\f0 \'94\'7b\'82\'cc\'90\'ab\'94\'5c\'8c\'fc\'8f\'e3\'82\'aa\'8c\'a9\'82\'e7\'82\'ea\'82\'e9\'81\'42 +\f1 \ +}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{93.068376068375983, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3205</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{78, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3206</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{101.12820512820514, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3207</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{85.35897435897428, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3208</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{93.068376068375983, 279}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3209</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + </array> + <key>ID</key> + <integer>3198</integer> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3193</integer> + </dict> + <key>ID</key> + <integer>3195</integer> + <key>Points</key> + <array> + <string>{393.49998906367091, 253.50001501742494}</string> + <string>{393.49998906367091, 278.49999681519546}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>7</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3166</integer> + </dict> + <key>ID</key> + <integer>3194</integer> + <key>Points</key> + <array> + <string>{145.50001140135399, 253.50001501742412}</string> + <string>{145.50001140135399, 278.49999681519836}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>5</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3188</integer> + </dict> + <key>ID</key> + <integer>3183</integer> + <key>Points</key> + <array> + <string>{404.12958176855881, 308.65921242132578}</string> + <string>{406.12364005661652, 313.43859392948741}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3191</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3191</integer> + </dict> + <key>ID</key> + <integer>3184</integer> + <key>Points</key> + <array> + <string>{396.35376840684916, 291.32505538205629}</string> + <string>{398.79684992475075, 296.4532657388113}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3193</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3189</integer> + </dict> + <key>ID</key> + <integer>3185</integer> + <key>Points</key> + <array> + <string>{388.5521039458219, 308.54763121332167}</string> + <string>{390.83970837630807, 313.55743010016084}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3192</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3190</integer> + </dict> + <key>ID</key> + <integer>3186</integer> + <key>Points</key> + <array> + <string>{383.22773442246, 308.66303411732099}</string> + <string>{381.17258494295106, 313.60514458829601}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3192</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3192</integer> + </dict> + <key>ID</key> + <integer>3187</integer> + <key>Points</key> + <array> + <string>{390.83198296208826, 291.43807798208542}</string> + <string>{388.62130964277918, 296.4951642188276}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3193</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{403.13675213675191, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3188</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{388.0683760683757, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3189</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{372.99999999999972, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3190</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{396.12820512820485, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3191</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{380.35897435897402, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3192</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{388.0683760683757, 279}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3193</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + </array> + <key>ID</key> + <integer>3182</integer> + </dict> + <dict> + <key>Class</key> + <string>Group</string> + <key>Graphics</key> + <array> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3161</integer> + </dict> + <key>ID</key> + <integer>3156</integer> + <key>Points</key> + <array> + <string>{156.117354157287, 308.66598811690199}</string> + <string>{158.10171385541472, 313.45012037448026}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3164</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3164</integer> + </dict> + <key>ID</key> + <integer>3157</integer> + <key>Points</key> + <array> + <string>{148.34528590039389, 291.33043112783105}</string> + <string>{150.78097495210633, 296.46296823208183}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3166</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3162</integer> + </dict> + <key>ID</key> + <integer>3158</integer> + <key>Points</key> + <array> + <string>{140.54250106184949, 308.55346170220059}</string> + <string>{142.82199652482811, 313.56775167989719}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3165</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3163</integer> + </dict> + <key>ID</key> + <integer>3159</integer> + <key>Points</key> + <array> + <string>{135.20708841106685, 308.65154074985202}</string> + <string>{133.13589378013071, 313.58321849338353}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3165</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>3165</integer> + </dict> + <key>ID</key> + <integer>3160</integer> + <key>Points</key> + <array> + <string>{142.81310344334779, 291.42703273046504}</string> + <string>{140.58724492463014, 296.47392848762632}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>0</string> + <key>HeadScale</key> + <real>0.5</real> + <key>Legacy</key> + <true/> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>3166</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{155.13675213675219, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3161</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;\f1\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 \'8c\'8b\'89\'ca\'82\'aa\'96\'be\'82\'e7\'82\'a9\'82\'c9\'92\'78\'82\'ad\'82\'c8\'82\'c1\'82\'c4\'82\'a2\'82\'e9\'81\'42 +\f1 \ +12 +\f0 \'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5\'8e\'c0\'8d\'73\'82\'b5\'82\'bd\'8d\'db\'81\'41 +\f1 Java +\f0 \'82\'c6\'82\'cc\'8f\'91\'82\'ab\'8d\'9e\'82\'dd\'82\'cc\'90\'ab\'94\'5c\'8d\'b7\'82\'cd\'81\'41 +\f1 1.30 +\f0 \'94\'7b\'82\'c5\'82\'a0\'82\'e9\'81\'42 +\f1 \ + +\f0 \'83\'56\'83\'93\'83\'4f\'83\'8b\'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5\'8e\'c0\'8d\'73\'82\'b5\'82\'bd\'8f\'ea\'8d\'87\'82\'c6\'94\'e4\'8a\'72\'82\'b5\'82\'bd\'8f\'ea\'8d\'87\'81\'41 +\f1 12 +\f0 \'83\'58\'83\'8c\'83\'62\'83\'68\'82\'c5 +\f1 2.40 +\f0 \'94\'7b\'82\'cc\'90\'ab\'94\'5c\'8c\'fc\'8f\'e3\'82\'aa\'8c\'a9\'82\'e7\'82\'ea\'82\'e9\'81\'42 +\f1 \ +}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{140.06837606837598, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3162</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{125, 313.33043478260845}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3163</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{148.12820512820514, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3164</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{132.35897435897428, 296.16521739130428}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3165</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{140.06837606837598, 279}, {10.86324786324781, 12.669565217391387}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3166</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + </array> + <key>ID</key> + <integer>3155</integer> + </dict> + <dict> + <key>Bounds</key> + <string>{{342, 176}, {29, 17}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>8</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Pad</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 Tree}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{337, 193}, {113, 60}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>7</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 Oshiro}</string> + </dict> + <key>VFlip</key> + <string>YES</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{94, 176}, {29, 17}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>6</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Pad</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 Tree}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{89, 193}, {113, 60}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>5</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs28 \cf0 Daichi}</string> + </dict> + <key>VFlip</key> + <string>YES</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{59, 92}, {54, 22}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>YES</string> + <key>Flow</key> + <string>Resize</string> + <key>ID</key> + <integer>4</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Pad</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 Jungle}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + <key>Wrap</key> + <string>NO</string> + </dict> + <dict> + <key>Bounds</key> + <string>{{51.5, 121}, {456, 233}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>3181</integer> + <key>Shape</key> + <string>Rectangle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Align</key> + <integer>0</integer> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural + +\f0\fs28 \cf0 Map}</string> + </dict> + <key>TextPlacement</key> + <integer>0</integer> + </dict> + </array> + <key>GridInfo</key> + <dict/> + <key>GuidesLocked</key> + <string>NO</string> + <key>GuidesVisible</key> + <string>YES</string> + <key>HPages</key> + <integer>1</integer> + <key>ImageCounter</key> + <integer>1</integer> + <key>KeepToScale</key> + <true/> + <key>Layers</key> + <array> + <dict> + <key>Lock</key> + <string>NO</string> + <key>Name</key> + <string>Layer 1</string> + <key>Print</key> + <string>YES</string> + <key>View</key> + <string>YES</string> + </dict> + </array> + <key>LayoutInfo</key> + <dict> + <key>Animate</key> + <string>NO</string> + <key>circoMinDist</key> + <real>18</real> + <key>circoSeparation</key> + <real>0.0</real> + <key>layoutEngine</key> + <string>dot</string> + <key>neatoSeparation</key> + <real>0.0</real> + <key>twopiSeparation</key> + <real>0.0</real> + </dict> + <key>LinksVisible</key> + <string>NO</string> + <key>MagnetsVisible</key> + <string>NO</string> + <key>MasterSheets</key> + <array/> + <key>ModificationDate</key> + <string>2014-02-04 04:37:01 +0000</string> + <key>Modifier</key> + <string>Daichi TOMA</string> + <key>NotesVisible</key> + <string>NO</string> + <key>Orientation</key> + <integer>2</integer> + <key>OriginVisible</key> + <string>NO</string> + <key>PageBreaks</key> + <string>YES</string> + <key>PrintInfo</key> + <dict> + <key>NSBottomMargin</key> + <array> + <string>float</string> + <string>41</string> + </array> + <key>NSHorizonalPagination</key> + <array> + <string>coded</string> + <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG</string> + </array> + <key>NSLeftMargin</key> + <array> + <string>float</string> + <string>18</string> + </array> + <key>NSPaperSize</key> + <array> + <string>size</string> + <string>{595, 842}</string> + </array> + <key>NSPrintReverseOrientation</key> + <array> + <string>int</string> + <string>0</string> + </array> + <key>NSRightMargin</key> + <array> + <string>float</string> + <string>18</string> + </array> + <key>NSTopMargin</key> + <array> + <string>float</string> + <string>18</string> + </array> + </dict> + <key>PrintOnePage</key> + <false/> + <key>ReadOnly</key> + <string>NO</string> + <key>RowAlign</key> + <integer>1</integer> + <key>RowSpacing</key> + <real>36</real> + <key>SheetTitle</key> + <string>Canvas 1</string> + <key>SmartAlignmentGuidesActive</key> + <string>YES</string> + <key>SmartDistanceGuidesActive</key> + <string>YES</string> + <key>UniqueID</key> + <integer>1</integer> + <key>UseEntirePage</key> + <false/> + <key>VPages</key> + <integer>1</integer> + <key>WindowInfo</key> + <dict> + <key>CurrentSheet</key> + <integer>0</integer> + <key>ExpandedCanvases</key> + <array> + <dict> + <key>name</key> + <string>Canvas 1</string> + </dict> + </array> + <key>Frame</key> + <string>{{1008, 396}, {881, 922}}</string> + <key>ListView</key> + <true/> + <key>OutlineWidth</key> + <integer>142</integer> + <key>RightSidebar</key> + <false/> + <key>ShowRuler</key> + <true/> + <key>Sidebar</key> + <true/> + <key>SidebarWidth</key> + <integer>119</integer> + <key>VisibleRegion</key> + <string>{{-94, 0}, {747, 783}}</string> + <key>Zoom</key> + <real>1</real> + <key>ZoomValues</key> + <array> + <array> + <string>Canvas 1</string> + <real>1</real> + <real>1</real> + </array> + </array> + </dict> +</dict> +</plist>