next up previous
Next: 研究の成果 Up: 「KL1のゴールスケジュー リング最適化」に関する成果概要 Previous: 研究の背景と目的

研究の内容

動的スレッド切替

スレッド内のゴールは

  1. スレッド内ゴールは後続ゴールにデータ依存を生じないように静的に実 行順序が固定される
  2. ゴールの中断はスレッドの中断となるため、あるスレッドにおける中断 したゴールの後続ゴールはその中断ゴール再開まで決してスケジュールされな い
  3. スレッド内ゴールは入力引数がそろっている限り逐次的に実行する

のように実行される。

しかしながら、3をそのまま用いると、スレッドの切り替えはスレッドの中断 および終了時まで行われない。これでは、生成・参照プロセス間のゴール(ス レッド)の切り替えが必ず中断で行われてしまうという問題が生じてしまう。

この問題を解決するためには、スレッドの実行の途中であっても、スレッドを メッセージ指向的に切り替えるような機構が必要である。この生成・参照プロ セス間の中断による切り替えの影響が最も大きいと考えられるのは、生成・参 照スレッド内にそれぞれループ構造が存在し、そのループ内のゴール同士がス レッド間で論理的な通信を行う場合である。

よって再帰呼出し時をメッセージ指向的なスレッド切替を行うタイミングとす れば、このような問題を避けることができる。しかしながら再帰呼出し時に常 にスレッド切替を許してしまうと、参照側が必要とするデータをループを用い て生成する場合、構造データの最外側の値が具体化された段階でスレッドの切 替が起きてしまい、不完全なメッセージによるスレッドの切り替えが頻発して しまう。したがって効率のよいスレッド切替を行うためには、切替を行うべき 再帰呼出しを判別する必要がある。

並列環境におけるスレッドスケジューリング

並列環境における実行では、そのプログラムの持つ並列性をいかに抽出するか が重要になる。

スレッド化手法を適用することで、

といったことが起こる。スレッド化手法を並列環境に適用する際には、従来の ゴール単位のスケジューリングに比べて、データ要求メッセージに対する応答 性が低下する可能性がある。このためノード単位の実行速度は向上しているに もかかわらず、この応答性の低下による動的な並行性の低下が、システム全体 としての性能を低下させてしまうことがある。

例えば、あるノードN c上のスレッド T cが他のノードN pに対して要求メッセージを出した場合を考えてみる。 この場合T cは要求したデータが到着するま で中断するが、このときN cに実行可能なス レッドが存在しないと、ノードN cはアイド ル状態になってしまう。この影響を最小限に押さえるためには、データ要求メッ セージに対する返信は可能な限り早く行う必要がある。

そこで本研究では、プログラムの持つ並列性を実行時にできる限り抽出するよ うなスレッドスケジューリング手法を提案、実装する。

静的解析手法

昨年度の研究では、スレッド化のためにモード・型解析 [2,3]を ベースにした依存解析手法を提案した。今年度は、前記の手法を実現するため に、以下の情報を得られるような拡張を行う。

  1. 効率的な動的スレッド切替を行うには、どの再帰呼出しで切替を行うべ きか

  2. 並列環境でのメッセージ応答性を確保するために、どのスレッドを優先 的にスケジュールすべきか


next up previous
Next: 研究の成果 Up: 「KL1のゴールスケジュー リング最適化」に関する成果概要 Previous: 研究の背景と目的



www-admin@icot.or.jp