O problema de roteamento de dados em rede de computadores consiste em minimizar o tempo médio de atraso na transmissão de mensagens, escolhendo para elas um caminho ótimo, através dos arcos da rede. Em seu trabalho, Luvezute propôs um algoritmo primai de relaxamento para otimizar o problema de roteamento de dados. O algoritmo proposto por Luvezute resolve iterativamente o problema de multifluxo, decompondo-o da forma mais independente possível, em subproblemas de simples fluxo, sendo um subproblema para cada mensagem. Esta independência entre os cálculos permite que a resolução dos subproblemas seja simultânea, admitindo-se assim uma implementação em paralelo. Nesta dissertação apresentamos um algoritmo paralelo, do tipo Fase I para encontrar uma solução inicial factível para o problema de multifluxo. Este algoritmo permite resolver de maneira mais rápida os problemas de grande porte que é o nosso objetivo inicial. O algoritmo de Fase I aqui desenvolvido pode ser utilizado para problemas de Multifluxo em geral, isto é, problemas com função objetivo linear ou não linear. O algoritmo desenvolvido foi escrito em linguagem C e implementado numa rede de microcomputadores, usando o sistema operacional UNIX. Além dos testes computacionais, apresentamos uma análise da eficiência do algoritmo e do seu speedup. / In this thesis a parallel algorithm is presented to find a feasible initial solution for the routing problem. The optimal routing in packet-switched networks consists of minimizing the medium delay time in the transmission of messages. This problem belongs to the class of multicommodity network flow problems. The developed algorithm can be used to solve multicommodity network flow problems with linear or nonlinear objective function. It solves, in fast way, problems of great size. The algorithm was written in C language and implemented in the computers network. The operating system UNIX was used. They are presented experimental results, and an analysis of the efficiency and the speedup.

El filtro mediano es una de las operaciones básicas en el procesamiento de imágenes digitales, su función es la de eliminar el ruido impulsivo sin alterar la información de la imagen. A pesar de estas características, su uso se ve restringido debido al alto costo computacional del filtro. Las propuestas tradicionales de solución, consisten en disminuir la complejidad del algoritmo del filtro mediano, y en vectorizar los algoritmos existentes. Esta vectorización se realiza al utilizar las unidades SIMD (Single Instruction Multiple Data - Instrucción Única Múltiples Datos) de los procesadores modernos. Ésta les permite realizar una misma operación a un conjunto, o vector, de datos de manera simultánea, con lo que se obtiene un mejor desempeño computacional. En el presente trabajo se implementa el filtro mediano con el algoritmo vectorial propuesto por Kolte [1], el cual aprovecha las ventajas de las unidades SIMD. La eficiencia computacional de la implementación realizada se compara con el algoritmo Filtro Mediano en Tiempo Constante, propuesto recientemente por Perreault [2], el cual presenta una complejidad de O(1). La implementación realizada es 75 y 18.5 veces mas rápida que la implementación de referencia, para áreas de análisis de 3 x 3 y 5 x 5 respectivamente. Se concluye además que la vectorización de un algoritmo no necesariamente obtiene los mismos resultados que un algoritmo diseñado específicamente para ser implementado en unidades vectoriales [3]. / Tesis

Made available in DSpace on 2015-04-14T14:50:21Z (GMT). No. of bitstreams: 1 380878.pdf: 1375038 bytes, checksum: 4a0949656d8c8c055a95425d6e4ae376 (MD5) Previous issue date: 2006-01-19 / Em um sistema de processamento paralelo heterog?neo, a redu??o do tempo de resposta das aplica??es pode ser alcan?ada se for levada em considera??o a natureza heterog?nea do ambiente computacional. Este trabalho enquadra-se neste contexto e descreve o modelo cujo objetivo ? otimizar o desempenho de aplica??es paralelas MPI executadas sobre m?quinas agregadas heterog?neas. Para isto, desenvolve-se uma estrat?gia de escalonamento global dos processos que comp?em a aplica??o, a qual visa realizar um mapeamento equilibrado de processos aos n?s no in?cio da execu??o (est?tico), de modo a balancear a carga e tendo por conseq??ncia a minimiza??o do tempo de execu??o. Isto se d? de forma transparente ao usu?rio e ? gradativamente refinado ao longo das execu??es da aplica??o, atrav?s de um ciclo de adapta??o apoiado pela an?lise autom?tica de informa??es de monitora??o obtidas em execu??es pr?vias da mesma. Para avaliar o modelo, foi desenvolvida uma ferramenta que implementa o m?todo proposto. Esta ferramenta foi instalada e configurada no Centro de Pesquisa em Alto Desempenho (CPAD) localizado na PUCRS e uma an?lise de algumas aplica??es paralelas executadas atrav?s da ferramenta, no agregado principal do CPAD, ? apresentada.

Os atuais sistemas de HPC tem realizado simulações mais complexas possíveis, produzindo benefícios para diversas áreas de pesquisa. Para atender à crescente demanda de processamento dessas simulações, novos equipamentos estão sendo projetados, visando à escala exaflops. Um grande desafio para a construção destes sistemas é a potência que eles vão demandar, onde perspectivas atuais alcançam GigaWatts. Para resolver este problema, esta tese apresenta uma abordagem para aumentar a eficiência energética usando recursos de HPC, objetivando reduzir os efeitos do desequilíbrio de carga e economizar energia. Nós desenvolvemos uma estratégia baseada no consumo de energia, chamada ENERGYLB, que considera características da plataforma, irregularidade e dinamicidade de carga das aplicações para melhorar a eficiência energética. Nossa estratégia leva em conta carga computacional atual e a frequência de clock dos cores, para decidir entre chamar uma estratégia de balanceamento de carga que reduz o desequilíbrio de carga migrando tarefas, ou usar técnicas de DVFS par ajustar as frequências de clock dos cores de acordo com suas cargas computacionais ponderadas. Como as diferentes arquiteturas de processador podem apresentam dois níveis de granularidade de DVFS, DVFS-por-chip ou DVFS-por-core, nós criamos dois diferentes algoritmos para a nossa estratégia. O primeiro, FG-ENERGYLB, permite um controle fino da frequência dos cores em sistemas que possuem algumas dezenas de cores e implementam DVFS-por-core. Por outro lado, CG-ENERGYLB é adequado para plataformas de HPC composto de vários processadores multicore que não permitem tal refinado controle, ou seja, que só executam DVFS-por-chip. Ambas as abordagens exploram desbalanceamentos residuais em aplicações interativas e combinam balanceamento de carga dinâmico com técnicas de DVFS. Assim, eles reduzem a frequência de clock dos cores com menor carga computacional os quais apresentam algum desequilíbrio residual mesmo após as tarefas serem remapeadas. Nós avaliamos a aplicabilidade das nossas abordagens utilizando o ambiente de programação paralela CHARM++ sobre benchmarks e aplicações reais. Resultados experimentais presentaram melhorias no consumo de energia e na demanda potência sobre algoritmos do estado-da-arte. A economia de energia com ENERGYLB usado sozinho foi de até 25% com nosso algoritmo FG-ENERGYLB, e de até 27% com nosso algoritmo CG-ENERGYLB. No entanto, os desequilíbrios residuais ainda estavam presentes após as serem tarefas remapeadas. Neste caso, quando as nossas abordagens foram empregadas em conjunto com outros balanceadores de carga, uma melhoria na economia de energia de até 56% é obtida com FG-ENERGYLB e de até 36% com CG-ENERGYLB. Estas economias foram obtidas através da exploração do desbalanceamento residual em aplicações interativas. Combinando balanceamento de carga dinâmico com DVFS nossa estratégia é capaz de reduzir a demanda de potência média dos sistemas paralelos, reduzir a migração de tarefas entre os recursos disponíveis, e manter o custo de balanceamento de carga baixo. / Current HPC systems have made more complex simulations feasible, yielding benefits to several research areas. To meet the increasing processing demands of these simulations, new equipment is being designed, aiming at the exaflops scale. A major challenge for building these systems is the power that they will require, which current perspectives reach the GigaWatts. To address this problem, this thesis presents an approach to increase the energy efficiency using of HPC resources, aiming to reduce the effects of load imbalance to save energy. We developed an energy-aware strategy, called ENERGYLB, which considers platform characteristics, and the load irregularity and dynamicity of the applications to improve the energy efficiency. Our strategy takes into account the current computational load and clock frequency, to decide whether to call a load balancing strategy that reduces load imbalance by migrating tasks, or use Dynamic Voltage and Frequency Scaling (DVFS) technique to adjust the clock frequencies of the cores according to their weighted loads. As different processor architectures can feature two levels of DVFS granularity, per-chip DVFS or per-core DVFS, we created two different algorithms for our strategy. The first one, FG-ENERGYLB, allows a fine control of the clock frequency of cores in systems that have few tens of cores and feature per-core DVFS control. On the other hand, CGENERGYLB is suitable for HPC platforms composed of several multicore processors that do not allow such a fine-grained control, i.e., that only perform per-chip DVFS. Both approaches exploit residual imbalances on iterative applications and combine dynamic load balancing with DVFS techniques. Thus, they reduce the clock frequency of underloaded computing cores, which experience some residual imbalance even after tasks are remapped. We evaluate the applicability of our approaches using the CHARM++ parallel programming system over benchmarks and real world applications. Experimental results present improvements in energy consumption and power demand over state-of-the-art algorithms. The energy savings with ENERGYLB used alone were up to 25%with our FG-ENERGYLB algorithm, and up to 27%with our CG-ENERGYLB algorithm. Nevertheless, residual imbalances were still present after tasks were remapped. In this case, when our approaches were employed together with these load balancers, an improvement in energy savings of up to 56% is achieved with FG-ENERGYLB and up to 36% with CG-ENERGYLB. These savings were obtained by exploiting residual imbalances on iterative applications. By combining dynamic load balancing with the DVFS technique, our approach is able to reduce the average power demand of parallel systems, reduce the task migration among the available resources, and keep load balancing overheads low.

Este trabalho apresenta o desenvolvimento de uma linguagem para descrição simplificada de algoritmos paralelos, um tradutor e um simulador de rede. Com vistas à avaliação de desempenho, a linguagem permite uma prototipagem fácil e abrangente para descrever vários tipos de programas paralelos, envolvendo estruturas de controle, repetição e as partes de comunicação e computação. Para interpretar o código escrtio na linguagem, foi desenvolvido um tradutor que traduz o código simplificado descrito pela linguagem desenvolvida, gerando código C++. O simulador de rede computa os tempos envolvidos nas comunicações. O simulador interage com o código gerado pelo tradutor. Para validação foram utilizados alguns programas de testes e resultado da simulação comparado com o da execução em um cluster de computadores pessoais. / This work presents the development of a language for simplified description of parallel algorithms, a language translator and a network simulator. The language aims to allow an easy parallel program prototyping for performance evaluation purposes and aims to be enough comprehensive to describe several kinds of parallel programs including execution control structures, repetition communication and computation parts. A translator that translates the simplified code described by the language was developed producing C++ code. A network simulator computes the communication times. The simulator interacts with the code produced by the translator. For validation some tests programs were used and the simulation results compared with the execution times in a cluster of personal computers.

Este trabalho descreve um projeto simples de gerenciamento de clusters que apresenta uma interface de usuário para as tarefas mais comuns de uso e gerenciamento de um cluster utilizado como máquina paralela. A partir do estudo de vários softwares existentes hoje, o sistema projetado foi adequado às necessidades do cluster do Laboratório de Processamento Paralelo Aplicado do Instituto de Física de São Carlos. O sistema é baseado em páginas HTML e scripts CGI. O uso de HTML e CGI se demonstrou apropriado para o desenvolvimento desse tipo de sistemas. / This work describes a simple cluster management system that operates as a user interface for some common user and manager tasks performed on a cluster used as parallel machine. We studied some cluster management systems from the literature and then designed a system with the needs of our research laboratory in mind. The system was implemented using HTML pages and CGI scripts. The use of HTML and CGI was found adequate for this type of systems.

O desenvolvimento de aplicações de forma a atingir níveis de desempenho próximos aos níveis teóricos de uma determinada plataforma é uma tarefa que exige conhecimento técnico do ambiente de hardware, uma vez que o software deve explorar detalhes específicos da plataforma em questão. Pelo fato do software ser específico à plataforma, caso ela evolua ou se altere, as otimizações realizadas podem não explorar a nova arquitetura de forma eficiente. Auto-tuners são sistemas que surgiram como um meio automatizado de adaptar um determinado software a uma arquitetura alvo. Essa adaptação ocorre através de uma busca empírica de valores ótimos para parâmetros específicos de uma aplicação, a fim de ajustá-los às características do hardware, ou ainda através da geração de códigofonte otimizado para a plataforma. Este trabalho propõe um módulo auto-tuner orientado à adaptação parametrizada de uma aplicação paralela, que trabalha variando os fatores da dimensão do domínio bidimensional, o número de processos e a extensão das regiões de sobreposição. Para cada variação dos fatores, o auto-tuner testa a aplicação na arquitetura paralela de forma a buscar a combinação de parâmetros com melhor desempenho. Para possibilitar o auto-tuning, foi desenvolvida uma classe em linguagem C++ denominada Mesh, baseada no padrão MPI. A classe busca abstrair a decomposição de domínios de uma aplicação paralela por meio do uso de Orientação a Objetos, e facilita a variação da extensão das regiões de sobreposição entre os subdomínios. Os resultados experimentais demonstraram que o auto-tuner explora o ganho de desempenho pela variação do número de processos da aplicação, que também é tratado pelo módulo auto-tuner. A arquitetura paralela utilizada na validação não se mostrou ideal para uma otimização através do aumento da extensão das regiões sobrepostas entre subdomínios. / Achieving the peak performance level of a particular platform requires technical knowledge of the hardware environment involved, since the software must explore specific details inherent to the hardware. Once the software is optimized for a target platform, if the hardware evolves or is changed, the software probably would not be as efficient in the new environment. This performance portability problem is addressed by software auto-tuning, which emerged in the past decade as an automated technique to adapt a particular software to an underlying hardware. The software adaptation is performed by an auto-tuner. The auto-tuner is an entity that empirically adjusts specific application parameters in order to improve the overall application performance, or even generates source-code optimized for the target platform. This dissertation proposes an auto-tuner to optimize the domain decomposition of a parallel application that performs stencil computations. The proposed auto-tuner works in a parameterized adaptation fashion, and varies the dimensions of a 2D domain, the number of parallel processes and the extension of the overlapping zones between subdomains. For each combination of parameter values, the auto-tuner probes the application in the parallel architecture in order to seek the best combination of values. In order to make auto-tuning possible, it is proposed a C++ class called Mesh, based on the Message Passing Interface (MPI) standard. The role of this class is to abstract the domain decomposition from the application using the Object Orientation facilities provided by C++, and also to enable the extension of the overlapping zones between subdomain. The experimental results showed that the performance gains were mainly due to the variation of the number of processes, which was one of the application factors dealt by the auto-tuner. The parallel architecture used in the experiments showed itself as not adequate for optimizing the domain decomposition by increasing the overlapping zones extension.

O presente trabalho apresenta o desenvolvimento de um sistema de Visão Artificial inteligente visando uma maior velocidade de processamento, um menor custo e aumento na produtividade industrial. Para o desenvolvimento do sistema foi utilizado o computador paralelo SPP3 desenvolvido no LCAD (Laboratório de Computação de Alto Desempenho) do ICMSC (Instituto de Ciências e Matemática de São Carlos) que utiliza uma arquitetura paralela MIMD com memória distribuída e a uma rede de comunicação de alta velocidade do tipo Myrinet [TRINDADE, 1994]. Este trabalho de tese teve como proposta desenvolver um sistema de visão em tempo real. Para atender os objetivos propostos citados, realizou-se de forma inédita a utilização de métodos estatísticos na extração do mínimo de características naturais (textura) e artificiais (histograma), invariantes à transformações geométricas, que definam a cena (ou objeto), para formar os vetores de atributos destinados ao treinamento e aprendizagem de redes neurais, utilizando ainda a técnica de invariância pelo treinamento. E para melhorar ainda mais a eficiência recorreu-se a utilização do paralelismo de hardware e software, proporcionando uma aplicação para multicomputadores / The present work presents the development of an intelligent Artificial Vision system seeking larger processing speed, smaller cost and increase in the industrial productivity. For the development of the system, a parallel computer was used, the SPP3 developed in LCAD (Laboratory of Computation of High Performance computing) of the ICMSC (Institute of Sciences and Mathematics of São Carlos). The SPP3 uses a parallel architecture MIMD with distributed memory and the a high-speed Myrinet communication network [TRINDADE, 1994]. This Thesis\'s work has with plan the development of a vision\'s sistem in real time. To attend the objetives cited, it was realized of original form, the utilization of statistical methods in extraction of less natural feature (texture) and artificial (histogram) invariants for geometrics transformations, that define the scene (or objects), to form the attributes vectors destinated for training and learning of neural networks, still using the invariants technical for training. And to improve more the eficient have recourse to use parallelism of hardware and software, giving a application to multicomputers

No description available.

Made available in DSpace on 2013-08-07T18:42:24Z (GMT). No. of bitstreams: 1 000426166-Texto+Completo-0.pdf: 1112842 bytes, checksum: 272980ccb156c75a298ac99c2e9c1b46 (MD5) Previous issue date: 2010 / Bounding the solution set of Systems of Linear Equations is a major problem in Computer Science. However, traditional methods offer no guarantee of correct solutions and not even of the existence of a solution. Hence, automatic result verification is an important additional tool in these algorithms. However, Verified Computing increases the computational cost and, in some cases, the required resolution time becomes unacceptable. The use of High Performance Computing (HPC) techniques appears as a solution. Several works have focused on optimizing Verified Computing performance for computer clusters. However, many changes have been occurring in High Performance Computing. Given the number of cores on multicore chips expected to reach tens in a few years, efficient implementations of numerical solutions using shared memory programming models is of urgent interest. In this context, this work presents a self-verified solver for Dense Interval Linear Systems optimized for parallel execution on multicores processors. The adopted strategies have resulted in a scalable solver that obtained up to 85% of reduction at execution time and a speedup of 6. 70 when solving a 15,000x15,000 Interval Linear System on a eight core computer. / A resolução de Sistemas de Equações Lineares é um problema de grande importância em Ciência da Computação. Entretanto, os métodos tradicionais não oferecem garantia de soluções corretas e nem mesmo da existência de uma solução. Por isso, cada vez mais tem-se aplicado a Computação Verificada em tais algoritmos. Por outro lado, a Computação Verificada aumenta o custo computacional e, em alguns casos, impossibilita a resolução dos sistemas em um tempo aceitável. Uma alternativa encontrada para minimizar o custo é a utilização de Computação Paralela. Diversos trabalhos têm focado em otimizar a Computação Verificada para execução em agregados de computadores. Entretanto, dado o grande avanço dos processadores com múltiplos núcleos de processamento (cores), é uma necessidade premente que sejam também propostas soluções baseadas em modelos de paralelismo para memória compartilhada buscando, assim, explorar eficientemente as novas arquiteturas. Nesse contexto, o presente trabalho apresenta uma ferramenta para resolução verificada de Sistemas Lineares Densos Intervalares de Grande Porte. Além de prover verificação automática dos resultados, a ferramenta é otimizada para execução em arquiteturas multicore. As estratégias adotadas permitiram desenvolver uma solução escalável que, ao resolver Sistemas Intervalares de ordem 15. 000x15. 000 em um computador com 8 cores, obteve redução de 85% no tempo de execução e speedup de 6,70 em comparação com a solução inicial.