Parallel programs may be represented as a set of interrelated sequential tasks. When multiprocessors are used to execute such programs, the parallel portion of the application can be speeded up by an appropriate allocation of processors to the tasks of the application. Given a parallel application de ned by a task precedence graph, the goal of task scheduling (or processor assignment) is thus the minimization of the makespan of the application. In a heterogeneous multiprocessor system, task scheduling consists in determining which tasks will be assigned to each processor, as well as the execution order of the tasks assigned to each processor. In this work, we apply the tabu search metaheuristic to the solution of the task scheduling problem on a heterogeneous multiprocessor environment under precedence constraints. The topology of the Mean Value Analysis solution package for product form queueing networks is used as the framework for performance evaluation. We show that tabu search obtains much better results, i.e. shorter completion times, improving from 20 to 30% the makespan obtained by the most appropriate algorithm previously published in the literature. Keywords: Parallel processing, task scheduling, heterogenous processors, precedence constraints, makespan minimization, heuristics, tabu search. Programas paralelos podem ser representados por um conjunto de tarefas seq uenciais relacionadas. Quando multiprocessadores são utilizados para executar tais programas, a fra cão paralela da aplica cão pode ser acelerada pela aloca cão apropriada de processadores as tarefas da aplica cão. Dada uma aplica cão paralela de nida por um grafo de precedência, o objetivo do escalonamento de tarefas (ou aloca cão de processadores) e então a minimiza cão do tempo total de sua execu cão. Em um sistema formado por processadores heterogêneos, o escalonamento de tarefas consiste em determinar quais tarefas devem ser alocadas a cada processador, assim como a odem de execu cão das tarefas alocadas ao mesmo processador. Neste trabalho aplica-se a metaheur stica busca tabu a solu cão do problema de escalonamento de tarefas em um ambiente formado por multiprocessadores heterogêneos sob restri cões de precedência. A topologia do grafo de tarefas associada ao algoritmo de an alise do valor m edio para redes de las na forma produto e utilizada como plataforma para avalia cão do desempenho da heur stica. Mostra-se que a busca tabu obt em melhores resultados, isto e, tempos de execu cão menores, reduzindo de 20 a 30% os tempos de execu cão obtidos pelo algoritmo mais apropriado anteriormente publicado na literatura. Palavras-chaves: Processamento paralelo, escalonamento de tarefas, processadores heterogêneos, restri cões de precedência, minimiza cão do tempo de execu cão, heur sticas, busca tabu.
Porto et al. REF apply the tabu search algorithm to the static task scheduling problem in a heterogeneous multiprocessor environment under precedence constraints.
A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Precedence Constraints
Computer Science