Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Search

Abstract

Modern day computing increasingly relies on specialization to satiate growing performance and efficiency requirements. A core challenge in designing such specialized hardware architectures is how to perform mapping space search, i.e., search for an optimal mapping from algorithm to hardware. Prior work shows that choosing an inefficient mapping can lead to multiplicative-factor efficiency overheads. Additionally, the search space is not only large but also non-convex and non-smooth, precluding advanced search techniques. As a result, previous works are forced to implement mapping space search using expert choices or sub-optimal search heuristics. This work proposes Mind Mappings, a novel gradient-based search method for algorithm-accelerator mapping space search. The key idea is to derive a smooth, differentiable approximation to the otherwise non-smooth, non-convex search space. With a smooth, differentiable approximation, we can leverage efficient gradient-based search algorithms to find high-quality mappings. We extensively compare Mind Mappings to black-box optimization schemes used in prior work. When tasked to find mappings for two important workloads (CNN and MTTKRP), the proposed search finds mappings that achieve an average $1.40\times$, $1.76\times$, and $1.29\times$ (when run for a fixed number of steps) and $3.16\times$, $4.19\times$, and $2.90\times$ (when run for a fixed amount of time) better energy-delay product (EDP) relative to Simulated Annealing, Genetic Algorithms and Reinforcement Learning, respectively. Meanwhile, Mind Mappings returns mappings with only $5.32\times$ higher EDP than a possibly unachievable theoretical lower-bound, indicating proximity to the global optima.

Appears in the proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '21), April 19-23, 2021, Virtual, USA

References in corpus (20)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• XGBoost: A Scalable Tree Boosting System
• Efficient Estimation of Word Representations in Vector Space
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Neural Architecture Search with Reinforcement Learning
• The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
• Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• SCALE-Sim: Systolic CNN Accelerator Simulator
• REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
• EIE: Efficient Inference Engine on Compressed Deep Neural Network
• SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks
• Backpropagation through the Void: Optimizing control variates for black-box gradient estimation
• Ithemal: Accurate, Portable and Fast Basic Block Throughput Estimation using Deep Neural Networks
• An Alternative View: When Does SGD Escape Local Minima?
• Black-Box Optimization with Local Generative Surrogates
• Adversarial Variational Optimization of Non-Differentiable Simulators
• Marvel: A Data-centric Compiler for DNN Operators on Spatial Accelerators
• Constructing Deep Neural Networks by Bayesian Network Structure Learning
• Reinforcement Learning and Adaptive Sampling for Optimized DNN Compilation

Cited by in corpus (10)

• A Full-Stack Search Technique for Domain Optimized Deep Learning Accelerators
• FEATHER: A Reconfigurable Accelerator with Data Reordering Support for Low-Cost On-Chip Dataflow Switching
• HighLight: Efficient and Flexible DNN Acceleration with Hierarchical Structured Sparsity
• Shared Memory-contention-aware Concurrent DNN Execution for Diversely Heterogeneous System-on-Chips
• How to keep pushing ML accelerator performance? Know your rooflines!
• Stream: Design Space Exploration of Layer-Fused DNNs on Heterogeneous Dataflow Accelerators
• CoSA: Scheduling by Constrained Optimization for Spatial Accelerators
• Search for Optimal Systolic Arrays: A Comprehensive Automated Exploration Framework and Lessons Learned
• Data-Driven Offline Optimization For Architecting Hardware Accelerators
• Union: A Unified HW-SW Co-Design Ecosystem in MLIR for Evaluating Tensor Operations on Spatial Accelerators