Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural Networks for Edge Devices

Byung Hoon Ahn, Jinwon Lee, Jamie Menjay Lin, Hsin-Pai Cheng, Jilei Hou, Hadi Esmaeilzadeh

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

Abstract

Recent advances demonstrate that irregularly wired neural networks from Neural Architecture Search (NAS) and Random Wiring can not only automate the design of deep neural networks but also emit models that outperform previous manual designs. These designs are especially effective while designing neural architectures under hard resource constraints (memory, MACs, . . . ) which highlights the importance of this class of designing neural networks. However, such a move creates complication in the previously streamlined pattern of execution. In fact one of the main challenges is that the order of such nodes in the neural network significantly effects the memory footprint of the intermediate activations. Current compilers do not schedule with regard to activation memory footprint that it significantly increases its peak compared to the optimum, rendering it not applicable for edge devices. To address this standing issue, we present a memory-aware compiler, dubbed SERENITY, that utilizes dynamic programming to find a sequence that finds a schedule with optimal memory footprint. Our solution also comprises of graph rewriting technique that allows further reduction beyond the optimum. As such, SERENITY achieves optimal peak memory, and the graph rewriting technique further improves this resulting in 1.68x improvement with dynamic programming-based scheduler and 1.86x with graph rewriting, against TensorFlow Lite with less than one minute overhead.
BibTeX
@inproceedings{ahn2020ordering,
  author = {Byung Hoon Ahn and Jinwon Lee and Jamie Menjay Lin and Hsin-Pai Cheng and Jilei Hou and Hadi Esmaeilzadeh},
  title = {{Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural Networks for Edge Devices}},
  booktitle = {MLSys},
  year = {2020},
}
Figure