Modelos Computacionais de Fluxo de Dados

  • L. E. Buzato UNICAMP
  • C. M. F. R. Calsavara UNICAMP
  • A. J. Catto UNICAMP

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.
Publicado
26/09/1988
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.