平成９年度　委託研究ソフトウェアの提案

(11) 要求駆動スケジューリングによるＫＬ１実装方式の研究

　　
研究代表者： 近山　隆　教授
東京大学　工学系研究科　電子工学専攻


［目次］

  1. 研究の背景
  2. 研究の目的
  3. 研究内容
  4. 研究体制／研究方法
  5. 想定されるソフトウェア成果

［研究の背景］

　並列論理型言語 KL1 は, 実行順序に節選択の判定に必要なデータのフロー から決まるもの以外の制約を持たず, 細粒度並列実行を可能にするセマンティ クスを持っている。このため、プログラムに内在する並列性はプロセッサ数を 大きく上回ることが多く, さまざまなスケジューリング方式が提案されてきて いる。たとえば, 手続き駆動のスケジューリング (PIM, KLIC など), データ 駆動のスケジューリング (上田), スレッド単位のスケジューリング (Tick, 中島など) などがその例である。
　関数型言語においても, Non-strict な言語の場合データフロー以外の実行 順の制約はなく, 実行粒度は KL1 とほぼ同等であるので, さまざまなスケジュー リングが可能である。関数型言語の逐次実装においては遅延評価 (lazy evaluation) が多く試みられており, 並列実行もこれを拡張した形をとること が多い (Multilisp の future など)。逐次計算の場合, 遅延評価はデータが 必要になった時点で計算を開始するため, 最終結果に寄与しない計算を自動的 に除去できるメリットがある。並列処理の場合, 必要になるか定かでない投機 的計算を空きプロセッサで先に始めておくことは, プロセッサの有効利用を促 すが, そのためのプログラムの設計はかなり難しい。要求駆動の枠組を用いて 値の必要度を何らかの形で指定する方式をとれば, プログラマの負担を軽減で きる可能性がある (Osbourne の sponsor model など)。
　並列論理型言語においては関数型と異なり要求が明示的でないことなどから, 要求駆動によるスケジューリング方式はあまり試みられていない。中島らによ る分散メモリ並列処理系での応答優先スケジューリングは, 要求駆動の考え方 を一部採り入れたものと見ることができるが, 基本的なスケジューリングはス レッド単位の手続き駆動であり, 要求駆動を徹底したものではない。

［研究の目的］

　本研究は最終的には効率的な自動資源配分を行なう並列論理型言語処理系の 構成方式を確立することを目的とするが, 本研究においてはそこにいたるひと つのステップとして, 並列論理型言語 KL1 に対する要求駆動に基づくスケジュー リングを用いた処理方式で十分な効率が得られることを確認することを目的と する。上述の研究背景の項で述べたように, 要求駆動方式を用いることによっ て資源配分機構の設計が容易になると考えられるが, それによって実行効率が 大幅に低下したのでは, アプローチ自身の見直しが必要になるので, まず十分 な効率が得られるいことを確認することが提案する研究の目的である。
　関数型言語においては値の生成者と利用者の対応がプログラムの構造と一致 しているため, 要求駆動のスケジューリングはごく素直な方針で実現できる。 論理型言語においては値の生成者と利用者の関係が明示的でなく, 共有変数を 媒介してのものであるため, 要求駆動方式のスケジューリングを単純に実現し ようとすると大きな実行時オーバヘッドを伴うことが予想される。しかし, 近 年研究が進んでいる抽象解釈などを用いたプログラムの静的解析を行なえば, 値の生成利用の関係を把握することが可能である。この結果をスケジューリン グに利用すれば, 実行時オーバヘッドが過大でない要求駆動スケジューリング を行なうことも可能であろうと考えられる。
　提案する研究においては, 静的解析結果に基づいて要求駆動方式スケジュー リングを行なえば, 並列論理型言語に対しても十分な性能が得られることを確 認することを目的とする。そのためには机上の検討のみならず, 実際に試作処 理系を構成し, その上で種々のプログラムを動作させ評価する必要がある。こ れは要求駆動スケジューリングに基づく資源配分機構の研究の前提となる研究 であり, 従来並列論理型言語を適用しにくかった複雑な資源配分を必要とする 応用分野にも適用できるようにするための基礎となるものである。

［研究内容］

　従来並列論理型言語に対して要求駆動方式のスケジューリングを適用する研 究はほとんどなく, 基本的な方式の設計から行なう必要がある。したがって, かなり多岐に渡る研究開発が必要と考えられる。しかしながら, 処理方式の研 究においては実際に処理系を作成してみないと気づきにくい困難を見落とす可 能性があるため, 方式の有効性を実証するには処理系の試作は必須である。
　そこで, 本研究においては以下の内容の研究を行なう予定である。

(1) 単純な要求駆動スケジューリング方式の設計

従来の研究があまりないことから, いきなり高度の最適化を施した処 理方式を設計することは困難と考えられる。そこで, まず比較的単純 な方針に基づいた要求駆動スケジューリング方式の KL1 処理方式を 設計する。これには, まず関数型言語システムへの適用例などを調査 し, それらを並列論理型に対してどのように適用できるかを考え, ま ずもっとも平易な形で要求駆動スケジューリングを行なう方式を設計 する。

(2) 単純な方式のオーバヘッドの解析

言語仕様の違いから, 関数型言語で用いられている方式をほとんどそ のまま並列論理型言語に適用するにはさまざまな問題が生ずるものと 考えられる。したがって, 平易な方式を用いたのでは実行時に大きな オーバヘッドが残る可能性が高い。そこで, 平易な方式に基づいた処 理を行なった場合にどのようなところに実行オーバヘッドが生ずるか を, 小規模のプログラムに対して適用した場合どうなるかを中心に検 討する。

(3) オーバヘッドを削減するための新方式の設計

平易な方式でのオーバヘッドのそれぞれについて, どのようにすれば それらを無くす, あるいは削減することができるかを検討し, 最適化 を施したスケジューリング方式を設計する。現在のところ, 静的解析 によるデータの入出力関係を解析することによって, 複数のゴールの 間のデータフローによる必然的な実行順序関係を抽出し, 複数ゴール をまとめたスレッドを構成, このスレッドを単位とした要求駆動スケ ジューリングすることでオーバヘッドの多くを削減できるのではない かという見通しを持っている。

(4) 新方式のサンプルコーディングによる性能の見極め

設計したスケジューリング方式でどの程度の性能が得られるかを見極 めるために, その方式で想定するオブジェクトコードを作成, 実行時 システムの一部を試作し, ベンチマークプログラムを用いて性能を計 測し, 有効性を確かめる。コンパイラでこうしたコードを生成するた めにはプログラムの静的解析の結果を利用する必要があると考えられ るが, この段階では必要な静的解析が行なえたものと仮定し, それに 基づくオブジェクトコード (C プログラムを想定) を手書きすること によってオブジェクトコードを作成する。

(5) 要求駆動スケジューリング方式に基づく KL1 処理系の構成

設計した方式に基づいて KL1 処理系全体を再構成する。このために は以下の各項目についての研究開発を行なう。

(5-1) 静的解析系の設計と試作
最適化したオブジェクトコードの生成に必要となる解析情報 を抽出する, プログラムの静的解析系の設計と試作。ステッ プ (3) において必要とわかった情報が既存の解析系でも得 られるものであれば, 既存のものを用いる。また, 解析がか なり難しく, 本研究の中で行なうことは時間的困難であるこ とがわかれば, 人手で情報を提供する方式とすることも考え られる。

(5-2) 最適化コンパイラの設計と試作
静的解析情報に基づいて最適化したオブジェクトコードを生 成する, 最適化コンパイラの設計と試作。コード生成が複雑 で最終的な C レベルのコードまでの翻訳系の作成に時間的 に困難を伴う場合は, KL1 レベルのソース → ソースの変換 で可能な範囲の最適化を行なうこととし, このレベルに止め る可能性がある。また, C レベルまでの生成が必須であるよ うな最適化については, コンパイル方針を確立した上で, 実 際の翻訳は人手で行なう方法も考える。

(5-3) 実行時システムの設計と試作
最適化オブジェクトコードを実行する上で必要な実行時シス テムの設計・試作。あらゆる場合に対応できる実行時システ ムの構築には多くの手間を要することから, 本研究の範囲で は例外的な場合にのみ必要な機能を省略し, 良く使われる機 能のみを用いたプログラムが正常実行するのに足る部分のみ を試作することも考えられる。

(6) 試作した KL1 処理系の評価

実際の KL1 プログラムに対して試作した処理系を適用し, どの程度 の性能が得られるかを評価, 設計した方式の実用的な場面における有 効性を検証する。

今回提案する研究の範囲では大規模応用システム等に対しての評価を 行なうことは時間的に困難であることから, 限定された範囲のプログ ラム (ベンチマークプログラムなど) についてのみ行なう。

［研究体制／研究方法］

(1) 研究体制

　　 氏名 所属
研究代表者近山　隆東京大学
研究協力者宇佐　治彦東京大学

(2) 研究の方法

　本研究は効率的な自動資源配分を行なう並列論理型言語処理系の構成方式を 確立することを最終的な目的としているが, そこに至るためには全体として以 下の各ステップを踏んで研究を遂行していくことを考えている。

(1) 単純な要求駆動スケジューリング方式の設計
(2) 単純な方式のオーバヘッドの解析
(3) オーバヘッドを削減するための新方式の設計
(4) 新方式のサンプルコーディングによる性能の見極め
(5) 要求駆動スケジューリング方式に基づく KL1 処理系の構成
(5-1) 静的解析系の設計と試作
(5-2) 最適化コンパイラの設計と試作
(5-3) 実行時システムの設計と試作
(6) 試作した KL1 処理系の評価
(7) 自動資源配分を行なう KL1 システムの設計・試作

　この過程中のステップ (4) において要求駆動スケジューリングでは十分な 性能を得られないことが判明した場合, その後のステップを踏むことには大き な意味がない。また, ステップ (4) で十分な性能が得られることがわかった 場合でも, 処理系の全面的な再構成を伴う全ステップを1年間の研究期間内に すべて完了することは困難である。
　このため, ここに提案する1ヶ年に渡る研究においては, 上述の研究ステッ プのうち (1)〜(4) を行ない, ステップ (5) については:

(5-1) 既存の, あるいは試作する簡便な静的解析系で抽出可能な解析 結果のみを用いる。あるいは, 人手で必要な情報を入力する。
(5-2) KL1 レベルのソース→ソースの変換で可能な範囲のコンパイル を行なう。あるいはコンパイル方針を確立した上で, 実際の翻 訳は人手で行なう。
(5-3) 例外的な場合にのみ必要な実行時システム機能は省略し, 良く 使われる機能のみを用いたプログラムが正常実行するのに足る 部分のみを試作する。

などの方法を用いて作業量を削減する。またステップ (6) については十分大 きな規模の応用システム等に対しての評価を行なうことは時間的に困難である ことから, 限定された範囲のプログラムについてのみ行なう。ステップ (7) については今回提案のの研究の対象外とする。
　本研究はこの方針で研究を遂行し, その成果をまとめて公表する。その後, 本格的な処理系の再構成と評価は, 提案者のグループあるいは他の研究グルー プとの連携などにより, 来年度以降に研究計画を再構成する予定である。

［想定されるソフトウェア成果］

(1)作成されるソフトウェア名称

要求駆動方式 KL1 処理系 (仮称)

(2)そのソフトウェアの機能／役割／特徴

【ソフトウェアの機能】

　基本的に KLIC と同様の機能を提供する。すなわち, 与えられた KL1 プロ グラムを動作させるために必要な諸機能すべてを提供する。ただし, 試作処理 系であるため, 一部機能においては省略があり, すべての KL1 プログラムが 動作するわけではない。また, 本来なら提供すべき機能の一部については, 既 存のソフトウェアを利用する, ユーザが情報を供給するなどの手段で代替する 可能性がある。たとえばプログラムの静的解析系については, 可能なら既存の 解析系を利用, あるいは解析結果にあたる宣言をプログラム中に記述する方針 をとる可能性がある。また, 実行時システムについては KLIC の提供する実行 時システムを一部流用する可能性がある。

【ソフトウェアの役割】

以下のふたつの役割が考えられる。

(a) 通常の KL1 処理系として KLIC に代わるものとして

本研究の終了時点では機能上の制約から KLIC を完全に代替できるだ けの完成度を持つシステムとはなりにくい。また, KLIC を代替でき る対象についても本システムの方が必ず性能上有利であるとは限らな い。しかし, スケジューリング方式が要求駆動方式であることから, 手続き駆動の KLIC と異なり不要な計算を行なわないので, 不要な計 算を含むプログラムも効率良く実行でき, 種々の計算が必須である計 算とそうでない計算が絡み合ってあらかじめ判定が困難であるような 複雑なアルゴリズムの記述にあたって, プログラム構成が容易になる。

(b) 自動資源配分を行なう並列論理型言語システムのベースとして

要求駆動のスケジューリング方式は, 自動的に資源配分を行なうシス テムを設計・試作していく場合に有利であると考えられる。したがっ て, 本システムは自動資源配分を行なう並列論理型言語システムを試 作する場合のベースとして, 手続き駆動方式の KLIC よりも有利であ る場合が多いと考えられる。

【ソフトウェアの特徴】

KLIC とは異なる要求駆動のスケジューリング方式を持つため, 同じプログラ ムに対して KLIC とは異なる順で実行する。上述のようにこれは自動資源配分 を行なう並列論理型システムのベースとして手続き駆動スケジューリング方式 をとる KLIC よりも優れていると考えられる。また, 自由な実行順を持つ並列 論理型言語の研究において, 新たなスケジューリング方式に基づくシステムは, 新たなさまざまな処理方式の実験のベースとしても役立つ。

(3)ソフトウェアの構成／構造

【ソフトウェアの構成】

システムは以下のようなモジュールからなる。

(A) 静的解析系
KL1 プログラムから, 入出力の依存関係など, 要求駆動方式 のスケジューリングのオーバヘッドを除く最適化に必要な情 報を抽出する。

(B) 最適化コンパイラ
KL1 プログラムと静的解析系の出力から, 最適化した要求駆 動方式のオブジェクトコードを生成する。

(C) 実行時システム
最適化した要求駆動方式のオブジェクトコードを実行するの に必要な, 実行時ルーチンの機能を提供する。

このうち (A) については, 検討の結果既存の静的解析系の提供する機能で十 分であることがわかれば, 既存の解析系を利用する可能性がある。

【より大きなシステムの一部として】

このシステムをそのままの形でより大きなシステムの一部として利用すること は考えにくい。しかし, 将来自動資源配分を行なう並列論理型言語システムを 構成する際には, そのベースとして利用できる可能性が高い。

【既存のソフトウェアへの機能付加】

本システムは KLIC を拡張したものではないが, KLIC と同様の機能を提供す るものであり, 実行時システムなどの一部を流用する可能性も高い。このため, KLIC に要求駆動方式スケジューリング機能を付加したものと見ることもでき る。

(4)参考とされたICOTフリーソフトウェアとの関連

KLIC

(5)使用予定言語および動作環境／必要とされるソフトウェア・パッケージ／ポータビリティなど

使用言語: KL1 (解析系, 翻訳系), C (実行時システム)
動作環境: UNIX-ベースの計算機システム
必要ソフトウェア: KLIC
ポータビリティ: KLIC の動作するシステムすべて

(6)ソフトウェアの予想サイズ（新規作成分の行数）

KL1: 解析系, 翻訳系の一部 1,000行程度
　　テストプログラムなど 500行程度
C:　実行時システム 500行程度

(7)ソフトウェアの利用形態

【利用形態】

(a) 通常の KL1 処理系として KLIC に代わるものとして

本研究の終了時点では KLIC を完全に代替するものにはならないと予 想されるが, 一部のプログラムについては要求駆動方式の利点から本 システムが有利になると考えられる。

(b) 自動資源配分を行なう並列論理型言語システムのベース

自動的に資源配分を行なうシステムを設計・試作していく場合に, そ のベースになり, 研究を加速する。

【セールスポイント】

(a) 要求駆動であることから不要な計算を行なわないので, 不要な計算を含 むプログラムも効率良く実行でき, 種々の計算が必須である計算とそう でない計算が絡み合ってあらかじめ判定が困難であるような複雑なアル ゴリズムの記述にあたって, プログラム構成が容易になる。

(b) 自動資源配分を行なう並列論理型言語システムを構築する場合, 従来の 手続き駆動の処理系をベースにするよりもはるかに容易に構築できるも のと期待できる。

(8)添付予定資料

○ 機能仕様書
○ 内部構成とアルゴリズムに関する文書
○ ユーザマニュアル

www-admin@icot.or.jp