Mind mappings: enabling efficient algorithm-accelerator mapping space search
Authors:
Top Cited Papers
Open Access
- 17 April 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 943-958
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), Mind Mapping finds mappings that achieve an average 1.40×, 1.76×, and 1.29× (when run for a fixed number of steps) and 3.16×, 4.19×, and 2.90× (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× higher EDP than a possibly unachievable theoretical lower-bound, indicating proximity to the global optima.Keywords
All Related Versions
Funding Information
- DARPA SDH (HR0011-18-3-0007)
- NSF (942888)
This publication has 56 references indexed in Scilit:
- 340 mV–1.1 V, 289 Gbps/W, 2090-Gate NanoAES Hardware Accelerator With Area-Optimized Encrypt/Decrypt GF(2 4 ) 2 Polynomials in 22 nm Tri-Gate CMOSIEEE Journal of Solid-State Circuits, 2015
- Measuring the curse of dimensionality and its effects on particle swarm optimization and differential evolutionApplied Intelligence, 2014
- A comparative review of approaches to prevent premature convergence in GAApplied Soft Computing, 2014
- A large population size can be unhelpful in evolutionary algorithmsTheoretical Computer Science, 2012
- Efficient BackProp2012
- Parameter Tuning of Evolutionary Algorithms: Generalist vs. Specialist2010
- Efficiently exploring architectural design spaces via predictive modelingACM SIGOPS Operating Systems Review, 2006
- Surrogate-based analysis and optimizationProgress in Aerospace Sciences, 2005
- Optimization by Simulated AnnealingScience, 1983
- Analysis of Individual Differences in Multidimensional Scaling Via an N-way Generalization of “Eckart-Young” DecompositionPsychometrika, 1970