Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Implementazione di un vincolo table su un CSPsolver GPU-based

Tesi di Laurea

Tommaso Campari

27 Ottobre 2016 - A.A. 2015-2016

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Indice

Introduzione ai CSP

Introduzione a CUDA

Il solver iNVIDIOSO

Il Table Constraint

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

I CSP: Constraint Satisfaction Problem

Constraint:Sia X una sequenza finita di variabili X = {x1, ..., xn} conn > 0 con i rispettivi domini D = {d1, ..., dn}. Un constraint csu X definito come c ⊆ d1 × ...× dn e un sottoinsieme delprodotto cartesiano dei domini.

CSP:un CSP e una tripla P = 〈X ,D, C〉 dove:

I X : rappresenta l’insieme delle variabili {x1, ..., xn}I D: rappresenta l’insieme dei domini necessariamente non

vuoti {d1, ..., dn} associati univocamente alle variabili.

I C: rappresenta l’insieme dei vincoli sulle variabili X .

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Risolvere un CSP

L’obbiettivo e trovare una o piu soluzioni ammissibili.

Soluzione:Una soluzione e un’assegnamento delle variabili che soddisfa tutti ivincoli del CSP.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Arc e Bound consistency

L’operazione di consistency rimuove dai domini delle variabiliassociate ad un constraint valori che sicuramente non portano auna soluzione.

Arc consistency

I Analizza ogni valore deldominio;

I E’ piu costosa;

I Elimina valori che nonportano a soluzione.

Bound consistency

I Analizza solo i valori agliestremi del dominio.

I E’ meno costosa;

I Elimina solo i valori agliestremi del dominio che nonportano a soluzione.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Introduzione a CUDA

CUDA:

I Architettura general purpose per ilparallel computing;

I Sfrutta il motore di calcolo delleGPU per risolvere problemi;

I Utilizza blocchi e thread per ilparallelismo;

I Le funzioni parallele sonodenominate Kernel.

Figura:Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Parallelismo dinamico

Parallelismo dinamico:Estensione al modello diprogrammazione CUDA:

I Permette ai Kernel di essereinvocati direttamente della GPU;

I Minor comunicazione CPU → GPUe viceversa;

I Maggior efficienza e flessibilita.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

iNVIDIOSO

Si tratta di un CSP solver:

I Sperimentale;

I Ancora in fase di sviluppo;

I Con supporto all’architettura CUDA.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

La rappresentazione dei domini in iNVIDIOSO

I domini sono rappresentati secondo due modalita:

I Bound rapresentation: le variabili i cui domini hanno unadifferenza tra il minimo e il massimo elemento di almeno 256sono implementati come una coppia di valori denominatiBound;

I Bitmask rapresentation: altrimenti sono implementatimediante una bitmask composta da 8 interi a 32 bit, doveognuno di questi se impostato a 1 rappresenta un elementopresente nel dominio.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Obiettivi della tesi

I Ideare un algoritmo parallelo efficiente per il vincolo table;

I Integrarlo sul solver;

I Dimostrare l’effettiva possibilita di propagare i vincoli inparallelo.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Il Table Constraint

Si tratta di un constraint estensionale definito elencandoesplicitamente una lista di n tuple di valori permessi per le variabilinel suo scope.

Esempio: table([X1,X2,X3], [〈1, 2, 3〉, 〈4, 5, 6〉, 〈7, 8, 9〉]) conD1,D2 e D3 fissati a [1, ..., 10]. La tabella associata al vincolopuo quindi essere vista come:

X1 X2 X3

t1 1 2 3

t2 4 5 6

t3 7 8 9

Dopo il filtering: D1 = {1, 4, 7},D2 = {2, 5, 8} e D3 = {3, 6, 9}Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

L’algoritmo di consistenza sequenziale

L’algoritmo di consistenza e stato innanzitutto pensato perun’esecuzione sequenziale su CPU e in particolare vuole sfruttare larappresentazione dei domini fornita dal solver.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Bound consistency sequenziale per una variabile

Nel caso di esecuzione su domini con rappresentazione tramitecoppia di bound viene eseguita la consistenza per la variabile delloscope selezionata solo sul lower e sull’upper bound.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Arc consistency sequenziale per una variabile

Nel caso di esecuzione su domini con rappresentazione tramitebitmask viene eseguita la consistenza per la variabile dello scopeselezionata su ogni elemento del dominio.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Schema di implementazione con multithreading su CUDA

La prima implementazione fa utilizzo di un solo blocco con 256thread in esecuzione parallela.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Bound consistency con multithreading

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Arc consistency con multithreading

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Risultati ottenuti con il multithreading su CUDA(I)

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Risultati ottenuti con il multithreading su CUDA(II)

I L’andamento dovrebbe essere a tempo costante parallelo;

I Non accade perche un thread si occupa di un valore deldominio, che puo essere associato a molte tuple;

I Nel test il numero di queste tuple pero era lineare rispetto alladimensione della table.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Schema dell’implementazione con il parallelismo dinamico

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Consistency con il parallelismo dinamico

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Confronto tra le due implementazioni parallele

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Lavori futuri

I Integrazione dei vincoli estensionali sul parser di iNVIDIOSO;

I Integrazione del parallelismo dinamico su iNVIDIOSO;

I Modifica dell’algoritmo di ordinamento con un mergesortparallelo;

I Bilanciamento del lavoro tra i thread in caso di distribuzionenon uniforme dei valori nelle tuple.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Conclusioni

Gli obiettivi inizialmente proposti sono stati raggiunti ed inparticolare:

I La propagazione dei vincoli su GPU e possibile;

I L’algoritmo implementato(specie nel caso del parallelismodinamico) e efficiente e filtra correttamente le soluzioni.

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based

Introduzione ai CSP Introduzione a CUDA Il solver iNVIDIOSO Il Table Constraint

Grazie per l’attenzione!

Tommaso Campari

Implementazione di un vincolo table su un CSP solver GPU-based