Orientador: Ricardo de Oliveira Anido / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T18:29:05Z (GMT). No. of bitstreams: 1 Brandao_RobertoFerreira_D.pdf: 7422287 bytes, checksum: 8a3bf1a72bd7e9fc92b34f8992db6d3e (MD5) Previous issue date: 2003 / Resumo: Este trabalho faz contribuições ao avanço do conhecimento de três diferentes áreas dos sistemas de distribuição de documentos via Web: gerenciamento de espaço em caches para Web, redes hierárquicas de caches cooperativos e servidores Web baseados em c1usters de processadores. Primeiramente, é apresentado um estudo sobre a utilização de caches cooperativos. A cooperatividade permite um melhor aproveitamento dos recursos dos meios de transmissão, possibilitando um menor tempo de espera aos usuários dos serviços da Web. Na área de gerenciamento de espaço em caches para Web foi desenvolvido o GDE (Gerenciador Dinâmico de Espaço), que além de apresentar desempenho compatível com as melhores estratégias de gerenciamento de espaço em caches usadas atualmente, possui a vantagem de poder variar automaticamente o direcionamento do trabalho do cache, podendo fazer com que o cache varie dinamicamente a QoS (Quality 01 Service) oferecida aos usuários do sistema. Este trabalho apresenta também um simulador paralelo de redes de caches distribuídos, hierárquicos e cooperativos, que é capaz de usar o poder de processamento de computadores paralelos para simular situações reais de uso de caches para Web, permitindo assim avaliar paralelamente um grande número de possibilidades para a construção de redes de caches para Web. Para aumentar o desempenho dos caches formadores de redes hierárquicas, é proposta a utilização da estratégia de Passagem de Recomendação, que permite conseguir altas taxas de desempenho sem se preocupar com o problema da perda de referência da popularidade inicial dos arquivos. O estudo de servidores Web baseados em c1usters de processadores foi direcionado principalmente a computadores com a arquitetura Beowulf. Neste trabalho são apresentados resultados da avaliação da possibilidade de usar computadores com essa arquitetura como servidores Web de alto desempenho, escaláveis e tolerantes a falhas. Para isso, é proposto um modelo do servidor e apresentados testes realizados com um protótipo implementado / Abstract: This document describes a research work that makes contributions towards a better understanding of three different areas related to document distribution via Internet: Web cache space management, hierarchical and cooperative caches and clustered Web servers. First, it is presented a study on Web cache cooperation. Cooperation allows better resource utilization, making possible a lower response time to the users. The startegy named GDE (Gerenciador Dinâmico de Espaço - Dynamic Space Manager) allows to Web caches both to present good performance and ability of providing different QoS (Quality of Service) to the users. This document also presents a parallel simulator for distributed, hierarchical and cooperative caches networks. That simulator is able to use the high processing power provided by parallel computers to simulate real situations of caches network work. To increase the perfonnance of the caches within a Web cache network, this documents propose a strategy named Passagem de Recomendação (Recommendation Passing), that allows getting high perfonnance from the caches regardless the replacement policy they use, avoiding problems caused by the lost of initial popularity reference. This document also describes a study regarding the possibility of using a Beowulf c1uster as a high perfonnance, high availability and fault tolerant Web server. That study was accomplished using a model whose characteristics were used to build a prototype. Some evaluation results of that prototype are also presented. / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

El cálculo de la trayectoria de partículas en la atmósfera es una actividad abordada desde hace mucho tiempo, tomando en cuenta un enfoque clásico del uso de los computadores, en el cual se utilizan sus recursos como Procesador Central (CPU) y Memoria RAM. Este enfoque, que ha servido para alcanzar los logros actuales, con predicciones bastante acertadas, aún adolece de problemas claves y en cierta medida irresolubles, que se ven acentuados cuando los procesos se hacen más complejos, ya sea incorporando muchas partículas, o tomando en cuenta modelos de desplazamiento más realistas. El presente trabajo aborda un enfoque totalmente nuevo, el cual hace uso de una componente física de los computadores llamada “Tarjeta Gráfica”, la cual cuenta con su propia unidad de procesamiento gráfico llamada GPU por sus siglas en inglés. Esta componente, gracias a su gran cantidad de núcleos, ofrece la posibilidad de realizar paralelamente entre sí todos, o una parte de los cálculos que le son asignados, de una manera mucho más potente que lo conseguido en la actualidad al hacer uso solamente de CPU. Este problema es abordado mediante la implementación de un programa en dos versiones: una para funcionar exclusivamente en CPU y la otra para hacer uso de GPU en los cálculos. De esta manera se puede contar con un método directo para comparar el desempeño de estos dos enfoques, contrastarlos entre sí, y deducir los casos en que uno supera al otro. El principal insumo en la comparación de estos cálculos es la información del pronóstico del viento. El programa fue aplicado a una situación real: la erupción del Volcán Chaitén, para un día cuyos datos se poseían de antemano. Los resultados obtenidos fueron graficados y comparados con una imagen satelital correspondiente al mismo día simulado, siendo posible comprobar la alta similitud entre ellas. El tiempo de cálculo empleado por la versión que funciona en GPU supera en algunos casos en más de doscientas veces lo que tarda su contraparte CPU, sin afectar en gran medida la exactitud de los cálculos. Esto permite comprobar efectivamente que las GPU superan ampliamente el desempeño de las CPU, cuando el problema abordado es altamente paralelizable. Este es un tema que no está en absoluto cerrado, por cuanto son muchos los caminos donde seguir explorando las ventajas y desventajas del uso de GPU para estos cálculos. Por ejemplo se puede ver cómo funcionan las GPU incorporando procesos físicos más complejos para el cálculo de los desplazamientos de las partículas, o se puede considerar algunas propiedades físicas de estas partículas, como lo es la masa por ejemplo.

Ingeniero Civil Mecánico / Dentro de los métodos de simulación numérica para resolución de ecuaciones diferenciales parciales (EDP's), los métodos sin malla han sido desarrollados desde hace aproximadamente veinte años. A diferencia del método de elementos finitos, los métodos sin malla no necesitan una malla definida para la construcción de sus funciones de base, las que se crean únicamente por la distribución de los nodos en el dominio. Esta característica hace a este método más atractivo en problemas donde exista distorsión de la malla, sin embargo, requieren un tiempo extra en su cálculo y un esfuerzo mayor en su programación. El presente trabajo tiene por objetivo realizar un algoritmo numérico eficiente mediante programación en paralelo, para la resolución de problemas en la mecánica de sólidos mediante el método sin malla Galerkiano con funciones de base de máxima entropía. La motivación de este trabajo es suplir uno de los principales defectos de los métodos sin malla, ser computacionalmente costosos. Son abordados los antecedentes del método sin malla, elasticidad lineal y la programación en paralelo. Se utiliza el método sin malla Galerkiano basado en la forma débil, con funciones de base de máxima entropía. Se trabaja con el software computacional MATLAB y la librería Parallel Computing Toolbox en la implementación de la programación en paralelo para tres problemas específicos y se analiza el error numérico, convergencia, tiempo de cómputo, e indicadores de desempeño para la programación en paralelo, como lo son Speedup y Eficiencia paralela. Se obtienen errores numéricos aceptables, entregados por las normas relativas L^2 y H^1, obteniendo convergencia en los tres problemas. Los tiempos de cómputo se reducen al implementar la programación paralela en todos los casos. La convergencia del problema es independiente del número de procesadores utilizados. Se obtienen los mejores resultados de Speedup y Eficiencia paralela para problemas por sobre los 5000 grados de libertad. Se recomienda trabajar problemas por sobre esta cifra en la implementación de la programación en paralelo para la resolución de problemas en la mecánica de sólidos mediante el método sin malla Galerkiano. Se cumple objetivo principal, logrando realizar algoritmo numérico mediante programación en paralelo, para la resolución de problemas en la mecánica de sólidos mediante el método sin malla Galerkiano con funciones de base de máxima entropía.

Orientador: Hans Kurt Edmund Leisenberg / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-18T09:33:54Z (GMT). No. of bitstreams: 1 Cavalcanti_CarlosFredericoMarcelodaCunha_M.pdf: 2077810 bytes, checksum: c17ae9fa4d6e194954a64c2ad678a02f (MD5) Previous issue date: 1993 / Resumo: Um sistema multicomputacional possui características que, quando bem exploradas, permitem obter um ganho real em desempenho e funcionalidade não encontrados em outros sistemas, ou mesmo em cada computador individualmente. Para explorar estas características é necessário integrar, de uma forma adequada, todos os recursos individuais em um recurso único, agora representados pelo sistema. Assim, a interligação de todos os computadores refletirá em ganho caso haja uma efetiva cooperação entre eles. Quanto maior o comprometimento dos elementos que participam desta cooperação - hardware, sistema operacional, linguagens e ferramentas de apoio - com o sistema multicomputacional, maior será o ganho de desempenho e funcionalidade do sistema. Esta dissertação caracteriza estes mecanismos (agentes) que possuem o objetivo de viabilizar a cooperação dos processadores em um sistema multicomputacional através da distribuição de código. Para que isto fosse possível foi idealizado uma entidade abstrata denominada camada de redirecionamento. A camada de redirecionamento juntamente com seu modelo computacional constituem um novo paradigma para a análise de sistemas distribuídos. Vários sistemas multicomputacionais são discutidos analisando a distribuição de código sob a óptica da camada de redirecionamento. / Abstract: A multicomputer system has some characteristics which, when well explored, allow us to get real throughtput and funcionality that aren't found in other systems, or even in each individual computer. In order to explore these characteristics it is necessary to integrate, in an adequate manner, all the single resources in only one resource, now representing the system. .So, the integration of individual computers will produce in a gain if a real cooperation among them is established. The greater the engagement of these elements - hardware, operating systems, languagens and support tools - with the multicomputer system, the greater will be the gain of throughtput and funcionality of the system. This dissertation characterizes these mechanisms (agents) whose aim is to make the cooperation of processors in a multicomputer system possible via code distribution. In order to achive this goal, an abstract entity and its computacional model were idealized which establishes a new paradigm for the analysis of distributed systems. Several multicomputer systems are discussed and their code distribution analysed under the proposed redirection layer paradigm. / Mestrado / Mestre em Ciência da Computação

Algoritmos de balanceamento de carga são utilizados em sistemas distribuídos para homogeneizar a ocupação dos recursos computacionais disponíveis. A homogeneidade na ocupação do ambiente permite otimizar a alocação de recursos e, conseqüentemente, aumentar o desempenho das aplicações. Com o advento dos sistemas distribuídos de alta escala, fazem-se necessárias pesquisas para a construção de algoritmos de balanceamento de carga que sejam capazes de gerir com eficiência esses sistemas. Essa eficiência é medida através do número de mensagens geradas no ambiente, do suporte a ambientes heterogêneos, do uso de políticas que consomem poucos recursos do sistema, da estabilidade em alta carga, da escalabilidade do sistema e dos baixos tempos de resposta. Com o objetivo de atender as necessidades dos sistemas distribuídos de alta escala, este doutorado propõe, apresenta e avalia um novo algoritmo de balanceamento de carga denominado TLBA (Tree Load Balancing Algorithm). Esse algoritmo organiza os computadores do sistema em uma topologia lógica na forma de árvore, sobre a qual são executadas operações de balanceamento de carga. Para validar o TLBA foi construído um simulador que, submetido a testes, permitiu comprovar suas contribuições, que incluem: o baixo número de mensagens geradas pelas operações de balanceamento de carga; a estabilidade em altas cargas; os baixos tempos médios de resposta de processos. Para validar os resultados de simulação, foi construído um protótipo do TLBA. Esse protótipo confirmou os resultados de simulação e, conseqüentemente, as contribuições do algoritmo. / Load balancing algorithms are applied in distributed systems to homogenize the occupation of the available computational resources. The homogeneity of the environment occupation allows optimising the resource allocation and consequently, increasing the application performance. With the advent of the large-scale distributed systems, it was necessary to start researching the construction of load balancing algorithms which are able to manage these systems with efficiency. This efficiency is measured through the number of messages generated on the environment; the support to heterogeneous environments and the load balance policies which should spend the minimal resources time; the stability in overloaded situations; the system scalability; and the processes average response times, that should be small. With the aim to achieve the large-scale distributed systems requirements, this Ph.D. proposes, presents and evaluates a new load balancing algorithm named TLBA (Tree Load Balancing Algorithm). This algorithm arranges the computers on a logical network topology with a tree format. The load balancing operations are executed over this tree. To evaluate the TLBA algorithm, a simulator was built that was submitted to tests that confirmed the following characteristics: the small number of messages generated by the load balancing operations; the stability in overloaded situations; the small average processes response times. To validate the simulation results a TLBA prototype was implemented. This prototype confirmed the simulation results and consequently the contributions of the proposed algorithm.

O objetivo principal deste trabalho é a paralelização de um modelo global de previsão do tempo em diferenças finitas com refinamento local. Este é baseado nas equações primitivas, e faz uso de uma discretização semi-Lagrangiana e semi-implícita em três níveis no tempo em uma malha de Lorenz na vertical e uma malha do tipo C de Arakawa na horizontal. A discretização horizontal é feita através de diferenças finitas de segunda ordem. A equação escalar elíptica tridimensional resultante é desacoplada em um sistema de equações bidimensionais do tipo Helmholtz, o qual é resolvido por meio de um método multigrid. O modelo de paralelização foi desenvolvido para máquinas com memória distribuída, fazendo uso de MPI para passagens de mensagens e baseado em técnicas de decomposição de domínio. O acoplamento apenas local dos operadores de diferenças finitas viabiliza a decomposição em duas direções horizontais. Evitamos a decomposição vertical, tendo em vista o forte acoplamento nesta direção das parametrizações de fenômenos físicos. A estratégia de paralelização foi elaborada visando o uso eficiente de centenas ou alguns milhares de processadores, dependendo da resolução do modelo. Para tal, a malha localmente refinada é separada em três regiões: uma grossa, uma de transição e uma fina, onde cada uma delas é dividida de forma independente entre um número de processadores proporcional ao número de pontos que cada uma armazena, garantindo assim um balanceamento de carga adequado. Não obstante, para resolver o sistema de equações bidimensionais do tipo Helmholtz foi necessário mudar a estratégia de paralelização, dividindo o domínio unicamente nas direções vertical e latitudinal. Ambas partes do modelo com paralelizações diferentes estão conectadas por meio da estratégia de transposição de dados. Testamos nosso modelo utilizando até 1024 processadores e os resultados ainda mostraram uma boa escalabilidade. / The main goal of this work is the parallelization of a weather prediction model employing finite differences on locally refined meshes. The model is based on the primitive equations and uses a three-time-level semi-implicit semi-Lagrangian temporal discretization on a Lorenz-type vertical grid combined with a horizontal Arakawa C-grid. The horizontal discretization is performed by means of second order finite differences. The resulting three-dimensional scalar elliptic equation is decoupled into a set of Helmholtz-type two-dimensional equations, solved by a multigrid method. The parallelization has been written for distributed-memory machines, employing the MPI message passing standard and was based on domain decomposition techniques. The local coupling of the finite difference operators was exploited in a two-dimensional horizontal decomposition. We avoid a vertical decomposition due to the strong coupling of physical parameterization routines. The parallelization strategy has been designed in order to allow the efficient use of hundreds to a few thousand processors, depending on the model resolution. In order to achieve this, the locally refined mesh is split into three regions: a coarse, a transition and a fine one, each decomposed independently. The number of allocated processors for each region is proportional to the number of the grid-points it contains, in order to guarantee a good load-balancing distribution. However, to solve the set of Helmholtz-type bidimensional equations it was necessary to change the parallelization strategy, splitting the domain only in vertical and latitudinal directions. Both parts of the model with different parallelizations are related by means the data transposition strategy. We tested our model using up to 1024 processors and the results still showed a good scalability.

Esta tesis tiene el objetivo de estudiar aplicaciones de la transformada wavelet discreta (DWT) al álgebra lineal numérica. Se hace un estudio de las distintas variantes de paralelización de la DWT y se propone una nueva variante paralela, en memoria distribuida, con distribuciones de datos orientadas a bloques de matrices, como la 2DBC de ScaLAPACK. La idea es que la DWT en muchos casos es una operación intermedia y debe ajustarse a las distribuciones de datos que se estén usando. Se define y demuestra una forma de calcular exactamente la cantidad de elementos que debe comunicar cada procesador para que se puedan calcular de forma independiente todo los coeficientes wavelet en una cantidad de niveles determinada. Finalmente se propone una variante específica, más eficiente, para el cálculo de la DWT-2D cuando se aplica como paso previo a la resolución de un sistema de ecuaciones distribuido 2DBC, considerando una permutación de las filas y columnas del sistema que minimiza las comunicaciones. Otro de los aportes de esta tesis es el de considerar como un caso típico, el cálculo de la DWT-2D no estándar en matrices dispersas, proponemos algoritmos para realizar esta operación sin necesidad de construir explícitamente la matriz wavelet. Además tenemos en cuenta el fenómeno de rellenado (fill-in) que ocurre al aplicar la DWT a una matriz dispersa. Para ello exploramos con los métodos de reordenamiento clásicos de grado mínimo y de reducción a banda. De forma adicional sugerimos como pueden influir esos reordenamientos a la convergencia de los métodos multimalla ya que ocurre una redistribución de la norma de la matriz hacia los niveles inferiores de la representación multi-escala, lo que garantizaría una mejor compresión. El campo de aplicación de la transformada wavelet que se propone es la resolución de grandes sistemas de ecuaciones lineales. / Acevedo Martínez, L. (2009). Computación paralela de la transformada Wavelet; Aplicaciones de la transformada Wavelet al Álgebra Lineal Numérica [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7107 / Palancia

En diversas aplicaciones prácticas cada vez es más frecuente la presencia de problemas de optimización que involucran variables que deben tomar valores discretos. Debido a su naturaleza combinatoria, los problemas de optimización discretos presentan por lo general una complejidad computacional exponencial, y por tanto son mucho más complicados de resolver que los problemas continuos. El trabajo descrito en esta tesis se ha centrado en el estudio y solución al problema de encontrar el punto de una retícula más cercano a un punto dado. Dicho problema puede originarse, entre otras múltiples aplicaciones prácticas, en la detección de señales en sistemas de comunicaciones inalámbricos MIMO (Multiple Input - Multiple Output). Los problemas de optimización discretos no pueden abordarse con métodos de convergencia rápida basados en derivadas. En su lugar, la solución se obtiene mediante métodos como Ramificación y Poda, programación dinámica y búsquedas heurísticas. El trabajo presentado ha consistido, en primer lugar, en realizar un amplio estudio del estado del arte de los métodos de Búsqueda Directa (que son métodos de optimización no basados en derivadas) y de los métodos Sphere-Decoding (pertenecientes al esquema de Ramificación y Poda). En segundo lugar, se ha abordado la paralelización de estos métodos dirigida a distintas arquitecturas, bien sea arquitecturas con memoria compartida, memoria distribuida y esquemas híbridos; además de explorar, en el caso de la Búsqueda Directa, variantes asíncronas de paralelización. Adicionalmente se proponen mejoras en los propios algoritmos secuenciales. Se diseñaron e implementaron diversas variantes de métodos de Búsqueda Directa, las cuales tuvieron buenos resultados en la resolución del Problema Inverso Aditivo de Valores Singulares, pues lograron converger y obtener mejor precisión en la solución que los métodos basados en derivadas tipo Newton. / Trujillo Rasúa, RA. (2009). Algoritmos paralelos para la solución de problemas de optimización discretos aplicados a la decodificación de señales [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7108 / Palancia

The polynomial eigenvalue problem appears in many areas of scientific and technical computing. It can be seen as a generalization of the linear eigenvalue problem in which the equation P(lambda)x = 0, that defines the problem, involves a polynomial P(lambda), of degree d, in the parameter lambda (the eigenvalue), and d+1 matrix coefficients. In its turn, the polynomial eigenvalue problem is a particular case of the nonlinear eigenvalue problem, T(lambda)x = 0, in which T is a nonlinear matrix function. These problems appear in diverse areas of application such as acoustics, fluid mechanics, structure analysis, or photonics. This thesis focuses on the study of methods for the numerical resolution of the polynomial eigenvalue problem, as well as the adaptation of such methods to the most general nonlinear case. Mainly, we consider methods of projection, that are appropriate for the case of sparse matrices of large dimension, where only a small percentage of eigevalues and eigenvectors are required. The algorithms are studied from the point of view of high-performance computing, considering issues like (computational and memory) efficiency and parallel computation. SLEPc, Scalable Library for Eigenvalue Problem Computations, is a software library for the parallel solution of large-scale eigenvalue problems. It is of general purpose and can be used for standard and generalized problems, both symmetric and nonsymmetric, with real or complex arithmetic. As a result of this thesis, we have developed several solvers for polynomial an nonlinear eigenproblems, which have included in the last versions of this software. On one hand, we consider methods based on the linearization of the polynomial problem, that solves an equivalent linear eigenproblem of dimension several times the initial size. Among them, the TOAR method stands out, that repre- sents the search subspace basis in an efficient way in terms of memory, and is appropriate to handle the increase of dimension of the linear problem. The thesis also proposes specific variants for the particular case of symmetric matrices. In all these methods we consider several aspects to provide the implementations with robustness and flexibility, such as spectral transformations, scaling, and techniques of extraction. In addition to the methods of linearization, we propose methods of Newton type, such as the method of Jacobi-Davidson with deflation and the method of Newton for invariant pairs. Due to its characteristics, the latter is not usually employed as a proper method, but as a technique for refinement of the solutions obtained with another method. The previous methods can also be applied to the resolution of the nonlinear problem, using techniques like polynomial or rational interpolation, being necessary in some cases to adapt the algorithms. This thesis covers also these cases. For all the considered algorithms we have made parallel implementations in SLEPc, and have studied its numerical behaviour and its parallel performance in problems coming from real applications. / El problema polinómico de valores propios aparece en muchas áreas de la computación científica y técnica. Puede verse como una generalización del problema lineal de valores propios en el que la ecuación P(lambda)x=0, que define el problema, involucra un polinomio P(lambda), de grado d, en el parámetro lambda del autovalor, y d+1 coeficientes matriciales. A su vez, el problema polinómico de valores propios es un caso particular del problema no lineal de valores propios, T(lambda)x=0, en el que T es una función matricial no lineal. Estos problemas aparecen en diversas áreas de aplicación como acústica, mecánica de fluidos, análisis de estructuras, o fotónica. Esta tesis se centra en el estudio de métodos para la resolución numérica del problema polinómico de valores propios, así como la adaptación de dichos métodos al caso más general no lineal. Principalmente, se consideran métodos de proyección, que son apropiados para el caso de matrices dispersas de gran dimensión cuando se requiere solo un pequeño porcentaje de los valores y vectores propios. Los algoritmos se estudian desde el punto de vista de la computación de altas prestaciones, teniendo en consideración aspectos como la eficiencia (computacional y de memoria) y la computación paralela. SLEPc, Scalable Library for Eigenvalue Problem Computations, es una biblioteca software para la resolución de problemas de valores propios de gran dimensión en paralelo. Es de propósito general y puede usarse para problemas estándares y generalizados, simétricos y no simétricos, con aritmética real o compleja. Como fruto de esta tesis, se han desarrollado diversos solvers para problemas polinómicos y no lineales, los cuales se han incluido en las últimas versiones de este software. Por un lado, se abordan métodos basados en la linealización del problema polinómico, que resuelven un problema lineal equivalente de dimensión varias veces la del inicial. Entre ellos se destaca el método TOAR, que representa la base del subespacio de búsqueda de una forma eficiente en términos de memoria, y es adecuado para manejar el aumento de dimensión del problema lineal. La tesis también propone variantes específicas para el caso particular de matrices simétricas. En todos estos métodos se consideran diversos aspectos para dotar a las implementaciones de robustez y flexibilidad, tales como transformaciones espectrales, escalado, y técnicas de extracción. Además de los métodos de linealización, se proponen métodos de tipo Newton, como el método de Jacobi-Davidson con deflación y el método de Newton para pares invariantes. Por sus características, este último no suele utilizarse como un método en sí mismo sino como técnica de refinamiento de las soluciones obtenidas con otro método. Los métodos anteriores pueden aplicarse a la resolución del problema no lineal, utilizando técnicas como la interpolación polinómica o racional, siendo necesario en algunos casos adaptar los algoritmos. La tesis cubre también estos casos. Para todos los algoritmos considerados se han realizado implementaciones paralelas en SLEPc, y se ha estudiado su comportamiento numérico y sus prestaciones paralelas en problemas procedentes de aplicaciones reales. / El problema polinòmic de valors propis apareix en moltes àrees de la computació científica i tècnica. Pot veure's com una generalització del problema lineal de valors propis en el qual l'equació P(lambda)x=0, que defineix el problema, involucra un polinomi P(lambda), de grau d, en el paràmetre lambda de l'autovalor, i d+1 coeficients matricials. Al seu torn, el problema polinòmic de valors propis és un cas particular del problema no lineal de valors propis, T(lambda)x=0, en el qual T és una funció matricial no lineal. Aquests problemes apareixen en diverses àrees d'aplicació com a acústica, mecànica de fluids, anàlisis d'estructures, o fotònica. Aquesta tesi se centra en l'estudi de mètodes per a la resolució numèrica del problema polinòmic de valors propis, així com l'adaptació d'aquests mètodes al cas més general no lineal. Principalment, es consideren mètodes de projecció, que són apropiats per al cas de matrius disperses de gran dimensió quan es requereix solament un reduït percentatge dels valors i vectors propis. Els algorismes s'estudien des del punt de vista de la computació d'altes prestacions, tenint en consideració aspectes com l'eficiència (computacional i de memòria) i la computació paral·lela. SLEPc, Scalable Library for Eigenvalue Problem Computations, és una biblioteca software per a la resolució de problemes de valors propis de gran dimensió en paral·lel. És de propòsit general i pot usar-se per a problemes estàndards i generalitzats, simètrics i no simètrics, amb aritmètica real o complexa. Com a fruit d'aquesta tesi, s'han desenvolupat diversos solvers per a problemes polinòmics i no lineals, els quals s'han inclòs en les últimes versions d'aquest software. D'una banda, s'aborden mètodes basats en la linealització del problema polinòmic, que resolen un problema lineal equivalent de dimensió diverses vegades la de l'inicial. Entre ells es destaca el mètode TOAR, que representa la base del subespai de cerca d'una forma eficient en termes de memòria, i és adequat per a manejar l'augment de dimensió del problema lineal. La tesi també proposa variants específiques per al cas particular de matrius simètriques. En tots aquests mètodes es consideren diversos aspectes per a dotar a les implementacions de robustesa i flexibilitat, tals com a transformacions espectrals, escalat, i tècniques d'extracció. A més dels mètodes de linealització, es proposen mètodes de tipus Newton, com el mètode de Jacobi-Davidson amb deflació i el mètode de Newton per a parells invariants. Per les seues característiques, aquest últim no sol utilitzar-se com un mètode en si mateix sinó com a tècnica de refinament de les solucions obtingudes amb un altre mètode. Els mètodes anteriors poden aplicar-se a la resolució del problema no lineal, utilitzant tècniques com la interpolació polinòmica o racional, sent necessari en alguns casos adaptar els algorismes. La tesi cobreix també aquests casos. Per a tots els algorismes considerats s'han realitzat implementacions paral·leles en SLEPc, i s'ha estudiat el seu comportament numèric i les seues prestacions paral·leles en problemes procedents d'aplicacions reals. / Campos González, MC. (2017). Implementación paralela de métodos iterativos para la resolución de problemas polinómicos de valores propios [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/86134 / TESIS

Submitted by Hellen Luz (hellencrisluz@gmail.com) on 2017-07-04T18:45:28Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_EstrategiasParalelismoGpgpu.pdf: 1964519 bytes, checksum: 90e88c79511a80729d175e52be5bc30b (MD5) / Approved for entry into archive by Irvana Coutinho (irvana@ufpa.br) on 2017-08-18T13:25:09Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_EstrategiasParalelismoGpgpu.pdf: 1964519 bytes, checksum: 90e88c79511a80729d175e52be5bc30b (MD5) / Made available in DSpace on 2017-08-18T13:25:09Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_EstrategiasParalelismoGpgpu.pdf: 1964519 bytes, checksum: 90e88c79511a80729d175e52be5bc30b (MD5) Previous issue date: 2017-03-23 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O cálculo do fluxo de carga provê informações fundamentais em um sistema elétrico de potência, informações necessárias para que sejam realizados estudos nos sistemas. No entanto, o fluxo de carga só pode ser realizado em estado de regime permanente. Caso o sistema sofra alguma alteração, seja por variação nas cargas ou modificações dos equipamentos de controle, este cálculo é necessário ser refeito. Por essa necessidade, de constantemente ter que realizar o controle no fluxo de carga, começou-se uma busca por otimizar o tempo necessário desta tarefa. Uma das soluções abordadas para isso foi a utilização de computação paralela, a qual começou a ser utilizada a General Purpose Graphics Processing Unit (GPGPU) como uma alternativa de melhor custo benefício para execuções em arquiteturas paralelas, que consiste na utilização de Graphic Processing Units (GPU) não somente para processamento gráfico, mas também para propósitos gerais. Diversos trabalhos têm tirado proveito da utilização de GPGPU nos cálculos do fluxo de carga, contudo, não há um consenso sobre qual estratégia utilizar para paralelizar neste tipo de hardware, ficando a cargo de cada autor o trabalho de desenvolver seu próprio método, dificultando a utilização da arquitetura para a implementação desses cálculos, tanto para fins acadêmicos, quanto para o mercado. Pela falta de um consenso e palas divergências encontradas nos trabalhos, esta dissertação visa analisar as etapas do fluxo de carga, identificando quais estão mais aptas a paralelização em GPGPU com o intuito de realizar múltiplos cálculos do fluxo de carga simultâneos e reduzir o tempo necessário para o processamento, difundindo uma estratégia eficiente para sistemas de larga escala no mercado e no meio acadêmico, facilitando a replicação para trabalhos futuros com utilização de metaheurísticas para otimização de sistemas elétricos de potência. / The load flow calculation provides fundamental information for an electric power system. However, the load flow can only be carried out in the steady state, in the event of a system suffering any change, by variation in the loads or modifications of the control equipment, this calculation is necessary to be redone. Because of this need, frequently have to perform the load flow, a research has begun to optimize the time needed for this task. A General-Purpose Graphic Processing Unit (GPGPU) as a cost-effective alternative to parallel architecture runs, which has a GPU not only for graphics purposes but also for general purposes. Several works were taken for the use of GPGPU in load flow calculations, there is no consensus on the content of the material, being in charge of each one of the work of its own method, making it difficult to use the architecture for an implementation of calculations, both for academic purposes and for the market. Due to the lack of consensus and differences found in the work, this dissertation aims to analyze the steps of the load flow, identifying which is more suitable to parallelize in GPGPU in order to perform simultaneous load flow calculations and reduces the time required for the processing, an efficient strategy for large scale systems in the market and not academic environment, facilitate the replication for future works using metaheuristics for optimization of power electrical systems.