April 24, 2015

Dear John E. Miller,

We have never stopped working on the Langford problem. Now we are happy and proud to announce that we have computed L(2,27).

Hybrid CPU-GPU supercomputers now represent 10% of the Top500 list, and we have to consider the high computing potential delivered by their accelerators. But, due to their huge irregularity, combinatorial problems are bad candidates for GPU programming.

We propose a general scheme allowing to represent any combinatorial search problem as a CSP and develop the resolution with a 3-level parallelization: a top-level server develops the search tree in order to generate consistent tasks ; the clients continue the development into a large number of sub-tasks, that are treated by the CPU cores and GPUs in a concurrent way.

This work is supported by the Computing Center of Champagne-Ardenne (University of Reims). The experiments were led in March 2015 on the ROMEO supercomputer: ROMEO HPC Center. This cluster provides 130 nodes each composed of 2 Ivy Bridge CPUs (E5-2650v2, 8 cores, 2.6GHz) and 2 Tesla K20Xm GPUs.

We have implemented the Miller's algorithm with an MPI-OpenMP-CUDA approach and this allowed us to compute L(2,20) in less than 3 hours using 129 hybrid servers (ie 258 CPUs and 258 GPUs), and L(2,21) in 33hours.

In order to go further we have adapted this approach to the Godfrey's alorithm. With further optimizations and code tuning, we were able to compute L(2,24) in 2.4 hours on 16 servers (32 CPUs and 32 GPUs). Finally, we had a large experiment using best-effort distributed computing, and got L(2,27) with an average amount of 181 CPU-GPU machines during 2 days (1 day and 20 hours).

        L(2,27) = 111,683,606,778,027,803,456

The team involved in this project is composed of University of Reims researchers from CReSTIC laboratory, SysCom group: Christophe Jaillet (associate professor), Michaël Krajëcki (full professor, team leader), Arnaud Renard (research engineer), Julien Loiseau (Master degree student), François Alin (external professor).

We have submitted an article detailing this work. I will send you the reference as soon as it is published.

Best regards,
Ch Jaillet

Christophe Jaillet
CReSTIC, SysCom group
Mathematics and Computer science Department
University of Reims Champagne-Ardenne
UFR Sciences Exactes et Naturelles
Campus du Moulin de la Housse
BP 1039 - 51687 REIMS Cedex 2

Email rcvd April 24, 2015. Edited slightly for URLs and HTML.
Author's telephone number and e-mail address removed.