Yuka Ikarashi

ALT User-schedulable languages (USLs) help programmers productively optimize programs by providing safe means of transforming them. Current USLs are designed to give programmers exactly the control they want, while automating all other concerns. However, there is no universal answer for what performance-conscious programmers want to control, how they want to control it, and what they want to automate, even in relatively narrow domains. We claim that USLs should, instead, be designed to grow. We present Exo 2, a scheduling language that enables users to define new scheduling operations externally to the compiler. By composing a set of trusted, fine-grained primitives, users can safely write their own scheduling library to build up desired automation. We identify actions (ways of modifying code), inspection (ways of interrogating code), and references (ways of pointing to code) as essential for any user-extensible USL. We fuse these ideas into a new mechanism called Cursors that

ALT We implemented Exo 2 on top of the Exo object language. Exo object code will be framed in boxes to distinguish it from Exo 2 scheduling code (without the frame) throughout the paper. We introduce Exo with a matrix-vector multiply example (gemv, inset above), although the specifics of Exo are mostly incidental to this paper. Both procedure arguments and variable declarations follow the syntax ⟨𝑛𝑎𝑚𝑒⟩:⟨𝑡𝑦𝑝𝑒⟩[⟨𝑠𝑖𝑧𝑒⟩] @ ⟨𝑚𝑒𝑚𝑜𝑟𝑦⟩. In gemv, f32 is a numeric type for 32-bit floating point. The ⟨𝑠𝑖𝑧𝑒⟩s may be constants, or refer dependently to other arguments (e.g., [M,N]) as they do here. The @ symbol, followed by a mem- ory space identifier, specifies the memory space where the variable or argument resides (e.g., @DRAM). The asserts guarantee that all sizes are even multiples of 8, which can be exploited during scheduling. Finally, for i in seq(0, M) is a sequential for loop that iterates from 0 to 𝑀 − 1, inclusive. In Exo 2, schedules are Python meta-programs that ...

ALT Figure 7. 7b encapsulates BLAS level 2, skinny matrix-specific optimization in a single library function, used to optimize both transpose (7c) and non-transpose (7a) gemv and ger, amortizing the cost of writing schedules across kernel variants.

ALT Figure 10. Exo 2 implementation of Halide’s blur_x.compute_at(blur_y, x) operation. The starting code is a tiled version of the blur algorithm. We first fuse the blur_x and blur_y computations at the y loop level, and then fuse at the x loop level. Focusing on the second fusion, the bounds inference inspection described in Section 4 determines the producer (blur_x) accesses in the x loop. Then, a sequence of primitive actions is applied to the object code to yield code fused at the x loop level. Figure 11. Halide’s blur algorithm and schedule. Figure 12. Exo 2’s blur schedule. Figure 13. Exo 2 schedules show competitive performance to corresponding expert-written Halide schedules on a variety of image sizes