Алгоритм суммирования для параллельной программы

Question

Я пытаюсь написать параллельный алгоритм в три раза быстрее, чем последовательный алгоритм, который делает практически то же самое. См. Пастебин.

http://pastebin.com/3DDyxfPP

Pasted:

Привет всем. Я выполняю задание для класса и делаю большую часть его, однако у меня возникают некоторые проблемы с математикой. Я пытаюсь вычислить выражение:

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

i идет от 1 до 10 миллионов. быстрый последовательный алгоритм Дано:

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».

, например: «Не используйте функцию POW на каждой итерации для параллельного кода, потому что он не будет бить время» Math.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); 
     } 
    } 
} 

Моя проблема заключается в том, что моя последовательная программа работает быстрее, чем параллельная. Проблема с алгоритмом, который я использую.

Может ли кто-нибудь помочь?

Answer 1

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

On Intel Core i7, это дает ускорение около 3x для вашего размера проблемы.

Обязательные напоминания:

• Не используйте DateTime.Now для измерения коротких интервалов времени. Вместо этого используйте класс Stopwatch.
• Не выполняйте измерения времени поперечной резьбы. Подождите, пока ваши рабочие потоки будут завершены из основного потока, и оттуда выберете окончательное чтение.