Mercurial > hg > Papers > 2012 > nobu-thesis

--- a/paper/thesis.tex	Mon Feb 27 16:07:40 2012 +0900
+++ b/paper/thesis.tex	Mon Feb 27 18:34:32 2012 +0900
@@ -83,6 +83,7 @@
 %謝辞
 \input{thanx.tex}

+
 %参考文献
 \nocite{*}
 \bibliographystyle{junsrt}
--- a/presen/cbc.md	Mon Feb 27 16:07:40 2012 +0900
+++ b/presen/cbc.md	Mon Feb 27 18:34:32 2012 +0900
@@ -3,46 +3,20 @@

 ---

-はじめに
+研究の背景と成果
 ---------

 .notes: plop

-- 当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。
-- コードセグメントは C の関数よりも細かな単位で、状態を表すことができる。
-- その為 CbC では状態遷移記述を行うことが出来、状態探索といったモデル検査等に使えると考えている。
-
----
-
-研究の目的
----------
-
+- 当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。
 - CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。
 - しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。
 - また、GCC の最新の機能を使用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。
-- 本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートをすると共に実装の修正を行った。
+
+<h2>本研究では CbC-GCC のアップデートを行い、より良いコードを生成する CbC の処理系を開発した。</h2>

 ---

-発表内容
-========
-
-.fx: foo bar
-
-<ul>
-<li>Continuation based C</li>
-<li>CbC の実装(修正点)</li>
-<ol>
-<li>Tail Call Elimination の強制付与</li>
-</ol>
-<li>性能評価</li>
-<li>まとめ</li>
-</ul>
-
-
----
-
-
 Continuation based C
 ========
 コードセグメント単位での記述と継続を基本としたプログラミング言語
@@ -209,7 +183,7 @@

 CbC の実装: Tail Call Elimination
 ========
-Tail Call Elimination の条件をチェックする expand_call関数
+Tail Call Elimination の条件をチェックする関数
 ---------
 - 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。
 - この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
@@ -236,10 +210,11 @@
     <img src="./pix/conv1_mac_for_presen.png" style="height:15em">
   </td>
 </table>
-
+<li>GCC-4.5 では動かなかったプログラムが GCC-4.6 では問題なく動いている。</li>
 <li>引数 2、3 の結果はほぼ同じ</li>
 <li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li>

+
 ---


@@ -257,13 +232,13 @@
       <img src="./pix/state_conv1_noopt.png">
   </td>
   <tr>
-    <td>GCC-4.5<br>の最適化</td>
+    <td>GCC-4.5<br>の最適化<br>(-O2)</td>
     <td style="margin:auto; text-align:center;">
     <img src="./pix/state_conv1_45.png">
   </td>
   </tr>
   <tr>
-    <td>GCC-4.6<br>の最適化</td>
+    <td>GCC-4.6<br>の最適化<br>(-O2)</td>
     <td style="margin:auto; text-align:center;">
       <img src="./pix/state_conv1_46.png">
     </td>
@@ -312,6 +287,47 @@

 ---

+jmp と call
+========
+<table width=100%>
+<caption>インライン展開無しの conv1 プログラム実行結果</caption>
+<td style="text-align:center;">
+<img src="./pix/fno_inline.png">
+</td>
+</table>
+
+<li>引数 0 は C の関数で書かれたプログラム</li>
+<li>引数 3 は引数 0 のプログラムをただ CbC に書き直したもの</li>
+
+---
+
+
+構文の追加
+========
+リカーシブタイプの宣言に使う"__rectype"
+---------
+- 関数宣言時、以下のように引数に自分自身を指す型を入れたい。
+<pre>
+\_\_code func(int, func*);
+<pre>
+- 上記の宣言ではエラーがでる。その為、以下のような宣言になる。
+<pre>
+\_\_code func(int, \_\_code (*)());
+</pre>
+- しかし、これでは正しい情報をコンパイラに渡せていない。関数ポインタの引数に型情報が入っていないからである。
+<pre>
+\_\_code func(int, \_\_code (*)(int, \_\_code(*)(int, \_\_code(*)(int, ...))))
+</pre>
+- だが、正しい情報を渡そうとすると上記のように再帰してしまい、宣言できない。
+- そこで __rectype という構文を追加して宣言中の関数自身を指すようにした。
+<pre>
+\_\_code func(int, rectype*);
+</pre>
+
+
+---
+
+
 conv1 プログラム
 ========
 - conv1 プログラムでは計算と継続を交互に繰り返し行なう。
--- a/presen/presen.css	Mon Feb 27 16:07:40 2012 +0900
+++ b/presen/presen.css	Mon Feb 27 18:34:32 2012 +0900
@@ -1,3 +1,2 @@
-.incremental {
+.hideme, .incremental {visibility: hidden;}

-}
\ No newline at end of file
--- a/presen/presentation.html	Mon Feb 27 16:07:40 2012 +0900
+++ b/presen/presentation.html	Mon Feb 27 18:34:32 2012 +0900
@@ -85,15 +85,17 @@
         <div class="slide has_notes">
           <div class="inner">

-            <header><h2>はじめに</h2></header>
+            <header><h2>研究の背景と成果</h2></header>


             <section><p class="notes">plop</p>
 <ul>
-<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。</li>
-<li>コードセグメントは C の関数よりも細かな単位で、状態を表すことができる。</li>
-<li>その為 CbC では状態遷移記述を行うことが出来、状態探索といったモデル検査等に使えると考えている。</li>
-</ul></section>
+<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。</li>
+<li>CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。</li>
+<li>しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。</li>
+<li>また、GCC の最新の機能を使用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。</li>
+</ul>
+<h2>本研究では CbC-GCC のアップデートを行い、より良いコードを生成する CbC の処理系を開発した。</h2></section>

           </div>
           <div class="presenter_notes">
@@ -120,79 +122,6 @@
         <div class="slide">
           <div class="inner">

-            <header><h2>研究の目的</h2></header>
-
-
-            <section><ul>
-<li>CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。</li>
-<li>しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。</li>
-<li>また、GCC の最新の機能を使用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。</li>
-<li>本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートをすると共に実装の修正を行った。</li>
-</ul></section>
-
-          </div>
-          <div class="presenter_notes">
-            <header><h1>Presenter Notes</h1></header>
-            <section>
-
-            </section>
-          </div>
-          <footer>
-
-            <aside class="source">
-              Source: <a href="./cbc.md">./cbc.md</a>
-            </aside>
-
-            <aside class="page_number">
-              3/21
-            </aside>
-          </footer>
-        </div>
-      </div>
-
-      <!-- slide source: ./cbc.md -->
-      <div class="slide-wrapper">
-        <div class="slide foo bar">
-          <div class="inner">
-
-            <header><h1>発表内容</h1></header>
-
-
-            <section><ul>
-<li>Continuation based C</li>
-<li>CbC の実装(修正点)</li>
-<ol>
-<li>Tail Call Elimination の強制付与</li>
-</ol>
-<li>性能評価</li>
-<li>まとめ</li>
-</ul></section>
-
-          </div>
-          <div class="presenter_notes">
-            <header><h1>Presenter Notes</h1></header>
-            <section>
-
-            </section>
-          </div>
-          <footer>
-
-            <aside class="source">
-              Source: <a href="./cbc.md">./cbc.md</a>
-            </aside>
-
-            <aside class="page_number">
-              4/21
-            </aside>
-          </footer>
-        </div>
-      </div>
-
-      <!-- slide source: ./cbc.md -->
-      <div class="slide-wrapper">
-        <div class="slide">
-          <div class="inner">
-
             <header><h1>Continuation based C</h1></header>


@@ -225,7 +154,7 @@
             </aside>

             <aside class="page_number">
-              5/21
+              3/21
             </aside>
           </footer>
         </div>
@@ -284,7 +213,7 @@
             </aside>

             <aside class="page_number">
-              6/21
+              4/21
             </aside>
           </footer>
         </div>
@@ -348,7 +277,7 @@
             </aside>

             <aside class="page_number">
-              7/21
+              5/21
             </aside>
           </footer>
         </div>
@@ -407,7 +336,7 @@
             </aside>

             <aside class="page_number">
-              8/21
+              6/21
             </aside>
           </footer>
         </div>
@@ -450,7 +379,7 @@
             </aside>

             <aside class="page_number">
-              9/21
+              7/21
             </aside>
           </footer>
         </div>
@@ -464,7 +393,7 @@
             <header><h1>CbC の実装: Tail Call Elimination</h1></header>


-            <section><h2>Tail Call Elimination の条件をチェックする expand_call関数</h2>
+            <section><h2>Tail Call Elimination の条件をチェックする関数</h2>
 <ul>
 <li>今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。</li>
 <li>この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
@@ -487,7 +416,7 @@
             </aside>

             <aside class="page_number">
-              10/21
+              8/21
             </aside>
           </footer>
         </div>
@@ -513,6 +442,8 @@
   </td>
 </table>

+<li>GCC-4.5 では動かなかったプログラムが GCC-4.6 では問題なく動いている。</li>
+
 <li>引数 2、3 の結果はほぼ同じ</li>

 <li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li></section>
@@ -531,7 +462,7 @@
             </aside>

             <aside class="page_number">
-              11/21
+              9/21
             </aside>
           </footer>
         </div>
@@ -557,13 +488,13 @@
       <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/state_conv1_noopt.png">
   </td>
   <tr>
-    <td>GCC-4.5<br>の最適化</td>
+    <td>GCC-4.5<br>の最適化<br>(-O2)</td>
     <td style="margin:auto; text-align:center;">
     <img src="./pix/state_conv1_45.png">
   </td>
   </tr>
   <tr>
-    <td>GCC-4.6<br>の最適化</td>
+    <td>GCC-4.6<br>の最適化<br>(-O2)</td>
     <td style="margin:auto; text-align:center;">
       <img src="./pix/state_conv1_46.png">
     </td>
@@ -584,7 +515,7 @@
             </aside>

             <aside class="page_number">
-              12/21
+              10/21
             </aside>
           </footer>
         </div>
@@ -619,7 +550,7 @@
             </aside>

             <aside class="page_number">
-              13/21
+              11/21
             </aside>
           </footer>
         </div>
@@ -653,7 +584,7 @@
             </aside>

             <aside class="page_number">
-              14/21
+              12/21
             </aside>
           </footer>
         </div>
@@ -693,6 +624,93 @@
             </aside>

             <aside class="page_number">
+              13/21
+            </aside>
+          </footer>
+        </div>
+      </div>
+
+      <!-- slide source: ./cbc.md -->
+      <div class="slide-wrapper">
+        <div class="slide">
+          <div class="inner">
+
+            <header><h1>jmp と call</h1></header>
+
+
+            <section><p><table width=100%>
+<caption>インライン展開無しの conv1 プログラム実行結果</caption>
+<td style="text-align:center;">
+<img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/fno_inline.png">
+</td>
+</table></p>
+<li>引数 0 は C の関数で書かれたプログラム</li>
+
+<li>引数 3 は引数 0 のプログラムをただ CbC に書き直したもの</li></section>
+
+          </div>
+          <div class="presenter_notes">
+            <header><h1>Presenter Notes</h1></header>
+            <section>
+
+            </section>
+          </div>
+          <footer>
+
+            <aside class="source">
+              Source: <a href="./cbc.md">./cbc.md</a>
+            </aside>
+
+            <aside class="page_number">
+              14/21
+            </aside>
+          </footer>
+        </div>
+      </div>
+
+      <!-- slide source: ./cbc.md -->
+      <div class="slide-wrapper">
+        <div class="slide">
+          <div class="inner">
+
+            <header><h1>構文の追加</h1></header>
+
+
+            <section><h2>リカーシブタイプの宣言に使う"__rectype"</h2>
+<ul>
+<li>関数宣言時、以下のように引数に自分自身を指す型を入れたい。
+<pre>
+__code func(int, func*);
+<pre></li>
+<li>上記の宣言ではエラーがでる。その為、以下のような宣言になる。
+<pre>
+__code func(int, __code (*)());
+</pre></li>
+<li>しかし、これでは正しい情報をコンパイラに渡せていない。関数ポインタの引数に型情報が入っていないからである。
+<pre>
+__code func(int, __code (<em>)(int, __code(</em>)(int, __code(*)(int, ...))))
+</pre></li>
+<li>だが、正しい情報を渡そうとすると上記のように再帰してしまい、宣言できない。</li>
+<li>そこで __rectype という構文を追加して宣言中の関数自身を指すようにした。
+<pre>
+__code func(int, rectype*);
+</pre></li>
+</ul></section>
+
+          </div>
+          <div class="presenter_notes">
+            <header><h1>Presenter Notes</h1></header>
+            <section>
+
+            </section>
+          </div>
+          <footer>
+
+            <aside class="source">
+              Source: <a href="./cbc.md">./cbc.md</a>
+            </aside>
+
+            <aside class="page_number">
               15/21
             </aside>
           </footer>
@@ -1028,19 +1046,20 @@


         <tr id="toc-row-2" class="sub">
-          <th><a href="#slide2">はじめに</a></th>
+          <th><a href="#slide2">研究の背景と成果</a></th>
           <td><a href="#slide2">2</a></td>
         </tr>

-        <tr id="toc-row-3" class="sub">
-          <th><a href="#slide3">研究の目的</a></th>
-          <td><a href="#slide3">3</a></td>
-        </tr>
-


+      <tr id="toc-row-3">
+        <th><a href="#slide3">Continuation based C</a></th>
+        <td><a href="#slide3">3</a></td>
+      </tr>
+
+
       <tr id="toc-row-4">
-        <th><a href="#slide4">発表内容</a></th>
+        <th><a href="#slide4">Continuation based C</a></th>
         <td><a href="#slide4">4</a></td>
       </tr>

@@ -1052,61 +1071,61 @@


       <tr id="toc-row-6">
-        <th><a href="#slide6">Continuation based C</a></th>
+        <th><a href="#slide6">CbC の実装 : Tail Call Elimination</a></th>
         <td><a href="#slide6">6</a></td>
       </tr>


       <tr id="toc-row-7">
-        <th><a href="#slide7">Continuation based C</a></th>
+        <th><a href="#slide7">CbC の実装: Tail Call Elimination</a></th>
         <td><a href="#slide7">7</a></td>
       </tr>


       <tr id="toc-row-8">
-        <th><a href="#slide8">CbC の実装 : Tail Call Elimination</a></th>
+        <th><a href="#slide8">CbC の実装: Tail Call Elimination</a></th>
         <td><a href="#slide8">8</a></td>
       </tr>


       <tr id="toc-row-9">
-        <th><a href="#slide9">CbC の実装: Tail Call Elimination</a></th>
+        <th><a href="#slide9">性能評価</a></th>
         <td><a href="#slide9">9</a></td>
       </tr>


       <tr id="toc-row-10">
-        <th><a href="#slide10">CbC の実装: Tail Call Elimination</a></th>
+        <th><a href="#slide10">最適化の比較</a></th>
         <td><a href="#slide10">10</a></td>
       </tr>


       <tr id="toc-row-11">
-        <th><a href="#slide11">性能評価</a></th>
+        <th><a href="#slide11">GCC の最適化</a></th>
         <td><a href="#slide11">11</a></td>
       </tr>


       <tr id="toc-row-12">
-        <th><a href="#slide12">最適化の比較</a></th>
+        <th><a href="#slide12">アップデートに合わせる有用性</a></th>
         <td><a href="#slide12">12</a></td>
       </tr>


       <tr id="toc-row-13">
-        <th><a href="#slide13">GCC の最適化</a></th>
+        <th><a href="#slide13">まとめ</a></th>
         <td><a href="#slide13">13</a></td>
       </tr>


       <tr id="toc-row-14">
-        <th><a href="#slide14">アップデートに合わせる有用性</a></th>
+        <th><a href="#slide14">jmp と call</a></th>
         <td><a href="#slide14">14</a></td>
       </tr>


       <tr id="toc-row-15">
-        <th><a href="#slide15">まとめ</a></th>
+        <th><a href="#slide15">構文の追加</a></th>
         <td><a href="#slide15">15</a></td>
       </tr>