# HG changeset patch # User Nobuyasu Oshiro # Date 1330466564 -32400 # Node ID 8539cd84106e1b50cc39a3a46ff187bec9532530 # Parent 1d66e06ae2c2642f2ec91aa21665837e9f6e6a43 modify diff -r 1d66e06ae2c2 -r 8539cd84106e paper/graffle/state_conv1_45.graffle --- a/paper/graffle/state_conv1_45.graffle Tue Feb 28 22:47:04 2012 +0900 +++ b/paper/graffle/state_conv1_45.graffle Wed Feb 29 07:02:44 2012 +0900 @@ -157,8 +157,8 @@ 26 Points - {123.7487, 357.61755} - {164.6412, 319.55411} + {123.74873, 357.61752} + {164.64119, 319.55411} Style @@ -189,6 +189,18 @@ Circle Style + fill + + Color + + b + 1 + g + 1 + r + 0 + + shadow Draws @@ -318,6 +330,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -349,6 +373,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -379,6 +415,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -409,6 +457,18 @@ Circle Style + fill + + Color + + b + 1 + g + 1 + r + 0 + + shadow Draws @@ -476,7 +536,7 @@ MasterSheets ModificationDate - 2012-02-27 18:34:20 +0000 + 2012-02-28 14:55:04 +0000 Modifier Nobuyasu Oshiro NotesVisible @@ -557,7 +617,7 @@ Frame - {{435, 4}, {693, 938}} + {{536, 120}, {693, 938}} ListView OutlineWidth diff -r 1d66e06ae2c2 -r 8539cd84106e paper/graffle/state_conv1_46.graffle --- a/paper/graffle/state_conv1_46.graffle Tue Feb 28 22:47:04 2012 +0900 +++ b/paper/graffle/state_conv1_46.graffle Wed Feb 29 07:02:44 2012 +0900 @@ -224,6 +224,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -255,6 +267,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -285,6 +309,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -352,7 +388,7 @@ MasterSheets ModificationDate - 2012-02-27 18:33:52 +0000 + 2012-02-28 14:54:44 +0000 Modifier Nobuyasu Oshiro NotesVisible @@ -433,7 +469,7 @@ Frame - {{633, 100}, {693, 938}} + {{-49, 73}, {693, 938}} ListView OutlineWidth diff -r 1d66e06ae2c2 -r 8539cd84106e paper/graffle/state_conv1_noopt.graffle --- a/paper/graffle/state_conv1_noopt.graffle Tue Feb 28 22:47:04 2012 +0900 +++ b/paper/graffle/state_conv1_noopt.graffle Wed Feb 29 07:02:44 2012 +0900 @@ -124,8 +124,8 @@ 19 Points - {118.70056, 237.57617} - {159.50687, 199.41438} + {118.74377, 237.61328} + {159.62735, 199.53978} Style @@ -190,8 +190,8 @@ 17 Points - {178.49965, 355.5} - {178.49933, 378.5} + {178.49991, 355.5} + {178.49982, 378.5} Style @@ -223,8 +223,8 @@ 16 Points - {178.45464, 281.49997} - {178.4137, 304.50012} + {178.48746, 281.5} + {178.47615, 304.5} Style @@ -315,6 +315,18 @@ Circle Style + fill + + Color + + b + 1 + g + 1 + r + 0 + + shadow Draws @@ -346,8 +358,8 @@ 11 Points - {98.999924, 304.5} - {98.999847, 281.5} + {98.999977, 304.5} + {98.999962, 281.5} Style @@ -379,8 +391,8 @@ 10 Points - {99.088615, 378.50012} - {99.168541, 355.49948} + {99.024498, 378.5} + {99.046593, 355.49997} Style @@ -412,8 +424,8 @@ 8 Points - {178.33638, 207.4995} - {178.18878, 230.5018} + {178.45477, 207.49997} + {178.41397, 230.50012} Style @@ -444,6 +456,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -475,6 +499,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -505,6 +541,18 @@ Circle Style + fill + + Color + + b + 0 + g + 1 + r + 1 + + shadow Draws @@ -535,6 +583,18 @@ Circle Style + fill + + Color + + b + 1 + g + 1 + r + 0 + + shadow Draws @@ -602,7 +662,7 @@ MasterSheets ModificationDate - 2012-02-27 18:31:21 +0000 + 2012-02-28 14:54:59 +0000 Modifier Nobuyasu Oshiro NotesVisible @@ -683,7 +743,7 @@ Frame - {{653, 80}, {693, 938}} + {{1140, 114}, {693, 938}} ListView OutlineWidth diff -r 1d66e06ae2c2 -r 8539cd84106e presen/cbc.md --- a/presen/cbc.md Tue Feb 28 22:47:04 2012 +0900 +++ b/presen/cbc.md Wed Feb 29 07:02:44 2012 +0900 @@ -23,7 +23,7 @@ コードセグメント単位での記述と継続を基本としたプログラミング言語 --------- -
  • コーセグメント:CbC におけるプログラムの基本単位
  • +
  • コーセグメント:CbC におけるプログラムの基本単位
    • C の関数よりも細かな単位
    • 構文は C と同じだが、C から関数コールとループ制御が取り除かれた形
    • @@ -95,34 +95,34 @@ 階乗を求める CbC のプログラム
      -\_\_code print_factorial(int prod)
      +\_\_code print_factorial(int prod)
       {
         printf("factorial = %d\n",prod);
         exit(0);
       }
      -\_\_code factorial0(int prod, int x)
      +\_\_code factorial0(int prod, int x)
       {
         if ( x >= 1) {
      -    goto factorial0(prod\*x, x-1);
      +    goto factorial0(prod\*x, x-1);
         }else{
      -    goto print_factorial(prod);
      +    goto print_factorial(prod);
         }
       }
      -\_\_code factorial(int x)
      +\_\_code factorial(int x)
       {
      -  goto factorial0(1, x);
      +  goto factorial0(1, x);
       }
       int main(int argc, char \*\*argv)
       {
         int i;
         i = atoi(argv[1]);
      -  goto factorial(i);
      +  goto factorial(i);
       }
       
      -
    • __code によるコードセグメントの宣言
    • -
    • 引数付きの goto でコードセグメントを呼び出すことができる
    • +
    • __code によるコードセグメントの宣言
    • +
    • 引数付きの goto でコードセグメントを呼び出すことができる
    • 内部では call ではなく jmp 命令でコードセグメントの処理が遷移している
    • @@ -190,13 +190,13 @@ ======== 末尾除去の条件をチェックする関数 --------- -- 関数が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。 -- その関数を元に、『コードセグメントは末尾除去』にかける専用の関数を用意していた。 +- 関数(コードセグメント)が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。 +- その関数を元に、『コードセグメントを末尾除去にかける』専用の関数を用意していた。 - しかしこの方法は、元になった関数が修正に合わせて専用の関数も修正を行う必要があった。 実装の修正とその利点 --------- -- しかし, 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更。 +- しかし 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更 - 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。 - また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。 @@ -210,8 +210,7 @@ ========
    • 本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。
    • この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。
    • -
    • conv1: 加算と継続を交互に繰り返すプログラム
    • - +
    • conv1: 加算と継続を交互に繰り返すプログラム。指定した回数ループする。
    • @@ -250,8 +249,8 @@ @@ -277,7 +276,7 @@ --- -

      最適化の比較

      +

      最適化の比較(conv1)

      各コンパイラにより生成されたプログラムの速度比較
       void func_b(){
      -  A;
      -  B;
      +  X;
      +  Y;
       }
       
       void func_a() {
      @@ -263,10 +262,10 @@
       
       void func_a() {
      -  A;
      -  B;
      -  A;
      -  B;
      +  X;
      +  Y;
      +  X;
      +  Y;
       }
       
      @@ -333,7 +332,9 @@ CbC ======== -
    • 状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する
    • + +状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する +---------
    • 組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース
    • 現存する記述言語は状態遷移の記述に向いていない
    • スタックが状態を隠蔽するため、分割しにくい、検証が難しい
    • @@ -341,8 +342,9 @@ 具体的な CbC の利用予定 --------- -- モデル検査 - Cerium の実装 +- 状態探索 + --- @@ -369,7 +371,24 @@ --- +引数の並びに上書きコピー +======== +
    • 以下の呼び出しを行うと、スタックの書き換えがおこる
    • +
      +void funcA(int a, int b) {
      +  funcB(b, a);
      +}
      +
      +

      それぞれの最適化にかかった conv1プログラムの挙動(引数 1)

      + + + +
      + +
      + +--- jmp と call @@ -383,27 +402,6 @@ --- -conv1 プログラム -======== -
    • 性能評価で用いた conv1 プログラムの C 版
    • -
      -f0(int i) {
      -    int k,j;
      -    k = 3+i;
      -    j = g0(i+3);
      -    return k+4+j;
      -}
      -g0(int i) {
      -    return h0(i+4)+i;
      -}
      -h0(int i) {
      -    return i+4;
      -}
      -
    • 性能評価はこのプログラムを CbC へと書き換えて行なっている。
    • - ---- - - CbC-GCC のアップデート手法 ======== @@ -455,6 +453,31 @@ --- + +conv1 プログラム +======== +
    • 性能評価で用いた conv1 プログラムの C 版
    • +
      +f0(int i) {
      +    int k,j;
      +    k = 3+i;
      +    j = g0(i+3);
      +    return k+4+j;
      +}
      +g0(int i) {
      +    return h0(i+4)+i;
      +}
      +h0(int i) {
      +    return i+4;
      +}
      +
    • 性能評価はこのプログラムを CbC へと書き換えて行なっている。
    • +
    • 引数 1 のプログラムは上のプログラムをただ CbC へと書き換えたもの
    • +
    • 引数 2 と 3 のプログラムは手動で最適化を行なって CbC へと書き換えたもの
    • + + +--- + + conv1 プログラム ======== - conv1 プログラムでは計算と継続を交互に繰り返し行なう。 @@ -484,11 +507,11 @@ - _CbC_return、 _CbC_environment キーワードを使うことで使える。 - 以下の使い方の場合、戻値 1 を返す。
      -__code c1(__code ret(int,void *),void *env) {
      +\_\_code c1(\_\_code ret(int,void *),void *env) {
           goto ret(1,env);
       }
       int main() {
      -    goto c1(__return, __environment);
      +    goto c1(\_\_return, \_\_environment);
       }
       
      @@ -498,77 +521,6 @@ --- -CbC 引数渡し -======== -
    • CbC では引数渡しにできるだけレジスタを用いるようにしている.
    • - - - - - - - - - - - - - -
      fastcall属性有・無の実行速度
      fastcall無し
      - -
      fastcall有り
      - -
      - - ---- - - - -引数の並びに上書きコピー -======== -
    • 以下の呼び出しを行うと、スタックの書き換えがおこる
    • -
      -void funcA(int a, int b) {
      -  funcB(b, a);
      -}
      -
      - - - - - -
      - -
      - - ---- - -最適化の比較 -======== - - - - - - - - - - - -
      各コンパイラにより生成されたコードの速度比較
      - - - -
      x86/Linuxx86/OS X (10.7)
      - - - ---- - - 最適化の比較 ======== @@ -636,6 +588,28 @@ --- +最適化の比較 +======== + + + + + + + + + + + +
      各コンパイラにより生成されたコードの速度比較
      + + + +
      x86/Linuxx86/OS X (10.7)
      + + + +--- @@ -645,3 +619,6 @@ + + + diff -r 1d66e06ae2c2 -r 8539cd84106e presen/pix/state_conv1_45.png Binary file presen/pix/state_conv1_45.png has changed diff -r 1d66e06ae2c2 -r 8539cd84106e presen/pix/state_conv1_46.png Binary file presen/pix/state_conv1_46.png has changed diff -r 1d66e06ae2c2 -r 8539cd84106e presen/pix/state_conv1_noopt.png Binary file presen/pix/state_conv1_noopt.png has changed diff -r 1d66e06ae2c2 -r 8539cd84106e presen/presentation.html --- a/presen/presentation.html Tue Feb 28 22:47:04 2012 +0900 +++ b/presen/presentation.html Wed Feb 29 07:02:44 2012 +0900 @@ -70,7 +70,7 @@ @@ -109,7 +109,7 @@ @@ -124,7 +124,7 @@

      コードセグメント単位での記述と継続を基本としたプログラミング言語

      -
    • コーセグメント:CbC におけるプログラムの基本単位
    • +
    • コーセグメント:CbC におけるプログラムの基本単位
      • C の関数よりも細かな単位
      • @@ -163,7 +163,7 @@ @@ -222,7 +222,7 @@ @@ -240,34 +240,34 @@ 階乗を求める CbC のプログラム
        -__code print_factorial(int prod)
        +__code print_factorial(int prod)
         {
           printf("factorial = %d\n",prod);
           exit(0);
         }
        -__code factorial0(int prod, int x)
        +__code factorial0(int prod, int x)
         {
           if ( x >= 1) {
        -    goto factorial0(prod*x, x-1);
        +    goto factorial0(prod*x, x-1);
           }else{
        -    goto print_factorial(prod);
        +    goto print_factorial(prod);
           }
         }
        -__code factorial(int x)
        +__code factorial(int x)
         {
        -  goto factorial0(1, x);
        +  goto factorial0(1, x);
         }
         int main(int argc, char **argv)
         {
           int i;
           i = atoi(argv[1]);
        -  goto factorial(i);
        +  goto factorial(i);
         }
         
        -
      • __code によるコードセグメントの宣言
      • -
      • 引数付きの goto でコードセグメントを呼び出すことができる
      • +
      • __code によるコードセグメントの宣言
      • +
      • 引数付きの goto でコードセグメントを呼び出すことができる
      • 内部では call ではなく jmp 命令でコードセグメントの処理が遷移している
      @@ -286,7 +286,7 @@ @@ -326,7 +326,7 @@ @@ -384,7 +384,7 @@ @@ -400,13 +400,13 @@

      末尾除去の条件をチェックする関数

        -
      • 関数が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。
      • -
      • その関数を元に、『コードセグメントは末尾除去』にかける専用の関数を用意していた。
      • +
      • 関数(コードセグメント)が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。
      • +
      • その関数を元に、『コードセグメントを末尾除去にかける』専用の関数を用意していた。
      • しかしこの方法は、元になった関数が修正に合わせて専用の関数も修正を行う必要があった。

      実装の修正とその利点

        -
      • しかし, 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更。
      • +
      • しかし 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更
      • 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。
      • また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。
      @@ -425,7 +425,7 @@ @@ -441,7 +441,7 @@

    • 本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。
    • この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。
    • -
    • conv1: 加算と継続を交互に繰り返すプログラム
    • +
    • conv1: 加算と継続を交互に繰り返すプログラム。指定した回数ループする。
    • @@ -457,12 +457,9 @@
      各コンパイラにより生成されたプログラムの速度比較
      x86/OS X (10.7)
      -
    • Mac の GCC-4.5 では動かなかった 32bit のプログラムが GCC-4.6 では問題なく動いている。
    • -
    • 引数 2、3 は手動で最適化をかけている。
    • - -
    • 引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い
    • +
    • 引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い
    • @@ -478,7 +475,7 @@
      @@ -505,8 +502,8 @@
       void func_b(){
      -  A;
      -  B;
      +  X;
      +  Y;
       }
       
       void func_a() {
      @@ -518,10 +515,10 @@
       
       
       void func_a() {
      -  A;
      -  B;
      -  A;
      -  B;
      +  X;
      +  Y;
      +  X;
      +  Y;
       }
       
      @@ -543,7 +540,7 @@ @@ -554,7 +551,7 @@
      -

      最適化の比較

      +

      最適化の比較(conv1)

      @@ -596,7 +593,7 @@ @@ -630,7 +627,7 @@ @@ -670,7 +667,7 @@ @@ -684,15 +681,15 @@

      CbC

      -

    • 状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する
    • -
    • 組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース
    • +

      状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する

      +

    • 組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース
    • 現存する記述言語は状態遷移の記述に向いていない
    • スタックが状態を隠蔽するため、分割しにくい、検証が難しい
    • 以上の問題を解決する言語として CbC は提案されている。
    • 具体的な CbC の利用予定

        -
      • モデル検査
      • Cerium の実装
      • +
      • 状態探索
      @@ -709,7 +706,7 @@ @@ -752,7 +749,49 @@ + + + + + +
      +
      +
      + +

      引数の並びに上書きコピー

      + + +

    • 以下の呼び出しを行うと、スタックの書き換えがおこる
    • +
      +void funcA(int a, int b) {
      +  funcB(b, a);
      +}
      +

      +
      + + + +
      + +
      + +
      +
      +

      Presenter Notes

      +
      + +
      +
      +
      + + + +
      @@ -787,51 +826,7 @@ - - - - - -
      -
      -
      - -

      conv1 プログラム

      - - -

    • 性能評価で用いた conv1 プログラムの C 版
    • -
      -f0(int i) {
      -    int k,j;
      -    k = 3+i;
      -    j = g0(i+3);
      -    return k+4+j;
      -}
      -g0(int i) {
      -    return h0(i+4)+i;
      -}
      -h0(int i) {
      -    return i+4;
      -}
      -
    • 性能評価はこのプログラムを CbC へと書き換えて行なっている。
    • - -
      -
      -

      Presenter Notes

      -
      - -
      -
      -
      - - - -
      @@ -873,7 +868,7 @@
      @@ -922,7 +917,53 @@ + + + + + +
      +
      +
      + +

      conv1 プログラム

      + + +

    • 性能評価で用いた conv1 プログラムの C 版
    • +
      +f0(int i) {
      +    int k,j;
      +    k = 3+i;
      +    j = g0(i+3);
      +    return k+4+j;
      +}
      +g0(int i) {
      +    return h0(i+4)+i;
      +}
      +h0(int i) {
      +    return i+4;
      +}
      +
    • 性能評価はこのプログラムを CbC へと書き換えて行なっている。
    • +
    • 引数 1 のプログラムは上のプログラムをただ CbC へと書き換えたもの
    • +
    • 引数 2 と 3 のプログラムは手動で最適化を行なって CbC へと書き換えたもの
    • + +
      +
      +

      Presenter Notes

      +
      + +
      +
      +
      + + + +
      @@ -973,7 +1014,7 @@
      @@ -993,11 +1034,11 @@
    • 以下の使い方の場合、戻値 1 を返す。

      -code c1(code ret(int,void ),void env) {
      +__code c1(__code ret(int,void ),void env) {
           goto ret(1,env);
       }
       int main() {
      -    goto c1(return, environment);
      +    goto c1(__return, __environment);
       }
       

    • @@ -1020,141 +1061,7 @@ - - - - - -
      -
      -
      - -

      CbC 引数渡し

      - - -

    • CbC では引数渡しにできるだけレジスタを用いるようにしている.
    • - - - - - - - - - - - - - -
      fastcall属性有・無の実行速度
      fastcall無し
      - -
      fastcall有り
      - -

      - -
      -
      -

      Presenter Notes

      -
      - -
      -
      -
      - - - - -
      -
      -
      - - -
      -
      -
      - -

      引数の並びに上書きコピー

      - - -

    • 以下の呼び出しを行うと、スタックの書き換えがおこる
    • -
      -void funcA(int a, int b) {
      -  funcB(b, a);
      -}
      -

      - - - - -
      - -
      - -
      -
      -

      Presenter Notes

      -
      - -
      -
      -
      - - - - -
      -
      -
      - - -
      -
      -
      - -

      最適化の比較

      - - -
      - - - - - - - - - -
      各コンパイラにより生成されたコードの速度比較
      - - - -
      x86/Linuxx86/OS X (10.7)
      - -
      -
      -

      Presenter Notes

      -
      - -
      -
      -
      - - - -
      @@ -1228,7 +1135,26 @@
    • 保存していた関数ポインタへの継続はインライン展開は行われない
    • --> ---- +--- + +最適化の比較 +======== + + + + + + + + + + + +
      各コンパイラにより生成されたコードの速度比較
      + + + +
      x86/Linuxx86/OS X (10.7)
      @@ -1244,7 +1170,29 @@ + +
      + + + +