Un nouveau cadre diviser pour régner pour SAT distribué · Un nouveau cadre diviser pour regner...

Dolius+PeneLoPe

Un nouveau cadre diviser pour regner pourSAT distribue

Gilles Audemard, Benoıt Hoessen,Saıd Jabbour, Cedric Piette

Universite Lille-Nord de FranceCRIL - CNRS UMR 8188

Artois, F-62307 Lens{audemard,hoessen,jabbour,piette}@cril.fr

13 juin 2013

Ce travail est supporte par le CNRS et OSEO, grace au projet ISI “Pajero”.

1 / 12

Dolius+PeneLoPe

Background

Solveurs SAT

Beaucoup de solveurs de type Conflict driven clauselearning (CDCL)

CDCL cree une clause par conflit

Les redemarrages sont assez frequents

Exemple: PeneLoPe, Glucose, (p)lingeling,cryptominisat, minisat, ...

2 / 12

Dolius+PeneLoPe

Background

Solveurs SAT

Beaucoup de solveurs de type Conflict driven clauselearning (CDCL)

CDCL cree une clause par conflit

Les redemarrages sont assez frequents

Exemple: PeneLoPe, Glucose, (p)lingeling,cryptominisat, minisat, ...

2 / 12

Dolius+PeneLoPe

Background

Solveurs SAT

Beaucoup de solveurs de type Conflict driven clauselearning (CDCL)

CDCL cree une clause par conflit

Les redemarrages sont assez frequents

Exemple: PeneLoPe, Glucose, (p)lingeling,cryptominisat, minisat, ...

2 / 12

Dolius+PeneLoPe

Background

Solveurs SAT

Beaucoup de solveurs de type Conflict driven clauselearning (CDCL)

CDCL cree une clause par conflit

Les redemarrages sont assez frequents

Exemple: PeneLoPe, Glucose, (p)lingeling,cryptominisat, minisat, ...

2 / 12

Dolius+PeneLoPe

Background

Solveurs SAT

Beaucoup de solveurs de type Conflict driven clauselearning (CDCL)

CDCL cree une clause par conflit

Les redemarrages sont assez frequents

Exemple: PeneLoPe, Glucose, (p)lingeling,cryptominisat, minisat, ...

2 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initialeC i la clause apprise apres i conflitsS un ensemble de variablesFS une formule booleenne sur l’ensemble Sz(α) represente α ou ¬α en fonction du contexteUn noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initiale

C i la clause apprise apres i conflitsS un ensemble de variablesFS une formule booleenne sur l’ensemble Sz(α) represente α ou ¬α en fonction du contexteUn noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initialeC i la clause apprise apres i conflits

S un ensemble de variablesFS une formule booleenne sur l’ensemble Sz(α) represente α ou ¬α en fonction du contexteUn noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initialeC i la clause apprise apres i conflitsS un ensemble de variables

FS une formule booleenne sur l’ensemble Sz(α) represente α ou ¬α en fonction du contexteUn noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initialeC i la clause apprise apres i conflitsS un ensemble de variablesFS une formule booleenne sur l’ensemble S

z(α) represente α ou ¬α en fonction du contexteUn noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initialeC i la clause apprise apres i conflitsS un ensemble de variablesFS une formule booleenne sur l’ensemble Sz(α) represente α ou ¬α en fonction du contexte

Un noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Definitions

Σ la formule initialeC i la clause apprise apres i conflitsS un ensemble de variablesFS une formule booleenne sur l’ensemble Sz(α) represente α ou ¬α en fonction du contexteUn noeud est un element de calcul travaillantindependamment des autres.

3 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Comment?

Division de l’espace de recherche en utilisant FS et ¬FSPour une division j de l’espace de recherche, l’ensemble Sjsera utilise.

Un noeud devra resoudre l’instance Σn∧

j=1z(FSj ).

n∧j=1

z(FSj ) forme le guiding path (gp)

Lors de la division du travail, l’ensemble C i ,1 ≤ i ≤ n peutetre transmis

4 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Comment?

Division de l’espace de recherche en utilisant FS et ¬FS

Pour une division j de l’espace de recherche, l’ensemble Sjsera utilise.

Un noeud devra resoudre l’instance Σn∧

j=1z(FSj ).

n∧j=1

z(FSj ) forme le guiding path (gp)

Lors de la division du travail, l’ensemble C i ,1 ≤ i ≤ n peutetre transmis

4 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Comment?

Division de l’espace de recherche en utilisant FS et ¬FSPour une division j de l’espace de recherche, l’ensemble Sjsera utilise.

Un noeud devra resoudre l’instance Σn∧

j=1z(FSj ).

n∧j=1

z(FSj ) forme le guiding path (gp)

Lors de la division du travail, l’ensemble C i ,1 ≤ i ≤ n peutetre transmis

4 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Comment?

Division de l’espace de recherche en utilisant FS et ¬FSPour une division j de l’espace de recherche, l’ensemble Sjsera utilise.

Un noeud devra resoudre l’instance Σn∧

j=1z(FSj ).

n∧j=1

z(FSj ) forme le guiding path (gp)

Lors de la division du travail, l’ensemble C i ,1 ≤ i ≤ n peutetre transmis

4 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Comment?

Division de l’espace de recherche en utilisant FS et ¬FSPour une division j de l’espace de recherche, l’ensemble Sjsera utilise.

Un noeud devra resoudre l’instance Σn∧

j=1z(FSj ).

n∧j=1

z(FSj ) forme le guiding path (gp)

Lors de la division du travail, l’ensemble C i ,1 ≤ i ≤ n peutetre transmis

4 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Comment?

Division de l’espace de recherche en utilisant FS et ¬FSPour une division j de l’espace de recherche, l’ensemble Sjsera utilise.

Un noeud devra resoudre l’instance Σn∧

j=1z(FSj ).

n∧j=1

z(FSj ) forme le guiding path (gp)

Lors de la division du travail, l’ensemble C i ,1 ≤ i ≤ n peutetre transmis

4 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Architecture

Architecture centralisee: des esclaves et un maitreStrategie de vol de travailMaitre = mise en relation des esclavesEsclave = solveur SAT, prise de decision pour former leguiding pathTransfert des donnees (gp, clauses apprises) d’esclave aesclave

5 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Architecture

Architecture centralisee: des esclaves et un maitre

Strategie de vol de travailMaitre = mise en relation des esclavesEsclave = solveur SAT, prise de decision pour former leguiding pathTransfert des donnees (gp, clauses apprises) d’esclave aesclave

5 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Architecture

Architecture centralisee: des esclaves et un maitreStrategie de vol de travail

Maitre = mise en relation des esclavesEsclave = solveur SAT, prise de decision pour former leguiding pathTransfert des donnees (gp, clauses apprises) d’esclave aesclave

5 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Architecture

Architecture centralisee: des esclaves et un maitreStrategie de vol de travailMaitre = mise en relation des esclaves

Esclave = solveur SAT, prise de decision pour former leguiding pathTransfert des donnees (gp, clauses apprises) d’esclave aesclave

5 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Architecture

Architecture centralisee: des esclaves et un maitreStrategie de vol de travailMaitre = mise en relation des esclavesEsclave = solveur SAT, prise de decision pour former leguiding path

Transfert des donnees (gp, clauses apprises) d’esclave aesclave

5 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Architecture

Architecture centralisee: des esclaves et un maitreStrategie de vol de travailMaitre = mise en relation des esclavesEsclave = solveur SAT, prise de decision pour former leguiding pathTransfert des donnees (gp, clauses apprises) d’esclave aesclave

5 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Division

M

Ej

E E

E

E

Ei

6 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Division

M

Ej

E E

E

E

Ei

6 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Division

M

Ej

E E

E

E

Ei

6 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Division

M

Ej

E E

E

E

Ei

6 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Formation du guiding path

le guiding path ne peut etre unsatdiviser de maniere pertinente

7 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Formation du guiding path

le guiding path ne peut etre unsat

diviser de maniere pertinente

7 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Formation du guiding path

le guiding path ne peut etre unsatdiviser de maniere pertinente

7 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Difficultes avec guiding path

diviser Σ = (α ∧ a) ∨ (α ∧ ¬a) en prenant a et ¬aeffet ping pong

2.5

2.5 0.01

2.5 0.01

2.5 0.01

2.5 0.01

1.5 0.01

a

b

c

d

e

¬b

¬a

¬c

¬d

¬e

8 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Difficultes avec guiding path

diviser Σ = (α ∧ a) ∨ (α ∧ ¬a) en prenant a et ¬a

effet ping pong

2.5

2.5 0.01

2.5 0.01

2.5 0.01

2.5 0.01

1.5 0.01

a

b

c

d

e

¬b

¬a

¬c

¬d

¬e

8 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Difficultes avec guiding path

diviser Σ = (α ∧ a) ∨ (α ∧ ¬a) en prenant a et ¬aeffet ping pong

2.5

2.5 0.01

2.5 0.01

2.5 0.01

2.5 0.01

1.5 0.01

a

b

c

d

e

¬b

¬a

¬c

¬d

¬e

8 / 12

Dolius+PeneLoPe

Resoudre SAT en distribue

Difficultes avec guiding path

diviser Σ = (α ∧ a) ∨ (α ∧ ¬a) en prenant a et ¬aeffet ping pong

2.5

2.5 0.01

2.5 0.01

2.5 0.01

2.5 0.01

1.5 0.01

a

b

c

d

e

¬b

¬a

¬c

¬d

¬e

8 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera

- VSIDS- Changement de polarite

Avant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaire

Deux heuristiques pour la selection de la variable surlaquelle on divisera

- VSIDS- Changement de polarite

Avant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera

- VSIDS- Changement de polariteAvant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera- VSIDS

- Changement de polariteAvant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera- VSIDS- Changement de polarite

Avant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera- VSIDS- Changement de polariteAvant de diviser son travail, un esclave doit travailler auminimum 2,5 secondes

Le nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera- VSIDS- Changement de polariteAvant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avance

Communication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Details

Pour l’instant, FS est une clause unitaireDeux heuristiques pour la selection de la variable surlaquelle on divisera- VSIDS- Changement de polariteAvant de diviser son travail, un esclave doit travailler auminimum 2,5 secondesLe nombre d’esclaves ne doit pas etre connu a l’avanceCommunication via TCP/IP

9 / 12

Dolius+PeneLoPe

Implementation

Resultats

100

120

140

160

180

200

220

0 1 2 3 4 5 6 7

nb s

olu

tions

8 workers, 300 instances, max 1200 sec par instance

10 / 12

Dolius+PeneLoPe

Implementation

Resultats

100

120

140

160

180

200

220

0 1 2 3 4 5 6 7

nb s

olu

tions

8 workers, 300 instances, max 1200 sec par instance

10 / 12

Dolius+PeneLoPe

Implementation

Resultats

100

120

140

160

180

200

220

0 1 2 3 4 5 6 7

nb s

olu

tions

8 workers, 300 instances, max 1200 sec par instance

10 / 12

Dolius+PeneLoPe

Implementation

Resultats

100

120

140

160

180

200

220

0 1 2 3 4 5 6 7

nb s

olu

tions

8 workers, 300 instances, max 1200 sec par instance

10 / 12

Dolius+PeneLoPe

Implementation

Resultats

100

120

140

160

180

200

220

0 1 2 3 4 5 6 7

nb s

olu

tions

8 workers, 300 instances, max 1200 sec par instance

10 / 12

Dolius+PeneLoPe

Implementation

Resultats

100

120

140

160

180

200

220

0 1 2 3 4 5 6 7

nb s

olu

tions

8 workers, 300 instances, max 1200 sec par instance

10 / 12

Dolius+PeneLoPe

Vers l’infini et au-dela

Ameliorations futures

Utiliser des formules complexes pour diviser l’espace derechercheRendre l’implementation independante de PeneLoPe

11 / 12

Dolius+PeneLoPe

Vers l’infini et au-dela

Ameliorations futures

Utiliser des formules complexes pour diviser l’espace derecherche

Rendre l’implementation independante de PeneLoPe

11 / 12

Dolius+PeneLoPe

Vers l’infini et au-dela

Ameliorations futures

Utiliser des formules complexes pour diviser l’espace derechercheRendre l’implementation independante de PeneLoPe

11 / 12

Dolius+PeneLoPe

Vers l’infini et au-dela

Conclusions

Dolius+PeneLoPe permet de resoudre des instancesSAT sur une architecture distribueePossibilite de tester differentes facon de diviser le travail

12 / 12