Slide 1: Solving unsolvable combinatorial problems with AI
January 31, 2023 Solving unsolvable combinatorial problems with AI Chris Lott Senior Director, Engineering Qualcomm Technologies, Inc. @QCOMResearch
Slide 2: Today's agenda
Today’s agenda • The need for combinatorial optimization • Solving combinatorial optimization problems with AI • Improved chip design with AI • Improved compilers with AI • Future directions • Questions? 3
Slide 3: How do you find an optimal solution when faced with many choices?
How do you find an optimal solution when faced with many choices? Some problems have more possible solutions than a game of Go: ~10 170 4
Slide 4: Combinatorial optimization problems are all around us
Combinatorial optimization problems are all around us Supply chain optimization Hardware-specific compiler Finding solutions can provide significant benefits: • Reducing cost • Reducing time • Increasing performance Airline network planning Chip design 5
Slide 5: Traveling Salesman Problem (TSP)
Traveling Salesman Problem (TSP) Exemplifies the combinatorial optimization problem Given a set of N cities with travel distance between each pair, find the shortest path that visits each city exactly once Example: Using a brute force search method, if a computer can check a solution in a microsecon
Slide 6: How to approach solving TSP with brute force
An instance of the Search space Search space traveling salesman problem a (represented as a tree) a • Start at any city 100 b 100 75 • Choose from N-1 next cities 125 125 100 75 100 b c d e • Choose from N-2 next cities 75 50 150 • ...... e c 125 125 d e • Choose last city and connect 50 c 250 to st
Slide 7: Existing TSP solutions face challenges
Existing TSP solutions face challenges C 7 B C 7 B An instance of the 8 5 8 5 traveling salesman problem Search space 4 7 6 A 4 7 6 A N0 6 cost = 25 a a 6 100 b 7 9 7 9 125 D 3 E D 3 E 75 100 100 75 125 100 75 N1 N2 N3 N4 50 b c d e cost = 35 cost = 53 cost = 25 cost = 31 e C 7 B C 7 B 125 125 150 B
Slide 8: Existing combinatorial optimization techniques have limitations
Existing combinatorial optimization techniques have limitations Scale Learning Search heuristics don’t scale to larger problems in Techniques don’t incorporate knowledge learned acceptable compute time and cost, and do not from solving many problems. They start each guarantee satisfaction of all the
Slide 9: AI addresses challenges of traditional combinatorial optimization solutions
AI process Standard process AI addresses challenges of traditional combinatorial Optimization optimization solutions metric Leverages learned problem structure 𝒑𝒂𝒓𝒂𝒎𝒆𝒕𝒆𝒓𝒔 AI Heuristics AI Solver Scales to larger instances Offers a general framework Develop an AI algorithm that can learn…
Slide 10: Optimizing chip design with AI
Optimizing chip design with AI Exploring Bayesian optimization to reduce combinatorial search space “Bayesian Optimization for Macro Placement”, ICML 2022
Slide 11: Competing combinatorial optimization objectives in chip design
Production Design cost reduction efficiency Chip Yield – more Test # of tools iterations License cost Area complex fab process Time Power-performance Capital optimization expense (Capex) System-level power Chip-level power # of compute servers Emulation platforms Competing combinatorial optimization
Slide 12: Semiconductor scaling advantage is approaching a cliff
Semiconductor scaling advantage is approaching a cliff Foundation Key elements Disruption Moore’s Law 50% Chips PPA scaling less gain Design Combinatorial 100x automation optimization PVT corners Cloud 10x Computing servers expense PPA = Power, Performance, Area 13
Slide 13: Area scaling over time
Area scaling over time 1 Stdcell Analog/IO Scaling 0,1 SRAM bitcell Memory 0.5X / 2yr Digital logic analog/IO Theoretical Moore’s Law 0,01 2012 2014 2016 2018 2020 2022 2024 2026 2028 2030 Year CO needs to compensate for diminishing technology gains and PVT corner increase within acceptable compute
Slide 14: How can we solve the chip optimization problem?
How can we solve the chip optimization problem? Challenges Standard cells (logic gates) 0 (107 — 109) in chip Point-like placement: AND 1. Placing mixed-size blocks – standard cells and macros Macros (memories) (memories) 0 (10 — 100) Minimize power and area while satisfying timing constraints withi
Slide 15: Chip design is comprised of iterative macro and standard cell placement
Chip design is No-overlap 2D: comprised of 𝑁! ! Inner loop iterative macro and standard cell placement A complex and very computationally intensive part of chip design Hours-days Designers manually select a macro placement and use solvers to Macro placement Cell placement optimize the standard cell
Slide 16: Bayesian optimization efficiently solves problems iteratively
Bayesian optimization efficiently solves problems iteratively True function Goal ⋆: Data Surrogate Find minimum of an expensive function Surrogate Cost uncertainty 1. Fit a probabilistic surrogate Search space model Exploration of highly uncertain areas vs Cost (tradeoff) 3. 2. Exploitation of promi
Slide 17: Bayesian optimization for macro layout
Bayesian Inner loop optimization for macro layout Inner loop optimization incorporated into PPA surrogate function (50!)2 ≈ 10128 Hours-days Macro placement Cell placement Surrogate function Outer loop Bayesian optimization learns a surrogate function, which maps each macro placement to a PPA qualit
Slide 18: Bayesian optimization can converge faster
Simulated annealing Bayesian optimization can Wire length converge faster with better design metrics compared to conventional simulated annealing heuristics for an unconstrained version Number of evaluations Number of evaluations Number of evaluations of the problem Bayesian optimization Results are
Slide 19: Data-driven AI optimization can aid designers
Algorithmic optimization Data-driven AI optimization based on analytic can aid designers with fast solutions needs evaluations and guide human guidance algorithmic optimization with optimal inputs Slow, costly, Fast, cheap, but accurate and for sign-off and accurate for automation optimization 20
Slide 20: AI compilers can be optimized with AI
AI compilers can be optimized with AI AI can improve core components of compilers, including sequencing, scheduling, tiling, and placement “Neural topological ordering for computation graphs”, NeurIPS 2022
Slide 21: Tools: Qualcomm AI Model Studio
AI Frameworks Tools: Qualcomm AI AI Runtimes Model Studio Qualcomm® Neural Processing SDK TF Lite Micro Direct ML TF Lite Qualcomm® AI Engine Direct AIMET AIMET Model Zoo Math Libraries Compilers Virtual platforms NAS Profilers & Debuggers Programming Languages Core Libraries Model analyzers System
Slide 22: The AI compiler converts an input neural net into an efficient program
Neural net Sequencing Compiler Sequencing Tiling Placement Scheduling Deployment … Tiling and placement Sequencing Deployment Splits net blocks into efficient Determines the best compute Puts the resulting code Ops and places them ordering of the nodes generated code onto on multiple compute devices
Slide 23: The runtime on the target device is expensive to evaluate
The runtime on the target device is expensive to evaluate • It can take minutes to set up the compiler with all your decisions and run one computation graph • Quite a large decision space • Goal: minimizing the runtime of the pipeline over the space of tiling, sequencing, and scheduling choices • Me
Slide 24: Sequencing has a big impact on memory usage
Sequencing has a big impact on memory usage Option #1: Data pre-fetch Option #2: Low memory utilization ACT_0 ACT_1 ACT_0 ACT_1 WT_A CONV_A_0 CONV_A_1 WT_A CONV_A_0 CONV_A_1 Minimizing memory usage: WT_B CONV_B_0 CONV_B_1 WT_B CONV_B_0 CONV_B_1 • Maximizes inferences/sec by reducing waits for extern
Slide 25: Sequencing computation graphs to minimize memory usage
Sequencing computation graphs to minimize memory usage Computation graph (Ops) Path cost during execution progression of improvements • # sequences is # node permutations that follow precedence constraints • Grows exponentially in # nodes in compute graph Input Objective Application A computation gr
Slide 26: End-to-end machine learning (ML) for sequencing
End-to-end machine learning (ML) for sequencing ML-based sequencer Embedding Propagator Sequencer Sequence probabilities Policy Net Search Input compute sampling, beam Embed Encoder Decoder Ordering graph RL-trained search, greedy agent Key components Initial embeddings Encoder Decoder Objective Use
Slide 27: A combination of real and synthetic graphs used for training
Synthetic graphs Real graphs We released the algorithm to make these A combination of real and synthetic graphs used for training We developed a novel approach to generating realistic synthetic graphs since real graph data is scarce 28
Slide 28: Our model generalizes well and beats baselines comprehensively
Real graphs test set (23 graphs) Our model generalizes well and beats baselines comprehensively Memory usage gap % • Dataset of 115 representative graphs • Size: few dozen to 1k nodes • Our model performs better and is much faster • Results on Snapdragon 8 Sequence generation time BS: Beam Search; D
Slide 29: End-to-end ML for scheduling
End-to-end ML Directed Acyclic Graph for scheduling (DAG) Maximize utilization of parallel hardware while maintaining sequence duration Input 1 1.0 A computation graph with Op durations, set of compute devices 2 2 1.0 Output Schedule: Define the start time 1 3 4 and device allocation for all nodes 3
Slide 30: Our end-to-end ML scheduler achieves state-of-the-art results
Node graphs Algorithm 200 – 500 500 – 700 700 – 1000 SpeedUp SpeedUp SpeedUp End-to-end ML structure CP 3.17 2.80 2.74 similar to previous for sequencing, train to Baseline minimize latency SPT 3.11 2.87 2.66 schedulers Results for a set of compute MOPNR 3.18 2.82 2.74 graphs of different sizes Achi
Slide 31: Broad range of research directions for AI combinatorial optimization
Robustify learning to distribution shift AI-augmentation of solvers Ensure good results for diverse inputs Combine best of solvers and AI methods Scale AI up to larger graphs Multi-core compiler Need to efficiently extract Further develop AI approaches global graph structure Broad range targeting ma
Slide 32: Improved combinatorial optimization techniques offer benefits across industries
Improved combinatorial optimization techniques offer benefits for a variety of use cases across industries Qualcomm AI Research has achieved state-of-the-art results in combinatorial optimization for chip design and AI compilers We are enabling combinatorial optimization technology at scale to addre
Slide 33: Questions
Questions Connect with us www.qualcomm.com/research/artificial-intelligence www.qualcomm.com/news/onq @QCOMResearch www.youtube.com/c/QualcommResearch www.slideshare.net/qualcommwirelessevolution 34
Slide 34: Thank you
Thank you Nothing in these materials is an offer to sell any of the components References in this presentation to “Qualcomm” may mean Qualcomm Incorporated, or devices referenced herein. Qualcomm Technologies, Inc., and/or other subsidiaries or business units within the Qualcomm corporate structure,