Resumen

El problema de las N-Reinas juega un papel importante en la investigación académica y en la aplicación práctica. El algoritmo heurístico se utiliza a menudo para resolver la variante 2 del problema de las N-Reinas. En el proceso de resolución, la evaluación de la solución candidata, es decir, la función de aptitud, a menudo ocupa la gran mayoría del tiempo de ejecución y se convierte en la clave para mejorar la velocidad. En este artículo, se proponen tres esquemas paralelos basados en CPU y cuatro esquemas paralelos basados en GPU, y se implementa un esquema serial como referencia. Los resultados experimentales muestran que, para un problema de N-Reinas a gran escala, el esquema GPU de grano grueso logró una aceleración máxima de 307 veces sobre un homólogo de CPU de un solo hilo al evaluar una solución candidata. Cuando se aplica el esquema GPU de grano grueso al recocido simulado en la resolución de la variante 2 del problema de las N-Reinas con un tamaño de problema de no

• 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