Summer Of HPC Introduction – Oliver Legg

Who am I?

Hello! My name is Oliver Legg, I’m 22 years old and I’m from Cheshire, England. I recently graduated from the University of Liverpool with a first-class honours degree in Computer Science /w Software Development. Other than being interested in technology, I enjoy powerlifting, bouldering and playing video games.

I first began my computer science endeavour at a young age from enjoying playing video games. The desire to make them led me to programming and bamboozled me with a lot of information I didn’t understand at that age. Fortunately, over the years I have learnt more and more from the world of computer science, which led me to where I am now.

Why SoHPC?

The summer of HPC was introduced to me by a lecturer who spoke very highly of the programme. Having enjoyed studying HPC at university, I knew I wanted to expand my knowledge in this area. With the opportunity to work on ICHEC’s supercomputer, ‘Kay’, the opportunity was too good to pass up. Without hesitation, I applied for this programme and requested to be assigned to the project titled, “Parallel anytime branch and bound algorithm for finding the treewidth of graphs”.

What is “Parallel anytime branch and bound algorithm for finding the treewidth of graphs?”

I don’t plan to go into too much detail about the project in this post, therefore, a harsh oversimplification of this project would be to call it “a clever algorithm for computing the treewidth of a graph”. The treewidth of a graph is how far the graph is from being a tree. With this treewidth value, you can speed up solving certain computational problems on the graph. These problems could include pathfinding or checking connectivity (does there exist a path from A to B?) and more. You can read more about the project here.

Despite enjoying the challenge of reciting the lengthy project title, I chose this project because I have previously enjoyed solving graph theory problems. I wrote my final year project dissertation on accelerating a graph drawing algorithm with a GPU.

Teammate, Mentor and ICHEC

The project is split between myself and my teammate, Valentin Trophime – please have a read of his latest post. I have also briefly met my project mentor, Niall Moran and have been working with my project co-mentor, John Brennan. Many thanks to them and everyone at ICHEC as they have been exceptionally welcoming and helpful.

What have we done so far?

In the first week of the PRACE programme, was a training week which involved:

• An introduction to SoHPC
• Python Programming on HPC systems
• OpenMP
• MPI

For this project, we plan to use Julia (a script-like programming language for HPC), so the first week with our mentor was spent learning Julia and treewidth theory. We needed to implement a min-fill and min-width heuristic from Gogate & Dechter’s paper on “A Complete Anytime Algorithm for Treewidth“. This week’s plan is to implement a depth first search on a graph with an algorithm from the same paper.

Conclusion

Thank you for taking the time to read this post; I intend to write more in-depth posts about the project in the future. If you have any questions, please leave a comment.

Oliver Legg