[Bug] Padded, quantized convolution operators give incorrect results on edges

[guberti]

When the microTVM team was working on our submission for MLPerf Tiny, we noticed the kws model had slightly worse accuracy than expected (we classified 897/1000 samples correctly, while folks are expected to classify at least 900/1000 correctly).

The bug has been remarkably hard to track down. We have a bunch of end-to-end operator tests, and our results match exactly with those in other parts of TVM. I originally thought this was a padding issue, but that didn't pan out.

It turns out the issue is caused by a bugged optimization for re-quantization. This issue only occurs in quantization (which is why our tests didn't catch it - those don't include quantization steps), and only on the edges of padded tensors (which explains why it hurt accuracy slightly, but not a ton).

I've written up an explanation of the issue below.

cc @alanmacd @areusch @gromero @mehrdadh @mkatanbaf

[guberti]

The optimization explained

Consider a fused, quantized conv2d operator, like those in the MLPerf Tiny (or any quantized MobileNetV1 model). In addition to having a kernel and bias, our operator has an input zero point $I_{ZP}$ (an integer constant, usually -128), in addition to some other quantization-related parameters. We can write the fused operator as follows:

$$\begin{equation*} \textrm{requantize} \left( \textrm{conv2d} \left( \textrm{input} - I_{ZP}, \textrm{kernel} \right) + \textrm{bias} \right) \end{equation*}$$

Let's focus only on what happens before re-quantization. We need to subtract the input zero point $I_{ZP}$ from every data element before doing multiplication, which usually means just adding 128. However, this poses two problems.

1. This is really slow, because this subtraction happens for every element.
2. Each element in $\textrm{input}$ and $\textrm{kernel}$ is an int8 value ranging from -128 to 127, so adding the zero point to the input means it ranges from 0 to 255 instead. This means we need a uint8 x int8 multiplication, but a lot of platforms don't have those or don't have them as SIMD instructions.

Luckily, there's a "solution"! Suppose $I_{ZP} = -128$, though this approach works for any value. We notice that:

$$\begin{align*} & (\text{in}_0 + 128) \times \text{ker}_0 + (\text{in}_1 + 128) \times \text{ker}_1 + \cdots + (\text{in}_n + 128) \times \text{ker}_n \\\ = & \text{in}_0 \times \text{ker}_0 + \cdots + \text{in}_n\times \text{ker}_n + (\text{ker}_0 + \cdots + \text{ker}_n) \times 128 \end{align*}$$

Awesome! All we have to do is compute $(\text{ker}_0 + \cdots + \text{ker}_n) \times 128$ (which can be done at compile time, since the kernel is a constant). Then we can do just int8 x int8 multiplications, and then just add the constant value we computed to the bias!

Why this doesn't work

It seems like this is a free optimization that does not affect accuracy. However, consider what happens when we use this alongside padding.

If our kernel height and width are larger than 1x1, (e.g. 3x3 as is common), doing a convolution will give a slightly smaller output tensor than we started with. This is usually undesirable, so we add ("pad") rows and columns of zeros to the input tensor to make the output the same size as the input.

How does this padding actually done? TFLite Micro does it by dynamically setting the bounds for the reduce loops, but this is kinda slow. Alternatively, TVM does it by copying the input tensor to a new tensor with zeros for the extra rows and columns (this is probably faster).

The zero point (-128) should not be subtracted from the padded values (see the TensorFlow implementation above). However, if we use this algebraic simplification trick, that's exactly what happens. This ultimately means that our QNN convolution gives the wrong results whenever working on a padded edge row.

The solution

Luckily, the solution is super simple! Instead of padding the tensor with zeros, we just need to pad the tensor with the input zero point. In theory using Relax, this could be done by the layer before, as the previous layer's output zero point is the same as the current layer's input zero point.

[tmoreau89]

CC @ibsidorenko as an FYI

[masahi]

This is not a bug from QNN right? We already do pad by input zp https://github.com/apache/tvm/blob/main/src/relay/qnn/op/convolution.cc#L250

[guberti]

This is not a bug from QNN right? We already do pad by input zp https://github.com/apache/tvm/blob/main/src/relay/qnn/op/convolution.cc#L250

Unfortunately, it seems I may have spoken too soon 😅. I took a closer look, and @masahi is right. I got confused because microTVM does not pass a constant to pad, which I assumed meant the padded constant was zero (as zero is the default).

tvm/python/tvm/topi/arm_cpu/mprofile/dsp/conv2d.py

Lines 80 to 82 in 034dc67

	pad_before = [0, pad_top, pad_left, 0]
	pad_after = [0, pad_down, pad_right, 0]
	padded_data = pad(data, pad_before, pad_after, name="padded_data")

However, I didn't actually check the generated code to make sure what occurred. Looking more closely at the generated code shows that padding-like operations happen in two places. A padding-like operation does occur inside the generated conv2d function code:

  for (int32_t i1 = 0; i1 < 50; ++i1) {
    for (int32_t i2 = 0; i2 < 50; ++i2) {
      for (int32_t i3 = 0; i3 < 8; ++i3) {
        int32_t cse_var_1 = (((i1 * 400) + (i2 * 8)) + i3);
        ((int8_t*)padded_data)[cse_var_1] = ((int8_t*)p0)[cse_var_1];
      }
    }
  }

However, this does not do anything, and does not need to. Because of the QNN legalization steps, a function like this runs beforehand, and is what actually does the padding.

TVM_DLL int32_t tvmgen_default_fused_nn_pad_cast(void* args, int32_t* arg_type_ids, int32_t num_args, void* out_ret_value, int32_t* out_ret_tcode, void* resource_handle) {
  void* arg_p0 = (((TVMValue*)args)[0].v_handle);
  int32_t arg_p0_code = arg_type_ids[0];
  void* arg_T_cast = (((TVMValue*)args)[1].v_handle);
  int32_t arg_T_cast_code = arg_type_ids[1];
  void* p0 = (((DLTensor*)arg_p0)[0].data);
  void* arg_p0_shape = (((DLTensor*)arg_p0)[0].shape);
  void* arg_p0_strides = (((DLTensor*)arg_p0)[0].strides);
  int32_t dev_id = (((DLTensor*)arg_p0)[0].device.device_id);
  void* T_cast = (((DLTensor*)arg_T_cast)[0].data);
  void* arg_T_cast_shape = (((DLTensor*)arg_T_cast)[0].shape);
  void* arg_T_cast_strides = (((DLTensor*)arg_T_cast)[0].strides);
  if (!(arg_p0_strides == NULL)) {
  }
  if (!(arg_T_cast_strides == NULL)) {
  }
  for (int32_t ax0_ax1_fused_ax2_fused = 0; ax0_ax1_fused_ax2_fused < 9409; ++ax0_ax1_fused_ax2_fused) {
    for (int32_t ax3_inner = 0; ax3_inner < 3; ++ax3_inner) {
      int32_t cse_var_1 = (ax0_ax1_fused_ax2_fused % 97);
      ((int16_t*)T_cast)[((ax0_ax1_fused_ax2_fused * 3) + ax3_inner)] = ((int16_t)(((ax0_ax1_fused_ax2_fused < 9312) && (cse_var_1 < 96)) ? ((int8_t*)p0)[((((ax0_ax1_fused_ax2_fused / 97) * 288) + (cse_var_1 * 3)) + ax3_inner)] : (int8_t)-128));
    }
  }
  return 0;
}

At the end, you can see the -128 zero point, as should be the case.

There is still an accuracy issue with microTVM models, but my explanation for what's happening is wrong. I'm closing this issue, but will make a new one if/when I do track down the issue. Thanks to @masahi for making me check my work :).