Logo of Science Foundation Ireland  Logo of the Higher Education Authority, Ireland7 CapacitiesGPGPU Research Projects
Ireland's High-Performance Computing Centre | ICHEC
Home | News | Infrastructure | Outreach | Services | Research | Support | Education & Training | Consultancy | About Us | Login

A Sudoku Game Against The Clock and the Intel Xeon Phi (December 2013)

Phidoku main screen [High-Res Image]. Phidoku introduction to FLOPS screen [High-Res Image]. Phidoku algorithm overview [High-Res Image]. Introduction to Fionn [High-Res Image].

ICHEC was one of the first groups in the world to develop code for the Intel Xeon Phi co-processor showcasing a demo at the ISC12 conference. The demo compared the performance of the Intel Sandy Bridge processor and Intel Xeon Phi co-processor for finding sudoku grids that can be uniquely solved from only a 17 number hint. The code used is almost identical to that used for the 16-clue problem, developed by UCD Scientist, Prof. Gary McGuire, and ICHEC computational scientist, Gilles Civario. The demo was also shown at the BT Young Scientist in January 2013 to highlight the uses of parallel processing. The challenge for the 50th Edition of BT Young Scientist in January 2014 was to make the demo more interactive to attract students to the stand, allow them compete against the Xeon Phi and other students at the event. Here is an account by Ruairi Short a computational scientist at ICHEC and a recent graduate (2013) of the EPCC MSc. in High Performance Computing, where he designed and developed an interactive game "phidoku" for students to solve sudoku puzzles while still showcasing the Intel Xeon Phi card against the Intel Ivy Bridge architecture.

If you would like to play this game please visit the ICHEC stand at the BT Young Scientist and Technology Exhibition from the 9th to 11th of January 2014.

Game Specifications

The idea was to use the existing demo and provide a front end to make in more interactive. This front end would show the output from the Intel Xeon Phi and Ivy Bridge processors, similar to the old demo, but also provide the students with a sudoku puzzle to solve while this was happening. It was important to ensure that students did not spend too long on the machine so sudoku puzzles had to be designed with a solve time of between one and two minutes. The students details would also be stored and a record kept of their times, with the idea of giving out prizes each day for the fastest solve. Along with this, the Intel Xeon Phi and Ivy Bridge simulations would be run on ICHEC's new supercomputer Fionn.

Ruairi's Story

In late October 2013 Ruairi was assigned to develop this new sudoku game as part of the outreach programme within ICHEC. He was interested to begin developing a graphical interface and decided to use Qt as the basic design tool. He learned much about this tool and began work on the graphical interface and came up with the name "Phidoku". As the backend simulation would be running on the Intel Xeon Phi this was also a great opportunity to get to use this relatively new technology and to understand more about how to use it.

Before anything could start, it was necessary to get to grips with the old code, to ensure the final demo would present the original in a consistent way. This was a good learning experience for using the Intel Xeon Phi and understanding how code is written optimally for it. Coming from a theoretical physics background, Ruairi also found the maths behind the 17 clue problem to be very interesting. There are 6 × 1017 different sudoku grids, but using the mathematical properties of these, the number necessary to be checked can be reduced to 5,472,780,538. This is still a huge number and clever algorithms were necessary to eliminate these as fast as possible. Simply put, a hitting algorithm is used to construct clues from a number of unavoidable sets. These unavoidable sets are numbers which are completely necessary to have on the grid in order to construct a unique solution. If there are less than 17 clues after grouping these unavoidable sets, we can check if it is uniquely solvable! For more information, you can read more about the 16-clue problem on which this is based.

The main sudoku game was implemented first to ensure the program was always usable and then additional features were added, such as navigation using arrow keys and colouring of boxes when incorrect numbers were entered. Then the high score pages were built and the user details entry dialog. The next stage was the communication between the old demo and the new front end. This proved to be one of the more technical challenges of the problem with use of ssh tunnelling chosen as the method. This allowed for a socket connection between the computer to be used at the BT Young Scientist Exhibition and Fionn, over which the communication of the grids could take place. Setting this up required much testing but eventually it worked! The next stage was to edit the old demo in order to allow for this communication to occur. The old code is very largely written in assembly and highly optimised C++ which makes for very hard reading, but it was possible to attach the communication module in a separate file and maintain program flow. Ensuring the correct communication was taking place also proved to be important, but this was solved by sending messages with informative headers and start messages. In the end the code produced should be easily translatable to further projects that require a similar solution.

Beta testing then took place in the office and much thanks were given to other ICHEC staff who had comments on the layout and design. In the end JC proved to be the fastest with a time just 20 milliseconds faster than Ruairi. A last minute rush then saw the final background pictures for the main page designed and delivered and the layout finalised and looking very attractive!

Overall this was a very satisfying project, providing an opportunity to see it through from beginning to end. Much was learned about design on software projects and graphical interfaces. It was also a good opportunity to play with the Intel Xeon Phi and learn about how it is used to achieve best performance. It is hoped that this work will help people understand highly parallel applications and inspire students to take up high performance computing!