Paralelismo como solução para redução de complexidade de problemas combinatoriais

• Ano de defesa: 2011
• Autor(a) principal: Nobre, Ricardo Holanda
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual do Ceará
• Palavras-chave em Português: Computação; Mochila Booleana; Paralelismo
• Link de acesso: https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=70961

A constante demanda por alto desempenho computacional tem ganhado espaço, acelerada pelos mais diversos setores da atuação humana, que buscam na computação a resolução de problemas até então considerados insolúveis ou cuja resolução exige um grande esforço computacional, principalmente devido à complexidade matemática inerente aos mesmos. Não obstante a isso, a resolução de um problema através de sistemas computacionais exige cada vez mais capacidade de processamento, o que, por sua vez, constitui um limite nos atuais processadores, aliado ao fato de que os sistemas computacionais convencionais não resolvem determinadas classes de problemas em tempo polinomial, como é o caso do problema da mochila da otimização combinatória. O presente trabalho analisa a utilização massiva do paralelismo como uma solução viável e factível, em si mesma, para reduzir a complexidade de tempo de vários tipos de problemas, dentre eles os problemas combinatórios, quando a dimensão dos dados de entrada é menor ou igual ao número de processadores paralelos. Aborda-se esta temática sobre o prisma do ''pensar em paralelo'', em contraponto a construção seqüencial dos algoritmos, culminando na propositura de um novo algoritmo para o problema da mochila (0-1), idealizado originalmente para ser executado em paralelo, e cuja complexidade de tempo é bem superior aos atuais algoritmos exatos existentes.Palavras-chaves: Paralelismo, redução de complexidade, problemas combinatoriais, arquitetura massivamente paralela, GPU Computing, CUDA, mochila booleana.