CoSA: Scheduling by Constrained Optimization for Spatial Accelerators
  Recent advances in Deep Neural Networks (DNNs) have led to active development
of specialized DNN accelerators, many of which feature a large number of
processing elements laid out spatially, together with a multi-level memory
hierarchy and flexible interconnect. While DNN accelerators can take advantage
of data reuse and achieve high peak throughput, they also expose a large number
of runtime parameters to the programmers who need to explicitly manage how
computation is scheduled both spatially and temporally. In fact, different
scheduling choices can lead to wide variations in performance and efficiency,
motivating the need for a fast and efficient search strategy to navigate the
vast scheduling space.
  To address this challenge, we present CoSA, a constrained-optimization-based
approach for scheduling DNN accelerators. As opposed to existing approaches
that either rely on designers' heuristics or iterative methods to navigate the
search space, CoSA expresses scheduling decisions as a constrained-optimization
problem that can be deterministically solved using mathematical optimization
techniques. Specifically, CoSA leverages the regularities in DNN operators and
hardware to formulate the DNN scheduling space into a mixed-integer programming
(MIP) problem with algorithmic and architectural constraints, which can be
solved to automatically generate a highly efficient schedule in one shot. We
demonstrate that CoSA-generated schedules significantly outperform
state-of-the-art approaches by a geometric mean of up to 2.5x across a wide
range of DNN networks while improving the time-to-solution by 90x.
