000004576 001__ 4576 000004576 005__ 20150325135713.0 000004576 037__ $$aTAZ-PFC-2010-018 000004576 041__ $$aspa 000004576 1001_ $$aOlivito del Ser, Javier 000004576 24500 $$aDiseño e implementación de un procesador específico para la resolución de Sudokus 000004576 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2010 000004576 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/ 000004576 520__ $$aEste 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. 000004576 521__ $$aIngeniero en Informática 000004576 540__ $$aDerechos regulados por licencia Creative Commons 000004576 6531_ $$aProcesador 000004576 6531_ $$aSudoku 000004576 6531_ $$aDiseño hardware 000004576 6531_ $$aArquitectura de computadores 000004576 6531_ $$aFPT 000004576 700__ $$aResano Ezcaray, Jesús Javier$$edir. 000004576 700__ $$aGonzález Calvo, Carlos$$edir. 000004576 7102_ $$aUniversidad de Zaragoza$$bInformática e Ingeniería de Sistemas$$cArquitectura y Tecnología de Computadores 000004576 830__ $$aCPS 000004576 8560_ $$f499166@celes.unizar.es 000004576 8564_ $$s1806637$$uhttps://zaguan.unizar.es/record/4576/files/TAZ-PFC-2010-018.pdf$$yMemoria (spa) 000004576 8564_ $$s737036$$uhttps://zaguan.unizar.es/record/4576/files/TAZ-PFC-2010-018_ANE.pdf$$yAnexos (spa) 000004576 909CO $$ooai:zaguan.unizar.es:4576$$pdriver$$pproyectos-fin-carrera 000004576 950__ $$a 000004576 980__ $$aTAZ$$bPFC$$cCPS