Mercurial > hg > Papers > 2018 > parusu-master

annotate paper/gearsOS.tex @ 2:b3fc9cc0d85f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add section
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Sun, 07 Jan 2018 05:22:05 +0900
parents
children 86340b0bf212
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \chapter{Gears OS}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \section{Code GearとData Gear}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 Gears OS はプログラムとデータの単位として Gear を用いる。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 Gear は並列実行の単位、データの分割、Gear 間の接続等になる。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 Code Gear はプログラムの処理そのもので、任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 また、Code Gear は接続された Data Gear 以外には参照を行わない。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Gears OS では \figref{codegear-datagear} で示しているように Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 Code Gear 間の移動は継続を用いて行われる。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 継続は関数呼び出しとは異なり、呼び出し元に戻らず、Code Gear 内で次の Code Gear への継続を行う。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 そのため Code Gear, Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 \begin{figure}[htbp]
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \begin{center}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 \includegraphics[scale=1.0]{./fig/codegear-datagear.pdf}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 \end{center}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 \caption{Code Gear と Data Gear の依存関係}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 \label{fig:codegear-datagear}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 \end{figure}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 \section{Continuation based C}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 Gears OS の実装は本研究室で開発されているCbC(Continuation based C) を用いて行う。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 CbC の記述例を\coderef{cg1}に, 実際にこのソースコードが実行される際の遷移を\figref{cg1}に示す。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 CbC の Code Gear は \_\_code という型を持つ関数として記述する。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 Code Gear は継続で次の Code Gear に遷移する性質上、関数とは違い戻り値は持たない。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 そのため、\_\_code は Code Gear の戻り値ではなく、Code Gear であることを示すフラグとなっている。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 Code Gear から次の Code Gear への遷移は goto による継続で処理を行い、次の Code Gear への引数として入出力を与える。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 \coderef{cg1}内の goto cg1(a+b); が継続にあたり、(a+b) がcg1 への入力になる。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 CbC の goto による継続は Scheme の継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 したがって、この継続を軽量継続と呼ぶ。
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 \lstinputlisting[caption=CodeSegmentの軽量継続, label=code:cg1]{./src/cg1.cbc}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 \begin{figure}[htbp]
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 \begin{center}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 \includegraphics[scale=1.0]{./fig/goto.pdf}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 \end{center}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 \caption{goto による Code Gearの軽量継続}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 \label{fig:cg1}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 \end{figure}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 \section{Meta Computation}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 \section{Context}
b3fc9cc0d85f Add section
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 \section{Interface}