Dağıtık sistemlerde çok düzeyli görev atama algoritmaları

Task assignment problem deals with assigning tasks to processors in order to minimize the sum of execution and communication costs in a distributed sys tem. In this work, we propose a novel task clustering scheme which considers the differences between the execution times of tasks to be clustered as well as the communication costs between them. We use this clustering approach with proper assignment schemes to implement two-phase assignment algorithms which can be used to find suboptimal solutions to any task assignment prob lem. In addition, we adapt the multilevel scheme used in graph/hypergraph partitioning to the task assignment. Multilevel assignment algorithms reduce the size of the original problem by collapsing tasks, find an initial assignment on the smaller problem, and then projects it towards the original problem by successively refining the assignment at each level. We propose several clus tering schemes for multilevel assignment algorithms. The performance of all proposed algorithms are evaluated through an experimental study where the as signment qualities are compared with two up-to-date heuristics. Experimental results show that our algorithms substantially outperform both of the existing heuristics. Key words: Task assignment, distributed systems, task clustering, multilevel task assignment methods, Kernighan-Lin Heuristic.