Обмен данными, параллельные программы

Имеются две основные модели параллельного выполнения программы на многопроцессорных компьютерах — модель передачи сообщений и модель общей памяти. В первой параллельная программа представляет собой систему процессов, взаимодействующих посредством передачи сообщений, что может быть использовано на любых многопроцессорных конфигурациях. Во второй параллельная программа представляет собой систему нитей (threads), взаимодействующих посредством общих переменных и примитивов синхронизации. Нить — легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память. Эта модель может использоваться только на многопроцессорных системах с общей памятью или с DSM (Distributed Shared Memory — распределенная общая память).

В качестве модели программирования можно выбрать одну из этих моделей, например Фортран+MPI, Си+Pthreads, Occam, однако такая низкоуровневая модель непривычна и неудобна, заставляя иметь дело с параллельными процессами и низкоуровневыми примитивами передачи сообщений или синхронизации. И, главное, программист должен распределять вычисления (а в модели передачи сообщений еще и данные) между процессами. Поэтому вполне естественно, что прикладной программист хотел бы иметь дело с высокоуровневой моделью программирования, которая позволяла бы описывать алгоритм в терминах массива целиком (как это делается на последовательных компьютерах), а не манипулировать локальными частями массива, размер которых зависит от числа используемых процессоров.

Примером такой высокоуровневой модели является модель последовательного программирования. Мечта всех прикладных программистов — получить инструмент, автоматически преобразующий его последовательную программу в параллельную. К сожалению, для систем с распределенной памятью такое автоматическое распараллеливание обеспечить не удается.

Во-первых, поскольку взаимодействие процессоров через коммуникационную систему требует значительного времени (время самого простого взаимодействия велико по сравнению со временем выполнения одной машинной команды), то вычислительная работа должна распределяться между процессорами крупными порциями. Совсем другая ситуация была на векторных машинах и на многопроцессорных системах с общей памятью, где для автоматического распараллеливания программ на языке Фортран достаточно было проанализировать только самые внутренние циклы программы на предмет возможности параллельного выполнения (замены на векторные операции). В случае мультипроцессоров приходилось уже анализировать объемлющие циклы для нахождения более крупных порций работы, распределяемых между процессорами. Такое укрупнение требует анализа крупных фрагментов программы, обычно включающих в себя вызовы различных процедур, что, в свою очередь, требует сложного межпроцедурного анализа. Поскольку в реальных программах могут использоваться конструкции, статический анализ которых принципиально невозможен (например, косвенная индексация элементов массивов), то с увеличением порций распределяемой работы увеличивается вероятность того, что распараллеливатель откажется обрабатывать конструкции, которые на самом деле допускают параллельное выполнение.

Ещё посмотрите лекцию "16. Проблема острых кишечных инфекций" по этой теме.

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

В третьих, распределение вычислений и данных должно быть произведено согласованно. Несогласованность приведет, вероятнее всего, к тому, что параллельная программа будет выполняться гораздо медленнее последовательной. Если на системе с общей памятью распараллелить один цикл, занимающий 90% времени решения задачи, то можно рассчитывать на почти десятикратное ускорение программы, даже если оставшиеся 10% будут выполняться последовательно. На системе с распределенной памятью распараллеливание этого цикла без учета последовательной части может вызвать не ускорение, а замедление программы, поскольку для выполнения последовательной части потребуется интенсивный обмен данными между процессорами. Согласованное распределение вычислений и данных требует тщательного анализа всей программы, и любая неточность может привести к катастрофическому замедлению.

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

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