Tratamento de Código Seqüencial no Modelo de Fluxo de Dados
Abstract
One of unanswered questions in multiprocessing is that of determining the ideal size or "granularity" of tasks or processes, aiming at an acceptable machine performance. The difficulties here stem from the fact that granularity conflicts with synchronization requirements. Multiprocessors based on the von Neumann model exploit parallelism at procedure and command level, thus supporting coarse granularity. This requires fewer synchronizations, but does not fully exploit application parallelism. Dataflow machines, on the other hand, exploit instruction-level parallelism, thus supporting fine granularity. Despite there better approach to parallelism, dataflow machines are penalized by the large number of required synchronizations. This paper addresses the issue of reducing the number of required synchronizations in the dataftow model by grouping sequential pieces of code.
References
Ackerman, W. B. Data Flow Languages. IEEE Computer, 15(2):15-25, fev 1982.
Almasi, G. S. & Gottlieb, A. Highly Parallel Computing. Benjamin/Cummings, 1989.
Arvind & Iannucci, R. A. Two Fundamentals Issues in Multiprocessing. In Thakkar, S. S., ed., Selected Reprints on Dataflow and Reduction Architectures, pp. 140-164, 1987.
Backus, J. Can Programming Be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs. Communications of the ACM, 21(8):613-641, ago 1978.
Buehrer, R. & Ekanadham, K., Incorporating Data Flow Ideas into von Neumann Processors for Parallel Execution. IEEE Trans. on Computers, 36(12):1515-1522, dez 1987.
Davis, A. L. & Keller, R. M. Data Flow Program Graphs. IEEE Computer, 15(2):26-41, fev 1982.
Gajski, D. D., Padua, D. A., Kuck, D. J. & Kuhn, R. H. A Second Opinion on Data Flow Machines and Languages. IEEE Computer, 15(2):58-69, fev 1982.
Gajski, D.D. & Pier, J., Essential Issues in Multiprocessor Systems, IEEE Computer, pp. 9-27, jun 1985.
Gao, G. R., Hum, H. H. J. & Wong, Y. Towards Efficient Fine-Grain Software Pipelining. In International Conference on Supercomputing, pp. 369-379, 1990.
Ghezzy, C. & Jazayeri, M. Programming Languages Concepts 2/E Cap. 7, Wiley, 1987.
Grafe, V.G. et al, The εpsilon Dataflow-Processor. In Proceedings of the 16'th Annual International Symposium on Computer Architecture, pp. 36-45, mai 1989.
Gurd, J. & Watson, I. Preliminary Evaluation of a Prototype Dataflow Computer. IFIP, pp. 545-551, 1983.
Gurd, J. R., Kirkham, C. C. & Watson, I. The Manchester Prototype Dataflow Computer. Communications of the ACM, 28(1):34-52, jan 1985.
Iannucci, R. A. Towards a Dataflow/von Neumann Hybrid Architectures. In Proceedings of the 15th Annual International Symposium on Computer Architectures, pp. 131-140, jun 1988.
Lorenzo, P. A. R. Escalonamento de Processos em uma Arquitetura de Fluxo de Dados. Dissertação de Mestrado em elaboração. Departamento de Ciência da Computação, UNICAMP.
McGraw, J. et. al. SISAL: Stream and Iteration in a Single-Assignment Language. Language Reference Manual, version 1.1, Departament of Computer Science, University of Manchester, jul 1983.
Papadopoulos, G. M. & Culler, D. E. Monsoon: An Explicit Token-Store Architecture. In Proceedings of the 17th Annual International Symposium on Computer Architectures, pp. 82-91, 1990.
Sakai, S. et al. An Architecture of a Dataflow Single Chip Processor. In Proceedings of the 16 Annual International Symposium on Computer Architectures, pp. 46-53, mai 1989.
Srini, V. P. An Architectural Comparison of Dataflow Systems. IEEE Computer, 19(3):68-88, mar 1986.
Treleaven, P. C., Brownbridge, D. R. & Hopkins, R. P. Data-Driven and Demand-Driven Computer Architectures. ACM Computing Surveys, 14(1):93-143, mar 1982.
Veen, A. H. Dataflow Machine Architecture. ACM Computing Surveys, 18(4):365-396, dez 1986.
Vegdahl, S. R. A Survey of Proposed Architectures for the Execution of Functional Languages. IEEE Transactions on Computers, C-23(12):1050-1071, dez 1984.
Visoli, M. C. Tramento de Código Seqiiencial no Modelo de Fluxo de Dados. Dissertação de Mestrado em elaboração. Departamento de Ciência da Computação, UNICAMP.
Watson, I. & Gurd, J. R A Practical Dataflow Computer. IEEE Computer, 15(2):51-57, fev 1982.
Almasi, G. S. & Gottlieb, A. Highly Parallel Computing. Benjamin/Cummings, 1989.
Arvind & Iannucci, R. A. Two Fundamentals Issues in Multiprocessing. In Thakkar, S. S., ed., Selected Reprints on Dataflow and Reduction Architectures, pp. 140-164, 1987.
Backus, J. Can Programming Be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs. Communications of the ACM, 21(8):613-641, ago 1978.
Buehrer, R. & Ekanadham, K., Incorporating Data Flow Ideas into von Neumann Processors for Parallel Execution. IEEE Trans. on Computers, 36(12):1515-1522, dez 1987.
Davis, A. L. & Keller, R. M. Data Flow Program Graphs. IEEE Computer, 15(2):26-41, fev 1982.
Gajski, D. D., Padua, D. A., Kuck, D. J. & Kuhn, R. H. A Second Opinion on Data Flow Machines and Languages. IEEE Computer, 15(2):58-69, fev 1982.
Gajski, D.D. & Pier, J., Essential Issues in Multiprocessor Systems, IEEE Computer, pp. 9-27, jun 1985.
Gao, G. R., Hum, H. H. J. & Wong, Y. Towards Efficient Fine-Grain Software Pipelining. In International Conference on Supercomputing, pp. 369-379, 1990.
Ghezzy, C. & Jazayeri, M. Programming Languages Concepts 2/E Cap. 7, Wiley, 1987.
Grafe, V.G. et al, The εpsilon Dataflow-Processor. In Proceedings of the 16'th Annual International Symposium on Computer Architecture, pp. 36-45, mai 1989.
Gurd, J. & Watson, I. Preliminary Evaluation of a Prototype Dataflow Computer. IFIP, pp. 545-551, 1983.
Gurd, J. R., Kirkham, C. C. & Watson, I. The Manchester Prototype Dataflow Computer. Communications of the ACM, 28(1):34-52, jan 1985.
Iannucci, R. A. Towards a Dataflow/von Neumann Hybrid Architectures. In Proceedings of the 15th Annual International Symposium on Computer Architectures, pp. 131-140, jun 1988.
Lorenzo, P. A. R. Escalonamento de Processos em uma Arquitetura de Fluxo de Dados. Dissertação de Mestrado em elaboração. Departamento de Ciência da Computação, UNICAMP.
McGraw, J. et. al. SISAL: Stream and Iteration in a Single-Assignment Language. Language Reference Manual, version 1.1, Departament of Computer Science, University of Manchester, jul 1983.
Papadopoulos, G. M. & Culler, D. E. Monsoon: An Explicit Token-Store Architecture. In Proceedings of the 17th Annual International Symposium on Computer Architectures, pp. 82-91, 1990.
Sakai, S. et al. An Architecture of a Dataflow Single Chip Processor. In Proceedings of the 16 Annual International Symposium on Computer Architectures, pp. 46-53, mai 1989.
Srini, V. P. An Architectural Comparison of Dataflow Systems. IEEE Computer, 19(3):68-88, mar 1986.
Treleaven, P. C., Brownbridge, D. R. & Hopkins, R. P. Data-Driven and Demand-Driven Computer Architectures. ACM Computing Surveys, 14(1):93-143, mar 1982.
Veen, A. H. Dataflow Machine Architecture. ACM Computing Surveys, 18(4):365-396, dez 1986.
Vegdahl, S. R. A Survey of Proposed Architectures for the Execution of Functional Languages. IEEE Transactions on Computers, C-23(12):1050-1071, dez 1984.
Visoli, M. C. Tramento de Código Seqiiencial no Modelo de Fluxo de Dados. Dissertação de Mestrado em elaboração. Departamento de Ciência da Computação, UNICAMP.
Watson, I. & Gurd, J. R A Practical Dataflow Computer. IEEE Computer, 15(2):51-57, fev 1982.
Published
1992-10-26
How to Cite
VISOLI, Marcos C.; CATTO, Arthur J..
Tratamento de Código Seqüencial no Modelo de Fluxo de Dados. 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. 147-158.
DOI: https://doi.org/10.5753/sbac-pad.1992.22708.
