Many-Core Approaches to Combinatorial Problems: case of the Langford problem

Abstract : As observed from the last TOP500 list - November 2015 -, GPUs-accelerated clusters emerge as clear evidence. But exploiting such architectures for combinatorial problem resolution remains a challenge. In this context, this paper focuses on the resolution of an academic combinatorial problem, known as the Langford pairing problem, which can be solved using several approaches. We first focus on a general solving scheme based on CSP (Constraint Satisfaction Problem) formalism and backtrack called the Miller algorithm. This method enables us to compute instances up to L(2, 21) using both CPU and GPU computational power with load balancing. As dedicated algorithms may still have better computation efficiency we took advantage of Godfrey’s algebraic method to solve the Langford problem and implemented it using our multiGPU approach. This allowed us to recompute the last open instances, L(2, 27) and L(2, 28), respectively in less than 2 days and 23 days using best-effort computation on the ROMEO supercomputer with up to 500,000 GPU cores.
Type de document :
Article dans une revue
Supercomputing frontiers and innovations , 2016, 3 (2), 〈10.14529/jsfi160202〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
Contributeur : Julien Loiseau <>
Soumis le : jeudi 1 février 2018 - 09:35:41
Dernière modification le : mercredi 14 février 2018 - 01:02:55
Document(s) archivé(s) le : mercredi 2 mai 2018 - 12:46:00


Fichiers éditeurs autorisés sur une archive ouverte




M. Krajecki, J Loiseau, F Alin, C. Jaillet. Many-Core Approaches to Combinatorial Problems: case of the Langford problem. Supercomputing frontiers and innovations , 2016, 3 (2), 〈10.14529/jsfi160202〉. 〈hal-01698255〉



Consultations de la notice


Téléchargements de fichiers