Modelos Computacionais de Fluxo de Dados
Resumo
Modelos de Fluxo de Dados têm sido exaustivamente estudados como uma alternativa para a implementação de máquinas paralelas. Este trabalho descreve os principais modelos: estático e dinâmico, discutindo suas características. Alguns problemas apresentados pelos modelos e implementações realizadas são avaliados.
Referências
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), pag. 613-641, Agosto de 1978.
Miller, R. E.,"A Comparison of Some Theoretical Models of Parallel Computation". IEEE Trans. on Computers, C-22 (8), pag. 710-717, Agosto de 1973.
Treleaven, P. C., Brownbridge, D. R., Hopkins e Richard P., "Data-driven and Demand-driven Computer Architecture", Computing Surveys, 14 (1), pag. 93-143, Margo de 1982.
Mags, G. A., "A Network of Microprocessors to Execute Reduction Languages, Part I", Int. J. of Computer and Info. Sciences, 8 (5), pag. 349-385, 1979.
Magó, G. A., "A Network of Microprocessors to Execute Reduction Languages, Part II", Int. J. of Computer and Info. Sciences, 8 (6), pag. 435-471, 1979.
Watson, I., Watson, P. e Woods, V., "Parallel Data Driven Graph Reduction", Fifth Generation Comp. Arch., Proc. of the 10th World Computer Congress, IFIP 1986, pag. 203-219.
Dennis, J. B., "Models of Data Flow Computation", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 346-354.
Kavi, K. M., Buckles, B. P. e Bhat, U. N., "A Formal Definition of Data Flow Graph Models", IEEE Trans. on Computers, C-35 (11), pag. 940-948, Novembro de 1986.
Dennis, J. B., "Static Data Flow Computation", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 355-363.
Tanenbaum, A. S., "Structured Computer Organization", Prentice-Hall, 1984.
Dennis, J. B., "VIM: An Experimental Computer System to Support General Functional Programming", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 370-381.
Arvind, Kathail, V. e Pingali, K., "A Dataflow Architecture with Tagged Tokens", MIT Laboratory for Computer Science, Int. Report MIT/LCS/TM-174, Setembro de 1980.
Dettner, R., "Dataflow at MIT", Eletronics & Powers, 32 (8), pag. 570-571, Agosto de 1986.
Gostelow, K. P. e Thomas, R. E., "A View of Dataflow", National Computer conference - AFIPS NCC, 48, pag. 1-8, Junho de 1979.
Anderson, J. P., "Program Structures for Parallel Processing", Communications of the ACM, 8 (12), pag. 786-788, Dezembro de 1965.
Karp, R. e Miller, R., "Properties of a Model for Parallel Computations: determinacy, termination, queueing", Siam J. Applied Math., 14 (6), pag. 1390-1411. Novembro de 1966.
Hoare, C. A. R., "An Axiomatic Basis for Computer Programming", Commun tions of the ACM, 12 (10), pag. 576-580. Outubro de 1969.
Dijkstra, E. W., "Guarded Commands, Nondeterminacy and Formal Derivation of Programs", Communications of the ACM, 18 (8), pag. 453-457, Agosto de 1975.
Dijkstra, E. W., "A Discipline of Programming", Prentice-Hall, 1976.
Hansen, P. B., "Distributed Processes: A Concurrent Programming Concept", Communications of the ACM, 21 (11), pag. 934-941, Novembro de 1978.
Hoare, C. A. R., "Communicating Sequential Processes", Communications of the ACM, 21 (8), pag. 666-677, Agosto de 1978.
Kierburtz, R. B. e Silberschatz, A., "Comments on Communicating Sequential Processes", ACM Transactions on Programming Languages and Systems, 1 (2), pag. 218-225, Outubro de 1979.
Tesler, L. G. e Enea, H. J., "A Language Design for Concurrent Processes", AFIPS, Spring Joint Conference, 32, pag. 403-408, 1968.
Chamberlin, D. D., "The "single-assignment" approach to parallel processing", Fall Joint Computer Conference, 39, pag. 263-269, 1971.
Comte, Durrieu, Gelly, Plas e Syre, "Parallelism, Control and Synchronization Expressions in a Single Assignment Language", ACM Sigplan Notices, 13 (1), pag. 25-33, Janeiro de 1978.
Dennis, J. B., "Functional Programming for Data Flow Computation", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 364-369.
Gajski, D. D., Padua, D. A., Kuck, D. J. e Kuhn, R. H., "A Second Opinion on Data Flow Machines and Languages", IEEE Computer, 15 (2), pag. 58-70, Fevereiro de 1982.
Ashcroft, E. A. e Wadge, W. W., "Lucid, a Nonprocedural Language with Iteration", Communications of the ACM, 20 (7), pag. 519-526, Julho de 1977.
Bush, V.J., A Data Flow Implementation of Lucid", M.Sc. Thesis, Dep. of Computer Science, Univ. of Manchester, Outubro de 1979.
McGraw, J. et. al, "SISAL - Streams and Iteration in a Single Assignment Language", Language Reference Manual, ver. 1.0, Lawrence Livermore National Lab.. 1983.
Wadge, W. W. e Ashcroft, E. A., "Lucid, the Dataflow Programming Language", Academic Press, 1985.
Dennis, J. B., "Data Flow Supercomputers", IEEE Computer, 13 (11), pag. 48-56, Novembro de 1980.
Arvind, Gostelow, K. P. e Plouffe, W., "An Asynchronous Programming Language and Computing Machine", Tech. Report, Dep. of Information and Computer Science, Univ. of California, Irvine, Dezembro de 1978.
Gurd, J., Watson, I. e Glauert, J., "A Multilayered Data Flow Computer Architecture", Internal Report, Dep. of Computer Science, Univ. of Manchester, Julho de 1978.
Gurd, J. e Watson, I, "Data Driven System for High Speed Parallel Computing - part 1: Structuring software for parallel execution", Computer Design, 19 (6), pag. 91-100, Junho de 1980.
Gurd, J. e Watson, I., "Data Driven System for High Speed Parallel Computing - part 2: Hardware design", Computer Design, 19 (7), pag. 97-106, Julho de 1980.
Catto, A. J., "Nondeterministic Programming in a Dataflow Environment", Ph.D. Thesis, Dep. of Computer Science, Univ. of Manchester, Junho de 1981.
Watson, I. e Gurd, J., "A Practical Data Flow Computer", IEEE Computer, 15 (2), pag. 51-57, Fevereiro de 1982.
Watson, I. e Gurd, J., "Preliminary Evaluation of a Prototype Dataflow Computer", Proc. of the 9 th World Computer Congress, IFIP 1983, pag. 545-551.
Gurd, J. R., Kirkham, C. C. e Watson, LI, "The Manchester Prototype Dataflow Computer", Communications of the ACM, 28 (1), pag. 34-52, Janeiro de 1985.
Sargeant, J. e Kirkham, C. C., "Stored Data Structures on the Manchester Data Flow Machine", Computer Architecture News, 14 (2), pag. 235-242, Junho de 1986.
Kawakami, K. e Gurd, J. R., "Scalable Data Flow Structure Store", Computer Architecture News, 14 (2), pag. 243-250, Junho de 1986.
Gaudiot, J. L., "Methods for Handling Structures in a Data Flow System", Computer Architecture News, 14 (2), pag.352-358, Junho de 1986.
Gaudiot, J. L., "Structure Handling in Data Flow Systems", IEEE Trans. on Computers, C-35 (6), pag. 489-502, Junho de 1986.
Ruggiero, C. A., "Throttle Mechanisms for the Manchester Dataflow Machine", Tech. Rep. Series, UMCS-87-8-1, Ph.D Thesis, Dep. of Computer Science, Univ. of Manchester, Julho de 1987.
Granski, M., Koren, I. e Silberman, G. M., "The Effect of Operation Scheduling on the Performance of a Dataflow Computer", IEEE Trans. on Computers, C-36 (9), pag. 1019-1029, Setembro de 1987.
Ghosal, D. e Bhuyan, L.W., "Analytical and Architectural Modifications of a Data Flow Computer", Computer Architecture News, 15 (2), pag. 81-89, 1987.
Buehrer, R. e Ekanadham, K., "Incorporating Data Flow Ideas into von Neumann Processors for Parallel Execution", IEEE Trans. on Computers, C-36 (12), pag. 1515-1522, Dezembro de 1987.
Srini, V. P., "An Architectural Comparison of Data Flow Systems", IEEE Computer, 19 (3), pag. 68-88, Março de 1986.
Miller, R. E.,"A Comparison of Some Theoretical Models of Parallel Computation". IEEE Trans. on Computers, C-22 (8), pag. 710-717, Agosto de 1973.
Treleaven, P. C., Brownbridge, D. R., Hopkins e Richard P., "Data-driven and Demand-driven Computer Architecture", Computing Surveys, 14 (1), pag. 93-143, Margo de 1982.
Mags, G. A., "A Network of Microprocessors to Execute Reduction Languages, Part I", Int. J. of Computer and Info. Sciences, 8 (5), pag. 349-385, 1979.
Magó, G. A., "A Network of Microprocessors to Execute Reduction Languages, Part II", Int. J. of Computer and Info. Sciences, 8 (6), pag. 435-471, 1979.
Watson, I., Watson, P. e Woods, V., "Parallel Data Driven Graph Reduction", Fifth Generation Comp. Arch., Proc. of the 10th World Computer Congress, IFIP 1986, pag. 203-219.
Dennis, J. B., "Models of Data Flow Computation", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 346-354.
Kavi, K. M., Buckles, B. P. e Bhat, U. N., "A Formal Definition of Data Flow Graph Models", IEEE Trans. on Computers, C-35 (11), pag. 940-948, Novembro de 1986.
Dennis, J. B., "Static Data Flow Computation", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 355-363.
Tanenbaum, A. S., "Structured Computer Organization", Prentice-Hall, 1984.
Dennis, J. B., "VIM: An Experimental Computer System to Support General Functional Programming", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 370-381.
Arvind, Kathail, V. e Pingali, K., "A Dataflow Architecture with Tagged Tokens", MIT Laboratory for Computer Science, Int. Report MIT/LCS/TM-174, Setembro de 1980.
Dettner, R., "Dataflow at MIT", Eletronics & Powers, 32 (8), pag. 570-571, Agosto de 1986.
Gostelow, K. P. e Thomas, R. E., "A View of Dataflow", National Computer conference - AFIPS NCC, 48, pag. 1-8, Junho de 1979.
Anderson, J. P., "Program Structures for Parallel Processing", Communications of the ACM, 8 (12), pag. 786-788, Dezembro de 1965.
Karp, R. e Miller, R., "Properties of a Model for Parallel Computations: determinacy, termination, queueing", Siam J. Applied Math., 14 (6), pag. 1390-1411. Novembro de 1966.
Hoare, C. A. R., "An Axiomatic Basis for Computer Programming", Commun tions of the ACM, 12 (10), pag. 576-580. Outubro de 1969.
Dijkstra, E. W., "Guarded Commands, Nondeterminacy and Formal Derivation of Programs", Communications of the ACM, 18 (8), pag. 453-457, Agosto de 1975.
Dijkstra, E. W., "A Discipline of Programming", Prentice-Hall, 1976.
Hansen, P. B., "Distributed Processes: A Concurrent Programming Concept", Communications of the ACM, 21 (11), pag. 934-941, Novembro de 1978.
Hoare, C. A. R., "Communicating Sequential Processes", Communications of the ACM, 21 (8), pag. 666-677, Agosto de 1978.
Kierburtz, R. B. e Silberschatz, A., "Comments on Communicating Sequential Processes", ACM Transactions on Programming Languages and Systems, 1 (2), pag. 218-225, Outubro de 1979.
Tesler, L. G. e Enea, H. J., "A Language Design for Concurrent Processes", AFIPS, Spring Joint Conference, 32, pag. 403-408, 1968.
Chamberlin, D. D., "The "single-assignment" approach to parallel processing", Fall Joint Computer Conference, 39, pag. 263-269, 1971.
Comte, Durrieu, Gelly, Plas e Syre, "Parallelism, Control and Synchronization Expressions in a Single Assignment Language", ACM Sigplan Notices, 13 (1), pag. 25-33, Janeiro de 1978.
Dennis, J. B., "Functional Programming for Data Flow Computation", in Control Flow and Data Flow: Concepts of Distributed Programming, NATO ASI Series, Vol. F14, Springer-Verlag, 1985, pag. 364-369.
Gajski, D. D., Padua, D. A., Kuck, D. J. e Kuhn, R. H., "A Second Opinion on Data Flow Machines and Languages", IEEE Computer, 15 (2), pag. 58-70, Fevereiro de 1982.
Ashcroft, E. A. e Wadge, W. W., "Lucid, a Nonprocedural Language with Iteration", Communications of the ACM, 20 (7), pag. 519-526, Julho de 1977.
Bush, V.J., A Data Flow Implementation of Lucid", M.Sc. Thesis, Dep. of Computer Science, Univ. of Manchester, Outubro de 1979.
McGraw, J. et. al, "SISAL - Streams and Iteration in a Single Assignment Language", Language Reference Manual, ver. 1.0, Lawrence Livermore National Lab.. 1983.
Wadge, W. W. e Ashcroft, E. A., "Lucid, the Dataflow Programming Language", Academic Press, 1985.
Dennis, J. B., "Data Flow Supercomputers", IEEE Computer, 13 (11), pag. 48-56, Novembro de 1980.
Arvind, Gostelow, K. P. e Plouffe, W., "An Asynchronous Programming Language and Computing Machine", Tech. Report, Dep. of Information and Computer Science, Univ. of California, Irvine, Dezembro de 1978.
Gurd, J., Watson, I. e Glauert, J., "A Multilayered Data Flow Computer Architecture", Internal Report, Dep. of Computer Science, Univ. of Manchester, Julho de 1978.
Gurd, J. e Watson, I, "Data Driven System for High Speed Parallel Computing - part 1: Structuring software for parallel execution", Computer Design, 19 (6), pag. 91-100, Junho de 1980.
Gurd, J. e Watson, I., "Data Driven System for High Speed Parallel Computing - part 2: Hardware design", Computer Design, 19 (7), pag. 97-106, Julho de 1980.
Catto, A. J., "Nondeterministic Programming in a Dataflow Environment", Ph.D. Thesis, Dep. of Computer Science, Univ. of Manchester, Junho de 1981.
Watson, I. e Gurd, J., "A Practical Data Flow Computer", IEEE Computer, 15 (2), pag. 51-57, Fevereiro de 1982.
Watson, I. e Gurd, J., "Preliminary Evaluation of a Prototype Dataflow Computer", Proc. of the 9 th World Computer Congress, IFIP 1983, pag. 545-551.
Gurd, J. R., Kirkham, C. C. e Watson, LI, "The Manchester Prototype Dataflow Computer", Communications of the ACM, 28 (1), pag. 34-52, Janeiro de 1985.
Sargeant, J. e Kirkham, C. C., "Stored Data Structures on the Manchester Data Flow Machine", Computer Architecture News, 14 (2), pag. 235-242, Junho de 1986.
Kawakami, K. e Gurd, J. R., "Scalable Data Flow Structure Store", Computer Architecture News, 14 (2), pag. 243-250, Junho de 1986.
Gaudiot, J. L., "Methods for Handling Structures in a Data Flow System", Computer Architecture News, 14 (2), pag.352-358, Junho de 1986.
Gaudiot, J. L., "Structure Handling in Data Flow Systems", IEEE Trans. on Computers, C-35 (6), pag. 489-502, Junho de 1986.
Ruggiero, C. A., "Throttle Mechanisms for the Manchester Dataflow Machine", Tech. Rep. Series, UMCS-87-8-1, Ph.D Thesis, Dep. of Computer Science, Univ. of Manchester, Julho de 1987.
Granski, M., Koren, I. e Silberman, G. M., "The Effect of Operation Scheduling on the Performance of a Dataflow Computer", IEEE Trans. on Computers, C-36 (9), pag. 1019-1029, Setembro de 1987.
Ghosal, D. e Bhuyan, L.W., "Analytical and Architectural Modifications of a Data Flow Computer", Computer Architecture News, 15 (2), pag. 81-89, 1987.
Buehrer, R. e Ekanadham, K., "Incorporating Data Flow Ideas into von Neumann Processors for Parallel Execution", IEEE Trans. on Computers, C-36 (12), pag. 1515-1522, Dezembro de 1987.
Srini, V. P., "An Architectural Comparison of Data Flow Systems", IEEE Computer, 19 (3), pag. 68-88, Março de 1986.
Publicado
26/09/1988
Como Citar
BUZATO, L. E.; CALSAVARA, C. M. F. R.; CATTO, A. J..
Modelos Computacionais de Fluxo de Dados. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 2. , 1988, São José dos Campos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1988
.
p. 15-21.
DOI: https://doi.org/10.5753/sbac-pad.1988.23512.
