FAT – Ferramenta para Alocação de Tarefas de Aplicações Distribuídas em Arquiteturas Multiprocessadoras
Resumo
A alocação de tarefas de aplicações distribuidas em arquiteturas multiprocessadoras deve escolher os processadores mais adequados para execução das tarefas, visando a minimização do tempo de execução e de comunicação entre outros, bem como o balanceamento de carga no sistema. O processo de alocação depende basicamente da estrutura da aplicação e da configuração da arquitetura envolvidas. Desta forma, o projetista de aplicações distribuidas ou de arquiteturas paralelas possui uma tarefa complexa nas mãos se desejar obter o máximo desempenho na execução da aplicação. Este trabalho apresenta o sistema FAT, uma Ferramenta para Alocação de Tarefas baseada em uma heuristica de alocação, para o auxilio no projeto de aplicações distribuidas ou no projeto de arquiteturas multiprocessadoras. São apresentados o escopo de aplicação, a heuristica de alocação e a interface com o usuário.
Referências
BARAK,A. E SHILOH,A., "A Distributed Load Balancing Policy for a Multicomputer", Software Practice and Experience, n15, september 1985, pp.901-913
BERGER,M.J., BOKHARI,S.H., "A Partitioning Strategy for Nonuniform Problems on Multiprocessors", IEEE Transactions on Computers, vol C36, n5, may 1987, pp.570-580
BERMAN,F., "Experiences with an Automatic Solution to the Mapping Problem", The Characteristics of Parallel Algorithms, MIT Press Series in Scientific Computation, 1987, pp 307-334
BILLIONNET,A. E COSTA,M.C., "Affectation Optimale des Taches et des Fichiers dans un Systeme Distribue: Survey et se", Acordo de Cooperação do Departamento de Engenharia Elétrica da Universidade Católica do Rio de Janeiro e o Governo Francês, Agosto 1987, 50 páginas
BOKHARI,S.H., "On The Mapping Problem", IEEE Transactions on Computers, vol C30, n3, march 1981, pp207-214
BRYANT,R.M. AND AGRE,J.R., "A Queueing Network Approach to the Module Allocation Problem to Distributed Systems", Computers, ACM, september, 1981
CASAVANT,T.L., KUHL,J.G., "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems", IEEE Transactions on Software Engineering, vol14, n2, february 1988, pp.141-154
CHOW,Y.C. E KOHLER,W.H., "Models for Dynamic Load Balancing in Heterogeneous Multiple Processor Systems", IEEE Transactions on Computers, volC28, may 1979, pp.354-361
CHU,W.W., HOLLOWAY,L.J., LAN,M., EFE,K., "Task Allocation in Distributed Data Processing", Computer, n13, november 1980, pp.57-69
CHU,W.W., "Introduction in the Special Issue on Distributed Processing Systems", IEEE Transactions on Computers, volC29, december 1980, pp.1037-1038
EAGER,D.L.,LAZOWSKA,E.D., ZAHORJAN,J., "A Comparison of Receiver-Initiated and Sender-Initiated Dynamic Load Sharing", DEC Systems Research Center, Technical Report, april 1985
EFE,K.,"Heuristic Models of Task Assignment Scheduling in Distributed Systems", Computer, n15, june 1982, pp.50-56
FERGUSON,D.F., LEITNER,G., KAR,G., NIKOLAOU,C.N., "Relocating Processes in a Distributed Computer System", IBM Research Report, RC 11190 (#50429) 6/11/85, 20 pages
GAREY,M.,JOHNSON,D.S., "Computers and Intractability: A Guide to the Theory of NP-completeness", W.H.Freeman and Co., San Francisco, 1979.
GILET, E., "Operational Research", Springer Verlag,1978
GYLYS,V.B. E EDWARDS,J.A., "Optimal Partitioning of Workload for Distributed Systems", in Dig. COMPCON Fall 1976, pp. 353-357
HOUSTIS,C.E., "Distributed Processing Performance Evaluation", Proceedings of the Third International Conference on Data Communication Systems and Their Performance, RJ-Brazil, june 1987, Ed. Campus, pp.391-406
HUANG,H.K., BARBOSA, V.C., "Técnicas para Alocacão Estatica de Tarefas em Sistemas Distribuídos", Programa de Sistemas, Relatório Técnico, setembro 1989, COPPE- UFRJ
HWANG,K., "Advanced Parallel Processing with Supercomputer Arquitectures", Proceedings of the IEEE, vol75, n10, october 1987, pp.1348-1379
IRANI,K.B. & NAJI,A.R., "A Heuristic for Task Scheduling on Large Multiprocessor Systems", Proceedings of the IFIP, WG 10.3 Working Conference on Distributed Processing, Amsterdam, The Netherlands, North Holland, 1988
KIRNER,C., MENDES, S.B.T., "Sistemas Operacionais Distribuídos. Aspectos Gerais e Análise de sua Estrutura", Campus, 1988.
RICHARD MA,P-Y., LEE,E.Y.S., TSUCHIYA,M., "A Task Allocation Model for Distributed Computing Systems", IEEE Transactions on Computers, volC31, n1, jan 82, pp.41-47
NICOL,D.M., REYNOLDS JR,P.F., "Optimal Dynamic Remmaping of Data Parallel Computations", IEEE Transactions on Computers, vol39, n2, february 1990, pp.206-219
PORTO, S.C.S.,MENASCE, D.A., "Uma Metodologia de Construção de Algoritmos Heurísticos para Escalonamento de Tarefas em MPAHs", Anais XI Congresso SBC, 5 a 9 de agosto de 1991, Santos-SP, pp110-125
SHRIVASTAVA,S.K., "Replicated Distributed Processing", Technical Report Series no. 222, University of Newcastle upon Tyne, Computing Laboratory, England, october 1986
STONE,H.S., "Multiprocessor Scheduling with the Aid of Network Flow Algorithm" IEEE Transactions on Software Engineering, vol SE3, january 1977, pp.85-93
THOMASIAN,A. AND BAY,P.F., "Analytic Queueing Networks for Parallel Processing", IEEE Transactions on Computers, vol C35, n12, december 1986, pp 1045-1054
TREVELIN, L.C., "Uma Metodologia para Avaliação de Desempenho de Aplicações de Tempo Real em Arquiteturas Paralelas", Dissertação de Doutorado, Departamento de Informatica, PUC/RJ, 1991
WOLFSTAHL,Y, "Mapping Parallel Programs to Multiprocessors: A Dynamic approach", Parallel Computing, North Holland, n10, 1989, pp45-50
ZHAO,W., RAMAMRITHAM,K., STANKOVIC,J.A., "Scheduling Tasks with resource Requirements in Hard Real-Time Systems", IEEE Transactions on Software Engineering, vol SE13, n5, may 1987, pp.564-577
BERGER,M.J., BOKHARI,S.H., "A Partitioning Strategy for Nonuniform Problems on Multiprocessors", IEEE Transactions on Computers, vol C36, n5, may 1987, pp.570-580
BERMAN,F., "Experiences with an Automatic Solution to the Mapping Problem", The Characteristics of Parallel Algorithms, MIT Press Series in Scientific Computation, 1987, pp 307-334
BILLIONNET,A. E COSTA,M.C., "Affectation Optimale des Taches et des Fichiers dans un Systeme Distribue: Survey et se", Acordo de Cooperação do Departamento de Engenharia Elétrica da Universidade Católica do Rio de Janeiro e o Governo Francês, Agosto 1987, 50 páginas
BOKHARI,S.H., "On The Mapping Problem", IEEE Transactions on Computers, vol C30, n3, march 1981, pp207-214
BRYANT,R.M. AND AGRE,J.R., "A Queueing Network Approach to the Module Allocation Problem to Distributed Systems", Computers, ACM, september, 1981
CASAVANT,T.L., KUHL,J.G., "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems", IEEE Transactions on Software Engineering, vol14, n2, february 1988, pp.141-154
CHOW,Y.C. E KOHLER,W.H., "Models for Dynamic Load Balancing in Heterogeneous Multiple Processor Systems", IEEE Transactions on Computers, volC28, may 1979, pp.354-361
CHU,W.W., HOLLOWAY,L.J., LAN,M., EFE,K., "Task Allocation in Distributed Data Processing", Computer, n13, november 1980, pp.57-69
CHU,W.W., "Introduction in the Special Issue on Distributed Processing Systems", IEEE Transactions on Computers, volC29, december 1980, pp.1037-1038
EAGER,D.L.,LAZOWSKA,E.D., ZAHORJAN,J., "A Comparison of Receiver-Initiated and Sender-Initiated Dynamic Load Sharing", DEC Systems Research Center, Technical Report, april 1985
EFE,K.,"Heuristic Models of Task Assignment Scheduling in Distributed Systems", Computer, n15, june 1982, pp.50-56
FERGUSON,D.F., LEITNER,G., KAR,G., NIKOLAOU,C.N., "Relocating Processes in a Distributed Computer System", IBM Research Report, RC 11190 (#50429) 6/11/85, 20 pages
GAREY,M.,JOHNSON,D.S., "Computers and Intractability: A Guide to the Theory of NP-completeness", W.H.Freeman and Co., San Francisco, 1979.
GILET, E., "Operational Research", Springer Verlag,1978
GYLYS,V.B. E EDWARDS,J.A., "Optimal Partitioning of Workload for Distributed Systems", in Dig. COMPCON Fall 1976, pp. 353-357
HOUSTIS,C.E., "Distributed Processing Performance Evaluation", Proceedings of the Third International Conference on Data Communication Systems and Their Performance, RJ-Brazil, june 1987, Ed. Campus, pp.391-406
HUANG,H.K., BARBOSA, V.C., "Técnicas para Alocacão Estatica de Tarefas em Sistemas Distribuídos", Programa de Sistemas, Relatório Técnico, setembro 1989, COPPE- UFRJ
HWANG,K., "Advanced Parallel Processing with Supercomputer Arquitectures", Proceedings of the IEEE, vol75, n10, october 1987, pp.1348-1379
IRANI,K.B. & NAJI,A.R., "A Heuristic for Task Scheduling on Large Multiprocessor Systems", Proceedings of the IFIP, WG 10.3 Working Conference on Distributed Processing, Amsterdam, The Netherlands, North Holland, 1988
KIRNER,C., MENDES, S.B.T., "Sistemas Operacionais Distribuídos. Aspectos Gerais e Análise de sua Estrutura", Campus, 1988.
RICHARD MA,P-Y., LEE,E.Y.S., TSUCHIYA,M., "A Task Allocation Model for Distributed Computing Systems", IEEE Transactions on Computers, volC31, n1, jan 82, pp.41-47
NICOL,D.M., REYNOLDS JR,P.F., "Optimal Dynamic Remmaping of Data Parallel Computations", IEEE Transactions on Computers, vol39, n2, february 1990, pp.206-219
PORTO, S.C.S.,MENASCE, D.A., "Uma Metodologia de Construção de Algoritmos Heurísticos para Escalonamento de Tarefas em MPAHs", Anais XI Congresso SBC, 5 a 9 de agosto de 1991, Santos-SP, pp110-125
SHRIVASTAVA,S.K., "Replicated Distributed Processing", Technical Report Series no. 222, University of Newcastle upon Tyne, Computing Laboratory, England, october 1986
STONE,H.S., "Multiprocessor Scheduling with the Aid of Network Flow Algorithm" IEEE Transactions on Software Engineering, vol SE3, january 1977, pp.85-93
THOMASIAN,A. AND BAY,P.F., "Analytic Queueing Networks for Parallel Processing", IEEE Transactions on Computers, vol C35, n12, december 1986, pp 1045-1054
TREVELIN, L.C., "Uma Metodologia para Avaliação de Desempenho de Aplicações de Tempo Real em Arquiteturas Paralelas", Dissertação de Doutorado, Departamento de Informatica, PUC/RJ, 1991
WOLFSTAHL,Y, "Mapping Parallel Programs to Multiprocessors: A Dynamic approach", Parallel Computing, North Holland, n10, 1989, pp45-50
ZHAO,W., RAMAMRITHAM,K., STANKOVIC,J.A., "Scheduling Tasks with resource Requirements in Hard Real-Time Systems", IEEE Transactions on Software Engineering, vol SE13, n5, may 1987, pp.564-577
Publicado
26/10/1992
Como Citar
FRANCHIN, Marcelo Nicoletti; PEGORARO, Renê; FERASOLI FILHO, Humberto; TREVELIN, Luis Carlos.
FAT – Ferramenta para Alocação de Tarefas de Aplicações Distribuídas em Arquiteturas Multiprocessadoras. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 4. , 1992, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1992
.
p. 517-535.
DOI: https://doi.org/10.5753/sbac-pad.1992.22732.
