Efficient Winograd or Cook-Toom Convolution Kernel Implementation on Widely Used Mobile CPUs

Partha Maji, Andrew Mundy, Ganesh Dasika, Jesse G. Beu, Matthew Mattina, Robert D. MullinsarXiv 2019 · OpenReview

TL;DR

This paper tackles the challenge of efficiently implementing computationally intensive Winograd/Cook-Toom convolution algorithms on resource-constrained mobile CPUs. By developing a novel region-wise multi-channel approach and leveraging ARMv8-A NEON SIMD instructions, they achieve significant inference latency reductions, up to 60%, compared to traditional methods on widely used mobile processors.

What Problem Does This Paper Address?

The increasing demand for AI at the "edge" – on devices like smartphones and wearables – necessitates efficient execution of deep neural networks (DNNs), particularly Convolutional Neural Networks (CNNs). While algorithmic optimizations like Winograd and Cook-Toom offer substantial theoretical reductions in computation for CNNs, their practical implementation on embedded CPUs, which are characterized by limited memory and power budgets, has been largely overlooked. This paper aims to bridge this gap by demonstrating how these advanced convolution algorithms can be effectively implemented and accelerated on common mobile processors like Arm Cortex-A.

Methods

The core of the paper's contribution lies in its novel region-wise multi-channel scheme for implementing Winograd or Cook-Toom convolutions. This approach breaks down the input tensor into smaller regions and processes them in a multi-channel manner. Key techniques include:

  • Leveraging ARMv8-A NEON SIMD Instructions: The authors heavily utilize the SIMD (Single Instruction, Multiple Data) capabilities of ARMv8-A processors to perform parallel computations on multiple data elements simultaneously.
  • NHWC Data Layout Preference: While NCHW is common, the paper argues for the NHWC (Number, Channels, Height, Width) layout for better SIMD utilization, especially when dealing with multiple channels. This allows for more efficient loading and processing of data within SIMD registers.
  • GEMM-based Hadamard Product Computation: The paper frames the core operation of Winograd/Cook-Toom (element-wise multiply-accumulate) as a General Matrix Multiplication (GEMM) problem, allowing them to leverage highly optimized GEMM libraries.
  • Input and Output Transforms: The Winograd/Cook-Toom algorithms involve transforming data into a different domain, performing computations, and then transforming it back. The paper details efficient implementations of these input and output transforms tailored for the target architecture.

Datasets

The paper does not discuss training datasets. Instead, it focuses on evaluating the inference performance of existing, well-known CNN models.

  • Models Evaluated: VGG19, VGG16, GoogleNet, Inception-v3, and SqueezeNet. These represent a range of CNN architectures with varying complexities.
  • Evaluation Platform: Huawei HiKey 960 development platform, specifically utilizing the Arm Cortex-A73 cores.

Key Insights and Ideas

  • The "Edge" Demands Efficient Algorithms: The paper strongly advocates for the necessity of optimizing advanced algorithms like Winograd/Cook-Toom for edge devices, moving beyond theoretical speedups to practical, real-world performance.
  • NHWC is King for SIMD on Mobile: The authors make a compelling case for the NHWC data layout on ARMv8-A, demonstrating how it better aligns with SIMD register capabilities for processing multiple channels efficiently.
  • Transform Costs are Real: While Winograd/Cook-Toom offer significant computational savings, the paper acknowledges that the overhead of transforming data to and from the alternative domain can impact overall speedup. Amortizing these costs over multiple operations is crucial.
  • Leveraging Existing Optimizations: The paper effectively combines algorithmic advancements (Winograd/Cook-Toom) with low-level hardware optimizations (NEON SIMD) and established computational frameworks (GEMM) for maximum impact.

Key Results

  • Significant Inference Latency Reduction: The proposed region-wise multi-channel Winograd/Cook-Toom implementation achieves substantial performance improvements.
  • Full Network Speedup: Up to 60% improvement over existing im2row/im2col based techniques.
  • Per-Layer Speedup: Average speedups of 2-3x and peak speedups of 4x over aggressively optimized classical im2row/col techniques.
  • Practical Performance: For SqueezeNet on Cortex-A73, the implementation achieves an average inference rate of 47 frames/sec, which is sufficient for many real-time embedded applications.
  • Scalability: The authors suggest their scheme can be readily deployed to other widely used ARMv8-A cores.

Limitations and Future Work

  • Theoretical vs. Achieved Speedup: The paper acknowledges that the achieved speedups are lower than theoretical maximums. This is attributed to the overhead of data transformations and the challenges of implementing these algorithms in a real system.
  • Amortizing Transform Costs: A key area for future improvement is further optimizing the transform stages to better amortize their costs, especially for smaller layers where transform overhead can be more significant.
  • Broader Architecture Support: While tested on Cortex-A73, extending the implementation to other ARMv8-A cores and potentially other embedded architectures would be a natural next step.
  • Energy Efficiency: While the paper focuses on latency reduction, further investigation into the energy efficiency benefits of this approach would be valuable for embedded systems.

Summary updated

Abstract

The Winograd or Cook-Toom class of algorithms help to reduce the overall compute complexity of many modern deep convolutional neural networks (CNNs). Although there has been a lot of research done on model and algorithmic optimization of CNN, little attention has been paid to the efficient implementation of these algorithms on embedded CPUs, which usually have very limited memory and low power budget. This paper aims to fill this gap and focuses on the efficient implementation of Winograd or Cook-Toom based convolution on modern Arm Cortex-A CPUs, widely used in mobile devices today. Specifically, we demonstrate a reduction in inference latency by using a set of optimization strategies that improve the utilization of computational resources, and by effectively leveraging the ARMv8-A NEON SIMD instruction set. We evaluated our proposed region-wise multi-channel implementations on Arm Cortex-A73 platform using several representative CNNs. The results show significant performance improvements in full network, up to 60%, over existing im2row/im2col based optimization techniques
BibTeX
@misc{maji2019efficient,
  author = {Partha Maji and Andrew Mundy and Ganesh Dasika and Jesse G. Beu and Matthew Mattina and Robert D. Mullins},
  title = {{Efficient Winograd or Cook-Toom Convolution Kernel Implementation on Widely Used Mobile CPUs}},
  year = {2019},
  eprint = {1903.01521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.01521},
}
Figure