C # Threading a nested loop function with two separate execution jobs

Question

I am trying to improve the speed of my program without changing the algorithm.

I am currently using this DFT implementation:

public double[] dft(double[] data) {
        int n = data.Length;
        int m = n;// I use m = n / 2d;
        float[] real = new float[n];
        float[] imag = new float[n];
        double[] result = new double[m];
        float pi_div = (float)(2.0 * Math.PI / n);
        for (int w = 0; w < m; w++) {
            float a = w * pi_div;
            for (int t = 0; t < n; t++) {
                real[w] += (float)(data[t] * Math.Cos(a * t)); //thinking of threading this
                imag[w] += (float)(data[t] * Math.Sin(a * t)); //and this
            }
            result[w] = (float)(Math.Sqrt(real[w] * real[w] + imag[w] * imag[w]) / n);
        }
        return result;
    }

It's pretty slow, but there is one place in it where I see improvements. The internal parts of functions are two separate tasks. Real and imaginary amounts can be made separately, but must always be combined to calculate the result.

Any ideas? I tried several implementations that I saw on the Internet, but they all crashed and I have very few threads.

Answer 1

, , , Parallel .

, , , , , :

public double[] ParallelDft(double[] data) {
  int n = data.Length;
  int m = n;// I use m = n / 2d;
  float[] real = new float[n];
  float[] imag = new float[n];
  double[] result = new double[m];
  float pi_div = (float)(2.0 * Math.PI / n);
  Parallel.For(0, m,
    w => {
      float a = w * pi_div;
      for (int t = 0; t < n; t++) {
        real[w] += (float)(data[t] * Math.Cos(a * t)); //thinking of threading this
        imag[w] += (float)(data[t] * Math.Sin(a * t)); //and this
      }
      result[w] = (float)(Math.Sqrt(real[w] * real[w] + imag[w] * imag[w]) / n);
    }
  );
  return result;
}

Parallel.For. .

- SIMD CPU. System.Numerics.Vectors Yeppp! SIMD , .

Answer 2

Task For, , (ConcurrentDictionary).

, :

public ConcurrentDictionary<int, double> result = new ConcurrentDictionary<int, double>();
        public  void dft(double[] data)
        {
            int n = data.Length;
            int m = n;// I use m = n / 2d;
            float pi_div = (float)(2.0 * Math.PI / n);
            for (int w = 0; w < m; w++)
            {
                var w1 = w;
                Task.Factory.StartNew(() =>
                {
                    float a = w1*pi_div;
                    float real = 0;
                    float imag=0;
                    for (int t = 0; t < n; t++)
                    {
                        real += (float)(data[t] * Math.Cos(a * t));
                        imag += (float)(data[t] * Math.Sin(a * t)); 
                    }
                    result.TryAdd(w1, (float) (Math.Sqrt(real*real + imag*imag)/n));
                });
            }
        }