Resumen

El problema de las N-Reinas juega un papel importante en la investigacin acadmica y en la aplicacin prctica. El algoritmo heurstico se utiliza a menudo para resolver la variante 2 del problema de las N-Reinas. En el proceso de resolucin, la evaluacin de la solucin candidata, es decir, la funcin de aptitud, a menudo ocupa la gran mayora del tiempo de ejecucin y se convierte en la clave para mejorar la velocidad. En este trabajo, se proponen tres esquemas paralelos basados en CPU y cuatro esquemas paralelos basados en GPU, y se implementa un esquema serial como lnea base. Los resultados experimentales muestran que, para un problema de las N-Reinas a gran escala, el esquema de GPU de grano grueso logr una aceleracin mxima de 307 veces en comparacin con un contraparte de CPU de un solo hilo al evaluar una solucin candidata. Cuando se aplica el esquema de GPU de grano grueso al recocido simulado en la resolucin de la variante 2 del problema de las N-Reinas

• Materias:Funciones Flujo de información Estudio de población Modelado de sistemas Modelo de campo
• Subjects:Functions Information flow Population study System modeling Field model
• Palabras claves:Problema de las n reinas; Algoritmo heurístico; Función de aptitud; Esquemas paralelos; CPU; GPU
• Keywords:N-queens problem; Heuristic algorithm; Fitness function; Parallel schemes; CPU; GPU