Последовательная и параллельная модели программирования
Модель программирования - это совокупность приемов программирования, отвечающих архитектуре абстрактного компьютера, предназначенного для выполнения определенного класса алгоритмов.
Модель программирования основана на определенном представлении о логической организации компьютера, его архитектуре.
Существуют различные архитектуры, и одной из схем их классификации является таксономия Флинна, основанная на описании работы компьютера с потоками команд и данных (рис. 1.1 - 1.5).
(рис 1.1) Параметры классификации Флинна
(рис 1.2 ) Архитектура SISD (Single Instruction Stream - Single Data Stream) - один поток команд и один поток данных 
(рис 1.3 ) Архитектура SIMD (Single Instruction Stream - Multiple Data Stream) - один поток команд и несколько потоков данных 
(рис 1.4 ) Архитектура MISD (Multiple Instruction Stream - Single Data Stream) - несколько потоков команд и один поток данных 
(рис 1.5 ) Архитектура MIMD (Multiple Instruction Stream - Multiple Data Stream) - несколько потоков команд и несколько потоков данных Взаимодействие данных и команд может быть представлено информационным графом. Информационный граф описывает последовательность выполнения операций и взаимную зависимость между различными макрооперациями или блоками операций.
Узлами информационного графа являются макрооперации, а однонаправленными дугами - каналы обмена данными (рис. 1.6).
(рис 1.6) Информационный граф программыКаждый узел можно охарактеризовать парой $$(n, s)$$, где $$n$$ - имя узла, $$s$$ - его размер. Размер узла определяется количеством элементарных операций, входящих в его состав.
Дуга характеризуется парой $$(v, d)$$, где $$v$$ - пересылаемые данные, а $$d$$ - время, затрачиваемое на ее пересылку.
Информационный граф содержит линейные участки, а также многосвязные фрагменты (циклы). Предельные случаи информационного графа,
топологически эквивалентные линейной последовательности макроопераций и лесу линейных последовательностей (рис. 1.7), соответствуют чистым последовательной и параллельной моделям вычислений.
(рис 1.7) Предельные случай информационного графа программыДля последовательной модели программирования характерны следующие особенности:
относительно невысокая производительность;
применение стандартных языков программирования;
хорошая переносимость программ на уровне исходного кода.
Параллельная модель программирования характеризуется:
возможностью добиться более высокой производительности программ;
применением специальных приемов программирования;
применением специальных инструментов программирования;
более высокой трудоемкостью программирования;
проблемами с переносимостью программ.
При разработке параллельных приложений возникают и специфические для параллельной модели программирования проблемы:
управление работой множества процессов;
организация межпроцессных пересылок данных;
вероятность тупиковых ситуаций (взаимных блокировок). Блокировки возникают, если процесс или поток ожидает доступ к ресурсу, заблокированному другим процессом, блокируя, в свою очередь, доступ к ресурсу, требуемому для продолжения работы второго процесса или потока;
нелокальный и динамический характер ошибок. Процессы или потоки выполняются на разных процессорах или ядрах. Загрузка вычислительных узлов изменяется с течением времени, поэтому для обеспечения корректной работы параллельной программы может потребоваться явная синхронизация;
утрата детерминизма (предсказуемого поведения программы в процессе ее исполнения). Параллельная программа может давать разные результаты при повторных запусках даже без модификации кода и исходных данных.
Это является следствием "гонок за данными" - одновременного и асинхронного доступа разных процессов или потоков к общим переменным;
необходимость заботиться о масштабируемости программы (масштабируемость -это свойство вычислительной системы, компьютерной сети или процесса/процессов, которое заключается в сохранении способности эффективно работать при возрастании их сложности);
необходимость заботиться о сбалансированной загрузке вычислительных узлов.
Модели параллельного программирования
В рамках параллельной модели программирования существуют различные подходы, ориентированные на разные архитектуры высокопроизводительных вычислительных систем и различные инструментальные средства. Перечислим некоторые из них.
Модель передачи сообщений
Основные особенности данного подхода:
Программа порождает несколько задач.
Каждой задаче присваивается свой уникальный идентификатор.
Взаимодействие осуществляется посредством отправки и приема сообщений.
Новые задачи могут создаваться во время выполнения параллельной программы, несколько задач могут выполняться на одном процессоре.
Модель параллелизма данных
Основные особенности данного подхода:
Одна операция применяется к множеству элементов структуры данных. Программа содержит последовательность таких операций.
"Зернистость" вычислений мала.
Программист должен указать транслятору, как данные следует распределить между задачами.
Модель общей памяти
В модели общей (разделяемой) памяти задачи обращаются к общей памяти, имея общее адресное пространство и выполняя операции считывания/записи.
Управление доступом к памяти осуществляется с помощью разных механизмов, таких, например, как семафоры. В рамках этой модели не требуется описывать обмен данными между задачами в явном виде. Это упрощает программирование. Вместе с тем особое внимание приходится уделять соблюдению детерминизма, таким явлениям, как "гонки за данными" и т. д.
Законы Амдала
Законы Амдала составляют теоретическую основу оценок достижимой производительности параллельных программ. Они сформулированы для некоторой идеализированной модели параллельных вычислений,
в которой, например, не учитывается латентность (конечное время передачи данных) коммуникационной среды и т. д.
1-й закон
Производительность вычислительной системы, состоящей из связанных между собой устройств, определяется самым медленным компонентом.
2-й закон
Пусть время выполнения алгоритма на последовательной машине $$T_1$$, причем $$T_s$$ - время выполнения последовательной части алгоритма, а $$T_p$$ - параллельной.
Тогда при выполнении той же программы на идеальной параллельной машине, содержащей $$N$$ процессорных элементов коэффициент ускорения:
$$K=\frac{T_1}{T_2}=\frac{T_s+T_p}{T_s+\frac{T_p}{N}}=\frac{1}{S+\frac{P}{N}}$$
где $$S=\frac{T_s}{T_s+T_p}$$ и $$P=\frac{T_p}{T_s+T_p}$$
- относительные доли последовательной и параллельной частей $$(S + P = 1)$$. Графическое представление закона Амдала дано на рис. 1.8.
3-й закон
Пусть система состоит из $$N$$ простых одинаковых процессорных элементов, тогда при любом режиме работы $$K\le \frac{1}{P}$$
(рис 1.8) Зависимость ускорения от доли параллельного кода и числа процессоров в законе Амдала
Две парадигмы параллельного программирования
На рис. 1.9 представлен информационный граф, показывающий, что в общем случае в программе присутствуют как параллелизм данных, так и параллелизм задач.
(рис 1.9) Параллелизм задач и параллелизм данныхПараллелизм данных
Наличие нескольких стрелок, связывающих соседние вершины информационного графа, означает применение одной операции сразу к нескольким элементам данных (массиву).
Различные фрагменты такого массива могут обрабатываться на векторном процессоре или на разных процессорах параллельной вычислительной системы.
Векторизация или распараллеливание в рамках данного подхода выполняются во время трансляции. В этом случае при разработке параллельного приложения от программиста требуется:
задание опций векторной или параллельной оптимизации транслятору;
задание директив параллельной компиляции;
использование специализированных языков параллельных вычислений, библиотек подпрограмм, специально разработанных с учетом конкретной архитектуры компьютера и оптимизированных для этой архитектуры.
Основные особенности данного подхода перечислены ниже:
обработкой данных управляет одна программа;
пространство имен является глобальным;
параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.
При программировании на основе параллелизма данных часто используются специализированные языки или надстройки над языками - DVM Fortran, HPF (High Perfomance Fortran) и другие.
Реализация модели параллелизма данных требует поддержки параллелизма на уровне транслятора. Такую поддержку могут обеспечивать:
препроцессоры,использующие существующие последовательные трансляторы и специализированные библиотеки, с реализациями параллельных алгоритмических конструкций;
распараллеливающие трансляторы,которые выявляют параллелизм в исходном коде программы и выполняют его преобразование в параллельные конструкции.
Для того чтобы упростить преобразование, в исходный текст программы могут добавляться специальные директивы трансляции.
Параллелизм задач
Петли, образованные в информационном графе "толстыми стрелками", соответствуют параллелизму задач, идея которого основана на разбиении вычислительной задачи на несколько относительно самостоятельных подзадач.
Каждая подзадача выполняется на своем процессоре. Данный подход ориентирован на архитектуру MIMD.
В рамках подхода, основанного на параллелизме задач, для каждой подзадачи пишется своя собственная программа на обычном языке программирования, чаще всего это Fortran и С.
Подзадачи должны обмениваться результатами своей работы, получать исходные данные. Практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист может контролировать распределение данных между различными процессорами и различными подзадачами, а также обмен данными.
Проблемы, связанные с данным подходом:
повышенная трудоемкость разработки программы и ее отладки;
на программиста ложится вся ответственность за равномерную и сбалансированную загрузку процессоров параллельного компьютера;
программисту приходится минимизировать обмен данными между задачами, так как затраты времени на пересылку данных обычно относительно велики;
опасность возникновения тупиковых ситуаций, когда отправленное одной программой сообщение не приходит к месту назначения.
Привлекательные особенности:
большая гибкость и большая свобода, предоставляемая программисту в разработке программы, эффективно использующей ресурсы параллельного компьютера;
возможность достижения максимального быстродействия.
Основными инструментами программирования являются специализированные библиотеки ( MPI - Message Passing Interface, PVM - Parallel Virtual Machines ).
Разработка параллельного алгоритма
Выделяют следующие этапы разработки параллельного алгоритма
Декомпозиция.На этом этапе выполняются анализ задачи и оценка возможности распараллеливания. Задача и связанные с ней данные разделяются на более мелкие части - подзадачи и фрагменты структур данных.
Особенности архитектуры конкретной вычислительной системы на данном этапе могут не учитываться.
Проектирование коммуникаций (обменов данными) между задачами.Определяются коммуникации, необходимые для пересылки исходных данных, промежуточных результатов выполнения подзадач, а также коммуникации, необходимые для управления работой подзадач.
Выбираются методы коммуникации.
Укрупнение.Подзадачи объединяются в более крупные блоки, если это позволяет повысить эффективность алгоритма и снизить трудоемкость разработки.
Планирование вычислений.Распределение подзадач между процессорами. Основной критерий выбора способа размещения подзадач - эффективное использование процессоров с минимальными затратами времени на обмены данными.
Рассмотрим эти этапы подробнее.
Декомпозиция (сегментирование, расщепление)
Существуют разные методы декомпозиции. Рассмотрим основные подходы.
Декомпозиция по данным
Вначале сегментируются данные, затем алгоритм их обработки. Данные разбиваются на фрагменты приблизительно одинакового размера. С фрагментами данных связываются операции их обработки, из которых и формируются подзадачи. Затем определяются необходимые пересылки данных.
Пересечение частей, на которые разбивается задача, должно быть сведено к минимуму, что позволяет избежать дублирования вычислений. Схема разбиения в дальнейшем может уточняться. Если необходимо для уменьшения числа обменов, допускается увеличение степени перекрытия подзадач.
Сначала анализируются структуры данных наибольшего размера, либо те, обращение к которым происходит чаще всего. На разных стадиях расчета могут использоваться разные структуры данных, поэтому могут использоваться как статические, так и динамические схемы декомпозиции этих структур.
Рекурсивная дихотомия
Используется для разбиения области на подобласти, которым соответствует примерно одинаковая трудоемкость вычислений, а коммуникации сведены к минимуму. Область сначала разбивается на две части вдоль одного измерения.
Разбиение повторяется рекурсивно в каждой новой подобласти столько раз, сколько потребуется для получения необходимого числа подзадач.
Рекурсивная координатная дихотомия
Может применяться к нерегулярным сеткам. Деление выполняется на каждом шаге вдоль того измерения, по которому сетка имеет наибольшую протяженность.
Метод рекурсивной дихотомии графа
Используется для нерегулярных сеток. В нем с помощью информации о топологии решетки минимизируется количество ребер, пересекающих границы подобластей. Это позволяет снизить количество коммуникаций.
Функциональная декомпозиция
Вначале сегментируется вычислительный алгоритм, а затем уже под эту схему подгоняется схема декомпозиции данных. Метод функциональной декомпозиции может оказаться полезным в ситуации,
где нет структур данных, которые очевидно могли бы быть распараллелены. Эффективность декомпозиции обеспечивается выполнением следующих рекомендаций:
количество подзадач после декомпозиции должно примерно на порядок превосходить количество процессоров;
следует избегать лишних вычислений и пересылок данных;
подзадачи должны быть примерно одинакового размера;
в идеале сегментация должна быть такой, чтобы с увеличением объема задачи количество подзадач также возрастало (при сохранении постоянным размера одной подзадачи).
Размер подзадачи определяется зернистостью алгоритма. Мерой зернистости является количество операций в блоке. Выделяют три степени зернистости:
Мелкозернистый параллелизм - на уровне команд (менее 20 команд на блок, количество параллельно выполняемых подзадач - от единиц до нескольких тысяч, средний масштаб параллелизма около 5 команд на блок).
Среднеблочный параллелизм - на уровне процедур. Размер блока до 2000 команд. Выявление такого параллелизма сложнее реализовать, поскольку следует учитывать межпроцедурные зависимости.
Требования к коммуникациям меньше, чем в случае параллелизма на уровне команд.
Крупноблочный параллелизм - на уровне программ (задач). Соответствует выполнению независимых программ на параллельном компьютере. Крупноблочный параллелизм требует поддержки операционной системой.
Важнейшим условием декомпозиции является независимость подзадач. Существуют следующие виды независимости:
Независимость по данным - данные, обрабатываемые одной частью программы, не модифицируются другой ее частью.
Независимость по управлению - порядок выполнения частей программы может быть определен только во время выполнения программы (наличие зависимости по управлению предопределяет последовательность выполнения).
Независимость по ресурсам - обеспечивается достаточным количеством компьютерных ресурсов.
Независимость по выводу - возникает, если две подзадачи не производят запись в одну и ту же переменную, а независимость по вводу-выводу,
если операторы ввода/вывода двух или нескольких подзадач не обращаются к одному файлу (или переменной).
Полной независимости добиться обычно не удается.
Проектирование коммуникаций
Можно выделить следующие основные типы коммуникаций:
локальные - каждая подзадача связана с небольшим набором других подзадач;
глобальные - каждая подзадача связана с большим числом других подзадач;
структурированные - каждая подзадача и подзадачи, связанные с ней, образуют регулярную структуру (например, с топологией решетки);
неструктурированные - подзадачи связаны произвольным графом;
статические - схема коммуникаций не изменяется с течением времени;
динамические - схема коммуникаций изменяется в процессе выполнения программы;
синхронные - отправитель и получатель данных координируют обмен;
асинхронные - обмен данными не координируется.
Рекомендации по проектированию коммуникаций:
количество коммуникаций у подзадач должно быть примерно одинаковым, иначе приложение становится плохо масштабируемым;
там, где это возможно, следует использовать локальные коммуникации;
коммуникации должны быть, по возможности, параллельными.
Укрупнение
На этапе укрупнения (агломерации) учитывается архитектура вычислительной системы и задачи, полученные на первых двух этапах, объединяются для того, чтобы их число соответствовало числу процессоров.
При выполнении агломерации должны быть соблюдены следующие требования:
должны быть снижены накладные расходы на коммуникации;
если при укрупнении приходится дублировать вычисления или данные, это не должно приводить к потере производительности и масштабируемости программы;
результирующие задачи должны иметь примерно одинаковую трудоемкость;
должна быть сохранена масштабируемость;
должна быть сохранена возможность параллельного выполнения;
должна быть снижена стоимость трудоемкости разработки.
Планирование вычислений
На этапе планирования определяют, на каких процессорах будут выполняться подзадачи. Основной критерий эффективности здесь - минимизация времени выполнения программы.
Стратегия размещения задач на процессорах строится на основе компромисса между требованием максимальной независимости выполняющихся задач (минимизация коммуникаций) и глобальным учетом состояния вычислений.
Чаще всего применяются стратегии хозяин/работник, иерархические и децентрализованные стратегии.
Хозяин/работник (Master/slave)
Главная задача отвечает за размещение подчиненных задач (рис. 1.10). Подчиненная задача получает исходные данные для обработки от главной задачи и возвращает ей результат работы.
(рис 1.10) Простая схема хозяин/работникИерархическая схема хозяин/работник
Подчиненные задачи разделены на непересекающиеся подмножества и у каждого из этих подмножеств есть своя главная задача (рис. 1.11).
Главные задачи подмножеств управляются одной "самой главной" задачей.
(рис 1.11) Иерархическая схема хозяин/работникДецентрализованные схемы
В этом случае главная задача отсутствует. Задачи обмениваются данными друг с другом, придерживаясь определенной стратегии (рис. 1.12).
Это может быть случайный выбор объекта коммуникации или взаимодействие с небольшим числом ближайших соседей. В гибридной централизованно-распределенной схеме запрос посылается главной задаче,
а она передает его подчиненным задачам, используя метод кругового планирования.
Динамически сбалансированная загрузка может быть эффективно реализована, если учтены следующие соображения:
если каждый процессор выполняет одну подзадачу, длительность выполнения всей программы будет определяться самой "медленной" подзадачей,
поэтому оптимальная производительность достигается, если все подзадачи имеют одинаковый размер;
сбалансированность может быть обеспечена посредством загрузки каждого процессора несколькими задачами.
(рис 1.12) Децентрализованная схема
Многопоточные программы
Поток (нить) представляет собой последовательный поток управления (последовательность команд) в рамках одной программы.
При создании процесса порождается главный поток, выполняющий инициализацию процесса. Он же начинает выполнение команд. Поток и процесс соотносятся следующим образом:
процесс имеет главный поток, инициализирующий выполнение команд процесса;
любой поток может порождать в рамках одного процесса другие потоки;
каждый поток имеет собственный стек;
потоки, соответствующие одному процессу, имеют общие сегменты кода и данных.
При разработке многопоточных приложений возникают те же проблемы, что и при разработке параллельных. Это:
гонки за данными;
блокировки;
активные блокировки;
несбалансированность загрузки.
Гонки за данными
Гонки за данными являются следствием зависимостей, когда несколько потоков модифицируют содержимое одной и той же области памяти.
Наличие гонок за данными не всегда является очевидным. Они могут приводить к конфликтам двух типов:
конфликт "чтение-запись";
конфликт "запись-запись".
Имеются два способа борьбы с гонками за данными:
использование преимущественно локальных по отношению к потоку, а не разделяемых переменных;
управление доступом к разделяемым переменным с помощью различных средств синхронизации (они могут быть реализованы с помощью семафоров, событий, критических секций, взаимных блокировок - мьютексов).
Гонки за данными могут быть скрыты синтаксисом языка программирования. Некоторые примеры приведены в табл. 1.1
Примеры конструкций языка программирования, в которых могут возникать гонки за данными
| Поток 1
| Поток 2
| Причина возникновения гонок за данными
|
|---|
| $$X += 1$$ |
$$X += 2$$ |
Компилятор заменяет операцию += раздельными операциями чтения и записи $$X$$ |
| $$A[i] += 1$$ |
$$A[j] += 2$$ |
Возможно совпадение значений индексов $$i$$ и $$j$$ |
| $$*p += 1$$ |
$$*q += 2$$ |
Указатели $$p$$ и $$q$$ могут ссылаться на один адрес |
| $$Func(1)$$ |
$$Func(2)$$ |
Func может суммировать значение аргумента и значение внутренней разделяемой переменной |
| $$Add [abc], 1$$ |
$$add [abc], 2$$ |
На уровне команд модификация $$[ abc ]$$ заменяется
раздельными операциями чтения и записи |
Блокировки
Блокировка (тупик) возникает, если поток ожидает выполнение условия, которое не может быть выполнено.
Обычно возникновение тупиковой ситуации является следствием конкуренции потоков за ресурс, который удерживается одним из них. Условия возникновения тупика:
доступ к ресурсу эксклюзивен (возможен только одним потоком);
поток может удерживать ресурс, запрашивая другой;
ни один из конкурирующих потоков не может освободить запрашиваемый ресурс.
Активной блокировкой называют ситуацию, когда поток не производит вычислений, но и не блокируется. Потоки пытаются преодолеть помеху, создаваемую другим потоком.
Последовательная и параллельная модели программирования
Модель программирования - это совокупность приемов программирования, отвечающих архитектуре абстрактного компьютера, предназначенного для выполнения определенного класса алгоритмов.
Модель программирования основана на определенном представлении о логической организации компьютера, его архитектуре.
Существуют различные архитектуры, и одной из схем их классификации является таксономия Флинна, основанная на описании работы компьютера с потоками команд и данных (рис. 1.1 - 1.5).
(рис 1.1) Параметры классификации Флинна(рис 1.2 ) Архитектура SISD (Single Instruction Stream - Single Data Stream) - один поток команд и один поток данных (рис 1.3 ) Архитектура SIMD (Single Instruction Stream - Multiple Data Stream) - один поток команд и несколько потоков данных (рис 1.4 ) Архитектура MISD (Multiple Instruction Stream - Single Data Stream) - несколько потоков команд и один поток данных (рис 1.5 ) Архитектура MIMD (Multiple Instruction Stream - Multiple Data Stream) - несколько потоков команд и несколько потоков данных Взаимодействие данных и команд может быть представлено информационным графом. Информационный граф описывает последовательность выполнения операций и взаимную зависимость между различными макрооперациями или блоками операций.
Узлами информационного графа являются макрооперации, а однонаправленными дугами - каналы обмена данными (рис. 1.6).
(рис 1.6) Информационный граф программыКаждый узел можно охарактеризовать парой $$(n, s)$$, где $$n$$ - имя узла, $$s$$ - его размер. Размер узла определяется количеством элементарных операций, входящих в его состав.
Дуга характеризуется парой $$(v, d)$$, где $$v$$ - пересылаемые данные, а $$d$$ - время, затрачиваемое на ее пересылку.
Информационный граф содержит линейные участки, а также многосвязные фрагменты (циклы). Предельные случаи информационного графа,
топологически эквивалентные линейной последовательности макроопераций и лесу линейных последовательностей (рис. 1.7), соответствуют чистым последовательной и параллельной моделям вычислений.
(рис 1.7) Предельные случай информационного графа программыДля последовательной модели программирования характерны следующие особенности:
относительно невысокая производительность;
применение стандартных языков программирования;
хорошая переносимость программ на уровне исходного кода.
Параллельная модель программирования характеризуется:
возможностью добиться более высокой производительности программ;
применением специальных приемов программирования;
применением специальных инструментов программирования;
более высокой трудоемкостью программирования;
проблемами с переносимостью программ.
При разработке параллельных приложений возникают и специфические для параллельной модели программирования проблемы:
управление работой множества процессов;
организация межпроцессных пересылок данных;
вероятность тупиковых ситуаций (взаимных блокировок). Блокировки возникают, если процесс или поток ожидает доступ к ресурсу, заблокированному другим процессом, блокируя, в свою очередь, доступ к ресурсу, требуемому для продолжения работы второго процесса или потока;
нелокальный и динамический характер ошибок. Процессы или потоки выполняются на разных процессорах или ядрах. Загрузка вычислительных узлов изменяется с течением времени, поэтому для обеспечения корректной работы параллельной программы может потребоваться явная синхронизация;
утрата детерминизма (предсказуемого поведения программы в процессе ее исполнения). Параллельная программа может давать разные результаты при повторных запусках даже без модификации кода и исходных данных.
Это является следствием "гонок за данными" - одновременного и асинхронного доступа разных процессов или потоков к общим переменным;
необходимость заботиться о масштабируемости программы (масштабируемость -это свойство вычислительной системы, компьютерной сети или процесса/процессов, которое заключается в сохранении способности эффективно работать при возрастании их сложности);
необходимость заботиться о сбалансированной загрузке вычислительных узлов.
Модели параллельного программирования
В рамках параллельной модели программирования существуют различные подходы, ориентированные на разные архитектуры высокопроизводительных вычислительных систем и различные инструментальные средства. Перечислим некоторые из них.
Модель передачи сообщений
Основные особенности данного подхода:
Программа порождает несколько задач.
Каждой задаче присваивается свой уникальный идентификатор.
Взаимодействие осуществляется посредством отправки и приема сообщений.
Новые задачи могут создаваться во время выполнения параллельной программы, несколько задач могут выполняться на одном процессоре.
Модель параллелизма данных
Основные особенности данного подхода:
Одна операция применяется к множеству элементов структуры данных. Программа содержит последовательность таких операций.
"Зернистость" вычислений мала.
Программист должен указать транслятору, как данные следует распределить между задачами.
Модель общей памяти
В модели общей (разделяемой) памяти задачи обращаются к общей памяти, имея общее адресное пространство и выполняя операции считывания/записи.
Управление доступом к памяти осуществляется с помощью разных механизмов, таких, например, как семафоры. В рамках этой модели не требуется описывать обмен данными между задачами в явном виде. Это упрощает программирование. Вместе с тем особое внимание приходится уделять соблюдению детерминизма, таким явлениям, как "гонки за данными" и т. д.
Законы Амдала
Законы Амдала составляют теоретическую основу оценок достижимой производительности параллельных программ. Они сформулированы для некоторой идеализированной модели параллельных вычислений,
в которой, например, не учитывается латентность (конечное время передачи данных) коммуникационной среды и т. д.
1-й закон
Производительность вычислительной системы, состоящей из связанных между собой устройств, определяется самым медленным компонентом.
2-й закон
Пусть время выполнения алгоритма на последовательной машине $$T_1$$, причем $$T_s$$ - время выполнения последовательной части алгоритма, а $$T_p$$ - параллельной.
Тогда при выполнении той же программы на идеальной параллельной машине, содержащей $$N$$ процессорных элементов коэффициент ускорения:
$$K=\frac{T_1}{T_2}=\frac{T_s+T_p}{T_s+\frac{T_p}{N}}=\frac{1}{S+\frac{P}{N}}$$
где $$S=\frac{T_s}{T_s+T_p}$$ и $$P=\frac{T_p}{T_s+T_p}$$
- относительные доли последовательной и параллельной частей $$(S + P = 1)$$. Графическое представление закона Амдала дано на рис. 1.8.
3-й закон
Пусть система состоит из $$N$$ простых одинаковых процессорных элементов, тогда при любом режиме работы $$K\le \frac{1}{P}$$
(рис 1.8) Зависимость ускорения от доли параллельного кода и числа процессоров в законе Амдала
Две парадигмы параллельного программирования
На рис. 1.9 представлен информационный граф, показывающий, что в общем случае в программе присутствуют как параллелизм данных, так и параллелизм задач.
(рис 1.9) Параллелизм задач и параллелизм данныхПараллелизм данных
Наличие нескольких стрелок, связывающих соседние вершины информационного графа, означает применение одной операции сразу к нескольким элементам данных (массиву).
Различные фрагменты такого массива могут обрабатываться на векторном процессоре или на разных процессорах параллельной вычислительной системы.
Векторизация или распараллеливание в рамках данного подхода выполняются во время трансляции. В этом случае при разработке параллельного приложения от программиста требуется:
задание опций векторной или параллельной оптимизации транслятору;
задание директив параллельной компиляции;
использование специализированных языков параллельных вычислений, библиотек подпрограмм, специально разработанных с учетом конкретной архитектуры компьютера и оптимизированных для этой архитектуры.
Основные особенности данного подхода перечислены ниже:
обработкой данных управляет одна программа;
пространство имен является глобальным;
параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.
При программировании на основе параллелизма данных часто используются специализированные языки или надстройки над языками - DVM Fortran, HPF (High Perfomance Fortran) и другие.
Реализация модели параллелизма данных требует поддержки параллелизма на уровне транслятора. Такую поддержку могут обеспечивать:
препроцессоры,использующие существующие последовательные трансляторы и специализированные библиотеки, с реализациями параллельных алгоритмических конструкций;
распараллеливающие трансляторы,которые выявляют параллелизм в исходном коде программы и выполняют его преобразование в параллельные конструкции.
Для того чтобы упростить преобразование, в исходный текст программы могут добавляться специальные директивы трансляции.
Параллелизм задач
Петли, образованные в информационном графе "толстыми стрелками", соответствуют параллелизму задач, идея которого основана на разбиении вычислительной задачи на несколько относительно самостоятельных подзадач.
Каждая подзадача выполняется на своем процессоре. Данный подход ориентирован на архитектуру MIMD.
В рамках подхода, основанного на параллелизме задач, для каждой подзадачи пишется своя собственная программа на обычном языке программирования, чаще всего это Fortran и С.
Подзадачи должны обмениваться результатами своей работы, получать исходные данные. Практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист может контролировать распределение данных между различными процессорами и различными подзадачами, а также обмен данными.
Проблемы, связанные с данным подходом:
повышенная трудоемкость разработки программы и ее отладки;
на программиста ложится вся ответственность за равномерную и сбалансированную загрузку процессоров параллельного компьютера;
программисту приходится минимизировать обмен данными между задачами, так как затраты времени на пересылку данных обычно относительно велики;
опасность возникновения тупиковых ситуаций, когда отправленное одной программой сообщение не приходит к месту назначения.
Привлекательные особенности:
большая гибкость и большая свобода, предоставляемая программисту в разработке программы, эффективно использующей ресурсы параллельного компьютера;
возможность достижения максимального быстродействия.
Основными инструментами программирования являются специализированные библиотеки ( MPI - Message Passing Interface, PVM - Parallel Virtual Machines ).
Разработка параллельного алгоритма
Выделяют следующие этапы разработки параллельного алгоритма
Декомпозиция.На этом этапе выполняются анализ задачи и оценка возможности распараллеливания. Задача и связанные с ней данные разделяются на более мелкие части - подзадачи и фрагменты структур данных.
Особенности архитектуры конкретной вычислительной системы на данном этапе могут не учитываться.
Проектирование коммуникаций (обменов данными) между задачами.Определяются коммуникации, необходимые для пересылки исходных данных, промежуточных результатов выполнения подзадач, а также коммуникации, необходимые для управления работой подзадач.
Выбираются методы коммуникации.
Укрупнение.Подзадачи объединяются в более крупные блоки, если это позволяет повысить эффективность алгоритма и снизить трудоемкость разработки.
Планирование вычислений.Распределение подзадач между процессорами. Основной критерий выбора способа размещения подзадач - эффективное использование процессоров с минимальными затратами времени на обмены данными.
Рассмотрим эти этапы подробнее.
Декомпозиция (сегментирование, расщепление)
Существуют разные методы декомпозиции. Рассмотрим основные подходы.
Декомпозиция по данным
Вначале сегментируются данные, затем алгоритм их обработки. Данные разбиваются на фрагменты приблизительно одинакового размера. С фрагментами данных связываются операции их обработки, из которых и формируются подзадачи. Затем определяются необходимые пересылки данных.
Пересечение частей, на которые разбивается задача, должно быть сведено к минимуму, что позволяет избежать дублирования вычислений. Схема разбиения в дальнейшем может уточняться. Если необходимо для уменьшения числа обменов, допускается увеличение степени перекрытия подзадач.
Сначала анализируются структуры данных наибольшего размера, либо те, обращение к которым происходит чаще всего. На разных стадиях расчета могут использоваться разные структуры данных, поэтому могут использоваться как статические, так и динамические схемы декомпозиции этих структур.
Рекурсивная дихотомия
Используется для разбиения области на подобласти, которым соответствует примерно одинаковая трудоемкость вычислений, а коммуникации сведены к минимуму. Область сначала разбивается на две части вдоль одного измерения.
Разбиение повторяется рекурсивно в каждой новой подобласти столько раз, сколько потребуется для получения необходимого числа подзадач.
Рекурсивная координатная дихотомия
Может применяться к нерегулярным сеткам. Деление выполняется на каждом шаге вдоль того измерения, по которому сетка имеет наибольшую протяженность.
Метод рекурсивной дихотомии графа
Используется для нерегулярных сеток. В нем с помощью информации о топологии решетки минимизируется количество ребер, пересекающих границы подобластей. Это позволяет снизить количество коммуникаций.
Функциональная декомпозиция
Вначале сегментируется вычислительный алгоритм, а затем уже под эту схему подгоняется схема декомпозиции данных. Метод функциональной декомпозиции может оказаться полезным в ситуации,
где нет структур данных, которые очевидно могли бы быть распараллелены. Эффективность декомпозиции обеспечивается выполнением следующих рекомендаций:
количество подзадач после декомпозиции должно примерно на порядок превосходить количество процессоров;
следует избегать лишних вычислений и пересылок данных;
подзадачи должны быть примерно одинакового размера;
в идеале сегментация должна быть такой, чтобы с увеличением объема задачи количество подзадач также возрастало (при сохранении постоянным размера одной подзадачи).
Размер подзадачи определяется зернистостью алгоритма. Мерой зернистости является количество операций в блоке. Выделяют три степени зернистости:
Мелкозернистый параллелизм - на уровне команд (менее 20 команд на блок, количество параллельно выполняемых подзадач - от единиц до нескольких тысяч, средний масштаб параллелизма около 5 команд на блок).
Среднеблочный параллелизм - на уровне процедур. Размер блока до 2000 команд. Выявление такого параллелизма сложнее реализовать, поскольку следует учитывать межпроцедурные зависимости.
Требования к коммуникациям меньше, чем в случае параллелизма на уровне команд.
Крупноблочный параллелизм - на уровне программ (задач). Соответствует выполнению независимых программ на параллельном компьютере. Крупноблочный параллелизм требует поддержки операционной системой.
Важнейшим условием декомпозиции является независимость подзадач. Существуют следующие виды независимости:
Независимость по данным - данные, обрабатываемые одной частью программы, не модифицируются другой ее частью.
Независимость по управлению - порядок выполнения частей программы может быть определен только во время выполнения программы (наличие зависимости по управлению предопределяет последовательность выполнения).
Независимость по ресурсам - обеспечивается достаточным количеством компьютерных ресурсов.
Независимость по выводу - возникает, если две подзадачи не производят запись в одну и ту же переменную, а независимость по вводу-выводу,
если операторы ввода/вывода двух или нескольких подзадач не обращаются к одному файлу (или переменной).
Полной независимости добиться обычно не удается.
Проектирование коммуникаций
Можно выделить следующие основные типы коммуникаций:
локальные - каждая подзадача связана с небольшим набором других подзадач;
глобальные - каждая подзадача связана с большим числом других подзадач;
структурированные - каждая подзадача и подзадачи, связанные с ней, образуют регулярную структуру (например, с топологией решетки);
неструктурированные - подзадачи связаны произвольным графом;
статические - схема коммуникаций не изменяется с течением времени;
динамические - схема коммуникаций изменяется в процессе выполнения программы;
синхронные - отправитель и получатель данных координируют обмен;
асинхронные - обмен данными не координируется.
Рекомендации по проектированию коммуникаций:
количество коммуникаций у подзадач должно быть примерно одинаковым, иначе приложение становится плохо масштабируемым;
там, где это возможно, следует использовать локальные коммуникации;
коммуникации должны быть, по возможности, параллельными.
Укрупнение
На этапе укрупнения (агломерации) учитывается архитектура вычислительной системы и задачи, полученные на первых двух этапах, объединяются для того, чтобы их число соответствовало числу процессоров.
При выполнении агломерации должны быть соблюдены следующие требования:
должны быть снижены накладные расходы на коммуникации;
если при укрупнении приходится дублировать вычисления или данные, это не должно приводить к потере производительности и масштабируемости программы;
результирующие задачи должны иметь примерно одинаковую трудоемкость;
должна быть сохранена масштабируемость;
должна быть сохранена возможность параллельного выполнения;
должна быть снижена стоимость трудоемкости разработки.
Планирование вычислений
На этапе планирования определяют, на каких процессорах будут выполняться подзадачи. Основной критерий эффективности здесь - минимизация времени выполнения программы.
Стратегия размещения задач на процессорах строится на основе компромисса между требованием максимальной независимости выполняющихся задач (минимизация коммуникаций) и глобальным учетом состояния вычислений.
Чаще всего применяются стратегии хозяин/работник, иерархические и децентрализованные стратегии.
Хозяин/работник (Master/slave)
Главная задача отвечает за размещение подчиненных задач (рис. 1.10). Подчиненная задача получает исходные данные для обработки от главной задачи и возвращает ей результат работы.
(рис 1.10) Простая схема хозяин/работникИерархическая схема хозяин/работник
Подчиненные задачи разделены на непересекающиеся подмножества и у каждого из этих подмножеств есть своя главная задача (рис. 1.11).
Главные задачи подмножеств управляются одной "самой главной" задачей.
(рис 1.11) Иерархическая схема хозяин/работникДецентрализованные схемы
В этом случае главная задача отсутствует. Задачи обмениваются данными друг с другом, придерживаясь определенной стратегии (рис. 1.12).
Это может быть случайный выбор объекта коммуникации или взаимодействие с небольшим числом ближайших соседей. В гибридной централизованно-распределенной схеме запрос посылается главной задаче,
а она передает его подчиненным задачам, используя метод кругового планирования.
Динамически сбалансированная загрузка может быть эффективно реализована, если учтены следующие соображения:
если каждый процессор выполняет одну подзадачу, длительность выполнения всей программы будет определяться самой "медленной" подзадачей,
поэтому оптимальная производительность достигается, если все подзадачи имеют одинаковый размер;
сбалансированность может быть обеспечена посредством загрузки каждого процессора несколькими задачами.
(рис 1.12) Децентрализованная схема
Многопоточные программы
Поток (нить) представляет собой последовательный поток управления (последовательность команд) в рамках одной программы.
При создании процесса порождается главный поток, выполняющий инициализацию процесса. Он же начинает выполнение команд. Поток и процесс соотносятся следующим образом:
процесс имеет главный поток, инициализирующий выполнение команд процесса;
любой поток может порождать в рамках одного процесса другие потоки;
каждый поток имеет собственный стек;
потоки, соответствующие одному процессу, имеют общие сегменты кода и данных.
При разработке многопоточных приложений возникают те же проблемы, что и при разработке параллельных. Это:
гонки за данными;
блокировки;
активные блокировки;
несбалансированность загрузки.
Гонки за данными
Гонки за данными являются следствием зависимостей, когда несколько потоков модифицируют содержимое одной и той же области памяти.
Наличие гонок за данными не всегда является очевидным. Они могут приводить к конфликтам двух типов:
конфликт "чтение-запись";
конфликт "запись-запись".
Имеются два способа борьбы с гонками за данными:
использование преимущественно локальных по отношению к потоку, а не разделяемых переменных;
управление доступом к разделяемым переменным с помощью различных средств синхронизации (они могут быть реализованы с помощью семафоров, событий, критических секций, взаимных блокировок - мьютексов).
Гонки за данными могут быть скрыты синтаксисом языка программирования. Некоторые примеры приведены в табл. 1.1
Примеры конструкций языка программирования, в которых могут возникать гонки за данными
| Поток 1
| Поток 2
| Причина возникновения гонок за данными
|
|---|
| $$X += 1$$ |
$$X += 2$$ |
Компилятор заменяет операцию += раздельными операциями чтения и записи $$X$$ |
| $$A[i] += 1$$ |
$$A[j] += 2$$ |
Возможно совпадение значений индексов $$i$$ и $$j$$ |
| $$*p += 1$$ |
$$*q += 2$$ |
Указатели $$p$$ и $$q$$ могут ссылаться на один адрес |
| $$Func(1)$$ |
$$Func(2)$$ |
Func может суммировать значение аргумента и значение внутренней разделяемой переменной |
| $$Add [abc], 1$$ |
$$add [abc], 2$$ |
На уровне команд модификация $$[ abc ]$$ заменяется
раздельными операциями чтения и записи |
Блокировки
Блокировка (тупик) возникает, если поток ожидает выполнение условия, которое не может быть выполнено.
Обычно возникновение тупиковой ситуации является следствием конкуренции потоков за ресурс, который удерживается одним из них. Условия возникновения тупика:
доступ к ресурсу эксклюзивен (возможен только одним потоком);
поток может удерживать ресурс, запрашивая другой;
ни один из конкурирующих потоков не может освободить запрашиваемый ресурс.
Активной блокировкой называют ситуацию, когда поток не производит вычислений, но и не блокируется. Потоки пытаются преодолеть помеху, создаваемую другим потоком.
