Технологии распараллеливания

Автор: Лабусов А.Н.

Источник: http://www.spbcas.ru/cfd/techn/Parallel.htm#ch2

Один из архитекторов системы IBM/360 Амдаль (G.Amdahl) в 1967 году сформулировал закон в виде следующего постулата: «Производительность вычислительной системы определяется самым медленным ее компонентом». Если предположить, что p – относительное время, затрачиваемое последовательными командами в программе ( 1-p соответственно время исполнения параллельных инструкций), то максимальное теоретическое ускорение s за счет распараллеливания в системе из N процессоров может быть рассчитано по следующей формуле:
s=1/[(1-p)/N+p]

Используя закон Амдаля можно сделать верхнюю оценку ускорения: например, при доле последовательных операций в программе p=10% невозможно получить ускорение s выше 10, а при р=50% s < 2, причем получаемые предельные ускорения не зависят от числа процессоров N.

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

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

  • векторизация;
  • распараллеливание.

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

Векторизация

Данный метод распараллеливания применяется только на векторно-конвейерных машинах и имеет существенное ограничение – векторизации подлежат только циклы с заранее известным количеством итераций. Д. Кнутом (D.E.Knuth) было проанализировано большое количество программ на языке Fortran и было установлено, что в среднем циклы занимают менее 4% кода, но требуют на выполнение более 50% счетного времени. Таким образом кажущаяся ограниченность векторизации не является большим недостатком для алгоритмов, содержащих большое количество векторизуемых циклов. Мы не будем подробно освещать теорию векторизации (оптимизацию программного кода для эффективного использования векторного процессора). Перечислим лишь необходимые требования к циклам, подлежащим векторизации:

  • цикл должен быть самым внутренним;
  • не допустимы ветвления внутри тела цикла;
  • не допустимы вызовы внешних функций и процедур из тела цикла;
  • не должно быть рекурсии элементов векторов или массивов в теле цикла.

Распараллеливание

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

Методы распараллеливания можно условно разделить на следующие:

  1. директивами оптимизирующего компилятора;
  2. специальными директивами, расширяющими возможности языка к параллелизации;
  3. параллельные языки программирования;
  4. коммуникационные средства, или средства межпроцессорного интерфейса.

Разумеется, список возможных средств не исчерпывается перечисленными позициями, однако, по-видимому, вышеупомянутые методы имеют самое широкое распространение.

  1. Распараллеливание директивами компилятора является самым простым, «автоматическим» средством, которое может эффективно применяться для выборочного класса задач, однако обладает следующими недостатками:
    • непереносимость с одной системы на другую , или даже при смене компилятора с одного на другой;
    • поскольку вычислительная эффективность напрямую зависит от организации алгоритма (см. выше), то для хорошего результата все равно требуется «участие» программиста при написании параллельного кода;
    • достаточно узкий диапазон возможностей, предоставляемых компилятором для распараллеливания.
  2. Введение специальных директив, поддерживающих средства параллельной обработки, в стандартные языки программирования является перспективным направлением. Пример такого развития – HPF (High Performance Fortran) представляющий собой параллельное расширение Fortran'а с помощью оформленных с виде комментариев директив параллельной обработки. Можно отметить следующие преимущества такого подхода:
    • переносимость с одной системы на другую исходного кода, требуется лишь наличие HPF-компилятора;
    • совместимость с последовательной версией программы, поскольку директивы HPF, воспринимаются обычным Fortran-компилятором как комментарии, таким образом отладку последовательного можно проводить на машине без HPF-компилятора;
    • наглядность исходного текста программы, поскольку он не перегружен «избыточной» коммуникационной информацией, как например в MPI;
    • простота освоения пользователем, который должен только указать компилятору блоки для параллельного исполнения, а не конкретизировать какие данные и куда пересылать.