Um Esquema de Escalonamento em Dois Níveis para Jobs Paralelos em uma Rede de Estações de Trabalho
Resumo
Redes de estações de trabalho são um ambiente adequado para processamento paralelo. Ambientes de computação distribuída como o PVM provêm integração entre máquinas heterogêneas a fim de suportar a execução de vários jobs paralelos. Embora estes sistemas permitam que programas paralelos executem num conjunto de estações de trabalho, eles não tratam questões relativas ao gerenciamento e coordenação da distribuição do trabalho pela rede. Este trabalho trata o problema do escalonamento de jobs paralelos numa rede heterogênea de estações de trabalho. Heterogênea significa nesse contexto uma gama de arquiteturas de processadores e um amplo conjunto de jobs paralelos, com graus de paralelismo diferentes e mutáveis, co-existindo com jobs seqüenciais. O artigo consiste de duas partes. A primeira apresenta o projeto e a implementação de um escalonador distribuído para jobs paralelos, cujos objetivos são manter uma carga de trabalho balanceada e reduzir o tempo médio de execução dos jobs. A segunda parte analisa o impacto de jobs paralelos globais na performance de jobs interativos locais e propõe mecanismos para minimizar este impacto.
Referências
Almeida, V.A.F., Árabe, J.N.C., Loures, E.F. and Rímolo, G.S., "Scheduling Parallel Jobs on a Cluster of Heterogeneous Workstations", Proceedings of the High Performance Computing Confercnce '94, Singapore, September 1994, pp. 103-108.
Anderson, T.E., Culler, D.E., Patterson, D.A., and the NOW team, "A Case for NOW (Networks of Workstations)", IEEE Micro, to appear, 1995.
Beguelin, A., Seligman, E. and Starkcy, M., "Dome: Distributed Object Migration Environment", Technical Report CMU-CS-94-153, School of Computer Science, Carnegie Mellon University, May 1994.
Butler, R. and Lusk, E., "User's Guide to the P4 Programming System", Technical Report ANL-92/17, Argonne National Laboratory, 1992.
Carriero, N. and Gelemter, D., "How to Write Parallel Programs: A Guide to the Perplexed", ACM Computing Surveys, pp. 323-357, September 1989.
Casas, J., Konuru, R., Otto, S.W., Prouty, R. and Walpole, J., "Adaptive Load Migration Systems for PVM", Supercomputing '94, Washington DC, November 1994, pp. 390-399.
Eager, D., Lazowska, E. and Zahorjan J., "A Comparison of Receiver Initiated and Sender Initiated Dynamic Load Sharing", Performance Evoluation, Vol. 6, No. 1, April 1986.
Geist, A., Beguelin, A., Dongarra, J., Jiang, W., Manchek, R., and Sunderam, V., PVM: Parallel Virtual Machine A User's Guide and Tutorial for Networked Parallel Computing, The MIT Press, 1994.
Kaplan, J.A. a.nd Nelson, M.L., "A Comparison of Queueing, Cluster and Distributed Computing Systems", Technical Report NASA TM 109025 (Revision 1), NASA Langley Research Center, June 1994, pp. 50.
Kolawa, A., "The Express Programming Environment", Workshop on Heterogeneous Network-Based Concurrent Computing, Tallahassee, FL, October 1991.
Litzkow, M. and Livny, M., "Experience with the Condor Distributed Batch System", IEEE Workshop on Experimental Distributed Systems, Huntsville, AL, October 1990.
MacDougall, M.H., Simulating Computer Systems: Techniques and Tools, The MIT Press, 1987.
Message Passing Interface Forum, "MPI: A Message-Passing Interface Standard", Technical Report CS-94-230, Computer Science Department, University of Tennessee, Knox ville, TN, April 1994
"C-Linda Reference Manual", Scientific Computing Associates, Inc., 1992.
Sevcik K., "Application Scheduling and Processor Allocation in Multiprogrammed Paralell Systems", TR CSRI-282, University of Toronto, 1993.
Siegell, B. and Steenkiste, P., "Automatic Generation of Parallel Programs with Dynamic Load Balancing", Proceedings of the Third International Symposium on High Performance Distributed Computing, IEEE, San Fransisco, August 1994.
Weinrib A. and Shenker S., "Greed is not enough: adaptive load sharing in large heterogeneous systems", Proceedings of the IEEE INFOCOM, 1988.
Zahorjan, J. and McCann, C., "Processor Scheduling in Shared Memory Multiproces sors", Proceedings of ACM SIGMETRICS Conference, May 1990.
