Many-Core Approaches to Combinatorial Problems: case of the Langford Problem
DOI:
https://doi.org/10.14529/jsfi160202Abstract
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 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 the Godfrey 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.
References
Gardner M. Mathematics, magic and mystery. Dover publication; 1956.
Simpson JE. Langford Sequences: perfect and hooked. Discrete Math. 1983;44(1):97–104.
Miller JE. Langford’s Problem: http://dialectrix.com/langford.html; 1999. Available from: http://www.lclark.edu/~miller/langford.html.
Walsh T. Permutation Problems and Channelling Constraints. APES Research Group; 2001. APES-26-2001. Available from: http://www.dcs.st-and.ac.uk/~apes/reports/apes-26-2001.ps.gz.
Smith B. Modelling a Permutation Problem. In: Proceedings of ECAI’2000, Workshop on Modelling and Solving Problems with Constraints, RR 2000.18. Berlin; 2000. Available from: http://www.dcs.st-and.ac.uk/~apes/2000.html.
Larsen J. Counting the number of Skolem sequences using inclusion exclusion. 2009.
Assarpour A, Barnoy A, Liu O. Counting the Number of Langford Skolem Pairings; 2015.
Nvidia C. Compute unified device architecture programming guide. 2007.
Kirk DB, Wen-mei WH. Programming massively parallel processors: a hands-on approach. Newnes; 2012.
Habbas Z, Krajecki M, Singer D. Parallelizing Combinatorial Search in Shared Memory. In: Proceedings of the fourth European Workshop on OpenMP. Roma, Italy; 2002.
Montanari U. Networks of Constraints: Fundamental Properties and Applications to Pictures Processing. Information Sciences. 1974;7:95–132.
Prosser P. Hybrid algorithms for the constraint satisfaction problem. Computational intelligence. 1993;9(3):268–299.
Krajecki M. An object oriented environment to manage the parallelism of the FIIT applications. In: Parallel Computing Technologies. Springer; 1999. p. 229–235.
Volkov V. Better performance at lower occupancy. In: Proceedings of the GPU Technology Conference, GTC. vol. 10. San Jose, CA; 2010. p. 16.
Jaillet C. In french: R ́esolution parall`ele des probl`emes combinatoires [PhD]. Universit ́e de Reims Champagne-Ardenne, France; 2005.
Jette M, Grondona M. SLURM : Simple Linux Utility for Resource Management; June 23, 2003.
Downloads
Published
How to Cite
Issue
License
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-Non Commercial 3.0 License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.