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
Top Related