TinyML and Efficient Deep Learning Computing

Lecture notes for courses MIT 6.S965, Fall 2022 | MIT 6.5940, Fall 2023•2024

Courses

Lecture Notes

📖 Basics of Deep Learning

• Basic Terminologies, Shape of Tensors

Synapse(weight), Neuron(activation), Cell body

Fully-Connected layer, Convolution layer(padding, stride, receptive field, grouped convolution), Pooling layer

• Efficiency Metrics

Metrics(latency, storage, energy)

Memory-Related(#parameters, model size, #activations), Computation(MACs, FLOP)

📙 Efficient Inference

• Pruning Granularity, Pruning Critertion

Unstructured/Structured pruning(Fine-grained/Pattern-based/Vector-level/Kernel-level/Channel-level)

Pruning Criterion: Magnitude(L1-norm, L2-norm), Sensitivity and Saliency(SNIP), Loss Change(First-Order, Second-Order Taylor Expansion)

Data-Aware Pruning Criterion: Average Percentage of Zero(APoZ), Reconstruction Error, Entropy

• Automatic Pruning, Lottery Ticket Hypothesis

Finding Pruning Ratio: Reinforcement Learning based, Rule based, Regularization based, Meta-Learning based

Lottery Ticket Hypothesis(Winning Ticket, Iterative Magnitude Pruning, Scaling Limitation)

Pruning at Initialization(Connection Sensitivity, Gradient Flow)

• System & Hardware Support for Fine-grained Sparsity

Efficient Inference Engine(EIE format: relative index, column pointer)

• Sparse Matrix-Matrix Multiplication, GPU Support for Sparsity

Sparse Matrix-Matrix Multiplication(SpMM), CSR format

GPU Support for Sparsity: Hierarchical 1-Dimensional Tiling, Row Swizzle, M:N Sparsity, Block SpMM(Blocked-ELL format), PatDNN(FKW format)

• Basic Concepts of Quantization

Numeric Data Types: Integer, Fixed-Point, Floating-Point(IEEE FP32/FP16, BF16, NVIDIA FP8), INT4 and FP4

Uniform vs. Non-uniform quantization, Symmetric vs. Asymmetric quantization

Linear Quantization: Integer-Arithmetic-Only Quantization, Sources of Quantization Error(clipping, rounding, scaling factor, zero point)

• Vector Quantization

Vector Quantization(Deep compression: iterative pruning, K-means based quantization, Huffman encoding), Product Quantization

• Post Training Quantization

Weight Quantiztion: Per-Tensor Activation Per-Channel Activation, Group Quantization(Per-Vector, MX), Weight Equalization, Adative Rounding

Activation Quantization: During training(EMA), Calibration(Min-Max, KL-divergence, Mean Squared Error)

Bias Correction, Zero-Shot Quantization(ZeroQ)

• Quantization-Aware Training, Low bit-width quantization

Fake quantization, Straight-Through Estimator

Binary Quantization(Deterministic, Stochastic, XNOR-Net), Ternary Quantization

• Neural Architecture Search: basic concepts & manually-designed neural networks

input stem, stage, head

AlexNet, VGGNet, SqueezeNet(fire module), ResNet(bottleneck block, residual connection), ResNeXt(grouped convolution)

MobileNet(depthwise-separable convolution, width/resolution multiplier), MobileNetV2(inverted bottleneck block), ShuffleNet(channel shuffle), SENet(squeeze-and-excitation block), MobileNetV3(h-swish)

• Neural Architecture Search: Search Space

Search Space: Macro, Chain-Structured, Cell-based(NASNet), Hierarchical(Auto-DeepLab, NAS-FPN)

design search space: Cumulative Error Distribution, FLOPs distribution, zero-cost proxy

• Neural Architecture Search: Performance Estimation & Hardware-Aware NAS

Weight Inheritance, HyperNetwork, Weight Sharing(super-network, sub-network)

Performance Estimation Heuristics: Zen-NAS, GradSign

• Knowledge Distillation

Knowledge Distillation(distillation loss, softmax temperature)

What to Match?: intermediate weights, features(attention maps), sparsity pattern, relational information

Distillation Scheme: Offline Distillation, Online Distillation, Self-Distillation

• Distillation for Applications

Applications: Object Detection, Semantic Segmentation, GAN, NLP

Tiny Neural Network: NetAug

• MCUNet

MCUNetV1: TinyNAS, TinyEngine

MCUNetV2: MCUNetV2 architecture(MobileNetV2-RD), patch-based inference, joint automated search

⚙️ Efficient Training and System Support

• On-device Training, Transfer Learning

Efficient Transfer Learning: TinyTL(Bias-only Fine-tuning, Lite residual module)

Sparse Layer/Tensor Update(Contribution Analysis), Real Quantized Training

• Tiny Training Engine

Intermediate Representation(IR), Compile-Time Autodiff

Graph-level Optimization(Sparse Update, Operation Reordering)

• Compilers, Graph-level Optimization

Compilers: Halide, TVM, AutoTVM

Graph-level Optimization Framework: MetaFlow, IOS

• Microcontroller, Loop Optimization

Memory Hierarchy of Microcontroller, Primary Memory Format(NCHW, NHWC, CHWN)

Parallel Computing Techniques: Loop Optimization(Unrolling, Reordering, Tiling)

• Inference Optimization

Parallel Computing Techniques: SIMD Programming(CMSIS-NN)

Inference Optimization: Im2col, In-place, Choosing Data Layout(pointwise, depthwise), Winograd Convolution

🔧 Domain-Specific Optimizations

• Transformer

NLP Task(Discriminative, Generative), Pre-Transformer Era(RNN/LSTM, CNN)

Transformer: Tokenizer, Embedding, Multi-Head Attention(self-attention), Feed-Forward Network, Layer Normalization(Pre-Norm, Post-Norm), Positional Encoding

• Transformer Design Variants

Types of Transformer-based Models: Encoder-Decoder(T5), Encoder-only(BERT), Decoder-only(GPT)

Relative Positional Encoding(ALiBi, RoPE, interpolating RoPE), KV cache optimization(Multi-query Attention, Grouped-query Attention), Gated Linear Unit

• LLM Quantization

Quantization Difficulty of LLMs, Bottleneck of edge LLM Inference(Memory-bounded, Memory footprint of Weights)

Weight-activation Quantization: SmoothQuant(Activation Smoothing)

Weight-only Quantization: AWQ(1% Salient Weights, Activation-aware Scaling)

• Efficient System Support for LLM Quantization

System for Edge: TinyChat(Hardware-aware Weight Packing, Kernel Fusion)

System for Cloud: Overhead in Quantized GEMM, QServe(SmoothAttention, Dequantization with Reg-Level Parallelism)

• LLM Pruning & Sparsity

Weight Sparsity: Wanda

Contextual Sparsity: Deja Vu, Mixture-of-Experts

Attention Sparsity: SpAtten, H2O

• LLM Serving Systems

Metrics for LLM Serving(TTFT, TPOT, Latency, Throughput), Heuristics for Evaluation

PagedAttention(vLLM), FlashAttention, Speculative Decoding, Batching(Static, Dynamic, Continuous)

• LLM Post Training

Supervised Fine-Tuning, Reinforcement Learning from Human Feedback, Direct Preference Optimization

Parameter-Efficient Fine-Tuning: Additive(Adapter, Prompt/Prefix Tuning) Selective(BitFit), Reparameterized(LoRA)

PEFT Quantization: QLoRA, BitDelta

• Prompt Engineering

In-Context Learning: Zero-Shot Prompting, Few-Shot Prompting

Chain-of-Thought, Retrieval Augmented Generation

• Long Context LLM

LongLoRA(Shifted Sparse Attention), StreamingLLM(Attention Sink)

The Lost in the Middle Phenomenon, Needle In A Haystack Analysis, LongBench

• Efficient Attention, Beyond Transformers

DuoAttention(Retrieval, Streaming Head), Quest(Query-Aware Sparsity)

Mamba(Selective State-Space Models), Jamba

• Vision Transformer

Vision Transformer, High-Resolution Dense Prediction(Segment Anything)

Window Attention(Swin Transformer, FlatFormer), ReLU Linear Attention(EfficientViT, EfficientViT-SAM), Sparse Attention(SparseViT)

• ViT Training, AR Image Generation

Contrastive Learning(CLIP), Masked Image Modeling

Multi-modal LLMs(Flamingo, PaLM-E)

Autoregressive Image Generation(VAR, HART)

• Efficient Video Understanding

2D CNNs for Video Understanding, 3D CNNs for Video Understanding(I3D), Temporal Shift Module(TSM)

Other Efficient Methods: Kernel Decomposition, Multi-Scale Modeling, Neural Architecture Search(X3D), Skipping Redundant Frames/Clips, Utilizing Spatial Redundancy

• Generative Adversarial Networks (GANs)

GANs(Generator, Discriminator), Conditional/Unconditional GANs, Difficulties in GANs

Compress Generator(GAN Compression), Dynamic Cost GANs(Anycost GANs), Data-Efficient GANs(Differentiable Augmenatation)

• Efficient Point Cloud Recognition

3D Data: Point Clouds, Multi-view Images(Range Image, BEV Projection), Voxels(Dense, Sparse), Octree

Hybrid: Point-Voxel CNN(PVCNN, SPVConv), BEVFusion