# HG changeset patch # User mir3636 # Date 1492777416 -32400 # Node ID e04e25ad2f3c90da05cb29b47bad26101c6a2a8e # Parent 0f3881e77256cfb11b5be7ca9b01afafa5daedd4 update diff -r 0f3881e77256 -r e04e25ad2f3c paper/sigos.aux --- a/paper/sigos.aux Fri Apr 21 19:20:00 2017 +0900 +++ b/paper/sigos.aux Fri Apr 21 21:23:36 2017 +0900 @@ -3,20 +3,20 @@ \citation{gears} \newlabel{fig:cs}{{1}{2}} \newlabel{fig:gearsos}{{2}{2}} -\newlabel{excbc}{{1}{2}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {1}cbccode}{2}} -\newlabel{interface}{{2}{3}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {2}interface}{3}} -\newlabel{gearef1}{{3}{3}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {3}Gearef1}{3}} -\newlabel{gearef2}{{4}{3}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4}Gearef2}{3}} -\newlabel{stack_cbc}{{5}{3}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {5}exampleCG}{3}} -\newlabel{stack_c}{{6}{3}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {6}stub}{3}} -\newlabel{context}{{7}{4}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {7}context}{4}} +\newlabel{context}{{1}{2}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {1}context}{2}} +\newlabel{excbc}{{2}{3}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {2}cbccode}{3}} +\newlabel{interface}{{3}{3}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3}interface}{3}} +\newlabel{gearef1}{{4}{3}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4}Gearef1}{3}} +\newlabel{gearef2}{{5}{3}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {5}Gearef2}{3}} +\newlabel{stack_cbc}{{6}{4}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {6}exampleCG}{4}} +\newlabel{stack_c}{{7}{4}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {7}stub}{4}} \newlabel{init_context}{{8}{4}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {8}initcontext}{4}} \citation{*} diff -r 0f3881e77256 -r e04e25ad2f3c paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r 0f3881e77256 -r e04e25ad2f3c paper/sigos.log --- a/paper/sigos.log Fri Apr 21 19:20:00 2017 +0900 +++ b/paper/sigos.log Fri Apr 21 21:23:36 2017 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.2.4) 21 APR 2017 19:04 +This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.2.4) 21 APR 2017 19:44 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -207,44 +207,44 @@ File: ./pic/gears_structure.pdf Graphic file (type pdf) <./pic/gears_structure.pdf> LaTeX Font Info: Font shape `OT1/cmtt/bx/n' in size <7> not available -(Font) Font shape `OT1/cmtt/m/n' tried instead on input line 201. +(Font) Font shape `OT1/cmtt/m/n' tried instead on input line 186. + [2] +Overfull \hbox (66.99287pt too wide) in paragraph at lines 186--186 +[]\OT1/cmr/m/n/9 context + [] -Overfull \hbox (69.04842pt too wide) in paragraph at lines 201--201 + +Overfull \hbox (69.04842pt too wide) in paragraph at lines 207--207 []\OT1/cmr/m/n/9 cbccode [] -[2] -Overfull \hbox (71.64214pt too wide) in paragraph at lines 236--236 + +Overfull \hbox (71.64214pt too wide) in paragraph at lines 245--245 []\OT1/cmr/m/n/9 interface [] -Overfull \hbox (68.36577pt too wide) in paragraph at lines 252--252 +Overfull \hbox (68.36577pt too wide) in paragraph at lines 261--261 []\OT1/cmr/m/n/9 Gearef1 [] - -Overfull \hbox (68.36577pt too wide) in paragraph at lines 253--253 +[3] +Overfull \hbox (68.36577pt too wide) in paragraph at lines 262--262 []\OT1/cmr/m/n/9 Gearef2 [] -Overfull \hbox (84.27539pt too wide) in paragraph at lines 276--276 +Overfull \hbox (84.27539pt too wide) in paragraph at lines 285--285 []\OT1/cmr/m/n/9 exampleCG [] -[3] -Overfull \hbox (54.70755pt too wide) in paragraph at lines 277--277 + +Overfull \hbox (54.70755pt too wide) in paragraph at lines 286--286 []\OT1/cmr/m/n/9 stub [] - -Overfull \hbox (66.99287pt too wide) in paragraph at lines 283--283 -[]\OT1/cmr/m/n/9 context - [] - [4] -Overfull \hbox (80.86778pt too wide) in paragraph at lines 299--299 +Overfull \hbox (80.86778pt too wide) in paragraph at lines 306--306 []\OT1/cmr/m/n/9 initcontext [] @@ -252,10 +252,10 @@ Here is how much of TeX's memory you used: 3187 strings out of 493683 43727 string characters out of 6149654 - 372711 words of memory out of 5000000 + 325711 words of memory out of 5000000 6739 multiletter control sequences out of 15000+600000 18451 words of font info for 72 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 30i,10n,49p,213b,1567s stack positions out of 5000i,500n,10000p,200000b,80000s + 30i,10n,49p,213b,1628s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on sigos.dvi (5 pages, 47052 bytes). +Output written on sigos.dvi (5 pages, 47512 bytes). diff -r 0f3881e77256 -r e04e25ad2f3c paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 0f3881e77256 -r e04e25ad2f3c paper/sigos.tex --- a/paper/sigos.tex Fri Apr 21 19:20:00 2017 +0900 +++ b/paper/sigos.tex Fri Apr 21 21:23:36 2017 +0900 @@ -98,13 +98,23 @@ % きょだいなCDGの上で動かすと既存のアプリケーションを動かすことができる \section{メタ計算の重要性} +% 今ま プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理、スレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。 これらの計算をメタ計算と呼ぶ。 -メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。 +従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。 +実行時にメタ計算の変更を行う場合には、OS 内部のパラメータの変更を使用し、 +実行されるユーザープログラム自体への変更は限定的である。 +しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で +実際のシステムコール単位では不十分である。 +例えば、モデル検査ではアセンブラあるいはバイトコード、インタプリタレベルでのメタ計算が必要になる。 +しかし、バイトコードレベルでは粒度が細かすぎて扱いが困難になっている。 +具体的にはメタ計算の実行時間が大きくなってしまう。 +メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。 そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。 +これによりシステムコードよりも細かくバイトコードよりも大きなメタ計算の単位を提供できる。 Code Gear は処理の単位である。 関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。 @@ -115,8 +125,38 @@ CbCは軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。 また、当研究室で開発している Gears OS\cite{gears} は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。 +CbC での記述はメタ計算を含まないノーマルレベルでの記述と、 Code Gear、Data Gear の記述を含むメタレベルの記述の2種類がある。 +メタレベルでもさらに、メタ計算を用いることが可能になっている。 +この2つのレベルはプログラミング言語レベルでの変換として実現される。 +CbC は LLVM 上で実装されており、メタレベルでの変換系は本論文では、Perl による変換スクリプトにより実装されている。 -本研究では CbC を用いての Gears OS の実装と Gears OS におけるメタ計算の自動生成を行なう。 +Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。 +Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。 +Interface は複数の実装を持つことができ、Meta Data Gear によって定義される。 +Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。 + +従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call する。 +Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、 +操作に対応する Code Gear に goto する。 +Context とは使用される Code Gear と Data Gear を全て格納している Meta Data Gear である。 +これは従来のスレッド構造体に対応する。 +つまり Gears OS では従来はコンパイラが定義する ABI(Aplication Binary Interface) +を Meta Data Gear として CbC で表現し、メタ計算として操作することができる。 + +ノーマルレベルでは Context を直接見ることはできず、引数は Code Gear の引数を明示する必要がある。 +この時に呼び出し側の引数を不定長引数として追加する構文を CbC に追加した。 +これにより Interface 間の呼び出しを簡潔に記述することが出来るようになった。 +メタレベルでは Code Gear の引数は単一または複数の Data Gear として見ることができる。 +これは Context を直接操作することができることを意味する。 +この部分はノーマルレベルの Code Gear を呼び出す stub として生成される。 +ノーマルレベルでの goto 文はメタ計算への goto で置き換えられる。 +Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。 + +メタ計算の例としては並列処理があり、Context を切り替えることによって複数のスレッドを実現している。 +Context を複数の CPU に割り当てることにより並列実行を可能にしている。 + + +本研究では CbC を用いての Gears OS の実装と Gears OS におけるメタ計算(Context と stub)の自動生成の実装について述べる。 \section{Continuation based C (CbC)} CbC は Code Gear という処理の単位を用いて記述するプログラミング言語である。 @@ -180,9 +220,15 @@ \label{fig:gearsos} \end{figure} -Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。 +Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear を持つ。 Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。 +\lstinputlisting[label=context, caption=context]{./src/context1.c} + +Data Gear は union と struct によって表現される。 +Context には Data Gear の Data Type の情報が格納されている。 +この情報から確保する Data Gear のサイズなどを決定する。 + Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。 Context は Task でもあり、TaskManager によって Context が生成され Task Queue へ挿入する。 Gears OS における Task Queue は Synchronized Queue で実現される。 @@ -190,7 +236,7 @@ -\section{cbc のコードの例} +\section{CbC のコードの例} リスト\ref{excbc}は CbC で記述された stack のコードの一部である。 Code Gear は \_\_code Code Gear で始まり、次の Code Gear へ goto で遷移する。 @@ -227,6 +273,10 @@ interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。 +呼び出される Code Gear の引数となる Data Gear はここで全て定義される。 + + + Code Gear、Data Gear に参照するために Context を通す必要があるが、 interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。 %create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。 @@ -270,22 +320,20 @@ generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。 また、この時既に stub Code Gear が記述されている Code Gear は無視される。 -cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(\ref{stack_c}) +cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(Code\ref{stack_c}) \lstinputlisting[label=stack_cbc, caption=exampleCG]{./src/ex_cbc} \lstinputlisting[label=stack_c, caption=stub]{./src/ex_stub} \section{Context の生成} Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。 -Data Gear を取得するために generate context は context の定義 (リスト\ref{context}) を読み宣言されている Data Gear を取得する。 - -\lstinputlisting[label=context, caption=context]{./src/context1.c} +Data Gear を取得するために generate context は context の定義 (Code\ref{context}) を読み宣言されている Data Gear を取得する。 Code Gear の取得は指定された generate\_stub で生成されたコードから \_\_code 型を見て行う。 取得した Code Gear、Data Gear の enum の定義は enumCode.h、enumData.h に生成される。 Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。 -また、generate context は取得した Code/Data Gear から Context の生成を行うコード (リスト\ref{init_context}) も生成する。 +また、generate context は取得した Code/Data Gear から Context の生成を行うコード (Code\ref{init_context}) も生成する。 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 Code Gear は Context を通して Data Gear へアクセスする。