On Simulated Annealing for the Scheduling of Parallel Applications

• Rodrigo Fernandes de Mello USP
• Luciano José Senger UEPG

Resumo

A grid scheduling algorithm inspired on the simulated annealing meta-heuristic (SA) is presented. Guided by predictions about parallel applications resource usage, the algorithm uses SA to find a near-optimal solution which minimizes the overall execution time for scheduling problems on heterogeneous grids. The scheduling algorithm invalidated by simulations, using a model which considers the mainly details about the distributed computers and the jobs,and is compared with other scheduling algorithms. The results allows identify the best SA parameters values, that are the learning rate and the iteration size, for each grid size. We found good results when simulating the scheduling algorithm for grid sizes near by 512 computers. We also observed that the SA computing cost do not jeopardize the scheduling results, which are better when compared with the performance of other scheduling disciplines.

Palavras-chave: Simulated annealing, Application software, Processor scheduling, Scheduling algorithm, Grid computing, High performance computing, Computer simulation, Computational modeling, Concurrent computing, Resource management, parallel computing, parallel application scheduling, simulated annealing