近年、並列計算環境のハードウェア的な基盤が急速に整備されつつあるのに対 し、ソフトウェアに関する課題は山積しており、特に高い性能を発揮するプロ グラムを容易に開発する技術が強く求められている。そこで、KL1をはじめと する並行／並列型のプログラミング言語が期待されている。これらの言語は、 プログラムの並行性／並列性の記述を言語の基本的プリミティブとして備えて いるため、並列プログラムの記述が容易になる。しかしながら、言語の本質で ある並行性制御にともなうオーバヘッドのためにこれらの並行／並列型言語の 処理システムの性能は十分とは言えない。このオーバヘッドは並行実行単位が 小さすぎることに起因しており、プログラムの粒度をあげることでこのオーバ ヘッドは軽減できる。そこで本研究室では、プログラムをスレッドという静的 に順序付けされたゴール系列に分割することによって、プログラムの粒度を大 きくし、その動的なスケジューリングオーバヘッドを軽減するスレッド化手法 を提案してきた [1]。
スレッド化手法では、コンパイル時に依存解析を行い、ある節のゴール g i,g jに対して、 g iとg jの 間に双方向のデータ依存関係が存在しない場合、これらのゴールの実行順序を 静的に決定する。
各スレッドはそれぞれ途中でサスペンドすることはあっても、内部のゴールの 実行順序が入れ替わることはない。したがって、スレッド中のあるゴールで参 照データが未具体化だった場合には、スレッドごとサスペンドして他のスレッ ドに実行を切り替えても、デッドロックを生じることはない。また、スレッド 内は最適な逐次実行を行うように静的にスケジューリングを行いつつ、さらに、 スレッドを動的にスケジューリングすることで、元のプログラムが有する本質 的な並行動作を実現し、データの依存関係を保つことが可能になる。
本手法を用いることにより、従来のスケジューリング方式で生じる不必要な制 御移行を回避できる。一方、スレッド内ゴールの実行順序を静的に固定できる ことで、スタックを用いた効率的な実装が可能になり、プログラムの実行にお いて、実行・メモリ両効率の向上が達成できる。本研究室における昨年度の成 果である、逐次プログラムに対してこれらのスレッド化を行う処理系が、現在 IFSとして公開されている。
一方、本手法ではスレッド単位の動的スケジューリングを行うが、単純に従来 までのゴール単位でのスケジューリング手法をスレッド単位で使用したのでは、 実行粒度の違いによる様々な問題が生じる。したがって、スレッド化手法の効 果をより発揮するためには、本質的な並行・並列動作にともなうスレッドの中 断に対して、最小のオーバヘッドで対処できる動的なスレッドスケジューリン グ手法を確立する必要がある。