CoSA: Scheduling by Constrained Optimization for Spatial Accelerators
Authors:
Top Cited Papers
- 1 June 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 554-566
Abstract
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.5× across a wide range of DNN networks while improving the time-to-solution by 90×.Keywords
All Related Versions
This publication has 57 references indexed in Scilit:
- ShiDianNao2015
- OpenTuner2014
- Chlorophyll2014
- DianNaoACM SIGPLAN Notices, 2014
- When polyhedral transformations meet SIMD code generation2013
- Automatic memory partitioning and scheduling for throughput and power optimizationACM Transactions on Design Automation of Electronic Systems, 2011
- A practical automatic polyhedral parallelizer and locality optimizer2008
- Automatic generation of peephole superoptimizers2006
- An efficient and versatile scheduling algorithm based on SDC formulation2006
- Programming by sketching for bit-streaming programs2005