| |
| Acadêmico(a): Roger William Weber |
| Título: Ferramenta para Execução de Scripts OPL para otimização Combinatória em GPU |
| |
| Introdução: |
Otimização combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos. Em um problema de otimização combinatória tem-se uma função objetivo e um conjunto de restrições, ambos relacionados às variáveis de decisão. Os valores possíveis das variáveis de decisão são delimitados pelas restrições impostas sobre estas variáveis, formando um conjunto discreto (finito ou não) de soluções factíveis a um problema. Segundo Nazareth (2004, p. 1), otimização é a arte, a ciência e a matemática de encontrar o melhor membro de um conjunto finito ou infinito de possíveis escolhas e com base em algum objetivo mensurar o mérito de cada escolha no conjunto.
Vários problemas, de acordo com IBM Software (2011a), podem ser resolvidos usando otimização combinatória, podendo citar otimização de transporte, logística, produção, gerenciamento de riscos, alocação de recursos, entre outros. Problemas de otimização combinatória podem apresentar métodos exatos e eficientes de resolução, porém alguns destes problemas têm a necessidade de métodos não exatos (heurísticos), uma vez que sua formulação ou sua resolução exata levaria a uma complexidade intratável ou indesejável. Em todos os casos, a resolução de problemas de otimização combinatória pode ser feita usando alguma linguagem de notação matemática, como Optimization Programming Language (OPL), Algebraic Modeling Programming Language (AMPL) e General Algebraic Modeling System (GAMS).
A implementação dos métodos para resolução de problemas de otimização combinatória pode utilizar algoritmos paralelos, aproveitando melhor os recursos computacionais. Mas, para usar algoritmos paralelos de forma mais efetiva deve-se ter máquinas com o maior número de processadores possível.
Neste contexto, tem-se a General Purpose Graphics Processing Unit (GPGPU) ou unidade de processamento gráfico de propósito geral. Uma GPGPU inclui o uso de uma Graphics Processing Unit (GPU), ou unidade de processamento gráfico, juntamente com uma Central Processing Unit (CPU), ou unidade de processamento central, para acelerar aplicações de uso geral, científicas e de engenharia. A combinação de CPU e GPU é poderosa porque CPUs consistem de alguns núcleos otimizados para processamento serial, enquanto GPUs consistem em milhares de núcleos menores, mais eficientes, projetados para desempenho paralelo (NVIDIA CORPORATION, 2012a). Assim, partes seriais do código são executadas na CPU, enquanto partes paralelas executam na GPU.
Diante do exposto, desenvolveu-se uma ferramenta para interpretar scripts OPL, gerando código paralelo para máquina com placa de vídeo GPU. O código será gerado em C/C++.
|
| |
|
