第14回TOPPERS活用アイデア・アプリケーション開発コンテスト 活用アイデア部門 への「箱庭時間管理手法に関する先行研究調査と改良」の提案

第14回TOPPERS活用アイデア・アプリケーション開発コンテスト 活用アイデア部門 へ「箱庭時間管理手法に関する先行研究調査と改良」という表題で応募しまして，銅賞を受賞しました．本記事では，既に公開されている応募内容について改めて共有し，ふりかえりたいと思います．

応募内容

部門

活用アイデア部門

作品のタイトル

箱庭時間管理手法に関する先行研究調査と改良

作成者

山崎進

共同作業者

山崎進研究室

作品の対象者

• 箱庭WG
• 箱庭ラボ

使用する開発成果物

箱庭

目的・狙い

箱庭では，並行して動作する個々のシミュレータが独立して時間管理しているのを同期することが求められる．
箱庭の時間管理方式は，先行研究としてFMIを挙げた上で，並列化容易な分散制御方式を提案しているが，理論的背景が不足しているとのことである．
そこで，先行研究を徹底調査し，現行方式の妥当性と改良を検討する．

アイデア／アプリケーションの概要

現時点で我々が着目している先行研究の体系は次の3つである．

1. 1980年代ごろに盛んに研究された，因果律を保持するような並行かつ論理的な時間管理手法
2. メモリ一貫性モデル
3. 分散データベース

これらについて徹底的に先行研究を調査し，現行方式の妥当性を検証し，必要であれば改良を提案する．

背景: 箱庭アーキテクチャの現状

箱庭アーキテクチャは次の4系統の機能を有する．

• アセット管理
• 同期・通信
• スケジューリング
• 時間管理

アーキテクチャとしては次のような構成をしている．

• サーバーサイド
  • 機能
    • 箱庭アセットの登録
    • 各シミュレーションの開始・停止・初期化
  • 構成
    • 箱庭コンダクタサーバー
    • 箱庭アセット
    • 箱庭API
    • PDU
    • 箱庭コア機能
• クライアントサイド
  • 機能
    • 箱庭アセットとしてサーバーに接続
  • 構成
    • 箱庭コンダクタクライアント
    • 箱庭アセット

ネットワークの構成として次の4類型ある．

1. サーバーサイドの箱庭コンダクタを中心としてアセットと時間の管理を行い，他の類型のコンピュータに時間を配分する役割を担う．時間周期の異なるコンピュータへはプロキシを介して時間を配信する．
2. クライアントサイドの箱庭コンダクタを中心としてアセットの管理を行い，時間については1と同期する．
3. 1と異なる時間周期で動作するサーバーサイドの箱庭コンダクタによるアセットと時間の管理．1に備わるプロキシを介して接続する．
4. 箱庭アセットのみを備え，1に管理を委ねる．

箱庭では様々なシミュレータが混在しており，それぞれ固有のシミュレーション時間を持つので，シミュレーション時間の同期を取る必要がある．

箱庭が先行事例として踏まえているのは，Functional Mock-up Interface (FMI) である．FMIでは，中央制御方式によって，完全に時間同期が可能であり，かつシミュレータ間でユーザが設定する一定量の遅延時間を許容する．FMIでは，中央制御方式なので，精度調整は容易であるが，システム構成要素が増えると処理オーバーヘッドが大きくなる問題点を有する．

そこで箱庭では，分散制御方式を取り入れ，各シミュレータは箱庭時間を見ながら，シミュレーション時間を調整し時間同期するという方式を取る．箱庭時間より早い場合は，シミュレーション時間を遅くし，箱庭時間より遅い場合は，シミュレーション時間を早くすることで調整する．各シミュレーション時間を可視化して，時間同期の程度を定量化し，環境スペックの妥当性を評価・調整する．

箱庭ラボの森氏によると，箱庭の現行方式について，理論的な背景があるわけではないので，経験的な範囲での妥当性確認に留まっているとのことである．また，時間同期が性能ボトルネックになる可能性が否めない．

そこで本提案では，体系的な先行研究調査を実施し，妥当性確認と，必要であれば改良を図ることを目的とする．

手掛かりとなる既存体系

我々が現時点で先行研究調査の手がかりとして把握しているのは次の3つである．

1. 1980年代ごろに盛んに研究された，因果律を保持するような並行かつ論理的な時間管理手法
2. メモリ一貫性モデル
3. 分散データベース

1については，提案者が大学院時代に並列プログラミングに関する授業で学んだ，1980年代ごろの平行プログラミング言語で検討されていた時間管理方式である．提案者の記憶では，本手法の考え方としては，次のとおりである．まず，あるプロセスAの中で因果関係があるようなプログラムの断片があったとする．それぞれのプログラムの断片で，別のプロセスBへの通信が発生していたとしたときに，プロセスBからは，プロセスAの中の因果関係の順番を保った状態で，メッセージを観測することになる．一方，あるプロセスAの中で因果関係のないようなプログラムの断片から，同じようにプロセスBへそれぞれ通信が発生していた場合，プロセスBで観測される順番は特に保証されない．本手法では，この考え方に沿って，束(ラティス)となるような論理的な時間を定義する．

2については，プロセッサを並列化・分散化する過程で，メモリを読み書きするときにどこまでの順序関係の厳密さを求めるかというようなモデルであり，TOPPERSカーネルをはじめとしたRTOSではお馴染みの考え方である．

3については，データベースの基本的な考え方であるコミットとロールバックをいかなる順番で行ってもデータ一貫性を保つように，分散環境で保障するような研究がなされている．

本提案では，これらの手がかりを踏まえて，並行時間管理に関する先行研究での議論を徹底的に調査する．その先行研究調査の内容は箱庭WGにレポートとして報告していき，ディスカッションを踏まえて，箱庭の現行時間管理方式の妥当性について検討し，潜在的な技術的課題を特定することで，箱庭のあるべき並行時間管理を模索する．