Implementação paralela do algoritmo iterativo de busca do parâmetro de regularização ótimo para o funcional de Tikhonov no problema de restauração de imagens

O uso de técnicas com o funcional de Tikhonov em processamento de imagens tem sido amplamente usado nos últimos anos. A ideia básica nesse processo é modificar uma imagem inicial via equação de convolução e encontrar um parâmetro que minimize esse funcional afim de obter uma aproximação da imagem original. Porém, um problema típico neste método consiste na seleção do parâmetro de regularização adequado para o compromisso entre a acurácia e a estabilidade da solução. Um método desenvolvido por pesquisadores do IPRJ e UFRJ, atuantes na área de problemas inversos, consiste em minimizar um funcional de resíduos através do parâmetro de regularização de Tikhonov. Uma estratégia que emprega a busca iterativa deste parâmetro visando obter um valor mínimo para o funcional na iteração seguinte foi adotada recentemente em um algoritmo serial de restauração. Porém, o custo computacional é um fator problema encontrado ao empregar o método iterativo de busca. Com esta abordagem, neste trabalho é feita uma implementação em linguagem C++ que emprega técnicas de computação paralela usando MPI (Message Passing Interface) para a estratégia de minimização do funcional com o método de busca iterativa, reduzindo assim, o tempo de execução requerido pelo algoritmo. Uma versão modificada do método de Jacobi é considerada em duas versões do algoritmo, uma serial e outra em paralelo. Este algoritmo é adequado para implementação paralela por não possuir dependências de dados como de Gauss-Seidel que também é mostrado a convergir. Como indicador de desempenho para avaliação do algoritmo de restauração, além das medidas tradicionais, uma nova métrica que se baseia em critérios subjetivos denominada IWMSE (Information Weighted Mean Square Error) é empregada. Essas métricas foram introduzidas no programa serial de processamento de imagens e permitem fazer a análise da restauração a cada passo de iteração. Os resultados obtidos através das duas versões possibilitou verificar a aceleração e a eficiência da implementação paralela. A método de paralelismo apresentou resultados satisfatórios em um menor tempo de processamento e com desempenho aceitável.

Implementação paralela de um código de elementos finitos em 2D para as Equações de Navier-Stokes para fluidos incompressíveis com transporte de escalares.

O estudo do fluxo de água e do transporte escalar em reservatórios hidrelétricos é importante para a determinação da qualidade da água durante as fases iniciais do enchimento e durante a vida útil do reservatório. Neste contexto, um código de elementos finitos paralelo 2D foi implementado para resolver as equações de Navier-Stokes para fluido incompressível acopladas a transporte escalar, utilizando o modelo de programação de troca de mensagens, a fim de realizar simulações em um ambiente de cluster de computadores. A discretização espacial é baseada no elemento MINI, que satisfaz as condições de Babuska-Brezzi (BB), que permite uma formulação mista estável. Todas as estruturas de dados distribuídos necessárias nas diferentes fases do código, como pré-processamento, solução e pós-processamento, foram implementadas usando a biblioteca PETSc. Os sistemas lineares resultantes foram resolvidos usando o método da projeção discreto com fatoração LU por blocos. Para aumentar o desempenho paralelo na solução dos sistemas lineares, foi empregado o método de condensação estática para resolver a velocidade intermediária nos vértices e no centróide do elemento MINI separadamente. Os resultados de desempenho do método de condensação estática com a abordagem da solução do sistema completo foram comparados. Os testes mostraram que o método de condensação estática apresenta melhor desempenho para grandes problemas, às custas de maior uso de memória. O desempenho de outras partes do código também são apresentados.

Análise da tectônica de colocação de diques cretácicos na região de São Sebastião, SP

O trabalho foi desenvolvido no litoral norte do estado de São Paulo, onde ocorrem boas exposições de rochas intrusivas da porção meridional do Enxame de Diques da Serra do Mar, de idade eocretácica. O objetivo principal da dissertação é caracterizar os regimes tectônicos associados à colocação e à deformação de diques máficos na área de São Sebastião (SP) e sua distribuição espacial, a partir de interpretações de imagens de sensores remotos, análise de dados estruturais de campo e descrição petrográfica das rochas ígneas. A área apresenta grande complexidade no tocante ao magmatismo, uma vez que ocorrem diques de diabásios toleítico e alcalino, lamprófiro e rochas alcalinas félsicas como fonolitos, traquitos e sienitos, estes sob a forma diques, sills e plugs. Os diabásios toleíticos tem idades em torno 134 Ma, correlatas com o início do rifteamento sul-atlântico, enquanto que as rochas alcalinas datam de 86 Ma e estão relacionadas com um magmatismo intraplaca posterior. Os lineamentos estruturais orientam-se majoritariamente na direção ENE-WSW, paralela às foliações metamórficas e zonas de cisalhamento observadas no campo e descritas na literatura, referentes ao Domínio Costeiro da Faixa Ribeira. Os diques se orientam na direção NE-SW, com azimute semelhante porém ângulos de mergulho discordantes da foliação em grande parte da área, onde as foliações são de baixo ângulo. Um segundo conjunto de lineamentos orientado NW-SE ocorre como um importante conjunto de fraturas que cortam tanto as rochas do embasamento proterozóico quanto as rochas alcalinas neocretácicas. Diques com esta orientação são escassos. Um terceiro conjunto NNE-SSW ocorre na porção oeste da área, associado à presença de diques de diabásio que por vezes mostram indicadores de movimentação sinistral. A análise cinemática dos diques mostra um predomínio de distensão pura durante sua colocação, com um tensor de compressão mínima de orientação NW-SE, ortogonal ao principal trend dos diques. Componentes direcionais, por vezes ambíguas, são comumente observadas, com um discreto predomínio de componente sinistral. O mesmo padrão cinemático é observado para os diques toleíticos e para os alcalinos, sugerindo que o campo de tensões local pouco variou durante o Cretáceo. Embora o embasamento não tenha sido diretamente reativado durante a colocação dos diques, sua anisotropia pode ter controlado de certa forma a orientação do campo de tensões local durante o Cretáceo. Os mapas geofísicos da bacia de Santos existentes na literatura sugerem certo paralelismo entre as estruturas observadas na área de estudo e aquelas interpretadas na bacia. As estruturas NNE-SSW são paralelas ao trend das sub-bacias e ao gráben de Merluza, enquanto que as estruturas NW-SE são paralelas a zonas de transferência descritas na literatura.

Paralelização em CUDA/GLSL do algoritmo SIFT para reconhecimento de íris

Neste trabalho é estudada a viabilidade de uma implementação em paralelo do algoritmo scale invariant feature transform (SIFT) para identificação de íris. Para a implementação do código foi utilizada a arquitetura para computação paralela compute unified device architecture (CUDA) e a linguagem OpenGL shading language (GLSL). O algoritmo foi testado utilizando três bases de dados de olhos e íris, o noisy visible wavelength iris image Database (UBIRIS), Michal-Libor e CASIA. Testes foram feitos para determinar o tempo de processamento para verificação da presença ou não de um indivíduo em um banco de dados, determinar a eficiência dos algoritmos de busca implementados em GLSL e CUDA e buscar valores de calibração que melhoram o posicionamento e a distribuição dos pontos-chave na região de interesse (íris) e a robustez do programa final.

Paralelização do algoritmo FDK para reconstrução 3D de imagens tomográficas usando unidades gráficas de processamento e CUDA-C

A obtenção de imagens usando tomografia computadorizada revolucionou o diagnóstico de doenças na medicina e é usada amplamente em diferentes áreas da pesquisa científica. Como parte do processo de obtenção das imagens tomográficas tridimensionais um conjunto de radiografias são processadas por um algoritmo computacional, o mais usado atualmente é o algoritmo de Feldkamp, David e Kress (FDK). Os usos do processamento paralelo para acelerar os cálculos em algoritmos computacionais usando as diferentes tecnologias disponíveis no mercado têm mostrado sua utilidade para diminuir os tempos de processamento. No presente trabalho é apresentada a paralelização do algoritmo de reconstrução de imagens tridimensionais FDK usando unidades gráficas de processamento (GPU) e a linguagem CUDA-C. São apresentadas as GPUs como uma opção viável para executar computação paralela e abordados os conceitos introdutórios associados à tomografia computadorizada, GPUs, CUDA-C e processamento paralelo. A versão paralela do algoritmo FDK executada na GPU é comparada com uma versão serial do mesmo, mostrando maior velocidade de processamento. Os testes de desempenho foram feitos em duas GPUs de diferentes capacidades: a placa NVIDIA GeForce 9400GT (16 núcleos) e a placa NVIDIA Quadro 2000 (192 núcleos).

Modelagem numérica de elementos tracionados em aço inoxidável com parafusos defasados

Atualmente, a utilização do aço inoxidável em elementos estruturais é considerada uma solução cara para os problemas da engenharia estrutural. Todavia, mudanças de atitudes dentro da construção civil, uma transição global para um desenvolvimento sustentável e redução em impactos ambientais têm seguramente provocado um aumento na utilização do aço inoxidável. As normas de projeto de aço inoxidável atuais são, em grande parte, baseadas em analogias assumidas com o comportamento de estruturas desenvolvidas com aço carbono. Todavia, o aço inoxidável apresenta quatro curvas não-lineares tensão versus deformação (tensão e compressão, paralela e perpendicular a laminação do material), sem patamar de escoamento e região de encruamento claramente definidos, modificando assim, o comportamento global das estruturas que o utilizam. Em elementos estruturais submetidos a forças axiais de tração, a ruptura da seção líquida representa um dos estados limites últimos a serem verificados. Com o objetivo de se avaliar a resistência a tração de elementos estruturais aparafusados em aço inoxidável S304, este trabalho apresenta um modelo numérico baseado no método dos elementos finitos através do programa Ansys (versão 11). A não-linearidade do material foi considerada através do critério de plastificação de Von Mises e curvas tensão versus deformação verdadeira. A não-linearidade geométrica foi introduzida no modelo através da Formulação de Lagrange atualizado. O modelo numérico foi calibrado com resultados experimentais obtidos em ensaios de laboratório, a partir de ligações aparafusadas alternadas rígidas, onde não se ocorre nenhuma rotação entre os membros, transferindo nenhum momento fletor, apenas esforço normal e cisalhante.

Comportamento Estrutural de Elementos em Aço Inoxidável

Atualmente, a utilização do aço inoxidável em elementos estruturais ainda é por muitos engenheiros e arquitetos, considerada uma solução extravagante para os problemas da engenharia. Todavia, mudanças de atitudes dentro da construção civil e uma transição global para um desenvolvimento sustentável e redução em impactos ambientais tem seguramente provocado um aumento no uso do aço inoxidável. A maioria das normas de projeto de aço inoxidável atuais ainda são baseadas em analogias assumidas com o comportamento de estruturas de aço carbono. Todavia, o aço inoxidável apresenta quatro curvas tensão versus deformação não-lineares sem patamar de escoamento e região de encruamento claramente definidos (tração e compressão, paralela e perpendicular a direção de laminação), modificando assim, seu o comportamento global. Na presente investigação foram utilizados o aço inoxidável austenítico 304, e o aço carbono USI 300, ambos com tensão de escoamento similares, mas com tensões últimas e ductilidades distintos. Em elementos estruturais submetidos a tensões normais de tração, usualmente a ruptura da seção líquida representa um dos estados limites últimos a serem verificados. Com o objetivo de se avaliar a resistência a tração de elementos estruturais aparafusados em aço inoxidável, este trabalho executou um programa experimental inovador envolvendo ligações aparafusadas defasadas sob tração. O programa experimental foi executado em peças de aço carbono e aço inoxidável de forma a comparar as principais semelhanças e diferenças entre estes dois tipos de aços estruturais. O programa experimental possibilitou que conclusões significativas no comportamento a tração destas ligações pudessem ser observadas. Dentre outras variáveis que controlam estes estados limites últimos foi verificada a influência significativa da espessura da placa de aplicação do carregamento, disposição, configuração e número de parafusos da ligação e propriedades do aço inoxidável como ductilidade e razão entre suas tensões de escoamento e de ruptura.

Teoria quântica de campos para férmions interagentes no plano a temperatura e potencial químico finitos, na presença de um campo magnético externo oblíquo

Neste trabalho, os efeitos de um campo magnético oblíquo externo no modelo de Gross- Neveu (2+1)-dimensional, que inclui as componentes paralela e perpendicular do campo em relação ao sistema, são estudados no contexto da simetria quiral e discreta do modelo. Nosso principal interesse está nos efeitos deste campo sobre o diagrama de fase do sistema, onde também incluímos os efeitos combinados de temperatura e potencial químico. Os diagramas de fase são obtidos através do potencial efetivo a 1 loop para o modelo, derivado em primeira ordem na expansão 1=N. Transições de fase relevantes que podem ser estudadas através deste modelo são, por exemplo, metal-isolante em matéria condensada e na teoria quântica de campos de férmions planares em geral. A relação entre a transição de fase com quebra da simetria quiral e discreta e o surgimento de um gap (ou a presença de um valor esperado no vácuo do campo escalar diferente de zero), como função do campo magnético oblíquo, é analisada em detalhes.

Hardware paralelo reconfigurável para identificação de alinhamentos de sequências de DNA.

Amostras de DNA são encontradas em fragmentos, obtidos em vestígios de uma cena de crime, ou coletados de amostras de cabelo ou sangue, para testes genéticos ou de paternidade. Para identificar se esse fragmento pertence ou não a uma sequência de DNA, é necessário compará-los com uma sequência determinada, que pode estar armazenada em um banco de dados para, por exemplo, apontar um suspeito. Para tal, é preciso uma ferramenta eficiente para realizar o alinhamento da sequência de DNA encontrada com a armazenada no banco de dados. O alinhamento de sequências de DNA, em inglês DNA matching, é o campo da bioinformática que tenta entender a relação entre as sequências genéticas e suas relações funcionais e parentais. Essa tarefa é frequentemente realizada através de softwares que varrem clusters de base de dados, demandando alto poder computacional, o que encarece o custo de um projeto de alinhamento de sequências de DNA. Esta dissertação apresenta uma arquitetura de hardware paralela, para o algoritmo BLAST, que permite o alinhamento de um par de sequências de DNA. O algoritmo BLAST é um método heurístico e atualmente é o mais rápido. A estratégia do BLAST é dividir as sequências originais em subsequências menores de tamanho w. Após realizar as comparações nessas pequenas subsequências, as etapas do BLAST analisam apenas as subsequências que forem idênticas. Com isso, o algoritmo diminui o número de testes e combinações necessárias para realizar o alinhamento. Para cada sequência idêntica há três etapas, a serem realizadas pelo algoritmo: semeadura, extensão e avaliação. A solução proposta se inspira nas características do algoritmo para implementar um hardware totalmente paralelo e com pipeline entre as etapas básicas do BLAST. A arquitetura de hardware proposta foi implementada em FPGA e os resultados obtidos mostram a comparação entre área ocupada, número de ciclos e máxima frequência de operação permitida, em função dos parâmetros de alinhamento. O resultado é uma arquitetura de hardware em lógica reconfigurável, escalável, eficiente e de baixo custo, capaz de alinhar pares de sequências utilizando o algoritmo BLAST.

Arquitetura de uma rede de interconexão com memória compartilhada baseada na topologia crossbar

Multi-Processor System-on-Chip (MPSoC) possui vários processadores, em um único chip. Várias aplicações podem ser executadas de maneira paralela ou uma aplicação paralelizável pode ser particionada e alocada em cada processador, a fim de acelerar a sua execução. Um problema em MPSoCs é a comunicação entre os processadores, necessária para a execução destas aplicações. Neste trabalho, propomos uma arquitetura de rede de interconexão baseada na topologia crossbar, com memória compartilhada. Esta arquitetura é parametrizável, possuindo N processadores e N módulos de memórias. A troca de informação entre os processadores é feita via memória compartilhada. Neste tipo de implementação cada processador executa a sua aplicação em seu próprio módulo de memória. Através da rede, todos os processadores têm completo acesso a seus módulos de memória simultaneamente, permitindo que cada aplicação seja executada concorrentemente. Além disso, um processador pode acessar outros módulos de memória, sempre que necessite obter dados gerados por outro processador. A arquitetura proposta é modelada em VHDL e seu desempenho é analisado através da execução paralela de uma aplicação, em comparação à sua respectiva execução sequencial. A aplicação escolhida consiste na otimização de funções objetivo através do método de Otimização por Enxame de Partículas (Particle Swarm Optimization - PSO). Neste método, um enxame de partículas é distribuído igualmente entre os processadores da rede e, ao final de cada interação, um processador acessa o módulo de memória de outro processador, a fim de obter a melhor posição encontrada pelo enxame alocado neste. A comunicação entre processadores é baseada em três estratégias: anel, vizinhança e broadcast. Essa aplicação foi escolhida por ser computacionalmente intensiva e, dessa forma, uma forte candidata a paralelização.

Implementação de Visualização de Dados Tridimensionais de Malhas Irregulares no Processador Cell Broadband Engine.

A renderização de volume direta tornou-se uma técnica popular para visualização volumétrica de dados extraídos de fontes como simulações científicas, funções analíticas, scanners médicos, entre outras. Algoritmos de renderização de volume, como o raycasting, produzem imagens de alta qualidade. O seu uso, contudo, é limitado devido à alta demanda de processamento computacional e o alto uso de memória. Nesse trabalho, propomos uma nova implementação do algoritmo de raycasting que aproveita a arquitetura altamente paralela do processador Cell Broadband Engine, com seus 9 núcleos heterogêneos, que permitem renderização eficiente em malhas irregulares de dados. O poder computacional do processador Cell BE demanda um modelo de programação diferente. Aplicações precisam ser reescritas para explorar o potencial completo do processador Cell, que requer o uso de multithreading e código vetorizado. Em nossa abordagem, enfrentamos esse problema distribuindo a computação de cada raio incidente nas faces visíveis do volume entre os núcleos do processador, e vetorizando as operações da integral de iluminação em cada um. Os resultados experimentais mostram que podemos obter bons speedups reduzindo o tempo total de renderização de forma significativa.

Otimização do problema de localização de instalações aplicado ao comércio e distribuição de combustíveis

Um dos problemas mais relevantes em organizações de grande porte é a escolha de locais para instalação de plantas industriais, centros de distribuição ou mesmo pontos comerciais. Esse problema logístico é uma decisão estratégica que pode causar um impacto significativo no custo total do produto comercializado. Existem na literatura diversos trabalhos que abordam esse problema. Assim, o objetivo desse trabalho é analisar o problema da localização de instalações proposto por diferentes autores e definir um modelo que seja o mais adequado possível ao mercado de distribuição de combustíveis no Brasil. Para isso, foi realizada uma análise do fluxo de refino e distribuição praticado neste segmento e da formação do respectivo custo de transporte. Foram consideradas restrições como capacidade de estoque, gama de produtos ofertados e níveis da hierarquia de distribuição. A partir dessa análise, foi definido um modelo matemático aplicado à redução dos custos de frete considerando-se a carga tributária. O modelo matemático foi implementado, em linguagem C, e permite simular o problema. Foram aplicadas técnicas de computação paralela visando reduzir o tempo de execução do algoritmo. Os resultados obtidos com o modelo Single Uncapacited Facility Location Problem (SUFLP) simulado nas duas versões do programa, sequencial e paralela, demonstram ganhos de até 5% em economia de custos e redução do tempo de execução em mais de 50%.

Precondicionadores baseados na aproximação da inversa.

Neste trabalho de dissertação apresentaremos uma classe de precondicionadores baseados na aproximação esparsa da inversa da matriz de coecientes, para a resolução de sistemas lineares esparsos de grandes portes através de métodos iterativos, mais especificamente métodos de Krylov. Para que um método de Krylov seja eficiente é extremamente necessário o uso de precondicionadores. No contexto atual, onde computadores de arquitetura híbrida são cada vez mais comuns temos uma demanda cada vez maior por precondicionadores paralelizáveis. Os métodos de inversa aproximada que serão descritos possuem aplicação paralela, pois so dependem de uma operação de produto matriz-vetor, que é altamente paralelizável. Além disso, alguns dos métodos também podem ser construídos em paralelo. A ideia principal é apresentar uma alternativa aos tradicionais precondicionadores que utilizam aproximações dos fatores LU, que apesar de robustos são de difícil paralelização.