Expert programmers will write highly optimized library implementations using sketching and autotuning. Programmers may sketch sophisticated implementations, which will then be synthesized and autotuned. Sketching serves as an alternative to optimizing compilers for the efficiency layer, and supports optimizations that adapt to the application and hardware needs. For example, a data-structure-agnostic sketch will be synthesized into a library module composable with the application data structures. We will develop sketching for 1) grid operations that go beyond stencils, 2) lock-free data structures, and 3) turning synchronous specifications into asynchronous implementations that use non-blocking memory operations. We will add linguistic support for sketching into language(s) for programming in the efficiency layer, develop synthesizers for completing holes in sketches, and build tool support for sketching. The goals are to make sketching as natural as programming (with no formal systems training) and to make synthesis scalable enough for high-performance implementations of most dwarfs.

(Objective: The overall success metric for this work is that where Sketching is applied it will show a 10X productivity improvement over developing parallel code by hand.)