Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Qualificação Mestrado

Qualificação do Mestrado
by

Eduardo Moreira

on 5 August 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Qualificação Mestrado

Aluno: Eduardo Batista Gomes Moreira
Orientador: Cláudio Nogueira de Meneses

Algoritmos Paralelos em GPUs para Problemas de
Programação Quadrática Binária Irrestrita

Introdução
Trabalhos
Anteriores

Transformações
para UQP

Programação Paralela usando GPUs
Métodos para
resolver o UQP

Resultados
Computacionais

Centro de Matemática, Computação e Cognição
Agradecimentos
Problema Quadrático Binário Irrestrito
Unconstrained Binary Quadratic Problem
(1968) Peter L. Hammer
(1992) Panos M. Pardalos
(1994) Jue Xue
(1999) J. E. Beasley
(1998-Hoje) Fred Glover
(2010) Jianjun Gao, Chunli Liu
(2011) Shenshen Gu
Complexidade Computacional
O UQP pertence a classe de complexidade NP-Difícil
Algumas instâncias podem ser resolvidas em tempo polinomial
UQP como um framework
Vários problemas de otimização combinatória podem ser vistos sob a forma UQP
UQP
Multiple Knapsack Problems
Maximum Diversity Problems
Asymmetric Assignment Problems
Task Allocation Problems
P-Median Problems
Maximum Clique Problems
(Problema das P-Medianas)
(Problema de Alocação de Tarefas)
(Problema da Mochila Múltipla)
(Problema da Máxima Diversidade)
(Problema de Atribuição Assimétrica)
(Problema da Clique Máxima)
Função Objetivo Linear
Função Objetivo Quadrática
nVidia GeForce GTX 680
GPUs são placas gráficas com muitos núcleos que geralmente são utilizados para processamento de imagens.
Multicore e Manycore
Fonte: nVidia
Fonte: nVidia
Evolução das GPUs
Ambiente 1
Computador
Dell Precision T3500, processador Intel Xeon 64 bits, 4 núcleos de 2.53 GHz, 5.8 GB de Memória RAM.
Nvidia Quadro FX 1800, 1.3 GHz, 64 bits, 8 Multi-processadores, 64 núcleos, 768 MB de Memória Global.
Linux Ubuntu 11.04
GPU
Sistema Operacional
Instâncias de Teste
ORLib
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/bqpinfo.html
Grupo de instâncias
60 instâncias agrupadas em conjuntos de 50, 100, 250, 500, 1000 e 2500 variáveis.
Densidade
Aproximadamente 10%
Método Exato
Tabu Search (TS)
Para instâncias com mais de 100 variáveis o solver retornou erro de falta de memória.
Segundo Fred Glover, TS é uma estratégia feita para ajudar heurísticas a não ficarem presas em ótimos locais.
Pseudo-código do Tabu Search
Variable Neighborhood Search (VNS)
Pseudo-código do VNS
O VNS é uma metaheurística com a finalidade de resolver problemas de otimização global e combinatória.
Esta técnica baseia-se na mudança sistemática de vizinhanças junto com uma estratégia de busca local.
TS x VNS
Tabu Search Sequencial x Paralelo
Speedup no Ambiente 1
Tabu Search
Simulated Annealing
Variable Neighborhood Search
Algoritmos Genéticos
GRASP
Colônia de Formigas
Métodos Exatos
Branch-and-Bound
Branch-and-Cut
Compiladores
Versão sequencial: GCC
Versão paralela: NVCC
CUDA Capability: 1.1
Ambiente 2
Computador
Cooler Master, processador Intel Core i7 3930k, 12 núcleos de 3.2 GHz, 32 GB de Memória RAM.
Nvidia EVGA GeForce GTX 680, 1006 MHz, 64 bits, 8 SMX, 1536 núcleos, 2 GB de Memória Global.
Linux Ubuntu 11.10
GPU
Sistema Operacional
Compiladores
Versão sequencial: GCC
Versão paralela: NVCC
CUDA Capability: 3.0
Progresso e
Cronograma

Ambiente 1
Ambiente 2
Tabu Search
Tabu Search Sequencial x Paralelo
Comparação entre os ambientes
Atividades realizadas
Cronograma
Próximas
Atividades
1
2
3
II ERAD-SP (07/2011)
XVI ELAVIO (02/2012)
III ERAD-SP (07/2012)
XVI CLAIO / XLIV SBPO (09/2012)
Visita ao ICMC-USP (10/2012)
Visita ao DCC-IME-USP (11/2012)
Testar instâncias com matrizes densas
Implementar métodos exatos
Visitar o DCC-UFMG
1. Revisão bibliográfica
2. Implementação sequencial de métodos heurísticos
3. Implementação de métodos heurísticos usando GPUs
4. Implementação de métodos exatos sequenciais
5. Implementação de métodos exatos usando GPUs
6. Testes computacionais e análise de resultados
7. Escrita da dissertação
8. Defesa da dissertação
Métodos Heurísticos
Re-cálculo do valor
da função objetivo

Exemplo
Ambientes de
Experimentos

Solver do método exato
IBM ILOG CPLEX v12.4
N(x), Vizinhanças de uma solução
1-Flip
2-Flip
Comparações entre o Tabu Search Sequencial e o Paralelo em escala de tempo logarítmica
Comparações entre o Tabu Search Sequencial e o Paralelo em escala de tempo logarítmica
Speedup entre Ambiente 1 e Ambiente 2
Exemplo de um Tabu Search
Exemplo de um VNS
x
(2)
x
(3)
x
(4)
x
(5)
x
(7)
x
(6)
x
(1)
x
(5)
Full transcript