A Batch-mode Mapping Algorithm in Highly Heterogeneous Computational Grids using Learning Automata

The computational grid is a new paradigm in parallel and distributed computing systems for realizing a virtual supercomputer over idle resources available in a wide area network like the Internet. Computational Grids are characterized for exploiting highly heterogeneous resources; so, one of the main concerns in developing computational grids is how to effectively map tasks onto heterogeneous resources in order to gain high utilization. Two approaches for mapping the tasks exist, online mode and batch mode. In batch-mode at any mapping event, a batch of tasks is mapped, whereas in online mode only one task is mapped. In this paper, two batch-mode algorithms for task mapping based on learning automata are introduced. To show the effectiveness of the proposed algorithms, computer simulations have been conducted. The results of experiments show that the proposed algorithms outperform three best existing mapping algorithms when the heterogeneity of the environment is very high.

Keywords:

Computational grid , Metatask , Mapping , Learning automata , Heterogeneous computing