TL;DR
This paper introduces SERENITY, a novel compiler optimization framework that tackles the challenge of efficiently scheduling irregularly wired neural networks on memory-constrained edge devices. By employing dynamic programming with adaptive soft budgeting and identity graph rewriting, SERENITY significantly reduces peak memory footprint and off-chip traffic, enabling deployment of advanced AI models on resource-limited hardware.
What Problem Does This Paper Address?
The increasing popularity of Neural Architecture Search (NAS) and Random Network Generators has led to the development of neural networks with highly irregular connection patterns. While these "irregularly wired" networks often achieve superior accuracy and can adapt to hardware constraints, their complex execution flow poses a significant challenge for deployment on edge devices. Conventional deep learning compilers and frameworks, designed for regular network topologies, struggle with the unpredictable and potentially large peak memory footprint of these irregular networks, often exceeding the limited memory capacity of edge devices. This paper addresses the critical need for a scheduling mechanism that can optimize these irregular networks for memory efficiency on edge hardware.
Methods
SERENITY employs a multi-pronged approach:
- Dynamic Programming-based Scheduling: The core of SERENITY is a dynamic programming algorithm that searches for an optimal node schedule to minimize peak memory footprint. It leverages graph properties to identify and memoize repeated subproblems (signatures of zero-indegree sets), significantly reducing the search space compared to brute-force topological ordering.
- Adaptive Soft Budgeting: To further accelerate the scheduling process, SERENITY incorporates an adaptive soft budgeting technique. This involves a meta-search that dynamically adjusts a memory budget to prune suboptimal paths, balancing compilation time with the likelihood of finding a solution. It uses a binary search approach, guided by an initial estimate from Kahn's algorithm, to find an effective budget.
- Identity Graph Rewriting: To overcome the inherent limitations of scheduling based on the original graph topology, SERENITY introduces an identity graph rewriting scheme. This technique transforms the graph by substituting specific patterns (e.g., concatenation followed by convolution or depthwise convolution) with equivalent operations that have a lower memory footprint, without altering the network's mathematical integrity.
Datasets
The paper evaluates SERENITY on representative irregularly wired neural networks, including:
- DARTS (learned normal cell for ImageNet)
- SwiftNet (for Human Presence or Absence dataset)
- RandWire (for CIFAR10 and CIFAR100 datasets)
These networks are derived from Neural Architecture Search (NAS) and Random Network Generators.
Key Insights and Ideas
- Irregularity is a Feature, Not a Bug (for Edge): Irregularly wired networks, while challenging to schedule, can be designed to better fit hardware constraints than their regular counterparts.
- Scheduling is Key to Memory Footprint: The order in which nodes are executed has a profound impact on the peak memory required, especially for irregular networks.
- Dynamic Programming for Memory Optimization: By treating scheduling as a dynamic programming problem and identifying reusable subproblems, significant efficiency gains can be achieved.
- Adaptive Budgeting for Practical Compilation: A fixed memory budget can be too restrictive or too loose. An adaptive approach that dynamically searches for an optimal budget is crucial for balancing compilation time and solution quality.
- Graph Rewriting for Deeper Memory Savings: Modifying the network's computational graph itself, through identity graph rewriting, can unlock further memory footprint reductions beyond what scheduling alone can achieve.
Key Results
SERENITY demonstrates significant improvements over TensorFlow Lite:
- Memory Footprint Reduction: An average of 1.86x reduction in peak memory footprint, with graph rewriting contributing an additional 10.7%.
- Off-chip Traffic Reduction: A 1.76x reduction in off-chip traffic for devices with memory hierarchy, and in some cases, complete elimination of off-chip traffic.
- Compilation Time: An average of less than one minute of extra compilation time, making it practical for edge deployment.
- Scheduling Efficiency: The combination of dynamic programming, divide-and-conquer, and adaptive soft budgeting makes scheduling tractable, with average scheduling times around 40-50 seconds.
Limitations and Future Work
- Complexity of Dynamic Programming: While significantly improved, the dynamic programming approach still has an exponential time complexity of O(|V| × 2|V|), which could be a bottleneck for extremely large graphs.
- Graph Rewriting Scope: The paper focuses on specific graph rewriting patterns (channel-wise and kernel-wise partitioning for convolution and depthwise convolution). Future work could explore a wider range of rewriting rules.
- Hardware Specificity: While targeting edge devices, the current evaluation is general. Further work could explore hardware-specific optimizations and co-design.
- Future Work: The authors suggest that their work is an initial step towards orchestrating irregular networks under stringent memory constraints and that compiler techniques enabling new forms of intelligent workloads hold significant potential.
Summary updated