Skip to content

Latest commit

 

History

History
225 lines (172 loc) · 6.28 KB

dwconv.md

File metadata and controls

225 lines (172 loc) · 6.28 KB

Depthwise convolution microkernels

This document describes how depthwise convolution (DWCONV) microkernels work.

All depthwise convolution microkernels live in src/*-dwconv, e.g. src/f32-dwconv.

The simplest microkernel to look at is probably f32-dwconv-up2x3-scalar.c.

Key parameters:

  • channel tile, how many channels the microkernel can process in each iteration
  • kernel tile, how many weights (kernel elements, each element is # channels values) the microkernel reads in each iteration. This can be greater than the actual number of kernel elements.

High level description

Each call to the DWCONV microkernel will produce 1 row of output.

For each element of this row of output, DWCONV will produce channel_tile number of outputs in the main loop, with a separate loop to handle remainders (remainder loop).

In each iteration of the main loop, the microkernel will read channel_tile biases, channel_tile * kernel_tile inputs, channel_tile * kernel_tile weights, and, optionally, channel_tile of per-channel scales, perform the convolution, then write channel_tile outputs.

In the remainder loop, the microkernel will read remainder_channels biases, remainder_channels * kernel_tile inputs, remainder_channels * kernel_tile weights, perform the convolution, and write remainder_channels outputs.

Microkernel arguments

void xnn_f32_dwconv_ukernel_up2x3__scalar(
    size_t channels,
    size_t output_width,
    const float** input,
    const float* weights,
    float* output,
    size_t input_stride,
    size_t output_increment,
    size_t input_offset,
    const float* zero,
    const struct xnn_f32_default_params params[restrict XNN_MIN_ELEMENTS(1)])
  • channels, number of output channels to compute
  • output_width, number of produced pixels
  • input, pointer to input indirection buffer
  • weights, pointer to weights
  • output, pointer to output
  • input_stride, number of bytes to add to the indirection buffer to advance to the input pointers corresponding to the next output element
  • output_increment, number of bytes to get to the next output element
  • input_offset, offset to add to pointers from indirection buffer, unless these pointers match the zero pointer
  • zero, pointer to zero buffer
  • params, min/max values for clamping the output

Packing

Based on the high level description of the microkernel, we will have to pack the weights such that we have:

  • channel_tile biases
  • channel_tile * kernel_tile weights

Repeated round_up(channels, channel_tile) times.

Indirection buffer

The indirection buffer is packed such that the channel_tile * kernel_tile pointers to input required for computing a single output is adjacent to each other. A simple way to pack it will then be:

input  kernel  output

ABC    ab      WX
DEF    cd      YZ
GHI

uncompressed indirection buffer for first row of output
ABDEBCEF

This requires kernel_tile * output_width pointers.

We can compress this if we pack the input pointers column first:

column first uncompressed:
ADBEBECF

Notice that BE is repeated. So we can elide it, provided that we tell the microkernel how much to skip over to get to the input pointers for the next output element (it is not just kernel_tile), that's what input_stride is for.

column first compressed:
ADBECF

The weights similarly have to be packed column first.

Compressed indirection buffer

One drawback of the indirection buffer is that its size is proportional to output size, which can be very big.

input  kernel

ABC    ab
DEF    cd
GHI
JKL
MNO
PQR
STU
VWX

indirection buffers:
ADBECF
DGEHFI
GJHKIL
JMKNLO
MPNQOR
PSQTRU
SVTWUX

Notice how along each column of the indirection buffer, each element is a constant offset, + 3, away. This allows us to compress along the Y dimension. We only need to have 1 row of indirection buffer, and specify a constant offset for each input as y index * 3.

indirection buffer (1 row):
ABCDEF

constant offset: 3 (added to each input)

row 0: ADBECF + 0 * 3 = ADBECF
row 1: ADBECF + 1 * 3 = DGEHFI
row 2: ADBECF + 2 * 3 = GJHKIL
row 3: ADBECF + 3 * 3 = JMKNLO
row 4: ADBECF + 4 * 3 = MPNQOR
row 5: ADBECF + 5 * 3 = PSQTRU
row 6: ADBECF + 6 * 3 = SVTWUX

This constant offset is calculate in the compute function (in operator-run.c) based on output_y, and passed as input_offset.

Note that left and right padding does not affect this: if we are reading from padding, the input pointer in the indirection buffer is set to the zero buffer, and in the microkernels, we check if the input pointer is the zero buffer before we add the input offset.

Top and bottom padding

The above compression scheme is incomplete as it does not handle top and bottom padding.

input  kernel

000
ABC    ab
DEF    cd
GHI
000

(uncompressed) indirection buffers:
0A0B0C
ADBECF
DGEHFI
G0H0I0

The above compression scheme will result in inputs like so:

row 0: 0A0B0C + 0 * 3 = 0A0B0C
row 1: 0A0B0C + 1 * 3 = 0D0E0F (wrong, due to zero buffer)

Due to the padding and zero buffer, the constant offset calculation does not work. So, we separate out the top section of the indirection buffer to account for top padding (and by the same logic, the bottom padding).

The compressed indirection buffer thus has 3 sections: top, middle (compressed), and bottom. The top and bottom account for top and bottom padding respectively and are not compressed, so there is a row of indirection buffers for each row of output in these sections. The compressed section is always 1 row.

input  kernel

000
ABC    ab
DEF    cd
GHI
000

compressed indirection buffers:
0A0B0C (top)
ADBECF (middle) (1 less row than uncompressed)
G0H0I0 (compressed)

In the compute function, we will then need to consider which row of output we are computing, as that will determine the row of indirection buffer to read, and also the input offset to use. With the above example:

output_y section row in indirection buffer input offset
0 top 0 0
1 mid 1 0
2 mid 1 3
3 bot 0 0