Mercurial > hg > Papers > 2011 > nobu-thesis

changeset 6:a0bf68477575

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix by kono
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Fri, 18 Nov 2011 19:31:32 +0900
parents b61dbe81b48c
children 24b02780ca8f
files nobu-graduation.dvi nobu-graduation.log nobu-graduation.pdf nobu-midthesis.tex
diffstat 4 files changed, 109 insertions(+), 108 deletions(-) [+]
line wrap: on
line diff
Binary file nobu-graduation.dvi has changed
--- a/nobu-graduation.log	Fri Nov 18 18:48:55 2011 +0900
+++ b/nobu-graduation.log	Fri Nov 18 19:31:32 2011 +0900
@@ -1,22 +1,11 @@
-This is e-pTeX, Version 3.1415926-p3.2-110415-2.3 (utf8.euc) (TeX Live 2011) (format=platex 2011.11.10)  18 NOV 2011 08:31
-entering extended mode
- restricted \write18 enabled.
- %&-line parsing enabled.
+This is pTeX, Version 3.141592-p3.1.10 (utf8.euc) (Web2C 7.5.4) (format=platex 2011.8.15)  18 NOV 2011 18:03
 **nobu-graduation.tex
 (./nobu-graduation.tex
-pLaTeX2e <2006/11/10> (based on LaTeX2e <2009/09/24> patch level 0)
-Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, af
-rikaans, arabic, basque, bulgarian, catalan, pinyin, croatian, czech, danish, d
-utch, ukenglish, usenglishmax, esperanto, estonian, farsi, finnish, french, gal
-ician, german, ngerman, swissgerman, hungarian, icelandic, indonesian, interlin
-gua, irish, italian, kurmanji, latin, latvian, lithuanian, mongolian, mongolian
-lmc, bokmal, nynorsk, polish, portuguese, romanian, russian, serbian, serbianc,
- slovak, slovenian, spanish, swedish, turkish, turkmen, ukrainian, uppersorbian
-, welsh, ancientgreek, ibycus, monogreek, greek, coptic, loaded.
-(/usr/local/texlive/2011/texmf-dist/tex/platex/base/jarticle.cls
+pLaTeX2e <2006/11/10>+0 (based on LaTeX2e <2003/12/01> patch level 0)
+(/usr/local/share/texmf/ptex/platex/base/jarticle.cls
 Document Class: jarticle 2006/06/27 v1.6 Standard pLaTeX class
 \c@@paper=\count81
-(/usr/local/texlive/2011/texmf-dist/tex/platex/base/jsize10.clo
+(/usr/local/share/texmf/ptex/platex/base/jsize10.clo
 File: jsize10.clo 2006/06/27 v1.6 Standard pLaTeX file (size option)
 )
 \c@part=\count82
@@ -37,33 +26,33 @@
 \bibindent=\dimen120
 \heisei=\count90
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/graphics/graphicx.sty
+(/usr/local/share/texmf-dist/tex/latex/graphics/graphicx.sty
 Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR)
 
-(/usr/local/texlive/2011/texmf-dist/tex/latex/graphics/keyval.sty
+(/usr/local/share/texmf-dist/tex/latex/graphics/keyval.sty
 Package: keyval 1999/03/16 v1.13 key=value parser (DPC)
 \KV@toks@=\toks15
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/graphics/graphics.sty
-Package: graphics 2009/02/05 v1.0o Standard LaTeX Graphics (DPC,SPQR)
+(/usr/local/share/texmf/tex/latex/graphics/dvipdfmx-contrib-latex/graphics.sty
+Package: graphics 2001/07/07 v1.0n Standard LaTeX Graphics (DPC,SPQR)
 
-(/usr/local/texlive/2011/texmf-dist/tex/latex/graphics/trig.sty
+(/usr/local/share/texmf-dist/tex/latex/graphics/trig.sty
 Package: trig 1999/03/16 v1.09 sin cos tan (DPC)
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/latexconfig/graphics.cfg
-File: graphics.cfg 2010/04/23 v1.9 graphics configuration of TeX Live
+(/usr/local/share/texmf-dist/tex/latex/graphics/graphics.cfg
+File: graphics.cfg 2005/02/03 v1.3 graphics configuration of teTeX/TeXLive
 )
-Package graphics Info: Driver file: dvips.def on input line 91.
+Package graphics Info: Driver file: dvips.def on input line 81.
 
-(/usr/local/texlive/2011/texmf-dist/tex/latex/graphics/dvips.def
+(/usr/local/share/texmf-dist/tex/latex/graphics/dvips.def
 File: dvips.def 1999/02/16 v3.0i Driver-dependant file (DPC,SPQR)
 ))
 \Gin@req@height=\dimen121
 \Gin@req@width=\dimen122
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/url/url.sty
+(/usr/local/share/texmf/ptex/latex/url/url.sty
 \Urlmuskip=\muskip10
-Package: url 2006/04/12  ver 3.3  Verb mode for urls, etc.
+Package: url 2004/03/15  ver 3.1  Verb mode for urls, etc.
 ) (./picins.sty
 Option `picins' Version 3.0 Sep. 1992, TH Darmstadt/HRZ
 \@BILD=\box41
@@ -110,7 +99,7 @@
 \c@envdp=\count112
 \d@envb=\dimen139
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/fancyhdr/fancyhdr.sty
+(/usr/local/share/texmf-dist/tex/latex/fancyhdr/fancyhdr.sty
 \fancy@headwidth=\skip44
 \f@ncyO@elh=\skip45
 \f@ncyO@erh=\skip46
@@ -121,7 +110,7 @@
 \f@ncyO@olf=\skip51
 \f@ncyO@orf=\skip52
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/listings.sty
+(/usr/local/share/texmf-dist/tex/latex/listings/listings.sty
 \lst@mode=\count113
 \lst@gtempboxa=\box44
 \lst@token=\toks16
@@ -133,24 +122,28 @@
 \lst@width=\dimen142
 \lst@newlines=\count117
 \lst@lineno=\count118
+\c@lstlisting=\count119
 \lst@maxwidth=\dimen143
 
-(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/lstmisc.sty
-File: lstmisc.sty 2007/02/22 1.4 (Carsten Heinz)
-\c@lstnumber=\count119
-\lst@skipnumbers=\count120
+(/usr/local/share/texmf-dist/tex/latex/listings/lstpatch.sty
+File: lstpatch.sty 2004/10/17 1.3b (Carsten Heinz)
+)
+(/usr/local/share/texmf-dist/tex/latex/listings/lstmisc.sty
+File: lstmisc.sty 2004/09/07 1.3 (Carsten Heinz)
+\c@lstnumber=\count120
+\lst@skipnumbers=\count121
 \lst@framebox=\box45
 )
-(/usr/local/texlive/2011/texmf-dist/tex/latex/listings/listings.cfg
-File: listings.cfg 2007/02/22 1.4 listings configuration
+(/usr/local/share/texmf-dist/tex/latex/listings/listings.cfg
+File: listings.cfg 2004/09/05 1.3 listings configuration
 ))
-Package: listings 2007/02/22 1.4 (Carsten Heinz)
+Package: listings 2004/10/17 1.3b (Carsten Heinz)
 
 
 LaTeX Warning: Unused global option(s):
     [9.5pt].
 
-(./nobu-graduation.aux)
+No file nobu-graduation.aux.
 \openout1 = `nobu-graduation.aux'.
 
 LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 22.
@@ -169,7 +162,6 @@
 LaTeX Font Info:    ... okay on input line 22.
 LaTeX Font Info:    Checking defaults for JT1/mc/m/n on input line 22.
 LaTeX Font Info:    ... okay on input line 22.
-\c@lstlisting=\count121
 LaTeX Font Info:    External font `cmex10' loaded for size
 (Font)              <12> on input line 26.
 LaTeX Font Info:    External font `cmex10' loaded for size
@@ -184,17 +176,22 @@
 (Font)              Font shape `JT1/gt/m/n' tried instead on input line 50.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <12> not available
 (Font)              Font shape `JY1/gt/m/n' tried instead on input line 50.
-File: figure/codesegment.eps Graphic file (type eps)
- <figure/codesegment.eps>
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <10> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 86.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 54.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <10> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 86.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 54.
+
+LaTeX Warning: Reference `fig:cs' on page 1 undefined on input line 54.
+
+File: figure/codesegment.eps Graphic file (type eps)
+<figure/codesegment.eps>
+
+LaTeX Warning: Reference `fig:continue' on page 1 undefined on input line 91.
+
 File: figure/continuation.eps Graphic file (type eps)
- <figure/continuation.eps>
+<figure/continuation.eps>
 File: pic/emblem-bitmap.eps Graphic file (type eps)
-
-<pic/emblem-bitmap.eps>
+ <pic/emblem-bitmap.eps>
 
 Package Fancyhdr Warning: \headheight is too small (0.0pt): 
  Make it at least 20.37784pt.
@@ -211,7 +208,7 @@
 
 LaTeX Font Info:    Try loading font information for OMS+cmr on input line 121.
 
-(/usr/local/texlive/2011/texmf-dist/tex/latex/base/omscmr.fd
+(/usr/local/share/texmf-dist/tex/latex/base/omscmr.fd
 File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions
 )
 LaTeX Font Info:    Font shape `OMS/cmr/m/n' in size <10> not available
@@ -232,12 +229,12 @@
 
  ) 
 Here is how much of TeX's memory you used:
- 2134 strings out of 494163
- 28438 string characters out of 3160585
- 90636 words of memory out of 3000000
- 5546 multiletter control sequences out of 15000+200000
- 13716 words of font info for 53 fonts, out of 3000000 for 9000
- 745 hyphenation exceptions out of 8191
- 27i,15n,43p,208b,1257s stack positions out of 5000i,500n,10000p,200000b,50000s
+ 2119 strings out of 94681
+ 28087 string characters out of 1169859
+ 89519 words of memory out of 1500000
+ 5424 multiletter control sequences out of 10000+50000
+ 13703 words of font info for 53 fonts, out of 1200000 for 2000
+ 566 hyphenation exceptions out of 8191
+ 27i,15n,43p,208b,1416s stack positions out of 5000i,500n,6000p,200000b,5000s
 
 Output written on nobu-graduation.dvi (2 pages, 14012 bytes).
Binary file nobu-graduation.pdf has changed
--- a/nobu-midthesis.tex	Fri Nov 18 18:48:55 2011 +0900
+++ b/nobu-midthesis.tex	Fri Nov 18 19:31:32 2011 +0900
@@ -28,11 +28,11 @@
 
 \section{研究背景と目的}
 当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している。
-また CbC の開発と共に CbC のコンパイラの開発も行なってきた。
-2008年には GCC-4.2 をベースとした CbC のコンパイラ (以下 CbC-GCC) が開発され、GCC の最適化やデバッグ、他アーキテクチャへの対応と言った恩恵を受けられるようになった。
-以降、GCC のアップデートに合わせて CbC-GCC のアップデートも行ってきた。
+Code Segment は並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。これにより、
+Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。
 
-本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行う。
+GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は、GCC のアップデートに合わせて変更する必要がある。
+本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い、Intel64 に対応するとともに、CbC の拡張を行う。
 
 %\subsection{研究内容}
 %今回 GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へとアップデートを行った。
@@ -43,13 +43,11 @@
 %本研究では、CbC-GCC を GCC-4.6 へのバージョンアップすると共に実装を突き詰めることを目的とする。
 %また、GCC に変わるコンパイラとして注目されてきている LLVM への CbC の実装の考察も行う。
 \section{Continuation basede C (CbC)}
-Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である。
-CbC のプログラムはコードセグメント毎に記述され、コード間を軽量継続により処理を移るという特徴を持つ。
+CbC のプログラムはコードセグメント毎に記述され、コード間をgoto(軽量継続)により処理を移る。
 構文は C と同じであるが、ループ制御や関数コールが取り除かれる。
 
 \subsection{コードセグメント}
-CbC においてのプログラムの基本単位としてコードセグメントという概念がある。
-記述の仕方は C の構文と同じで、型に“\_\_code” を使うことで宣言できる。
+コードセグメントの記述は C の関数の構文と同じで、型に“\_\_code” を使うことで宣言できる。
 コードセグメントへの移動は“goto” の後にコードセグメント名と引数を並べて記述することで行える。
 図\ref{fig:cs}はコードセグメント間の処理の流れを表している。
 
@@ -69,25 +67,20 @@
 
 \subsection{軽量継続(light-weight continuation)}
 コードセグメントは C の関数と違って返り値を持たず、処理が終われば次のコードセグメントへと処理を移る。
-このコードセグメント間の継続制御を軽量継続(light-weight continuation) と呼ぶ。
 C おいて関数呼び出しを繰り返し行う場合、呼び出された関数の引数の数だけスタックに値が積まれていく。
-だが、返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く、最小限のスタックの使用ですむ。
+だが、返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く、スタックは変更されない。
 
-軽量継続によりループ制御、関数コールとスタックの操作を意識し最適化がソースコードレベルで行えるようになる。
+軽量継続により並列化, ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる。
 
 
 %だが、返り値を持たないコードセグメントではスタックに積まれる値は1つのコードセグメントの引数の分だけですむ。
 
 \section{GCC-4.6 への実装}
-\subsection{軽量継続の実装}
-CbC はコードセグメント間の処理の移りを軽量継続で行う。
-その実態は、アセンブラでの関数の呼び出しを call ではなく jmp で行うようにするというものである。
-
+% \subsection{軽量継続の実装}
+GCCでの計量継続を Tail Call Ellimination (末尾除去)を強制することで実装する。
+これにより、コードセグメント間の移動を、call ではなく jmp 命令で実現する。
+コードセグメント自体には戻値はない。
 
-\subsubsection{Tail Call Elimination}
-GCC には最適化の1つに Tail Call Elimination (末尾除去) がある。
-Tail Call Elimination は関数の呼び出しを call ではなく jmp で行い、
-返り値を大元の関数に返すというものである。
 %「caller側とcallee側の返り値の型が同じ」といった、幾つかのの条件下において行われる最適化になる。
 図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す。
 \begin{figure}[htpb]
@@ -98,29 +91,29 @@
   \label{fig:continue}
 \end{figure}
 
-CbC における軽量継続の実装はこの Tail Call Elimination を用いて行われている。
-コードセグメントは全てこの Tail Call Elimination にかからなければならない。
-
 \subsubsection{expand\_call}
-ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で判断される.
-expand\_call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる.
+GCCでは、ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で以下の条件で判断される.
 
 \begin{itemize}
   \item caller 側と callee 側の返す値の型が一致している.
   \item 関数呼び出しがリターンの直前に行われている.
   \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
+  \item 引数の並びのコピーに上書きがない.
 \end{itemize}
 
-CbC の実装では上記の条件を,以下の様にして解決させている.
+CbC の実装では上記の条件を, 以下の様にして解決させている.
 
 \begin{itemize}
-  \item 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.
-  \item コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.
-  \item スタックサイズは決め打ちで行う.
+  \item コードセグメントは void 型で統一する
+  \item Cの関数からコードセグメントにgotoする場合は返す値の型チェックを行わない.
+  \item goto の直後に retrun を置く．
+  \item スタックサイズは関数宣言時に決まったサイズにする．
+  \item 引数は一旦、一時変数にコピーして重なりがないようにする．
 \end{itemize}
 
-だが、 CbC-GCC-4.5 において Tail Call Elimination にかからないコードセグメントがあることを確認できた。
-この点は GCC-4.6 へのアップデートに合わせ改善する。
+GCCでは, この他にもTCEを禁止しするルールがあり, GCC-4.5, 4.6 でも
+Tail Call Elimination にかからないコードセグメントがある.
+この点を改善する必要がある.
 
 
 %\subsubsection{try_tail_call フラグ}
@@ -152,18 +145,32 @@
 
 %\subsection{\_\_return 変数}
 \subsection{環境付き継続}
-CbC では通常の C の関数からコードセグメントに継続する際、
-元の C の関数に処理を戻すことがように環境付き継続を実装してある。
-環境付き継続は \_\_return, \_\_environment という CbC で定義した変数を参照することで用いることができる。
-この2つの変数は参照されると、参照した関数のアドレスを覚えておく。
-具体的には変数を参照した関数にコード\ref{code:_ret_val}の生成を行なっている。
-コードセグメントから戻るときには関数内で定義された \_cbc\_internal\_return 関数に飛び、
-リターンを行うのである。
+CbC には通常の C の関数からコードセグメントに継続する際、
+その関数から値を戻す処理への継続を得ることができる.
+これを環境付き継続という.
+これらは, 以下の二種類の CbC で定義した特殊変数である.
+\_\_environment は, 環境を表す情報である.
+\_\_return は,  これを環境付き継続の行き先であり, 関数の戻値と \_\_environment の二つの引数を持つ
+コードセグメントである. 例えば、以下のように使うと, \verb+main()+ は 1 を返す.
+
+\begin{verbatim}
+__code c1(__code ret(int,void *),void *env) {
+    goto ret(1,env);
+}
+
+int main() {
+    goto c1(__return, __environment);
+}
+\end{verbatim}
+
+GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
+戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(図\ref{code:_ret_val}).
+
 \begin{figure}[h]
   \begin{minipage}[b]{.45\textwidth}
     \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
 __label__ _cbc_exit0;
-int retval; // should be thread local                                                                                                                                                   
+static int retval; // should be thread local                                                                                                                                                   
 void _cbc_internal_return(int retval_, void *_envp){
   retval = retval_;
   goto _cbc_exit0;
@@ -179,10 +186,16 @@
 \end{figure}
 
 \subsubsection{環境付き継続の問題}
-しかし現在環境付き継続はスレッドセーフな実装でない。
-その為,マルチスレッドで環境付き継続を扱うと、元の関数に戻る前に別スレッド
-が記憶したアドレスの値を書き換えられる可能性があるからである。
-そこで、環境付き継続をスレッドセーフで実装する必要がある。
+現在環境付き継続は
+このコードを GCC 内部で生成することで実現している. これは正しく動作しているが,
+\verb+retval+に static を指定してしまうと,
+スレッドセーフな実装でなくなる.
+これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の
+組合せでは closure は正しく動作してないことがわかった. 
+Thread local 変数を用いると, やはり closure が出力されてしまう.
+本来は, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず,
+浮動小数点や構造体自体である可能性があり複雑である. 
+一つの解決策はレジスタ渡しと考えているが, 他の方もありえる. 少し重いが setjmp を用いた実装方法もある.
 
 
 \section{現状と今後の課題}
@@ -192,8 +205,11 @@
 %しかし、アップデートに伴い幾つか実装を見直す必要がでてきた。
 %同時に、現時点で見つかっている問題以外にもバグが無いかを調べていく。
 今後は本稿でも述べたとおり CbC コンパイラの実装を行なっていく。
-また、実装後は、32ビット,64ビットそれぞれでコンパイルしたプログラムの比較、
-それと Micro-C との性能比較も行う予定である。
+また、実装後は、32ビット, 64ビットそれぞれでコンパイルしたプログラムの比較、
+それと Micro-C による実装との性能比較も行う予定である。
+
+時間があれば, LLVM での実装, コードセグメントの宣言に便利な \verb+typedefrec+ の実装,
+あるいは, Google go 言語での実装などの研究も行う予定である.
 
 
 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある。
@@ -205,21 +221,9 @@
 \bibitem{1}{河野真治}:
 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002
 
-\bibitem{2}{河野真治}:
-“継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000
-
 \bibitem{3}{与儀健人,河野真治}:
 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008
 
-\bibitem{4}{与儀健人,河野真治}:
-“組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010
-
-\bibitem{5}{下地篤樹,河野真治}:
-“線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008
-
-\bibitem{6}{楊挺,河野真治}:
-“Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002
-
 \bibitem{7}{GNU Compiler Collection (GCC) Internals}:
 “http://gcc.gnu.org/onlinedocs/gccint/”