Mercurial > hg > Papers > 2018 > tobaru-sigos

view Slide/prosym.md @ 10:d4e58a38aae7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author tobaru
date Tue, 22 May 2018 10:13:39 +0900
parents 5790bdc1d515
children 6fdcb5241bda
line wrap: on
line source

title: Gears OS のモジュール化と並列 API
author: Mitsuki Miyagi, Yu Tobaru, Shinji Kono
profile: 琉球大学
lang: Japanese
code-engine: coderay

% ## OS の信頼性
% - コンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。
% - OS は非決定的な実行を持つため、OS の信頼性を保証するには、証明を用いる方法とプログラムの可能な実行を全て数え上げるモデル検査を用いる必要がある。
% 	- 従来のテストとデバッグではテスト仕切れない部分が残ってしまい、不十分。
% 	- モデル検査は無限の状態でなくても巨大な状態を調べる事になり、状態を有限に制限したり、状態を抽象化したりする方法が用いられる。
% 
% ## OS の拡張性
% - 時代とともに進歩するハードウェア、サービスに対応するために OS 自体が拡張される必要がある。
% - OS を検証する際にも、1度ではなくアプリケーションやサービス、デバイスが新しくなる毎に検証をやり直す必要がある。
% 
% ## OS の拡張性と信頼性の両立
% - OSの拡張性と信頼性の観点から、OS は信頼性と拡張性を両立させることが重要であるといえる。 
% - 本研究室では、OS の信頼性の保証と拡張性を実現することを目標に Gears OS を設計中である。
 
## Gears OS
- 現代のOS では拡張性と信頼性を両立させることが要求されている。
	- 時代と共にハードウェア、サービスが進歩していき、その度に OS を検証できる必要があるため、拡張性が必要。
	- OS は非決定的な実行を持ち、従来の OS ではテストしきれない部分が残ってしまうため、信頼性が欠けてしまうので信頼性のある OS が必要。
- 本研究室では、拡張性と信頼性を実現することを目標に Gears OS の開発を行なっている。

% 欠けてしまうで終わってるので　"それら"は 分かりづらい
% 並列API 研究目的とAPIとの繋がりがない
% モジュールとAPIの説明分ける
% 拡張性と信頼性を実現する時に Interfaceと par goto 構文がなぜ必要なのかに繋げる話が必要
% APIと実装の分離が望ましい理由は？

% ## API と実装の分離
% - Gears OS は Continuation based C(以下、CbC)によって記述されている。
% - CbC は Code Gear と Data Gear の単位でプログラムを記述していて、システムやアプリケーションを作る際に、この2つは柔軟に再利用する必要がある。
% - この時に、機能を接続する API と実装の分離が可能であることが望ましい。

% 上と繋がってない
% なんでモジュールシステムが必要？
% 形式化と言わない
% 形式化 formalization 
% ここでいう形式化はInterfaceとは関係ない
% interface は仕様とAPIの分離
% 実装の分割 がInterface
% まず、形式化が重要(仕様、実装、実行をlogicで記述)
% その記述にAgdaを使う

% Interfaceはほとんどかかない
% TaskScheduler の図も入れる Gears の構成のやつ


## スライドの流れ
- <font color="red">Interface</font>
- 並列API
- CbC
- Gears OS における並列実行
- 比較
- 今後の課題 


## Gears OS での形式化とInterfaceの導入
- 形式化とは仕様、実装、実行を Logic で記述する事である。
- Gears OS では、継続を使った関数型プログラムとして実装を記述する
- Logic としては、依存型関数言語である Agda を使う(外間の発表)
- 証明とモデル検査を使って、信頼性を確保する

## Gears OS の Interface 
- Code Gear と Deta Gear は Interface と呼ばれるまとまり(モジュール)で記述される。
	- Gears OS のモジュール化
- Interface 作成時に Code Gear の集合を指定することにより複数の実装(並列処理)を持つことができる。
- Interface は Data Gear で記述されて、Meta Deta Gear と呼ばれる。
- Java などの Class に相当する。
- Data Gear に Interface を呼び出す時に必要となる引数を全て格納する
% - 実装に使う Code Gear の番号が含まれている。
% - Code Gear の番号を変更することによって異なる実装を実現できる

% - Interface を外から呼び出すための Code Gear 群の型

% Interface は実行時に実装を入れ替える事ができる
% 呼び出すものはStack 上に積めない
% Contextも集合

## スライドの流れ
- Interface
- <font color="red">並列API</font>
- CbC
- Gears OS における並列実行
- 比較
- 今後の課題 


## 並列API
- Geas OS 信頼性を保証(テスト)するために、モジュールシステムが必要である。
- 本研究では、モジュールシステムとその応用である並列APIについて考察する。
- 並列APIは継続を基本とした関数型プログラミングと両立する必要があり、ここでは CbC の goto 文を拡張した **par goto** を導入する。
	- Interface でモジュール化
	- 応用として par goto を使って 並列API を実装

## スライドの流れ
- Interface
- 並列API
- <font color="red">CbC</font>
- Gears OS における並列実行
- 比較
- 今後の課題 





## CbC 
- ノーマルレベルとメタレベルの計算をまとめて表現できる言語として、本研究室で設計した CbC を用いる。
	- ノーマルレベルの計算
		- コンピュータの計算はプログラミング言語で行われる。
		- その部分をノーマルレベルの計算と呼ぶ。
	- メタレベルの計算
		- コードが実行される際の以下の部分が、メタレベルの計算という。
			- 処理系の詳細や使用する資源
			- コードの仕様や型などの部分

% ノーマルレベルとメタレベルの違い
% 以外 = メモリ
% 定義されたものに従って形式的にプログラムが記述されるが、その実行の資源や環境がメタレベル
% 実行するのはOSや資源
% 実際にはプログラムで記述されていない部分(CPU,メモリの資源、並列処理、外界の影響) この４つ書く
% CbC の特徴はメタもかける
% OS での資源はCbCでかける
% シミュレーションされた外界
% シミュレーションされてない外界はOSとは違うのでCbCで書けない
% ぱるすさんの図入れるMeta data Gear 

## CbC 
- CbC を用いることで、ノーマルレベルの計算の信頼性をメタレベルから保証できるようになる。
	- 処理の詳細やコードの型を数え上げる事による信頼性の保証
- CbC を用いてCode Gear と Data Gear を導入する。
	- Code Gear は並列処理の単位として利用
	- Data Gear はデータそのもの


% - 検証には 定理証明支援系である Agda を用いる。
% - Gears の記述をモジュール化するために Interface を導入した。
% - さらに並列処理の記述用に par goto 構文を導入する。

% ## par goto の実行
% - 本論文では Interface と par goto の実装を記述し、評価を行なった。
% - また、マルチ CPU と GPU 上での par goto 文の実行を確認した。

% par goto には構文と実行の話がある
% ストーリー的に早いのでここでは入れない 

## CbC の構文
- CbC の Code Gear は __code という型を持つ関数として記述する。
- 継続で次の Code Gear に遷移するので、戻り値は持たない。
- 遷移は goto 文による継続で処理を行い、引数として入出力を行う。
```c
__code cg0(int a, int b) {
    goto cg1(a+b);
}
__code cg1(int c) {
    goto cg2(c);
}
```
- CbC の記述だけでは並列実行にならない

% 関数呼び出しで実装したい　なのでpar つける
% 意味: 戻り値がなく　exitで呼び出す
% par goto (並列実行を実装したい、形式化したい=Agdaの記述をしたい) 並列実行を形式化する
% 本文のpar goto を削って載せる
% なぜ par goto が必要か
% context がこれの先に出てないとだめ
% 形式化はどうするの？-> par goto を使う。
% par goto を使えば並列実行されたGears の形式化ができる


## スライドの流れ
- Interface
- 並列API
- CbC
- <font color="red">Gears OS における並列実行</font>
- 比較
- 今後の課題 

## Gears における並列実行
- Gears OS ではメタ計算を柔軟に記述するためのプログラミングの単位として Code Gear と Data Gear を用いる。
- それぞれにメタレベルの単位が存在し、Meta Data Gear と Meta Code Gear と呼ぶ。
- メタレベルの計算は Perl スクリプトによって生成され、Code Gear で記述される。
<div style="text-align: center;">
    <img src="./image/meta_cg_dg.svg" alt="Meta Data Gear と Meta Code Gear" width="600">
</div>



% ## Interface
% - この時、Code Gear と Deta Gear は Interface と呼ばれるまとまり(モジュール)で記述される。
% - Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。

## Gears OS の構造 
- Gears OS は以下の要素で構成されている
	- Context
	- TaskQueue
	- TaskManager
	- Worker

<div style="text-align: center;">
    <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
</div>


## Context
- 1つのスレッド内で使われる Interface の Code Gear と Data Gear は Meta Data Gear に格納される。
- この Meta Data Gear を Context と呼ぶ。 
- Context を複製して複数の CPU に割り当てることにより並列実行が可能になる。 
- ノーマルレベルでは見る事ができない。
- Context は Task でもある。
- Task は実行する Code Gear と Data Gear を全て持っている。
<div style="text-align: center;">
    <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
</div>



## TaskManager
- Task を実行する Worker の生成
- Worker の管理
- Task の送信
<div style="text-align: center;">
    <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
</div>



## Worker
- TaskQueue から Task である Context を取得
- Task の Code Gear を実行
- Output Data Gear への書き出し
<div style="text-align: center;">
    <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
</div>



% exit が説明不足
% code gear の実行は他のシープに邪魔されない。
% 並列実行時の書き換えは許してない

## 1つの Code Gear の実行は他の Code Gear に割り込まれない 
- 共有された Data Gear があった時に、それに対する変更はただ1つの Code Gear だけが許される
- 読み込みは複数であってもいい
- Agda 側で、並列実行を Code Gear の順次実行としてシミュレーションするため
- このような実行になるように Gears OS の実装を行う

% 複数走ったなかの成功したものをコミットするのがexit 

<div style="text-align: center;">
    <img src="./image/gears_structure.png" alt="Gears OS の構造" width="400">
</div>





# par goto  
- Context(Task) の複製には par goto を用いる。
- 他に、入力の同期、タスクスケジューラへの Context の登録が行われる。
- 複数実行した時に、共有 Data Gear に書き込みを成功したかを確認(commit)するために __exit を使用する。
- par goto で生成された Task は __exit に継続することで終了する
- GearsOS の Task は Output Data Gear を生成した時点で終了する
- そのため、par goto では直接 __exit に継続せず、Output Data Gear への書き出し処理に継続される。
% - Code Gear と Data Gear の依存関係をノーマルレベルで記述できるようになる。
```c
__code code1(Integer *integer1, Integer * integer2, Integer *output) {
    par goto add(integer1, integer2, output, __exit);
    goto code2();
}
```

## Perl スクリプトによる Meta Data Gear の生成


% Task Manager
%  

```c
__code code1(struct Context *context, Integer *integer1, Integer *integer2, Integer *output) {
    // create context
    context->task = NEW(struct Context);
    initContext(context->task);

    // set task parameter
    context->task->next = C_add;
    context->task->idgCount = 2;
    context->task->idg = context->task->dataNum;
    context->task->maxIdg = context->task->idg + 2;
    context->task->odg = context->task->maxIdg;
    context->task->maxOdg = context->task->odg + 1;
...
    // set TaskManager->spawns parameter
    Gearef(context, TaskManager)->taskList = context->taskList;
    Gearef(context, TaskManager)->next1 = C_code2;
    goto parGotoMeta(context, C_code2);
}
``` 
%    // set Input Data Gear
%    context->task->data[context->task->idg+0] = (union Data*)integer1;
%    context->task->data[context->task->idg+1] = (union Data*)integer2;
%
%    // set Output Data Gear
%    context->task->data[context->task->odg+0] = (union Data*)integer3;


%    // add taskList Element
%    struct Element* element;
%    element = &ALLOCATE(context, Element)->Element;
%    element->data = (union Data*)context->task;
%    element->next = context->taskList;
%    context->taskList = element;
 
% 失敗した時はmeta compitation で処理する

% ***

% ## Interface


% ## Context

% ## 並列構文

## スライドの流れ
- Interface
- 並列API
- CbC
- Gears OS における並列実行
- <font color="red">比較</font>
- 今後の課題 


## Gears OS の評価(目的)
- 並列構文とそれを実現する Meta Compitation が十分に揃っているかを確認したい
- 並列処理の台数効果を確認する
- 既存の並列言語と比較して不要なオーバーヘッドがあるか調べたい  

## Gears OS の評価(環境)
- CPU、GPU環境で Gears OS の測定を行う。
- 使用した環境は次のようになる。
	- CPU 環境
		- Model : Dell PowerEdgeR630
		- Memory : 768GB
		- CPU : 2 × 18-Core Intel Xeon 2.30GHz
	- GPU 環境
		- GPU : GeForce GTX 1070
		- Cores : 1920
		- ClockSpeed : 1683MHZ
		- Memory Size : 8GB GDDR5

## Twice
- 評価には与えられた整数配列の全ての要素を2倍にする例題である Twice を使う。
- Twice では 通信時間を考慮しなければ、CPU より コア数の多い GPU が有利となる。
- 要素数2^27のデータに対する Twice の実行結果を示す。
	- CPU では2^27のデータを64個のデータに分割した。
	- kernel only は 通信速度を除いた速度である。

<table  border="1" align='center' width='50%'>
  <tbody>
    <tr>
      <td style="text-align: center;">Processor</td>
      <td style="text-align: center;">Time(ms)</td>
    </tr>
    <tr>
      <td style="text-align: center;">1 CPU</td>
      <td style="text-align: right;">1181.215</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">627.914</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">324.059</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">159.932</td>
    </tr>
    <tr>
      <td style="text-align: center;">16 CPUs</td>
      <td style="text-align: right;">85.518</td>
    </tr>
    <tr>
      <td style="text-align: center;">32 CPUs</td>
      <td style="text-align: right;">43.496</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU</td>
      <td style="text-align: right;">127.018</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU(kernel only)</td>
      <td style="text-align: right;">6.018</td>
    </tr>
  </tbody>
</table>

## 評価の考察
- コア数が上がるごとに、処理速度が上がっている。
	- 台数効果が見られる
- GPUでの実行は 32CPU に比べて約7.2倍の速度向上が見られた。
- 通信速度を含めると 16CPU より遅い。
	- 通信速度によるオーバーヘッド

<table  border="1" align='center' width='50%'>
  <tbody>
    <tr>
      <td style="text-align: center;">Processor</td>
      <td style="text-align: center;">Time(ms)</td>
    </tr>
    <tr>
      <td style="text-align: center;">1 CPU</td>
      <td style="text-align: right;">1181.215</td>
    </tr>
    <tr>
      <td style="text-align: center;">2 CPUs</td>
      <td style="text-align: right;">627.914</td>
    </tr>
    <tr>
      <td style="text-align: center;">4 CPUs</td>
      <td style="text-align: right;">324.059</td>
    </tr>
    <tr>
      <td style="text-align: center;">8 CPUs</td>
      <td style="text-align: right;">159.932</td>
    </tr>
    <tr>
      <td style="text-align: center;">16 CPUs</td>
      <td style="text-align: right;">85.518</td>
    </tr>
    <tr>
      <td style="text-align: center;">32 CPUs</td>
      <td style="text-align: right;">43.496</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU</td>
      <td style="text-align: right;">127.018</td>
    </tr>
    <tr>
      <td style="text-align: center;">GPU(kernel only)</td>
      <td style="text-align: right;">6.018</td>
    </tr>
  </tbody>
</table>

% なんでGo言語？
## Go 言語との比較
- Go 言語でも Twice を用いた検証を行い、Gears OS との速度比較を行なった。
- 1CPU と 32CPU では約4.33倍の速度向上が見られた。
- CPU数による速度向上は、Gears OS の方が上だが、処理速度では Go言語の方が速い結果となった。
<div style="text-align: center;">
    <img src="./image/vsgo.svg" alt="Goとの比較" width="500">
</div>


## スライドの流れ
- Interface
- 並列API
- CbC
- Gears OS における並列実行
- 比較
- <font color="red">今後の課題</font>


## スライドの流れ
- CbC
- Gears OS における並列実行
- 比較
- <font color="red">今後の課題</font>

## 今後の課題
- Go 言語との比較から 1CPU での動作が遅いことがわかった。
- par goto 文を使用することで、Contextを生成し、並列処理を行う。
- しかし、Context はメモリ空間の確保や使用する全ての Code Gear Data Gear の設定をする必要があり、生成に時間がかかってしまう事が原因。
- 処理が軽い場合は Context を生成しないようなチューニングが必要である。



## Perlスクリプトによる変換
```c
__code code1(struct Context *context, Integer *integer1, Integer *integer2, Integer *output) {
    // create context
    context->task = NEW(struct Context);
    initContext(context->task);

    // set task parameter
    context->task->next = C_add;
    context->task->idgCount = 2;
    context->task->idg = context->task->dataNum;
    context->task->maxIdg = context->task->idg + 2;
    context->task->odg = context->task->maxIdg;
    context->task->maxOdg = context->task->odg + 1;

    // create Data Gear Queue
    GET_META(integer1)->wait = createSynchronizedQueue(context);
    GET_META(integer2)->wait = createSynchronizedQueue(context);
    GET_META(integer3)->wait = createSynchronizedQueue(context);

    // set Input Data Gear
    context->task->data[context->task->idg+0] = (union Data*)integer1;
    context->task->data[context->task->idg+1] = (union Data*)integer2;

    // set Output Data Gear
    context->task->data[context->task->odg+0] = (union Data*)integer3;

    // add taskList Element
    struct Element* element;
    element = &ALLOCATE(context, Element)->Element;
    element->data = (union Data*)context->task;
    element->next = context->taskList;
    context->taskList = element;
    
    // set TaskManager->spawns parameter
    Gearef(context, TaskManager)->taskList = context->taskList;
    Gearef(context, TaskManager)->next1 = C_code2;
    goto meta(context, C_code2);
}
```