Publicação
Soluções para os problemas da soma máxima e do k-ésimo menor elemento de uma sequência usando o modelo BSP/CGM
| Resumo: | Neste trabalho são propostos algoritmos paralelos para os seguintes problemas: a subsequência de soma máxima, a submatriz de soma máxima, o hiper-retangulo de soma máxima e a seleção do k-esimo menor elemento de um sequencia não ordenada. Todos os problemas tratados possuem aplicações em diversas áreas da ciência, com destaque para biologia computacional, visão computacional, analise de volumes rochosos e de ordem. No projeto de nossos algoritmos adotamos uma extensão do modelo BSP/CGM de computação paralela e mostramos que, além do ambiente de memoria distribuida, o modelo BSP/CGM também pode ser utilizado em arquiteturas com memoria compartilhada e com múltiplos núcleos, tais como as GPUs. Diferentemente de soluções anteriores, nossos algoritmos e implementações utilizam novas estratégias na solução de cada problema. Apresentamos algoritmos paralelos para subproblemas relacionados ao problema da soma máxima, para os quais, de acordo com o nosso melhor conhecimento, a literatura não apresenta soluções no modelo BSP/CGM. As implementações foram construídas utilizando CUDA, MPI e OpenMP. Por fim, destacamos que nossos algoritmos são competitivos, quando comparados com as respectivas soluções sequenciais e paralelas já existentes. |
|---|---|
| Autores principais: | Lima, Anderson Corrêa de |
| Assunto: | Algorítmos Paralelos Parallel Algorithms Linguagem de Programação (Computadores) Programming Languages (Electronic Computers) Computação Computer Science |
| Ano: | 2016 |
| País: | Brasil |
| Tipo de documento: | tese de doutoramento |
| Tipo de acesso: | acesso aberto |
| Instituição associada: | IBICT |
| Idioma: | português |
| Origem: | Oasisbr |
| Resumo: | Neste trabalho são propostos algoritmos paralelos para os seguintes problemas: a subsequência de soma máxima, a submatriz de soma máxima, o hiper-retangulo de soma máxima e a seleção do k-esimo menor elemento de um sequencia não ordenada. Todos os problemas tratados possuem aplicações em diversas áreas da ciência, com destaque para biologia computacional, visão computacional, analise de volumes rochosos e de ordem. No projeto de nossos algoritmos adotamos uma extensão do modelo BSP/CGM de computação paralela e mostramos que, além do ambiente de memoria distribuida, o modelo BSP/CGM também pode ser utilizado em arquiteturas com memoria compartilhada e com múltiplos núcleos, tais como as GPUs. Diferentemente de soluções anteriores, nossos algoritmos e implementações utilizam novas estratégias na solução de cada problema. Apresentamos algoritmos paralelos para subproblemas relacionados ao problema da soma máxima, para os quais, de acordo com o nosso melhor conhecimento, a literatura não apresenta soluções no modelo BSP/CGM. As implementações foram construídas utilizando CUDA, MPI e OpenMP. Por fim, destacamos que nossos algoritmos são competitivos, quando comparados com as respectivas soluções sequenciais e paralelas já existentes. |
|---|
Atividades financiadas
Não foram encontrados projetos financiados.