Definição e avaliação de métricas para solucionadores SAT

Сomentários

Transcrição

Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Definição e avaliação de métricas para
solucionadores SAT
Fernando Augusto Fernandes Braz
Orientador: Mark Alan Junho Song
Departamento de Ciência da Computação
PUC Minas
9 de dezembro de 2009
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Sumário
1
Introdução
Motivação
Justificativa
Objetivos
2
Revisão de Literatura
Abordagem do DPLL
Métricas para Verificação Formal
3
Definição e Avaliação de Métricas para Solucionadores SAT
Descrição das Métricas
Conjunto Unificado de Métricas
4
Estudo de Caso
Testes Realizados
5
Conclusão
Trabalhos Futuros
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Motivação
Justificativa
Objetivos
Introdução
Fórmula booleana ϕ : SAT ou UNSAT
Solução trivial: dispor variáveis em uma árvore de decisão
Satisfabilidade booleana é um problema NP-Completo
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Motivação
Justificativa
Objetivos
Motivação
Vários solucionadores e heurísticas: processo de resolução
divergente; dificuldade para comparar resultados
Ausência de informações: aspecto interno do solucionador frente
às classes de problemas
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Motivação
Justificativa
Objetivos
Justificativa
Melhor entendimento do problema e das soluções
Identificação de alternativas para pesquisa
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Motivação
Justificativa
Objetivos
Objetivos
Características de cada solução
Abordagem adequada para cada classe de problemas
Comportamento de soluções distintas para um mesmo tipo de
problema
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Abordagem do DPLL
Métricas para Verificação Formal
Revisão de Literatura
Solução DPLL existe desde 1962
Poucas abordagens diferentes (Stålmarck e BDD)
SAT Competition e benchmarks
Classes de Problemas (reais, artesanais e aleatórios)
Aplicações para SAT: verificação de processadores, síntese
lógica, etc.
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Abordagem do DPLL
Métricas para Verificação Formal
Abordagem do DPLL
Motores decide, deduz e diagnostica
Backtrack para sair de estados UNSAT
Aprendizado de cláusulas: evitar conflitos recorrentes
BCP (Boolean Constraint Propagation)
Grafo de Implicação: detectar conflitos
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Abordagem do DPLL
Métricas para Verificação Formal
Métricas para Verificação Formal
Tempo de execução e uso de memória
Revelam pouco sobre o aspecto interno
Ausência de trabalhos para SAT envolvendo métricas
Consulta às métricas de Engenharia de Software
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Descrição das Métricas
Conjunto Unificado de Métricas
Definição e Avaliação de Métricas para Solucionadores SAT
Escolha das abordagens: zChaff, Rsat e Minisat
Critérios de escolha: vencedores em competições, eficientes
para diferentes classes de problema
Levantamento das métricas e Conjunto Unificado de Métricas
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Descrição das Métricas
Conjunto Unificado de Métricas
zChaff
Vencedor de 2002
Até pouco tempo estado da arte
VSIDS (prioriedade reduzida em 50% a cada mil conflitos)
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Descrição das Métricas
Conjunto Unificado de Métricas
Rsat
Vencedor de 2007 (real)
Estruturas de dados leves
Progress Saving: atribuições anteriores a um conflito são
armazenadas
Pré-processador SATElite
VSIDS (baseado no zChaff)
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Descrição das Métricas
Conjunto Unificado de Métricas
Minisat
Vencedor de 2007 (real e aleatório)
Atual estado da arte
VSIDS agressivo (prioriedade reduzida em 5% a cada conflito)
Backtrack não-cronológico
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Descrição das Métricas
Conjunto Unificado de Métricas
Descrição das Métricas
Métricas exclusivas: reordenações (zChaff), máximo de
literais/cláusulas aprendidas (Minisat), etc.
Métricas comuns: cláusulas aprendidas, reinícios, propagações,
memória, tempo de execução, etc.
11 Métricas comuns compondo o Conjunto Unificado de Métricas
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Descrição das Métricas
Conjunto Unificado de Métricas
Conjunto Unificado de Métricas
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Estudo de Caso
Testes Benchmark da SAT Competition e IBM
Ambiente de Testes uniforme (mesma máquina e configurações)
Tamanho 6= Complexidade
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Testes Realizados
36 Testes para diferentes Classes de Problemas:
13 Problemas Reais (microprocessadores da IBM)
13 Problemas Artesanais (jogos de paridade em grafos)
10 Problemas Aleatórios (OnTreshold, 7-SAT)
Tempos de execução variando de instântaneo a várias horas
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Testes Artesanais
Métricas
Cláusulas atuais
Cláusulas originais
Cláusulas aprendidas
Cláusulas eliminadas
Literais atuais
Literais conflito
Variáveis
Reinícios
Propagações
Memória
Tempo de execução
Solucionadores
zChaff
Rsat
Minisat
54
53
53
53
53
53
1
0
0
0
0
53
115
114
114
1
0
1
27
27
27
0
0
1
13
3
23
134944 4944 3860000
0
0
0
Tabela: instance_n2_i2_pp.cnf (artesanal)
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Observações Testes Artesanais
Necessidade de maior precisão
Tempo de execução idêntico
Solucionador não importa para instâncias triviais
Rsat superior para instâncias artesanais
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Testes Aleatórios
Métricas
Cláusulas atuais
Cláusulas originais
Cláusulas aprendidas
Cláusulas eliminadas
Literais atuais
Literais conflito
Variáveis
Reinícios
Propagações
Memória
Tempo de execução
zChaff
88865
4005
1823088
1738228
1534058
34110602
45
2588
23872459
125107472
4264.27
Solucionadores
Rsat
Minisat
9719
3717
4005
4005
3801661
2173
3792191
2852987
91872
31112
54664356
38535440
45
45
1533
24
7848492
22052582
36350924
6740000
38553.12492
251.336
Tabela: S2067396253-13.UNSAT.shuffled.cnf (aleatória)
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Observações Testes Aleatórios
zChaff apresenta tempos medianos frente aos demais
Rsat foi desenvolvido voltado para problemas reais,
comprometendo seu desempenho para problemas aleatórios
Minisat superior para problemas aleatórios (menos reinícios, uso
de memória e tempo de execução)
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Testes Reais
Métricas
Cláusulas atuais
Cláusulas originais
Cláusulas aprendidas
Cláusulas eliminadas
Literais atuais
Literais conflito
Variáveis
Reinícios
Propagações
Memória
Tempo de execução
Solucionadores
zChaff
Rsat
Minisat
72797
56572
54486
65728
65415
65728
7575
22659
8100
506
31502
547661
484065
345706
340624
369114
584946
214560
13215
13215
13215
2
22
10
6888316
71232
5375397
8823120 3823868 8420000
5.85037 18.30914
3.2082
Tabela: bmc-ibm-13.cnf (real)
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Testes Realizados
Observações Testes Reais
Problemas reais apesar de grandes são triviais
Poucos conflitos e reinícios frente a problemas aleatórios, por
exemplo
Solucionadores apresentaram resultados similares
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Trabalhos Futuros
Conclusão
Constatações realizadas na área, como por exemplo, problemas
reais apresentarem poucos conflitos, logo, menos reinícios
Para instâncias pequenas qualquer solucionador pode ser
utilizado
Para problemas artesanais orienta-se utilizar o Rsat, e para
problemas aleatórios o Minisat
Problemas reais apresentaram resultados equivalentes entre os
solucionadores
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Trabalhos Futuros
Trabalhos Futuros
Expansão do Conjunto Unificado de Métricas
Novos solucionadores
Novos paradigmas
Uso de outros benchmarks
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT
Introdução
Revisão de Literatura
Definição e Avaliação de Métricas para Solucionadores SAT
Estudo de Caso
Conclusão
Trabalhos Futuros
Perguntas
Fernando Augusto Fernandes Braz Orientador: Mark Alan Junho Song
Definição e avaliação de métricas para solucionadores SAT