Evaluation Scheme of Tasks Allocation with Metaheuristic Algorithms in Mesh Connected Processors
Wojciech Kmiecik, Leszek Koszałka, Iwona Poźniak-Koszałka, Andrzej Kasprzak · 2011
This paper focuses on applying three meta-heuristic local search algorithms to solve the problem of allocating two-dimensional tasks within a two-dimensional processor mesh in a period of time. The objective is to maximize the level of mesh utilization. To achieve this goal we adapt three algorithms: Tabu Search, Simulated Annealing and Random Search, as well as we design an auxiliary algorithm Dumb Fit and adapt another auxiliary algorithm named First Fit. To measure the efficiency of the algorithms we introduce our own evaluating function called Cumulative Effectiveness and a derivative Utilization Factor. Finally, we implement an experimentation system to test these algorithms on different sets of tasks to allocate. Moreover, a short analysis based on results of series of experiments conducted on three different categories of task sets (small tasks, mixed tasks and large tasks) is presented.