[pt] Na área de biologia computacional a busca por informações relevantes em meio a volumes de dados cada vez maiores é uma atividade fundamental. Dentre outras, uma tarefa importante é a execução da ferramenta BLAST (Basic Local Alignment Search Tool), que possibilita comparar biosseqüências a fim de se descobrir homologias entre elas e inferir as demais informações pertinentes. Um dos problemas a serem resolvidos no que diz respeito ao custo de execução do BLAST se refere ao tamanho da base de dados, que vem aumentando consideravelmente nos últimos anos. Avaliar o BLAST com estrat´egias paralelas e distribuídas com apoio de agrupamento de computadores tem sido uma das estratégias mais utilizadas para obter ganhos de desempenho. Nesta dissertação, é realizada uma alocação física replicada da base de dados (de seqüências), onde cada réplica é fragmentada em partes distintas, algumas delas escolhidas como primárias. Dessa forma, é possível mostrar que se aproveitam as principais vantagens das estratégias de execução sobre bases replicadas e fragmentadas convencionais, unindo flexibilidade e paralelismo de E/S. Associada a essa alocação particular da base, são sugeridas duas formas de balanceamento dinâmico da carga de trabalho. As abordagens propostas são realizadas de maneira não intrusiva no código BLAST. São efetuados testes de desempenho variados que demonstram não somente a eficácia no equilíbrio de carga como também eficiência no processamento como um todo. / [en] A fundamental task in the area of computational biology is the search for relevant information within the large amount of available data. Among others, it is important to run tools such as BLAST - Basic Local Alignment Search Tool - effciently, which enables the comparison of biological sequences and discovery of homologies and other related information. However, the execution cost of BLAST is highly dependent on the database size, which has considerably increased. The evaluation of BLAST in distributed and parallel environments like PC clusters has been largely investigated in order to obtain better performances. This work reports a replicated allocation of the (sequences) database where each copy is also physically fragmented, with some fragments assigned as primary. This way we show that it is possible to execute BLAST with some nice characteristics of both replicated and fragmented conventional strategies, like flexibility and I/O parallelism. We propose two dynamic workload balancing strategies associated with this data allocation. We have adopted a non- intrusive approach, i.e., the BLAST code remains unchanged. These methods are implemented and practical results show that we achieve not only a balanced workload but also very good performances.

[pt] Ultimamente, sensores orbitais de alta resolução espacial estão fornecendo uma quantidade crescente de dados sobre a superfície da Terra. A análise destes dados implica em uma alta carga computacional, que tem motivado pesquisas envolvendo hardwares e softwares mais eficientes para estas aplicações. Neste contexto, uma questão importante reside na segmentação de imagens que envolve longos tempos de processamento e é etapa fundamental na análise de imagens baseada em objetos. Os avanços recentes das modernas unidades de processamento gráfico ou GPUs abriram a possibilidade de se explorar a capacidade de processamento paralelo para melhorar o desempenho da segmentação. Este trabalho apresenta uma versão paralela do algoritmo de segmentação multicritério, introduzido originalmente por Baatz e Schappe (2000), concebido para ser executado por GPUs. A arquitetura do hardware subjacente consiste em um sistema massivamente paralelo com múltiplos elementos processadores projetado especialmente para o processamento de imagens. O algoritmo paralelo é baseado no processamento de cada pixel em uma diferente linha de controle (thread) de modo a aproveitar a capacidade paralela da GPU. Esta dissertação também sugere alterações no cálculo de heterogeneidade do algoritmo, o que aumenta o desempenho computacional da segmentação. Os experimentos com o algoritmo paralelo proposto apresentaram uma aceleração maior do que 7 em relação à versão sequencial. / [en] Lately, orbital sensors of high spatial resolution are providing an increasing amount of data about the Earth surface. Analysis of these data implies in a high computational load, which has motivated researches on more efficient hardware and software for these applications. In this context, an important issue lies in the image segmentation that involves long processing times and is a key step in object based image analysis. The recent advances in modern programmable graphics units or GPUs have opened the possibility of exploiting the parallel processing capabilities to improve the segmentation performance. This work presents a parallel version of the multicriterion segmentation algorithm, introduced originally by Baatz and Schappe (2000), implemented in a GPU. The underlying hardware architecture consists of a massive parallel system with multiple processing elements designed especially for image processing. The parallel algorithm is based on processing each pixel as a different thread so as to take advantage of the fine-grain parallel capability of the GPU. In addition to the parallel algorithm, this dissertation also suggests a modification to the heterogeneity computation that improves the segmentation performance. The experiments under the proposed parallel algorithm present a speedup greater than 7 in relation to the sequential version.

[pt] Esta tese apresenta uma nova proposta para modelagem das funções de custo futuro, utilizadas na Programação Dinâmica Estocástica (PDE). A técnica proposta é aplicada ao planejamento da operação de médio prazo de sistemas elétricos de potência. Através da discretização do espaço de estados, o algoritmo de fechos convexos (convex hull) é utilizado na obtenção de uma série de hiperplanos que compõe um conjunto convexo. Estes planos representam uma aproximação linear por partes da função de custo futuro. O custo operacional médio utilizando a metodologia proposta considerando-se um único cenário de afluências foi comparado com o custo obtido da programação dinâmica dual determinística para o mesmo cenário de afluências. Esta análise mostra a convergência das duas metodologias e é utilizada para determinar o nível mínimo de discretização necessário para modelagem das funções de custo futuro. A partir deste resultado é feita a extensão da análise para diversos cenários de afluências utilizando-se a metodologia proposta, sendo a função de custo futuro obtida através da média do custo de operação para os diversos cenários, em cada discretização. A aplicabilidade do método é mostrada utilizando um caso exemplo de duas usinas hidrelétricas reais em cascata. Adicionalmente, um estudo de caso analisa as vantagens da paralelização do código de programação, onde métricas tais como fator de aceleração e eficiência são analisadas. Por fim, é apresentada uma simulação contendo todo o sistema elétrico brasileiro, representado por reservatórios equivalentes. / [en] This thesis presents a new approach for the expected-cost-to-go functions modeling used in the stochastic dynamic programming (SDP) algorithm. The proposed technique is applied to the long-term operation planning of electrical power systems. Using state space discretization, the convex hull algorithm is used for constructing a series of hyperplanes that composes a convex set. These planes represent a piecewise linear approximation for the expected-cost-to-go functions. The mean operation costs obtained by the proposed methodology for a single water inflow scenario were compared with those from the deterministic dual dynamic programming for the same inflow scenario.This sensitivity analysis shows the convergence of both methods and is used to determine the minimum discretization level necessary to model the expected-cost-to-go functions. From the obtained result the proposed methodology is extended to the analysis of a set of water inflow scenarios, where the expected-cost-to-go function is obtained by the mean operation cost to all the considered scenario in each discretization level. The applicability of the proposed methodology for two hydro plants in a cascade is demonstrated. Additionally, a case study using code parallelization is presented aiming at gaining computational performance, where the parallelization performance, as speedup and efficiency are measured. To finish with a simulation with the whole Brazilian electrical system considering aggregated reservoir is presented.

[pt] O processamento de sinais sísmicos é peça chave na exploração petrolífera. O caminho entre aquisição de dados e interpretação sísmica é composto por uma trilha de processos interdependentes, entre eles os processos de modelagem e migração. A dissertação apresenta a composição de um algoritmo de modelagem acústica 2D no domínio da transformada wavelet a partir de ferramentas próprias e outras já existentes na literatura. São estabelecidas as aproximações necessárias à solução em meios heterogêneos e à independência entre os subdomínios de processamento. Esta independência possibilita a exploração de técnicas de processamento paralelo. Através de exemplos, seu desempenho é avaliado com comparações à solução via diferenças finitas. Estas soluções são ainda submetidas ao mesmo processo de migração baseado em um terceiro modo de solução. / [en] Seismic signal processing is a key step to oil exploration. The path between data acquisition and seismic interpretation is composed by a sequence of interdependent processes, among which are modeling and migration processes. A 2D acoustic modeling algorithm in wavelet Transform domain, based on custom tools and tools already made known in literature is presented. Approximations necessary for the solution in inhomogeneous media and for complete independence between processing subspaces are established. Such independence allows exploration of parallel processing techniques. Throughout examples, performance is evaluated in comparison to finite-difference solution. These solutions are further processed by a migration technique based in yet another solution method.

[pt] O problema de escalonamento de tarefas divisíveis consiste em determinar como uma carga a ser processada deve ser dividida entre processadores e em que ordem cada fração de carga será enviada a cada processador. Considera-se o escalonamento em redes estrela com computadores e enlaces heterogêneos. Nesta dissertação são propostas formulações originais deste problema como modelos de programação linear inteira mista, assim como um novo algoritmo de complexidade O(n) para a solução ótima de um caso especial. Além disso, também são propostas duas novas heurísticas para o problema, que permitem a elaboração de bons escalonamentos para instâncias de grande porte em um reduzido tempo de processamento. / [en] The problem of divisible job scheduling consists of determining how to divide the data to be processed among processors and in which order each fraction should be sent to them. In this dissertation, we consider the divisible load scheduling problem in star networks with heterogeneous computers and links. Original mixed integer linear programming formulations of this problem are proposed, as well as a new algorithm with complexity O(n) to find the optimal solution for a special case. We also propose two fast heuristics that achieve good results for instances representing large scale computing systems.