Esta tese melhora o upper bound de tempo e de espaço da resolução paralela do Subset-Sum Problem (SSP) - que é uma variante do Problema da Mochila - numa máquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura científica, isto é, tanto na abordagem através das listas como por programação dinâmica. Com relação ao primeiro paradigma, é apresentada uma paralelização ótima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaço O(2n/2), onde 1 p < 2n/2/n2. Como esse algoritmo seqüencial tem até hoje a melhor complexidade de tempo para a resolução do Problema da Mochila, então nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teórico de toda a literatura. Além disso, são apresentados três algoritmos paralelos adaptativos baseados no paradigma da programação dinâmica, que são os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaço O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaço do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente até o momento.

O algoritmo que resolve o método de advecção proposto por Walcek tem como principais características a conservação dos valores de picos, tanto de máximo quanto de mínimo, e a baixa difusão numérica. Entretanto este algoritmo possui também uma característica intrínseca que limita a implementação de paralelismo por cooperação de tarefas: exige dependências de fluxo no cálculo das células do domínio. O presente trabalho propõe a mudança no paradigma de programação do algoritmo original para torná-lo aderente ao processamento a fluxo de dados. Nesse tipo de processamento a computação ocorre em forma de tarefas que são definidas de acordo com os valores/estado dos dados de entrada. Essas tarefas podem ou não conter dependências e permitem ainda uma organização não sequencial do processamento. Quando tarefas independentes surgem, a obtenção de paralelismo passa a ser trivial. Experimentos realizados sobre domínios unidimensionais mostram que a abordagem a fluxo de dados expõe situações propícias ao processamento paralelo outrora desconhecidas, além de obter um tempo total de processamento inferior ao algoritmo original. Quando considerando domínios multidimensionais, a nova abordagem consegue um desempenho paralelo equivalente e um tempo total de processamento até 2,5 mais rápido do que a abordagem original.

O principal objetivo deste trabalho é apresentar uma análise de desempenho de algoritmos de compressão de imagens, levando em consideração a energia demandada por eles. Em outras palavras, além dos critérios comumente utilizados para avaliar o desempenho de algoritmos de compressão de imagens (e.g., taxa-distorção), este trabalho também irá considerar uma variável custo em termos de energia (i.e., taxa-distorção-energia). Uma avaliação desse tipo pode permitir que a escolha de um algoritmo de compressão de imagens para operar em sistemas com restrição de energia (e.g., satélites de sensoriamento remoto) seja mais apropriada. Sabe-se que uma análise envolvendo o gasto de energia de um algoritmo apresentará resultados que dependerão do hardware que o executa. Por isso, o estudo feito por esse trabalho irá abordar o assunto considerando questões importantes da esfera da computação, onde alguns experimentos irão envolver plataformas de processamento com características distintas. Também é sabido que os processadores mais recentes permitem o processamento paralelo de operações. Quando utilizado, esse recurso é capaz de aumentar a eficiência do algoritmo em termos de tempo de processamento e gasto de energia. Por outro lado, os algoritmos de compressão de imagens mais utilizados, foram desenvolvidos sob a óptica do processamento sequencial de operações (assim como suas implementações mais usuais). Dito isso, este trabalho também irá avaliar o ganho de desempenho que é possível alcançar ao se perseguir a criação de algoritmos de compressão que façam uso do recurso de processamento paralelo. Os resultados das análises apontam para um aumento significativo do desempenho dos algoritmos analisados, em termos de tempo de processamento e gasto de energia, quando utilizado o recurso de processamento paralelo. Além disso, será possível analisar de que forma as estratégias de compressão adotadas pelos algoritmos que serão analisados irão impactar no consumo de energia do sistema.

Since the introduction of Data Warehouse (DW) and Online Analytical Processing (OLAP) technologies, efficient computation of data cubes has become one of the most relevant and pervasive problems in the DW area. The data cube operator has exponential complexity; therefore, the materialization of a data cube involves both huge amount of memory and substantial amount of time for its generation. Reducing the size of data cubes, without loss of generality, thus becomes one of the essential aspects for achieving effective OLAP services. Previous approaches reduce substantially the cube size using graph representations. A data cube can be viewed as a set of sub-graphs. In general, the approaches eliminate prefix redundancy and part of suffix redundancy of a data cube. In this work, we propose three major contributions to reduce the data cube size: MDAG, MCG and p-Cube Approaches. The MDAG approach eliminates the wildcard all (*), which represents an entire aggregation, from the cube representation, using the dimensional ID. It also uses the internal nodes to reduce the cube representation height, number of branches and number of common suffixed nodes. Unfortunately, the MDAG approach just reduces the data cube suffix redundancy, so in order to complete eliminate prefix/suffix redundancies we propose the MCG approach. The MCG approach produces a full cube with a reduction ratio of 70-90% when compared to a Star full cube representation. In the same scenarios, the new Star approach, proposed in 2007, reduces only 10-30%, Dwarf 30-50% and MDAG 40-60% of memory consumption when compared to Star approach. Our approaches are, on average, 20-50% faster than Dwarf and Star approaches. In this work, we also propose a parallel cube approach, named p-Cube. The p-Cube approach improves the runtime of Star, MDAG and MCG approaches, while keeping their low memory consumption benefits. The p-Cube approach uses an attribute-based data cube decomposition strategy which combines both task and data parallelism. It uses the dimensions attribute values to partition the data cube into a set of disjoint sub-cubes with similar size. The p-Cube approach provides similar memory consumption among its threads. Its logical design can be implemented in shared-memory, distributed-memory and hybrid architectures with minimal adaptation.

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.

Abordagens para computação de cubos de dados utilizando a estratégia de índices invertidos, tais como Frag-Cubing, são alternativas eficientes em relação às tradicionais abordagens para computação de cubos de dados com alta dimensionalidade, entretanto tais abordagens são limitadas pela memória principal (RAM) disponível. Neste trabalho, é apresentadado duas abordgens iniciais: qCube e H-Frag. qCube é uma extensão da abordagem Frag-Cubing que possibilita consultas de intervalo e H-Frag é uma abordagem que utiliza memória principal e memória externa a partir de definições do usuário. Com base nas abordagens iniciais, propomos duas outras que utilizam o sistema de memória composto por memória principal e memória externa, o qual chamamos de sistema híbrido de memória, para computar e manter atualizado cubos com alta dimensionalidade e elevado número de tuplas: HIC e bCubing. Em HIC, partições de cubos são armazenados em RAM e na memória externa utilizando a mesma representação de Frag-Cubing, contudo valores de atributos frequentes são armazenados em memória principal e valores de atributos pouco frequentes são armazenados em memória externa. HIC utiliza um parâmetro, chamado frequência acumulada crítica, para definir quais os valores de atributo são armazenados em memória principal ou em memória externa. bCubing particiona uma lista de identificadores de tuplas (TIDs) implementando a inversão de tuplas em dois níveis: um nível onde o identificador é o índice de bloco (BID) e o segundo nível onde o identificador é o índice da tupla (TID). As listas de TIDs dos valores de atributos são armazenadas em memória externa. As listas de BIDs são mantidas em memória principal e indexadas pelos valores de atributos. bCubing é capaz de calcular e manter atualizadas medidas holísticas de forma exata em cubos com alta dimensionalidade e elevado número de tuplas. Experimentos utilizando uma relação com 480 dimensões e 107 tuplas mostram que a abordagem bCubing é apenas 30% mais lenta do que Frag-Cubing para computação de cubos e aproximadamente 3 vezes mais rápida para responder consultas multidimensionais complexas a partir de tais relações. Um cubo massivo com 60 dimensões e 109 tuplas foi computado por bCubing usando 84 GB de RAM, enquanto o Frag-Cubing não computou tal cubo em uma máquina com 128 GB de RAM sem realizar operações de swap do sistema operacional. O impacto do cálculo de medidas holísticas em um cubo de dados com alta dimensionalidade também foi avaliado e os resultados demonstram que a abordagem bCubing gasta, em média, 10% mais tempo ao calcular medidas holísticas do que consultas com medidas COUNT. A abordagem bCubing respondeu consultas em um cubo de dados com 1.2 bilhões de tuplas em até 4 minutos, sendo uma destas consultas Q composta por dois operadores de subcubo e um operador EQUAL. A consulta Q calculou três medidas holísticas de forma exata: desvio padrão, mediana e moda.

Com o objetivo de desenvolver eficientemente sistemas conexionistas úteis para a solução de problemas do mundo real, se faz necessária a utilização de ferramentas que facilitem a manipulação de diversos aspectos envolvidos na construção destes sistemas tais como: topologia, métodos e parâmetros de treinamento, processamento de dados de entrada/saída e análise de resultados e desempenho. Nesta dissertação será apresentado um ambiente que utiliza uma arquitetura cliente/servidor para desenvolvimento de sistemas conexionistas denominado Servidor Aniel. Serão detalhados os módulos que compõem o servidor em termos funcionais e quais as necessidades das aplicações clientes para sua utilização.