PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Multi Channel Convolution using General Matrix Multiplication

Aravind Vasudevan, Andrew Anderson, David Gregg

arXiv:1704.04428v2cs.CVcs.PF

TL;DR

CNN convolutional layers are computationally intensive, while im2col increases memory use and reduces data locality through input replication. The paper proposes GEMM-based MCMK convolution without replicated inputs and finds that its methods outperform im2col in most tested scenarios.

  • Problem

    im2col enables GEMM-based convolution but replicates input data, causing memory expansion and reduced data locality, especially problematic for memory-constrained systems.

  • Method

    The paper formulates MCMK convolution for non-replicated inputs using parallel GEMM, including a kn2row variant with one GEMM call followed by output accumulation.

  • Results

    The GEMM-based methods outperform im2col in a great majority of tested scenarios and often outperform direct convolution and Intel MKL-DNN.

  • Takeaways & Limitations

    The proposed approaches retain optimized GEMM libraries while avoiding im2col input replication and improving data locality.

Abstract

from arXiv · show

Convolutional neural networks (CNNs) have emerged as one of the most successful machine learning technologies for image and video processing. The most computationally intensive parts of CNNs are the convolutional layers, which convolve multi-channel images with multiple kernels. A common approach to implementing convolutional layers is to expand the image into a column matrix (im2col) and perform Multiple Channel Multiple Kernel (MCMK) convolution using an existing parallel General Matrix Multiplication (GEMM) library. This im2col conversion greatly increases the memory footprint of the input matrix and reduces data locality. In this paper we propose a new approach to MCMK convolution that is based on General Matrix Multiplication (GEMM), but not on im2col. Our algorithm eliminates the need for data replication on the input thereby enabling us to apply the convolution kernels on the input images directly. We have implemented several variants of our algorithm on a CPU processor and an embedded ARM processor. On the CPU, our algorithm is faster than im2col in most cases.

I. INTRODUCTION

CNN convolutional layers dominate computation, motivating GEMM-based implementations that avoid im2col’s input expansion. The paper proposes non-replicated-input formulations and evaluates them on CPU and ARM processors.

  • Convolutional layers perform most of the computation in successful CNNs.
  • GEMM provides an existing optimized routine for implementing DNN convolution on new processors and accelerators.
  • For a k × k kernel, im2col can make the column matrix k^2 times larger than the original image, stressing embedded memory and increasing traffic.
  • The proposed approach uses a non-replicated input and expresses convolution as one or a sequence of matrix multiplications.
  • The methods are evaluated on an ARM Cortex-A57 and an Intel Core i5-4570 using highly optimized parallel GEMM.
  • The new GEMM-based approaches perform better than im2col in a great majority of the tested scenarios.

II. BACKGROUND

CNNs are built from standard layers, including convolution, pooling, activation, fully connected, and loss layers.

  • CNNs commonly comprise convolutional, pooling, activation, fully connected, and loss layers.

A. Multi-channel convolution as sum of single channel convolutions

A convolutional layer maps multi-dimensional inputs and kernels to outputs by building multi-channel operations from single-channel convolutions. Multiple-channel single-kernel results are then combined across kernels.

  • A convolutional layer takes a 3D input tensor and a 4D kernel tensor and produces a 3D output tensor.
  • Single Channel Single Kernel convolution is the core operation of a convolutional layer.
  • The Multiple Channel Single Kernel operation sums 2D convolutions over corresponding input and kernel channels.
  • In this formulation, C denotes the number of input and kernel channels, while I(c) and K(c) denote their cth channels.
  • The paper excludes strided convolutions, for which output dimensions differ from input dimensions, because they represent a small proportion of computation in most CNNs.
  • Multiple Channel Multiple Kernel convolution concatenates the resultant matrices from the multiple-channel single-kernel operations.

MCMK(IC, KM

The im2col and im2row methods transform convolution into GEMM by unrolling local input patches and kernels into matrices, but they replicate or rearrange input data.

  • MCMK convolution represents M kernels with C channels and concatenates the resulting channel matrices.
  • im2col copies each input patch into a column of an intermediate input-patch matrix.
  • im2col unrolls each kernel into a row of the kernel-patch matrix and multiplies it by the input-patch matrix with GEMM.
  • im2row instead unrolls local patches into rows and kernels into columns before multiplying the two matrices.

III. A NEW APPROACH

The proposed GEMM-based MCMK methods avoid input replication by computing convolutions through matrix multiplication and combining shifted intermediate results.

  • Motivation: The proposed algorithms eliminate input data replication, addressing im2col's memory expansion while potentially improving data locality.For a k × k kernel, im2col can make the input-patch matrix k2 larger than the original input.
  • 1 × 1 convolution: For k = 1, MCMK convolution is equivalent to multiplying an M × C kernel matrix by a C × [H × W] input matrix.The resulting [M] × [H × W] matrix represents an output with H × W spatial dimensions and M channels.
  • Kernel decomposition: For k > 1, the method expresses convolution as k2 separate 1 × 1 convolutions whose intermediate results are shifted and summed.Offset intermediate values that fall outside the final output boundaries are discarded.
  • kn2row: kn2row uses one GEMM to produce a [k2 × M] × [H × W] matrix, then applies a shift-add pass to obtain the [M] × [H × W] output.The kernels are reordered so channel data is contiguous, and the k2 M-sized submatrices are summed with appropriate offsets.
  • kn2col: kn2col swaps kernel and input layouts, multiplying an [H × W] × [C] input matrix by a [C] × [k2 × M] kernel matrix.This produces an [H × W] × [k2 × M] matrix before the corresponding combination step.

IV. EXPERIMENTS AND RESULTS

The study evaluates proposed GEMM-based MCMK implementations across desktop and embedded processors, CNN operations, and direct-convolution baselines. The GEMM-based methods are often much faster than direct methods and can outperform Intel MKL-DNN.

  • Platforms: The evaluation uses an embedded ARM Cortex-A57 and a desktop Intel Core i5-4570, each with four cores and SIMD support.The ARM processor has a 128-bit SIMD unit, while the Intel processor has a 256-bit SIMD unit.
  • Workloads: The implementations cover MCMK operations from AlexNet, VGG-16, and GoogLeNet, with direct convolution included for performance context.Several direct-convolution variants were also tested, including versions associated with Caffe and Intel Xeon Phi optimization guidance.
  • Baselines: The fastest direct method on average was the reference method that sums single-channel convolutions.This comparison provides a direct-convolution baseline alongside the proposed GEMM-based methods.
  • Baselines: The benchmarks include Intel MKL-DNN, whose convolution backend uses highly optimized SIMD code generated for AVX2 and AVX-512 processors.MKL-DNN serves as a comparison with an optimized production convolution implementation.
  • Results: The GEMM-based methods were often much faster than direct methods and often outperformed code generated by Intel's MKL-DNN.The result is reported across the evaluated MCMK operations and processors.

A. Performance Trends

Performance varies substantially with convolutional-layer depth and implementation strategy. The results therefore support selecting different convolution methods for different network contexts rather than relying on one universally best method.

  • Layer characteristics: As layer depth increases, input-channel counts rise while individual feature-map sizes decrease.The trend is observed across the graphs in Figures 5 and 6.
  • Data layout: Row-based input layout improves spatial locality because consecutive patch elements are consecutive in memory.The results suggest im2col is a poor CPU choice, although it may perform well on GPUs.
  • Layer dependence: Benchmark performance varies substantially with convolutional-layer depth, with methods favoring different early or late layers.This variability occurs across the evaluated implementation strategies.
  • Architecture-specific trends: Direct convolution is strong for VGG-16's first layer but is quickly outpaced by GEMM-based methods in deeper layers.For AlexNet, the GEMM-based methods are reported as always faster.
  • Strategy selection: No GEMM-based method performs universally well across all contexts, so peak performance may require a mixture of implementation strategies.The best method depends on the network layer and workload context.

V. RELATED WORK

Prior work commonly implements multi-channel, multi-kernel convolution with im2col and GEMM, while alternatives reduce input replication or create column-matrix tiles lazily. These approaches trade memory use, locality, flexibility, and performance across implementations.

  • Im2col-based methods: Im2col extends Toeplitz-matrix convolution and remains widely used in frameworks including Caffe, Theano, and Torch.It converts convolution into GEMM after replicating image pixels across matrix columns.
  • Im2col-based methods: Batching input images can improve throughput by matching input-matrix sizes to the GEMM library’s optimal sizes.
  • Replication-free methods: Directly coded MCMK loop nests eliminate im2col replication and support larger batch sizes under local-memory constraints.A naive loop nest performed poorly, but a program generator and autotuner achieved satisfactory performance.
  • Tiled methods: Lazy im2col creates column-matrix sub-tiles in on-chip memory and achieves speedups of around 0% to 30% over Caffe’s standard im2col.The sub-matrix tiles are matched to the underlying GEMM implementation’s tile sizes.

VI. CONCLUSION

MCMK convolution is a dominant DNN cost, and im2col’s input expansion creates memory and locality problems. The proposed GEMM-based kn2row approach improves locality, but the evaluated methods remain strongly context-dependent, motivating a selection cost model.

  • Motivation: MCMK convolution is the most computationally expensive DNN operation and requires careful tuning for caches, on-chip memories, registers, and parallelism.Performance characteristics differ across processors and accelerators, requiring retuning for each target.
  • Limitations of im2col: Im2col expands the input quadratically in the convolution radix k, creating memory pressure for embedded systems and reducing locality through redundant data movement.
  • Proposed approach: The kn2row approach makes one GEMM call and post-processes its output to accumulate partial results into a single matrix.The paper states that this approach drastically increases data locality compared with im2col.
  • Conclusion: The strong context dependence of evaluated methods motivates a cost model to guide MCMK implementation selection.Methods can perform very well in some contexts and very poorly in others.
Loading 1704.04428v2…