Wed 17 Jun 2015 10:05 - 10:30 at PLDI Main BLUE (Portland 254-255) - Performance Chair(s): Mary Hall

Highly optimized programs are prone to bit rot, where performance quickly becomes suboptimal in the face of new hardware and compiler techniques. In this paper we show how to automatically lift performance-critical stencil kernels from a stripped x86 binary and generate the corresponding code in the high-level domain-specific language Halide. Using Halide’s state-of-the-art optimizations targeting current hardware, we show that new optimized versions of these kernels can replace the originals to rejuvenate the application for newer hardware.

The original optimized code for kernels in stripped binaries is nearly impossible to analyze statically. Instead, we rely on dynamic traces to regenerate the kernels. We perform buffer structure reconstruction to identify input, intermediate and output buffer shapes. We abstract from a forest of concrete dependency trees which contain absolute memory addresses to symbolic trees suitable for high-level code generation. This is done by canonicalizing trees, clustering them based on structure, inferring higher-dimensional buffer accesses and finally by solving a set of linear equations based on buffer accesses to lift them up to simple, high-level expressions.

Helium can handle highly optimized, complex stencil kernels with input-dependent conditionals. We lift seven kernels from Adobe Photoshop giving a 75% performance improvement, four kernels from IrfanView, leading to 4.97× performance, and one stencil from the miniGMG multigrid benchmark netting a 4.25× improvement in performance. We manually rejuvenated Photoshop by replacing eleven of Photoshop’s filters with our lifted implementations, giving 1.12× speedup without affecting the user experience.

Wed 17 Jun

Displayed time zone: Tijuana, Baja California change

09:15 - 10:55
PerformanceResearch Papers at PLDI Main BLUE (Portland 254-255)
Chair(s): Mary Hall University of Utah
09:15
25m
Talk
Automated Detection of Performance Bugs via Static Analysis
Research Papers
Oswaldo Olivo , Isil Dillig University of Texas, Austin, Calvin Lin UT Austin
Media Attached
09:40
25m
Talk
Autotuning Algorithmic Choice for Input Sensitivity
Research Papers
Yufei Ding North Carolina State University, Jason Ansel Massachusetts Institute of Technology, Kalyan Veeramachaneni Massachusetts Institute of Technology, Xipeng Shen North Carolina State University, Una-May O’Reilly Massachusetts Institute of Technology, Saman Amarasinghe MIT
Link to publication Media Attached
10:05
25m
Talk
Helium: Lifting High-Performance Stencil Kernels from Stripped x86 Binaries to Halide DSL Code
Research Papers
Charith Mendis MIT CSAIL, Jeffrey Bosboom MIT CSAIL, Kevin Wu MIT CSAIL, Shoaib Kamil MIT CSAIL, USA, Jonathan Ragan-Kelley Stanford, Sylvain Paris Adobe, Qin Zhao Google, Saman Amarasinghe MIT
Media Attached
10:30
25m
Talk
Profile-Guided Meta-Programming
Research Papers
William J. Bowman Northeastern University, Swaha Miller Cisco Systems, Inc, Vincent St-Amour Northeastern University, R. Kent Dybvig Cisco Systems, Inc
Link to publication Media Attached