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.
| Identifer | oai:union.ndltd.org:IBICT/urn:repox.ist.utl.pt:RI_PUC_RS:oai:meriva.pucrs.br:10923/1477 |
| Date | January 2010 |
| Creators | Milani, Cleber Roberto |
| Contributors | Fernandes, Luiz Gustavo Leão |
| Publisher | Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da PUC_RS, instname:Pontifícia Universidade Católica do Rio Grande do Sul, instacron:PUC_RS |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds