分散環境における最悪応答時間の改善を考慮したタスククラスタリング

摘要

In various types of task scheduling in a distributed system, "task clusterin", which aggregates several tasks into one task cluster for assigning it to one machine, can effectively reduce response time. In case that the number of task cluster must be adjusted to the number of machines, several task clusters must be aggregated into larger one. Such an process leads to the increase of response time due to the decrease of the degree of parallelism. In this paper, we propose a task clustering algorithm which imposes a lower bound of total execution size in each task cluster to achieve reduction of response time with decreasing number of task cluster. The experimental results show that our proposed algorithm can effectively reduce response time after scheduling when data transfer time among tasks is large with reduced number of machines.%分散環境においてタスクを実行する場合に実行マシン数を制限しないタスクスケジューリングでは，タスク同士を集約して各マシンへの割り当て単位（タスククラスタ）とするタスククラスタリングが有効である．タスククラスタの数を実行マシン数に合わせる場合，タスククラスタリングの後にタスククラスタ同士をまとめる必要があるが，その一方で実行の並列性が失われ，応答時間が増加する可能性がある．本稿では，実行マシン数を制限するためにタスククラスタリング時にクラスタサイズの下限値を設けた上で，応答時間を抑える手法を提案する．シミュレーションの結果．タスク間のデータ転送時間が大きいほど，少ないマシン数で従来手法よりもスケジュール後の応答時間が抑えられることが分かった．