Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для вычисления

[jeckos]

Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для вычисления выражения a0-а1+a2-а3+a4-а5+...

 

[rrrFer]

Сначала пишешь последовательный код:

double s = 0;
for (int i = 0; i < n; ++i) {
  if (i%2)
    s += a[i];
  else
    s -= a[i];
}

Что происходит? - перебираются последовательно элементы массива. Если индекс элемента четный - он добавляется к сумме, иначе - вычитается.

Теперь распараллеливаешь - например с OpenMP:

double s = 0;
#pragma omp parallel for reduction(+:s)
for (int i = 0; i < n; ++i) {
  if (i%2)
    s += a[i];
  else
    s -= a[i];
}

В чем вообще суть решения?
Тебе надо вычислить сумму, и очевидно, переменная в которой она хранится должна быть обще для потоков. Мы объявляем переменную s вне параллельной секции, поэтому она по умолчанию является общей (shared).

Мы могли бы в каждом потоке просто прибавлять элемент к сумме (как в последовательном решении), но это не сработает, ведь нельзя одновременно изменять одну и туже область памяти (она является разделяемым ресурсом). Тогда мы могли бы подумать, что проблему можно решить критической секцией (поместить в #pragma omp critical изменения общей переменной). Это будет работать, но очень медленно, ведь в критической секции в один момент времени может находиться только один поток, поэтому программа фактически превратится в последовательную (в ней будет много потоков, но они будут только то и делать, что ждать друг друга).

В этой связи, правильное решение - создать в каждом потоке свою локальную переменную, накопить в ней часть результата, а затем сложить все локальные переменные в общую. Складывать локальные переменные можно уже в критической секции - это оптимально.

Но вот эту самую операцию и выполняет опция reduction. Мы указываем reduction(+:s) - в результате, в каждом потоке создается своя локальная переменная s, тип которой берется из одноименной общей переменной. В качестве начального значения локальной переменной автоматически присваивается ноль, т.к. reduction выполняет оператор +. При выходе из параллельной области над всеми локальными переменными выполняется соотствующая операция и результат помещается в общую переменную.

 

[vital]

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