Retired but not forgotten: Algorithm research with a Supercomputer

Professor Emeritus Tadao Takaoka, a recently retired computer scientist from the University of Canterbury, has devoted his research career to designing efficient algorithms for classical computer science problems – shortest path, data structures, combinatorial generations and subarray problems to name a few. A number of his works still hold the title of “best known” solutions to this day.

In the area of parallel algorithms, Prof. Takaoka has long been fascinated by 2D mesh architecture, a two-dimensional network of computing nodes, where each node is relatively light with little computing power and is allowed to communicate with its four neighbouring nodes only. This is a strict constraint, but with clever orchestration of data movement, sending the right data to the right neighbour at the right time all happening in parallel, one can still compute the solution very fast.

Despite its shortcomings, this architecture is easy to mass-produce in the form of a chip, such as an Application Specific Integrated Circuit (ASIC) or Field Programmable Gate Array (FPGA). These chips are widely used in most modern digital devices to carry out a special function. A parallel algorithm designed for this architecture potentially gives the power of a parallel computer in a tiny form factor at a correspondingly tiny cost.

Attribution: 

2D mesh architecture showing data and control flow

Takaoka and his students have been designing 2D mesh algorithms for various problems – all-pairs shortest path, maximum subarray, matrix multiplication and maximum convex sum – since the 1980s. One of his PhD graduates, now a NeSI scientific programmer, Sung Bae, recalls: “When I designed a parallel algorithm for maximum subarray in 2002, there was no hardware within our reach to test it. All I could do was mathematically prove its correctness and analyse its speed in theoretical terms.”

Bae adds, “When the first Blue Gene/L was installed at BlueFern [now UC HPC, NeSI’s Canterbury base] in 2007, I knew it was the ideal machine to test my algorithm, but sadly I had already finished my PhD.” Little did he know he would eventually get to work for NeSI.

Since Bae joined NeSI, Takaoka reinstigated 2D mesh algorithm research and used NeSI’s technical support to drive Blue Gene. New solutions for old challenging problems came one after another. The best solution for distributed matrix multiplication by L.E. Cannon, known as Cannon’s algorithm (1969) and the solution for the all-pairs shortest path (APSP) problem by Takaoka himself (1992) hadn’t been challenged for many years, but new solutions finally dethroned them.

In the algorithm research community, the performance of an algorithm is expressed in theoretical terms, such as the number of communication steps required to complete the computation. The use of Blue Gene uncovered by this theoretical measurement doesn’t show the whole picture in real life. The new APSP algorithm is only 12.5% faster in theory, but measured 40% faster in practice, thanks to its simpler design. On the other hand, the new matrix multiplication algorithm, in theory two times faster than Cannon’s, showed a modest 30~40% speed increase in practice due to an extra operation, the impact of which was considered negligible in theory. Such an empirical analysis was not attainable in the past.

Takaoka says: “Parallel computing is a fascinating area where theory and practice meet in a productive and tangible way. It is not, however, straightforward to find out what part of the given problem can be parallelised and what part cannot. We need a lot of skills for parallel programming through practical experience. It is for this reason that I introduced the use of Blue Gene into my Stage 4 course 'Advanced Algorithms' as well as for my own research. Dr Sung Bae helped me a lot in the guidance of students into the programming environment of Blue Gene with LoadLeveler, MPI programming and the Linux environment. We are very grateful to NeSI for the use of Blue Gene and the supporting team. Thanks to their generosity, we were able to develop a culture of supercomputing and parallel programming at the University of Canterbury.”

Prof. Takaoka, even though retired from the University of Canterbury, is still active and now leads a “research club” called Algorithm Research Institute (ARI) with his PhD graduates Tongwook Shinn and Sung Bae. NeSI’s Blue Gene/P supercomputer is being retired in June 2016. Like Prof. Takaoka himself, it will be leaving a tremendous legacy and a large number of research papers with its name attached.