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

Dissertação de Mestrado

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

Eduardo Moreira

on 8 August 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Dissertação de 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
(2013) 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
K-Coloring Problem
Generalized Independent Set
Manufacturer's Pallet Loading Problem
Set Partitioning
Set Packing Problem
Maximum Clique Problems
(Empacotamento de Conjuntos)
(Particionamento de Conjuntos)
(Coloração de Vértices em um Grafo com K Cores)
(Conjunto Independente Generalizado)
(Carregamento de Objetos em Estrados)
(Problema do Clique Máximo)
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
Evolução das GPUs
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%
Tabu Search (TS)
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.
Fonte: NVIDIA
Tabu Search
Simulated Annealing
Variable Neighborhood Search
Algoritmos Genéticos
GRASP
Colônia de Formigas
Métodos Exatos
Branch-and-Bound
Branch-and-Cut
Ambiente de experimentos
Computador
Processador Intel Core i7 3930k, 6 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
nvcc release 5.0
Trabalhos Futuros
Tabu Search Paralelo
Métodos Heurísticos
Contribuições
Solver do método exato
IBM ILOG CPLEX v12.4
N(x), Vizinhanças de uma solução
1-Flip
2-Flip
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)
Função Objetivo Linear
Função Objetivo Quadrática
Branch and Bound (B&B)
Pseudo-código do B&B
O B&B é uma estratégia de divisão e conquista que utiliza um método de enumeração implícita.
x = 0
0
x = 1
x = 0
x = 1
x = 0
x = 1
0
1
1
1
1
-8
-8
0
-3
2
S
1
S
2


3
S
4
S
5
6
7
Pesquisa
Resultados Teóricos
Recálculo do Valor da Função Objetivo com Mudança do Valor de Uma Variável
Implementações
em CUDA
Resumo dos Métodos de Recálculo
Recálculo do Valor da Função Objetivo com Mudanças nos Valores de Duas Variáveis
Cálculo do Limitante Inferior à f(x) no Branch and Bound
Tabu Search
Branch and Bound
Classe Difícil
Proposta no artigo de Rodgers e Pardalos (1989)
Fórmula
Densidade
100%
Teóricos
Implementações
Criar uma nova função de Limitante Inferior para o B&B;
Criar fórmulas de recálculo do Limitante Inferior no B&B para outras situações;
Fazer um estudo poliédrico do espaço de soluções do UQP linearizado.
Implementar um B&B com recálculo do Limitante Inferior;
Fazer um balanceamento de carga entre as threads;
Utilizar uma representação decimal para o vetor solução;
Implementar o TS e o B&B de maneira distribuída com MPI e CUDA;
Implementar uma busca local paralela no TS;
Melhorar a implementação sequencial do VNS e implementá-lo em paralelo com GPUs.
Métodos Heurísticos
Métodos Exatos
Tabu Search x VNS
CPLEX
Branch and Bound
Métodos
Recálculo do Limitante Inferior
(percentual de coeficientes não nulos)
(2013) Francisco Chicano
(2013) Fan Wang
Assumindo problema de minimização

S
S
S
Full transcript