Mercurial > hg > Papers > 2016 > mitsuki-midterm

annotate midterm.tex @ 1:45bc92a01821 draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author mir3636
date Fri, 21 Oct 2016 23:25:49 +0900
parents 6abb63b73e47
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \usepackage[dvipdfmx]{graphicx}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 \usepackage{picins}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 \usepackage{fancyhdr}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 %\pagestyle{fancy}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 \rhead{}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 \cfoot{}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 \setlength{\headheight}{0mm}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 \setlength{\headsep}{5mm}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 \setlength{\textwidth}{181mm}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 \setlength{\textheight}{261mm}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 \setlength{\footskip}{0mm}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \pagestyle{empty}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 \input{dummy.tex}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 \begin{document}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 \title{LLVM/clang 上の CbC コンパイラの改良と Gears OS サポート}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 \author{135756F 氏名 宮城光希 {}{} 指導教員 : 河野 真治}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 \date{}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 \maketitle
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 \thispagestyle{fancy}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27
1
mir3636
parents: 0
diff changeset
28 \section{メタ計算の重要性}
mir3636
parents: 0
diff changeset
29
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 プログラムを記述する際に通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。これらの計算を Meta Computation と呼ぶ。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Segment、Data Segment という単位を提案している。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 Code Segment は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 Code Segment、Data Segment にはそれぞれメタレベルの単位である Meta Code Segment、Meta Data Segment が存在し、これらを用いて Meta Computation を実現する。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37
1
mir3636
parents: 0
diff changeset
38 また、Code Segment 単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 CbCは軽量継続による遷移を行うので、継続前の Code Segment に戻ることはなく、状態遷移ベースのプログラミングに適している。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
1
mir3636
parents: 0
diff changeset
41 Data Gear は CbC で記述された Gears OS によって管理される。Gears OS では一つのスレッドは Data Gears と Code Gears を管理する Context をただ一つ持つ。
mir3636
parents: 0
diff changeset
42 Context は Meta Data Gears の一つである。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 本研究では、LLVM/clang 上での CbC コンパイラの改良と Gears OS の構文のサポートを行う。
1
mir3636
parents: 0
diff changeset
45
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 \section{Continuation based C (CbC)}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47
1
mir3636
parents: 0
diff changeset
48 CbC では Code Segment は \_\_code という型を持つ関数の構文で定義される。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
1
mir3636
parents: 0
diff changeset
50 Code Segment は 戻り値を持たないので、return 文は存在しない。goto の後に Code Segment 名と引数を並べて、次の Code Gears の遷移を記述する。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
1
mir3636
parents: 0
diff changeset
52 この goto の行き先を継続と呼ぶ。Scheme の継続と異なり CbC には環境がないので、この継続は単なる行き先である。したがってこれを軽量継続と呼ぶこともある。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 \begin{figure}[htpb]
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 \centering
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 \includegraphics[width=70mm]{pic/codesegment.pdf}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 \caption{gotoによる Code Segment 間の接続}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 \label{fig:codesegment}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 \end{figure}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60
1
mir3636
parents: 0
diff changeset
61 \section{LLVM/clang による CbC の実装}
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。
1
mir3636
parents: 0
diff changeset
63 LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 clang は LLVM をバックエンドとして利用する C/C++/Objective-C のコンパイラである。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
1
mir3636
parents: 0
diff changeset
67 LLVMでは、最適化や中間表現の変換を何段階か行う。多くの pass は最適化のために存在し、そのなかから任意のものを利用することができる。
mir3636
parents: 0
diff changeset
68 pass には以下のようなものがある。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 \subsubsection*{SelectionDAG Instruction Selection (SelectionDAGISel)}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し、最適化を行う。その後 Machine Code を生成する。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 \subsubsection*{SSA-based Machine Code Optimizations}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 SSA-based Machine Code に対する最適化を行う。各最適化はそれぞれ独立した pass になっている。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 \subsubsection*{Register Allocation}
1
mir3636
parents: 0
diff changeset
75 仮想レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、SSA-based でなくなる。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 \subsubsection*{Prolog/Epilog Code Insertion}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 Prolog/Epilog Code の挿入を行う。どちらも関数呼び出しに関わるものであり、Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、Epilog は呼び出し元の関数に戻る際に行う処理である。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 \subsubsection*{Late Machine Code Optimizations}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 Machine Code に対してさらに最適化を行う。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 \subsubsection*{Code Emission}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 Machine Code を MC Layer での表現に変換する。その後さらにターゲットのアセンブリ言語へ変換し、その出力を行う。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 \begin{figure}[ht]
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 \centering
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 \includegraphics[width=90mm]{pic/llvmProcess.pdf}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 \caption{LLVM の 処理過程}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 \label{fig:llvmProcess}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 \end{figure}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
1
mir3636
parents: 0
diff changeset
90 \section{LLVM/clang のデバッグ}
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 LLVM/clang で CbC をコンパイルした際 Code Segment 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 局所変数でポインタを参照していると clang は生成する LLVM IR に オブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 ここでオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 しかしCbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 \section{Gears OS の構文サポート}
1
mir3636
parents: 0
diff changeset
101 Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
mir3636
parents: 0
diff changeset
102 Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。Meta Code Gear は通常の Code Gear の直後に遷移され、Meta Computation を実行する。
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 CbC では処理を Code Segment を用いたプログラミング言語であるため、 Gears OS の Code Gear を記述するのに適している。
1
mir3636
parents: 0
diff changeset
107 そこで Gears OS の構文のサポートが必要になる。現在は python を用いたプログラム変換で実現されている。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 Gears OS では Context という接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Dara Gear である。Gears OS では必要な Code/Data Gear に参照したい場合、Context を通す必要がある。
1
mir3636
parents: 0
diff changeset
110 Context の自動生成を行うようにする。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 \section{今後の課題}
1
mir3636
parents: 0
diff changeset
113 今後の課題は現状の Gears OS のコードをリファクタリングし通常計算とメタ計算の分離を明確にする。
mir3636
parents: 0
diff changeset
114 必要なメタ計算部分の CbC による実装を統一する。
mir3636
parents: 0
diff changeset
115 Context 、 Meta Code Gear 、 Meta Data Gear を生成するプログラム変換系を作成する。
mir3636
parents: 0
diff changeset
116 これを用いて Gears OS の記述を行う。
mir3636
parents: 0
diff changeset
117 これにより Gears OS のメタ計算を柔軟に行うことができるようになり、 Gears OS 自体の信頼性を向上し, Gears OS の拡張性を実現することができると考えられる。
0
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 \begin{thebibliography}{9}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 \bibitem{1}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 徳森 海斗 : LLVM Clang 上の Continuation based C コンパイラ の改良,
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 \bibitem{2}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 伊波立樹, 東恩納琢偉, 河野真治 : Code Gear、 Data Gear に基づく OS のプロトタイプ, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2016).
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 \bibitem{3}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 大城 信康, 河野真治 : Continuation based C の GCC 4.6 上の実装について, 第53回プログラミング・シンポジウム(2012)
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 \bibitem{4}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 与儀健人, 河野真治 : Continuation based c コンパイラの gcc-4.2 による実装, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2008).
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 \bibitem{5}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 The LLVM Compiler Infrastructure
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 \bibitem{6}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 LLVM Language Reference Manual
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 \end{thebibliography}
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 \end{document}