FAT – Ferramenta para Alocação de Tarefas de Aplicações Distribuídas em Arquiteturas Multiprocessadoras
Abstract
The task allocation of distributed aplications on multiprocessor architectures must choose the suitable processors for task execution, among the minimization of communication and execution costs as well as system load balancing. The assignment process basically depends on the aplication structure and architecture configuration envolved. Therefore, the distributed application or arquitecture designer has a complex work in hands if he/she wishes to get the maximum performance of the application. This work presents the FAT ("Ferramenta para Alocação de Tarefas") system - A Tool for Task Allocation based on an allocation heuristic, for helping the design of distributed applications or the design of multiprocessor architectures. The application scope, the heuristic and the user interface are described in this paper.
References
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
Published
1992-10-26
How to Cite
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.
