Mercurial > hg > Papers > 2014 > kaito_sigos

Binary file 2014_sigos.pdf has changed
--- a/2014_sigos.tex	Thu Apr 03 18:54:53 2014 +0900
+++ b/2014_sigos.tex	Thu Apr 10 15:21:23 2014 +0900
@@ -1,1 +1,1 @@
-\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
%\usepackage{jtygm}
\usepackage{mediabb}
\usepackage{float}

% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の LLVM/clang 3.5 上の実装について]%
	{Continuation based C の LLVM/clang 3.5 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on LLVM/clang 3.5}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{徳森 海斗\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Kaito Tokumori\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{徳森 海斗\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: kaito@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment を用いるプログラミング手法を提案している. この手法を用いるプログラミング言語として CbC の開発を行っており, これは C の下位の言語になる. 本研究では, LLVM/clang-3.5 をベースとした CbC コンパイラの実装を行い, LLVM/clang-3.5 への CbC の具体的な実装について述べる.
\end{abstract}


% 英文概要
\begin{eabstract}
We suggest a programming paradigm which use data segments and code segments. We develop CbC which is a lower language of C and uses that programming paradigm. In this study, we implement CbC compiler on LLVM/clang and introduce implemented Continuation based C Compiler on LLVM/clang-3.5.
\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

%}{

%\nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals}
%\bibliographystyle{junsrt}
%\bibliography{cbc.bib}
 
\end{document}
\ No newline at end of file
+\documentclass[private]{ipsjpapers}
%\documentstyle{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線
\usepackage{listings}
%\usepackage{jtygm}
\usepackage{mediabb}
\usepackage{float}
\lstset{
  language={C},
  basicstyle={\footnotesize\ttfamily},
  identifierstyle={\footnotesize},
  commentstyle={\footnotesize\itshape},
  keywordstyle={\footnotesize\bfseries},
  ndkeywordstyle={\footnotesize},
  stringstyle={\footnotesize\ttfamily},
  frame={tb},
  breaklines=true,
  columns=[l]{fullflexible},
  numbers=left,
  xrightmargin=0zw,
  xleftmargin=3zw,
  numberstyle={\scriptsize},
  stepnumber=1,
  numbersep=1zw,
  lineskip=-0.5ex
}

% 巻数，号数などの設定
%\setcounter{巻数}{41}
%\setcounter{号数}{6}
%\setcounter{volpageoffset}{1234}
%\受付{12}{2}{4}
%\採録{12}{5}{11}

\pagestyle{empty}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
%\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
	$\backslash$#1\fi}

%\checklines	% 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[Continuation based C の LLVM/clang 3.5 上の実装について]%
	{Continuation based C の LLVM/clang 3.5 上の実装について}
% 英文表題
\etitle{The implementation of Continuation based C Compiler on LLVM/clang 3.5}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{徳森 海斗\affiref{URYUKYU}\nomember\and
	河野 真治\affiref{URYUKYU}\member{19841765}}
	

% 英文著者名
\eauthor{Kaito Tokumori\affiref{URYUKYU}\and
	Shinji Kono\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{徳森 海斗\\
	〒903-0213 沖縄県中頭郡西原町字千原1番地\\
	琉球大学 情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
	email: kaito@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment を用いるプログラミング手法を提案している. この手法を用いるプログラミング言語として CbC の開発を行っており, これは C の下位の言語になる. 本研究では, LLVM/clang-3.5 をベースとした CbC コンパイラの実装を行い, LLVM/clang-3.5 への CbC の具体的な実装について述べる.
\end{abstract}


% 英文概要
\begin{eabstract}
We suggest a programming paradigm which use data segments and code segments. We develop CbC which is a lower language of C and uses that programming paradigm. In this study, we implement CbC compiler on LLVM/clang and introduce implemented Continuation based C Compiler on LLVM/clang-3.5.
\end{eabstract}

% 表題などの出力
\maketitle
\thispagestyle{empty} 

\section{研究目的}
当研究室では, プログラムをコードセグメント, データセグメントという単位を用いて書くという手法を提案している. この手法を用いてプログラミングを行う言語として Continuation based C (以下CbC) というプログラミング言語を開発しており, これは C の下位の言語にあたる. CbC においてコードセグメント間の処理の移動は goto 文を用いた軽量継続によって行われ, これは Tail Call Elimination というコンパイラの持つ最適化の強制によって実現される. CbC では継続前の code segment に戻ることはなく, 状態遷移ベースのプログラミングを行うのに適しており, これは OpenCL, CUDA, そして Cerium といった並列開発環境を用いたプログラムの記述に向いている. \\
　これまでに開発された CbC のコンパイラは Micro-C をベースにしたものと GCC をベースにしたものの二種がある.
　GCC 上に CbC コンパイラを実装した理由の一つに, 当時の UNIX 環境における コンパイラの標準が GCC であったからというものがあった. しかし, Mac OS X の最新版である Mavericks では GCC の代わりに LLVM/clang が用いられるようになり, 環境が変わりつつあることがわかる. 
このような背景から, LLVM/clang を用いて CbC をコンパイルできるのが良いという考えが生じた. 本研究では LLVM/clang 上に CbC コンパイラの実装を行う.
%\nocite{kono:2002a, kono:2000a, kono:2008a, yogi:2008a, yogi:2008b, yan:2002a,gcc_internals}
%\bibliographystyle{junsrt}
%\bibliography{cbc.bib}
 
\section{Continuation based C (CbC)}
CbC では C の関数の代わりに code segment を用いて処理を記述し,  code segment 間の移動に goto を用いる. 
構文は C と同じであるが, ループ制御や関数コールが取り除かれる. 

code segment の記述は C の関数の構文と同じで, 型に \_\_code を使うことで宣言でき, code segment 間の移動は goto の後に code segment 名と引数を並べて記述することで行える. 
この goto による処理の遷移を継続と呼ぶ. 
図\ref{fig:cs}は code segment 間の処理の流れを表している. 

\begin{figure}[h]
  \begin{center}
\scalebox{0.30}{\includegraphics{figure/codesegment.pdf}}
  \end{center}
  \caption{goto による code segment 間の継続}
  \label{fig:cs}
\end{figure}


code segment は C の関数と異なり戻り値を持たず, 処理が終われば次の code segment へと処理を移る. 
C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. 
しかし, 戻り値を持たない code segment ではスタックに値を積んでいく必要が無く, スタックは変更されない. 
このようなスタックに値を積まない継続, つまり呼び出し元の環境を持たない継続を軽量継続と呼び, 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. \\
　以下の図\ref{fig:factorial}に示されたプログラムは与えられた数値の階乗を算出する CbC プログラムである. %このコードの factorial0 という code segment に注目すると, 条件判別を行い, その結果に応じて自分自身への再帰的な継続を行うか別の code segment への継続を行うかという処理を行っていることがわかる. CbC ではこのようにしてループ処理を制御する.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.35}{\includegraphics{figure/factorial.pdf}}
  \end{center}
  \caption{階乗を計算する CbC プログラムの例}
  \label{fig:factorial}
\end{figure}

%\section{LLVM/clang の概要}
%LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.\\
%　clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
\section{LLVM/clang で扱われる内部表現}
　CbC コンパイラの実装の前に, LLVM 及び clang で扱われる内部表現について触れる. LLVM, clang はコンパイル対象コードを clang Abstract Syntax Tree (clangAST), LLVM IR, Selection Directed Acycric Graph (SelectionDAG), Machine Code, MCLayer の順に変換し, その後アセンブラ言語へと変換する. 図\ref{fig:llvmFlow}は clang がソースコードを読み込み, アセンブラ言語を出力するまでの流れを表した図である.

\begin{figure}[htpb]
  \begin{center}
\scalebox{0.25}{\includegraphics{figure/clang_llvm_structure.pdf}}
  \end{center}
  \caption{clang, LLVM によるコンパイルの一連の流れ}
  \label{fig:llvmFlow}
\end{figure}

\end{document}
\ No newline at end of file
Binary file figure/clang_llvm_structure.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/figure/clang_llvm_structure.xbb	Thu Apr 10 15:21:23 2014 +0900
@@ -0,0 +1,8 @@
+%%Title: ./figure/clang_llvm_structure.pdf
+%%Creator: extractbb 20130405
+%%BoundingBox: 0 0 791 464
+%%HiResBoundingBox: 0.000000 0.000000 790.500000 463.500000
+%%PDFVersion: 1.4
+%%Pages: 1
+%%CreationDate: Thu Apr 10 15:18:45 2014
+
Binary file figure/codesegment.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/figure/codesegment.xbb	Thu Apr 10 15:21:23 2014 +0900
@@ -0,0 +1,8 @@
+%%Title: ./figure/codesegment.pdf
+%%Creator: extractbb 20130405
+%%BoundingBox: 0 0 611 302
+%%HiResBoundingBox: 0.000000 0.000000 610.500000 301.500000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Thu Apr 10 15:18:45 2014
+
Binary file figure/factorial.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/figure/factorial.xbb	Thu Apr 10 15:21:23 2014 +0900
@@ -0,0 +1,8 @@
+%%Title: ./figure/factorial.pdf
+%%Creator: extractbb 20130405
+%%BoundingBox: 0 0 557 584
+%%HiResBoundingBox: 0.000000 0.000000 556.500000 583.500000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Thu Apr 10 15:18:45 2014
+