Tratamento de Código Seqüencial no Modelo de Fluxo de Dados
Resumo
Uma das questões ainda não resolvidas eficientemente em multiprocessamento é a determinação do tamanho ou granularidade ideal das tarefas ou processos, com o objetivo de obter desempenho aceitável. A dificuldade decorre do fato de que a granularidade conflita com o volume de sincronizações a serem realizadas. Máquinas multiprocessadoras baseadas no modelo von Neumann exploram paralelismo ao nível de subprograma e comandos e, conseqüentemente, suportam granularidade grossa. Isso implica em um número menor de sincronizações, mas também numa inadequada exploração do paralelismo das aplicações. Máquinas de fluxo de dados, por sua vez, exploram paralelismo ao nível de instrução, suportando, portanto, granularidade fina. Apesar de tratarem o paralelismo mais adequadamente do que as máquinas de von Neumann, as máquinas de fluxo de dados pecam pela necessidade de um grande número de sincronizações. Este artigo trata da redução do número de sincronizações no modelo de fluxo de dados a partir do agrupamento de código seqüencial.
Referências
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.
