changeset 11:2d9b3ad3e524

result
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Sun, 14 Feb 2016 05:01:15 +0900
parents 571f9f8d99e1
children a077276f53cc
files paper/appendix.tex paper/conclusion.tex paper/master_paper.pdf paper/master_paper.tex paper/thanx.tex
diffstat 5 files changed, 184 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/appendix.tex	Sun Feb 14 05:01:15 2016 +0900
@@ -0,0 +1,158 @@
+\chapter*{発表履歴}
+\addcontentsline{toc}{chapter}{発表文献}
+
+\begin{itemize}
+\item{Implementing Continuation based language in LLVM and Clang, Kaito TOKUMORI, Shinji KONO, LOLA 2015,Kyoto, July, 2015}
+\item {Continuation based C の LLVM/clang 3.5 上の実装について, 徳森海斗, 河野真治, 情報処理学会システムソフトウェアとオペレーティングシステム研究会, May, 2014}
+\end{itemize}
+
+\chapter{環境付き継続の計測に使用したソースコード}
+\begin{lstlisting}[frame=lrbt,label=gotowithenv,caption={}]
+#define LOOP 50000000
+
+#include <stdio.h>
+
+__code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env);
+
+__code factorial(int n,int result,int orig,__code(*print)(int,int,int,__code(*)(),__code(*)(),void*),__code(*exit1)(int,void *), void *exit1env)
+{
+    if (n<0) {
+      printf("#0008:err %d!\n",n);
+      goto (*exit1)(0,exit1env);
+    }
+    if (n==0)
+      goto (*print)(n,result,orig,print,exit1,exit1env);
+    else {
+      result += n;
+      n--;
+      goto factorial(n,result,orig,print,exit1,exit1env);
+    }
+}
+
+
+int calc(int n){
+  __code (*ret)(int,void *) = __return;
+  void* env = __environment;
+  goto factorial(n,1,n,print,ret,env);
+  return 0;
+}
+
+int main( int ac, char *av[])
+{
+  int i;
+  long ans;
+  for(i=LOOP,ans=0;i>0;i--){
+    ans += calc(10);
+  }
+
+  printf("%ld\n",ans);
+}
+
+__code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env)
+{
+  goto (*exit1)(result,exit1env);
+}
+\end{lstlisting}
+
+\chapter{計算を繰り返すコード (C)}
+\begin{lstlisting}[frame=lrbt,label=calc,caption={}]
+#define LOOP 500000000
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int func4(int a, int b){
+  return a+b;
+}
+
+int func3(int a, int b){
+  return func4(b,b/a);
+}
+
+int func2(int a, int b){
+  return func3(b,a*b);
+}
+
+int func1(int a, int b){
+  return func2(b,a+b);
+}
+
+int start_func(int loop){
+  int i, a;
+  a = 0;
+  for (i=0;i<loop;i++)
+    a += func1(1,2);
+  return a;
+}
+
+int main( int ac, char *av[]){
+  printf("%d\n",start_func(LOOP));
+  return 0;
+}
+\end{lstlisting}
+
+\chapter{計算を繰り返すコード (CbC)}
+\begin{lstlisting}[frame=lrbt,label=calcCbC,caption={}]
+#define LOOP 500000000
+
+#include <stdio.h>
+#include <stdlib.h>
+
+__code code4(int a, int b, int loop, int ans){
+  goto start_code(ans+a+b, loop-1);
+}
+
+__code code3(int a, int b, int loop, int ans){
+  goto code4(b,b/a,loop, ans);
+}
+
+__code code2(int a, int b, int loop, int ans){
+  goto code3(b,a*b,loop, ans);
+}
+
+__code code1(int a, int b, int loop, int ans){
+  goto code2(b,a+b,loop, ans);
+}
+
+__code start_code(int ans, int loop){
+  if (loop>0)
+    goto code1(1,2,loop, ans);
+  else
+    goto print(ans);
+}
+
+int main( int ac, char *av[]){
+  goto start_code(0,LOOP);
+  return 0;
+}
+
+__code print(int a){
+  printf("%d\n",a);
+  exit(0);
+}
+\end{lstlisting}
+
+\chapter{計算を繰り返すコード (Scheme)}
+\begin{lstlisting}[frame=lrbt,label=calcScheme,caption={}]
+(define LOOP 500000000)
+
+(define (print_ans ans)
+  (print ans))
+
+(define (code4 a b loop ans)
+  (start_code (+ ans (+ a b)) (- loop 1)))
+  
+(define (code3 a b loop ans)
+  (code4 b (/ b a) loop ans))
+
+(define (code2 a b loop ans)
+  (code3 b (* a b) loop ans))
+
+(define (code1 a b loop ans)
+  (code2 b (+ a b) loop ans))
+
+(define (start_code ans loop)
+  (if (> loop 0) (code1 1 2 loop ans) (print_ans ans) ))
+
+(start_code 0 LOOP)
+\end{lstlisting}
--- a/paper/conclusion.tex	Sun Feb 14 02:52:17 2016 +0900
+++ b/paper/conclusion.tex	Sun Feb 14 05:01:15 2016 +0900
@@ -1,2 +1,21 @@
 \chapter{結論} \label{chapter:conclusion}
+本研究では Continuation based C (CbC) の LLVM clang ベースのコンパイラの改良を行った.
+
+CbC は code segment を基本単位として用いる言語であり, 並列フレームワーク Gears OS の実装にも用いている.
+
+LLVM clang ベースの CbC コンパイラは 2014 年の研究によって開発された. 今回の研究では LLVM builtin の setjmp, longjmp を用いることによる環境付き継続の改善, omit leaf frame pointer を強制することによるさらなる最適化の付加, プロトタイプ宣言の自動化を行った.
+
+また, Gears OS をサポートするためのスクリプトも作成し, data segment, meta code segment を利用する CbC の記述量を減らすことが出来た.
+
+環境付き継続の速度計測では, 元のものの 7 倍近い速度を出すことに成功し, アセンブリコードを直接生成する高速な Micro-C のものと比較しても殆ど差がなくなった.
+
+C との比較でも良好な結果が得られ, スタックポインタ, フレームポインタの操作の最適化, 除去が速度向上に繋がることが確認できた.
+
 \section{今後の課題}
+今回の改良により環境付き継続を大幅に高速化することが出来たが, アセンブリコードを直接生成できる builtin 関数を実装し, それを利用することでさらなる高速化を行えることがわかった. ただしこの場合各アーキテクチャ毎に対応しなければならない, 最適化が適切にかかるようにする必要があるという難点がある. しかし今回実装した環境付き継続でも十分な速度は出せているので, 未対応のものに対しては builtin setjmp, longjmp を用いるという対応でも良いだろう. 
+
+また, 今回は提案した構文に柔軟に対応するために Gears OS 向けの構文を python スクリプトを用いてサポートしたが, これらの機能をコンパイラ内部に実装し, Gears OS のコードを直接コンパイルできるようにする必要がある. この時 data segment の signature を利用できるようにする構文も実装するのがよいだろう.
+
+前述したとおり CbC では code segment に tail call elimination を強制することで軽量継続を実現しているが, 最適化レベルによっては強制に失敗する例があることが判明している. 最適化と軽量継続を両立する改善が必要である. 
+
+その他, 現在 CbC は C 言語を基に作られているため C コンパイラを利用できるという利点はあるものの, C の構文に縛られているという欠点もある. そのため C に依存しない code segment, data segment を用いる新しいプログラミング言語の開発の検討も課題の一つである. 
Binary file paper/master_paper.pdf has changed
--- a/paper/master_paper.tex	Sun Feb 14 02:52:17 2016 +0900
+++ b/paper/master_paper.tex	Sun Feb 14 05:01:15 2016 +0900
@@ -96,7 +96,8 @@
 \bibliography{master_paper}
 
 %発表文献
-%\input{appendix.tex}
+\appendix
+\input{appendix.tex}
 
 %付録
 
--- a/paper/thanx.tex	Sun Feb 14 02:52:17 2016 +0900
+++ b/paper/thanx.tex	Sun Feb 14 05:01:15 2016 +0900
@@ -1,2 +1,7 @@
 \chapter*{謝辞}
 \addcontentsline{toc}{chapter}{謝辞}
+
+本研究の遂行,本論文の作成にあたり, 御多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治准教授に心より感謝致します.
+また, 本研究の遂行及び本論文の作成にあたり, 与儀健人さん, 大城信康さんの研究論文は大いに参考になりました. 深く感謝致します.
+そして, 一年間共に研究を行い暖かな気遣いと励ましをもって支えてくれた並列信頼研究室の全てのメンバーに感謝致します.
+最後に, 有意義な時間を共に過ごした理工学研究科情報工学専攻の学友, 並びに物心両面で支えてくれた家族に深く感謝致します.