Когда требуется распараллеливание вычислений

В классическом курсе программирования, который обычно читается, начиная с первого курса, студентам, как правило, не рассказывают о параллельном программировании. Хотя бы потому, что эта тема появляется в программах старших курсов и подается уже как что-то грандиозное. На самом деле, о распараллеливании вычислений смело можно говорить и с первокурсниками. И не только говорить, но и показывать реальные примеры, опираясь на минимальный объем знаний у начинающих. Об этом мы и поговорим в этой публикации. Этот материал вполне сойдет за учебный и может быть использован преподавателями программирования и студентами младших курсов.

Для начала немного ликбеза. Применение параллельных вычислений обосновано, если требуется выполнить большое число рутинных повторяющихся вычислений, когда время, требуемое на них можно считать критично важным. В синтетических студенческих учебных задачах такая проблема обычно не должна появляться. Хотя, на стадии изучения программирования многие студенты делают ошибки при проектировании логики и как результат получают избыточные вычисления. Но, это особый случай и мы его оставим в покое. На младших курсах обычно в задачах еще не используются численные методы и необходимость достижения точности в вычислениях. Но и в довольно простых задачах может появиться потребность параллельных вычислений. Приведем тут некоторые примеры. Для реализации примеров параллельных вычислений будет использована библиотека OpenMP и публикация в "Блоге программиста" об использовании параллельных циклов в OpenMP, а также фрагменты кода с этого сайта.

Типично, даже организация циклов (а это чаще всего и изучают первокурсники) может привести к тому, что вычисления становятся слишком долгими. Например, такие проблемы могут возникнуть с вложенными циклами. При работе с матрицами (вспомним математику и решение систем уравнений) уже приходится создавать вложенные циклы. А если система с большим числом уравнений? Тоже вычисление определителя большого может потребовать заметное время. Или еще задача: поиск ранга большой матрицы. Ну и или разреженные матрицы больших размеров. Новички часто, чтобы не мучиться с логикой, делают вложения циклов глубже двух - три, четыре вложенных цикла да еще и с кучей условных операторов внутри. Именно на таких примерах и стоит показать студентам азы распараллеливания с помощью параллельных циклов в OpenMP. Для понимания требуется минимальный уровень и знание языка С++ на начальном уровне.

В примере, приведенном ниже показано сравнение времени, потраченного на вычисление суммы элементов массива целых рандомных чисел в диапазоне от 1 до 9. Для сравнения приведены две функции, вычисляющие сумму: без распараллеливания и с распараллеливанием. Вычисляется также время, потраченное на вычисления, выполняемые первой и второй функциями. Даже для такого предельно тривиального случая уже удается поймать разницу. Чем сложнее будет цикл, тем больше будет разница. Смотрите пример кода ниже.

#include <iostream> // C++ [GCC 9.2.0] 
#include <omp.h>
// сумма без распараллеливания
int summa(int *a, const int n) {
 int summa = 0;
 {
 for (int i = 0; i < n; ++i)
 summa += a[i];
 }
 return summa;
}

// сумма с распараллеливанием
int sum_arr(int *a, const int n) {
 int sum = 0;
#pragma omp parallel shared(a) reduction (+: sum) num_threads(2)
 {
# pragma omp for
 for (int i = 0; i < n; ++i)
 sum += a[i];
 }
 return sum;
}

int main() {

int a[10000000];
int i;
 
srand(time(0)); // инициализация генерации случайных чисел
//генерируем целый случайный массив 
for (i = 0; i < 10000000; i++)
 a[i] = 1 + rand() % 9;
//измеряем время вычисления без распараллеливания
clock_t start, end;
 start = clock();
std::cout << summa(a,10000000) << std::endl; 
end = clock();
printf("Без распараллеливания за %.4f секунд\n", ((double) end - start) / 
((double) CLOCKS_PER_SEC));

start = clock();
std::cout << sum_arr(a,10000000) << std::endl;
end = clock();
printf("С распараллеливанием за %.4f секунд\n", ((double) end - start) / 
((double) CLOCKS_PER_SEC));

return 0;
}

Студентам же можно предложить написать свой пример двух циклов для решения какой-то задачи с большим числом итераций и показать эффективность применения параллельных вычислений. И когда на старшем курсе студенты будут изучать курс "Параллельное программирование", то у них уже будет осознанное представление о нем и его возможностях.