Mercurial > hg > Papers > 2017 > mitsuki-thesis

changeset 26:8644cade9765

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update
author mir3636
date Thu, 16 Feb 2017 09:19:18 +0900
parents 327435666caa
children f38236c1362e
files presen/index.html presen/slide.html presen/slide.md
diffstat 3 files changed, 41 insertions(+), 261 deletions(-) [+]
line wrap: on
line diff
--- a/presen/index.html	Thu Feb 16 08:14:21 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,248 +0,0 @@
-<!DOCTYPE html>
-
-<html>
-  <head>
-    <title>Presentation</title>
-    
-    <meta charset='utf-8'>
-    <script
-       src='./slides.js'></script>
-  </head>
-
-  <style>
-    /* Your individual styles here, or just use inline styles if that’s
-    what you want. */
-
-  </style>
-
-  <body style='display: none'>
-    <section class='slides layout-regular template-default'>
-
-      <!-- 
-           Your slides (<article>s) go here. Delete or comment out the
-           slides below.
-        -->
-      <article>
-        <h1>Implementation of CbC compiler on LLVM/clang 3.5</h1>
-        <h3 class="title">Kaito Tokumori　　27 Feb 2014</h3>
-        <div align="right">Teacher : Shinji Kono</div>
-      </article>
-
-      <article>
-        <h3>Introduction of CbC</h3>
-	<ul>
-          <li>CbC is programming language.
-          <li>CbC stands for Continuation based C.
-          <li>For pararell tasks.
-          <li>For state machine.
-          <li>For meta computation.
-	</ul>
-      </article>
-
-      <article>
-        <h3>CbC compilers</h3>
-	<ul>
-          <li>Micro-C
-          <li>GCC
-          <li>LLVM/clang  <font color="ff3300">&lt;= New!!</font>
-	</ul>
-      </article>
-
-      <article>
-        <h3>LLVM/clang??</h3>
-	<br>
-        <h3 class='yellow'>What??</h3>
-	<ul>
-          <li>LLVM is compiler framework.
-          <li>clang is C/C++/Obj-C compiler frontend.
-	</ul>
-        <h3 class='yellow'>Why??</h3>
-	<ul>
-          <li>Apple supported.
-          <li>OS X default compiler.
-          <li>LLVM IR (Intermidiate Representation).
-	</ul>
-      </article>
-
-      <article>
-        <h3>Basic strategy of implementation</h3>
-	<ul>
-          <li>A code segment is implemented by normal function.
-          <li>Transition is implemented by forced tail call.
-          <li>Goto with environment is implemented by setjmp/longjmp.
-          <li><span class='red'>Do not modify intermidiate code.</span>
-	</ul>
-      </article>
-
-      <article>
-        <h3>Problems</h3>
-	<ul>
-          <li>Code segment go-to moves between function.</li>
-          <li>LLVM IR jmp instruction is limited in a function.</li>
-          <li>LLVM IR can't express code segment jump...</li>
-          <br>
-	</ul>
-	<ul class="build">
-          <li>But LLVM has tail call elimination,<br>
-            so there is a way to generate unlimited jmp instruction in LLVM.</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>Solution</h3>
-        <pre>define fastcc void @factorial(i32 %x) #0 {
-entry:
-  <span class="red">tail</span> call <span class="red">fastcc</span> void @factorial0(i32 1, i32 %x)
-  ret void
-}</pre>
-	<ul>
-          <li>LLVM IR has call flag.
-          <li>Tail and fastcc flag are enable to tail call elimination!
-          <li><h3 class='yellow'>We can implement CbC compiler on LLVM!!</h3>
-	</ul>
-      </article>
-
-      <article>
-        <h3>Structure of LLVM/clang</h3>
-	<div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div>
-      </article>
-
-      <article>
-        <h3>Implementation on parser</h3>
-	<div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div>
-	<ul>
-          <li>Code segment type</li>
-          <li>Goto syntax</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>Implementation on parser</h3>
-	<div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div>
-	<ul>
-          <!-- <li>Goto with environment</li> -->
-          <li>Include setjmp.h always.
-          <li>Generate C struct for saving environment.
-          <li>Insert setjmp statement.
-          <li>Generate longjmp code segment as return.
-	</ul>
-      </article>
-
-      <article>
-        <h3>Implementation on code generator</h3>
-	<div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div>
-	<ul>
-          <!-- <li>Keep tail call elimination</li> -->
-          <li>Enable to tailcallopt LangOption.
-          <li>Add a return statement after code sgment call.
-          <li>Add fastcc calling convention.
-          <li>Enable to TailCallElim pass.
-	</ul>
-      </article>
-
-
-      <article class='smaller'>
-        <h3>Compiling result</h3>
-          <table  border="0">
-            <tbody>
-              <tr>
-                <td>
-		  <pre>__code factorial(int x)
-{
-  goto factorial0(1, x);
-}
-</pre>
-		</td>
-                <td>
-		  <pre>_factorial:               ## @factorial
-    .cfi_startproc
-## BB#0:                ## %entry
-    pushq    %rbp
-Ltmp12:
-    .cfi_def_cfa_offset 16
-Ltmp13:
-    .cfi_offset %rbp, -16
-    movq    %rsp, %rbp
-Ltmp14:
-    .cfi_def_cfa_register %rbp
-    movl    $1, %eax
-    movl    %edi, -4(%rbp)      ## 4-byte Spill
-    movl    %eax, %edi
-    movl    -4(%rbp), %esi      ## 4-byte Reload
-    popq    %rbp
-    <span class="red">jmp    _factorial0       ## TAILCALL</span>
-    .cfi_endproc</pre>
-		</td>
-              </tr>
-            </tbody>
-          </table>
-	<ul>
-          <li>Jmp instructions are in assembler source.</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>Benchmark result</h3>
-          <table  border="2" style="font-size:18pt;">
-            <tbody>
-              <tr>
-                <td bgcolor="#8091B5"></td>
-                <td style="text-align: center;">no optimized code</td>
-                <td style="text-align: center;">optimized code A</td>
-                <td style="text-align: center;">optimized code B</td>
-              </tr>
-              <tr>
-                <td style="text-align: center;">Micro-C</td>
-                <td style="text-align: right;">6.06 s</td>
-                <td style="text-align: right;">2.21 s</td>
-                <td style="text-align: right;">2.40 s</td>
-              </tr>
-              <!-- <tr> -->
-              <!--   <td style="text-align: center;">GCC -O0</td> -->
-              <!--   <td style="text-align: right;">1.59 s</td> -->
-              <!--   <td style="text-align: right;">1.02 s</td> -->
-              <!--   <td style="text-align: right;">0.99 s</td> -->
-              <!-- </tr> -->
-              <tr>
-                <td style="text-align: center;">GCC -O2</td>
-                <td style="text-align: right;">1.59 s</td>
-                <td style="text-align: right;">1.02 s</td>
-                <td style="text-align: right;">0.99 s</td>
-              </tr>
-              <!-- <tr> -->
-              <!--   <td style="text-align: center;">LLVM -O0</td> -->
-              <!--   <td style="text-align: right;">5.52 s</td> -->
-              <!--   <td style="text-align: right;">3.95 s</td> -->
-              <!--   <td style="text-align: right;">4.64 s</td> -->
-              <!-- </tr> -->
-              <tr>
-                <td style="text-align: center;">LLVM -O2</td>
-                <td style="text-align: right;">5.52 s</td>
-                <td style="text-align: right;">3.95 s</td>
-                <td style="text-align: right;">4.64 s</td>
-              </tr>
-            </tbody>
-          </table>
-	<ul>
-	  <li>LLVM can compile CbC examples like other CbC compilers.</li>
-	  <li>LLVM is slower than other compilers but it is not important for us.</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>Conclusion</h3>
-	<ul>
-          <li>We can use LLVM/clang to compile CbC code.</li>
-          <li>We did not modify LLVM IR to implement CbC compiler.</li>
-	</ul>
-	<h3 class='yellow'>Future</h3>
-	<ul>
-          <li>Data segment interface</li>
-          <li>Meta computation</li>
-          <li>Dynamic rewriting of a jmp</li>
-          <li>Generating specialized code</li>
-	</ul>
-      </article>
-
-  </body>
-</html>
--- a/presen/slide.html	Thu Feb 16 08:14:21 2017 +0900
+++ b/presen/slide.html	Thu Feb 16 09:19:18 2017 +0900
@@ -87,7 +87,7 @@
 <!-- === begin markdown block ===
 
       generated by markdown/1.2.0 on Ruby 2.2.0 (2014-12-25) [x86_64-darwin13]
-                on 2017-02-16 08:10:32 +0900 with Markdown engine kramdown (1.9.0)
+                on 2017-02-16 09:18:39 +0900 with Markdown engine kramdown (1.9.0)
                   using options {}
   -->
 
@@ -106,6 +106,7 @@
 <!-- _S9SLIDE_ -->
 <h1 id="code-gear--data-gear">Code Gear と Data Gear</h1>
 <ul>
+  <li>Code Gear とはプログラムの処理の単位である。</li>
   <li>Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。</li>
   <li>Data Gear はデータの単位であり、Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。</li>
 </ul>
@@ -150,7 +151,7 @@
 <!-- _S9SLIDE_ -->
 <h1 id="context">Context</h1>
 <ul>
-  <li>Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。</li>
+  <li>Gears OS には Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。</li>
   <li>Gears OSは必要なCode/DataGearに参照したい場合、このContext を通す必要がある。</li>
 </ul>
 
@@ -213,7 +214,7 @@
 <ul lang="impl">
   <li>interface を記述することで Context を通して Code Gear が参照できるようになった。</li>
   <li>create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。</li>
-  <li>return で interface を返し、その先で指定した Code Gear へ継続できるようになる。</li>
+  <li>return で interface を返し、その先で inter face の持つ Code Gear へと継続できるようになる。</li>
 </ul>
 <pre><code>Stack* createSingleLinkedStack(struct Context* context) {
     struct Stack* stack = new Stack();
@@ -235,7 +236,7 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="contextstub-code-segment-">Context、stub Code Segment の自動生成</h1>
+<h1 id="contextstub-code-gear-">Context、stub Code Gear の自動生成</h1>
 <ul>
   <li>Gears OS では通常の計算の他に Context や stub などの meta computation を記述する必要がある。</li>
   <li>現在の CbC で Gears OS を記述すると、この meta computation の記述も行わなくてはならず、これには多くの労力を要する。</li>
@@ -246,10 +247,26 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h1 id="generate-context">generate context</h1>
+<h1 id="stub-code-gear-">stub Code Gear の生成</h1>
 <ul>
-  <li>generate_stub は指定された cbc ファイルの __code型である Code Gear を取得</li>
-  <li>generate_context は context.h から Data Gear、c ファイルから Code Gear の取得
+  <li>stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。</li>
+  <li>stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。</li>
+  <li>generate_stub は指定された cbc ファイルの __code型である Code Gear を取得。</li>
+  <li>引数と interface を照らし合わせ、Gearef または GearImpl を決定する。</li>
+  <li>cbc ファイルのから、生成した stub Code Gear を加えて、c ファイルを生成する。</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h1 id="context-">Context の生成</h1>
+<ul>
+  <li>Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。</li>
+  <li>generate_context は context.h から Data Gear、c ファイルから Code Gear を取得。</li>
+  <li>取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。</li>
+  <li>generate_context は取得した Code/Data Gear から Context の生成を行うコードを生成する。</li>
+  <li>これらを自動生成することで Gears OS の記述量を約半分にすることができます。
 <img src="./fig/generate_context.svg" alt="message" width="800" /></li>
 </ul>
 
--- a/presen/slide.md	Thu Feb 16 08:14:21 2017 +0900
+++ b/presen/slide.md	Thu Feb 16 09:19:18 2017 +0900
@@ -11,6 +11,7 @@
 - そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
 
 # Code Gear と Data Gear
+- Code Gear とはプログラムの処理の単位である。
 - Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
 - Data Gear はデータの単位であり、Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
 
@@ -38,7 +39,7 @@
 - Meta Code Gear で OS の 機能であるメモリ管理やスレッド管理を行う。
 
 # Context
-- Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
+- Gears OS には Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
 - Gears OSは必要なCode/DataGearに参照したい場合、このContext を通す必要がある。
 
 # Gearef、GearImpl
@@ -84,7 +85,7 @@
 # interface の記述
 - interface を記述することで Context を通して Code Gear が参照できるようになった。
 - create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
-- return で interface を返し、その先で指定した Code Gear へ継続できるようになる。
+- return で interface を返し、その先で inter face の持つ Code Gear へと継続できるようになる。
 ```impl
 Stack* createSingleLinkedStack(struct Context* context) {
     struct Stack* stack = new Stack();
@@ -102,14 +103,24 @@
 }
 ```
 
-# Context、stub Code Segment の自動生成
+# Context、stub Code Gear の自動生成
 - Gears OS では通常の計算の他に Context や stub などの meta computation を記述する必要がある。
 - 現在の CbC で Gears OS を記述すると、この meta computation の記述も行わなくてはならず、これには多くの労力を要する。
 - この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。
 
-# generate context 
-- generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得
-- generate\_context は context.h から Data Gear、c ファイルから Code Gear の取得
+# stub Code Gear の生成
+- stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
+- stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
+- generate_stub は指定された cbc ファイルの __code型である Code Gear を取得。
+- 引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
+- cbc ファイルのから、生成した stub Code Gear を加えて、c ファイルを生成する。
+
+# Context の生成
+- Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。 
+- generate_context は context.h から Data Gear、c ファイルから Code Gear を取得。
+- 取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
+- generate_context は取得した Code/Data Gear から Context の生成を行うコードを生成する。
+- これらを自動生成することで Gears OS の記述量を約半分にすることができます。
 <img src="./fig/generate_context.svg" alt="message" width="800" >
 
 # 今後の課題