近年, 計算機の能力向上や低価格化により, 個人で容易に計算機ネットワークを構築でき, Dual Processor技術やHyper-Threading技術など, 並列処理に対する期待が高まっている. また, 新たな並列処理環境としてパソコンやワークステーションをネットワークで接続した計算機クラスタ環境が注目されている. しかし, 計算機クラスタ環境におけるプロセッサ間通信はオーバヘッドが大きいため, 並列プログラムの実行に大きく影響する. また, 通信が同時期に発生すると各通信のパケットが通信路を共有するので通信時間が長くなる. そのため, 計算機クラスタ環境上で効率の良い並列処理を実現するには, 通信オーバヘッドや通信の同時期発生による遅延等を考慮して並列タスクを生成する必要がある.
従来のタスクグラフ・スケジューリング・アルゴリズム(TSA)では, 通信時間はタスク間の通信量から一意に定まる値として扱われ, 通信オーバヘッド処理も考慮されていなかった. そのため, 従来のTSAによる割当て結果を基に計算機クラスタ環境上で並列処理を実現すると, 並列化による実行効率向上が期待通りに得られないという問題がある.
本稿では, 通信状態の解析に基づいたタスク・スケジューリング手法を提案する. 本手法では, 通信オーバヘッド処理や通信の重なりを考慮するために, 並列計算モデルLogPQに基づく環境パラメータを用いて通信状態を解析する. 環境パラメータは通信処理に関するパラメータを中心に構成されており, 送受信オーバヘッド時間や通信路の容量等を表す. 環境パラメータを基に通信状態を解析することで, 従来のTSAで考慮されていなかった通信オーバヘッド処理による遅延時間や通信の同時期発生による遅延時間等が得られる. 解析処理を従来のTSAに応用することで, より実行環境に適した並列タスクを生成できる.
通信処理の解析では, 通信の同時期発生や通信路容量等を考慮するために各通信を一つ一つ順を追って解析する必要がある. また, TSAの種類によっては, 一つのタスクグラフのスケジューリングに対して(タスク数)×(プロセッサ数)回, 通信状態を解析しなければならない. したがって, スケジューリングが進むにつれて解析時間が増加し, スケジューリングに要する時間が膨大になる. しかし, 既に割り当てられたタスク間における通信は, まだ割り当てられていないタスクへの通信が同時期に起こらない限り, 各解析間で変化しない. そこで, 我々は解析間で変化しない状態を保存し利用することで解析時間を短縮する手法を開発した. これにより, 複雑で処理コストの高い解析処理をTSAに組み込むことが可能となり, 通信オーバヘッドや通信の同時期発生を考慮したタスクを生成することが可能となった.