Mercurial > hg > Papers > 2016 > mitsuki-midterm

comparison 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
comparison
equal deleted inserted replaced
0:6abb63b73e47 1:45bc92a01821
23 \author{135756F 氏名 宮城光希 {}{} 指導教員 : 河野 真治} 23 \author{135756F 氏名 宮城光希 {}{} 指導教員 : 河野 真治}
24 \date{} 24 \date{}
25 \maketitle 25 \maketitle
26 \thispagestyle{fancy} 26 \thispagestyle{fancy}
27 27
28 \section{研究目的} 28 \section{メタ計算の重要性}
29
29 プログラムを記述する際に通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。これらの計算を Meta Computation と呼ぶ。 30 プログラムを記述する際に通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。これらの計算を Meta Computation と呼ぶ。
30 31
31 Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。 32 Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
32
33 そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Segment、Data Segment という単位を提案している。 33 そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Segment、Data Segment という単位を提案している。
34 34
35 Code Segment は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。 35 Code Segment は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
36
37 Code Segment、Data Segment にはそれぞれメタレベルの単位である Meta Code Segment、Meta Data Segment が存在し、これらを用いて Meta Computation を実現する。 36 Code Segment、Data Segment にはそれぞれメタレベルの単位である Meta Code Segment、Meta Data Segment が存在し、これらを用いて Meta Computation を実現する。
38 37
39 また、処理を Code Segment、データを Data Segment とした単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。 38 また、Code Segment 単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。
40
41 CbCは軽量継続による遷移を行うので、継続前の Code Segment に戻ることはなく、状態遷移ベースのプログラミングに適している。 39 CbCは軽量継続による遷移を行うので、継続前の Code Segment に戻ることはなく、状態遷移ベースのプログラミングに適している。
42 40
43 CbCと同様に処理を Code Gear、データを Data Gear とした単位を用いた並列実行をサポートした Gears OS も開発している。 Gears OS は CbC で記述されている。 41 Data Gear は CbC で記述された Gears OS によって管理される。Gears OS では一つのスレッドは Data Gears と Code Gears を管理する Context をただ一つ持つ。
42 Context は Meta Data Gears の一つである。
44 43
45 本研究では、LLVM/clang 上での CbC コンパイラの改良と Gears OS の構文のサポートを行う。 44 本研究では、LLVM/clang 上での CbC コンパイラの改良と Gears OS の構文のサポートを行う。
45
46 \section{Continuation based C (CbC)} 46 \section{Continuation based C (CbC)}
47 CbC では C の関数の代わりに Code Segment を用いて処理を記述している。
48 47
49 Code Segment の宣言は C の関数の構文と同様に記述し、型に \_\_code を使うことで宣言できる。 48 CbC では Code Segment は \_\_code という型を持つ関数の構文で定義される。
50 49
51 Code Segment は C の関数と異なり戻り値を持たず、 Code Segment 間の移動は goto の後に Code Segment 名と引数を並べて記述する独自の構文を用いて行う。 50 Code Segment は 戻り値を持たないので、return 文は存在しない。goto の後に Code Segment 名と引数を並べて、次の Code Gears の遷移を記述する。
52 51
53 この goto による処理の遷移を継続と呼ぶ。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。 52 この goto の行き先を継続と呼ぶ。Scheme の継続と異なり CbC には環境がないので、この継続は単なる行き先である。したがってこれを軽量継続と呼ぶこともある。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。
54 53
55 \begin{figure}[htpb] 54 \begin{figure}[htpb]
56 \centering 55 \centering
57 \includegraphics[width=70mm]{pic/codesegment.pdf} 56 \includegraphics[width=70mm]{pic/codesegment.pdf}
58 \caption{gotoによる Code Segment 間の接続} 57 \caption{gotoによる Code Segment 間の接続}
59 \label{fig:codesegment} 58 \label{fig:codesegment}
60 \end{figure} 59 \end{figure}
61 60
62 C では関数呼び出しを行う際、現在までの位置を環境として保持するが、戻り値を持たない Code Segment は呼び出し元の環境を保持しない。 61 \section{LLVM/clang による CbC の実装}
63 ここで環境とは現在のスタックの状態のことを指す。このように呼び出し元の環境を持たない継続を軽量継続と呼ぶ。
64 軽量継続によって、並列化、ループ制御、関数コールといったスタックを意識した最適化がソースコードレベルで行うことができる。
65
66 しかし CbC と C の記述を交える際、CbC の code segment から C の関数への呼び出しは問題なく行えるが、逆の場合呼び出し元の環境に戻るための特殊な継続が必要となる。これを環境付き継続とよぶ。
67
68 環境付き継続を用いる場合 C の関数から code segment へ接続する際に \_\_return、\_\_environment という変数を渡す。
69 \section{LLVM/clang}
70 LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。 62 LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。
71 単に LLVM といった場合は LLVM Core のことを指す。以降は本文でも単に LLVM といった場合は LLVM Core のことを指す。 63 LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。
72
73 LLVM はコンパイラ基盤であり、コンパイラのバックエンド部分の処理を行う。
74 LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語や実行可能なファイルに変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。
75
76 LLVM のフロントエンドはターゲットの言語を LLVM IR に変換することによって LLVM の最適化機構を利用することができる。
77 64
78 clang は LLVM をバックエンドとして利用する C/C++/Objective-C のコンパイラである。 65 clang は LLVM をバックエンドとして利用する C/C++/Objective-C のコンパイラである。
79 66
80 フロントエンドとして clang を使用し、与えられたコードから LLVM IRを生成し、LLVM はこれを最適化し機械語に変換を行う。 67 LLVMでは、最適化や中間表現の変換を何段階か行う。多くの pass は最適化のために存在し、そのなかから任意のものを利用することができる。
81 68 pass には以下のようなものがある。
82 LLVM は LLVM IR を直接的にターゲットのアセンブリ言語へ変換を行うわけではなく、中間表現を何度か変えその度に最適化を行い、最終的にターゲットのアセンブリ言語に変換する。
83
84 LLVMでは、最適化や中間表現の変換といったコンパイラを構成する処理は全てpassが行う。多くの pass は最適化のために存在し、この pass を組み合わせることにより、LLVM の持つ機能の中から任意のものを利用することができる。
85
86 LLVM ターゲットのアセンブリ言語を生成するまでの過程を記すと以下のようになる。
87 69
88 \subsubsection*{SelectionDAG Instruction Selection (SelectionDAGISel)} 70 \subsubsection*{SelectionDAG Instruction Selection (SelectionDAGISel)}
89 LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し、最適化を行う。その後 Machine Code を生成する。 71 LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し、最適化を行う。その後 Machine Code を生成する。
90 \subsubsection*{SSA-based Machine Code Optimizations} 72 \subsubsection*{SSA-based Machine Code Optimizations}
91 SSA-based Machine Code に対する最適化を行う。各最適化はそれぞれ独立した pass になっている。 73 SSA-based Machine Code に対する最適化を行う。各最適化はそれぞれ独立した pass になっている。
92 \subsubsection*{Register Allocation} 74 \subsubsection*{Register Allocation}
93 仮装レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、SSA-based でなくなる。 75 仮想レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、SSA-based でなくなる。
94 \subsubsection*{Prolog/Epilog Code Insertion} 76 \subsubsection*{Prolog/Epilog Code Insertion}
95 Prolog/Epilog Code の挿入を行う。どちらも関数呼び出しに関わるものであり、Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、Epilog は呼び出し元の関数に戻る際に行う処理である。 77 Prolog/Epilog Code の挿入を行う。どちらも関数呼び出しに関わるものであり、Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、Epilog は呼び出し元の関数に戻る際に行う処理である。
96 \subsubsection*{Late Machine Code Optimizations} 78 \subsubsection*{Late Machine Code Optimizations}
97 Machine Code に対してさらに最適化を行う。 79 Machine Code に対してさらに最適化を行う。
98 \subsubsection*{Code Emission} 80 \subsubsection*{Code Emission}
103 \includegraphics[width=90mm]{pic/llvmProcess.pdf} 85 \includegraphics[width=90mm]{pic/llvmProcess.pdf}
104 \caption{LLVM の 処理過程} 86 \caption{LLVM の 処理過程}
105 \label{fig:llvmProcess} 87 \label{fig:llvmProcess}
106 \end{figure} 88 \end{figure}
107 89
108 \section{LLVM/clang のリファクタリング} 90 \section{LLVM/clang のデバッグ}
109 LLVM/clang で CbC をコンパイルした際 Code Segment 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。 91 LLVM/clang で CbC をコンパイルした際 Code Segment 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。
110 92
111 局所変数でポインタを参照していると clang は生成する LLVM IR に オブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。 93 局所変数でポインタを参照していると clang は生成する LLVM IR に オブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。
112 94
113 ここでオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。 95 ここでオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。
114 96
115 しかしCbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。 97 しかしCbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。
116 そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。 98 そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。
117 99
118 \section{Gears OS の構文サポート} 100 \section{Gears OS の構文サポート}
119 Gears OS では並列実行するための Task を実行する Code Gear と実行に必要な Input Data Gear 、出力される Output Data Gear の組で表現する。 101 Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
120 Input/Output Data Gear によって依存関係が決定し並列実行を行う。 102 Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。
121 103
122 Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。Meta Code Gear は通常の Code Gear の直後に遷移され、Meta Computation を実行する。 104 Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。Meta Code Gear は通常の Code Gear の直後に遷移され、Meta Computation を実行する。
123 105
124 CbC では処理を Code Segment を用いたプログラミング言語であるため、 Gears OS の Code Gear を記述するのに適している。 106 CbC では処理を Code Segment を用いたプログラミング言語であるため、 Gears OS の Code Gear を記述するのに適している。
125 そこで Gears OS の構文のサポートを CbC を用いて行う。 107 そこで Gears OS の構文のサポートが必要になる。現在は python を用いたプログラム変換で実現されている。
126 108
127 Gears OS では Context という接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Dara Gear である。Gears OS では必要な Code/Data Gear に参照したい場合、Context を通す必要がある。 109 Gears OS では Context という接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Dara Gear である。Gears OS では必要な Code/Data Gear に参照したい場合、Context を通す必要がある。
128 110 Context の自動生成を行うようにする。
129 Context は膨大であるためプログラマが記述するには負担であるため CbC では Context の自動生成を行うようにする。
130 111
131 \section{今後の課題} 112 \section{今後の課題}
132 本研究では LLVM/clang によるコンパイルの際、Code Segment 内の局所変数で tail call が出ない不具合を修正した。今後の課題としては、まだ Gears OS の構文サポートの実装が行われていないのでこれを実装することが優先される。 113 今後の課題は現状の Gears OS のコードをリファクタリングし通常計算とメタ計算の分離を明確にする。
114 必要なメタ計算部分の CbC による実装を統一する。
115 Context 、 Meta Code Gear 、 Meta Data Gear を生成するプログラム変換系を作成する。
116 これを用いて Gears OS の記述を行う。
117 これにより Gears OS のメタ計算を柔軟に行うことができるようになり、 Gears OS 自体の信頼性を向上し, Gears OS の拡張性を実現することができると考えられる。
133 118
134 \begin{thebibliography}{9} 119 \begin{thebibliography}{9}
135 \bibitem{1} 120 \bibitem{1}
136 徳森 海斗 : LLVM Clang 上の Continuation based C コンパイラ の改良, 121 徳森 海斗 : LLVM Clang 上の Continuation based C コンパイラ の改良,
137 \bibitem{2} 122 \bibitem{2}