--- a/midterm.tex	Fri Oct 21 23:25:49 2016 +0900
+++ b/midterm.tex	Thu Oct 26 19:48:08 2017 +0900
@@ -2,6 +2,7 @@
 \usepackage[dvipdfmx]{graphicx}
 \usepackage{picins}
 \usepackage{fancyhdr}
+\usepackage{here}
 %\pagestyle{fancy}
 \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
 \rhead{}
@@ -19,116 +20,93 @@
 
 \input{dummy.tex}
 \begin{document}
-\title{LLVM/clang 上の CbC コンパイラの改良と Gears OS サポート}
-\author{135756F 氏名 宮城光希 {}{} 指導教員 : 河野 真治}
+\title{分散データベースJungleの評価}
+\author{145762E 氏名 仲松栞 {}{} 指導教員 : 河野 真治}
 \date{}
 \maketitle
 \thispagestyle{fancy} 
 
-\section{メタ計算の重要性}
+\section{研究背景}
+スマートフォンやタブレット端末の普及にともない、年々Webサービスの利用者は増加した一方で、データ量が増大し、サーバ側への負荷も増加している。
+これを解決するため、Webサービスには、よりシステムの処理能力を拡張する性質である、スケーラビリティが求められてきている。
+スケーラビリティとは、
+webサービスにスケーラビリティを付与する方法の１つに、データベースにスケーラビリティを持たせる事が考えられる。
 
-プログラムを記述する際に通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。これらの計算を Meta Computation と呼ぶ。
-
-Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
-そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Segment、Data Segment という単位を提案している。  
+そこで、当研究室ではスケーラビリティを持つデータベースとして木構造を持つ分散データベースjungleを開発している。
 
-Code Segment は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
-Code Segment、Data Segment にはそれぞれメタレベルの単位である Meta Code Segment、Meta Data Segment が存在し、これらを用いて Meta Computation を実現する。
+これまでに行われた分散環境上でのJungleの性能を検証する実験では、使用するTestプログラムのフロントエンドにWebサーバーJettyが使用されており、純粋なJungleの性能は測定できていなかった。今回は、新たに改良されたJungleの性能を、Webサーバーを取り除いたTestプログラムを用いて測定することを目的とする。
+
+\section{分散データベースJungle}
+Jungleは、当研究室で開発を行っている木構造の分散データベースで、Javaを用いて実装されている。
 
-また、Code Segment 単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。
-CbCは軽量継続による遷移を行うので、継続前の Code Segment に戻ることはなく、状態遷移ベースのプログラミングに適している。
-
-Data Gear は CbC で記述された Gears OS によって管理される。Gears OS では一つのスレッドは Data Gears と Code Gears を管理する Context をただ一つ持つ。
-Context は Meta Data Gears の一つである。
+Jungleはデータをオンメモリで保持している。しかし、オンメモリのままでは電源が落ちた際にデータが失われてしまうという問題がある。
+そこで、データの復旧を行えるよう、Jungleではログによって、バージョンごとにデータを保持している。
+Jungleの分散ノード間の通信は木の変更のログを交換することによって、分散データベースを構成するよう設計されている。
+持続性のある分散ノードを用いることでJungleの持続性を保証することができる。
 
-本研究では、LLVM/clang 上での CbC コンパイラの改良と Gears OS の構文のサポートを行う。
+Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
 
-\section{Continuation based C (CbC)}
+通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造[3]を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。
 
-CbC では Code Segment は \_\_code という型を持つ関数の構文で定義される。
+Jungleは基本的にオンメモリで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
 
-Code Segment は 戻り値を持たないので、return 文は存在しない。goto の後に Code Segment 名と引数を並べて、次の Code Gears の遷移を記述する。
+\section{分散フレームワークAliceによる分散環境の構築}
+本研究では、分散環境上でのJungleの性能を確認する為、VMを32台用意し、それぞれでJungleを起動して、Jungle間で通信をする環境をつくる。
+Jungle間の通信部分を、当研究室で開発している並列分散フレームワークAlice[1]にて再現する。
 
-この goto の行き先を継続と呼ぶ。Scheme の継続と異なり CbC には環境がないので、この継続は単なる行き先である。したがってこれを軽量継続と呼ぶこともある。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。
+Aliceとは当研究室で開発している並列分散フレームワークである。Aliceにより、トポロジーを構成する機能とデータアクセスの機構が提供される。
 
-\begin{figure}[htpb]
+Aliceには、ネットワークのトポロジーを構成するTopologyManager[2]という機能が備わっている。TopologyManagerに参加表明をしたサーバーノードに順番に、接続先のサーバーノードのIPアドレス、ポート番号、接続名を送り、受け取ったサーバーノードはそれらに従って接続する。
+今回、TopologyManagerはVM32台分のJungleを、それぞれ木構造のトポロジーを形成するように采配する（図\ref{fig:topologymanager} ）。
+
+\begin{figure}[H]
     \centering
-    \includegraphics[width=70mm]{pic/codesegment.pdf}
-    \caption{gotoによる Code Segment 間の接続}
-    \label{fig:codesegment}
+    \includegraphics[width=70mm]{pic/topologymanager.pdf}
+    \caption{AliceによるJungleの木構造トポロジーの形成}
+    \label{fig:topologymanager}
 \end{figure}
 
-\section{LLVM/clang による CbC の実装}
-LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。
-LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。
-
-clang は LLVM をバックエンドとして利用する C/C++/Objective-C のコンパイラである。
+AliceによってJungleのネットワークを木構造のトポロジーで形成した後に、Jungle間でのデータの通信部分を再現しなければならない。そこで、TreeOperationLog[2]を利用する。TreeOperationLogには、ノードの編集の履歴などの情報が入っている。TreeOperationLogをAliceによって他のJungleへ送ることで、送信元のJungleと同じ編集を送信先のJungleで行う。こうして、Jungle間でのデータの同期を可能にしている。
+\section{TORQUE Resource Manager}
+分散環境上でのJungleの性能を測定するにあたり、VM32台にJungleを起動させた後、それぞれでデータを書き込むプログラムを動作させる。プログラムを起動する順番やタイミングは、TORQUE Resource Manager[1]というジョブスケジューラーによって管理する。
 
-LLVMでは、最適化や中間表現の変換を何段階か行う。多くの pass は最適化のために存在し、そのなかから任意のものを利用することができる。
-pass には以下のようなものがある。
-  
-\subsubsection*{SelectionDAG Instruction Selection (SelectionDAGISel)}
-    LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し、最適化を行う。その後 Machine Code を生成する。
-\subsubsection*{SSA-based Machine Code Optimizations}
-    SSA-based Machine Code に対する最適化を行う。各最適化はそれぞれ独立した pass になっている。
-\subsubsection*{Register Allocation}
-    仮想レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、SSA-based でなくなる。
-\subsubsection*{Prolog/Epilog Code Insertion}
-    Prolog/Epilog Code の挿入を行う。どちらも関数呼び出しに関わるものであり、Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、Epilog は呼び出し元の関数に戻る際に行う処理である。
-\subsubsection*{Late Machine Code Optimizations}
-    Machine Code に対してさらに最適化を行う。
-\subsubsection*{Code Emission}
-    Machine Code を MC Layer での表現に変換する。その後さらにターゲットのアセンブリ言語へ変換し、その出力を行う。
+TORQUE Resource Manager は、ジョブを管理・投下・実行する３つのデーモンで構成されており、
+ジョブの管理・投下を担うデーモンが稼働しているヘッダーノードから、ジョブの実行を担うデーモンが稼働している計算ノードへジョブが投下される（図\ref{fig:torque} ）。
+  \begin{figure}[ht]
+    \begin{center}
+        \includegraphics[width=70mm]{./pic/torque.pdf}
+    \end{center}
+        \caption{TORQUEの構成}
+         \label{fig:torque}
+\end{figure}
+ユーザーはジョブを記述したシェルスクリプトを用意し、スケジューラーに投入する。その際に、利用したいマシン数やCPUコア数を指定する。TORQUEは、ジョブに必要なマシンが揃い次第、受け取ったジョブを実行する。
+\section{Testプログラム}
+これまでの分散環境上でのJungleの性能を測定する実験で使われたTestプログラムは、フロントエンドにJettyというWebサーバーが使われていた。
+このままでは、Webサーバーを仲介したJungleの性能の測定結果になってしまう。
+今回、Webサーバーを取り除き、これまでの研究により純粋にJungleの性能を測定するTestプログラムを作成する。
 
-\begin{figure}[ht]
+Testプログラムは、木構造における子ノードに、データを複数書き込む機能を提供する。
+末端の複数の子ノードにデータをそれぞれ書き込み、最終的にrootノードへデータをmergeしていく(図\ref{fig:logupdatetest} ）。
+\begin{figure}[H]
     \centering
-    \includegraphics[width=90mm]{pic/llvmProcess.pdf}
-    \caption{LLVM の 処理過程}
-    \label{fig:llvmProcess}
+    \includegraphics[width=70mm]{pic/logupdatetest.pdf}
+    \caption{LogupdateTestによるJungleの性能測定}
+    \label{fig:logupdatetest}
 \end{figure}
 
-\section{LLVM/clang のデバッグ}
-LLVM/clang で CbC をコンパイルした際 Code Segment 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。
-
-局所変数でポインタを参照していると clang は生成する LLVM IR に オブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。
-
-ここでオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。
-
-しかしCbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。
-そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。
-
-\section{Gears OS の構文サポート}
-Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
-Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。
-
-Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。Meta Code Gear は通常の Code Gear の直後に遷移され、Meta Computation を実行する。
-
-CbC では処理を Code Segment を用いたプログラミング言語であるため、 Gears OS の Code Gear を記述するのに適している。
-そこで Gears OS の構文のサポートが必要になる。現在は python を用いたプログラム変換で実現されている。
-
-Gears OS では Context という接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Dara Gear である。Gears OS では必要な Code/Data Gear に参照したい場合、Context を通す必要がある。
-Context の自動生成を行うようにする。
-
-\section{今後の課題}
-今後の課題は現状の Gears OS のコードをリファクタリングし通常計算とメタ計算の分離を明確にする。
-必要なメタ計算部分の CbC による実装を統一する。
-Context 、 Meta Code Gear 、 Meta Data Gear を生成するプログラム変換系を作成する。
-これを用いて Gears OS の記述を行う。
-これにより Gears OS のメタ計算を柔軟に行うことができるようになり、 Gears OS 自体の信頼性を向上し, Gears OS の拡張性を実現することができると考えられる。
+\section{今後の作業}
+今後の方針として、本研究室で開発している並列分散フレームワークであるAlice[1]とTORQUE Resource Manager[1]を用いて、分散環境上でのJungleの性能を測定する。
+測定後は、結果をふまえ、Jungleの性能を向上させる為のmergeアルゴリズム等を考案・実装し、スケーラビリティを持つ実用的な分散データベースの開発を目指す。
 
 \begin{thebibliography}{9}
     \bibitem{1}
-        徳森 海斗 : LLVM Clang 上の Continuation based C コンパイラ の改良,
+        杉本 優 : 分散フレームワーク Alice上の Meta Computation と応用,
     \bibitem{2}
-        伊波立樹, 東恩納琢偉, 河野真治 : Code Gear、 Data Gear に基づく OS のプロトタイプ, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2016).
+        大城 信康 : 分散 Database Jungle に関する研究,
     \bibitem{3}    
-        大城 信康, 河野真治 : Continuation based C の GCC 4.6 上の実装について, 第53回プログラミング・シンポジウム(2012)
+        金川 竜己 : 非破壊的木構造データベース Jungle とその評価
     \bibitem{4}
-        与儀健人, 河野真治 : Continuation based c コンパイラの gcc-4.2 による実装, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2008).
-    \bibitem{5}
-        The LLVM Compiler Infrastructure
-    \bibitem{6}
-        LLVM Language Reference Manual
-
+        大城 信康, 杉本 優, 河野真治 : Data Segment の分散データベースへの応用, 日本ソフトウェア科学会(2013).
+   
 \end{thebibliography}
 \end{document}