Computer Generation of Commercial Libraries Becomes a Reality

 

July 18, 2008

Intel has announced that the new version of its high performance library IPP, used by thousands of companies world-wide, will feature a new domain for functions generated by Spiral, a tool developed in ECE under the lead of Professors Markus Püschel and José Moura. Spiral can replace the human programmer in the very difficult task of writing highest performance code for important numerical functions and often achieves even better performance than human programmers. The technology underlying Spiral's success was developed by ECE Research Scientist Franz Franchetti and Püschel's recent Ph.D. graduate Yevgen Voronenko.

Spiral's core domain is linear transforms, which are crucial building blocks for many high performance applications. Examples of transforms include various versions of the discrete Fourier transform, discrete cosine transforms, filters, discrete wavelet transforms, and many others.

Current practice in high performance library development is to carefully hand-tune and hand-optimize code whenever a new platform is released (which happens on an annual or bi-annual basis), a costly effort that requires several man-months to complete. With Spiral it becomes possible to reduce this effort to a few hours of computer time. Besides being cheaper, this makes it possible to take advantage of new platforms faster.

High performance libraries for transforms and others are the performance critical building blocks for many DoD relevant applications. In other words, if the libraries run fast, the applications will run fast. One important example is the discrete Fourier transform, which Spiral can generate and which is used in most signal processing applications. Spiral-generated code for transforms will typically run 10 to 30 times faster than a straightforward implementation by a skilled programmer without training in performance optimization. Compared to the best existing human-written code (typically highly tuned assembly code), Spiral-generated code may be anywhere between competitive or 5 times faster.

Spiral generates libraries using an innovative formal framework that enables the automation of various optimizations typically performed by a human programmer including vectorization and parallelization for recent multicore platforms and tuning to a given computer's memory hierarchy. Further, for a desired transform, Spiral can autonomously generate and evaluate thousand's of algorithmic alternatives to find the fastest solution for a given computing platform. Each of the above optimizations performed automatically by Spiral are difficult to perform by hand would require highly skilled programmers.

Spiral is funded by Darpa, NSF, and several companies in projects led by Professors José Moura and Markus Püschel, both CMU. The technology underlying Spiral's recent success with Intel was developed by ECE Research Scientist Franz Franchetti and Püschel's recent PhD graduate Yevgen Voronenko who also received the ECE best dissertation award for his work. This last generation of Spiral builds on an earlier prototype developed at CMU jointly with the research groups of David Padua at the University of Illinois at Urbana-Champaign and Jeremy Johnson at Drexel University.

One the Intel side, the use of Spiral in IPP became possible through a collaboration initiated and supported by Intel fellow David Kuck, Math Kernel Library Senior Principal Engineer Peter Tang, and IPP Technical Manager Boris Sabanin.

The current research in the Spiral project can be divided into two main directions

  1. Expand Spiral's library generation abilities beyond transforms to other numerical functionality and applications. Examples currently studied are Viterbi decoding, synthetic aperture radar (SAR) imaging, JPEG2000 image compression, and basic linear algebra kernels.
  2. Together with ECE Prof. James Hoe and the groups at UIUC and Drexel, attack the far out problem of automatic application-platform co-design and co-optimization. In other words, given an application, answer the question of what is the best computing platform, instantiate the platform, and then generate optimized code for this platform.

Headshot of JosÈ Moura

Headshot of Markus P¸schel

Research Scientist Franz Franchetti

In contrast to the "Current" way of developing libraries, Spiral ("Future") raises the level of abstraction for complete automation without sacrifices in performance.

Headshot of Yevgen Voronenko

Related People:

José Moura

Markus Püschel

Franz Franchetti

Related Groups:

SPIRAL