Este trabalho utiliza o problema subset-sum (SSP) como estudo de caso, com o objetivo de analisar a complexidade de paralelização em Unidades de Processamento Gráficas (GPU). O SSP foi escolhido por pertencer à classe dos problemas NP-Completo, possuir grande necessidade de memória e não ter cálculo de ponto flutuante, além de ser amplamente estudado na área acadêmica devido a sua importância prática e teórica. Estas características representam um desafio para paralelização em GPUs, pelo fato de serem especialistas em cálculos de ponto flutuante e por possuir pouca quantidade de memória em relação ao grande número de núcleos. Basicamente, são apresentados 3 novos algoritmos, implementados em linguagem CUDA C, com baixo consumo de memória: somente , onde , é a capacidade da mochila e é a quantidade de itens, ao invés de do paradigma de Bellman, referentes aos algoritmos do estado da arte implementados na mesma arquitetura. Esta característica permite um ganho significativo na quantidade de instâncias solucionáveis, além do melhor tempo computacional. Para uma variedade de benchmarks, obteve-se bons valores de speed-up em relação aos melhores resultados práticos conhecidos até agora. Isto foi possível graças a um novo método para a solução do SSP, permitindo sua computação em tempo e mesmo espaço, caso processadores sejam utilizados.

Este trabalho apresenta um novo hardware coprocessador para acelerar aplicações desenvolvidas utilizando-se o Paradigma Orientado a Notificações (PON), cuja essência se constitui em uma nova forma de influência causal baseada na colaboração pontual entre entidades granulares e notificantes. Uma aplicação PON apresenta as vantagens da programação baseada em eventos e da programação declarativa, possibilitando um desenvolvimento de alto nível, auxiliando o reuso de código e reduzindo o processamento desnecessário existente das aplicações desenvolvidas com os paradigmas atuais. Como uma aplicação PON é composta de uma cadeia de pequenas entidades computacionais, comunicando-se somente quando necessário, é um bom candidato a implementação direta em hardware. Para investigar este pressuposto, criou-se um coprocessador capaz de executar aplicações PON existentes. O coprocessador foi desenvolvido utilizando-se linguagem VHDL e testado em FPGAs, mostrando um decréscimo de 96% do número de ciclos de clock utilizados por um programa se comparado a implementação puramente em software da mesma aplicação, considerando uma dada materialização em um framework em PON. / This work presents a new hardware coprocessor to accelerate applications developed using the Notification-Oriented Paradigm (NOP). A NOP application has the advantages of both event-based programming and declarative programming, enabling higher level software development, improving code reuse, and reducing the number of unnecessary computations. Because a NOP application is composed of a network of small computational entities communicating only when needed, it is a good candidate for a direct hardware implementation. In order to investigate this assumption, a coprocessor that is able to run existing NOP applications was created. The coprocessor was developed in VHDL and tested in FPGAs, providing a decrease of 96% in the number of clock cycles compared to a purely software implementation.

Este trabalho apresenta um novo hardware coprocessador para acelerar aplicações desenvolvidas utilizando-se o Paradigma Orientado a Notificações (PON), cuja essência se constitui em uma nova forma de influência causal baseada na colaboração pontual entre entidades granulares e notificantes. Uma aplicação PON apresenta as vantagens da programação baseada em eventos e da programação declarativa, possibilitando um desenvolvimento de alto nível, auxiliando o reuso de código e reduzindo o processamento desnecessário existente das aplicações desenvolvidas com os paradigmas atuais. Como uma aplicação PON é composta de uma cadeia de pequenas entidades computacionais, comunicando-se somente quando necessário, é um bom candidato a implementação direta em hardware. Para investigar este pressuposto, criou-se um coprocessador capaz de executar aplicações PON existentes. O coprocessador foi desenvolvido utilizando-se linguagem VHDL e testado em FPGAs, mostrando um decréscimo de 96% do número de ciclos de clock utilizados por um programa se comparado a implementação puramente em software da mesma aplicação, considerando uma dada materialização em um framework em PON. / This work presents a new hardware coprocessor to accelerate applications developed using the Notification-Oriented Paradigm (NOP). A NOP application has the advantages of both event-based programming and declarative programming, enabling higher level software development, improving code reuse, and reducing the number of unnecessary computations. Because a NOP application is composed of a network of small computational entities communicating only when needed, it is a good candidate for a direct hardware implementation. In order to investigate this assumption, a coprocessor that is able to run existing NOP applications was created. The coprocessor was developed in VHDL and tested in FPGAs, providing a decrease of 96% in the number of clock cycles compared to a purely software implementation.

A geração e processamento de imagens em computadores envolve o processamento de quantidades massivas de elementos de imagem. Devido à grande demanda do mercado de entretenimento, as unidades de processamento gráfico, ou GPUs, evoluiram muito nas últimas décadas, caracterizando-se pela operação com grandes volumes de dados e pelo paralelismo massivo, atingindo volumes de operações superiores aos das CPUs. As GPUs foram concebidas inicialmente para o processamento gráfico e renderização de imagens 3D. Contudo, recentemente, fornecedores de hardware gráfico possibilitaram que programadores desenvolvessem código de propósito geral para suas arquiteturas por meio de interfaces específicas de programação. O novo uso para essas arquiteturas tornou-se muito interessante onde quer que processamento massivo, repetitivo e paralelizável fosse necessário. Neste trabalho apresenta-se uma discussão sobre as vantagens e desvantagens derivadas do uso da tecnologia CUDA para acelerar o processamento de dados brutos de um radar de abertura sintética (SAR) operando em tempo real. Propõe-se um modo de processamento em tempo real baseado na divisão dos dados brutos em blocos, ressaltando os ganhos e custos desta abordagem. Também são propostos critérios de viabilidade para esse modo de processamento baseado no tempo de processamento dos blocos e nos dados do sensor SAR. É introduzida a tecnologia GPGPU (General Purpose computing on Graphics Processing Unit) representada pelo CUDA. Além disso, apresentam-se uma descrição do processamento SAR, o paradigma GPGPU e a tecnologia CUDA. Apresentam-se também a implementação do processador SAR Range-Doppler em CPU (single-thread) e em CUDA e o seu teste em experimentos comparando o desempenho de execução de cada implementação e a análise da viabilidade de processamento nos termos definidos neste trabalho. Os resultados experimentais demonstram um ganho considerável de desempenho utilizando-se o CUDA, apontando-o como arquitetura propícia para síntese de imagens SAR de tempo real.