Estimated and Observed Performance of Heuristic Algorithrns for Task Scheduling on Heterogeneous Processors
Resumo
Aplicações paralelas com um comportamento regular e bem conhecido, onde as estimativas dos tempos de execução de tarefas são bastante razoáveis, adequam-se bem ao escalonamento estático (em oposição ao escalonamento dinâmico, realizado durante a execução da aplicação). Este é o caso de várias aplicações científicas paralelas. O escalonamento de tarefas em um ambiente heterogêneo, onde os processadores apresentam capacidades diferentes de processamento, é ainda mais complexo do que em um ambiente homogêneo. Escalonamento estático de tarefas baseia-se em dados estimados sobre a aplicação paralela e a arquitetura do sistema e tem recebido freqüentemente um enfoque heurístico. Por isso, uma avaliação de desempenho realística de um algoritmo de escalonamento de tarefas poderá apenas ser completamente realizado se resultados práticos também forem considerados. Neste sentido, o presente trabalho analisa a qualidade de dois algoritmos de escalonamento, um heurístico de construção e outro baseado na metaheurística de busca tabu. Esta análise compara resultados determinísticos com resultados observados do tempo de execução de diversas aplicações paralelas sintéticas em máquinas paralelas reais de acordo com o escalonamento previámente obtido.
Referências
T.G. CRAINIC, M. TOULOUSE, and M. GENDREAU, "Towards a Taxonomy of Parallel Tabu Search Algorithms", Research Report CRT-933, Centre de Recherche sur les Transports, Université de Montréal, 1993.
C.-N. FIECHTER "A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems", Discrete Applied Mathematics 51 (1994), 243-267.
B. GARCIA and M. TOULOUSE, "A Parallel Tabu Search for the Vehicle Routing Problem with Time Windows", Computers and Operations Research 21 (1994), 1025-1033.
M.R. GAREY and D.S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, 1979.
F. GLOVER and M. LAGUNA, "Tabu Search", Chapter 3 in Modem Heuristic Techniques for Combinatorial Problems (C.R. Reeves, cd.), 70-150, Blackwell Scientific Publications, Oxford, 1992.
F. GLOVER, E. TAILLARD, and D. DE WERRA, "A User's Guide to Tabu Search", Annals of Operations Research 41 (1993), 3-28.
J.P. KITAJIMA, B. PLATEAU, P.BOUVRY, and D. TRYSTRAM, "A method and a tool for performance evaluation. A case study: Evaluating mapping strategies", Proceedings of the 1994 Cray Users Group Meeting, Tours, 1994.
D.A. MENASCÉ and V. ALMEIDA, "Cost-Performance Analysis of Heterogeneity in Supercomputer Architectures", Proceedings of the Supercomputing '90 Conference, New York, 1990.
D.A. MENASCÉ and S.C.S. PoRTO, "Processor Assignment in Heterogeneous Parallel Architectures", Proceedings of the IEEE International Parallel Processing Symposium, 186-191, Beverly Hills, 1992.
J. MIGUEL, A. ARRUABARRENA, R. BEIVIDE, and J. A. GREGORIO, "Assessing the performance of the new IBM SP2 communication subsystem", IEEE Parallel & Distributed Technology 4(1996), 12-22.
S.C.S. PORTO and C.C. RIBEIRO, "A Tabu Search Approach to Task Scheduling on Heterogeneous Processors under Precedence Constraints", International Journal of High-Speed Computing 7 (1995), 45-71.
S.C.S. PORTO and C.C. RIBEIRO, "Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints", Journal of Heuristics 1 (1996), 207-233.
S.C.S. PORTO, J.P.W. KITAJIMA, and C.C. RIBEIRO, "Performance Evaluation of a Parallel Tabu Search Scheduling Algorithm", Solving Combinatorial Problems in Parallel (joint workshop with the International Parallel Processing Symposium'91), April1-5 1997, Geneva.
C.R. REEVES, Chapter 1 in Modem Heuristic Techniques for Combinatorial Problems (C.R. Reeves, ed.), Blackwell Scientific Publications, Oxford, 1992.
V.S. SUNDERAM, G. A. GEIST, J. DONGARRA, and R. MANCHEK, "The PVM concurrent computing system: evolution, experiences, and trends", Parallel Computing 20(1994), 531-546.
E. TAILLARD, "Parallel Taboo Search Techniques for the Job Shop Scheduling Problem", ORSA Journal on Computing 6 (1994), 108-117.
