\documentclass[a4j,12pt]{jreport}
\usepackage[dvipdfmx]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{ascmac} 
\usepackage{here}
\usepackage{url}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{listings, jlisting}
%% \input{dummy} %% font

\lstset{
    language=java, 
    tabsize=2, 
    frame=single, 
    basicstyle={\ttfamily\footnotesize},% 
    identifierstyle={\footnotesize},% 
    commentstyle={\footnotesize\itshape},% 
    keywordstyle={\footnotesize\bfseries},% 
    ndkeywordstyle={\footnotesize},% 
    stringstyle={\footnotesize\ttfamily}, 
    breaklines=true, 
    captionpos=b, 
    columns=[l]{fullflexible},% 
    xrightmargin=0zw,% 
    xleftmargin=1zw,% 
    aboveskip=1zw, 
    numberstyle={\scriptsize},% 
    stepnumber=1, 
    numbersep=0.5zw,% 
    lineskip=-0.5ex, 
    numbers=left 
}
\renewcommand{\lstlistingname}{Code}

\setlength{\itemsep}{-1zh}

\title{GearsOS on Raspberry Pi}
\icon{
    \includegraphics[width=80mm,bb=0 0 595 642]{fig/ryukyu.pdf} %%元は 642じゃなくて842
}
\year{平成30年度 卒業論文}
\belongto{琉球大学工学部情報工学科}
\author{145759E 桃原 優 \\ 指導教員 {河野 真治} }

\makeatletter
\newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}
\makeatother
\setlength\abovecaptionskip{0pt}

\begin{document}

% タイトル
\maketitle
\baselineskip 17pt plus 1pt minus 1pt

\pagenumbering{roman}
\setcounter{page}{0}

\tableofcontents	% 目次
\listoffigures		% 図目次
\listoftables		% 表目次

%以下のように、章ごとに個別の tex ファイルを作成して、
% main.tex をコンパイルして確認する。
%章分けは個人で違うので下のフォーマットを参考にして下さい。

% はじめに

% １章では研究目的を書かない(もったいない)




\chapter{(序章)}
\pagenumbering{arabic}
問題提起\\
研究目的はかかない


\label{chap:Introduction}


% 

%序論の目安としては1枚半ぐらい．
%英語発表者は，最終予稿の「はじめに」の英訳などを載せてもいいかも．



% \chapter{CbC}
% Continuation based C(以下、CbC)は、本研究室で LLVM/Clang 上に実装した言語である。

% CbC は Code Segment 間を、goto によって継続的に遷移し処理を行っている。
% その流れを図\ref{fig:CodeSegment} に示す。

 

% \begin{figure}[htpb]
 %  \begin{center}
   % \scalebox{1}{\includegraphics{images/codesegment.pdf}}
  % \end{center}
  % \caption{goto による Code Segment 間の継続}
  % \label{fig:CodeSegment}
% \end{figure}

% \label{chap:CbC}


% \section{Code Segment}
% CbC は Code Segment を基本的な処理単位とする。C の関数とは異なり返り値を持たないが、
% Code Segment の宣言は C の関数の構文と同じように行い、型に \_\_code を用いる。

% CbC は for 文や while 文といったループ制御構文を持たないので、
% ループ処理は自分自身への再帰的な継続を行う事で実現する。

% 現在の Code Segment から次の Code Segment への移動は 
% goto の後に Code Segment 名と引数を並べて記述する。この goto 
% による処理の遷移を継続と呼ぶ。C と異なり、戻り値を持たない Code Segment 
% ではスタックに値を積んで行く必要が無くスタックは変更されない。
% このようなスタックに値を積まない継続を軽量継続と呼ぶ。この軽量継続により、
% 並列化、ループ制御、関数コールとスタックの操作を意識した
% 最適化がソースコードレベルで行えるようになる。




% \chapter{GearsOS}
% \label{chap:GearsOS}


% \section{GearsOS}
% 当研究室では、CodeSegmentとDataSegmentによって構成される 
% GearsOSの開発を行っている。GearsOSは、並列プログラミングフレームワーク
% の Cerium と分散フレームワークの Alice の開発を通して得られた知見を元に
% 開発を進めている。

% Cerium はオブジェクト指向言語である C++ を用いて開発した並列プログラミング
% フレームワークである。Cell、マルチコアCPU、GPU を用いた並列実行をサポート
% している。並列処理の単位として Task を記述し、Task に他の Task との
% 依存関係を設定する事で並列実行を実現するが、データは汎用ポインタで Task に
% 渡されるため、データの依存関係を保証できない。データの正しさや依存関係を
% 保証できていないので、並列処理は行えるが、信頼性が低い。その知見から、
% 並列分散処理 には Code の分割だけではなく Data の分割も必要である事が
% 分かった。

%  Alice では処理の単位である、 Code Segment、データの単位である 
% Data Segment を用いてプログラムを記述する。Code Segment は使用する Input Data Segment、Output Data Segment  を指定することで処理とデータの依存関係を解決する。Gears OSでは、Gear という単位を用いてプログラムを Code Gear、Data Gear に細かく分割するが、これは Alice のCode Segment、Data Segment にそれぞれ対応する。\\
% Gears OS では CbC を用いて Data Sement を定義し、
% 実装を行っている。

% 当研究室で開発している Code Segment を処理単位とする プログラミング言語
% CbC を用いて Data Segment を定義し、Gears OS の実装を行っている。


% \section{Code Gear と Data Gear}
% Gears OS では、プログラムの単位として Gear を用いる。
% Gear は並列実行の単位、データの分割、Gear 間の接続等になる。

% Code Gear はプログラムの処理そのものであり、任意の数の Data Gear を参照し、
% 処理が完了すると任意の数の Data Gear に書き込む。Code Gear は接続された 
% Data Gear 以外にアクセスできない。Code Segment と同じように Code Gear から
% 次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定する事で実現できる。

% Data Gear はデータそのものを表す。int や 文字列などの Primitive Data Type 
% を持っている。Gear の特徴として処理やデータの構造が Code Gear、Data Gear 
% に閉じている事にある。これにより、実行時間、メモリ使用量などを予測可能なものにすることができる。

\chapter{RaspberryPi上でのGearsOS}


当研究室では CbC(Continuation base C) とCbC を用いて実装する 
GearsOS の研究を行っている。

CbC は Code Segment と Data Segment という単位でプログラムを記述する。
Code Segment は並列処理の単位として利用でき、
Data Segment はデータそのもので型を持っていて、
CbC はメタレベルの処理，並列処理を記述することができる。

メタレベルの処理では、メモリ管理、スレッド管理、CPU や GPU の資源管理
を記述することができる。

本研究では、ARM で動くシングルボードコンピュータである 
Raspberry Pi 上で Gears OS を動かせるようになる事で、
ハードウェア上でもメタレベルの処理、並列実行ができるプログラミング
を記述できるようになる事を目指している。

しかし、メモリの関係上 RaspberryPi 上で CbC の make を行うと、
かなりの時間がかかる。

解決案として、OSX 上で CrossCompile を行う方法と、Linux 環境で 
CrossCompile を行う方法を提案する。




\label{chap:rpiGears}



\chapter{RaspberryPi上での実装}

\label{chap:rpi}

\section{CbCのmake時間}
%  Raspberry Pi の OS である Raspbian ではメモリが 256MB なので
%  Raspberry Pi 上で直接 CbC をコンパイルするには時間がかかる。qemu によるメモリの拡張もできないので、別の手法で Raspberry Pi 上に CbC を実装する方が好ましい。
Raspberry Pi 1 のメモリは 256MB と小さいため、 CbC をコンパイルすることができない。
Raspberry Pi 3 だとメモリは 1GB あり CbC をコンパイルできるが、時間がかかる。



学科のサーバの一つでLinux環境であるDALMORE

\begin{table}[htb]
\centering
\scalebox{1.5}[1.5]{
  \begin{tabular}{| c | r | r |} \hline
    環境(メモリ) & 時間 & 比較 \\ \hline \hline
    RaspberryPi(1GB) & 15時間11分06秒 & 1.00倍 \\ \hline
    OSX(16GB) & 2時間16分06秒 & 6.69倍 \\ \hline
    Linux(500GB) & 2分26秒 & 374.42倍 \\ \hline
  \end{tabular}
  }
\end{table}



% qemuによる拡張ができない原因


\section{T図形}
CbC を Raspberry Pi で動かすためのアプローチの手法を、I と T の形をした
図の組み合わせによって説明を行う。I の上部分に cbclang や Xv6 などのソースコード名を、
下部分にその機能の記述言語を記してある。T の下にある I は特別で、上に VM 下に VM を乗せている
 OS が記されている。  T の上部分は左に入力されるファイル、右に出力されるその機能によって出力される
 ファイルが記され、下部分にその機能の記述言語が記されている。
 
例として、cbclang のソースコード(I)と、 Raspberry Pi 上の clang (T) 
を図\ref{fig:examples} に示す。

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.70}{\includegraphics{images/examples_2.pdf}}
 \end{center}
 \caption{T図形の例}
 \label{fig:examples}
\end{figure}

\break
Raspberry Pi でコンパイルを行うまでの過程を、図\ref{images:RaspberryPi}に示す。

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.30}{\includegraphics{images/RaspberryPi_2.pdf}}
 \end{center}
 \caption{Raspberry Pi}
 \label{images:RaspberryPi}
\end{figure}


\break



\chapter{CrossCompile}
\label{chap:CrossCompile}
OSX 上で CrossCompile する事で make 時間の問題を解決する方法がある。
% CrossCompile とは、別の OS で実行可能なコードを生成するコンパイルの手法である。
% つまり、OSX であらかじめ Raspberry Pi で CbC が動くように CrossCompile を行い、そのコードを Raspberry Pi に移せばよい。\\ 
  CrossCompile とは、別の OS で実行可能なコードを生成するコンパイルの手法である。


% この研究でOSX とLinuxそれぞれで LLVMとGCCのCrossCompileを行う説明

Raspberry Pi の OS である Rasbian が qemu によるメモリの拡張もできないので、
別の手法で Raspberry Pi 上に CbC を実装する方が好ましい。


\chapter{OSX}
\label{chap:OSX}
  
  
\section{LLVM}

arm-linux-gnueabihf-gcc というツールチェーンを使用し、C で書かれたファイルを CrossCompile することで OSXで
 ARM のコードを生成できる事を確認した。その際のコマンドをリスト\ref{OSXCrossCompile}に、生成されたファイルにfileコマンドで調べた結果をリスト\ref{OSXfile}に示す。
 \begin{lstlisting}[frame=lrbt,label=OSXCrossCompile,caption={CrossCompileの例}]
 /usr/local/linaro/arm-linux-gnueabihf-raspbian/bin/arm-linux-gnueabihf-gcc -g -o hello hello.c
\end{lstlisting}


 \begin{lstlisting}[frame=lrbt,label=OSXfile,caption={生成したファイル}]
$ file hello
hello: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter 
/lib/ld-linux-armhf.so.3, for GNU/Linux 2.6.26, 
BuildID[sha1]=a78af9ba00197d52a8ed7cbac433b24360c57283, not stripped
\end{lstlisting}


\break

 この時、出力は mach-o になるので、mach-o の 
 loader 作ることで CbC が動かせるようになる。
 
  まだ実装できていないが、OSX 上で行えるためコンパイルの速度向上が望める。
OSX 上で コンパイルを行うまでの過程を、図\ref{fig:OSX}に示す。

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.7}{\includegraphics{images/OSX_2.pdf}}
 \end{center}
 \caption{OSX}
 \label{fig:OSX}
\end{figure}


\section{GCC}

\break

\chapter{Linux}
\section{LLVM}


\section{GCC}

CrossCompile と別に Linux 環境で CbC を動かした後に、Raspberry Pi に載せる手法がある。

 Linux の LLVM でコンパイルすることができれば elf のコードを書けるようになるので、
 elf のloader を作る事で、CbC を動かすことができる。
 
  また、Linux 用の gcc を CbC に書き直す際に、gcc7 に書き直せば linker がそのまま使えるので、
  Xv6 で動くようになる。
  
  Xv6とは、マサチューセッツ工科大の大学院生向け講義の教材として使うために、UNIX V6 という OS を 
  ANSI-C に書き換え、x86に移植した OS である。
Xv6 は Raspberry Pi に移植する事ができる。ANSI-C で書かれている Xv6 を CbC に書き直す事で、
Raspberry Pi で CbC を動かせるようになる。

  Linux 上 で LLVM がコンパイルできない原因はまだ分かってないが、
  メモリを上げる事でこの方法でもコンパイルの速度向上が望める。 
Linux 上で コンパイルを行うまでの過程を、図\ref{fig:OSX_Linux_VM}に示す。

\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.8}{\includegraphics{images/OSX_Linux_VM_2.pdf}}
 \end{center}
 \caption{OSX Linux VM}
 \label{fig:OSX_Linux_VM}
\end{figure}

% Xv6詳しく


 \begin{lstlisting}[frame=lrbt,label=LinuxCrossCompile,caption={LinuxでのCrossCompile}]
  ./bin/clang -target arm-linux-gnueabi -mfpu=neon-fp16 -marm -I /net/open/Linux/arm/gcc-arm-none-eabi-7-2017-q4-major/arm-none-eabi/include/ hello.c -c -mfloat-abi=hard
\end{lstlisting}


\chapter{今後の課題}
\label{chap:Task}

Xv6 で CbC が動くようになれば、Raspberry Pi 以外のハードウェアでの実装も容易になるので、Linux 上での実装を目指して研究を進めていく。Xv6 で CbC が動けば、続けて Linux 上で Gears OS の実装も行なっていく。




\break



% \addcontentsline{toc}{chapter}{謝辞}
\chapter*{謝辞}
 \addcontentsline{toc}{chapter}{謝辞}
\label{chap:Acknowledgments}


%基本的な内容は以下の通り．参考にしてみて下さい．
%厳密な決まりは無いので，個々人の文体でも構わない．
%GISゼミや英語ゼミに参加した人はその分も入れておく．
%順番は重要なので気を付けるように．(提出前に周りの人に確認してもらう．)

\hspace{1zw}





\chapter*{参考文献}
\addcontentsline{toc}{chapter}{参考文献}
\label{chap:References}


%\bibitem{*}内の * は各自わかりやすい名前などをつけて、
%論文中には \cite{*} のように使用する。
%これをベースに書き換えた方が楽かも。
%書籍、論文、URLによって若干書き方が異なる。
%URLを載せる人は参考にした年月日を最後に記入すること。

% \begin{thebibliography}

% \bibitem{cbc}
% {徳森 海斗, 河野真治}: LLVM Clang 上の Continuation based C コンパイラの改良
% , 琉球大学工学部情報工学科平成 27 年度学位論文(修士) (2015).

% \end{thebibliography}


% \addcontentsline{toc}{chapter}{付録}
\chapter*{付録}
 \addcontentsline{toc}{chapter}{付録}










\end{document}