Moore’s law reaching its physical limitations has pushed the industry to produce multicore processors. However, programming those processors with an imperative language is not easy since it requires developers to create and synchronize threads. A pure functional language is an adequate tool for this task both from the architectural point of view and from the developer’s. We will show that an architecture can benefit from the implicit parallelism present on functional programs and from the lack of side effects making it easier to parallelize. The developer benefits from functional languages from the superior expressiveness of the language to avoid bugs. In this dissertation, we present the ACQuA architecture, a multicore accelerator created to explore parallelism available in function calls from a pure functional program. ACQuA uses hardware support and a specificallytailored memory organization to minimize the overheads of scheduling, communication, and synchronization. Function calls are placed into a queue and are scheduled to different processing units. The processing units are interconnected and exchange results from function applications. In this work we defined a high level model of the accelerator and how to compile a functional program to it. We also simulated the accelerator and evaluated results, such as speedup, memory usage, and communication overhead of the proposed architecture. We defined the necessary traits of a program to achieve a good speedup on the architecture. On the ideal use case, we can increase the speed up at the same rate we increase the number of processing units in the architecture.

Este trabalho teve como finalidade a implementação de um método para a paralelização parcial de programas, escritos na linguagem funcional, SISAL utilizando as bibliotecas do padrão MPI (Message Passing Interface). Para tal, propusemos a transformação dos programas SISAL através do particionamento do loop paralelo forall, através do método de particionamento slice e a utilização do modelo de implementação do paralelismo SPMD (Single Program Multiple Data) no estilo de programas mestre/escravo. A validação de nossa proposta foi obtida através da realização de testes onde foram comparados os resultados obtidos com os programas originais e os programas com as alterações propostas / This work describes a method for the partial parallelization of SISAL programs into programs with calls to MPI routines. We focused on the parallelization of the forall loop (through slicing of the index range). The generated code is a master/slave SPMD program. The work was validated through the compilation of some simple SISAL programs and comparison of the results with an unmodified version

Este trabalho teve como finalidade a implementação de um método para a paralelização parcial de programas, escritos na linguagem funcional, SISAL utilizando as bibliotecas do padrão MPI (Message Passing Interface). Para tal, propusemos a transformação dos programas SISAL através do particionamento do loop paralelo forall, através do método de particionamento slice e a utilização do modelo de implementação do paralelismo SPMD (Single Program Multiple Data) no estilo de programas mestre/escravo. A validação de nossa proposta foi obtida através da realização de testes onde foram comparados os resultados obtidos com os programas originais e os programas com as alterações propostas / This work describes a method for the partial parallelization of SISAL programs into programs with calls to MPI routines. We focused on the parallelization of the forall loop (through slicing of the index range). The generated code is a master/slave SPMD program. The work was validated through the compilation of some simple SISAL programs and comparison of the results with an unmodified version

Made available in DSpace on 2014-06-12T15:57:39Z (GMT). No. of bitstreams: 2 arquivo3216_1.pdf: 6659432 bytes, checksum: 29ec979f8895b39460684d09a38f9764 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Diferentes linguagens de programação disponibilizam diferentes formas de se implementar uma funcionalidade. Por exemplo, acessar um banco de dados usando C++ ou Python podem ser duas tarefas completamente diferentes. Por outro lado, com o surgimento da Plataforma .NET o acesso a dados com C++ .NET ou IronPython, por exemplo, se tornaram atividades muito parecidas tendo apenas algumas diferenças sintáticas. A Plataforma .NET é distribuída com um conjunto padrão de compiladores para diferentes linguagens como C#, Visual Basic .NET, JScript e J#, todas são orientadas a objetos. Com isso podemos notar uma maior atenção comercial dada ao paradigma de orientação a objetos. No entanto, esse dado não significa que devamos concluir que outros paradigmas não possam ser suportados, pelo contrário e a criação da linguagem F# é um exemplo de que a Plataforma .NET pode dar suporte a diversos paradigmas. Haskell é uma linguagem puramente funcional, não-estrita e fortemente tipada. E por ser uma linguagem de alto poder de expressão e não permitir efeitos colaterais durante sua execução, um programa escrito em Haskell se torna mais fácil de testar, otimizar e paralelizar. No entanto há um grande vazio quando tocamos na questão de ferramentas e APIs para Haskell. Devido ao fato de desenvolvedores usarem uma grande gama de ferramentas e tecnologias, cada qual com diferentes funcionalidades e tipos, tem sido historicamente difícil garantir a interoperabilidade entre as linguagens. No entanto, os compiladores e ferramentas que tem como alvo máquinas virtuais como a Plataforma .NET tiram proveito do suporte a interoperabilidade entre linguagens inerente a esses tipos de sistemas. O presente trabalho propõe um novo esquema de compilação de Haskell para a Plataforma .NET utilizando F# como linguagem intermediária. Tal abordagem nos livra dos inúmeros problemas que a geração de código diretamente para MSIL pode trazer, possibilitando irmos um pouco mais além na questão da interoperabilidade

Made available in DSpace on 2014-06-12T15:59:35Z (GMT). No. of bitstreams: 2 arquivo5187_1.pdf: 772703 bytes, checksum: 4e26836d89a94b44e061ba19cd085a7a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2002 / A teoria das categorias é um ramo relativamente novo da investigação matemática. A idéia básica reside na observação de que diversas áreas da matemática envolvem o estudo ele objetos e mapeamentos entre estes objetos, por exemplo, conjuntos e funções, domínios intervalares e funções contínuas. Tal uniformidade de estrutura pode ser explorada livrando¬-se dos detalhes internos dos objetos, e focalizando-se somente nas funções e nos meios ele combiná-las. Motivados pelo caráter construtivo da teoria das categorias, neste trabalho tem-se como objetivo implementar construções categóricas intervalares através de progra¬mas em H askell

Made available in DSpace on 2014-06-12T15:59:41Z (GMT). No. of bitstreams: 2 arquivo5500_1.pdf: 3962680 bytes, checksum: 4dba3d9b94bbd26eb1eec27b1083b622 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2006 / Tradicionalmente, linguagens funcionais fornecem um grau de abstração superior ao encontrado em outros paradigmas (imperativo, orientado a objetos), o que se manifesta por meio de construções de alto nível como funções de alta ordem, aplicações parciais, polimorfismo paramétrico e, em algumas linguagens, avaliação sob demanda. Entretanto, a utilização do paradigma funcional tem-se restringido basicamente a aplicações acadêmicas. Essa restrição é em parte explicada pela ausência de ambientes de desenvolvimento e APIs que melhorem a produtividade do desenvolvedor na construção de aplicações que fazem uso das tecnologias mais recentes de desenvolvimento Web, computação distribuída, arquitetura orientada a serviços, entre outras. Por outro lado, plataformas como a Java Virtual Machine e, mais recentemente, a Plataforma .NET, disponibilizam uma amplagama de serviços e bibliotecas que satisfazem aos tipos de aplicações supracitados. O ambiente .NET, em particular, destaca-se por suportar múltiplas linguagens, apesar do suporte ser mais amplo a linguagens orientadas a objeto. Dentro desse contexto, surge a oportunidade de portar linguagens funcionais para essa plataforma, permitindo não apenas o acesso aos serviços por ela fornecidos como também uma interoperabilidade natural com outras linguagens. O objetivo deste trabalho é o desenvolvimento de uma implementação da linguagem funcional Hask ell para a Plataforma .NET. Tal implementaçãonão é trivial devido ao g a p semântico que existe entre uma linguagem funcional com avaliação sob demanda e um ambiente como o .NET. F oi desenvolvido um gerador de código capaz de gerar, a partir de um programa Hask ell, código em IL - linguagem assembly suportada pela máquina virtual. Paralelamente, foram conduzidas medições de desempenho do código gerado. Tais medições demonstraram performance razoável para váriosprogramas. Entretanto, a principal contribuição deste trabalho está na disponibilizaçãode uma implementação Hask ell que serve como principal passo rumo µa interoperabilidade com a Plataforma .NET. Além disso, a solução desenvolvida serve como um ambiente de teste e validação de diferentes alternativas de tradução de uma linguagem funcional para as construções encontradas em uma plataforma como .NET

Este trabalho descreve técnicas de análise estática de compilação baseadas na álgebra e programação linear que buscam otimizar a distribuição de loops forall e array em programas escritos na linguagem S/SAL visando à execução em máquinas paralelas de memória distribuídas. Na fase de alinhamento, nós trabalhamos com o alinhamento de hiperplanos onde objetivo é tentar encontrar as porções dos diferentes arrays que necessitam ser distribuídas juntas. Na fase de divisão, que tenta quebrar em partes independente dados e computações, nós usamos duas funções afins, a função de decomposição de dados e a função de decomposição de computação. A última fase, o mapeamento, distribui os elementos de computação nos elementos de processamento usando um conjunto de inequações. As técnicas foram implementadas num compilador SISAL, mas pode ser usada sem mudanças em outras linguagens de associação simples e com a adição de análise de dependências pode ser usada em linguagens imperativas. / This work describes static compiler analysis techniques based on linear algebra and linear programming for optimizing the distribution of forall loops and of array elements in programs written in the SISAL programming language for distributed memory parallel machines. In the alignment phase, attempt is made in the identification of portions of different arrays that need to be distributed jointly by means of alignment of hyperplanes. In the partitioning phase, effort is made in breaking as even possible the computation and pertinent data in independent parts, by means of using related functions: the data decomposition function and the computation decomposition function. The last phase is dedicated to the mapping, which comprises the distribution of the elements of computation into the existing processing elements by means of a set of inequations. These techniques are being implemented in a SISAL compiler, but can be also used without changes by means of other single assignment languages or, with the addition of dependency analysis when using other set of languages, as well.

o objetivo deste trabalho é apresentar a implementação em Java de uma máquina abstrata para execução distribuída de programas funcionais. Mostra-se como as facilidades da linguagem Java foram utilizadas para a implementação de uma linguagem funcional paralela que roda os programas funcionais de forma distribuída em uma rede de computadores. Linguagens Funcionais geralmente são implementadas usando uma máquina abstrata para a execução dos programas. Essas máquinas são usualmente máquinas de redução de grafos. Para se rodar os programas funcionais na máquina virtual Java implementou-se a máquina de redução de grafos G-Machine em Java. Nesta dissertação, apresenta-se inicialmente a implementação da G-Machine em Java, realizada como primeira etapa do trabalho e discute-se a abordagem utilizada para essa implementação. Mostra-se em seguida, como os programas funcionais podem ser compilados para rodar nessa G-Machine. Na segunda etapa do trabalho, modifica-se o sistema implementado para permitir a execução distribuída dos programas funcionais. Finalmente apresenta-se uma avaliação de desempenho e mostra-se possíveis trabalhos futuros. / The objective of this work is to present the implementation in the Java language of an abstract machine for distributed execution of functional programs. We show how the Java facilities were used to implement a parallel functional programming language with a distributed runtime system. Functional Languages are usually implemented using an abstract machine to execute programs. These abstract machines are usually graph reduction machines. To mn the functional programs on the Java Virtual Machine we have implemented the G-Machine graph reduction machine in Java. In this text, we first present the implementation of the G-Machine in J ava, and discuss its implementation. Then we show how this implementation was modified to allow distributed execution of functional programs. Finally some benchmarks, possible future works and conclusions are presented.

o objetivo deste trabalho é apresentar a implementação em Java de uma máquina abstrata para execução distribuída de programas funcionais. Mostra-se como as facilidades da linguagem Java foram utilizadas para a implementação de uma linguagem funcional paralela que roda os programas funcionais de forma distribuída em uma rede de computadores. Linguagens Funcionais geralmente são implementadas usando uma máquina abstrata para a execução dos programas. Essas máquinas são usualmente máquinas de redução de grafos. Para se rodar os programas funcionais na máquina virtual Java implementou-se a máquina de redução de grafos G-Machine em Java. Nesta dissertação, apresenta-se inicialmente a implementação da G-Machine em Java, realizada como primeira etapa do trabalho e discute-se a abordagem utilizada para essa implementação. Mostra-se em seguida, como os programas funcionais podem ser compilados para rodar nessa G-Machine. Na segunda etapa do trabalho, modifica-se o sistema implementado para permitir a execução distribuída dos programas funcionais. Finalmente apresenta-se uma avaliação de desempenho e mostra-se possíveis trabalhos futuros. / The objective of this work is to present the implementation in the Java language of an abstract machine for distributed execution of functional programs. We show how the Java facilities were used to implement a parallel functional programming language with a distributed runtime system. Functional Languages are usually implemented using an abstract machine to execute programs. These abstract machines are usually graph reduction machines. To mn the functional programs on the Java Virtual Machine we have implemented the G-Machine graph reduction machine in Java. In this text, we first present the implementation of the G-Machine in J ava, and discuss its implementation. Then we show how this implementation was modified to allow distributed execution of functional programs. Finally some benchmarks, possible future works and conclusions are presented.

Este trabalho descreve técnicas de análise estática de compilação baseadas na álgebra e programação linear que buscam otimizar a distribuição de loops forall e array em programas escritos na linguagem S/SAL visando à execução em máquinas paralelas de memória distribuídas. Na fase de alinhamento, nós trabalhamos com o alinhamento de hiperplanos onde objetivo é tentar encontrar as porções dos diferentes arrays que necessitam ser distribuídas juntas. Na fase de divisão, que tenta quebrar em partes independente dados e computações, nós usamos duas funções afins, a função de decomposição de dados e a função de decomposição de computação. A última fase, o mapeamento, distribui os elementos de computação nos elementos de processamento usando um conjunto de inequações. As técnicas foram implementadas num compilador SISAL, mas pode ser usada sem mudanças em outras linguagens de associação simples e com a adição de análise de dependências pode ser usada em linguagens imperativas. / This work describes static compiler analysis techniques based on linear algebra and linear programming for optimizing the distribution of forall loops and of array elements in programs written in the SISAL programming language for distributed memory parallel machines. In the alignment phase, attempt is made in the identification of portions of different arrays that need to be distributed jointly by means of alignment of hyperplanes. In the partitioning phase, effort is made in breaking as even possible the computation and pertinent data in independent parts, by means of using related functions: the data decomposition function and the computation decomposition function. The last phase is dedicated to the mapping, which comprises the distribution of the elements of computation into the existing processing elements by means of a set of inequations. These techniques are being implemented in a SISAL compiler, but can be also used without changes by means of other single assignment languages or, with the addition of dependency analysis when using other set of languages, as well.