dir. (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
| Additional title: |
Paral·lelització d'un solucionador All-SAT |
| Additional title: |
Paralelización de un solucionador All-SAT |
| Date: |
2023 |
| Abstract: |
Advancements in SAT solving algorithms with heuristics and more sophisticated inferring techniques have allowed a wide array of real world applications for SAT solvers to prosper. In this work, an All-SAT solver based on the DPLL algorithm has been developed, optimized, and ultimately parallelized, with the objective of learning about the intricacies of SAT solvers from a performance engineering perspective. Ultimately, as a result of this work, a correct and complete parallel All-SAT solver, based on task-parallelism and a divide-and-conquer paradigm, has been successfully implemented and tested with a set of benchmark satisfiability problems. |
| Abstract: |
Avanços en els algoritmes per a la resolució del problema SAT amb heurístiques i tècniques d'inferència més sofisticades han permès que prosperi una àmplia gamma d'aplicacions en el món real per als solucionadors SAT. En aquest treball, s'ha desenvolupat, optimitzat i finalment paral·lelitzat un solucionador All-SAT basat en l'algorisme DPLL, amb l'objectiu de conèixer les complexitats dels solucionadors SAT des d'una perspectiva d'enginyeria del rendiment. En última instància, com a resultat d'aquest treball, s'ha implementat amb èxit un solucionador All-SAT paral·lel correcte i complet, basat en el paral·lelisme de tasques i el paradigma divideix-i-venceràs, testejat amb un conjunt de problemes de satisfacibilitat de referència. |
| Abstract: |
Avances en los algoritmos para la resolución del problema SAT con heurísticas y técnicas de inferencia más sofisticadas han permitido que prospere una amplia gama de aplicaciones en el mundo real para los solucionadoes SAT. En este trabajo, se ha desarrollado, optimizado y finalmente paralelizado un solucionador All-SAT basado en el algoritmo DPLL, con el objetivo de conocer las complejidades de los solucionadores SAT desde una perspectiva de ingeniería del rendimiento. En última instancia, como resultado de este trabajo, se ha implementado con éxito un solucionador All-SAT paralelo, correcto y completo, basado en el paralelismo de tareas y el paradigma de divide-y-vencerás, testeado con un conjunto de problemas de satisfacibilidad de referencia. |
| Rights: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la comunicació pública de l'obra i la creació d'obres derivades, sempre que no sigui amb finalitats comercials i que es distribueixin sota la mateixa llicència que regula l'obra original. Cal que es reconegui l'autoria de l'obra original.  |
| Language: |
Anglès |
| Studies: |
Grau en Enginyeria Informàtica [2502441] |
| Study plan: |
Enginyeria Informàtica [958] |
| Document: |
Treball final de grau ; Text |
| Subject area: |
Menció Enginyeria de Computadors |
| Subject: |
All-SAT ;
SAT ;
DPLL ;
Solucionador ;
Paral·lelització ;
Tasques ;
CNF ;
Propagació unitària ;
Backtracking ;
Fórmula proposicional ;
Paralelización ;
Tasks ;
Propagación unitaria ;
Solver ;
Parallelization ;
Unit propagation ;
Back-tracking ;
Propositional formula |
guest ::
dir. (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
