Вычислительная математика Учебно-практическая задача Пути достижения параллелизма Моделирование и анализ параллельных вычислений Каскадная схема суммирования

Процессы и ресурсы Учебно-практическая задача

Учебно-практическая задача: Решение дифференциальных уравнений в частных производных

Коллективные операции обмена информацией

Для завершения круга вопросов, связанных с параллельной реализацией метода сеток на системах с распределенной памятью, осталось рассмотреть способы вычисления общей для всех процессоров погрешности вычислений. Возможный очевидный подход состоит в передаче всех локальных оценок погрешности, полученный на отдельных полосах сетки, на один какой-либо процессор, вычисления на нем максимального значения и рассылки полученного значения всем процессорам системы. Однако такая схема является крайне неэффективной – количество необходимых операций передачи данных определяется числом процессоров и выполнение этих операций может происходить только в последовательном режиме. Между тем, как показывает анализ требуемых коммуникационных действий, выполнение операций сборки и рассылки данных может быть реализовано с использованием рассмотренной в п. 4.1 пособия каскадной схемы обработки данных. На самом деле, получение максимального значения локальных погрешностей, вычисленных на каждом процессоре, может быть обеспечено, например, путем предварительного нахождения максимальных значений для отдельных пар процессоров (данные вычисления могут выполняться параллельно), затем может быть снова осуществлен попарный поиск максимума среди полученных результатов и т.д. Всего, как полагается по каскадной схеме, необходимо выполнить log2NP параллельных итераций для получения конечного значения (NP – количество процессоров). Разложить в ряд Фурье функцию периода , заданную на интервале формулой: 

Учитывая большую эффективность каскадной схемы для выполнения коллективных операций передачи данных, большинство базовых библиотек параллельных программ содержит процедуры для поддержки подобных действий. Так, в стандарте MPI [21] предусмотрены операции:

С учетом перечисленных процедур общая схема вычислений на каждом процессоре может быть представлена в следующем виде:

 // 
Алгоритм 6.8 – уточненный вариант

// схема Гаусса-Зейделя, ленточное разделение данных // действия, выполняемые на каждом процессоре do { // обмен граничных строк полос с соседями Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc); Sendrecv(u[1][*],N+2,PrevProc,u[M+1][*],N+2,NextProc); //<обработка полосы с оценкой погрешности dm> //вычисление общей погрешности вычислений dmax Reduce(dm,dmax,MAX,0); Broadcast(dmax,0); } while ( dmax > eps ); // eps - точность решения

(в приведенном алгоритме переменная dm представляет локальную погрешность вычислений на отдельном процессоре, параметр MAX задает операцию поиска максимального значения для операции сборки). Следует отметить, что в составе MPI имеется процедура Allreduce, которая совмещает действия редукции и рассылки данных. Результаты экспериментов для данного варианта параллельных вычислений для метода Гаусса-Зейделя приведены в табл. 6.4.

Другой способ измерения производительности заключается в определении числа вещественных операций, выполняемых компьютером в единицу времени. Единицей измерения является Flops (Floating point operations per second) - число операций с плавающей точкой, производимых компьютером за одну секунду. Такой способ является более приемлемым для пользователя, поскольку последний знает вычислительную сложность своей программы и, пользуясь этой характеристикой, может получить нижнюю оценку времени ее выполнения.

Информатика, черчение, математика