Optimizing DSP code for ARM in Signal Processing - Time & Space Complexity

Time Complexity: Optimizing DSP code for ARM

O(n * m)

Understanding Time Complexity

When optimizing DSP code for ARM processors, it is important to understand how the time to run the code changes as the input size grows.

We want to know which parts of the code take the most time as data size increases.

Scenario Under Consideration

Analyze the time complexity of the following DSP code snippet optimized for ARM.

// Simple FIR filter implementation
for (int i = 0; i < input_length - filter_length + 1; i++) {
    int32_t acc = 0;
    for (int j = 0; j < filter_length; j++) {
        acc += input[i + j] * filter[j];
    }
    output[i] = acc;
}
    

This code applies a FIR filter by sliding over the input signal and computing weighted sums.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops performing multiply-accumulate operations.
• How many times: Outer loop runs once per output sample (input_length - filter_length + 1 times), inner loop runs filter_length times per outer loop.

How Execution Grows With Input

As input size grows, the total operations grow by the product of input length and filter length.

Input Size (n)	Approx. Operations
10	~(10 - filter_length + 1) x filter_length
100	~(100 - filter_length + 1) x filter_length
1000	~(1000 - filter_length + 1) x filter_length

Pattern observation: Operations increase linearly with input size and filter length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the input size times the filter size.

Common Mistake

[X] Wrong: "The time depends only on the input size, so doubling input doubles time regardless of filter size."

[OK] Correct: The filter length also affects time because each output sample requires processing all filter coefficients.

Interview Connect

Understanding how nested loops affect time helps you explain performance in signal processing tasks clearly and confidently.

Self-Check

"What if we used a fast convolution algorithm like FFT-based convolution? How would the time complexity change?"

Practice

1. What is the main benefit of optimizing DSP code specifically for ARM processors?

easy

A. Enhanced web page loading speed

B. Faster and more efficient signal processing

C. Improved database queries

D. Better graphics rendering

Solution

1. Step 1: Understand DSP code purpose

   DSP code processes signals like audio or sensor data.

2. Step 2: Identify ARM optimization goal

   Optimizing for ARM makes this processing faster and uses less power.

3. Final Answer:

   Faster and more efficient signal processing -> Option B

4. Quick Check:

   ARM optimization = faster DSP [OK]

Hint: ARM optimization speeds up signal processing tasks [OK]

Common Mistakes:

• Confusing DSP with graphics or web tasks
• Thinking ARM optimization improves unrelated software
• Assuming optimization only affects power, not speed

2. Which of the following is a correct way to use ARM's SIMD instructions in DSP code?

easy

A. Using CMSIS-DSP library functions that leverage SIMD

B. Writing code only in Python without ARM-specific calls

C. Using standard C loops without any ARM intrinsics

D. Compiling code without any optimization flags

Solution

1. Step 1: Identify SIMD usage

   SIMD instructions process multiple data points at once for speed.

2. Step 2: Recognize CMSIS-DSP role

   CMSIS-DSP library provides ARM-optimized functions using SIMD.

3. Final Answer:

   Using CMSIS-DSP library functions that leverage SIMD -> Option A

4. Quick Check:

   SIMD use = CMSIS-DSP functions [OK]

Hint: Use CMSIS-DSP for ARM SIMD acceleration [OK]

Common Mistakes:

• Ignoring ARM-specific libraries
• Assuming Python alone uses ARM SIMD
• Not enabling compiler optimizations

3. Consider this ARM DSP C code snippet using loop unrolling:

for (int i = 0; i < 8; i += 2) {
  output[i] = input[i] * 2;
  output[i+1] = input[i+1] * 2;
}

What will be the value of output[3] if input = [1, 2, 3, 4, 5, 6, 7, 8]?

medium

A. 6

B. 4

C. 3

D. 8

Solution

1. Step 1: Understand loop unrolling effect

   The loop processes two elements per iteration, multiplying each by 2.

2. Step 2: Calculate output[3]

   input[3] = 4, so output[3] = 4 * 2 = 8.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   input[3]*2 = 8 [OK]

Hint: Multiply input[3] by 2 directly [OK]

Common Mistakes:

• Confusing index 3 with 2 or 4
• Forgetting loop unrolling doubles processing
• Assuming output equals input without change

4. This ARM DSP code snippet aims to use fixed-point math but has an error:

int16_t fixed_mul(int16_t a, int16_t b) {
  return (a * b) >> 15;
}

What is the main problem here?

medium

A. The multiplication may overflow before shifting

B. The shift operator should be << instead of >>

C. int16_t cannot hold the result of multiplication

D. The function should return int32_t instead

Solution

1. Step 1: Analyze multiplication of int16_t

   Multiplying two int16_t values can exceed 16 bits, causing overflow.

2. Step 2: Understand shift after multiplication

   Shifting right after overflow does not fix incorrect intermediate result.

3. Final Answer:

   The multiplication may overflow before shifting -> Option A

4. Quick Check:

   int16_t * int16_t can overflow [OK]

Hint: Use wider type for multiplication before shifting [OK]

Common Mistakes:

• Thinking shift direction is wrong
• Ignoring overflow risk in multiplication
• Assuming return type fixes overflow

5. You want to optimize a DSP filter on ARM Cortex-M using fixed-point math and SIMD. Which combination of techniques is best to improve speed and reduce power?

hard

A. Use floating-point math with standard loops and no SIMD

B. Write code in Python and rely on ARM compiler optimizations

C. Use CMSIS-DSP SIMD functions with loop unrolling and 16-bit fixed-point math

D. Use 32-bit fixed-point math without SIMD or loop unrolling

Solution

1. Step 1: Identify ARM DSP optimization techniques

   CMSIS-DSP provides SIMD functions optimized for ARM Cortex-M.

2. Step 2: Combine loop unrolling and fixed-point math

   Loop unrolling reduces loop overhead; 16-bit fixed-point math is faster and uses less power than floating-point.

3. Final Answer:

   Use CMSIS-DSP SIMD functions with loop unrolling and 16-bit fixed-point math -> Option C

4. Quick Check:

   Best speed and power = SIMD + loop unroll + fixed-point [OK]

Hint: Combine SIMD, loop unrolling, and fixed-point math [OK]

Common Mistakes:

• Choosing floating-point which is slower on Cortex-M
• Ignoring SIMD benefits
• Relying on Python for ARM DSP code