Escalonamento de Processos Considerando Atrasos de Comunicação
Resumo
Um dos problemas críticos em multiprocessadores é o escalonamento eficiente de processos, que engloba a partição do programa em módulos e seu endereçamento às unidades de processamento. Problemas como a determinação do tamanho ideal dos módulos e a análise do custo de comunicação ainda não tiveram soluções satisfatórias. Técnicas genéricas não conseguiram grande resultado devido à correlação entre as questões pontos e as arquiteturas alvo. Parâmetros como número de unidades de processamento e características da rede de intercomunicação têm que ser considerados em qualquer proposta de escalonamento. Iniciar os processos o mais cedo possível não garante um bom escalonamento. Esse procedimento, ao contrário do esperado, pode prejudicar o desempenho do sistema, devido à não consideração dos atrasos de comunicação existentes. Este artigo aborda fatores importantes para um escalonamento eficiente. Destacam-se a importância e a necessidade de um tratamento adequado dos atrasos de comunicação envolvidos no processamento paralelo.
Referências
Tilak Agerwala and Arvind. Data Flow Systems. IEEE Software, 15(2):10-13, February 1982.
William B. Ackerman. Data Flow Languages. IEEE Software, 15(2):15-25, February 1982.
Arvind and R. A. Iannucci. Two Fundamentals Issues in Multiprocessing. In S. S. Thakkar, editor, Selected Reprints on Dataflow and Reduction Architectures, pages 140-164, 1987.
R. G. Babb. Parallel Processing with Large-Grain Data Flow Techniques. Computer, pages 55-61, July 1984.
John Backus. Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of ACM, 21(8):613-641, August 1978.
Micah Beck and Jean-Luc Gaudiot. Static Schedulig for Dynamic Dataflow Machines. Journal of Parallel and Distributed Computing, 10(4):279-288, December 1990.
Donald D. Chamberlin. The "Single-assignment" approach to parallel processing. In Fall Joint Computer Conference, pages 263-269, 1971.
Thomas Casavant and Jon G. Kuhl. A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems. IEEE Transactions on Software Engineering, 14(2):141-154, February 1988.
E. G. Coffman Jr. Computer and Job-Shop Scheduling Theory. Wiley-Interscience, New York, 1976.
Yuan-Chieh Chow Chung-Yee Lee, Jing-Jang Hwang and Frank D. Anger. Multiprocessor Scheduling with Interprocessor Communication Delays. Operations Reseach Letters, 7(3):141-147, June 1988.
Subrata Dasgupta. Computer Architecture: a modern synthesis. Wiley, 1989.
Jack B. Dennis. Models of Data Flow Computation. In M. Brov, editor, Control Flow and Data Flow: Concepts of Distributed Programming, pages 345-398. Springer-Verlag Berlin Heidelberg, 1985.
Alan L. Davis and Robert M. Keller. Data Flow Program Graphs. IEEE Software. 15(2):26-41, February 1982.
Hesham El-Rewini and T. G. Lewis. Scheduling Parallel Program Tasks onto Arbitrary Target Machines. Journal of Parallel and Distributed Computing, 9:138-153, 1990.
Michael R. Garey and David S. Johnson. Computer and Intractability; a Guide to the Theory of NP-Ccompleteness. W. H. Freeman and Company, New York, 1979.
D. D. Gajski, D. A. Padua, and D. J. Kuck. A Second Opinion on Data Flow Machines and Languages. IEEE Software, 15(2):58-68, February 1982.
R.L. Graham. Bounds on Multiprocessing Anomalies and Related Packing Algorithms. AFIPS Conf. Proc., 40:205-217, 1972.
Boontee Kruatrachue and Ted Lewis. Grain Size Determination for Parallel Processing. IEEE Software, 5(1):23-32, January 1988.
Boontee Kruatrachue and Ted Lewis. Duplication Schedulinh Heuristic. Parallel research combined reports, Oregan State University Computer Science Department, 1992. Edited by Ted Lewis.
Boontee Kruatrachue and Ted Lewis. Optimal Grain Determination. Parallel research combined reports, Oregan State University Computer Science Department, 1992. Edited by Ted Lewis.
Paulo A. R. Lorenzo. Escalonamento de Processos em uma Arquitetura de Fluxo de Dados. Tese de Mestrado em elaboração. Departamento de Ciência da Computação, UNICAMP.
Vivek Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors. The MIT Press, 1989.
Philip C. Treleaven, David R. Brownbridge, and Richard P. Hopkins. Data-Driven and Demand-Driven Computer Architecture. Computing Surveys, 14(1):93-143, March 1982.
Don Towsley. Allocating Programs Containing Branches Loops Within a Multiple Processor System. IEEE Transaction on Software Engineering, 12(10):1018-1024, October 1986.
J. D. Ullman. NP-Complete Scheduling Problems. Journal of Computer and System Sciences, 10:384-393, 1975.
Harrick M. Vin, Francine Berman, and James S. Mattson Jr. Efficient Data-Driven Evaluation: Theory and Implementation. Journal of Parallel and Distributed Computing, 10(4):367-385. December 1990.
Marcos Cezar Visoli. Tratamento de Código Seqiiencial no Modelo de Fluxo de Dados. Tese de Mestrado em elaboração. Departamento de Ciência da Computação. UNICAMP.
Yoshinori Yamaguchi, Shuichi Sakai, and Yuetsu Kodama. Synchonization Mechanisms of a Highly Parallel Dataflow Machine EM-4. IEICE Transactions. 74(1):204-213, January 1991.
Toshitsugu Yuba, Toshio Shimada, and Yoshinori Yamaguchi. Dataflow Computer Development in Japan. In Proceedings of the 1990 International Conference on Supercomputing, pages 140-147, September 1990.
William B. Ackerman. Data Flow Languages. IEEE Software, 15(2):15-25, February 1982.
Arvind and R. A. Iannucci. Two Fundamentals Issues in Multiprocessing. In S. S. Thakkar, editor, Selected Reprints on Dataflow and Reduction Architectures, pages 140-164, 1987.
R. G. Babb. Parallel Processing with Large-Grain Data Flow Techniques. Computer, pages 55-61, July 1984.
John Backus. Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. Communications of ACM, 21(8):613-641, August 1978.
Micah Beck and Jean-Luc Gaudiot. Static Schedulig for Dynamic Dataflow Machines. Journal of Parallel and Distributed Computing, 10(4):279-288, December 1990.
Donald D. Chamberlin. The "Single-assignment" approach to parallel processing. In Fall Joint Computer Conference, pages 263-269, 1971.
Thomas Casavant and Jon G. Kuhl. A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems. IEEE Transactions on Software Engineering, 14(2):141-154, February 1988.
E. G. Coffman Jr. Computer and Job-Shop Scheduling Theory. Wiley-Interscience, New York, 1976.
Yuan-Chieh Chow Chung-Yee Lee, Jing-Jang Hwang and Frank D. Anger. Multiprocessor Scheduling with Interprocessor Communication Delays. Operations Reseach Letters, 7(3):141-147, June 1988.
Subrata Dasgupta. Computer Architecture: a modern synthesis. Wiley, 1989.
Jack B. Dennis. Models of Data Flow Computation. In M. Brov, editor, Control Flow and Data Flow: Concepts of Distributed Programming, pages 345-398. Springer-Verlag Berlin Heidelberg, 1985.
Alan L. Davis and Robert M. Keller. Data Flow Program Graphs. IEEE Software. 15(2):26-41, February 1982.
Hesham El-Rewini and T. G. Lewis. Scheduling Parallel Program Tasks onto Arbitrary Target Machines. Journal of Parallel and Distributed Computing, 9:138-153, 1990.
Michael R. Garey and David S. Johnson. Computer and Intractability; a Guide to the Theory of NP-Ccompleteness. W. H. Freeman and Company, New York, 1979.
D. D. Gajski, D. A. Padua, and D. J. Kuck. A Second Opinion on Data Flow Machines and Languages. IEEE Software, 15(2):58-68, February 1982.
R.L. Graham. Bounds on Multiprocessing Anomalies and Related Packing Algorithms. AFIPS Conf. Proc., 40:205-217, 1972.
Boontee Kruatrachue and Ted Lewis. Grain Size Determination for Parallel Processing. IEEE Software, 5(1):23-32, January 1988.
Boontee Kruatrachue and Ted Lewis. Duplication Schedulinh Heuristic. Parallel research combined reports, Oregan State University Computer Science Department, 1992. Edited by Ted Lewis.
Boontee Kruatrachue and Ted Lewis. Optimal Grain Determination. Parallel research combined reports, Oregan State University Computer Science Department, 1992. Edited by Ted Lewis.
Paulo A. R. Lorenzo. Escalonamento de Processos em uma Arquitetura de Fluxo de Dados. Tese de Mestrado em elaboração. Departamento de Ciência da Computação, UNICAMP.
Vivek Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors. The MIT Press, 1989.
Philip C. Treleaven, David R. Brownbridge, and Richard P. Hopkins. Data-Driven and Demand-Driven Computer Architecture. Computing Surveys, 14(1):93-143, March 1982.
Don Towsley. Allocating Programs Containing Branches Loops Within a Multiple Processor System. IEEE Transaction on Software Engineering, 12(10):1018-1024, October 1986.
J. D. Ullman. NP-Complete Scheduling Problems. Journal of Computer and System Sciences, 10:384-393, 1975.
Harrick M. Vin, Francine Berman, and James S. Mattson Jr. Efficient Data-Driven Evaluation: Theory and Implementation. Journal of Parallel and Distributed Computing, 10(4):367-385. December 1990.
Marcos Cezar Visoli. Tratamento de Código Seqiiencial no Modelo de Fluxo de Dados. Tese de Mestrado em elaboração. Departamento de Ciência da Computação. UNICAMP.
Yoshinori Yamaguchi, Shuichi Sakai, and Yuetsu Kodama. Synchonization Mechanisms of a Highly Parallel Dataflow Machine EM-4. IEICE Transactions. 74(1):204-213, January 1991.
Toshitsugu Yuba, Toshio Shimada, and Yoshinori Yamaguchi. Dataflow Computer Development in Japan. In Proceedings of the 1990 International Conference on Supercomputing, pages 140-147, September 1990.
Publicado
26/10/1992
Como Citar
LORENZO, Paulo A. R.; CATTO, Arthur J..
Escalonamento de Processos Considerando Atrasos de Comunicação. 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. 537-545.
DOI: https://doi.org/10.5753/sbac-pad.1992.22733.
