c#对嵌套循环函数执行线程处理，每次执行两个独立的作业

Question

我正在努力在不改变算法的情况下提高程序的速度。

目前我使用DFT的这种实现：

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;
    }

它相当慢，但有一个地方我可以看到可以改进。功能的内部部分是两个独立的任务。实数和虚数相加可以分别进行，但应始终连接以计算结果。

有什么想法吗？我尝试了一些我在网上看到的实现，但它们都崩溃了，我几乎没有线程经验。

Answer 1

当您有一个可以并行化的CPU绑定算法时，您可以使用Parallel类轻松地将单线程实现转换为多线程。

在你的例子中，你有两个嵌套的循环，但外循环的迭代次数远大于你可以执行的CPU核心的数量，所以只需要并行化外循环就可以让所有核心旋转：

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;
}

我已经获取了您的代码，并将外层for循环替换为Parallel.For。在我有八个超线程核心的计算机上，我的执行速度提高了七倍。

另一种提高执行速度的方法是在CPU上使用SIMD指令集。System.Numerics.Vectors库与Yeppp！库允许您从托管代码中调用SIMD指令，但使用这些指令来实现算法需要您做一些工作。

Answer 2

您应该为内部For创建一个新的Task，每个任务都将结果保存在线程安全字典（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));
                });
            }
        }