Application of R3Q for Medium-Grained Task with Nonuniform Computational Granularity

DOI Web Site

Bibliographic Information

Other Title
  • グリッドタスクスケジューリングアルゴリズムR3Qの不均一な中粒度タスクへの適用

Abstract

Evolutionary Computation (EC) has been recognized to be effective to various optimization problems. However, EC needs a large computational resource to calculate all the solution candidates for all the generations. To provide a required computational resource, grid computing can be a good approach for EC in many applications. In this paper, a computational method of how to implement Evolution Strategies (ES), which is a kind of EC, in a grid computing environment is discussed. In particular, we focus on the latency caused by distributing ES tasks using task scheduling algorithms. Conventionally, list scheduling with round-robin order replication (RR) is adopted to reduce waiting time due to synchronization for grid computing. However, in many cases of EC, RR does not show good performance due to the fact that many real world problems, e. g., the problems that belong to Evolutionary Robotics (ER), are medium-grained tasks, where RR does not work well. Therefore, in this paper, extended RR, round-robin replication remote work queue (R3Q) method is adopted to reduce both the communication overhead and waiting time due to synchronization. Our results show that R3Q can reduce the delay time, which is the sum of synchronous waiting time and communication time, compared to the other two methods. In addition, it is also shown that R3Q is effective to the problems in which the computation time of each task can be variable.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top