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

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

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

Волновые схемы параллельных вычислений

Рассмотрим теперь возможность построения параллельного алгоритма, который выполнял бы только те вычислительные действия, что и последовательный метод (может быть только в некотором ином порядке) и, как результат, обеспечивал бы получение точно таких же решений исходной вычислительной задачи. Как уже было отмечено выше, в последовательном алгоритме каждое очередное k-ое приближение значения  вычисляется по последнему k-ому приближению значений и и предпоследнему (k-1)-ому приближению значений и . Как результат, при требовании совпадения результатов вычислений последовательных и параллельных вычислительных схем в начале каждой итерации метода только одно значение  может быть пересчитано (возможности для распараллеливания нет). Но далее после пересчета  вычисления могут выполняться уже в двух узлах сетки  и  (в этих узлах выполняются условия последовательной схемы), затем после пересчета узлов  и  - в узлах ,  и  и т.д. Обобщая сказанное, можно увидеть, что выполнение итерации метода сеток можно разбить на последовательность шагов, на каждом из которых к вычислениям окажутся подготовленными узлы вспомогательной диагонали сетки с номером, определяемом номером этапа – см. рис. 6.8. Получаемая в результате вычислительная схема получила наименование волны или фронта вычислений, а алгоритмы, получаемые на ее основе, - методами волновой обработки данных (wavefront or hyperplane methods). Следует отметить, что в нашем случае размер волны (степень возможного параллелизма) динамически изменяется в ходе вычислений – волна нарастает до своего пика, а затем затухает при приближении к правому нижнему узлу сетки.

Таблица 6.3. Результаты экспериментов для параллельных вариантов алгоритма Гаусса-Зейделя с волновой схемой расчета (p=4)

(k – количество итераций, t – время в сек., S – ускорение)

Существуют два способа оценки пиковой производительности компьютера. Один из них опирается на число команд, выполняемых компьютером в единицу времени. Единицей измерения, как правило, является MIPS (Million Instructions Per Second). Производительность, выраженная в MIPS, говорит о скорости выполнения компьютером своих же инструкций. Но, во-первых, заранее не ясно, в какое количество инструкций отобразится конкретная программа, а, во-вторых, каждая программа обладает своей спецификой, и число команд от программы к программе может меняться очень сильно

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