4576 20150325135713.0 TAZ-PFC-2010-018 spa Olivito del Ser, Javier Diseño e implementación de un procesador específico para la resolución de Sudokus Zaragoza Universidad de Zaragoza 2010 by-nc-sa Creative Commons 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ Este proyecto surge como propuesta de participación en el Field-Programmable Technology ’09 Design Competition, concurso de diseño hardware que propuso el desarrollo de un procesador específico para resolver Sudokus de diferentes tamaños sobre una FPGA. Nuestro primer diseño consistió en la implementación de un algoritmo de ramificación y poda, utilizando como función de poda la eliminación de candidatos mediante las reglas del Sudoku. El diseño de la memoria y de la ruta de datos estuvo encaminado a explotar el paralelismo que presenta dicha función de poda. Los resultados de esta primera versión evidenciaron una necesidad de mejora, puesto que nuestro diseño era ineficiente en la resolución de Sudokus de gran tamaño o de alta complejidad. La versión final de nuestro procesador mejora estos resultados incorporando una etapa de preprocesamiento que aplicaba un conjunto de heurísticas capaces de acotar el espacio de búsqueda. Paralelamente, se desarrolló una versión software equivalente que se utilizó para depurar el diseño hardware y para evaluar la eficacia de las heurísticas existentes antes de implementarlas en el procesador hardware. Las mejoras de esta versión permiten una resolución eficiente de Sudokus de baja-media complejidad y gran tamaño (hasta orden 11: 121x121 casillas), si bien aun se muestra ineficiente en la resolución de los Sudokus de alta complejidad. Los resultados obtenidos con este diseño nos permitieron lograr el primer premio del FPT '09 Design Competition. Además el diseño fue elegido para su presentación en el congreso y una descripción del mismo fue publicada en sus actas, siendo accesible a toda la comunidad científica a través del IEEE Xplorer. Ingeniero en Informática Derechos regulados por licencia Creative Commons Procesador Sudoku Diseño hardware Arquitectura de computadores FPT Resano Ezcaray, Jesús Javier dir. González Calvo, Carlos dir. Universidad de Zaragoza Informática e Ingeniería de Sistemas Arquitectura y Tecnología de Computadores CPS 499166@celes.unizar.es 1806637 http://zaguan.unizar.es/record/4576/files/TAZ-PFC-2010-018.pdf Memoria (spa) 737036 http://zaguan.unizar.es/record/4576/files/TAZ-PFC-2010-018_ANE.pdf Anexos (spa) oai:zaguan.unizar.es:4576 driver proyectos-fin-carrera TAZ PFC CPS