Mercurial > hg > Papers > 2012 > nobu-thesis

changeset 37:cee254f6af59 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 28 Feb 2012 05:23:38 +0900
parents 975da5d0699e
children bbebd829c423
files paper/graffle/continuation.graffle paper/graffle/fno_inline.graffle presen/cbc.md presen/pix/continuation.png presen/pix/fno_inline.png presen/presentation.html
diffstat 6 files changed, 132 insertions(+), 109 deletions(-) [+]
line wrap: on
line diff
--- a/paper/graffle/continuation.graffle	Tue Feb 28 03:55:43 2012 +0900
+++ b/paper/graffle/continuation.graffle	Tue Feb 28 05:23:38 2012 +0900
@@ -153,7 +153,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{272, 99}, {41, 28}}</string>
+			<string>{{272, 113}, {41, 28}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -212,7 +212,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{164, 67}, {41, 28}}</string>
+			<string>{{163, 95}, {41, 28}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -336,12 +336,12 @@
 			<dict>
 				<key>stroke</key>
 				<dict>
+					<key>CornerRadius</key>
+					<real>80</real>
 					<key>HeadArrow</key>
 					<string>FilledArrow</string>
 					<key>HeadScale</key>
 					<real>1.4285709857940674</real>
-					<key>LineType</key>
-					<integer>1</integer>
 					<key>TailArrow</key>
 					<string>0</string>
 					<key>TailScale</key>
@@ -380,12 +380,12 @@
 			<dict>
 				<key>stroke</key>
 				<dict>
+					<key>CornerRadius</key>
+					<real>50</real>
 					<key>HeadArrow</key>
 					<string>FilledArrow</string>
 					<key>HeadScale</key>
 					<real>1.4285709857940674</real>
-					<key>LineType</key>
-					<integer>1</integer>
 					<key>TailArrow</key>
 					<string>0</string>
 					<key>TailScale</key>
@@ -424,12 +424,12 @@
 			<dict>
 				<key>stroke</key>
 				<dict>
+					<key>CornerRadius</key>
+					<real>50</real>
 					<key>HeadArrow</key>
 					<string>FilledArrow</string>
 					<key>HeadScale</key>
 					<real>1.4285709857940674</real>
-					<key>LineType</key>
-					<integer>1</integer>
 					<key>TailArrow</key>
 					<string>0</string>
 					<key>TailScale</key>
@@ -578,10 +578,10 @@
 				<key>Text</key>
 				<string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230
 {\fonttbl\f0\fswiss\fcharset0 Helvetica;}
-{\colortbl;\red255\green255\blue255;\red0\green0\blue0;}
+{\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs28 \cf2 func\
+\f0\fs28 \cf0 func\
 A}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
@@ -635,7 +635,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2011-11-15 23:58:55 +0000</string>
+	<string>2012-02-27 19:55:32 +0000</string>
 	<key>Modifier</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>NotesVisible</key>
--- a/paper/graffle/fno_inline.graffle	Tue Feb 28 03:55:43 2012 +0900
+++ b/paper/graffle/fno_inline.graffle	Tue Feb 28 05:23:38 2012 +0900
@@ -191,7 +191,7 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs24 \cf0 ./conv1 0}</string>
+\f0\fs24 \cf0 C}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
 			</dict>
@@ -538,7 +538,7 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc
 
-\f0\fs24 \cf0 ./conv1 3}</string>
+\f0\fs24 \cf0 CbC}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
 			</dict>
@@ -647,7 +647,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2012-02-27 16:00:40 +0000</string>
+	<string>2012-02-27 19:00:14 +0000</string>
 	<key>Modifier</key>
 	<string>Nobuyasu Oshiro</string>
 	<key>NotesVisible</key>
--- a/presen/cbc.md	Tue Feb 28 03:55:43 2012 +0900
+++ b/presen/cbc.md	Tue Feb 28 05:23:38 2012 +0900
@@ -3,11 +3,15 @@
 
 ---
 
-研究の背景と成果
+研究目的
 ---------
 
 .notes: plop
 
+<li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li>
+- 組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース
+- 現存する記述言語は状態遷移の記述に向いていない
+- スタックが状態を隠蔽するため、分割しにくい、検証が難しい
 - 当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。
 - CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。
 - しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。
@@ -29,10 +33,21 @@
 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li>
 </ul>
 
-<table width=100% >
-    <td style="margin-left:auto; margin-right: auto; text-align: center;">
-      <img src="./pix/codesegment.png" style="height:14em;">
+<table width=100%  border=1>
+  <tr>
+    <td style="margin-left:auto; margin-right: auto; text-align: center; width:50%" >
+      <img src="./pix/codesegment.png" style="width:100%">
     </td>
+    <td>
+      <pre style="margin-left:5%">
+__code cs_a(int num) {
+   :
+   :
+   goto cs_b();
+}
+      </pre>
+    </td>
+  </tr>
 </table>
 
 
@@ -81,37 +96,37 @@
 ========
 <table width=100% border=1>
 <caption>階乗を求める CbC のプログラム</caption>
-<td>
-<pre>
-    \_\_code print_factorial(int prod)
-    {
-      printf("factorial = %d\n",prod);
-      exit(0);
-    }
-    \_\_code factorial0(int prod, int x)
-    {
-      if ( x >= 1) {
-        goto factorial0(prod*x, x-1);
-      }else{
-        goto print_factorial(prod);
-      }
-    }
-    \_\_code factorial(int x)
-    {
-      goto factorial0(1, x);
-    }
-    int main(int argc, char **argv)
-    {
-      int i;
-      i = atoi(argv[1]);
-      goto factorial(i);
-    }
+<td width=50%>
+<pre style="margin-left:5%">
+\_\_code print_factorial(int prod)
+{
+  printf("factorial = %d\n",prod);
+  exit(0);
+}
+\_\_code factorial0(int prod, int x)
+{
+  if ( x >= 1) {
+    goto factorial0(prod\*x, x-1);
+  }else{
+    goto print_factorial(prod);
+  }
+}
+\_\_code factorial(int x)
+{
+  goto factorial0(1, x);
+}
+int main(int argc, char \*\*argv)
+{
+  int i;
+  i = atoi(argv[1]);
+  goto factorial(i);
+}
 </pre>
 </td>
 <td>
 <li>__code によるコードセグメントの宣言</li>
-<li>goto によるコードセグメントへの継続</li>
-<li>call ではなく jmp で処理を移る</li>
+<li>引数付きの goto でコードセグメントを呼び出すことができる</li>
+<li>内部では call ではなく jmp 命令でコードセグメントの処理が遷移している</li>
 </td>
 </table>
 
@@ -120,7 +135,7 @@
 
 Gnu Compiler Collection (GCC)
 ========
-<li>GCC: オープンソースのコンパイル群</li>
+<li>GCC: オープンソースのコンパイラ群</li>
 <li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li>
 <li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li>
 <table width=100%>
@@ -137,7 +152,7 @@
 
 CbC の実装 : 軽量継続
 ========
-<li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li>
+<li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Elimination(末尾除去)</font>により実装されている.</li>
 
 Tail Call Elimination
 ---------
@@ -162,8 +177,7 @@
   int main() {
     g(3,4);
     return 0;
-  }
-      </pre>
+  }</pre>
     </td>
     <td>
       <img src="./pix/continuation.png" style="height:80%;">
@@ -180,9 +194,9 @@
 Tail Call Elimination の条件
 ---------
 <ul>
-  <li>caller側とcallee側の戻値の型の一致している。</li>
+  <li>関数を呼び出す側(caller)と呼び出される側(callee)の戻値の型が一致している。</li>
   <li>関数呼び出しがリターン直前に行われている。</li>
-  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
+  <li>呼び出される関数(callee)の引数に用いられるスタックサイズが呼出元(caller)のそれより少ない。</li>
   <li>引数の並びのコピーに上書きがない。</li>
 </ul>
 
@@ -206,11 +220,11 @@
 - この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
 必要があった。
 
-実装の修正と修正による利点
+実装の修正とその利点
 ---------
 - しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。
 - 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。
-- また、コードセグメントへの継続が jmp ではなく call 命令で行われる場合があったが
+- また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。
 
 
 ---
@@ -218,7 +232,7 @@
 
 
 
-性能評価
+GCC-4.5, GCC-4.6 の性能比較
 ========
 <li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li>
 <li>この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。</li>
@@ -260,7 +274,7 @@
 <caption><h3>インライン展開の例</h3></caption>
 <tr>
 <td width=50%>
-<pre>
+<pre style="margin-left:5%">
 void func(){
   A;
   B;
@@ -273,7 +287,7 @@
 </pre>
 </td>
 <td>
-<pre>
+<pre style="margin-left:5%">
 int main() {
   A;
   B;
@@ -333,7 +347,7 @@
 ========
 - 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。
 - アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。
-- また、最適化の強制付与や環境付き継続の部分といった実装の修正も行えた。
+- また、最適化の強制付与やといった実装の修正も行えた。
 - 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。
 
 
@@ -353,9 +367,6 @@
 </td>
 </table>
 
-<li>引数 0 は C の関数で書かれたプログラム</li>
-<li>引数 3 は引数 0 のプログラムをただ CbC に書き直したもの</li>
-
 ---
 
 
Binary file presen/pix/continuation.png has changed
Binary file presen/pix/fno_inline.png has changed
--- a/presen/presentation.html	Tue Feb 28 03:55:43 2012 +0900
+++ b/presen/presentation.html	Tue Feb 28 05:23:38 2012 +0900
@@ -85,11 +85,16 @@
         <div class="slide has_notes">
           <div class="inner">
             
-            <header><h2>研究の背景と成果</h2></header>
+            <header><h2>研究目的</h2></header>
             
             
             <section><p class="notes">plop</p>
+<li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li>
+
 <ul>
+<li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
+<li>現存する記述言語は状態遷移の記述に向いていない</li>
+<li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
 <li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。</li>
 <li>CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。</li>
 <li>しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。</li>
@@ -134,10 +139,21 @@
 <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li>
 </ul>
 
-<table width=100% >
-    <td style="margin-left:auto; margin-right: auto; text-align: center;">
-      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/codesegment.png" style="height:14em;">
+<table width=100%  border=1>
+  <tr>
+    <td style="margin-left:auto; margin-right: auto; text-align: center; width:50%" >
+      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/codesegment.png" style="width:100%">
     </td>
+    <td>
+      <pre style="margin-left:5%">
+__code cs_a(int num) {
+   :
+   :
+   goto cs_b();
+}
+      </pre>
+    </td>
+  </tr>
 </table></section>
             
           </div>
@@ -229,37 +245,37 @@
             
             <section><p><table width=100% border=1>
 <caption>階乗を求める CbC のプログラム</caption>
-<td>
-<pre>
-    __code print_factorial(int prod)
-    {
-      printf("factorial = %d\n",prod);
-      exit(0);
-    }
-    __code factorial0(int prod, int x)
-    {
-      if ( x &gt;= 1) {
-        goto factorial0(prod<em>x, x-1);
-      }else{
-        goto print_factorial(prod);
-      }
-    }
-    __code factorial(int x)
-    {
-      goto factorial0(1, x);
-    }
-    int main(int argc, char </em>*argv)
-    {
-      int i;
-      i = atoi(argv[1]);
-      goto factorial(i);
-    }
+<td width=50%>
+<pre style="margin-left:5%">
+__code print_factorial(int prod)
+{
+  printf("factorial = %d\n",prod);
+  exit(0);
+}
+__code factorial0(int prod, int x)
+{
+  if ( x &gt;= 1) {
+    goto factorial0(prod*x, x-1);
+  }else{
+    goto print_factorial(prod);
+  }
+}
+__code factorial(int x)
+{
+  goto factorial0(1, x);
+}
+int main(int argc, char **argv)
+{
+  int i;
+  i = atoi(argv[1]);
+  goto factorial(i);
+}
 </pre>
 </td>
 <td>
 <li>__code によるコードセグメントの宣言</li>
-<li>goto によるコードセグメントへの継続</li>
-<li>call ではなく jmp で処理を移る</li>
+<li>引数付きの goto でコードセグメントを呼び出すことができる</li>
+<li>内部では call ではなく jmp 命令でコードセグメントの処理が遷移している</li>
 </td>
 </table></p></section>
             
@@ -291,7 +307,7 @@
             <header><h1>Gnu Compiler Collection (GCC)</h1></header>
             
             
-            <section><p><li>GCC: オープンソースのコンパイル群</li>
+            <section><p><li>GCC: オープンソースのコンパイラ群</li>
 <li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li>
 <li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li>
 <table width=100%>
@@ -331,7 +347,7 @@
             <header><h1>CbC の実装 : 軽量継続</h1></header>
             
             
-            <section><p><li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li></p>
+            <section><p><li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Elimination(末尾除去)</font>により実装されている.</li></p>
 <h2>Tail Call Elimination</h2>
 <p><li>関数呼び出しを call ではなく jmp 命令で行う最適化</li>
 <li>例えば、以下の場合関数 g は jmp 命令で関数 f へと処理が移る</li></p>
@@ -353,8 +369,7 @@
   int main() {
     g(3,4);
     return 0;
-  }
-      </pre>
+  }</pre>
     </td>
     <td>
       <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/continuation.png" style="height:80%;">
@@ -392,9 +407,9 @@
             
             <section><h2>Tail Call Elimination の条件</h2>
 <p><ul>
-  <li>caller側とcallee側の戻値の型の一致している。</li>
+  <li>関数を呼び出す側(caller)と呼び出される側(callee)の戻値の型が一致している。</li>
   <li>関数呼び出しがリターン直前に行われている。</li>
-  <li>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</li>
+  <li>呼び出される関数(callee)の引数に用いられるスタックサイズが呼出元(caller)のそれより少ない。</li>
   <li>引数の並びのコピーに上書きがない。</li>
 </ul></p>
 <h2>条件回避の為の実装</h2>
@@ -439,11 +454,11 @@
 <li>この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
 必要があった。</li>
 </ul>
-<h2>実装の修正と修正による利点</h2>
+<h2>実装の修正とその利点</h2>
 <ul>
 <li>しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。</li>
 <li>専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。</li>
-<li>また、コードセグメントへの継続が jmp ではなく call 命令で行われる場合があったが</li>
+<li>また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。</li>
 </ul></section>
             
           </div>
@@ -471,7 +486,7 @@
         <div class="slide">
           <div class="inner">
             
-            <header><h1>性能評価</h1></header>
+            <header><h1>GCC-4.5, GCC-4.6 の性能比較</h1></header>
             
             
             <section><p><li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li>
@@ -538,7 +553,7 @@
 <caption><h3>インライン展開の例</h3></caption>
 <tr>
 <td width=50%>
-<pre>
+<pre style="margin-left:5%">
 void func(){
   A;
   B;
@@ -551,7 +566,7 @@
 </pre>
 </td>
 <td>
-<pre>
+<pre style="margin-left:5%">
 int main() {
   A;
   B;
@@ -682,7 +697,7 @@
             <section><ul>
 <li>今回 CbC-GCC を GCC-4.6 へとアップデートを行った。</li>
 <li>アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。</li>
-<li>また、最適化の強制付与や環境付き継続の部分といった実装の修正も行えた。</li>
+<li>また、最適化の強制付与やといった実装の修正も行えた。</li>
 <li>細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。</li>
 </ul>
 <h2>今後の課題</h2>
@@ -724,10 +739,7 @@
 <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>
+</table></p></section>
             
           </div>
           <div class="presenter_notes">
@@ -1135,7 +1147,7 @@
       
         
         <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>
         
@@ -1184,7 +1196,7 @@
       
       
       <tr id="toc-row-10">
-        <th><a href="#slide10">性能評価</a></th>
+        <th><a href="#slide10">GCC-4.5, GCC-4.6 の性能比較</a></th>
         <td><a href="#slide10">10</a></td>
       </tr>