Теория и практика параллельных вычислений
Моделирование параллельных программ
Рассмотренная схема проектирования и реализации параллельных вычислений дает способ понимания параллельных алгоритмов и программ. На стадии проектирования параллельный метод может быть представлен в виде графа "подзадачи – сообщения", который представляет собой не что иное, как укрупненное (агрегированное) представление графа информационных зависимостей (графа "операции – операнды" – см. лекцию 2). Аналогично на стадии выполнения для описания параллельной программы может быть использована модель в виде графа "процессы – каналы", в которой вместо подзадач используется понятие процессов, а информационные зависимости заменяются каналами передачи сообщений. Дополнительно на этой модели может быть показано распределение процессов по процессорам вычислительной системы, если количество подзадач превышает число процессоров – см. рис. 4.2.
Рис. 4.2. Модель параллельной программы в виде графа "процессы - каналы"
Использование двух моделей параллельных вычислений2) позволяет лучше разделить проблемы, которые проявляются при разработке параллельных методов. Первая модель – граф "подзадачи – сообщения" – позволяет сосредоточиться на вопросах выделения подзадач одинаковой вычислительной сложности, обеспечивая при этом низкий уровень информационной зависимости между подзадачами. Вторая модель – граф "процессы – каналы" – концентрирует внимание на вопросах распределения подзадач по процессорам, обеспечивая еще одну возможность снижения трудоемкости информационных взаимодействий между подзадачами за счет размещения на одних и тех же процессорах интенсивно взаимодействующих процессов. Кроме того, эта модель позволяет лучше анализировать эффективность разработанного параллельного метода и обеспечивает возможность более адекватного описания процесса выполнения параллельных вычислений.
Дадим дополнительные пояснения для используемых понятий в модели "процессы – каналы":
- под процессом будем понимать выполняемую на процессоре программу, которая использует для своей работы часть локальной памяти процессора и содержит ряд операций приема/передачи данных для организации информационного взаимодействия с другими выполняемыми процессами параллельной программы;
- канал передачи данных с логической точки зрения может рассматриваться как очередь сообщений, в которую один или несколько процессов могут отправлять пересылаемые данные и из которой процесс-адресат может извлекать сообщения, отправляемые другими процессами.
В общем случае, можно считать, что каналы возникают динамически в момент выполнения первой операции приема/передачи с каналом. По степени общности канал может соответствовать одной или нескольким командам приема данных процесса-получателя; аналогично, при передаче сообщений канал может использоваться одной или несколькими командами передачи данных одного или нескольких процессов. Для снижения сложности моделирования и анализа параллельных методов будем предполагать, что емкость каналов является неограниченной и, как результат, операции передачи данных выполняются практически без задержек простым копированием сообщений в канал. С другой стороны, операции приема сообщений могут приводить к задержкам (блокировкам), если запрашиваемые из канала данные еще не были отправлены процессами – источниками сообщений.
Следует отметить важное достоинство рассмотренной модели "процессы – каналы" – в ней проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ.
