A computacao paralela, empregada no meio cientifico para resolucao de problemas que de- mandam grande poder computacional, teve nos ultimos anos o surgimento de um novo tipo de comunicacao entre instancias do paralelismo. Trata-se da Comunicacao Unilateral (CUL), onde somente uma instancia realiza a operacao de transferencia de informacoes, e esta ocorre em segundo plano, ao contrario da Comunicacao Bilateral (CBL), onde uma instancia envia a informacao e a outra recebe. Neste contexto se buscou analisar os beneficios que a CUL agrega ao paralelismo de um programa que se utiliza de uma grade nao estruturada em me- moria. Duas formas de apoio ao paralelismo foram utilizadas: uma biblioteca, a \"Message Passing Interface\" (MPI) (especificamente a sua parte que descreve a CUL), e uma extensao a linguagem Fortran, o Coarray Fortran (CAF). A semantica do MPI CUL e mais complexa que a do CAF, mas a do CAF e mais restritiva. Para analisar a semantica e desempenho da CUL foi realizada uma ambientacao utilizando MPI CUL e CAF no paralelismo de um programa simples, denominado jogo da Vida (Game of Life), com grade estruturada e com otimo desempenho paralelo atraves do MPI CBL. Na programacao o MPI CUL se mostrou verborragico (aumento do numero de linhas de codigo) e complexo, principalmente quando se utiliza um controle refinado de sincronismo entre as imagens. Ja o CAF reduziu o nu- mero de linhas de codigo (entre 20% e 40%), e o sincronismo e muito mais simples. Os resultados mostraram uma piora no desempenho no caso do MPI CUL, mas para o CAF o desempenho absoluto foi melhor que a implementacao original ate o numero de nucleos de processamento que compartilham a mesma memoria. Para grades nao estruturadas se utilizou o Ocean Land Atmospheric Model (OLAM), um modelo de simulacao do sistema terrestre com grade baseada em prismas triangulares, paralelizado atraves de MPI CBL. A implementacao da comunicacao por MPI CUL na estrutura do paralelismo existente mos- trou que esta semantica possui alguns pontos que podem prejudicar a programacao, como o tratamento da exposicao de memoria (cada instancia tem uma memoria exposta de tamanho diferente) e como e realizado o sincronismo entre as instancias. Em termos de desempenho as curvas de speed-ups mostraram que o MPI CUL prejudicou o OLAM independentemente da implementacao das bibliotecas ou do equipamento utilizado, com reducao de pelo menos 20% no speed-up para sete ou mais processadores. Assim como no jogo da Vida o MPI com comunicacao unilateral penalizou o desempenho. / Parallel computing is used to solve many scientific problems that demand intensive compu- ting power. Recently a new paradigm of communication between instances of the parallelism has appeared, called the one-sided communication (OSC), where only one instance performs the operation of information transfer, occurring in the background, as opposed to the two- sided communication (TSC), where one instance sends the information and the other receives it. In this context we analyze the benefits that OSC aggregates to the parallelism of a pro- gram that uses an unstructured grid in memory. Two OSC implementations were used: the \"Message Passing Interface\" (MPI) library (specifically the part that describes OSC), and Coarray Fortran (CAF), an extension of the Fortran language. The semantics of MPI OSC is more complex than that of CAF, but the semantics of CAF is more restrictive. To analyze the semantics and performance of OSC a simple program called Game of Life is used in a structured grid, giving very good parallel performance through MPI TSC. The MPI OSC program was verbose (increase in the number of lines of code) and complex, especially when using a more refined control to synchronize the parallel instances. On the other hand, CAF has reduced the number of lines of code (between 20% to 40%), and the synchronization is very simple. The results showed a worse performance in the case of MPI OSC, but for the CAF the absolute performance was better than the original implementation up to the number of processor cores that share the same memory. For unstructured grids we used the Ocean Land Atmospheric Model (OLAM), an earth simulation model on a grid based on triangular prisms, and parallelized with MPI TSC. The implementation with MPI OSC showed that this semantics has some points that may affect the coding of the communication structure, as in the treatment of memory exposure (each instance has an exposed memory of different size) and the way to treat the synchronization among instances. In terms of performance, the speedup curves showed that MPI OSC penalized OLAM, independently of the MPI implementation or the equipment used, with a reduction of at least 20% in speedup for seven or more processors. As in the Game of Life, MPI OSC degrades the performance.

Made available in DSpace on 2016-04-27T17:27:03Z (GMT). No. of bitstreams: 1 Sanqueilo de Lima Santos.pdf: 1226141 bytes, checksum: a8e18778521ed5cb86817b8537850de3 (MD5) Previous issue date: 2013-04-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The effort to go through the various forms of intentionality, in the constitution of objects of nature and spirit, is the goal for which they were produced in the complex descriptions Ideas II (1913 - 1922). The concept of regional ontology, which is treated Ideas I (1913) from the standpoint of its more general principles, is applied to particular problems in Ideen II, to demonstrate that reality and the characteristic features of each kind of objectivity (natural and spiritual) depend on intentionality. This is essential both to be donated, and to be recognized in its own ontological status. Our work focused on spiritual objectivity, and found himself thus engaged with themes that are present in the Cartesian Meditations (1931). The approach of spiritual objectivity depends on the exposure of the distinction between causality and motivation. Given the importance of the second, also requires more detailed analysis of the concepts of the spiritual world, empathy, intersubjectivity and expression. In the constitution of spiritual objectivity, its actually admits "predicates meaning" unlike natural objectivity. And our hypothesis is that the level of transcendental spirit, stated by Husserl, can only be sustained by a sense of ego, apparently secondary, whose predispositions of consciousness has essential debt with the body (Leib) and attitudes of parallelism / O esforço de percorrer as várias formas de intencionalidade, presentes na constituição dos objetos da natureza e do espírito, é a meta para a qual foram produzidas as complexas descrições em Ideias II (1913 1922). O conceito de ontologia regional, que é tratado Ideias I (1913) do ponto de vista dos seus princípios mais gerais, é aplicado a problemas particulares em Ideen II, no sentido de demonstrar que a realidade e os traços característicos de cada espécie de objetividade (natural e espiritual) dependem da intencionalidade. Essa é indispensável tanto para serem doados, quanto para serem reconhecidos em seu estatuto ontológico próprio. O nosso trabalho se concentrou na objetividade espiritual, e se viu, dessa forma, comprometido com temas que estão presentes nas Meditações Cartesianas (1931). A abordagem da objetividade espiritual depende da exposição da distinção entre causalidade e motivação. Pela importância da segunda, também exige a análise mais detalhada das noções de mundo espiritual, empatia, intersubjetividade e expressão. Na constituição das objetividades espirituais, a sua realidade admite predicados de significação , ao contrário da objetividade natural. E nossa hipótese é a de que o nível transcendental do espírito, afirmado por Husserl, só se sustenta mediante uma noção, aparentemente secundária, de ego, cujas predisposições de consciência contém uma dívida essencial com o corpo-próprio (Leib) e com o paralelismo das atitudes

Este trabalho apresenta um modelo de escalonamento hierárquico para exploração do paralelismo E Independente e do paralelismo OU na programação em lógica. O modelo utiliza informações de granulosidade geradas pelo GRANLOG (Granularity Analyzer for Logic Programming) para o auxílio ao escalonamento. Um estudo detalhado de ambientes de programação em lógica explorando o paralelismo é apresentado. A partir deste, é feita uma comparação destacando as principais características de cada um. O escalonamento em linhas gerais também é descrito e uma enfâse maior é dada ao escalonamento dinâmico. As principais vantagens e desvantagens de cada escalonador são mostradas. O modelo proposto recebe o nome de DSLP – Distributed Scheduler for Logic Programming e realiza o escalonamento em duas fases. Inicialmente é executada a Fase OU, na qual todo paralelismo OU é explorado. Em seguida, é iniciada a Fase E onde ocorre a exploração do paralelismo E Independente. A estratégia de escalonamento proposta, utiliza informações de complexidade do GRANLOG para determinar o trabalho a ser exportado, bem como o nível de sobrecarga dos nodos. Para validação do trabalho, um protótipo utilizando o ambiente Parallel Virtual Machine foi implementado. O protótipo é um simulador de programas Prolog e implementa a fase E de escalonamento. / This work presents a hierarchical scheduling model for exploration of the Independent AND parallelism and OR parallelism in logic programming. The model uses granularity information generated by GRANLOG (Granularity Analyzer for Logic Programming) to aid the scheduler. A detailed study of parallel logic programming environments is presented. Starting from this, it is made a comparison highlighting the main characteristics of each one. Scheduling in general is also described and the dynamic scheduling is pointed out. The main advantages and disadvantages of each scheduler are shown. The proposed model receives the name of DSLP – Distributed Scheduler for Logic Programming and it accomplishes the scheduling in two phases. Initially the OR Phase is executed and the whole OR parallelism is explored. Soon after, it is initiate the AND Phase with the exploration of the Independent AND parallelism. The scheduling strategy proposed uses complexity information generated by GRANLOG to determinate the task to be exported, as well as the nodes overloaded level. For work validation, a prototype using the Parallel Virtual Machine was implemented. The prototype is a Prolog simulator and it implements the scheduling AND phase.

Este trabalho a dedicado ao estudo da exploração de paralelismo OU na programação em lógica com restrições em ambientes distribuídos. A programação em lógica, cuja linguagem mais significativa 6 Prolog, tem como premissa a utilização da lógica de predicados como linguagem computacional. A programação em lógica com restrições (CLP) é uma extensão da programação em lógica, onde busca-se a eficiência e a possibilidade de executar novas classes de problemas. Variáveis em CLP podem pertencer a domínios específicos como, por exemplo, reais ou booleanos. O principal conceito introduzido é a restrição. Restrição a uma equação que representa uma certa informação sobre uma variável e a sua relação com outras variáveis. o uso de restrições foi proposto para diminuir o espaço de busca na execução dos programas. Apesar de mais eficientes que a programação em lógica clássica, para algumas aplicações reais o desempenho das linguagens CLP ainda é insatisfatório. Por isso, é necessário buscar alternativas novas como a execução em paralelo. A exploração de paralelismo implícito em programas em 1ógica já demonstrou resultados promissores. Vários modelos foram propostos e implementados utilizando as duas principais fontes de paralelismo — E e OU — de forma isolada ou combinada. O objetivo principal desse trabalho é apresentar o modelo pclp(FD) de exploração de paralelismo OU multi-sequêncial para um ambiente com memória distribuída. O modelo pclp(FD) caracteriza-se pela existência de vários trabalhadores, cada um deles possuindo uma maquina abstrata completa. O escalonamento de tarefas a realizado por uma política dinâmica e distribuída. Uma tarefa em pclp(FD) equivale a um ponto de escolha e a um contexto de execução. O contexto de execução a formado por porções da pilha do exportador. Para que o importador tenha acesso ao contexto de execução utiliza-se a cópia incremental, que a uma das varias técnicas possíveis. Cada trabalhador possui a sua própria copia privada das pilhas de execução. A cópia caracteriza-se pelo envio das pilhas de execução do exportador para uma área privada do importador. A cópia incremental é uma técnica mais otimizada que verifica a existência de partes comuns entre os trabalhadores, copiando apenas as panes novas. O algoritmo de cópia incremental proposto no modelo a feito sem nenhuma centralização de informação do estado das pilhas. O projeto e implementação de um prot6tipo para esse modelo, utilizando a linguagem clp(FD), que implementa CLP sobre domínios finitos, permitirá uma analise das vantagens e desvantagens do modelo proposto. Os resultados obtidos com a análise servirão de base para trabalhos futuros, visando aprimorar a implementação e o modelo. / This work is dedicated to the study of the exploration of OR parallelism in Constraint Logic Programming for distributed environment. Logic Programming, which the most meaningful language is Prolog, has as premise the use of the logic of predicates as computational language. Constraint Logic Programming or CLP is an extension of the logic programming, where efficiency and the possibility to execute new kinds of problems are searched. A variable in CLP can belong to specific domains as, for example, Real or Boolean. The main concept introduced is the constraint. Constraint is an equation that represents a certain information over a variable and its relation with others variables. The use of constraints was proposed to decrease search space in the program execution. Although it is more efficient than classic logic programming, for some real applications, the performance of CLP languages still is unsatisfactory. So, it is necessary to search alternatives as parallel execution. The exploration of implicit parallelism in programs in logic has already demonstrated promising results. Several models have been proposed and implemented using the two main sources of parallelism - AND and OR — in an isolated or combined form. The main objective of this work is to present the pclp(FD) model of exploration of multi-sequential OR parallelism for a distributed memory environment. The pclp(FD) model is characterized for the existence of some workers, each one of them possessing a complete abstract machine. Task scheduling is executed by one dynamic and distributed policy. A task in pclp(FD) is equivalent to a choice point and an execution context. Execution context is formed by portions of the stack of the exporter. So that importer has access to the execution context, it uses incremental copy, which is one of the several possible techniques. The copy is characterized for sending execution stacks of the exporter to a private area of the importer, that is, each worker possesses its private copy of the execution stacks. The incremental copy is a more optimized technique that verifies the existence of common parts between workers, copying only the new ones. The incremental copy algorithm proposed in the model executes without centralized information of the state of the stacks. A prototype project and implementation for this model, using the language clp(FD), that implements CLP over finite domains, will allow an analysis of advantages and disadvantages of the considered model. The results gotten with the analysis will serve of base for future works, aiming to improve the implementation and the model.

The Task Scheduling Paradigm is a general technique for leveraging fine and coarse grain parallelism from applications of several domains with minimum impact on code readability, relying on the automatic inference of data dependencies among tasks. The performance of Task Parallel applications is correlated with the speed at which the underlying Task Scheduling System is able to detect such dependencies, something that is critical for fine-granularity workloads, which cannot amortize scheduling overheads with long periods of useful computation. That being the case, several groups have recently been developing FPGA-accelerated Task Scheduling Systems architectures where a software Task Scheduling Runtime is able to offload its bookkeeping computations to an FPGA-based accelerator with the goal of efficiently scheduling fine-grained tasks to CPU cores. Even though these FPGA-accelerated systems offer substantial gains over the software-only baseline, it is also true that FPGA-CPU communication bottlenecks prevent such designs from handling scenarios with either large number of cores or very fine-grained tasks. With that in mind, we proposed the implementation of a Native Task Scheduling System that is, a processor with native support for task scheduling embedded into its architecture with the goal of substantially reducing these overheads. More specifically, this project aimed at embedding the HW logic of Picos, a mature Task Scheduling Accelerator developed by the Barcelona Supercomputing Center (BSC), into Rocket Chip, an open-source, silicon-proven, multi-core implementation of RISC-V. The ISA of the resulting system provides special instructions for Task Applications to interact with this Task Scheduling Logic, ruling out all FPGA-CPU communication latencies. To evaluate the prototype performance, we both (1) adapted Nanos, a mature Task Scheduling runtime, to benefit from the new task-scheduling-accelerating instructions; and (2) developed Phentos, a new HW-accelerated light weight Task Scheduling runtime. Our experiments show that task parallel programs using Nanos-RV the Nanos version ported to our system are on average 2.13 times faster than those being serviced by baseline Nanos, while programs running on Phentos are 13.19 times faster, considering geometric means. Using eight cores, Nanos-RV is able to deliver speedups with respect to serial execution of up to 5.62 times, while Phentos produces speedups of up to 5.72 times. / Paralelismo por Tarefas é uma técnica genérica de extração de paralelismo de granularidade arbitrária aplicável a programas de vários domínios, com mínimo impacto sobre legibilidade de código, baseada na inferência automática de dependências de dados entre tarefas. O desempenho de aplicações paralelas baseadas nesse paradigma depende da velocidade com a qual o runtime de Paralelismo por Tarefas que lhe dá suporte é capaz de detectar tais dependências, fato que é ainda mais crítico para aplicações envolvendo tarefas de granularidade fina, já que nesse cenário o overhead de escalonamento não é amortizado por períodos significativamente maiores de computação útil. Recentemente, diversos grupos têm desenvolvido Sistemas de Suporte a Paralelismo por Tarefas acelerados por FPGAs, os quais são capazes de fazer offload das operações de inferência de dependências para um acelerador em FPGA de modo a melhorar o seu desempenho ao lidar com tarefas de granularidade fina. Por outro lado, ainda que esses sistemas acelerados por FPGA apresentem ganhos substanciais com relação às alternativas baseadas puramente em software, o desempenho dessas soluções é prejudicado por gargalos de comunicação entre a CPU e a FPGA, os quais limitam a capacidade desses sistemas de lidar com cenários envolvendo grande número de núcleos ou tarefas muito finas. Motivados por isso, implementamos um Sistema de Suporte Nativo a Paralelismo por Tarefas isto é, um processador com suporte arquitetural nativo a Paralelismo por Tarefas com o objetivo de reduzir consideravelmente tais overheads de comunicação. Mais especificamente, integramos a lógica em hardware do Picos, um acelerador de Paralelismo por Tarefas desenvolvido pelo Barcelona Supercomputing Center (BSC), ao Rocket Chip, uma implementação multi-core de código livre do RISC-V desenvolvida pela Universidade da Califórnia, Berkeley. O sistema resultante contém em sua ISA (Instruction Set Architecture) as instruções necessárias para que aplicações baseadas em tarefas possam interagir diretamente com essa lógica de escalonamento, minimizando os overheads associados ao uso de runtimes intermediários e eliminando toda a latência de comunicação FPGA-CPU. Para avaliar a performance do protótipo que então se construiu, nós tanto (1) adaptamos o runtime de escalonamento de tarefas Nanos para que ele pudesse ser acelerado pelas novas instruções de escalonamento de tarefas, quanto (2) criamos um novo runtime leve de escalonamento de tarefas a que demos o nome de Phentos. Nossos experimentos mostram que programas baseados em paralelismo por tarefas usando o runtime Nanos-RV a versão do runtime Nanos com suporte ao sistema que produzimos são executados em média 2,13 vezes mais rapidamente do que versões dos mesmos programas utilizando a versão básica do Nanos, enquanto programas executados com o Phentos são em média 13,19 vezes mais rápidos do que suas versões correspondentes baseadas na mesma versão básica do Nanos. Tais valores médios correspondem à média geométrica dos conjuntos de dados pertinentes. Usando oito núcleos, Nanos-RV entrega ganhos de desempenho com relação a execuções seriais de até 5,62 vezes, enquanto Phentos entrega ganhos de até 5,72 vezes.

En esta tesis se estudia el modelo de ejecución de los procesadores multithreaded especulativos así como los requisitos necesarios para su implementación. El modelo de ejecución se basa en la inserción de instrucciones de spawn dentro del código secuencial. De esta manera, la ejecución de un programa en estos procesadores es similar a cualquier otro hasta que se encuentra con un punto de spawn. Entonces, se crea un nuevo thread especulativo en el punto indicado por la instrucción de spawn y ambos threads se ejecutan en paralelo. Cuanto el thread creador llega al punto inicial del thread especulativo, se ha de verificar si la especulación ha sido correcta. En ese caso, el contexto del thread no especulativo se gradúa y se libera para uso futuro de más threads especulativos. En caso de que la verificación no haya sido correcta, se recupera el estado correcto. En este modelo de ejecución siempre hay un thread no especulativo y puede haber múltiples threads especulativos.Para soportar este modelo de ejecución, se necesita: i) hardware capaz de crear y gestionar threads especulativo y ii) un mecanismo de particionado para dividir los programas en threads especulativos. Se han estudiado varias plataformas para gestionar threads de forma concurrente. Por un lado, los procesadores clustered se benefician de menores retardos, menor potencia consumida y una menor complejidad aunque las latencias de comunicación sean mayores. Por otro lado, las arquitecturas centralizadas se benefician del hecho de compartir recursos y menor latencia de comunicación, pero la complejidad del hardware es mucho mayor. En cualquier caso, el hardware ha de ser capaz de ejecutar múltiples threads simultáneamente con el inconveniente de que algunos valores van a tener que compartirse mientras que otros son copias privadas. Es decir, el procesador deberá ser capaz de gestionar múltiples versiones de un mismo registro o posición de memoria para cada uno de los threads que se estén ejecutando.Además, se ha puesto especial énfasis en la gestión de las dependencias de datos entre los threads especulativos ya que tienen un impacto muy importante en el rendimiento del procesador. Encontrar threads independientes es casi imposible en aplicaciones irregulares, por tanto los threads especulativos necesitarán de valores producidos por otros threads especulativos. Se han estudiado dos mecanismos: sincronizar el thread productor y el thread consumidor y predecir los valores dependientes. En el primer caso, se han propuesto mecanismos para pasar el valor tan pronto como ha sido producido del productor al consumidor, especialmente en el caso de valores de memoria. Por otro lado, el segundo modelo es mucho más atrayente ya que si todos los valores dependientes fueran predichos de forma correcta, los threads pasarían a ejecutarse de forma independiente. Se han evaluado múltiples predictores de valores propuestos en la literatura y se ha presentado un nuevo predictor especialmente pensado para este tipo de arquitecturas que es el predictor de incremento. Este predictor usa la información de control de los threads especulativos para predecir los valores y los resultados obtenidos son muy prometedores aún con tamaños muy reducidos del predictor. Finalmente, el particionado de las aplicaciones afecta al rendimiento de este tipo de procesadores. Se han propuesto y evaluado varios esquemas de particionado. Una familia de estos esquemas asigna threads especulativos a construcciones de programa que por si solas proporcionan cierta independencia de control. Políticas de esta familia son aquellas que crean threads especulativos en iteraciones de bucles, continuaciones de bucles y continuaciones de subrutinas. La segunda familia de esquemas de particionadose ayuda de un análisis basado en profiling para encontrar las parejas de spawn más idóneas para cada uno de los códigos. De esta manera, aquellas partes del programa que cumplan las mejores características se seleccionan para crear threads especulativos. Algunos criterios de selección que han sido considerados en esta tesis han sido: la independencia de control, el tamaño mínimo de los threads, la independencia de datos y su predictabilidad. Los resultados obtenidos por ambas familias han sido muy significativos, aunque el esquema basado en técnicas de profile mejora los resultados obtenidos por la otra familia.

Made available in DSpace on 2014-12-17T15:47:47Z (GMT). No. of bitstreams: 1 MonicaMP.pdf: 1183724 bytes, checksum: 59ab47a1731d0a647c07a25b7e4f0a84 (MD5) Previous issue date: 2008-02-21 / The increase of applications complexity has demanded hardware even more flexible and able to achieve higher performance. Traditional hardware solutions have not been successful in providing these applications constraints. General purpose processors have inherent flexibility, since they perform several tasks, however, they can not reach high performance when compared to application-specific devices. Moreover, since application-specific devices perform only few tasks, they achieve high performance, although they have less flexibility. Reconfigurable architectures emerged as an alternative to traditional approaches and have become an area of rising interest over the last decades. The purpose of this new paradigm is to modify the device s behavior according to the application. Thus, it is possible to balance flexibility and performance and also to attend the applications constraints. This work presents the design and implementation of a coarse grained hybrid reconfigurable architecture to stream-based applications. The architecture, named RoSA, consists of a reconfigurable logic attached to a processor. Its goal is to exploit the instruction level parallelism from intensive data-flow applications to accelerate the application s execution on the reconfigurable logic. The instruction level parallelism extraction is done at compile time, thus, this work also presents an optimization phase to the RoSA architecture to be included in the GCC compiler. To design the architecture, this work also presents a methodology based on hardware reuse of datapaths, named RoSE. RoSE aims to visualize the reconfigurable units through reusability levels, which provides area saving and datapath simplification. The architecture presented was implemented in hardware description language (VHDL). It was validated through simulations and prototyping. To characterize performance analysis some benchmarks were used and they demonstrated a speedup of 11x on the execution of some applications / O aumento na complexidade das aplica??es vem exigindo dispositivos cada vez mais flex?veis e capazes de alcan?ar alto desempenho. As solu??es de hardware tradicionais s?o ineficientes para atender as exig?ncias dessas aplica??es. Processadores de prop?sito geral, embora possuam flexibilidade inerente devido ? capacidade de executar diversos tipos de tarefas, n?o alcan?am alto desempenho quando comparados ?s arquiteturas de aplica??o espec?fica. Este ?ltimo, por ser especializado em uma pequena quantidade de tarefas, alcan?a alto desempenho, por?m n?o possui flexibilidade. Arquiteturas reconfigur?veis surgiram como uma alternativa ?s abordagens convencionais e vem ganhado espa?o nas ?ltimas d?cadas. A proposta desse paradigma ? alterar o comportamento do hardware de acordo com a aplica??o a ser executada. Dessa forma, ? poss?vel equilibrar flexibilidade e desempenho e atender a demanda das aplica??es atuais. Esse trabalho prop?e o projeto e a implementa??o de uma arquitetura reconfigur?vel h?brida de granularidade grossa, voltada a aplica??es baseadas em fluxo de dados. A arquitetura, denominada RoSA, consiste de um bloco reconfigur?vel anexado a um processador. Seu objetivo ? explorar paralelismo no n?vel de instru??o de aplica??es com intenso fluxo de dados e com isso acelerar a execu??o dessas aplica??es no bloco reconfigur?vel. A explora??o de paralelismo no n?vel de instru??o ? feita em tempo de compila??o e para tal, esse trabalho tamb?m prop?e uma fase de otimiza??o para a arquitetura RoSA a ser inclu?da no compilador GCC. Para o projeto da arquitetura esse trabalho tamb?m apresenta uma metodologia baseada no reuso de hardware em caminho de dados, denominada RoSE. Sua proposta ? visualizar as unidades reconfigur?veis atrav?s de n?veis de reusabilidade, que permitem a economia de ?rea e a simplifica??o do projeto do caminho de dados da arquitetura. A arquitetura proposta foi implementada em linguagem de descri??o de hardware (VHDL). Sua valida??o deu-se atrav?s de simula??es e da prototipa??o em FPGA. Para an?lise de desempenho foram utilizados alguns estudos de caso que demonstraram uma acelera??o de at? 11 vezes na execu??o de algumas aplica??es

Submitted by Automação e Estatística (sst@bczm.ufrn.br) on 2018-07-30T14:57:19Z No. of bitstreams: 1 MarcosOliveiraDaCruz_DISSERT.pdf: 4332421 bytes, checksum: 11b304b7cc6ad671b40e493871db983d (MD5) / Approved for entry into archive by clediane guedes (clediane@bczm.ufrn.br) on 2018-07-31T10:52:00Z (GMT) No. of bitstreams: 1 MarcosOliveiraDaCruz_DISSERT.pdf: 4332421 bytes, checksum: 11b304b7cc6ad671b40e493871db983d (MD5) / Made available in DSpace on 2018-07-31T10:52:00Z (GMT). No. of bitstreams: 1 MarcosOliveiraDaCruz_DISSERT.pdf: 4332421 bytes, checksum: 11b304b7cc6ad671b40e493871db983d (MD5) Previous issue date: 2016-01-22 / A evolução dos processadores tem sido marcada pela crescente demanda por desempenho para atender as aplicações cada vez maiores e mais complexas. Juntamente com essa necessidade de desempenho, a heterogeneidade das aplicações exige também uma grande flexibilidade dos processadores. Os processadores convencionais são capazes de fornecer desempenho ou flexibilidade, mas sempre privilegiando um desses aspectos em detrimento do outro. Arquiteturas adaptativas aceleradoras de granularidade grossa têm sido propostas como uma solução capaz de oferecer, ao mesmo tempo, flexibilidade e desempenho. No entanto, um dos principais desafios desse tipo de arquitetura é o mapeamento de aplicações que é um problema NP-Completo. Dentre os fatores que contribuem para essa complexidade está o modelo de interconexão utilizado, que normalmente, se baseia em crossbar ou algum modelo próximo ao crossbar. Técnicas de exploração de paralelismo, como software pipelining, também são usadas para atingir melhor desempenho. Essas técnicas aumentam ainda mais a complexidade dos algoritmos de mapeamento. Este trabalho apresenta uma arquitetura adaptativa que utiliza um mecanismo de comunicação baseado em envio de pacotes para interconectar unidades funcionais. A arquitetura combinada com o modelo de interconexão é capaz de explorar paralelismo em dois níveis, a saber, ILP (incluindo técnicas de software pipeline) e TLP. O mapeamento das aplicações deve ser efetuado em tempo de compilação utilizando um algoritmo desenvolvido para a arquitetura de complexidade O(1). A arquitetura foi implementada em SystemC e a execução de diversas aplicações foi simulada, explorando tanto ILP quanto TLP. As simulações obtiveram, em média, 41% de ganho de desempenho em comparação com um processador RISC de 8 estágios de pipeline. Os resultados obtidos nas simulações confirmam que é possível explorar o paralelismo inerente das aplicações. Além disso a partir da escolha do modelo de mapeamento (como exploração de threads, ou de paralelismo no nível de instruções, laços, etc) é possível obter diferentes resultados através da adaptação da arquitetura a aplicação. / A evolução dos processadores tem sido marcada pela crescente demanda por desempenho para atender as aplicações cada vez maiores e mais complexas. Juntamente com essa necessidade de desempenho, a heterogeneidade das aplicações exige também uma grande flexibilidade dos processadores. Os processadores convencionais são capazes de fornecer desempenho ou flexibilidade, mas sempre privilegiando um desses aspectos em detrimento do outro. Arquiteturas adaptativas aceleradoras de granularidade grossa têm sido propostas como uma solução capaz de oferecer, ao mesmo tempo, flexibilidade e desempenho. No entanto, um dos principais desafios desse tipo de arquitetura é o mapeamento de aplicações que é um problema NP-Completo. Dentre os fatores que contribuem para essa complexidade está o modelo de interconexão utilizado, que normalmente, se baseia em crossbar ou algum modelo próximo ao crossbar. Técnicas de exploração de paralelismo, como software pipelining, também são usadas para atingir melhor desempenho. Essas técnicas aumentam ainda mais a complexidade dos algoritmos de mapeamento. Este trabalho apresenta uma arquitetura adaptativa que utiliza um mecanismo de comunicação baseado em envio de pacotes para interconectar unidades funcionais. A arquitetura combinada com o modelo de interconexão é capaz de explorar paralelismo em dois níveis, a saber, ILP (incluindo técnicas de software pipeline) e TLP. O mapeamento das aplicações deve ser efetuado em tempo de compilação utilizando um algoritmo desenvolvido para a arquitetura de complexidade O(1). A arquitetura foi implementada em SystemC e a execução de diversas aplicações foi simulada, explorando tanto ILP quanto TLP. As simulações obtiveram, em média, 41% de ganho de desempenho em comparação com um processador RISC de 8 estágios de pipeline. Os resultados obtidos nas simulações confirmam que é possível explorar o paralelismo inerente das aplicações. Além disso a partir da escolha do modelo de mapeamento (como exploração de threads, ou de paralelismo no nível de instruções, laços, etc) é possível obter diferentes resultados através da adaptação da arquitetura a aplicação.

Submitted by HETHINI DO NASCIMENTO RIBEIRO (hethini.ribeiro@outlook.com) on 2018-10-08T23:20:34Z No. of bitstreams: 1 Dissertação_hethini.pdf: 1986842 bytes, checksum: f1d6e8b9be8decd1fb1e992204d2b2d0 (MD5) / Rejected by Elza Mitiko Sato null (elzasato@ibilce.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo: Problema 01) A FICHA CATALOGRÁFICA (Obrigatório pela ABNT NBR14724) está desconfigurada e falta número do CDU. Problema 02) Falta citação nos agradecimentos, segundo a Portaria nº 206, de 4 de setembro de 2018, todos os trabalhos que tiveram financiamento CAPES deve constar nos agradecimentos a expressão: "O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Código de Financiamento 001 Problema 03) Falta o ABSTRACT (resumo em língua estrangeira), você colocou apenas o resumo em português. Problema 04) Na lista de tabelas, a página referente a Tabela 9 está desconfigurada. Problema 05) A cidade na folha de aprovação deve ser Bauru, cidade onde foi feita a defesa. Bauru 31 de agosto de 2018 Problema 06) A paginação deve ser sequencial, iniciando a contagem na folha de rosto e mostrando o número a partir da introdução, a ficha catalográfica ficará após a folha de rosto e não deverá ser contada. OBS:-Estou encaminhando via e-mail o template/modelo das páginas pré-textuais para que você possa fazer as correções da paginação, sugerimos que siga este modelo pois ele contempla as normas da ABNT Lembramos que o arquivo depositado no repositório deve ser igual ao impresso, o rigor com o padrão da Universidade se deve ao fato de que o seu trabalho passará a ser visível mundialmente. Agradecemos a compreensão on 2018-10-09T14:18:32Z (GMT) / Submitted by HETHINI DO NASCIMENTO RIBEIRO (hethini.ribeiro@outlook.com) on 2018-10-10T00:30:40Z No. of bitstreams: 1 Dissertação_hethini_corrigido.pdf: 1570340 bytes, checksum: a42848ab9f1c4352dcef8839391827a7 (MD5) / Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2018-10-10T14:37:37Z (GMT) No. of bitstreams: 1 ribeiro_hn_me_sjrp.pdf: 1566499 bytes, checksum: 640247f599771152e290426a2174d30f (MD5) / Made available in DSpace on 2018-10-10T14:37:37Z (GMT). No. of bitstreams: 1 ribeiro_hn_me_sjrp.pdf: 1566499 bytes, checksum: 640247f599771152e290426a2174d30f (MD5) Previous issue date: 2018-08-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / No início desta década havia cerca de 5 bilhões de telefones em uso gerando dados. Essa produção global aumentou aproximadamente 40% ao ano no início da década passada. Esses grandes conjuntos de dados que podem ser capturados, comunicados, agregados, armazenados e analisados, também chamados de Big Data, estão colocando desafios inevitáveis em muitas áreas e, em particular, no campo Machine Learning. Algoritmos de Machine Learning são capazes de extrair informações úteis desses grandes repositórios de dados e por este motivo está se tornando cada vez mais importante o seu estudo. Os programas aptos a realizarem essa tarefa podem ser chamados de algoritmos de classificação e clusterização. Essas aplicações são dispendiosas computacionalmente. Para citar alguns exemplos desse custo, o algoritmo Quality Threshold Clustering tem, no pior caso, complexidade O(�������������5). Os algoritmos hierárquicos AGNES e DIANA, por sua vez, possuem O(n²) e O(2n) respectivamente. Sendo assim, existe um grande desafio, que consiste em processar grandes quantidades de dados em um período de tempo realista, encorajando o desenvolvimento de algoritmos paralelos que se adequam ao volume de dados. O objetivo deste trabalho é apresentar a paralelização do algoritmo de hierárquico divisivo DIANA. O desenvolvimento do algoritmo foi realizado em MPI e OpenMP, chegando a ser três vezes mais rápido que a versão monoprocessada, evidenciando que embora em ambientes de memória distribuídas necessite de sincronização e troca de mensagens, para um certo grau de paralelismo é vantajosa a aplicação desse tipo de otimização para esse algoritmo. / Earlier in this decade there were about 5 billion phones in use generating data. This global production increased approximately 40% per year at the beginning of the last decade. These large datasets that can be captured, communicated, aggregated, stored and analyzed, also called Big Data, are posing inevitable challenges in many areas, and in particular in the Machine Learning field. Machine Learning algorithms are able to extract useful information from these large data repositories and for this reason their study is becoming increasingly important. The programs that can perform this task can be called classification and clustering algorithms. These applications are computationally expensive. To cite some examples of this cost, the Quality Threshold Clustering algorithm has, in the worst case, complexity O (n5). The hierarchical algorithms AGNES and DIANA, in turn, have O (n²) and O (2n) respectively. Thus, there is a great challenge, which is to process large amounts of data in a realistic period of time, encouraging the development of parallel algorithms that fit the volume of data. The objective of this work is to present the parallelization of the DIANA divisive hierarchical algorithm. The development of the algorithm was performed in MPI and OpenMP, reaching three times faster than the monoprocessed version, evidencing that although in distributed memory environments need synchronization and exchange of messages, for a certain degree of parallelism it is advantageous to apply this type of optimization for this algorithm. / 1757857

Este trabalho a dedicado ao estudo da exploração de paralelismo OU na programação em lógica com restrições em ambientes distribuídos. A programação em lógica, cuja linguagem mais significativa 6 Prolog, tem como premissa a utilização da lógica de predicados como linguagem computacional. A programação em lógica com restrições (CLP) é uma extensão da programação em lógica, onde busca-se a eficiência e a possibilidade de executar novas classes de problemas. Variáveis em CLP podem pertencer a domínios específicos como, por exemplo, reais ou booleanos. O principal conceito introduzido é a restrição. Restrição a uma equação que representa uma certa informação sobre uma variável e a sua relação com outras variáveis. o uso de restrições foi proposto para diminuir o espaço de busca na execução dos programas. Apesar de mais eficientes que a programação em lógica clássica, para algumas aplicações reais o desempenho das linguagens CLP ainda é insatisfatório. Por isso, é necessário buscar alternativas novas como a execução em paralelo. A exploração de paralelismo implícito em programas em 1ógica já demonstrou resultados promissores. Vários modelos foram propostos e implementados utilizando as duas principais fontes de paralelismo — E e OU — de forma isolada ou combinada. O objetivo principal desse trabalho é apresentar o modelo pclp(FD) de exploração de paralelismo OU multi-sequêncial para um ambiente com memória distribuída. O modelo pclp(FD) caracteriza-se pela existência de vários trabalhadores, cada um deles possuindo uma maquina abstrata completa. O escalonamento de tarefas a realizado por uma política dinâmica e distribuída. Uma tarefa em pclp(FD) equivale a um ponto de escolha e a um contexto de execução. O contexto de execução a formado por porções da pilha do exportador. Para que o importador tenha acesso ao contexto de execução utiliza-se a cópia incremental, que a uma das varias técnicas possíveis. Cada trabalhador possui a sua própria copia privada das pilhas de execução. A cópia caracteriza-se pelo envio das pilhas de execução do exportador para uma área privada do importador. A cópia incremental é uma técnica mais otimizada que verifica a existência de partes comuns entre os trabalhadores, copiando apenas as panes novas. O algoritmo de cópia incremental proposto no modelo a feito sem nenhuma centralização de informação do estado das pilhas. O projeto e implementação de um prot6tipo para esse modelo, utilizando a linguagem clp(FD), que implementa CLP sobre domínios finitos, permitirá uma analise das vantagens e desvantagens do modelo proposto. Os resultados obtidos com a análise servirão de base para trabalhos futuros, visando aprimorar a implementação e o modelo. / This work is dedicated to the study of the exploration of OR parallelism in Constraint Logic Programming for distributed environment. Logic Programming, which the most meaningful language is Prolog, has as premise the use of the logic of predicates as computational language. Constraint Logic Programming or CLP is an extension of the logic programming, where efficiency and the possibility to execute new kinds of problems are searched. A variable in CLP can belong to specific domains as, for example, Real or Boolean. The main concept introduced is the constraint. Constraint is an equation that represents a certain information over a variable and its relation with others variables. The use of constraints was proposed to decrease search space in the program execution. Although it is more efficient than classic logic programming, for some real applications, the performance of CLP languages still is unsatisfactory. So, it is necessary to search alternatives as parallel execution. The exploration of implicit parallelism in programs in logic has already demonstrated promising results. Several models have been proposed and implemented using the two main sources of parallelism - AND and OR — in an isolated or combined form. The main objective of this work is to present the pclp(FD) model of exploration of multi-sequential OR parallelism for a distributed memory environment. The pclp(FD) model is characterized for the existence of some workers, each one of them possessing a complete abstract machine. Task scheduling is executed by one dynamic and distributed policy. A task in pclp(FD) is equivalent to a choice point and an execution context. Execution context is formed by portions of the stack of the exporter. So that importer has access to the execution context, it uses incremental copy, which is one of the several possible techniques. The copy is characterized for sending execution stacks of the exporter to a private area of the importer, that is, each worker possesses its private copy of the execution stacks. The incremental copy is a more optimized technique that verifies the existence of common parts between workers, copying only the new ones. The incremental copy algorithm proposed in the model executes without centralized information of the state of the stacks. A prototype project and implementation for this model, using the language clp(FD), that implements CLP over finite domains, will allow an analysis of advantages and disadvantages of the considered model. The results gotten with the analysis will serve of base for future works, aiming to improve the implementation and the model.