Can We Teach Computers to Write Fast Libraries?

Markus Püschel, Department of Electrical and Computer Engineering, Carnegie-Mellon University, Pittsburg, PA

Abstract: As the computing world "goes multicore," high performance library development finally becomes a nightmare. Optimal programs, and their underlying algorithms, have to be adapted to take full advantage of the platform's parallelism, memory hierarchy, and available instruction set. To make things worse, the best implementations are often platform-dependent and platforms are constantly evolving, which quickly renders libraries obsolete. As a consequence, developers are forced to permanently re-implement and re-optimize the same functionality and often even revert to assembly coding just as 50 years ago.

A number of research efforts have started to address this problem in a new area called Automatic Performance Tuning with the common goal to rethink the way libraries are created. In this talk we present Spiral, a program generation system for linear transforms. Spiral generates highly optimized, platform-tuned implementations of transforms directly from a problem specification. For a user-specified transform, Spiral generates alternative algorithms, optimizes them, compiles them into programs, and "intelligently" searches for the best match to the computing platform. The main idea behind Spiral is a mathematical, declarative framework to represent algorithms and the use of rewriting systems to generate and optimize algorithms at a high level of abstraction. Optimization includes parallelization for vector architectures, shared and distributed memory platforms, GPUs, and even FPGAs. Experimental results show that the code generated by Spiral competes with, and sometimes outperforms, the best available human-written library code. Further, recent research shows that it may be possible to extend Spiral into other domains such as coding or linear algebra. As for the question in the title: Spiral shows that, at least for well-understood problem domains, a positive answer may be in reach.

About the speaker: Markus Püschel is an Associate Research Professor of Electrical and Computer Engineering at Carnegie Mellon University. He received his Diploma (M.Sc.) in Mathematics and his Doctorate (Ph.D.) in Computer Science, in 1995 and 1998, respectively, both from the University of Karlsruhe, Germany. From 1998-1999 he was a Postdoctoral Researcher at Mathematics and Computer Science, Drexel University. Since 2000 he has been with Carnegie Mellon University. He is an Associate Editor for the IEEE Transactions on Signal Processing, and was a Guest Editor of the Journal of Symbolic Computation, the Proceedings of the IEEE, and an Associate Editor for the IEEE Signal Processing Letters. He is a 2007 recipient of the Outstanding Research Award of the College of Engineering, CMU, and holds the title of Privatdozent at the Department of Computer Science, University of Technology, Vienna. His research interests include computing, algorithms, applied mathematics, and signal processing theory/software/hardware.

More information