Program Synthesis for Performance

Presented as part of the 2012 HCSS conference.

Abstract

Extracting optimal performance from modern computing platforms has become increasingly difficult. The effect is particularly noticeable in computations that are of mathematical nature such as those needed in media processing, communication, control, data analytics, or scientific simulations. In these domains, straightfoward implementations often underperform by one or even two orders of magnitude. The reason is in optimizations that are known to be difficult and often impossible for compilers: parallelization, vectorization, and locailty optimizations.

On the other hand, many mathematical applications spend most of their runtime in well-defined mathematical kernels such as matrix computations, tranforms, interpolation, coding, and others. Since these are likely to be needed for decades to come, it makes sense to build program generation systems for their automatic production.

With Sprial we have built such a system for the domain of linear transforms. The key principles underlying Spiral are a domain specific mathematical language to represent algorithms, rewriting systems for different forms of parallelization and a locality optimization called recursion step closure, and the use of machine learning to adapt code at installation time. Spiral-generated code has proven to be often faster than any human-written code and has been deployed in industry.

More information: www.spiral.net

Biography:

Markus Püschel is a Professor of Computer Science at ETH Zurich, Switzerland since 2010. Before, he was a Professor of Electrical and Computer Engineering at Carnegie Mellon University, where he still has an adjunct status. 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. At Carnegie Mellon he was a recipient of the Outstanding Research Award of the College of Engineering and the Eta Kappa Nu Award for Outstanding Teaching. He also holds the title of Privatdozent at the University of Technology, Vienna, Austria. In 2009 he cofounded SpiralGen Inc. The work on Spiral has received several recognitions including being feature as NSF Discovery.

More information: http://www.inf.ethz.ch/~markusp