Mercurial > hg > Papers > 2017 > tobaru-midterm

comparison mid_thesis.tex @ 11:eb43376ecb12

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
今後の課題など追加
author tobaru
date Fri, 27 Oct 2017 18:31:05 +0900
parents cf9fc50057b3
children bf98aab22a60
comparison
equal deleted inserted replaced
10:cf9fc50057b3 11:eb43376ecb12
31 \thispagestyle{fancy} 31 \thispagestyle{fancy}
32 32
33 \section{Gears OS} 33 \section{Gears OS}
34 当研究室では、Code Segment と Data Segment によって構成される Gears OS の開発を行っている。Gears OS は、並列プログラミングフレームワークの Cerium と 分散フレームワークの Alice の開発を通して得られた知見を元に開発を進めている。 \\ 34 当研究室では、Code Segment と Data Segment によって構成される Gears OS の開発を行っている。Gears OS は、並列プログラミングフレームワークの Cerium と 分散フレームワークの Alice の開発を通して得られた知見を元に開発を進めている。 \\
35 Cerium はオブジェクト指向言語である C++ を用いて開発した並列プログラミングフレームワークである。Cell、マルチコアCPU、GPU を用いた並列実行をサポートしている。並列処理の単位として Task を記述し、Task に他の Task との依存関係を設定する事で並列実行を実現するが、データは汎用ポインタで Task に渡されるため、データの依存関係を保証できない。データの正しさや依存関係を保証できていないので、並列処理は行えるが、信頼性が低い。その知見から、並列分散処理 には Code の分割だけではなく Data の分割も必要である事が分かった。\\ 35 Cerium はオブジェクト指向言語である C++ を用いて開発した並列プログラミングフレームワークである。Cell、マルチコアCPU、GPU を用いた並列実行をサポートしている。並列処理の単位として Task を記述し、Task に他の Task との依存関係を設定する事で並列実行を実現するが、データは汎用ポインタで Task に渡されるため、データの依存関係を保証できない。データの正しさや依存関係を保証できていないので、並列処理は行えるが、信頼性が低い。その知見から、並列分散処理 には Code の分割だけではなく Data の分割も必要である事が分かった。\\
36 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 にそれぞれ対応する。\\ 36 % 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 にそれぞれ対応する。\\
37 Gears OS では 当研究室で開発している CbC を用いて Data Sement を定義し、実装を行っている。 37 Gears OS では 当研究室で開発している CbC を用いて Data Sement を定義し、実装を行っている。
38 %当研究室で開発している Code Segment を処理単位とする プログラミング言語 CbC を用いて Data Segment を定義し、Gears OS の実装を行っている。 38 %当研究室で開発している Code Segment を処理単位とする プログラミング言語 CbC を用いて Data Segment を定義し、Gears OS の実装を行っている。
39 39
40 40
41 \section{CbC} 41 \section{CbC}
43 CbC は Code Segment を基本的な処理単位とする。C の関数とは異なり返り値を持たないが、Code Segment の宣言は C の関数の構文と同じように行い、型に \_\_code を用いる。\\ 43 CbC は Code Segment を基本的な処理単位とする。C の関数とは異なり返り値を持たないが、Code Segment の宣言は C の関数の構文と同じように行い、型に \_\_code を用いる。\\
44 CbC は for 文や while 文といったループ制御構文を持たないので、ループ処理は自分自身への再帰的な継続を行う事で実現する。\\ 44 CbC は for 文や while 文といったループ制御構文を持たないので、ループ処理は自分自身への再帰的な継続を行う事で実現する。\\
45 現在の Code Segment から次の Code Segment への移動は goto の後に Code Segment 名と引数を並べて記述する。この goto による処理の遷移を継続と呼ぶ。C と異なり、戻り値を持たない Code Segment ではスタックに値を積んで行く必要が無くスタックは変更されない。このようなスタックに値を積まない継続を軽量継続と呼ぶ。この軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる。 45 現在の Code Segment から次の Code Segment への移動は goto の後に Code Segment 名と引数を並べて記述する。この goto による処理の遷移を継続と呼ぶ。C と異なり、戻り値を持たない Code Segment ではスタックに値を積んで行く必要が無くスタックは変更されない。このようなスタックに値を積まない継続を軽量継続と呼ぶ。この軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる。
46 46
47 47
48 \begin{figure}[htpb] 48 % \begin{figure}[htpb]
49 \begin{center} 49 % \begin{center}
50 \scalebox{0.5}{\includegraphics{pic/codesegment.pdf}} 50 % \scalebox{0.5}{\includegraphics{pic/codesegment.pdf}}
51 \end{center} 51 % \end{center}
52 \caption{goto による Code Segment 間の継続} 52 % \caption{goto による Code Segment 間の継続}
53 \label{fig:cs} 53 % \label{fig:cs}
54 \end{figure} 54 % \end{figure}
55 55
56 \section{Code Gear と Data Gear} 56 \section{Code Gear と Data Gear}
57 Gears OS では、プログラムの単位として Gear を用いる。Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 57 Gears OS では、プログラムの単位として Gear を用いる。Gear は並列実行の単位、データの分割、Gear 間の接続等になる。
58 Code Gear はプログラムの処理そのものであり、任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込む。Code Gear は接続された Data Gear 以外にアクセスできない。Code Segment と同じように Code Gear から次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定する事で実現できる。 58 Code Gear はプログラムの処理そのものであり、任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込む。Code Gear は接続された Data Gear 以外にアクセスできない。Code Segment と同じように Code Gear から次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定する事で実現できる。
59 Data Gear はデータそのものを表す。int や 文字列などの Primitive Data Type を持っている。Gear の特徴として処理やデータの構造が Code Gear、Data Gear に閉じている事にある。これにより、実行時間、メモリ使用量などを予測可能なものにすることができる。 59 Data Gear はデータそのものを表す。int や 文字列などの Primitive Data Type を持っている。Gear の特徴として処理やデータの構造が Code Gear、Data Gear に閉じている事にある。これにより、実行時間、メモリ使用量などを予測可能なものにすることができる。
62 % 接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear 等のためのメモリ空間を持っており、Context を通してアクセスすることができる。Context にはメインとなる Context と Worker 用の Context がある。Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉する事はできない。 62 % 接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear 等のためのメモリ空間を持っており、Context を通してアクセスすることができる。Context にはメインとなる Context と Worker 用の Context がある。Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉する事はできない。
63 63
64 64
65 65
66 66
67 \section{研究目的} 67 \section{Raspberry Pi 上の Gears OS}
68 本研究では、ARM で動くシングルボードコンピュータである Raspberry Pi 上で Gears OS を動かせるようになる事で、ハードウェア上でも信頼性があり、並列実行ができるプログラミングを を記述できるようになる事を目指している。\\ 68 本研究では、ARM で動くシングルボードコンピュータである Raspberry Pi 上で Gears OS を動かせるようになる事で、ハードウェア上でも信頼性があり、並列実行ができるプログラミングを を記述できるようになる事を目指している。\\
69 CbC を Raspberry Pi で動かすためのアプローチの手法を、I と T の形をした図の組み合わせによって説明を行う。I の上部分に cbclang や Xv6 などのソースコード名を、下部分にその機能の記述言語を記してある。T の下にある I は特別で、上に VM 下に VM を乗せている OS が記されている。 T の上部分は左に入力されるファイル、右に出力されるその機能によって出力されるファイルが記され、下部分にその機能の記述言語が記されている。\\ 69 CbC を Raspberry Pi で動かすためのアプローチの手法を、I と T の形をした図の組み合わせによって説明を行う。I の上部分に cbclang や Xv6 などのソースコード名を、下部分にその機能の記述言語を記してある。T の下にある I は特別で、上に VM 下に VM を乗せている OS が記されている。 T の上部分は左に入力されるファイル、右に出力されるその機能によって出力されるファイルが記され、下部分にその機能の記述言語が記されている。\\
70 例として、cbclang のソースコード(I)と、 Raspberry Pi 上の clang (T) を図\ref{fig:examples} に示す。 70 例として、cbclang のソースコード(I)と、 Raspberry Pi 上の clang (T) を図\ref{fig:examples} に示す。
71 71
72 \begin{figure}[htpb] 72 \begin{figure}[htpb]
79 79
80 80
81 81
82 82
83 \section{Raspberry Pi 上での実装} 83 \section{Raspberry Pi 上での実装}
84 Raspberry Pi の OS である Raspbian ではメモリが 256MB なので Raspberry Pi 上で直接 CbC をコンパイルするには時間がかかる。qemu によるメモリの拡張もできないので、別の手法で Raspberry Pi 上に CbC を実装する方が好ましい。\\ 84 % Raspberry Pi の OS である Raspbian ではメモリが 256MB なので Raspberry Pi 上で直接 CbC をコンパイルするには時間がかかる。qemu によるメモリの拡張もできないので、別の手法で Raspberry Pi 上に CbC を実装する方が好ましい。\\
85 Raspberry Pi 1 では、メモリが足りないため CbC をコンパイルすることができない。Raspberry Pi 3 だとコンパイルできるが、時間がかかる。qemu によるメモリの拡張もできないので、別の手法で Raspberry Pi 上に CbC を実装する方が好ましい。\\
86
85 Raspberry Pi でコンパイルを行うまでの過程を、図\ref{fig:RaspberryPi}に示す。 87 Raspberry Pi でコンパイルを行うまでの過程を、図\ref{fig:RaspberryPi}に示す。
86 88
87 \begin{figure}[htpb] 89 \begin{figure}[htpb]
88 \begin{center} 90 \begin{center}
89 \scalebox{0.17}{\includegraphics{pic/RaspberryPi_2.pdf}} 91 \scalebox{0.17}{\includegraphics{pic/RaspberryPi_2.pdf}}
94 96
95 97
96 98
97 99
98 \section{LLVM CrossCompile} 100 \section{LLVM CrossCompile}
99 Raspberri pi 上ではコンパイルするためのメモリが足りないので、OSX 上で CrossCompile する事でこの問題を解決する方法がある。\\ 101 OSX 上で CrossCompile する事でコンパイルの時間の問題を解決する方法がある。\\
100 CrossCompile とは、別の OS で実行可能なコードを生成するコンパイルの手法である。つまり、OSX であらかじめ Raspberry Pi で CbC が動くように CrossCompile を行い、そのコードを Raspberry Pi に移せばよい。\\ 102 % CrossCompile とは、別の OS で実行可能なコードを生成するコンパイルの手法である。つまり、OSX であらかじめ Raspberry Pi で CbC が動くように CrossCompile を行い、そのコードを Raspberry Pi に移せばよい。\\
101 arm-linux-gnueabihf-gcc を使用し、C で書かれたファイルを CrossCompile することで ARM のコードを生成できる事を確認した。CbC でも CrossCompile できるコンパイラを書く必要がある。OSX 上で コンパイルを行うまでの過程を、図\ref{fig:OSX}に示す。 103 CrossCompile とは、別の OS で実行可能なコードを生成するコンパイルの手法である。
104 arm-linux-gnueabihf-gcc を使用し、C で書かれたファイルを CrossCompile することで ARM のコードを生成できる事を確認した。この時、出力は mach-o になるので、mach-o の loader 作ることで Raspberry Pi で動かせるようになる。\\
105 まだ実装できていないが、OSX 上で行えるためコンパイルの速度向上が望める。
106 OSX 上で コンパイルを行うまでの過程を、図\ref{fig:OSX}に示す。
102 107
103 \begin{figure}[htpb] 108 \begin{figure}[htpb]
104 \begin{center} 109 \begin{center}
105 \scalebox{0.35}{\includegraphics{pic/OSX_2.pdf}} 110 \scalebox{0.35}{\includegraphics{pic/OSX_2.pdf}}
106 \end{center} 111 \end{center}
109 \end{figure} 114 \end{figure}
110 115
111 116
112 117
113 \section{仮想マシン} 118 \section{仮想マシン}
114 CrossCompile と別に linux 環境で CbC を動かした後に、Raspberry Pi に載せる手法がある 119 CrossCompile と別に Linux 環境で CbC を動かした後に、Raspberry Pi に載せる手法がある。\\
115 LLVM を動かす際に、オプションで target を指定する事で、ARM のコードを生成することができる。\\ 120 Linux の LLVM でコンパイルすることができれば elf のコードを書けるようになるので、elf のloader を作る事で、Raspberry Pi で動くようになる。\\
116 linux 用の gcc を CbC に書き直す際に、gcc7 に書き直せば linker がそのまま使えるので、xv6 で動くようになる。\\ 121 また、Linux 用の gcc を CbC に書き直す際に、gcc7 に書き直せば linker がそのまま使えるので、Xv6 で動くようになる。\\
117 xv6とは、マサチューセッツ工科大の大学院生向け講義の教材として使うために、UNIX V6 という OS を ANSI-C に書き換え、x86に移植した OS である。 122 Xv6とは、マサチューセッツ工科大の大学院生向け講義の教材として使うために、UNIX V6 という OS を ANSI-C に書き換え、x86に移植した OS である。
118 xv6 は Raspberry Pi に移植する事ができる。ANSI-C で書かれている xv6 を CbC に書き直す事で、Raspberry Pi で CbC を動かせるようになる。Linux 上で コンパイルを行うまでの過程を、図\ref{fig:OSX_Linux_VM}に示す 123 Xv6 は Raspberry Pi に移植する事ができる。ANSI-C で書かれている Xv6 を CbC に書き直す事で、Raspberry Pi で CbC を動かせるようになる。\\
124 Linux 上 で LLVM がコンパイルできない原因はまだ分かってないが、メモリを上げる事でこの方法でもコンパイルの速度向上が望める。
125 Linux 上で コンパイルを行うまでの過程を、図\ref{fig:OSX_Linux_VM}に示す
119 126
120 \begin{figure}[htpb] 127 \begin{figure}[htpb]
121 \begin{center} 128 \begin{center}
122 \scalebox{0.5}{\includegraphics{pic/OSX_Linux_VM_2.pdf}} 129 \scalebox{0.5}{\includegraphics{pic/OSX_Linux_VM_2.pdf}}
123 \end{center} 130 \end{center}
124 \caption{OSX Linux VM} 131 \caption{OSX Linux VM}
125 \label{fig:OSX_Linux_VM} 132 \label{fig:OSX_Linux_VM}
126 \end{figure} 133 \end{figure}
127 134
135 % Xv6詳しく
128 136
129 % xv6詳しく 137 \section{今後の課題}
138 Xv6 で CbC が動くようになれば、Raspberry Pi 以外のハードウェアでの実装も容易になるので、Linux 上での実装を目指して研究を進めていく。Xv6 で CbC が動けば、続けて Linux 上で Gears OS の実装も行なっていく。
130 139
131 140
132 % \section{clang のバージョンアップ} 141 % \section{clang のバージョンアップ}
133 % CbC はバージョン 3.9 の clang を使用している。現在のバージョンの LLVM と clang を使用して、CbCをコンパイラできるように修正を加える必要がある。 142 % CbC はバージョン 3.9 の clang を使用している。現在のバージョンの LLVM と clang を使用して、CbCをコンパイラできるように修正を加える必要がある。
134 143