Mercurial > hg > Papers > 2012 > nobu-thesis
changeset 35:01238ec569ea draft
commit
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 28 Feb 2012 03:55:29 +0900 |
parents | 3922a95e99a8 |
children | 975da5d0699e |
files | paper/graffle/state_conv1_45.graffle paper/graffle/state_conv1_46.graffle paper/graffle/state_conv1_noopt.graffle presen/cbc.md presen/pix/state_conv1_45.png presen/pix/state_conv1_46.png presen/pix/state_conv1_noopt.png presen/presentation.html |
diffstat | 8 files changed, 626 insertions(+), 275 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/graffle/state_conv1_45.graffle Mon Feb 27 18:34:32 2012 +0900 +++ b/paper/graffle/state_conv1_45.graffle Tue Feb 28 03:55:29 2012 +0900 @@ -44,7 +44,7 @@ <key>Creator</key> <string>Nobuyasu Oshiro</string> <key>DisplayScale</key> - <string>1 0/72 in = 1 0/72 in</string> + <string>1 0/72 in = 1.0000 in</string> <key>GraphDocumentVersion</key> <integer>8</integer> <key>GraphicsList</key> @@ -55,16 +55,14 @@ <key>Head</key> <dict> <key>ID</key> - <integer>4</integer> + <integer>14</integer> </dict> <key>ID</key> - <integer>12</integer> + <integer>29</integer> <key>Points</key> <array> - <string>{386.60852, 202.42825}</string> - <string>{349, 179}</string> - <string>{145, 178}</string> - <string>{112.36989, 201.78642}</string> + <string>{171.37816, 398.56644}</string> + <string>{116.12184, 501.43356}</string> </array> <key>Style</key> <dict> @@ -81,7 +79,7 @@ <key>Tail</key> <dict> <key>ID</key> - <integer>7</integer> + <integer>20</integer> </dict> </dict> <dict> @@ -90,14 +88,77 @@ <key>Head</key> <dict> <key>ID</key> - <integer>7</integer> + <integer>13</integer> </dict> <key>ID</key> - <integer>11</integer> + <integer>28</integer> <key>Points</key> <array> - <string>{354.5, 217.00012}</string> - <string>{381.49997, 217.00026}</string> + <string>{130.00002, 302}</string> + <string>{157.49998, 302}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>27</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{78.5, 277}, {51, 50}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>27</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\b\fs24 \cf0 main}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>13</integer> + </dict> + <key>ID</key> + <integer>26</integer> + <key>Points</key> + <array> + <string>{123.7487, 357.61755}</string> + <string>{164.6412, 319.55411}</string> </array> <key>Style</key> <dict> @@ -114,7 +175,37 @@ <key>Tail</key> <dict> <key>ID</key> - <integer>6</integer> + <integer>16</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{158, 351}, {51, 50}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>20</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\b\fs24 \cf0 f_g0}</string> + <key>VerticalPad</key> + <integer>0</integer> </dict> </dict> <dict> @@ -123,14 +214,14 @@ <key>Head</key> <dict> <key>ID</key> - <integer>6</integer> + <integer>16</integer> </dict> <key>ID</key> - <integer>10</integer> + <integer>19</integer> <key>Points</key> <array> - <string>{275.5, 217}</string> - <string>{302.5, 217}</string> + <string>{104.00001, 424.5}</string> + <string>{104.00001, 401.5}</string> </array> <key>Style</key> <dict> @@ -147,7 +238,7 @@ <key>Tail</key> <dict> <key>ID</key> - <integer>5</integer> + <integer>15</integer> </dict> </dict> <dict> @@ -156,14 +247,14 @@ <key>Head</key> <dict> <key>ID</key> - <integer>5</integer> + <integer>15</integer> </dict> <key>ID</key> - <integer>9</integer> + <integer>18</integer> <key>Points</key> <array> - <string>{196.50002, 217}</string> - <string>{223.49998, 217.00002}</string> + <string>{104.00001, 498.5}</string> + <string>{104.00001, 475.5}</string> </array> <key>Style</key> <dict> @@ -180,7 +271,7 @@ <key>Tail</key> <dict> <key>ID</key> - <integer>3</integer> + <integer>14</integer> </dict> </dict> <dict> @@ -189,14 +280,14 @@ <key>Head</key> <dict> <key>ID</key> - <integer>3</integer> + <integer>20</integer> </dict> <key>ID</key> - <integer>8</integer> + <integer>17</integer> <key>Points</key> <array> - <string>{117.50002, 217}</string> - <string>{144.49998, 217}</string> + <string>{183.50002, 327.5}</string> + <string>{183.50002, 350.5}</string> </array> <key>Style</key> <dict> @@ -213,16 +304,16 @@ <key>Tail</key> <dict> <key>ID</key> - <integer>4</integer> + <integer>13</integer> </dict> </dict> <dict> <key>Bounds</key> - <string>{{382, 192}, {56, 50}}</string> + <string>{{76, 351}, {56, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> - <integer>7</integer> + <integer>16</integer> <key>Shape</key> <string>Circle</string> <key>Style</key> @@ -249,11 +340,11 @@ </dict> <dict> <key>Bounds</key> - <string>{{303, 192}, {51, 50}}</string> + <string>{{78.5, 425}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> - <integer>6</integer> + <integer>15</integer> <key>Shape</key> <string>Circle</string> <key>Style</key> @@ -279,11 +370,11 @@ </dict> <dict> <key>Bounds</key> - <string>{{224, 192}, {51, 50}}</string> + <string>{{78.5, 499}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> - <integer>5</integer> + <integer>14</integer> <key>Shape</key> <string>Circle</string> <key>Style</key> @@ -309,11 +400,11 @@ </dict> <dict> <key>Bounds</key> - <string>{{66, 192}, {51, 50}}</string> + <string>{{158, 277}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> - <integer>4</integer> + <integer>13</integer> <key>Shape</key> <string>Circle</string> <key>Style</key> @@ -337,36 +428,6 @@ <integer>0</integer> </dict> </dict> - <dict> - <key>Bounds</key> - <string>{{145, 192}, {51, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>3</integer> - <key>Shape</key> - <string>Circle</string> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\b\fs24 \cf0 f_g0}</string> - <key>VerticalPad</key> - <integer>0</integer> - </dict> - </dict> </array> <key>GridInfo</key> <dict/> @@ -415,7 +476,7 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2012-02-26 09:55:05 +0000</string> + <string>2012-02-27 18:34:20 +0000</string> <key>Modifier</key> <string>Nobuyasu Oshiro</string> <key>NotesVisible</key> @@ -496,7 +557,7 @@ </dict> </array> <key>Frame</key> - <string>{{435, -12}, {693, 938}}</string> + <string>{{435, 4}, {693, 938}}</string> <key>ListView</key> <true/> <key>OutlineWidth</key>
--- a/paper/graffle/state_conv1_46.graffle Mon Feb 27 18:34:32 2012 +0900 +++ b/paper/graffle/state_conv1_46.graffle Tue Feb 28 03:55:29 2012 +0900 @@ -44,7 +44,7 @@ <key>Creator</key> <string>Nobuyasu Oshiro</string> <key>DisplayScale</key> - <string>1 0/72 in = 1 0/72 in</string> + <string>1 0/72 in = 1.0000 in</string> <key>GraphDocumentVersion</key> <integer>8</integer> <key>GraphicsList</key> @@ -55,25 +55,24 @@ <key>Head</key> <dict> <key>ID</key> - <integer>13</integer> + <integer>5</integer> </dict> <key>ID</key> - <integer>18</integer> + <integer>33</integer> <key>Points</key> <array> - <string>{313.60419, 261.15652}</string> - <string>{288, 241}</string> - <string>{217, 242}</string> - <string>{194.17786, 261.3317}</string> + <string>{147.36324, 244.32285}</string> + <string>{108, 298}</string> + <string>{147.54645, 350.48892}</string> </array> <key>Style</key> <dict> <key>stroke</key> <dict> + <key>CornerRadius</key> + <real>50</real> <key>HeadArrow</key> <string>FilledArrow</string> - <key>LineType</key> - <integer>1</integer> <key>TailArrow</key> <string>0</string> </dict> @@ -90,14 +89,78 @@ <key>Head</key> <dict> <key>ID</key> + <integer>5</integer> + </dict> + <key>ID</key> + <integer>29</integer> + <key>Points</key> + <array> + <string>{177.27339, 170.31975}</string> + <string>{242, 267}</string> + <string>{178.53525, 350.54852}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>CornerRadius</key> + <real>100</real> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{137.5, 124}, {51, 50}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>20</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\b\fs24 \cf0 main}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> <integer>7</integer> </dict> <key>ID</key> <integer>11</integer> <key>Points</key> <array> - <string>{279.5, 278}</string> - <string>{306.49997, 278}</string> + <string>{163.00002, 271.5}</string> + <string>{163.00002, 248.5}</string> </array> <key>Style</key> <dict> @@ -126,11 +189,11 @@ <integer>6</integer> </dict> <key>ID</key> - <integer>14</integer> + <integer>10</integer> <key>Points</key> <array> - <string>{200.50002, 278}</string> - <string>{227.49998, 278}</string> + <string>{163.00002, 345.5}</string> + <string>{163.00002, 322.5}</string> </array> <key>Style</key> <dict> @@ -147,12 +210,12 @@ <key>Tail</key> <dict> <key>ID</key> - <integer>13</integer> + <integer>5</integer> </dict> </dict> <dict> <key>Bounds</key> - <string>{{307, 253}, {56, 50}}</string> + <string>{{135, 198}, {56, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -183,7 +246,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{228, 253}, {51, 50}}</string> + <string>{{137.5, 272}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -213,11 +276,11 @@ </dict> <dict> <key>Bounds</key> - <string>{{149, 253}, {51, 50}}</string> + <string>{{137.5, 346}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> - <integer>13</integer> + <integer>5</integer> <key>Shape</key> <string>Circle</string> <key>Style</key> @@ -289,7 +352,7 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2012-02-26 09:56:14 +0000</string> + <string>2012-02-27 18:33:52 +0000</string> <key>Modifier</key> <string>Nobuyasu Oshiro</string> <key>NotesVisible</key>
--- a/paper/graffle/state_conv1_noopt.graffle Mon Feb 27 18:34:32 2012 +0900 +++ b/paper/graffle/state_conv1_noopt.graffle Tue Feb 28 03:55:29 2012 +0900 @@ -58,11 +58,74 @@ <integer>4</integer> </dict> <key>ID</key> + <integer>21</integer> + <key>Points</key> + <array> + <string>{125.00002, 182}</string> + <string>{152.49998, 182}</string> + </array> + <key>Style</key> + <dict> + <key>stroke</key> + <dict> + <key>HeadArrow</key> + <string>FilledArrow</string> + <key>LineType</key> + <integer>1</integer> + <key>TailArrow</key> + <string>0</string> + </dict> + </dict> + <key>Tail</key> + <dict> + <key>ID</key> + <integer>20</integer> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{73.5, 157}, {51, 50}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>ID</key> + <integer>20</integer> + <key>Shape</key> + <string>Circle</string> + <key>Style</key> + <dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg1252\cocoartf1138\cocoasubrtf230 +{\fonttbl\f0\fswiss\fcharset0 Helvetica;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\b\fs24 \cf0 main}</string> + <key>VerticalPad</key> + <integer>0</integer> + </dict> + </dict> + <dict> + <key>Class</key> + <string>LineGraphic</string> + <key>Head</key> + <dict> + <key>ID</key> + <integer>4</integer> + </dict> + <key>ID</key> <integer>19</integer> <key>Points</key> <array> - <string>{112.4254, 198.11032}</string> - <string>{103.82727, 182.45906}</string> + <string>{118.70056, 237.57617}</string> + <string>{159.50687, 199.41438}</string> </array> <key>Style</key> <dict> @@ -94,8 +157,8 @@ <integer>18</integer> <key>Points</key> <array> - <string>{309.3009, 181.97667}</string> - <string>{298.96802, 199.18106}</string> + <string>{152.49998, 404}</string> + <string>{125.00002, 404}</string> </array> <key>Style</key> <dict> @@ -127,8 +190,8 @@ <integer>17</integer> <key>Points</key> <array> - <string>{271.5, 160}</string> - <string>{296.5, 160}</string> + <string>{178.49965, 355.5}</string> + <string>{178.49933, 378.5}</string> </array> <key>Style</key> <dict> @@ -160,8 +223,8 @@ <integer>16</integer> <key>Points</key> <array> - <string>{194.50002, 160}</string> - <string>{219.49998, 160}</string> + <string>{178.45464, 281.49997}</string> + <string>{178.4137, 304.50012}</string> </array> <key>Style</key> <dict> @@ -183,7 +246,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{297, 135}, {51, 50}}</string> + <string>{{153, 379}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -213,7 +276,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{220, 135}, {51, 50}}</string> + <string>{{153, 305}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -243,7 +306,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{143, 135}, {51, 50}}</string> + <string>{{153, 231}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -283,8 +346,8 @@ <integer>11</integer> <key>Points</key> <array> - <string>{180.49998, 221}</string> - <string>{153.50002, 221}</string> + <string>{98.999924, 304.5}</string> + <string>{98.999847, 281.5}</string> </array> <key>Style</key> <dict> @@ -316,8 +379,8 @@ <integer>10</integer> <key>Points</key> <array> - <string>{259.5, 221}</string> - <string>{232.50002, 221}</string> + <string>{99.088615, 378.50012}</string> + <string>{99.168541, 355.49948}</string> </array> <key>Style</key> <dict> @@ -349,8 +412,8 @@ <integer>8</integer> <key>Points</key> <array> - <string>{117.50002, 160}</string> - <string>{142.49998, 160}</string> + <string>{178.33638, 207.4995}</string> + <string>{178.18878, 230.5018}</string> </array> <key>Style</key> <dict> @@ -372,7 +435,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{97, 196}, {56, 50}}</string> + <string>{{71, 231}, {56, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -403,7 +466,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{181, 196}, {51, 50}}</string> + <string>{{73.5, 305}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -433,7 +496,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{260, 196}, {51, 50}}</string> + <string>{{73.5, 379}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -463,7 +526,7 @@ </dict> <dict> <key>Bounds</key> - <string>{{66, 135}, {51, 50}}</string> + <string>{{153, 157}, {51, 50}}</string> <key>Class</key> <string>ShapedGraphic</string> <key>ID</key> @@ -539,7 +602,7 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2012-02-27 05:28:25 +0000</string> + <string>2012-02-27 18:31:21 +0000</string> <key>Modifier</key> <string>Nobuyasu Oshiro</string> <key>NotesVisible</key>
--- a/presen/cbc.md Mon Feb 27 18:34:32 2012 +0900 +++ b/presen/cbc.md Tue Feb 28 03:55:29 2012 +0900 @@ -25,7 +25,7 @@ <li>コーセグメント:CbC におけるプログラムの基本単位</li> <ul> <li>C の関数よりも細かな単位</li> -<li>C から関数コールとループ制御が取り除かれた形</li> +<li>構文は C と同じだが、C から関数コールとループ制御が取り除かれた形</li> <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li> </ul> @@ -118,7 +118,24 @@ --- -CbC の実装 : Tail Call Elimination +Gnu Compiler Collection (GCC) +======== +<li>GCC: オープンソースのコンパイル群</li> +<li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li> +<li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li> +<table width=100%> + <caption>GCC のアセンブラ言語出力までの流れ</caption> + <td style="margin:auto; text-align:center;"> + <img src="./pix/ir.png" style="height:15em"> + </td> +</table> +<li>ソースコードはアセンブラに変換される間に 4 つのデータ構造に変換される。</li> +<li>この中でも CbC の実装では Parser と RTL の生成部分に手が加えられている。</li> + +--- + + +CbC の実装 : 軽量継続 ======== <li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li> @@ -188,29 +205,41 @@ - 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。 - この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく 必要があった。 + +実装の修正と修正による利点 +--------- - しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。 -- 専用関数がなくなったことで今後より楽なアップデートを行なっていくことができるようになった。 +- 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。 +- また、コードセグメントへの継続が jmp ではなく call 命令で行われる場合があったが --- + 性能評価 ======== - -<li>conv1: 演算と継続を交互に繰り返すプログラム</li> +<li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li> +<li>この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。</li> +<li>conv1: 加算と継続を交互に繰り返すプログラム</li> -<table width=100%> - <caption>各コンパイラにより生成されたコードの速度比較</caption> +<table width=100% border=1> + <caption>各コンパイラにより生成されたプログラムの速度比較</caption> + <tr> <td style="margin:auto; text-align:center;"> <img src="./pix/conv1_for_resume.png" style="height:15em"> </td> <td> <img src="./pix/conv1_mac_for_presen.png" style="height:15em"> </td> + </tr> + <tr> + <td style="text-align:center;">x86/Linux</td> + <td style="text-align:center;">x86/OS X (10.7)</td> + </tr> </table> -<li>GCC-4.5 では動かなかったプログラムが GCC-4.6 では問題なく動いている。</li> +<li>Mac の GCC-4.5 では動かなかった 32bit のプログラムが GCC-4.6 では問題なく動いている。</li> <li>引数 2、3 の結果はほぼ同じ</li> <li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li> @@ -218,51 +247,79 @@ --- -最適化の比較 + +GCC-4.6 の最適化 ======== +- GCC-4.6 では最適化の 1つ『インライン展開』が強化されている。 + +インライン展開 +--------- +- 関数の処理をそのまま関数呼び出し部に展開することで call を省略できる最適化 + <table width=100% border=1> - <caption>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</caption> +<caption><h3>インライン展開の例</h3></caption> +<tr> +<td width=50%> +<pre> +void func(){ + A; + B; +} + +int main() { + func(); + func(); +} +</pre> +</td> +<td> +<pre> +int main() { + A; + B; + A; + B; +} +</pre> +</td> +</tr> +</table> +<li>func の呼び出しがなくなっている。</li> + + +--- + +<h1>最適化の比較</h1> +<table width=100% border=1> + <caption><h3>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</h3></caption> <tr> - <td>最適化</td> - <td style="text-align:center;">状態遷移</td> + <td width=30%>最適化なし</td> + <td width=30%>GCC-4.5の最適化(-O2)</td> + <td width=30%>GCC-4.6の最適化(-O2)</td> </tr> <tr> - <td>最適化無し</td> <td style="margin:auto; text-align:center;"> - <img src="./pix/state_conv1_noopt.png"> - </td> - <tr> - <td>GCC-4.5<br>の最適化<br>(-O2)</td> + <img src="./pix/state_conv1_noopt.png" style="width:65%;"> + </td> <td style="margin:auto; text-align:center;"> - <img src="./pix/state_conv1_45.png"> - </td> - </tr> - <tr> - <td>GCC-4.6<br>の最適化<br>(-O2)</td> + <img src="./pix/state_conv1_45.png" style="width:65%;"> + </td> <td style="margin:auto; text-align:center;"> - <img src="./pix/state_conv1_46.png"> + <img src="./pix/state_conv1_46.png" style="width:65%;"> </td> </tr> </table> ---- - - -GCC の最適化 -======== -- 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</l> -- これは、最適化の 1 つ『インライン展開』により各コードセグメントの計算がまとめて行われ、 -継続する数を減らされている為。 -- GCC-4.5 でもインライン展開はされていたが、GCC-4.6 はより良い最適化がかけられている。 +- 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。 +- GCC-4.5 でもインライン展開はされているが、GCC-4.6 はより良い最適化がかけられている。 --- - +最新版のアップデートに合わせる有用性 +======== -アップデートに合わせる有用性 -======== -- 今回の『インライン展開』のように GCC の最適化は日々改良されていく。 +- 今回の『インライン展開』のように GCC の最適化は日々改良されている。 - また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。 - それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。 @@ -275,9 +332,9 @@ まとめ ======== - 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。 -- アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った。 -- アップデートにかけたことで, より良い最適化がかかることを確認できた。 -- GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる。 +- アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。 +- また、最適化の強制付与や環境付き継続の部分といった実装の修正も行えた。 +- 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。 今後の課題 @@ -397,19 +454,6 @@ --- -GCC でのコンパイルの仕組み -======== - -<table width=100%> - <td style="margin:auto; text-align:center;"> - <img src="./pix/ir.png" style="height:15em"> - </td> -</table> - -<li>CbC の実装では Parser と RTL の生成部分に手が加えられている。</li> - ---- - 引数の並びに上書きコピー ======== @@ -435,6 +479,31 @@ ======== <table width=100% border=1> + <caption>各コンパイラにより生成されたコードの速度比較</caption> + <tr> + <td style="margin:auto; text-align:center;"> + <img src="./pix/O3_conv1_linux.png" style="height:15em"> + </td> + <td> + <img src="./pix/O3_conv1_mac.png" style="height:15em"> + </td> + </tr> + <tr> + <td style="text-align:center;">x86/Linux</td> + <td style="text-align:center;">x86/OS X (10.7)</td> + </tr> +</table> + + + +--- + + + +最適化の比較 +======== + +<table width=100% border=1> <caption>それぞれの最適化により吐かれたアセンブラコード</caption> <tr> <td width=50% style="text-align:center;">CbC-GCC-4.5</td>
--- a/presen/presentation.html Mon Feb 27 18:34:32 2012 +0900 +++ b/presen/presentation.html Tue Feb 28 03:55:29 2012 +0900 @@ -74,7 +74,7 @@ </aside> <aside class="page_number"> - 1/21 + 1/22 </aside> </footer> </div> @@ -111,7 +111,7 @@ </aside> <aside class="page_number"> - 2/21 + 2/22 </aside> </footer> </div> @@ -130,7 +130,7 @@ <ul> <li>C の関数よりも細かな単位</li> -<li>C から関数コールとループ制御が取り除かれた形</li> +<li>構文は C と同じだが、C から関数コールとループ制御が取り除かれた形</li> <li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li> </ul> @@ -154,7 +154,7 @@ </aside> <aside class="page_number"> - 3/21 + 3/22 </aside> </footer> </div> @@ -213,7 +213,7 @@ </aside> <aside class="page_number"> - 4/21 + 4/22 </aside> </footer> </div> @@ -277,7 +277,7 @@ </aside> <aside class="page_number"> - 5/21 + 5/22 </aside> </footer> </div> @@ -288,7 +288,47 @@ <div class="slide"> <div class="inner"> - <header><h1>CbC の実装 : Tail Call Elimination</h1></header> + <header><h1>Gnu Compiler Collection (GCC)</h1></header> + + + <section><p><li>GCC: オープンソースのコンパイル群</li> +<li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li> +<li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li> +<table width=100%> + <caption>GCC のアセンブラ言語出力までの流れ</caption> + <td style="margin:auto; text-align:center;"> + <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/ir.png" style="height:15em"> + </td> +</table> +<li>ソースコードはアセンブラに変換される間に 4 つのデータ構造に変換される。</li> +<li>この中でも CbC の実装では Parser と RTL の生成部分に手が加えられている。</li></p></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"> + 6/22 + </aside> + </footer> + </div> + </div> + + <!-- slide source: ./cbc.md --> + <div class="slide-wrapper"> + <div class="slide"> + <div class="inner"> + + <header><h1>CbC の実装 : 軽量継続</h1></header> <section><p><li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li></p> @@ -336,7 +376,7 @@ </aside> <aside class="page_number"> - 6/21 + 7/22 </aside> </footer> </div> @@ -379,7 +419,7 @@ </aside> <aside class="page_number"> - 7/21 + 8/22 </aside> </footer> </div> @@ -398,8 +438,12 @@ <li>今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。</li> <li>この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく 必要があった。</li> +</ul> +<h2>実装の修正と修正による利点</h2> +<ul> <li>しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。</li> -<li>専用関数がなくなったことで今後より楽なアップデートを行なっていくことができるようになった。</li> +<li>専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。</li> +<li>また、コードセグメントへの継続が jmp ではなく call 命令で行われる場合があったが</li> </ul></section> </div> @@ -416,7 +460,7 @@ </aside> <aside class="page_number"> - 8/21 + 9/22 </aside> </footer> </div> @@ -430,19 +474,26 @@ <header><h1>性能評価</h1></header> - <section><li>conv1: 演算と継続を交互に繰り返すプログラム</li> - -<table width=100%> - <caption>各コンパイラにより生成されたコードの速度比較</caption> + <section><p><li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li> +<li>この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。</li> +<li>conv1: 加算と継続を交互に繰り返すプログラム</li></p> +<table width=100% border=1> + <caption>各コンパイラにより生成されたプログラムの速度比較</caption> + <tr> <td style="margin:auto; text-align:center;"> <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/conv1_for_resume.png" style="height:15em"> </td> <td> <img src="./pix/conv1_mac_for_presen.png" style="height:15em"> </td> + </tr> + <tr> + <td style="text-align:center;">x86/Linux</td> + <td style="text-align:center;">x86/OS X (10.7)</td> + </tr> </table> -<li>GCC-4.5 では動かなかったプログラムが GCC-4.6 では問題なく動いている。</li> +<li>Mac の GCC-4.5 では動かなかった 32bit のプログラムが GCC-4.6 では問題なく動いている。</li> <li>引数 2、3 の結果はほぼ同じ</li> @@ -462,7 +513,7 @@ </aside> <aside class="page_number"> - 9/21 + 10/22 </aside> </footer> </div> @@ -473,33 +524,45 @@ <div class="slide"> <div class="inner"> - <header><h1>最適化の比較</h1></header> + <header><h1>GCC-4.6 の最適化</h1></header> - <section><p><table width=100% border=1> - <caption>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</caption> - <tr> - <td>最適化</td> - <td style="text-align:center;">状態遷移</td> - </tr> - <tr> - <td>最適化無し</td> - <td style="margin:auto; text-align:center;"> - <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/state_conv1_noopt.png"> - </td> - <tr> - <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>の最適化<br>(-O2)</td> - <td style="margin:auto; text-align:center;"> - <img src="./pix/state_conv1_46.png"> - </td> - </tr> -</table></p></section> + <section><ul> +<li>GCC-4.6 では最適化の 1つ『インライン展開』が強化されている。</li> +</ul> +<h2>インライン展開</h2> +<ul> +<li>関数の処理をそのまま関数呼び出し部に展開することで call を省略できる最適化</li> +</ul> +<table width=100% border=1> +<caption><h3>インライン展開の例</h3></caption> +<tr> +<td width=50%> +<pre> +void func(){ + A; + B; +} + +int main() { + func(); + func(); +} +</pre> +</td> +<td> +<pre> +int main() { + A; + B; + A; + B; +} +</pre> +</td> +</tr> +</table> +<li>func の呼び出しがなくなっている。</li></section> </div> <div class="presenter_notes"> @@ -515,7 +578,7 @@ </aside> <aside class="page_number"> - 10/21 + 11/22 </aside> </footer> </div> @@ -526,14 +589,32 @@ <div class="slide"> <div class="inner"> - <header><h1>GCC の最適化</h1></header> + <header><h1>最適化の比較</h1></header> - <section><ul> -<li>最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</l></li> -<li>これは、最適化の 1 つ『インライン展開』により各コードセグメントの計算がまとめて行われ、 -継続する数を減らされている為。</li> -<li>GCC-4.5 でもインライン展開はされていたが、GCC-4.6 はより良い最適化がかけられている。</li> + <section><table width=100% border=1> + <caption><h3>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</h3></caption> + <tr> + <td width=30%>最適化なし</td> + <td width=30%>GCC-4.5の最適化(-O2)</td> + <td width=30%>GCC-4.6の最適化(-O2)</td> + </tr> + <tr> + <td style="margin:auto; text-align:center;"> + <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/state_conv1_noopt.png" style="width:65%;"> + </td> + <td style="margin:auto; text-align:center;"> + <img src="./pix/state_conv1_45.png" style="width:65%;"> + </td> + <td style="margin:auto; text-align:center;"> + <img src="./pix/state_conv1_46.png" style="width:65%;"> + </td> + </tr> +</table> + +<ul> +<li>最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</li> +<li>GCC-4.5 でもインライン展開はされているが、GCC-4.6 はより良い最適化がかけられている。</li> </ul></section> </div> @@ -550,7 +631,7 @@ </aside> <aside class="page_number"> - 11/21 + 12/22 </aside> </footer> </div> @@ -561,11 +642,11 @@ <div class="slide"> <div class="inner"> - <header><h1>アップデートに合わせる有用性</h1></header> + <header><h1>最新版のアップデートに合わせる有用性</h1></header> <section><ul> -<li>今回の『インライン展開』のように GCC の最適化は日々改良されていく。</li> +<li>今回の『インライン展開』のように GCC の最適化は日々改良されている。</li> <li>また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。</li> <li>それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。</li> </ul></section> @@ -584,7 +665,7 @@ </aside> <aside class="page_number"> - 12/21 + 13/22 </aside> </footer> </div> @@ -600,9 +681,9 @@ <section><ul> <li>今回 CbC-GCC を GCC-4.6 へとアップデートを行った。</li> -<li>アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った。</li> -<li>アップデートにかけたことで, より良い最適化がかかることを確認できた。</li> -<li>GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる。</li> +<li>アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。</li> +<li>また、最適化の強制付与や環境付き継続の部分といった実装の修正も行えた。</li> +<li>細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。</li> </ul> <h2>今後の課題</h2> <ul> @@ -624,7 +705,7 @@ </aside> <aside class="page_number"> - 13/21 + 14/22 </aside> </footer> </div> @@ -662,7 +743,7 @@ </aside> <aside class="page_number"> - 14/21 + 15/22 </aside> </footer> </div> @@ -711,7 +792,7 @@ </aside> <aside class="page_number"> - 15/21 + 16/22 </aside> </footer> </div> @@ -762,7 +843,7 @@ </aside> <aside class="page_number"> - 16/21 + 17/22 </aside> </footer> </div> @@ -809,7 +890,7 @@ </aside> <aside class="page_number"> - 17/21 + 18/22 </aside> </footer> </div> @@ -857,43 +938,7 @@ </aside> <aside class="page_number"> - 18/21 - </aside> - </footer> - </div> - </div> - - <!-- slide source: ./cbc.md --> - <div class="slide-wrapper"> - <div class="slide"> - <div class="inner"> - - <header><h1>GCC でのコンパイルの仕組み</h1></header> - - - <section><table width=100%> - <td style="margin:auto; text-align:center;"> - <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/ir.png" style="height:15em"> - </td> -</table> - -<li>CbC の実装では Parser と RTL の生成部分に手が加えられている。</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"> - 19/21 + 19/22 </aside> </footer> </div> @@ -935,7 +980,51 @@ </aside> <aside class="page_number"> - 20/21 + 20/22 + </aside> + </footer> + </div> + </div> + + <!-- slide source: ./cbc.md --> + <div class="slide-wrapper"> + <div class="slide"> + <div class="inner"> + + <header><h1>最適化の比較</h1></header> + + + <section><table width=100% border=1> + <caption>各コンパイラにより生成されたコードの速度比較</caption> + <tr> + <td style="margin:auto; text-align:center;"> + <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/O3_conv1_linux.png" style="height:15em"> + </td> + <td> + <img src="./pix/O3_conv1_mac.png" style="height:15em"> + </td> + </tr> + <tr> + <td style="text-align:center;">x86/Linux</td> + <td style="text-align:center;">x86/OS X (10.7)</td> + </tr> +</table></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"> + 21/22 </aside> </footer> </div> @@ -1025,7 +1114,7 @@ </aside> <aside class="page_number"> - 21/21 + 22/22 </aside> </footer> </div> @@ -1071,13 +1160,13 @@ <tr id="toc-row-6"> - <th><a href="#slide6">CbC の実装 : Tail Call Elimination</a></th> + <th><a href="#slide6">Gnu Compiler Collection (GCC)</a></th> <td><a href="#slide6">6</a></td> </tr> <tr id="toc-row-7"> - <th><a href="#slide7">CbC の実装: Tail Call Elimination</a></th> + <th><a href="#slide7">CbC の実装 : 軽量継続</a></th> <td><a href="#slide7">7</a></td> </tr> @@ -1089,67 +1178,67 @@ <tr id="toc-row-9"> - <th><a href="#slide9">性能評価</a></th> + <th><a href="#slide9">CbC の実装: Tail Call Elimination</a></th> <td><a href="#slide9">9</a></td> </tr> <tr id="toc-row-10"> - <th><a href="#slide10">最適化の比較</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">GCC の最適化</a></th> + <th><a href="#slide11">GCC-4.6 の最適化</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">まとめ</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">jmp と call</a></th> + <th><a href="#slide14">まとめ</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">jmp と call</a></th> <td><a href="#slide15">15</a></td> </tr> <tr id="toc-row-16"> - <th><a href="#slide16">conv1 プログラム</a></th> + <th><a href="#slide16">構文の追加</a></th> <td><a href="#slide16">16</a></td> </tr> <tr id="toc-row-17"> - <th><a href="#slide17">CbC の実装: 環境付き継続</a></th> + <th><a href="#slide17">conv1 プログラム</a></th> <td><a href="#slide17">17</a></td> </tr> <tr id="toc-row-18"> - <th><a href="#slide18">CbC 引数渡し</a></th> + <th><a href="#slide18">CbC の実装: 環境付き継続</a></th> <td><a href="#slide18">18</a></td> </tr> <tr id="toc-row-19"> - <th><a href="#slide19">GCC でのコンパイルの仕組み</a></th> + <th><a href="#slide19">CbC 引数渡し</a></th> <td><a href="#slide19">19</a></td> </tr> @@ -1166,6 +1255,12 @@ </tr> + <tr id="toc-row-22"> + <th><a href="#slide22">最適化の比較</a></th> + <td><a href="#slide22">22</a></td> + </tr> + + </table> </div>