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 の構成のやつ ## Gears OS での形式化とInterfaceの導入 - 形式化とは仕様、実装、実行を Logic で記述する事である。 - Gears OS では、継続を使った関数型プログラムとして実装を記述する - Logic としては、依存型関数言語である Agda を使う(外間の発表) - 証明とモデル検査を使って、信頼性を確保する ## Gears OS の Interface - Code Gear と Deta Gear は Interface と呼ばれるまとまり(モジュール)で記述される。 - Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。 - Interface は Data Gear で記述されて、Meta Deta Gear と呼ばれる。 - Java などの Class に相当する。 % - Interface を外から呼び出すための Code Gear 群の型 - Interface を呼び出す時に必要となる引数を全て格納する Data Gear % - 実装に使う Code Gear の番号が含まれている。 % - Code Gear の番号を変更することによって異なる実装を実現できる % Interface は実行時に実装を入れ替える事ができる % 呼び出すものはStack 上に積めない % Contextも集合 ## 並列API - Geas OS 信頼性を保証するために、モジュールシステムが必要である。 - 本研究では、モジュールシステムとその応用である並列APIについて考察する。 - 並列APIは継続を基本とした関数型プログラミングと両立する必要があり、ここでは CbC の goto 文を拡張した par goto を導入する。 ## スライドの流れ - Interface - CbC - Gears OS における並列実行 - 比較 - 今後の課題 ## CbC - ノーマルレベルとメタレベルの計算を1つの言語で表現できる言語として、本研究室で設計した CbC を用いる。 - ノーマルレベルの計算 - コンピュータの計算はプログラミング言語で行われる。 - その部分をノーマルレベルの計算と呼ぶ。 - メタレベルの計算 - コードが実行される際の以下の部分が、メタレベルの計算という。 - 処理系の詳細や使用する資源 - コードの仕様や型などの部分 % ノーマルレベルとメタレベルの違い % 以外 = メモリ % 定義されたものに従って形式的にプログラムが記述されるが、その実行の資源や環境がメタレベル % 実行するのはOSや資源 % 実際にはプログラムで記述されていない部分(CPU,メモリの資源、並列処理、外界の影響) この4つ書く % CbC の特徴はメタもかける % OS での資源はCbCでかける % シミュレーションされた外界 % シミュレーションされてない外界はOSとは違うのでCbCで書けない % ぱるすさんの図入れるMeta data Gear ## CbC - CbC を用いることで、ノーマルレベルの計算の信頼性をメタレベルから保証できるようになる。 - CbC を用いて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 の形式化ができる ## スライドの流れ - CbC - Gears OS における並列実行 - 比較 - 今後の課題 ## Gears における並列実行 - Gears OS ではメタ計算を柔軟に記述するためのプログラミングの単位として Code Gear と Data Gear を用いる。 - それぞれにメタレベルの単位が存在し、Meta Data Gear と Meta Code Gear と呼ぶ。 - メタレベルの計算は Perl スクリプトによって生成され、Code Gear で記述される。
Processor | Time(ms) |
1 CPU | 1181.215 |
2 CPUs | 627.914 |
4 CPUs | 324.059 |
8 CPUs | 159.932 |
16 CPUs | 85.518 |
32 CPUs | 43.496 |
GPU | 127.018 |
GPU(kernel only) | 6.018 |