-4

我正在尝试编写一个并行算法，使其比执行基本相同操作的顺序算法快三倍。请参阅粘贴箱。

http://pastebin.com/3DDyxfPP

粘贴：

大家好。我正在为课堂做作业，并且完成了大部分作业，但是我在数学上遇到了一些问题。我正在尝试计算表达式：

100000000
∑ (9999999/10000000)^i * i^2
i = 1

我从 1 到 1000 万。给出了一个快速的顺序算法：

  double sum = 0.0;
  double fact1 = 0.9999999;
  for (int i = 1; i <= 10000000; i++)
  {
     sum += (fact1 * i * i);
     fact1 *= 0.9999999;
  }

我们应该实现它并验证它是否工作，以及在发布模式下计时。我已经完成并正常工作。然后时间会显示在控制台上。

 DateTime t = DateTime.Now;
 long saveticks = t.Ticks;

 double sum = 0.0;
 double fact1 = 0.9999999;
 for (int i = 1; i <= 100000000; i++)
 {
    sum += (fact1 * i * i);
    fact1 *= 0.9999999;
 }

 t = DateTime.Now;

然后，我们必须编写一个计时并行算法，该算法将赶超时间，并且应该在示例并行程序之后对其进行建模。它必须至少比顺序算法快 3 倍。我们将为并行程序使用 4 个处理元件。

有一个提示，“在你弄清楚每个处理元素将完成的工作之后，你可能需要使用耗时的 Pow 函数启动处理元素”。

例如：Math.Pow(x,y)

“不要在并行代码的每次迭代中使用 pow 函数，因为它不会赶上时间。”

这是我的并行程序代码。这对顺序算法和并行算法都进行了处理，并对它们进行了计时。

 const int numPEs = 4;
 const int size = 100000000;
 static double pSum;
 static int numThreadsDone;
 static int nextid;
 static object locker1 = new object();
 static object locker2 = new object();
 static long psaveticks;
 static DateTime pt;

 static void Main(string[] args)
 {
     DateTime t = DateTime.Now;
     long saveticks = t.Ticks;

     double sum = 0.0;
     double fact1 = 0.9999999;
     for (int i = 1; i <= 100000000; i++)
     {
         sum += (fact1 * (i * i));
         fact1 *= 0.9999999;
     }

     t = DateTime.Now;
     Console.WriteLine("sequential: " + ((t.Ticks - saveticks) / 100000000.0) + " seconds");
     Console.WriteLine("sum is " + sum);

     // time it
     pt = DateTime.Now;
     psaveticks = pt.Ticks;
     for (int i = 0; i < numPEs; i++)
     new Thread(countThreads).Start();

     Console.ReadKey();
 }



 static void countThreads()
 {
     int id;
     double localcount = 0;
     lock (locker1)
     {
         id = nextid;
         nextid++;
     }
     // assumes array is evenly divisible by the number of threads
     int granularity = size / numPEs;
     int start = granularity * id;

     for (int i = start; i < start + granularity; i++)
         localcount += (Math.Pow(0.9999999, i) * (i * i));

     lock (locker2)
     {
         pSum += localcount;
         numThreadsDone++;
         if (numThreadsDone == numPEs)
         {
             pt = DateTime.Now;
             Console.WriteLine("parallel: " + ((pt.Ticks - psaveticks) / 10000000.0) + " seconds");
             Console.WriteLine("parallel count is " + pSum);
         }
     }
 }

我的问题是我的顺序程序比并行程序快得多。我使用的算法一定有问题。

任何人都可以帮忙吗？

4

1 回答 1

0 
Console.WriteLine("sequential: " + ((t.Ticks - saveticks) / 100000000.0) + " seconds");

一秒钟内有 10,000,000 个滴答声。在上面的行中，您除以一个额外的数量级，100,000,000，使您的顺序执行看起来比实际快 10 倍。为避免这些错误，请使用 .NET Framework 本身的相应字段；在这种情况下，TimeSpan.TicksPerSecond。

您变慢的主要原因是您的并行代码比顺序代码的计算要求高得多。

// Inner loop of sequential code:
sum += (fact1 * (i * i));
fact1 *= 0.9999999;

// Inner loop of parallel code:
localcount += (Math.Pow(0.9999999, i) * (i * i));

从数学的角度来看，您有理由假设幂等于重复乘法。但是，从计算的角度来看，该Math.Pow操作比简单的乘法要昂贵得多。

减轻这些昂贵Math.Pow调用的一种方法是在每个线程的开头只执行一次幂运算，然后恢复使用普通乘法（就像在您的顺序情况下一样）：

double fact1 = Math.Pow(0.9999999, start + 1);
for (int i = start + 1; i <= start + granularity; i++)
{
    localcount += (fact1 * (i * i));
    fact1 *= 0.9999999;
}

在 Intel Core i7 上，这为您的问题大小提供了大约 3 倍的加速。

强制性提醒：

  • 不要DateTime.Now用于测量短暂的时间间隔。改用Stopwatch类。
  • 不要进行跨线程时间测量。等待您的工作线程从您的主线程完成，然后从那里获取最终读数。
于 2013-10-03T19:55:28.637 回答