Mercurial > hg > Papers > 2017 > ikkun-thesis

Binary file .DS_Store has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/finalPre.tex~	Wed Feb 15 19:03:19 2017 +0900
@@ -0,0 +1,208 @@
+\documentclass[twocolumn,twoside,9.5pt]{jarticle}
+\usepackage[dvipdfmx]{graphicx}
+\usepackage{picins}
+\usepackage{fancyhdr}
+\usepackage{abstract}
+\usepackage{url}
+%\pagestyle{fancy}
+\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
+\rhead{}
+\cfoot{}
+
+\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
+\setlength{\headheight}{0mm}
+\setlength{\headsep}{5mm}
+\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
+\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
+\setlength{\textwidth}{181mm}
+\setlength{\textheight}{261mm}
+\setlength{\footskip}{0mm}
+\pagestyle{empty}
+
+\input{dummy.tex}
+\renewcommand{\abstractname}{Abstract}
+\begin{document}
+\title{}
+%\title{Supporting NAT in Screen Sharing System TreeVNC}
+\author{125716B 氏名 {伊波}{立樹} 指導教員 : 河野 真治}
+\date{}
+\twocolumn [
+\maketitle
+\begin{onecolabstract}
+An implementation of Screen sharing system is presented.
+TreeVNC supports multicasting high resolution PC screen using tree structured network over PCs.
+Copying costs are distributed instead of the centralized heavy costs on a VNC server.
+It also possible to change screen server dynamically without changing display cables.
+TreeVNC is useful in a lecture which contains 40-60 students or small seminar.
+We add several improvements on TreeVNC, such as new connection method for supporting NAT, screen change in a separated thread, multiple screen selection, notification of connection errors.
+We also show the delay time distribution in real environments
+\end{onecolabstract}]
+\thispagestyle{fancy}
+
+\section{画面共有を利用したコミュニケーション}
+授業やゼミ等で、それぞれが PC 端末を持っている場合では、
+PC の機能を活かしたコミュニケーションが可能である。
+
+通常の授業では先生の用意した資料、 PC 画面を見ながら授業が進むことが多い。
+ゼミでは発表者を切り替えながら発表を行う。
+
+画面配信システム TreeVNC\cite{taninari:2011a}は発表者の画面を参加者の PC に表示する。
+そのため、参加者は手元の PC を使用しながら授業を受ける事が可能になる。
+更に発表者の切り替えの際もケーブルの差し替えずに共有する画面の切替を可能としている。
+
+Tree VNC は VNC\cite{vnc} を使用した画面配信を行っている。
+しかし通常の VNC では配信側に全ての参加者が接続するため、多人数の際の処理性能が落ちてしまう。
+Tree VNC では有線でネットワークに接続した参加者をバイナリツリー状に接続し、 配信コストをクライアントに分散させる仕組みになっている。
+そのため、授業で先生の画面を表示する際、多人数の生徒が参加しても処理性能が下がらない。
+また、ツリーのルートが参照している VNC サーバーを変更することで、共有する画面の切替が可能となる。
+
+しかし TreeVNC を授業やゼミで使用している中、 様々な問題が発生した。
+NATを越えたネットワーク接続に対応しておらず、遠隔地などで授業やゼミに参加することが出来ない。
+また、ゼミの際に、マルチディスプレイを使用して画面配信を行う際、すべての画面が配信され、不必要な画面まで表示されてしまう。
+
+そこで、本研究では上記の問題点を解決し、TreeVNCの有用性を評価することで授業やゼミを円滑に行えることを目標とする。
+
+\section{画面配信システムTreeVNC}
+VNC(Virtual Network Computing) は、 RFBプロトコルを用いて遠隔操作を行うリモートデスクトップソフトウェアである。
+
+TreeVNC は Java を用いて作成された TightVNC(Tight Virtual Network Computing)\cite{tightvnc} を元に作成されている。
+
+TreeVNC は クライアント同士を接続させ、画面描画のデータを受け取ったクライアントが次のクライアントにデータを流す方式を取っている。
+また、サーバへ接続しに来たクライアントをバイナリツリー状に接続する(図\ref{fig:tree})。
+バイナリツリー状に接続することで、$N$ 台のクライアントが接続しに来た場合、画面配信の画像データをコピーする回数は従来の VNC ではサーバ側で$N$ 回する必要があるが、TreeVNCでは各ノードが2回ずつコピーするだけで済む。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[width=50mm]{./pic/treeVnc.pdf}
+    \end{center}
+    \caption{構成される木構造}
+    \label{fig:tree}
+\end{figure}
+
+\section{NAT への対応}
+遠隔地からでもゼミや授業に参加できるよう、 NATを越えたネットワークから TreeVNC への接続を可能にした。
+
+図\ref{fig:directConnection} にNATを越えたネットワークからの接続を示す。
+別ネットワークからTreeVNCに参加する際、 直接配信側のネットワークの Root Node に接続を行う。
+この接続を Direct Connection と呼ぶ。
+
+Direct Connection した Node はそのネットワークの Root Node になる。
+そのネットワークの他の Node はそのネットワークの Root Node に接続し、木構造を生成する。
+
+配信側の Root Node は Direct Connection で接続された Root Node に対して Framebuffer Update で 画像データを送信する。
+Framebuffer Update が送信された Root Node は そのネットワークの Node に対して Framebuffer Update を送信する。
+
+これにより、NATを越えたネットワークの画面共有が可能となる。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[width=80mm]{./pic/directConnection.pdf}
+        \caption{遠隔地 Node からの接続}
+        \label{fig:directConnection}
+    \end{center}
+\end{figure}
+
+\section{マルチディスプレイ対応}
+画面配信側のPCがマルチディスプレイの場合、 VNC サーバーからは複数の画面全体の画像データが送信されてしまう。
+そこで、画面を共有する際、ディスプレイを選択させ、画面共有を行う機能を追加した\cite{parusu:2016a}。
+
+ディスプレイの情報は個々のクライアントでしか取得ができない。
+そのため、配信側は画面の切替を行う際に、ディスプレイを選択し、そのディスプレイの左上と右下の座標を取得する。
+その座標を Root Node への画面切り替えを要求する SERVER\_CHANGE\_REQUEST メッセージに付加させる。
+Root Node は 配信側の VNC サーバー に画像データを要求する FRAMEBUFFER\_UPDATE\_REPLY メッセージに送信された座標を付加する。
+VNC サーバーは要求された座標内の画像データを FRAMEBUFFER\_UPDATE メッセージで Root Node に送信する。
+これにより、一画面のみの表示が可能となる。
+
+図\ref{fig:multidisplay} は Display1 のみを画面共有する例を示している。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[width=70mm]{./pic/shareScreenToMultiDisplay.pdf}
+    \end{center}
+    \caption{マルチディスプレイへの対応}
+    \label{fig:multidisplay}
+\end{figure}
+
+\section{画面切り替えの安定化}
+画面切り替えを行う際、 配信中の画面を停止した後に画面の切り替え処理を実行していた。
+しかし、 切り替え先の VNC サーバーへの接続に時間がかかったり、 切り替え先の設定ミスなどで画面の切替がスムーズに行えない場合があった。
+
+そこで、 画面切り替えを行う際に新しく切り替え用のスレッドを生成し処理する変更を行った。
+Root Node は SERVER\_CHANGE\_REQUEST を受け取ると、 配信状態を維持したまま、画面切り替え用に新しくスレッドを生成する。
+切り替え用のスレッドは切り替えに必要なデータの設定、 VNC サーバー への接続など通常の切り替え処理を実行する。
+切り替えが完了した後に、 現在配信中の画面を停止し、画面の切替を行う。
+切り替え用のスレッドを用意することで、配信状況を維持したままスムーズな画面切り替えが可能になった。
+
+\section{クライアントへのエラー通知}
+TreeVNC には接続しているクライアントへのエラーの通知を行うことが出来なかった。
+そのため、 画面切り替えを行う際に切り替え先が VNC サーバーの共有設定をしていない場合 Root Node に接続エラーのダイアログが表示されるという実装になっており、切り替えを行ったクライアントには通知されていなかった。
+
+この問題を解決するために新しくERROR\_ANNOUNCE というメッセージを追加した。
+ERROR\_ANNOUNCE メッセージは Root Nodeから木構造を辿りながら末端の Node に通信を行うメッセージで、エラー通知したいクライアントの Node Nuber と エラー内容の文字列を付加して送信する。
+付加した Node Number に一致する Node がメッセージを受け取ると、 付加されたエラーの文字列をダイアログで表示する。
+エラー通知用のメッセージを追加することで、 各々のクライアントに対して通知を行うことが可能になった。
+
+\section{TreeVNC の評価}
+VNC サーバー から受信する画像データ、 TreeVNC で扱われるメッセージ通信は構成された木を伝って伝達される。
+接続する人数が増える毎に木の段数は増えていく。 そこで Root Node から木の末端の Node までの画像データ伝達の遅延を検証する実験を行った。
+
+今回授業を受講している学生が TreeVNC を使用した状態で実験を行った。
+TreeVNC には最大で17名が接続していた。
+バイナリツリーで木を構成した場合、 Node 数が17台だと深さが4となる。
+
+図\ref{fig:depth}は深さ4 の遅延の分布を示した散布図である。
+X軸はメッセージ伝達にかかった秒数(ms)、 Y軸は画像データのサイズ(Byte)である。
+画像データの伝達はほぼ1秒以内に収まっているが、容量が小さい場合でも時間がかかる場合がある。
+それはその送信の前に大容量の画像を送信した後の回線のDelayが残っているためだと考えられる。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[width=60mm]{./pic/depth4.eps}
+    \end{center}
+    \caption{データサイズと遅延の関係 : 深さ4}
+    \label{fig:depth}
+\end{figure}
+
+また、この実験で1つだけ極端に遅い Node が見られた。
+このような Node を木に配置した場合、その Node の 子 Node 以下に影響を及ぼすおそれがある。
+
+\section{ボトルネックになっている Node への対処}
+画像データを受け取る時間が遅い Node をそのまま木構造に配置しているとその子 Node 以下に影響を及ぼす。
+そのためネックになっている Node への対処が必要である。
+
+図\ref{fig:fixTree}は 6台の Node が接続している状態で Node1 がネックになっている場合の木の再構成を示している。
+Root Node はその Node がボトルネックなっているかの判断を遅延の実験で使用したメッセージを使って行う。
+ボトルネックになっているなら Root Node の nodeList からその Node を削除する。
+削除した Node の場所には末端の Node を配置するように CONNECT\_TO メッセージを送信する。
+nodeList から削除された Node は接続されたままなので、データの受信は行うが、 木構造には入らないため、ネックになっている Node の下に新しい Node が繋がることはない。
+そのためネックになっている Node 以下に影響を及ばすことがない。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[width=100mm]{./pic/fixTree.pdf}
+    \end{center}
+    \caption{ボトルネックになっている Node への対処}
+    \label{fig:fixTree}
+\end{figure}
+
+\section{まとめ}
+本研究では画面配信システム TreeVNC での NAT 対応、 マルチディスプレイ対応、共有画面切り替えの安定化、 各 Node へのエラー通知、TreeVNC の評価を行った。
+
+NATを越えに対応した Direct Connection という接続方法を確立し実装した。
+これにより、NAT を越えた別ネットワークのユーザーが TreeVNC に参加することが可能となった。
+
+マルチディスプレイの場合に画面を選択して配信することが可能になった。
+
+画面切り替えの際に切り替え用のスレッドを用意することでスムーズな画面切り替えが可能。
+
+新しく ERROR\_ANNOUNCE メッセージを追加することで各Nodeにエラー通知を行える様になった。
+
+今回の画像データの遅延実験を行い、 ボトルネックになっているノードがあることがわかった。
+また、ボトルネックになっているノードへの対処を行った。
+
+また今後の課題として音声配信機能の実装、マルチディスプレイ時の表示画面サイズの調整を行う
+
+\nocite{*}
+\bibliographystyle{junsrt}
+\bibliography{reference}
+\end{document}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/midterm.tex	Wed Feb 15 19:03:19 2017 +0900
@@ -0,0 +1,158 @@
+\documentclass[twocolumn,twoside,9.5pt]{jarticle}
+\usepackage[dvipdfmx]{graphicx}
+\usepackage{picins}
+\usepackage{fancyhdr}
+%\pagestyle{fancy}
+\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
+\rhead{}
+\cfoot{}
+
+\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
+\setlength{\headheight}{0mm}
+\setlength{\headsep}{5mm}
+\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
+\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
+\setlength{\textwidth}{181mm}
+\setlength{\textheight}{261mm}
+\setlength{\footskip}{0mm}
+\pagestyle{empty}
+
+\input{dummy.tex}
+\begin{document}
+\title{Code Gear Data Gear によるGPGPU処理実装}
+\author{135704C 氏名 {東恩納}{琢偉} 指導教員 : 河野 真治}
+\date{}
+\twocolumn [
+\maketitle
+\begin{英語abst}
+
+\end{英語abst}]
+\thispagestyle{fancy}
+
+\section{Gears OS}
+Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
+Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear
+に細かく分割する。
+Gearで表現される計算はメタ計算により実行される。例えば、
+従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
+接続する Gear を変更することでプログラムの振る舞いを変更することを可能
+にする柔軟性、メタ計算による並行制御,モデル検査を用いた信頼性の確保を目的とする。
+本研究では現状のGears OS のマルチCPUサポートに加えてGPGPUサポートを行
+う。
+GPGPUはCUDAまたはOpeCLで制御される。Gears OSからCide Gear Data Gearを
+これらに正しく渡す必要がある。
+
+Gears OS上のTaskはRed Black Tree上に格納される。rb\_treeはCbCで記述さ
+れており、木をたどるためのStackを一つ持つ。
+アルゴリズム全体はCode Gearの有向グラフで表される。実際にこの有向グラ
+フを作成した。これは一種のフローチャートになっている。木とStackに格納
+されるのはData Gearである。この木を用いて GPGPUを実行するエンジンに
+Taskを渡す。
+
+
+\section{Code Gear と Data Gear}
+Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda} の kernel に相当する。
+
+Code Gear は処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書き込む。また、接続された Data Gear 以外には参照を行わない。
+これは Alice の Input Data Segment と Output Data Segment の関係に対応しており、依存関係を解決し、 Code Segment の並列実行を可能とする。
+
+
+Code Gear はfunction callではないので、呼び出し元に戻る概念はない。
+その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。
+
+Data Gear は、int や文字列などの Primitive Data Type の組み合わせ
+（struct）である。
+Data Gearは様々な型を持つunionとして定義される。
+
+Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。
+これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
+
+\section{Context}
+ある Code Gear は次に実行する Code Gear を名前で指定する。これを継続と
+いう。
+Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
+これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。
+名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
+この Meta Data Gear を Context と呼ぶことにする。
+これは従来の OS の Process や Thread を表す構造体に対応する。
+
+Context には以下のようなものが格納される。
+\begin{itemize}
+    \item Code Gear の名前とポインタの対応表
+    \item Data Gear の Allocation 用の情報
+    \item Code Gear が参照する Data Gear へのポインタ
+    \item Data Gear に格納される Data Type の情報
+\end{itemize}
+
+\section{Red Black Tree}
+図\ref{fig:rb_tree}はRed Black Treeにおけるinsertとバランシングのアルゴリズムを表したものです。
+putした時、rootがあればNew Node をpushして空いているNodeにReplaceする。rootがなければinsertする。
+Red Black Treeのバランシングはバランスに必要な分Popで戻り、バランスさせる点まで来たらRoutateR RoutateLする。
+Routateは自分の今のNodeとParentとGrandPararentの３種類でroutateする。
+\begin{figure}[ht]
+    \centering
+    \includegraphics[width=70mm]{pic/rb_tree.pdf}
+    \caption{CbCでのRed Black Tree}
+    \label{fig:rb_tree}
+\end{figure}
+\section{GPGPU}
+ GPGPUとは画像処理に使われるGPUを画像処理以外で利用する技術である。
+GPUはCPUに比べコア数が圧倒的に多く、単純な計算しかできないが並列処理において一度に大量の計算ができるため利用されている。
+Gears OS は Code Gear に分割され処理の依存関係が明確になるので、並列な処理を書きやすい。またData Gear へのアクセスは接続されたCode Gear からのみであるから、処理中に変数が書き変わる事がない。
+図\ref{fig:gpgpu}では以下の流れで処理が行われる。
+\begin{itemize}
+    \item Data Gear をPersistent Data Tree に挿入。
+    \item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTask を生成。
+    \item 生成したTaskをTaskQueueに挿入。
+    \item Workerの起動。
+    \item WorkerがTskQueueからTaskを取得。
+    \item 取得した Task を元に必要なData Gear を Persistent Data Tree から取得。
+    \item 並列処理される Code Gear を実行。
+\end{itemize}
+
+\begin{figure}[ht]
+    \centering
+    \includegraphics[width=90mm]{pic/gearsosgpgpu.pdf}
+    \caption{Gears OS による GPGPU}
+    \label{fig:gpgpu}
+\end{figure}
+\section{今後の課題}
+ 今回、Gears OS のGPGPU処理についての基本的な設計と必要な機能の一部を紹介した。
+今後の課題としては、Gears OS による GPGPU処理を実装する。並列化処理に最適な Mappingをほどこす。Cerium、GearsでのMany CPU の並列化処理と比較しながら、GPGPU処理の測定、評価を行う。
+
+
+\begin{thebibliography}{10}
+    \bibitem{cerium}
+        宮國　渡，河野真治，神里　晃，杉山千秋：Cell 用の Fine-grain Task Manager
+        の実装，情報処理学会
+        システムソフトウェアとオペレーティング・システム研究会(OS) (2008).
+
+    \bibitem{alice}
+        赤嶺一樹，河野真治：DataSegment API
+        を用いた分散フレームワークの設計，日本ソフトウェア科学会第28回大会論文集
+        (2011).
+
+    \bibitem{gears}
+      伊波 立樹, 東恩納 琢偉,河野 真治:Code Gear、Data Gear に基づく OS のプロトタイプ、
+      情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) (2016).
+
+    \bibitem{segment}
+        河野真治，杉本　優：Code Segment と Data Segment
+        によるプログラミング手法，第54回プログラミング・シンポジウム (2013).
+
+    \bibitem{monad}
+        Eugenio Moggi, Notion of Computation and Monads(1991)
+
+    \bibitem{cbc-llvm}
+        徳森海斗，河野真治：Continuation based C の LLVM/clang 3.5
+        上の実装について，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
+        (2014).
+
+    \bibitem{opencl}
+        {Aaftab Munshi, Khronos OpenCL Working Group}: {\em {The OpenCL Specification Version 1.0}} (2007).
+
+    \bibitem{cuda}
+        : {CUDA}, {https://developer.nvidia.com/category/zone/cuda-zone/}.
+
+\end{thebibliography}
+\end{document}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/midterm.tex~	Wed Feb 15 19:03:19 2017 +0900
@@ -0,0 +1,154 @@
+\documentclass[twocolumn,twoside,9.5pt]{jarticle}
+\usepackage[dvipdfmx]{graphicx}
+\usepackage{picins}
+\usepackage{fancyhdr}
+%\pagestyle{fancy}
+\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
+\rhead{}
+\cfoot{}
+
+\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
+\setlength{\headheight}{0mm}
+\setlength{\headsep}{5mm}
+\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
+\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
+\setlength{\textwidth}{181mm}
+\setlength{\textheight}{261mm}
+\setlength{\footskip}{0mm}
+\pagestyle{empty}
+
+\input{dummy.tex}
+\begin{document}
+\title{CodeGear,DataGearによるGPGPU処理}
+\author{135704C 氏名 {東恩納}{琢偉} 指導教員 : 河野 真治}
+\date{}
+\maketitle
+\thispagestyle{fancy}
+
+\section{Gears OS}
+Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
+Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear
+に細かく分割する。
+Gearで表現される計算はメタ計算により実行される。例えば、
+従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
+接続する Gear を変更することでプログラムの振る舞いを変更することを可能
+にする柔軟性、メタ計算による並行制御,モデル検査を用いた信頼性の確保を目的とする。
+本研究では現状のGears OS のマルチCPUサポートに加えてGPGPUサポートを行
+う。
+GPGPUはCUDAまたはOpeCLで制御される。Gears OSからCide Gear Data Gearを
+これらに正しく渡す必要がある。
+
+Gears OS上のTaskはRed Black Tree上に格納される。rb\_treeはCbCで記述さ
+れており、木をたどるためのStackを一つ持つ。
+アルゴリズム全体はCode Gearの有向グラフで表される。実際にこの有向グラ
+フを作成した。これは一種のフローチャートになっている。木とStackに格納
+されるのはData Gearである。この木を用いて GPGPUを実行するエンジンに
+Taskを渡す。
+
+
+\section{Code Gear と Data Gear}
+Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda} の kernel に相当する。
+
+Code Gear は処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書き込む。また、接続された Data Gear 以外には参照を行わない。
+これは Alice の Input Data Segment と Output Data Segment の関係に対応しており、依存関係を解決し、 Code Segment の並列実行を可能とする。
+
+
+Code Gear はfunction callではないので、呼び出し元に戻る概念はない。
+その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。
+
+Data Gear は、int や文字列などの Primitive Data Type の組み合わせ
+（struct）である。
+Data Gearは様々な型を持つunionとして定義される。
+
+Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。
+これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
+
+\section{Context}
+ある Code Gear は次に実行する Code Gear を名前で指定する。これを継続と
+いう。
+Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
+これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。
+名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
+この Meta Data Gear を Context と呼ぶことにする。
+これは従来の OS の Process や Thread を表す構造体に対応する。
+
+Context には以下のようなものが格納される。
+\begin{itemize}
+    \item Code Gear の名前とポインタの対応表
+    \item Data Gear の Allocation 用の情報
+    \item Code Gear が参照する Data Gear へのポインタ
+    \item Data Gear に格納される Data Type の情報
+\end{itemize}
+
+\section{Red Black Tree}
+図\ref{fig:rb_tree}はRed Black Treeにおけるinsertとバランシングのアルゴリズムを表したものです。
+putした時、rootがあればNew Node をpushして空いているNodeにReplaceする。rootがなければinsertする。
+Red Black Treeのバランシングはバランスに必要な分Popで戻り、バランスさせる点まで来たらRoutateR RoutateLする。
+Routateは自分の今のNodeとParentとGrandPararentの３種類でroutateする。
+\begin{figure}[ht]
+    \centering
+    \includegraphics[width=70mm]{pic/rb_tree.pdf}
+    \caption{CbCでのRed Black Tree}
+    \label{fig:rb_tree}
+\end{figure}
+\section{GPGPU}
+ GPGPUとは画像処理に使われるGPUを画像処理以外で利用する技術である。
+GPUはCPUに比べコア数が圧倒的に多く、単純な計算しかできないが並列処理において一度に大量の計算ができるため利用されている。
+Gears OS は Code Gear に分割され処理の依存関係が明確になるので、並列な処理を書きやすい。またData Gear へのアクセスは接続されたCode Gear からのみであるから、処理中に変数が書き変わる事がない。
+図\ref{fig:gpgpu}では以下の流れで処理が行われる。
+\begin{itemize}
+    \item Data Gear をPersistent Data Tree に挿入。
+    \item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTask を生成。
+    \item 生成したTaskをTaskQueueに挿入。
+    \item Workerの起動。
+    \item WorkerがTskQueueからTaskを取得。
+    \item 取得した Task を元に必要なData Gear を Persistent Data Tree から取得。
+    \item 並列処理される Code Gear を実行。
+\end{itemize}
+
+\begin{figure}[ht]
+    \centering
+    \includegraphics[width=90mm]{pic/gearsosgpgpu.pdf}
+    \caption{Gears OS による GPGPU}
+    \label{fig:gpgpu}
+\end{figure}
+\section{今後の課題}
+ 今回、Gears OS のGPGPU処理についての基本的な設計と必要な機能の一部を紹介した。
+今後の課題としては、Gears OS による GPGPU処理を実装する。並列化処理に最適な Mappingをほどこす。Cerium、GearsでのMany CPU の並列化処理と比較しながら、GPGPU処理の測定、評価を行う。
+
+
+\begin{thebibliography}{10}
+    \bibitem{cerium}
+        宮國　渡，河野真治，神里　晃，杉山千秋：Cell 用の Fine-grain Task Manager
+        の実装，情報処理学会
+        システムソフトウェアとオペレーティング・システム研究会(OS) (2008).
+
+    \bibitem{alice}
+        赤嶺一樹，河野真治：DataSegment API
+        を用いた分散フレームワークの設計，日本ソフトウェア科学会第28回大会論文集
+        (2011).
+
+    \bibitem{gears}
+      伊波 立樹, 東恩納 琢偉,河野 真治:Code Gear、Data Gear に基づく OS のプロトタイプ、
+      情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) (2016).
+
+    \bibitem{segment}
+        河野真治，杉本　優：Code Segment と Data Segment
+        によるプログラミング手法，第54回プログラミング・シンポジウム (2013).
+
+    \bibitem{monad}
+        Eugenio Moggi, Notion of Computation and Monads(1991)
+
+    \bibitem{cbc-llvm}
+        徳森海斗，河野真治：Continuation based C の LLVM/clang 3.5
+        上の実装について，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
+        (2014).
+
+    \bibitem{opencl}
+        {Aaftab Munshi, Khronos OpenCL Working Group}: {\em {The OpenCL Specification Version 1.0}} (2007).
+
+    \bibitem{cuda}
+        : {CUDA}, {https://developer.nvidia.com/category/zone/cuda-zone/}.
+
+\end{thebibliography}
+\end{document}