Mercurial > hg > Papers > 2017 > suruga-sigos

Binary file paper/.DS_Store has changed
--- a/paper/sigos.aux	Fri Apr 21 01:50:26 2017 +0900
+++ b/paper/sigos.aux	Fri Apr 21 02:27:16 2017 +0900
@@ -4,8 +4,8 @@
 \newlabel{fig:PushPopDemerit}{{3}{3}}
 \newlabel{table:Diffetential API}{{1}{3}}
 \newlabel{fig:EditDifferencialTree}{{4}{3}}
-\newlabel{fig:EditDifferencialTree}{{5}{4}}
-\newlabel{fig:EditDifferencialTree}{{6}{4}}
+\newlabel{fig:Differential_Interface_Traverser}{{5}{4}}
+\newlabel{fig:Tree_ver2}{{6}{4}}
 \citation{*}
 \bibstyle{ipsjunsrt}
 \bibdata{sigos}
@@ -15,6 +15,5 @@
 \bibcite{opencl}{4}
 \bibcite{cuda}{5}
 \bibcite{gears}{6}
-\bibcite{cbc-lola}{7}
 \newlabel{table:Diffetential API}{{2}{5}}
 \gdef\ipsj@lastpage{5}
--- a/paper/sigos.bbl	Fri Apr 21 01:50:26 2017 +0900
+++ b/paper/sigos.bbl	Fri Apr 21 02:27:16 2017 +0900
@@ -1,9 +1,8 @@
 \begin{thebibliography}{1}

 \bibitem{cerium}
-宮國　渡，河野真治，神里　晃，杉山千秋\：Cell 用の Fine-grain Task Manager
-  の実装，情報処理学会
-  システムソフトウェアとオペレーティング・システム研究会(OS) (2008).
+金川竜己，河野真治\：非破壊的木構造データベース Jungle とその評価，情報処理学会
+  システムソフトウェアとオペレーティング・システム研究会(OS) (2015).

 \bibitem{alice}
 照屋のぞみ，河野真治\：分散フレームワークAliceのPC画面配信システムへの応用，第57回プログラミング・シンポジウム
@@ -25,8 +24,4 @@
   の設計，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
   (2015).

-\bibitem{cbc-lola}
-TOKKMORI, K. and KONO, S.: Implementing Continuation based language in LLVM and
-  Clang, {\em LOLA 2015} (2015).
-
 \end{thebibliography}
--- a/paper/sigos.blg	Fri Apr 21 01:50:26 2017 +0900
+++ b/paper/sigos.blg	Fri Apr 21 02:27:16 2017 +0900
@@ -12,48 +12,46 @@
 Warning--Missing required argument author in cuda
 Warning--there's no number and/or volumegears
 Warning--Missing required argument pages in gears
-Warning--there's no number and/or volumecbc-lola
-Warning--Missing required argument pages in cbc-lola
-You've used 7 entries,
+You've used 6 entries,
             2207 wiz_defined-function locations,
-            563 strings with 4942 characters,
-and the built_in function-call counts, 1207 in all, are:
-= -- 63
-> -- 60
+            559 strings with 4816 characters,
+and the built_in function-call counts, 982 in all, are:
+= -- 53
+> -- 45
 < -- 0
-+ -- 21
-- -- 14
-* -- 91
-:= -- 183
-add.period$ -- 7
-call.type$ -- 7
++ -- 16
+- -- 10
+* -- 71
+:= -- 150
+add.period$ -- 6
+call.type$ -- 6
 change.case$ -- 0
 chr.to.int$ -- 0
-cite$ -- 18
-duplicate$ -- 85
-empty$ -- 122
-format.name$ -- 20
-if$ -- 272
+cite$ -- 15
+duplicate$ -- 70
+empty$ -- 104
+format.name$ -- 12
+if$ -- 223
 int.to.chr$ -- 0
-int.to.str$ -- 7
-missing$ -- 5
-newline$ -- 24
-num.names$ -- 6
-pop$ -- 25
+int.to.str$ -- 6
+missing$ -- 4
+newline$ -- 21
+num.names$ -- 5
+pop$ -- 19
 preamble$ -- 1
 purify$ -- 0
 quote$ -- 0
-skip$ -- 48
+skip$ -- 41
 stack$ -- 0
 substring$ -- 0
-swap$ -- 2
-text.length$ -- 11
+swap$ -- 1
+text.length$ -- 9
 text.prefix$ -- 0
 top$ -- 0
 type$ -- 0
-warning$ -- 11
-while$ -- 6
-width$ -- 8
-write$ -- 49
-is.kanji.str$ -- 41
-(There were 11 warnings)
+warning$ -- 9
+while$ -- 5
+width$ -- 7
+write$ -- 42
+is.kanji.str$ -- 31
+(There were 9 warnings)
Binary file paper/sigos.dvi has changed
--- a/paper/sigos.log	Fri Apr 21 01:50:26 2017 +0900
+++ b/paper/sigos.log	Fri Apr 21 02:27:16 2017 +0900
@@ -1,4 +1,4 @@
-This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10)  21 APR 2017 01:41
+This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10)  21 APR 2017 02:26
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -160,12 +160,6 @@
 )
 (./dummy.tex) (./sigos.aux

-LaTeX Warning: Label `fig:EditDifferencialTree' multiply defined.
-
-
-LaTeX Warning: Label `fig:EditDifferencialTree' multiply defined.
-
-
 LaTeX Warning: Label `table:Diffetential API' multiply defined.

 )
@@ -250,16 +244,17 @@
 /9 addNewChild(
  []

-File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf)
-<./pic/EditDifferencialTree.pdf> [3]
-File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf)
- <./pic/EditDifferencialTree.pdf>
+[3]
+File: ./pic/Differential_Interface_Traverser.pdf Graphic file (type pdf)
+ <./pic/Differential_Interface_Traverser.pdf>
+File: ./pic/Tree_ver2.pdf Graphic file (type pdf)
+ <./pic/Tree_ver2.pdf> [4]
 Overfull \hbox (18.31381pt too wide) in paragraph at lines 241--246
  [][][]
  []

-[4] (./sigos.bbl
-Overfull \hbox (58.50209pt too wide) in paragraph at lines 21--22
+(./sigos.bbl
+Overfull \hbox (58.50209pt too wide) in paragraph at lines 20--21
 []\OT1/cmr/m/n/9 : CUDA, https://developer.nvidia.com/category/zone/cuda-
  []

@@ -272,12 +267,12 @@

  )
 Here is how much of TeX's memory you used:
- 3082 strings out of 493693
- 43101 string characters out of 6149787
+ 3090 strings out of 493693
+ 43373 string characters out of 6149787
  145093 words of memory out of 5000000
- 6630 multiletter control sequences out of 15000+600000
+ 6635 multiletter control sequences out of 15000+600000
  17185 words of font info for 66 fonts, out of 8000000 for 9000
  929 hyphenation exceptions out of 8191
  30i,13n,49p,943b,329s stack positions out of 5000i,500n,10000p,200000b,80000s

-Output written on sigos.dvi (5 pages, 35456 bytes).
+Output written on sigos.dvi (5 pages, 35256 bytes).
Binary file paper/sigos.pdf has changed
--- a/paper/sigos.tex	Fri Apr 21 01:50:26 2017 +0900
+++ b/paper/sigos.tex	Fri Apr 21 02:27:16 2017 +0900
@@ -203,30 +203,30 @@
 　Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。また、Differential Jungle Tree は、木の編集時複製を行わないため、 Index のアップデートは、 Editor が保持している木構造のデータを Index に追加するだけで良い。

  \paragraph* {Differential Jungle Tree の検索}
- 　Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。なので、過去の木に対して全探索を行なった場合、その版には無いはずのノードが取得できてしまう。例として、編集前の木である Tree ver1 と編集後の木である Tree ver2 があるとする(図\ref{fig:PushPopDemerit})。ここで、Tree ver1 に対して、全探索を行なった場合、本来Tree ver1 に存在しないノード3・４も検索対象に含まれてしまう。そこで、その版の木が持つ末尾ノード以下のSub Tree を検索対象から除外する、Differential Interface Traverser を実装した。Differential Interface Traverserを用いて木の全探索を行なった場合、Tree ver1 に存在しないノード３・４は検索対象から省かれる。
- %画像つくる
+ 　Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。なので、過去の木に対して全探索を行なった場合、その版には無いはずのノードが取得できてしまう。例として、編集前の木である Tree ver1 と編集後の木である Tree ver2 があるとする(図\ref{fig:Differential_Interface_Traverser})。ここで、Tree ver1 に対して、全探索を行なった場合、本来Tree ver1 に存在しないノード3・４も検索対象に含まれてしまう。そこで、その版の木が持つ末尾ノード以下のSub Tree を検索対象から除外する、Differential Interface Traverser を実装した。Differential Interface Traverserを用いて木の全探索を行なった場合、Tree ver1 に存在しないノード３・４は検索対象から省かれる。
+
 \begin{figure}[ht]
     \begin{center}
-        \includegraphics[width=70mm]{./pic/EditDifferencialTree.pdf}
+        \includegraphics[width=60mm]{./pic/Differential_Interface_Traverser.pdf}
     \end{center}
     \caption{複数の版の木の表現}
-    \label{fig:EditDifferencialTree}
+    \label{fig:Differential_Interface_Traverser}
 \end{figure}
  　Index を使用した検索を行う場合、各版の木に対応した Index があるため、Default Tree と検索のアルゴリズムは変わらない。これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。

 \paragraph* {Differential Jungle Tree の検索}
  　Differential Jungle Tree への Commit は、編集後の木のデータを持つ TreeContext を作り、編集前の木が持つ TreeContext と Atomic に入れ替えることで行われる。しかし、Differential Jungle Tree のCommit は、Default Jungle Tree の Commit と異なり、TreeContext の入れ替えと、 Editor が保持している木構造の末尾ノードへの Append の２つのプロセスからなる。 TreeContext の入れ替えに関しては、 Default Jungle Tree と同じように行い、末尾ノードへの Editor が持っている木構造の Append は、TreeContect の入れ替えが成功した後に行う。そうすることで、別Thread で行われている Commit と競合した際に、 TreeContext を入れ替えた Thread と別 Thread がAppend を行い、木の整合性が崩れることを回避している。
- 　また、過去の版の木に対して、編集を加えCommit を行なった場合、木の整合性が崩れてしまう問題もある。図()()を例に解説する。図（）の過去の版の木 Tree ver1 に新しいノード５を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード３・４という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが２つの子ノードを持っているせいで発生する。
+ 　また、過去の版の木に対して、編集を加えCommit を行なった場合、木の整合性が崩れてしまう問題もある。図(\ref{fig:Differential_Interface_Traverser})(\ref{fig:Tree_ver2})を例に解説する。図（）の過去の版の木 Tree ver1 に新しいノード５を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード３・４という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが２つの子ノードを持っているせいで発生する。
  　この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を１つしか持つことができないようにした。そうすることで木の整合性を保証している。


-%画像つくる
+
 \begin{figure}[ht]
     \begin{center}
-        \includegraphics[width=70mm]{./pic/EditDifferencialTree.pdf}
+        \includegraphics[width=50mm]{./pic/Tree_ver2.pdf}
     \end{center}
     \caption{木の整合性が崩れる例}
-    \label{fig:EditDifferencialTree}
+    \label{fig:Tree_ver2}
 \end{figure}

 \section{Red Black Jungle Tree の実装}