Papers/2014/toma-master: paper/chapter2.tex annotate

annotate paper/chapter2.tex @ 34:345eacdf29e4

add apendix

author	Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
date	Mon, 03 Feb 2014 16:54:48 +0900
parents	ff03e6179f19
children	ec3488a9ddd4

rev	line source
10 a349b2c01cfe add graffle Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 9 diff changeset	1 \chapter{Haskellによる並列データベースの設計}\label{ch:design}
2 d8b94e828d79 add tex files Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	2
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	3 \section{マルチプロセッサで十分な性能を得るためには}
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	4 現在、CPU はマルチコア化が進んでいる。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	5 マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保たなければならない\cite{amdahl}。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	6 % ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	7 % 利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	8 % スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	9 % 一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	10
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	11 CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできればよい。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	12 通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	13
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	14 本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	15 競合を発生させないためには、既にあるデータを変更しなければよい。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	16 非破壊的木構造は、変更元となる木構造を変更しない。
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	17 そのため、別々の CPU コアから並列にアクセスが可能であり、スケーラビリティを実現できる。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	18
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	19 \newpage
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	20 \section{非破壊的木構造}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	21 非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	22 既にあるデータを変更しないため、データの競合状態が発生せず、並列に読み書きが行える。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	23
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	24 また、元の木構造は破壊されることがないため、自由にコピーを行うことができる。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	25 コピーを複数作成することでアクセスを分散させることも可能である。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	26
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	27 図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	28
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	29 \begin{figure}[!htbp]
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	30 \begin{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	31 \includegraphics[width=120mm]{./images/nondestructive_tree_modification.pdf}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	32 \end{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	33 \caption{木構造の非破壊的編集}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	34 \label{fig:nondestructive_tree_modification}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	35 \end{figure}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	36
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	37 非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	38 そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	39
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	40 編集は以下の手順で行われる。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	41
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	42 \begin{enumerate}
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	43 \item{変更したいノードまでのパスを求める(図\ref{fig:nondestructive_tree_modification_step1})。}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	44 \item{変更したいノードをコピーし、コピーしたノードの内容を変更した新しいノードを作成する(図\ref{fig:nondestructive_tree_modification_step2})。}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	45 \item{求めたパス上に存在するノードをルートノードに向かってコピーする。コピーしたノードに一つ前にコピーしたノードを子供として追加した新しいノードを作成する(図\ref{fig:nondestructive_tree_modification_step3})。}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	46 \item{影響のないノードをコピー元の木構造と共有する(図\ref{fig:nondestructive_tree_modification_step4})。}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	47 \end{enumerate}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	48
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	49 \begin{figure}[!htbp]
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	50 \begin{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	51 \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step1.pdf}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	52 \end{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	53 \caption{ステップ1 : 変更したいノードまでのパスを求める}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	54 \label{fig:nondestructive_tree_modification_step1}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	55 \end{figure}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	56 \begin{figure}[!htbp]
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	57 \begin{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	58 \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step2.pdf}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	59 \end{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	60 \caption{ステップ2 : 変更したいノードをコピーし、コピーしたノードの内容を変更した新しいノードを作成する}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	61 \label{fig:nondestructive_tree_modification_step2}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	62 \end{figure}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	63 \begin{figure}[!htbp]
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	64 \begin{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	65 \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step3.pdf}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	66 \end{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	67 \caption{ステップ3 : 求めたパス上に存在するノードをルートノードまでコピーする}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	68 \label{fig:nondestructive_tree_modification_step3}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	69 \end{figure}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	70 \begin{figure}[!htbp]
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	71 \begin{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	72 \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step4.pdf}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	73 \end{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	74 \caption{ステップ4 : 影響のないノードは共有する}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	75 \label{fig:nondestructive_tree_modification_step4}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	76 \end{figure}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	77
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	78 \newpage
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	79 この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	80 閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	81 排他制御をせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用である。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	82 元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	83
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	84 \begin{figure}[!htbp]
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	85 \begin{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	86 \includegraphics[width=140mm]{./images/nondestructive_tree_modification_in_lace.pdf}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	87 \end{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	88 \caption{並列に読み書きが可能な非破壊的木構造}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	89 \label{fig:nondestructive_tree_modification_in_lace}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	90 \end{figure}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	91
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	92
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	93 \newpage
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	94 \section{ルートノード}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	95 非破壊的木構造では、ルートノードの管理が重要である。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	96 ルートノードは、木の最新の状態を更新・参照するのに使う。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	97 ルートノードの情報は、全てのスレッドで共有する必要があり、スレッドセーフに取り扱う必要がある。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	98 一度ルートノードの情報を取得すれば、その後は排他制御なしに木構造へアクセスできる（図\ref{fig:rootnode}）。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	99
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	100 \begin{figure}[!htbp]
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	101 \begin{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	102 \includegraphics[scale=0.6]{./images/rootnode.pdf}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	103 \end{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	104 \caption{排他制御なしの非破壊的木構造のアクセス}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	105 \label{fig:rootnode}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	106 \end{figure}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	107
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	108 ルートノードはスレッド間で共有する状態を持つため、Haskell では IO モナドを用いる必要がある。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	109 これには、Haskell のソフトウェア・トランザクショナル・メモリ（STM）を利用する。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	110 STM は排他制御を行わず、スレッドセーフに状態を扱うことができる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	111 STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	112 STM は、STM モナドという特殊なモナドの中でのみ変更できる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	113 STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する（atomically コンビネータを用いることで IO モナドとして返される）。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	114 いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	115 こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	116 トランザクションから出る時に、以下のことが１つだけ起こる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	117 \begin{itemize}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	118 \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	119 \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	120 \end{itemize}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	121
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	122 STM は排他制御を行わないため、簡単に扱うことができる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	123 ルートノードの情報の取得だけならば、並列に取得できる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	124 ルートノードの情報の更新の場合は、他から変更があれば再度やり直すということが自動的に行われる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	125
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	126 以前の実装では、ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	127 しかしながら、非破壊的木構造全体をSTMで管理すると並列実行時に性能が出ないため、ルートノードのみの管理に変更を行った。

Mercurial > hg > Papers > 2014 > toma-master

annotate paper/chapter2.tex @ 34:345eacdf29e4