Mercurial > hg > Papers > 2015 > kkb-sigos

annotate presen/index.html @ 17:dfd4f1eb8882

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Mon, 25 May 2015 16:22:34 +0900
parents ff895b2c6792
children 9159562b324c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 <!DOCTYPE HTML>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 <html lang="en-US">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 <head>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 <title>Monad に基づくメタ計算を基本とする Gears OS の設計</title>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 <meta charset="UTF-8">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 <meta name="viewport" content="width=1274, user-scalable=no">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 <meta name="generator" content="Slide Show (S9)">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 <meta name="author" content="小久保翔平">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 <link rel="stylesheet" href="themes/ribbon/styles/style.css">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 </head>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 <body class="list">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 <header class="caption">
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 <h1>Monad に基づくメタ計算を基本とする Gears OS の設計</h1>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 <p>小久保翔平</p>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 <div class="slide cover" id="Cover"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 <header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 <h2>Monad に基づくメタ計算を基本とする Gears OS の設計</h2>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 <h3 id="author">小久保翔平</h3>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 <h3 id="profile"></h3>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 <!-- todo: add slide.classes to div -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 <!-- todo: create slide id from header? like a slug in blogs? -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 <div class="slide" id="2"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 <header>
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
33 <h1 id="section">研究目的</h1>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 <!-- === begin markdown block ===
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 generated by markdown 1.1.1 on Ruby 2.0.0 (2013-02-24) [x86_64-darwin12.3.0]
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
38 on 2015-05-25 05:40:40 +0900 with Markdown engine kramdown (1.4.0)
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 using options {}
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
44 <p>Many Core CPU, GPU, SpursEngine などの異なる演算資源を有効に利用するためには、それぞれのアーキテクチャに合わせた記述が必要になる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
45 Gears OS は Many Core CPU, GPU といった並列環境に合わせた設計・開発を行う</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
46
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
47 <p>Gears OS では Gear という単位を用いて記述することで柔軟性のあるプログラムを作成することを可能とする。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
48 新たな Gear を接続することでデータの拡張や機能の追加を行うことができる</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
49
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
50 <p>並列実行の信頼性を確保するため Gears OS では作成されたプログラムに対して Model Checking を行う。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
51 並列プログラムに Model Checking を行うことでそのプログラムが取り得る状態を列挙する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
52 これにより、デッドロック等を検出することで信頼性を確保する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
53
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
54
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
55
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
56 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
57 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
58
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
59 <div class="slide" id="3"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
60 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
61 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
62 <h1 id="cerium--alice">Cerium と Alice</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
63 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
64 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
65
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
66 <p>先行研究として、本研究室では並列プログラミングフレームワーク Cerium と分散ネットフレームワーク Alice の開発を行なってきた</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 <p>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列処理を実現する。
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 依存関係はプログラム自身が記述する必要があり、Task の種類が増えるほど記述が繁雑になる。
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 また、Task 間の依存関係のみに注目しており、データの依存関係を正しく保証することができない</p>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 <p>Task が取り扱うデータに型情報がない
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 汎用ポインタを型変換して利用するしかなく、型検査を行うことができない</p>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
80 <div class="slide" id="4"><div>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 <header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 <h1 id="cerium--alice-1">Cerium と Alice</h1>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
87 <p>Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラミングを行う。
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 Code Segment が取り扱う Input/Output Data Segment を指定することで処理とデータの関係を決定する</p>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
90 <p>Alice では Computaion を Data Segment を待ち合わせて Code Segment を実行することと定義している。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
91 これに対し、Meta Computation は Computation を実現する Computation と定義することができる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
92 通信中の切断や再接続の処理などは Meta Computation に相当する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
93
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 <p>Data Segment にアクセスする API が設計上の問題で複雑化している。
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
95 また、Meta Computation 自体が Alice で記述されていない</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 <div class="slide" id="5"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 <header>
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
105 <h1 id="code-gear--data-gear">Code Gear と Data Gear</h1>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 <p>Gears OS ではプログラム実行単位として Gear を用いる。
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 Gear は変更実行の単位、データの分割、Gear 間の接続などになる</p>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 <p>Code Gear は実行コードそのものであり、OpenCL/CUDA の kernel に相当する。
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 接続された複数の Input Data Gear を参照し、単一または複数の Output Data Gear に書き込む。
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 Code Gear では接続された Data Gear のみに干渉することができる</p>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
116 <p>Data Gear には、Primitive Data Type が格納される。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
117 直接ポインタを扱うことはなく、自分が知らない Code/Data Gear は名前で指し示す</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
118
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
119 <p>Gear の特徴の一つとしてその処理が Code/Data Gear に閉じていることがある。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
120 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
121
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
122
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
123
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
124 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
125 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
126
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
127 <div class="slide" id="6"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
128 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
129 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
130 <h1 id="monad--meta-computation">Monad と Meta Computation</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
131 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
132 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
133
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
134 <p>関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるものがある。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
135 メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副作用、メモリ管理などがある。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
136 メタ計算の理論的な表現として Monad を用いることが Moggi らにより提案されている</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
137
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
138 <p>Moand は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するのに必要な情報を格納している。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
139 失敗する計算の場合は、計算が失敗したかどうかのフラグが Monad に含まれる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
140 通常の計算を Monad を返すように変更することでメタ関数が得られる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
141 逆に Monad の中にある通常の値のみに着目すると通常の関数となる</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
142
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
143
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
144
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
145 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
146 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
147
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
148 <div class="slide" id="7"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
149 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
150 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
151 <h1 id="gears-os--meta-computation">Gears OS における Meta Computation</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
152 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
153 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
154
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
155 <p>Gears OS では Code/Data Gear に Meta Code/Data Gear を付属することで Monad を表現する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
156 Meta Code/Data Gear は Code/Data Gear へのポインタを持っている。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
157 各 Gear の関連付けは Meta Gear を用いて行われる</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
158
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
159 <p>オブジェクトレベルである Gear ではポインタを扱わず、メタレベルである Meta Gear でのみポインタを扱う。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
160 これにより、ポインタ関連のセキュリティフローを防止する。</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
161
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
163
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 <div class="slide" id="8"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 <header>
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
170 <h1 id="section-1">実装言語</h1>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
174 <p>Gears OS の実装には、本研究室で開発している Continuation based C(CbC) を用いる</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
175
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
176 <p>CbC ではプログラムを Code Segment, Data Segment という単位で記述する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
177 Code Segment 間の処理の移動には関数呼び出しではなく、goto を用いた軽量継続を用いている</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
178
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
179 <p>CbC のコンパイルには LLVM をバックエンドとしたコンパイラを用いる</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
185
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 <div class="slide" id="9"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 <header>
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
189 <h1 id="gears-os-">Gears OS の構成</h1>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
192
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
193 <p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
194
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
195 <p>Gears OS では Context を生成し、Worker を起動する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
196 Worker は Synchronized Queue から Code Gear を取得し、実行する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
197 実行に必要な Data Gear は Context を通して、Persistent Data Gear から読み込みを行う。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
198 処理が終わると必要な Data Gear を Persistent Data Gear に書き込みを行う</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
199
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
200
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
201
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
204
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 <div class="slide" id="10"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 <header>
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
208 <h1 id="code-gear-">Code Gear の継続</h1>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
211
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
212 <p>Code Gear では、次に実行する Code Gear を名前で指定する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
213 Meta Code Gear が名前を解釈して、対応する Code Gear に引き渡す。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
214 Gear OS では、この Meta Code Gear を Context と定義する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
215
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
216 <p>Context には Code Gear の名前とポインタの対応表、Data Gear の Allocation 用の情報、Code Gear が参照する Data Gear へのポインタ、Data Gear に格納される Data Type の情報が格納されている</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
217
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
218
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
219
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
222
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
223 <div class="slide" id="11"><div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 <section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 <header>
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
226 <h1 id="persistent-data-gear">Persistent Data Gear</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
227 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
228 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
229
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
230 <p>Data Gear の管理には木構造を用いる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
231 この木構造は非破壊で構成される。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
232 非破壊的木構造では、ロックなしに平行して読み書き・参照を行うことが可能である</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
233
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
234 <p>変更前の木構造をすべて保持しているので過去のデータにアクセスすることもできる</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
235
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
236
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
237
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
238 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
239 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
240
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
241 <div class="slide" id="12"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
242 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
243 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
244 <h1 id="list">List</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
245 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
246 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
247
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
248 <p>通常 List は要素と次へのポインタを持つ構造体で表現される</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
249
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
250 <p>Gears OS の場合、オブジェクトレベルではポインタを扱わないので、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
251
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
252 <p><img src="pictures/List.svg" alt="List" style="width: 70%" /></p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
253
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
254
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
255
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
256 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
257 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
258
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
259 <div class="slide" id="13"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
260 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
261 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
262 <h1 id="synchronized-queue">Synchronized Queue</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
263 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
264 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
265
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
266 <p>Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
267
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
268 <p>Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
269 M:receiver/sender が CAS を行う Meta Code Gear となる</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
270
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
271 <p><img src="pictures/synchronizedQueue.svg" alt="sync" style="width: 80%" /></p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
272
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
273
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
274
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
275 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
276 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
277
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
278 <div class="slide" id="14"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
279 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
280 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
281 <h1 id="context">Context</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
282 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
283 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
284
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
285 <pre><code>/* Context definition */
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
286 enum Code {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
287 Code1,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
288 Code2,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
289 Allocator,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
290 };
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
291
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
292 enum UniqueData {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
293 Allocate,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
294 Tree,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
295 };
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
296
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
297 struct Context {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
298 int codeNum;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
299 __code (**code) (struct Context *);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
300 void* heap_start;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
301 void* heap;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
302 long dataSize;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
303 int dataNum;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
304 union Data **data;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
305 };
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
306 </code></pre>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
307
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
308
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
309
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
310 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
311 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
312
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
313 <div class="slide" id="15"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
314 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
315 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
316 <h1 id="code-gear">Code Gear</h1>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
317 </header>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
318 <!-- _S9SLIDE_ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
319
17
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
320 <pre><code>// Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
321 __code code1(Allocate allocate) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
322 allocate.size = sizeof(long);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
323 allocate.next = Code2;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
324 goto Allocate(allocate); // goes through meta
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
325 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
326
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
327 // Meta Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
328 __code meta(struct Context* context, enum Code next) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
329 // meta computation
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
330 goto (context-&gt;code[next])(context);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
331 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
332
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
333 // Meta Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
334 __code allocate(struct Context* context) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
335 context-&gt;data[++context-&gt;dataNum] = context-&gt;heap;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
336 context-&gt;heap += context-&gt;data[Allocate]-&gt;allocate.size;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
337 goto (context-&gt;code[context-&gt;data[Allocate]-&gt;allocate.next])(context);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
338 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
339
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
340 // Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
341 __code code2(Allocate allocate, Count count) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
342 // processing
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
343 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
344 </code></pre>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
345
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
346 <pre><code>// Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
347 __code code1(struct Context* context) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
348 context-&gt;data[Allocate]-&gt;allocate.size = sizeof(struct Node);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
349 context-&gt;data[Allocate]-&gt;allocate.next = Code2;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
350 goto meta(context, Allocate);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
351 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
352
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
353 // Meta Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
354 __code meta(struct Context* context, enum Code next) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
355 // meta computation
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
356 goto (context-&gt;code[next])(context);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
357 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
358
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
359 // Meta Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
360 __code allocate(struct Context* context) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
361 context-&gt;data[++context-&gt;dataNum] = context-&gt;heap;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
362 context-&gt;heap += context-&gt;data[Allocate]-&gt;allocate.size;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
363 goto (context-&gt;code[context-&gt;data[Allocate]-&gt;allocate.next])(context);
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
364 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
365
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
366 // Code Gear
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
367 __code code2(struct Context* context) {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
368 // processing content
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
369 }
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
370 </code></pre>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
371
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
372
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
373
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
374 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
375 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
376
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
377 <div class="slide" id="16"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
378 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
379 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
380 <h1 id="data-gear">Data Gear</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
381 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
382 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
383
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
384 <pre><code>union Data {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
385 struct Tree {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
386 union Data* root;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
387 union Data* current;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
388 union Data* prev;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
389 int result;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
390 } tree;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
391 struct Node {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
392 int key;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
393 int value;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
394 enum Color {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
395 Red,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
396 Black,
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
397 } color;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
398 union Data* left;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
399 union Data* right;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
400 } node;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
401 struct Allocate {
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
402 long size;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
403 enum Code next;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
404 } allocate;
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
405 };
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
406 </code></pre>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
407
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
408
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
409
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
410 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
411 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
412
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
413 <div class="slide" id="17"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
414 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
415 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
416 <h1 id="section-2">比較</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
417 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
418 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
419
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
420 <p>Code Gear は Cerium の Task、Alice の Code Segment, OpenCL/CUDA の kernel に相当する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
421
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
422 <p>Data Gear は Alice の Data Segment に相当する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
423 Ceirum, OpenCL/CUDA には Data Gear に相当する物は存在しない</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
424
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
425 <p>Cerium, OpenCL/CUDA では処理同士の依存関係を記述する必要があるが、Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
426
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
427
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
428
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
429 </section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
430 </div></div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
431
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
432 <div class="slide" id="18"><div>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
433 <section>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
434 <header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
435 <h1 id="section-3">まとめ</h1>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
436 </header>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
437 <!-- _S9SLIDE_ -->
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
438
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
439 <p>Gears OS では処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
440
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
441 <p>Gear という単位を用いて記述することでプログラムを柔軟に変更することを可能とした</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
442
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
443 <p>Meta Computation を Moand に基づいて実現する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
444 Gears OS では Meta Code/Data Gear を用いて Monad を表現する</p>
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
445
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
446 <p>機能として Model Checking を提供し、プログラムの信頼性を確保する</p>
12
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
447 <!-- === end markdown block === -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
448
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
449 </section>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
450 </div></div>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
451
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
452
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
453 <script src="scripts/script.js"></script>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
454 <!-- Copyright © 2010–2011 Vadim Makeev, http://pepelsbey.net/ -->
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
455 </body>
ff895b2c6792 add presen
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
456 </html>