Файл: 12. Параллельные методы решения дифференциальных уравнений в частных производных.pdf

поскольку связана с пересылкой между процессорами блоков данных большого объема. Возможный интересный способ улучшения ситуации состоит в организации
множественной волны вычислений, в соответствии с которой процессоры после отработки волны текущей итерации расчетов могут приступить к выполнению волны следующей итерации метода сеток. Так, например, процессор 0 (см. рис. 12.13), передав после обработки своего блока граничные данные и запустив, тем самым, вычисления на процессорах 1 и 4, оказывается готовым к исполнению следующей итерации метода Гаусса-Зейделя.
После обработки блоков первой (процессорах 1 и 4) и второй (процессор 0) волн, к вычислениям окажутся готовыми следующие группы процессоров (для первой волны - процессоры 2, 5 и 8, для второй волны - процессоры 1 и 4). Кроме того, процессор 0 опять окажется готовым к запуску очередной волны обработки данных. После выполнения

NB подобных шагов в обработке будет находиться одновременно
NB итераций и все процессоры окажутся задействованными. Подобная схема организации расчетов позволяет рассматривать имеющуюся процессорную решетку как
вычислительный конвейер поэтапного выполнения итераций метода сеток. Останов конвейера может осуществляться, как и ранее, по максимальной погрешности вычислений (проверку условия остановки следует начинать только при достижении полной загрузки конвейера после запуска NB итераций расчетов). Необходимо отметить также, что получаемое после выполнения условия остановки решение задачи Дирихле будет содержать значения узлов сетки от разных итераций метода и не будет, тем самым, совпадать с решением, получаемым при помощи исходного последовательного алгоритма.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 блоки со значениями предшествующей итерации
Нарастание волны блоки со значениями текущей итерации блоки, в которых могут быть пересчитаны значения
Пик волны
Затухание волны
0 1
2 3
4 5
6 7 8
9 10 11 12 13 14 15 0
1 2
3 4
5 6
7 8
9 10 11 12 13 14 15
Рис. 12.13.
Организация волны вычислений при блочной схеме разделения данных
12.3.6. Оценка трудоемкости операций передачи данных
Время выполнения коммуникационных операций значительно превышает длительность вычислительных команд. Оценка трудоемкости операций приема-передачи может быть осуществлена с использованием двух основных характеристик сети передачи:
латентности (latency), определяющей время подготовки данных к передаче по сети, и
пропускной способности сети (bandwidth), задающей объем передаваемых по сети за 1 сек. данных – более полное изложение вопроса содержится в разделе 3.
Пропускная способность наиболее распространенной на данный момент сети Fast Ethernet – 100
Mбит/с, для более современной сети Gigabit Ethernet – 1000 Мбит/с. В то же время, скорость передачи данных в системах с общей памятью обычно составляет сотни и тысячи миллионов байт в секунду. Тем самым, использование систем с распределенной памятью приводит к снижению скорости передачи данных не менее чем в 100 раз.
Еще хуже дело обстоит с латентностью. Для сети Fast Ethernet эта характеристика имеет значений порядка 150 мкс, для сети Gigabit Ethernet – около 100 мкс. Для современных компьютеров с тактовой частотой свыше 2 ГГц/с различие в производительности достигает не менее, чем 10000-100000 раз. При указанных характеристиках вычислительной системы для достижения 90% эффективности в рассматриваемом примере решения задачи Дирихле (т.е. чтобы в ходе расчетов обработка данных занимала не менее 90% времени от общей длительности вычислений и только 10% времени тратилось бы на операции передачи данных) размер блоков вычислительной сетки должен быть не менее N=7500 узлов по вертикали и горизонтали (объем вычислений в блоке составляет
5N
2
операций с плавающей запятой).
24

Как результат, можно заключить, что эффективность параллельных вычислений при использовании распределенной памяти определяется в основном интенсивностью и видом выполняемых коммуникационных операций при взаимодействии процессоров. Необходимый при этом анализ параллельных методов и программ может быть выполнен значительно быстрее за счет выделения типовых операций передачи данных – см. раздел 3. Так, например, в рассматриваемой учебной задаче решения задачи Дирихле практически все пересылки значений сводятся к стандартным коммуникационным действиям, имеющим адекватную поддержку в стандарте MPI (см. рис. 12.14):
- рассылка количества узлов сетки всем процессорам – типовая операция передачи данных от одного процессора всем процессорам сети (функция
MPI_Bcast);
- рассылка полос или блоков узлов сетки всем процессорам – типовая операция передачи разных данных от одного процессора всем процессорам сети (функция
MPI_Scatter);
- обмен граничных строк или столбцов сетки между соседними процессорами – типовая операция передачи данных между соседними процессорами сети (функция
MPI_Sendrecv);
0 1 2 процессоры
Рассылка количества узлов сетки
MPI_Bcast
Обеспечивающая процедура MPI
Операция приема- передачи
Рассылка полос или блоков узлов сетки
MPI_Scatter
Обмен границ соседних полос или блоков
MPI_Sendrecv
Сборка и рассылка погрешности вычислений
MPI_Allreduce
Сборка полос или блоков узлов сетки
MPI_Gather
Рис. 12.14.
Операции передачи данных при выполнении метода сеток в системе с распределенной памятью
- сборка и рассылка погрешности вычислений всем процессорам – типовая операция передачи данных от всех процессоров всем процессорам сети (функция
MPI_Allreduce);
- сборка на одном процессоре решения задачи (всех полос или блоков сетки) – типовая операция передачи данных от всех процессоров сети одному процессору (функция
MPI_Gather).
12.4. Краткий обзор раздела
В разделе рассматриваются параллельные методы для решения дифференциальных уравнений в частных производных. В качестве учебного примера используется проблема численного решения задачи
Дирихле для уравнения Пуассона. Наиболее распространенный подход численного решения
25

26
дифференциальных уравнений является метод конечных разностей. В разделе рассматриваются возможные способы организации параллельных вычислений для сеточных методов на многопроцессорных вычислительных системах с общей и распределенной памятью.
В подразделе 14.1 дается постановка задачи Дирихле для уравнения Пуассона, приводится описание метода конечных разностей и излагается алгоритм Гаусса-Зейделя для решения поставленной задачи.
В подразделе 14.2 при изложении вопросов организации параллельных вычислений для систем с общей памятью основное внимание уделяется технологиям OpenMP. Приводятся проблемы, возникающие при применении этой технологии, и даются пути решения данных проблем. Среди рассмотренных вопросов – синхронизация параллельных вычислений, способы выявления взаимоблокировок и исключение неоднозначности вычислений с использованием чередования обработки четных и нечетных строк и волновых схем расчетов. В завершении темы рассматривается схема динамической балансировки вычислительной нагрузки процессов при помощи организации очереди заданий.
В подразделе 14.3 обсуждаются вопросы организации параллельных вычислений для систем с распределенной памятью. Основное внимание уделяется проблемам разделения данных и организации обменов информацией между процессорами. Среди способов разделения области расчетов более подробно рассматривается ленточная схема, для блочного представления обрабатываемых данных дается только самая общая характеристика. Обсуждается возможность синхронного и асинхронного выполнения операций передачи данных. Для повышения эффективности параллельных вычислений описывается возможность организации множественной волновой схемы расчетов. В завершении приводятся оценки трудоемкости операций передачи данных.
12.5. Обзор литературы
Дополнительная информация по исследованию проблематики численного решения дифференциальных уравнений в частных производных и по методу конечных разностей может быть получена в Березин и Жидков (1966), Тихонов и Самарский (1977), полезная информация содержится также в Fox, et al. (1988).
Рассмотрение вопроса по организации памяти и использованию кэша приводится в Хамахер и
Вранешич (2003).
Информация по вопросам балансировки вычислительной нагрузки между процессорами может быть получена в Xu and Hwang (1998).
12.6. Контрольные вопросы
1. Как определяется задача Дирихле для уравнения Пуассона?
2. Как метод конечных разностей применяется для решения задачи Дирихле?
3. Какие способы определяют организацию параллельных вычислений для сеточных методов на многопроцессорных вычислительных системах с общей памятью?
4. В чем состоит проблема синхронизации параллельных вычислений?
5. Как характеризуется поведение параллельных участков программы, которое именуется состязанием потоков (
race condition)?
6. В чем состоит проблема взаимоблокировки?
7. Какой метод гарантирует однозначность результатов сеточных методов независимо от способа распараллеливания, но требует использования большого дополнительного объема памяти?
8. Как изменяется объем вычислений при применении методов волновой обработки данных?
9. Что такое фрагментирование (
chunking)?
10. Как повысить эффективность методов волновой обработки данных?
11. Как очередь заданий позволяет балансировать нагрузку процессорам?
12. Какие проблемы приходится решать при организации параллельных вычислений на системах с распределенной памятью?
13. Какие механизмы могут быть задействованы для передачи данных?
14. Каким образом организация множественной волны вычислений позволяет повысить эффективность волновых вычислений в системах с распределенной памятью?

27
12.7. Задачи и упражнения
1. Выполните реализацию первого и второго вариантов параллельного алгоритма Гаусса-Зейделя.
Сравните время выполнения разработанных программ.
2. Выполните реализации параллельного алгоритма на основе волновой схемы вычислений и параллельного алгоритма, в котором реализуется блочный подход к методу волновой обработки данных.
Сравните время выполнения разработанных программ.
3. Выполните реализацию очереди заданий параллельных вычислений для систем с общей памятью. При реализации необходимо обеспечить возможность обработки близких блоков на одних и тех же процессорах.
Литература
Березин И.С., Жидков И.П.
(1966). Методы вычислений.-М.:Наука
Гергель, В.П., Стронгин, Р.Г.
(2001). Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ (2 изд., 2003).
Корнеев В.В.
(2003) Параллельное программирование в MPI. Москва-Ижевск: Институт компьютерных исследований,2003
Немнюгин С., Стесик О.
(2002). Параллельное программирование для многопроцессорных вычислительных систем – СПб.: БХВ-Петербург.
Таненбаум Э.
(2002) . Архитектура компьютера. – СПб.: Питер.
Тихонов А.Н., Самарский А.А.
(1977). Уравнения математической физики. – М.: Наука.
Хамахер К., Вранешич З., Заки С.
(2003). Организация ЭВМ. –СПб:Питер.
Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., and Melon, R.
(2000). Parallel
Programming in OpenMP. Morgan Kaufmann Publishers.
Fox, G.C. et al.
(1988). Solving Problems on Concurrent Processors.- Prentice Hall, Englewood Cliffs, NJ.
Group, W., Lusk, E., Skjellum, A.
(1994). Using MPI. Portable Parallel Programming with the Message-
Passing Interface. –MIT Press.
Pfister, G. P.
(1995). In Search of Clusters. - Prentice Hall PTR, Upper Saddle River, NJ (2nd edn., 1998).
Roosta, S.H.
(2000). Parallel Processing and Parallel Algorithms: Theory and Computation. Springer-
Verlag,NY.
Tanenbaum, A.
(2001). Modern Operating System. 2nd edn. – Prentice Hall (русский перевод
Таненбаум Э. Современные операционные системы. – СПб.: Питер, 2002)
Xu, Z., Hwang, K.
(1998). Scalable Parallel Computing Technology, Architecture, Programming. –
Boston: McGraw-Hill.