docDefinição e avaliação de métricas para solucionadores SAT
download 
Denúncia 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
