Mercurial > hg > Papers > 2019 > mitsuki-master
changeset 56:a75b7b214f13
update
author | mir3636 |
---|---|
date | Tue, 12 Feb 2019 15:00:41 +0900 |
parents | 1e1804a9269a |
children | b0cf2255c503 |
files | paper/fig/normal_Code_Gear.graffle slide/s6/themes/blank.css slide/s6/themes/projection.css slide/scripts/prettify.css slide/slide.html slide/slide.md |
diffstat | 6 files changed, 198 insertions(+), 149 deletions(-) [+] |
line wrap: on
line diff
--- a/slide/s6/themes/blank.css Tue Feb 12 08:05:32 2019 +0900 +++ b/slide/s6/themes/blank.css Tue Feb 12 15:00:41 2019 +0900 @@ -72,6 +72,7 @@ font-size: 160%; } li { + margin-top: 15px; margin-bottom: 15px; } p,
--- a/slide/s6/themes/projection.css Tue Feb 12 08:05:32 2019 +0900 +++ b/slide/s6/themes/projection.css Tue Feb 12 15:00:41 2019 +0900 @@ -20,7 +20,7 @@ top: 0; left: 0; margin: 0; - padding: 0% 4% 0% 4%; + padding: 2% 4% 0% 4%; /* css note: order is => top right bottom left */ -moz-box-sizing: border-box; -webkit-box-sizing: border-box;
--- a/slide/scripts/prettify.css Tue Feb 12 08:05:32 2019 +0900 +++ b/slide/scripts/prettify.css Tue Feb 12 15:00:41 2019 +0900 @@ -1,14 +1,18 @@ /* CSS from google html5slides(https://code.google.com/p/html5slides/) */ +code { + display: inline-block; +} + pre > code { + display: block; + font-family: 'Droid Sans Mono', 'Courier New', monospace; font-size: 20px; line-height: 28px; padding: 5px 10px; - letter-spacing: -1px; - margin-top: 40px; margin-bottom: 40px;
--- a/slide/slide.html Tue Feb 12 08:05:32 2019 +0900 +++ b/slide/slide.html Tue Feb 12 15:00:41 2019 +0900 @@ -2,10 +2,10 @@ <html> <head> <meta http-equiv="content-type" content="text/html;charset=utf-8"> - <title>Gears OS の並列処理</title> + <title>継続を基本とした言語による OS のモジュール化</title> -<meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16]"> -<meta name="author" content="伊波 立樹" > +<meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.4.0 (2016-12-24) [x86_64-darwin16]"> +<meta name="author" content="宮城 光希" > <!-- style sheet links --> <link rel="stylesheet" href="s6/themes/projection.css" media="screen,projection"> @@ -32,7 +32,6 @@ $('code').each(function(_, el) { if (!el.classList.contains('noprettyprint')) { el.classList.add('prettyprint'); - el.style.display = 'block'; } }); prettyPrint(); @@ -67,14 +66,14 @@ <tr> <td> <div align="center"> - <h1><font color="#808db5">Gears OS の並列処理</font></h1> + <h1><font color="#808db5">継続を基本とした言語による OS のモジュール化</font></h1> </div> </td> </tr> <tr> <td> <div align="left"> - 伊波 立樹 + 宮城 光希 琉球大学理工学研究科 河野研 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;"> </div> @@ -86,21 +85,67 @@ <div class='slide '> <!-- === begin markdown block === - generated by markdown/1.2.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16] - on 2018-02-21 23:50:59 +0900 with Markdown engine kramdown (1.13.2) + generated by markdown/1.2.0 on Ruby 2.4.0 (2016-12-24) [x86_64-darwin16] + on 2019-02-12 13:32:52 +0900 with Markdown engine kramdown (1.16.2) using options {} --> <!-- _S9SLIDE_ --> -<h2 id="section">並列処理の重要性</h2> +<h2 id="section">研究目的</h2> +<ul> + <li>現代の OS では拡張性と信頼性を両立させることが要求されている。</li> + <li>信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。</li> + <li>ノーマルレベルの計算とメタレベルの計算を切り離して記述するために Code Gear と Data Gear という単位を用いている</li> + <li>Gears OS は Continuation based C(CbC) によってアプリケーションと OS そのものを記述する。</li> + <li>本研究では、CbC を用いた Gears OS のモジュール化と信頼性のある OS を実現するために xv6 の CbC による書き換えを行う。</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="os-">OS の拡張性と信頼性の両立</h2> +<ul> + <li>さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。</li> + <li>時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。</li> + <li>その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="os--1">OS の拡張性と信頼性の両立</h2> + <ul> - <li>並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている</li> - <li>しかし、並列処理のチューニングや信頼性を保証するのは難しい - <ul> - <li>共通資源の競合などの非決定的な実行が発生するため、従来のテストやデバッグではテストしきれない部分が残ってしまう</li> - <li>GPU などのアーキテクチャに合わせた並列プログラミングの記述</li> - </ul> - </li> + <li>これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。</li> + <li>検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。</li> + <li>このため信頼性と拡張性を両立させることが重要である。</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="section-1">メタ計算</h2> +<ul> + <li>プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。</li> + <li>メタ計算はノーマルレベルの計算から切り離して記述したい。</li> + <li>そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。</li> + <li>そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="continuation-based-c-cbc">Continuation based C (CbC)</h2> +<ul> + <li>Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。</li> + <li>Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する。</li> + <li>この goto 文による遷移を軽量継続と呼ぶ。</li> + <li>継続によって状態遷移ベースでのプログラミングが可能。</li> + <li>C と互換性のある言語で、C の関数も呼び出すことができる。</li> </ul> @@ -109,53 +154,73 @@ <!-- _S9SLIDE_ --> <h2 id="gears-os">Gears OS</h2> <ul> - <li>本研究室では処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している</li> - <li>並列処理の Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される</li> - <li>計算をノーマルレベルとメタレベルに階層化、 信頼性と拡張性をメタレベルで保証する - <ul> - <li>並列処理の信頼性を通常の計算(ノーマルレベル) に保証</li> - <li>CPU、GPU などの実行環境の切り替え、データ拡張等を提供</li> - </ul> - </li> + <li>Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。</li> + <li>並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。</li> + <li>Input/Output Data Gear の依存関係が解決された Code Gear を並列実行する。</li> </ul> +<div style="text-align: center;"> + <img src="./images/normal_Code_Gear.pdf" alt="normalCodeGear" width="600" /> +</div> + </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="gears-os-1">Gears OS</h2> +<h2 id="xv6--cbc-">xv6 の CbC 書き換え</h2> <ul> - <li>本研究では Gears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う</li> - <li>また、並列処理を行う例題を用いて評価、 OpenMP、 Go 言語との比較を行う</li> + <li>xv6 は 2006 年に MIT のオペレーティングシステムコースで教育用の目的として開発されたオペレーティングシステムである。</li> + <li>xv6 は UNIX V6 を x86 向けに再実装した OS である。</li> + <li>OS としての基本的な構造を持つにも関わらず、シンプルで扱いやすい。</li> + <li>継続を用いる CbC で記述することにより、実行可能な OS がそのまま状態遷移モデルに落ちる。</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="code-geardata-gear">Code Gear/Data Gear</h2> +<h2 id="cbc-">CbC のコード例</h2> <ul> - <li>Gears OS は Code Gear、 Data Gear という単位で構成される</li> - <li>Code Gear はプログラムの処理そのものを表す</li> - <li>Data Gear はデータそのものを表す</li> - <li>Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する</li> - <li>Code Gear と Input/Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う</li> + <li>Code Gear は__code Code Gear 名 (引数) の形で記述される。</li> + <li>Code Gear は戻り値を持たないので、return 文は存在しない。</li> + <li>goto Code Gear 名 (引数) で次の Code Gear への遷移を表し、これを継続と呼ぶ。</li> +</ul> + +<pre lang="Code_Gear"><code>__code cg0(int a, int b){ + goto cg1(a+b); +} + +__code cg1(int c){ + goto cg2(c); +} +</code></pre> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="gears-">Gears でのメタ計算</h2> +<ul> + <li>Gears OS ではメタ計算を Meta Code/Data Gear で表現する。</li> + <li>Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。</li> + <li>Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。</li> </ul> <div style="text-align: center;"> - <img src="./images/codegear-datagear-dependency.svg" alt="message" width="600" /> + <img src="./images/meta_Code_Gear.pdf" alt="MetaCodeGear" width="600" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-1">メタ計算</h2> +<h2 id="gears--1">Gears でのメタ計算</h2> <ul> - <li>メタ計算 は通常の計算を実行するための計算</li> - <li>信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等</li> - <li>Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる</li> - <li>メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる</li> + <li>ノーマルレベルとメタレベルの処理はそれぞれ並行して存在するものではなく、 +メタレベルの処理にも Meta Meta Gear となるメタレベルの処理が存在するように、 +階層上の構造となっている。</li> + <li>この2つのレベルはプログラミング言語レベルでの変換として実現される。</li> + <li>本研究では Perl スクリプトによって実装されている。</li> </ul> @@ -164,54 +229,12 @@ <!-- _S9SLIDE_ --> <h2 id="meta-gear">Meta Gear</h2> <ul> - <li>メタ計算 は Code Gear の接続間に行われる</li> - <li>この Gear を Meta Code/Data Gearと呼ぶ - <ul> - <li>Meta Code Gear は メタ計算 のプログラム部分</li> - <li>Meta Data Gear は Meta Code Gear で管理されるデータ部分</li> - </ul> - </li> - <li>Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う</li> -</ul> - -<div style="text-align: center;"> - <img src="./images/meta_cg_dg.svg" alt="message" width="850" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="continuation-based-c">Continuation based C</h2> -<ul> - <li>Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる</li> - <li>CbC は Code Gear を用いて記述する事を基本とする</li> + <li>Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。</li> + <li>通常の計算からはメタ計算は見ることができない。</li> </ul> - - +<div style="text-align: center;"> + <img src="./images/meta_gear.pdf" alt="MetaGear" width="600" /> </div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="continuation-based-c-1">Continuation based C</h2> -<ul> - <li>CbC の Code Gear の定義は <strong>__code CG名</strong> で行う</li> - <li>Code Gear 間は <strong>goto CG名</strong> で移動する。この移動を継続と呼ぶ</li> - <li>Code Gear の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない - <ul> - <li>このような環境を持たない継続を軽量継続と呼ぶ</li> - </ul> - </li> - <li>下記のコードでは Code Gear を2つ定義し、 cg0 から cg1 への継続を示している</li> -</ul> - -<pre lang="c"><code>__code cg0(int a, int b) { - goto cg1(a+b); -} - -__code cg1(int c) { - goto cg2(c); -} -</code></pre> </div>
--- a/slide/slide.md Tue Feb 12 08:05:32 2019 +0900 +++ b/slide/slide.md Tue Feb 12 15:00:41 2019 +0900 @@ -1,77 +1,72 @@ -title: Gears OS の並列処理 -author: 伊波 立樹 +title: 継続を基本とした言語による OS のモジュール化 +author: 宮城 光希 profile: 琉球大学理工学研究科 河野研 lang: Japanese code-engine: coderay -## 並列処理の重要性 -- 並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている -- しかし、並列処理のチューニングや信頼性を保証するのは難しい - - 共通資源の競合などの非決定的な実行が発生するため、従来のテストやデバッグではテストしきれない部分が残ってしまう - - GPU などのアーキテクチャに合わせた並列プログラミングの記述 +## 研究目的 +- 現代の OS では拡張性と信頼性を両立させることが要求されている。 +- 信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。 +- ノーマルレベルの計算とメタレベルの計算を切り離して記述するために Code Gear と Data Gear という単位を用いている +- Gears OS は Continuation based C(CbC) によってアプリケーションと OS そのものを記述する。 +- 本研究では、CbC を用いた Gears OS のモジュール化と信頼性のある OS を実現するために xv6 の CbC による書き換えを行う。 -## Gears OS -- 本研究室では処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している -- 並列処理の Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される -- 計算をノーマルレベルとメタレベルに階層化、 信頼性と拡張性をメタレベルで保証する - - 並列処理の信頼性を通常の計算(ノーマルレベル) に保証 - - CPU、GPU などの実行環境の切り替え、データ拡張等を提供 - -## Gears OS -- 本研究では Gears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う -- また、並列処理を行う例題を用いて評価、 OpenMP、 Go 言語との比較を行う +## OS の拡張性と信頼性の両立 +- さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。 +- 時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。 +- その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。 -## Code Gear/Data Gear -- Gears OS は Code Gear、 Data Gear という単位で構成される -- Code Gear はプログラムの処理そのものを表す -- Data Gear はデータそのものを表す -- Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する -- Code Gear と Input/Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う +## OS の拡張性と信頼性の両立 -<div style="text-align: center;"> - <img src="./images/codegear-datagear-dependency.svg" alt="message" width="600"> -</div> +- これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。 +- 検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。 +- このため信頼性と拡張性を両立させることが重要である。 ## メタ計算 -- メタ計算 は通常の計算を実行するための計算 -- 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等 -- Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる -- メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる +- プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。 +- メタ計算はノーマルレベルの計算から切り離して記述したい。 +- そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。 +- そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。 -## Meta Gear -- メタ計算 は Code Gear の接続間に行われる -- この Gear を Meta Code/Data Gearと呼ぶ - - Meta Code Gear は メタ計算 のプログラム部分 - - Meta Data Gear は Meta Code Gear で管理されるデータ部分 -- Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う +## Continuation based C (CbC) +- Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。 +- Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する。 +- この goto 文による遷移を軽量継続と呼ぶ。 +- 継続によって状態遷移ベースでのプログラミングが可能。 +- C と互換性のある言語で、C の関数も呼び出すことができる。 + +## Gears OS +- Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。 +- 並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。 +- Input/Output Data Gear の依存関係が解決された Code Gear を並列実行する。 <div style="text-align: center;"> - <img src="./images/meta_cg_dg.svg" alt="message" width="850"> + <img src="./images/normal_Code_Gear.pdf" alt="normalCodeGear" width="600"> </div> -## Continuation based C -- Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる -- CbC は Code Gear を用いて記述する事を基本とする +## xv6 の CbC 書き換え +- xv6 は 2006 年に MIT のオペレーティングシステムコースで教育用の目的として開発されたオペレーティングシステムである。 +- xv6 は UNIX V6 を x86 向けに再実装した OS である。 +- OS としての基本的な構造を持つにも関わらず、シンプルで扱いやすい。 +- 継続を用いる CbC で記述することにより、実行可能な OS がそのまま状態遷移モデルに落ちる。 -## Continuation based C -- CbC の Code Gear の定義は **__code CG名** で行う -- Code Gear 間は **goto CG名** で移動する。この移動を継続と呼ぶ -- Code Gear の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない - - このような環境を持たない継続を軽量継続と呼ぶ -- 下記のコードでは Code Gear を2つ定義し、 cg0 から cg1 への継続を示している +## CbC のコード例 +- Code Gear は\_\_code Code Gear 名 (引数) の形で記述される。 +- Code Gear は戻り値を持たないので、return 文は存在しない。 +- goto Code Gear 名 (引数) で次の Code Gear への遷移を表し、これを継続と呼ぶ。 -``` c -__code cg0(int a, int b) { - goto cg1(a+b); +```Code_Gear +__code cg0(int a, int b){ + goto cg1(a+b); } -__code cg1(int c) { - goto cg2(c); +__code cg1(int c){ + goto cg2(c); } ``` ## Data Gear の表現 -- Data Gear は構造体を用いて定義する +- Data Gear は Gears OS におけるデータの単位である。 - メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される - Data Gear をメモリに確保する際のサイズ情報はこの型から決定する @@ -91,16 +86,42 @@ }; ``` +## Gears でのメタ計算 +- Gears OS ではメタ計算を Meta Code/Data Gear で表現する。 +- Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。 +- Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。 + +<div style="text-align: center;"> + <img src="./images/meta_Code_Gear.pdf" alt="MetaCodeGear" width="600"> +</div> + +## Gears でのメタ計算 +- ノーマルレベルとメタレベルの処理はそれぞれ並行して存在するものではなく、 +メタレベルの処理にも Meta Meta Gear となるメタレベルの処理が存在するように、 +階層上の構造となっている。 +- この2つのレベルはプログラミング言語レベルでの変換として実現される。 +- 本研究では Perl スクリプトによって実装されている。 + +## Meta Gear +- Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。 +- 通常の計算からはメタ計算は見ることができない。 +<div style="text-align: center;"> + <img src="./images/meta_gear.pdf" alt="MetaGear" width="600"> +</div> + ## Context -- Context は従来のOS のスレッドやプロセスに対応し、以下の要素をもっている Meta Data Gear - - Data Gear を確保するためのメモリ空間 - - Code Gear の名前と関数ポインタとの対応表 - - Code Gear は番号(enum)で指定する - - Code Gear が参照する Data Gear へのポインタ - - Code Gear と同じく Data Gear も番号で指定する - - 並列実行用の Task 情報 - - Data Gear の型情報 -- Gears OS ではメタ計算で Context を経由して Code/Data Gear に番号でアクセスする +- Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている。 +- Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある。 +- Context は Meta Data Gear であるため、Meta Code Gear を介してアクセスする。 + +## Context +- Context は Code Gear のリストを持っており、enum で番号とアドレスを対応付けている。 +- + + + + + ## stub Code Gear - Data Gear にアクセスするには Context から番号を指定して行う