\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{平成29年度 卒業論文}
\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と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 を行う方法を提案する。


% compiler-rt 書く

\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 をmakeすることができない。
Raspberry Pi 3 だとメモリは 1GB あり CbC をmakeできるが、時間がかかる。



make時間の比較として研究室のサーバでメモリ16GBのfireflyと学科のサーバの一つでLinux環境であるメモリ756GBのDALMOREを用いる。
なお、fireflyとDALMOREではGoogleによって開発されたbuildシステムのninja-buildを用いてmakeを行なった。その結果を表\ref{tab:make_time}に示す。

% ninja

\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(756GB) & 2分26秒 & 374.42倍 \\ \hline
  \end{tabular}
  }
   \caption{make時間の比較}
 \label{tab:make_time}
\end{table}



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

\break



\chapter{CrossCompile}
\label{chap:CrossCompile}

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

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

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


\section{xv6}
  マサチューセッツ工科大の大学院生向け講義の教材として使うために、UNIX V6 という OS を 
  ANSI-C に書き換え、x86に移植したXv6 OS である。
Xv6 は Raspberry Pi に移植する事ができる。ANSI-C で書かれている Xv6 を CbC に書き直す事で、
Raspberry Pi で CbC を動かせるようになる。




\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


% xv6で書き直す場合


Raspberry Pi は ARM のコードを生成する。CbCはCによって記述されているため、Cから ARM.o を生成し、ARM.o から a.out を出力する。
Raspberry Pi 上でxv6を実装し、cbcからa.outを出力するまでの過程を図\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}




\chapter{OSX}
\label{chap:OSX}
  
  
\section{LLVM}
% これはELFのコード吐いただけ


arm-linux-gnueabihf-gcc というツールチェーンを使用し、C で書かれたファイルを CrossCompile することで OSXで
 ARM のコードを生成できる事を確認した。その際のコマンドをリスト\ref{OSXCrossCompile}に、生成されたファイルにfileコマンドで調べた結果をリスト\ref{OSXfile}に示す。
 % arm-linux-gnueabihf-gcc がなにをするためのツールチェーンか詳しく書く
 
 \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}

このファイルは Raspberry Pi 上で実行する事ができる。


\section{GCC}



\break

\section{xv6}
% 上のCrossCompileと別にxv6で実装する場合

OSX上でxv6を実装する場合、Cから mach-o のバイナリファイルが生成される。 
 この時、出力は mach-o になるので、mach-o の 
 loader 作ることで CbC が動かせるようになる。
 
 OSX 上で行えるためコンパイルの速度向上が望める。
xv6を実装しCbCからa.outを出力するまでの過程を、図\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}




\break

\chapter{Linux}
\section{LLVM}

 Linux の LLVM でコンパイルすることができれば elf のコードを書けるようになるので、
 elf のloader を作る事で、CbC を動かすことができる。


C言語で記述されたファイルからRaspberryPiで実行できるファイルを実行できるようにCrossCompileを行なった際のコマンドをCode\ref{LinuxCCrossCompile}に示す。




 \begin{lstlisting}[frame=lrbt,label=LinuxCCrossCompile,caption={Linux上でC言語ファイルの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}

コマンドの説明は次のようになる。
\begin{itemize}
  \item arm-linux-gnueabi は apt でインストールでき、/net/open/Linux/arm/ に展開される。-I オプションでそのディレクトリを読み込む。
  \item targetオプションでarm-linux-gnueabiを指定することで、armのコードを生成している。
  \item mfpu=neon-fp16 はARMv7の浮動小数点を有効にしている。
  \item marmでARMの命令セットをターゲットにしている。
  \item mfloat-abi=hard は浮動小数点演算にハードウェア命令を使用する
\end{itemize}

\break

また、make する際に、Cross環境を整える事でCompileする度にCode\ref{LinuxCCrossCompile}のようなコマンドを省略することができる。
Makefile の一部をCode\ref{LinuxLLVMmake} に示す。

 \begin{lstlisting}[frame=lrbt,label=LinuxLLVMmake,caption={Linux上のLLVM makeファイル}]
 QEMU = qemu-system-arm

include makefile.inc
CC = /usr/local/cbclang/bin/clang
AS = arm-linux-gnu-as
LD = arm-linux-gnu-ld
OBJCOPY = arm-linux-gnu-objcopy
OBJDUMP = arm-linux-gnu-objdump

CFLAGS = -target armv6-arm-none-eabi -fno-pic -static -fno-builtin -fno-strict-aliasing -Wall -I. -I ../cbclang/arm -g -O0


ASFLAGS = -target armv6-arm-none-eabi

LIBGCC = $(shell $(CC) $(CFLAGS) -print-libgcc-file-name)
 \end{lstlisting}

\begin{itemize}
  \item CC はコンパイラで、すでにmakeしたCbCのディレクトリを指定している。
  \item ASはアセンブラ、LDはリンカーで、それぞれarm-linux-gnuを指定してあげればよい。
% CFLAGS と ASFLAGSについても書く
  \item CFLAGS
  \item ASFLAGS
\end{itemize}


\break


\section{GCC}
% これもCrossCompileなので書き直す
% CrossCompile と別に Linux 環境で CbC を動かした後に、Raspberry Pi に載せる手法がある。


 

  

 \begin{lstlisting}[frame=lrbt,label=Linux_GCC_CrossCompile,caption={LinuxでのGCC CrossCompile}]
QEMU = qemu-system-arm

include makefile.inc
CC = arm-linux-gnu-gcc
AS = arm-linux-gnu-as
LD = arm-linux-gnu-ld
OBJCOPY = arm-linux-gnu-objcopy
OBJDUMP = arm-linux-gnu-objdump

CFLAGS = -fno-pic -static -fno-builtin -fno-strict-aliasing -Wall -I. -g -O0

ASFLAGS =

LIBGCC = $(shell $(CC) -print-libgcc-file-name)

LINK_BIN = $(call quiet-command,$(LD) $(LDFLAGS) \
        -T $(1) -o $(2) $(3) $(LIBS) -b binary $(4), "  LINK     $(TARGET_DIR)$@")

LINK_INIT = $(call quiet-command,$(LD) $(LDFLAGS) \
        $(1) -o $@.out $<, "  LINK     $(TARGET_DIR)$@")
OBJCOPY_INIT = $(call quiet-command,$(OBJCOPY) \
        -S -O binary --prefix-symbols="_binary_$@" $@.out $@, "  OBJCOPY  $(TARGET_DIR)$@")
\end{lstlisting}

\begin{itemize}
  \item CC はコンパイラで、すでにmakeしたCbCのディレクトリを指定している。
  \item ASはアセンブラ、LDはリンカーで、それぞれarm-linux-gnuを指定してあげればよい。
% CFLAGS と ASFLAGSについても書く
  \item CFLAGS
  \item ASFLAGS
\end{itemize}

なお、 Linux 用の gcc を CbC に書き直す際に、gcc7 に書き直せば linker がそのまま使えるので、
  xv6 で動くようになる。

\break 

\section{xv6} 
  メモリを割く事でLinux上でもコンパイルの速度向上が望める。 
  CbCはCによって記述されているので、Cから ARM.oのバイナリを生成し、ARM.oからa.outを出力する。
OSX上に立ち上げたLinux 上で xv6を実装するまでの過程を、図\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}






\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}