Orientador: Andre Luiz Morelato França

Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica

Resumo: Neste trabalho propõe-se uma metodologia para a decomposição da etapa de solução direta de um sistema de equações linear esparso Ax = b, obtendo-se um conjuntode tarefas independentes que podem ser processadas em paralelo usando máquinas multiprocessadores. Atualmente computadores...

Resumo: Neste trabalho propõe-se uma metodologia para a decomposição da etapa de solução direta de um sistema de equações linear esparso Ax = b, obtendo-se um conjuntode tarefas independentes que podem ser processadas em paralelo usando máquinas multiprocessadores. Atualmente computadores multiprocessadores tendem a apresentar baixo custo e desempenho comparável aos supercomputadores. Esta nova tecnologia poderá ser incorporada proximamente aos centros de controle em tempo real de sistemas de energia elétrica. A metodologia baseia-se na utilização da matriz de fatores inversos (W) particionada. O esquema de particionamento proposto consiste em dividir a matriz W de acordo com a profundidade dos nós na árvore dos caminhos de fatoração da matriz A. Neste esquema todas as informações necessárias para gerar as partições são obtidas diretamente da árvore de fatoração, sendo portanto de fácil implementação. Os elementos de todas as partições, exceto da última, podem ser obtidos diretamente da matriz L, sem necessidade de cálculos adicionais. O esquema de particionamento garante que novos elementos diferentes de zero ("fill-ins" adicionais) serão gerados apenas na última partição porque propositalmente esta última partição quebra relações de precedência. As substituições "forward" e "backward" são realizadas por linhas e por partições, e a estratégia proposta de divisão de tarefas atribui a um processador todo o conjunto de operações (multiplicação/adição) de uma linha em uma mesma partição. Na última partição pode-se agrupar as etapas "forward", diagonal e "backward", tornando a solução desta partição uma única etapa de multiplicação de uma matriz Wup (cheia) pelo vetor b. Isto é vantajoso em uma série de casos. A metodologia proposta transfere a velocidade da solução para a capacidade de realizar operações de ponto flutuante de cada processador, ou seja, à medida que processadores mais poderosos forem sendo desenvolvidos mais rápida será a solução em paralelo do problema quase na mesma proporção. Uma solução direta que use uma metodologia como a proposta neste trabalho, consegue uma redução nos tempos de comunicação entre processadores, como demonstra os resultados obtidos em uma implementação num computador multiprocessador com arquitetura de memória híbrida (local e global)

Abstract: This thesis describes a methodology for decomposing the repeat solution process of the equation Ax = b into independent tasks to be done in parallel, based on the matrix inverse factors (W-matrix) with partitions. It is a matter of fact that low-cost multiprocessor computers are now...

Abstract: This thesis describes a methodology for decomposing the repeat solution process of the equation Ax = b into independent tasks to be done in parallel, based on the matrix inverse factors (W-matrix) with partitions. It is a matter of fact that low-cost multiprocessor computers are now available featuring supercomputer-like performances. The partitioningscheme proposed in this thesis consists of breaking up the W-matrix according the depths of the factorization path tree. In this scheme, all the information needed to generate the partitions can be obtained straightforward from the network factorization path tree. The partitioning algorithm is simple and ease to implement. The elements of Wj matrices, except the last partition, can be obtained directly from L-matrix elements, not requiring extra work. The proposed scheme guarantees that additionaJ fills will be only created in the last partition. The forward and backward solutions are performed by rows, and the strategy proposed is to schedule on each processor the operations corresponding to a row of each partition. It should be kept in mind that the multiprocessor environments are equipped with powerful unit processors and then it seems a sound strategy to perform the . mult-add elementary operations inside the hardware in order to exploit its computing efficiency. This strategy seeks to match the parallel algorithm to the paralleJ architecture. The precedent relations - that give rise to delays - are replaced by mult-add operations performed inside the processor node without external communication. In the last partition, the forward, diagonal and backward solutions may be gathered, and so all the operations can be expressed as the product of matrix W1pby the updated components of vector b. The performance results show that the potentiaJ speedup of the solution time is essentially bounded by the floating point operation capability of each processor, denoting that the methodology is a suitable way to exploit the growing power of the computing technology