Application of R3Q for Medium-Grained Task with Nonuniform Computational Granularity
Masashi Oiso, Toshiyuki Yasuda, Kazuhiro Ohkura · TRANSACTIONS OF THE JAPAN SOCIETY OF MECHANICAL ENGINEERS Series C · 2012
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.