Немнюгин С.А. Средства программирования для многопроцессорных вычислительных систем
Подождите немного. Документ загружается.
11
•
предтрансляторы
,
которые
выполняют
предварительный
анализ
логической
структуры
программы
,
проверку
зависимостей
и
ограниченную
параллельную
оптимизацию
;
•
распараллеливающие
трансляторы
,
которые
выявляют
параллелизм
в
исходном
коде
программы
и
выполняют
его
преобразование
в
параллельные
конструкции
.
Для
того
чтобы
упростить
преобразование
,
в
исходный
текст
программы
могут
добавляться
специальные
директивы
трансляции
.
Параллелизм задач
Петли
,
образованные
в
информационном
графе
«
толстыми
стрелками
»,
соответствуют
параллелизму
задач
,
идея
которого
основана
на
разбиении
вычислительной
задачи
на
несколько
относительно
самостоятельных
подзадач
.
Каждая
подзадача
выполняется
на
своем
процессоре
.
Данный
подход
ориентирован
на
архитектуру
MIMD.
В
рамках
подхода
,
основанного
на
параллелизме
задач
,
для
каждой
подзадачи
пишется
своя
собственная
программа
на
обычном
языке
программирования
,
чаще
всего
это
Fortran
и
С
.
Подзадачи
должны
обмениваться
результатами
своей
работы
,
получать
исходные
данные
.
Практически
такой
обмен
осуществляется
вызовом
процедур
специализированной
библиотеки
.
Программист
может
контролировать
распределение
данных
между
различными
процессорами
и
различными
подзадачами
,
а
также
обмен
данными
.
Проблемы
,
связанные
с
данным
подходом
:
•
повышенная
трудоемкость
разработки
программы
и
ее
отладки
;
•
на
программиста
ложится
вся
ответственность
за
равномерную
и
сбалансированную
загрузку
процессоров
параллельного
компьютера
;
•
программисту
приходится
минимизировать
обмен
данными
между
задачами
,
так
как
затраты
времени
на
пересылку
данных
обычно
относительно
велики
;
•
опасность
возникновения
тупиковых
ситуаций
,
когда
отправленное
одной
программой
сообщение
не
приходит
к
месту
назначения
.
Привлекательные
особенности
:
•
большая
гибкость
и
большая
свобода
,
предоставляемая
программисту
в
разработке
программы
,
эффективно
использующей
ресурсы
параллельного
компьютера
;
•
возможность
достижения
максимального
быстродействия
.
Основными
инструментами
программирования
являются
специализированные
библиотеки
(MPI - Message Passing Interface, PVM - Parallel Virtual Machines).
Разработка параллельного алгоритма
Выделяют
следующие
этапы
разработки
параллельного
алгоритма
1.
Декомпозиция
.
На
этом
этапе
выполняются
анализ
задачи
и
оценка
возможности
распараллеливания
.
Задача
и
связанные
с
ней
данные
разделяются
на
более
мелкие
части
подзадачи
и
фрагменты
структур
данных
.
Особенности
архитектуры
конкретной
вычислительной
системы
на
данном
этапе
могут
не
учитываться
.
2.
Проектирование
коммуникаций
(
обменов
данными
)
между
задачами
.
Определяются
коммуникации
,
необходимые
для
пересылки
исходных
данных
,
промежуточных
результатов
выполнения
подзадач
,
а
также
коммуникации
,
необходимые
для
управления
работой
подзадач
.
Выбираются
методы
коммуникации
.
12
3.
Укрупнение
.
Подзадачи
объединяются
в
более
крупные
блоки
,
если
это
позволяет
повысить
эффективность
алгоритма
и
снизить
трудоемкость
разработки
.
4.
Планирование
вычислений
.
Распределение
подзадач
между
процессорами
.
Основной
критерий
выбора
способа
размещения
подзадач
эффективное
использование
процессоров
с
минимальными
затратами
времени
на
обмены
данными
.
Рассмотрим
эти
этапы
подробнее
.
Декомпозиция (сегментирование, расщепление)
Существуют
разные
методы
декомпозиции
.
Рассмотрим
основные
подходы
.
Декомпозиция по данным
Вначале
сегментируются
данные
,
затем
алгоритм
их
обработки
.
Данные
разбиваются
на
фрагменты
приблизительно
одинакового
размера
.
С
фрагментами
данных
связываются
операции
их
обработки
,
из
которых
и
формируются
подзадачи
.
Затем
определяются
необходимые
пересылки
данных
.
Пересечение
частей
,
на
которые
разбивается
задача
,
должно
быть
сведено
к
минимуму
,
что
позволяет
избежать
дублирования
вычислений
.
Схема
разбиения
в
дальнейшем
может
уточняться
.
Если
необходимо
для
уменьшения
числа
обменов
,
допускается
увеличение
степени
перекрытия
подзадач
.
Сначала
анализируются
структуры
данных
наибольшего
размера
,
либо
те
,
обращение
к
которым
происходит
чаще
всего
.
На
разных
стадиях
расчета
могут
использоваться
разные
структуры
данных
,
поэтому
могут
использоваться
как
статические
,
так
и
динамические
схемы
декомпозиции
этих
структур
.
Рекурсивная дихотомия
Используется
для
разбиения
области
на
подобласти
,
которым
соответствует
примерно
одинаковая
трудоемкость
вычислений
,
а
коммуникации
сведены
к
минимуму
.
Область
сначала
разбивается
на
две
части
вдоль
одного
измерения
.
Разбиение
повторяется
рекурсивно
в
каждой
новой
подобласти
столько
раз
,
сколько
потребуется
для
получения
необходимого
числа
подзадач
.
Рекурсивная координатная дихотомия
Может
применяться
к
нерегулярным
сеткам
.
Деление
выполняется
на
каждом
шаге
вдоль
того
измерения
,
по
которому
сетка
имеет
наибольшую
протяженность
.
Метод рекурсивной дихотомии графа
Используется
для
нерегулярных
сеток
.
В
нем
с
помощью
информации
о
топологии
решетки
минимизируется
количество
ребер
,
пересекающих
границы
подобластей
.
Это
позволяет
снизить
количество
коммуникаций
.
Функциональная декомпозиция
Вначале
сегментируется
вычислительный
алгоритм
,
а
затем
уже
под
эту
схему
подгоняется
схема
декомпозиции
данных
.
Метод
функциональной
декомпозиции
может
оказаться
полезным
в
ситуации
,
где
нет
структур
данных
,
которые
очевидно
могли
бы
быть
распараллелены
.
Эффективность
декомпозиции
обеспечивается
выполнением
следующих
рекомендаций
:
•
количество
подзадач
после
декомпозиции
должно
примерно
на
порядок
превосходить
количество
процессоров
;
•
следует
избегать
лишних
вычислений
и
пересылок
данных
;
13
•
подзадачи
должны
быть
примерно
одинакового
размера
;
•
в
идеале
сегментация
должна
быть
такой
,
чтобы
с
увеличением
объема
задачи
количество
подзадач
также
возрастало
(
при
сохранении
постоянным
размера
одной
подзадачи
).
Размер
подзадачи
определяется
зернистостью
алгоритма
.
Мерой
зернистости
является
количество
операций
в
блоке
.
Выделяют
три
степени
зернистости
:
1.
Мелкозернистый
параллелизм
на
уровне
команд
(
менее
20
команд
на
блок
,
количество
параллельно
выполняемых
подзадач
от
единиц
до
нескольких
тысяч
,
средний
масштаб
параллелизма
около
5
команд
на
блок
).
2.
Среднеблочный
параллелизм
на
уровне
процедур
.
Размер
блока
до
2000
команд
.
Выявление
такого
параллелизма
сложнее
реализовать
,
поскольку
следует
учитывать
межпроцедурные
зависимости
.
Требования
к
коммуникациям
меньше
,
чем
в
случае
параллелизма
на
уровне
команд
.
3.
Крупноблочный
параллелизм
на
уровне
программ
(
задач
).
Соответствует
выполнению
независимых
программ
на
параллельном
компьютере
.
Крупноблочный
параллелизм
требует
поддержки
операционной
системой
.
Важнейшим
условием
декомпозиции
является
независимость
подзадач
.
Существуют
следующие
виды
независимости
:
•
Независимость
по
данным
данные
,
обрабатываемые
одной
частью
программы
,
не
модифицируются
другой
ее
частью
.
•
Независимость
по
управлению
порядок
выполнения
частей
программы
может
быть
определен
только
во
время
выполнения
программы
(
наличие
зависимости
по
управлению
предопределяет
последовательность
выполнения
).
•
Независимость
по
ресурсам
обеспечивается
достаточным
количеством
компьютерных
ресурсов
.
•
Независимость
по
выводу
возникает
,
если
две
подзадачи
не
производят
запись
в
одну
и
ту
же
переменную
,
а
независимость
по
вводу
-
выводу
,
если
операторы
ввода
/
вывода
двух
или
нескольких
подзадач
не
обращаются
к
одному
файлу
(
или
переменной
).
Полной
независимости
добиться
обычно
не
удается
.
Проектирование коммуникаций
Можно
выделить
следующие
основные
типы
коммуникаций
:
•
локальные
каждая
подзадача
связана
с
небольшим
набором
других
подзадач
;
•
глобальные
каждая
подзадача
связана
с
большим
числом
других
подзадач
;
•
структурированные
каждая
подзадача
и
подзадачи
,
связанные
с
ней
,
образуют
регулярную
структуру
(
например
,
с
топологией
решетки
);
•
неструктурированные
подзадачи
связаны
произвольным
графом
;
•
статические
схема
коммуникаций
не
изменяется
с
течением
времени
;
•
динамические
схема
коммуникаций
изменяется
в
процессе
выполнения
программы
;
•
синхронные
отправитель
и
получатель
данных
координируют
обмен
;
•
асинхронные
обмен
данными
не
координируется
.
Рекомендации
по
проектированию
коммуникаций
:
14
•
количество
коммуникаций
у
подзадач
должно
быть
примерно
одинаковым
,
иначе
приложение
становится
плохо
масштабируемым
;
•
там
,
где
это
возможно
,
следует
использовать
локальные
коммуникации
;
•
коммуникации
должны
быть
,
по
возможности
,
параллельными
.
Укрупнение
На
этапе
укрупнения
(
агломерации
)
учитывается
архитектура
вычислительной
системы
и
задачи
,
полученные
на
первых
двух
этапах
,
объединяются
для
того
,
чтобы
их
число
соответствовало
числу
процессоров
.
При
выполнении
агломерации
должны
быть
соблюдены
следующие
требования
:
•
должны
быть
снижены
накладные
расходы
на
коммуникации
;
•
если
при
укрупнении
приходится
дублировать
вычисления
или
данные
,
это
не
должно
приводить
к
потере
производительности
и
масштабируемости
программы
;
•
результирующие
задачи
должны
иметь
примерно
одинаковую
трудоемкость
;
•
должна
быть
сохранена
масштабируемость
;
•
должна
быть
сохранена
возможность
параллельного
выполнения
;
•
должна
быть
снижена
стоимость
трудоемкости
разработки
.
Планирование вычислений
На
этапе
планирования
определяют
,
на
каких
процессорах
будут
выполняться
подзадачи
.
Основной
критерий
эффективности
здесь
минимизация
времени
выполнения
программы
.
Стратегия
размещения
задач
на
процессорах
строится
на
основе
компромисса
между
требованием
максимальной
независимости
выполняющихся
задач
(
минимизация
коммуникаций
)
и
глобальным
учетом
состояния
вычислений
.
Чаще
всего
применяются
стратегии
хозяин
/
работник
,
иерархические
и
децентрализованные
стратегии
.
Хозяин/работник (Master/slave)
Главная
задача
отвечает
за
размещение
подчиненных
задач
(
рис
. 10).
Подчиненная
задача
получает
исходные
данные
для
обработки
от
главной
задачи
и
возвращает
ей
результат
работы
.
Рис. 10.
Простая
схема
хозяин
/
работник
15
Иерархическая схема хозяин/работник
Подчиненные
задачи
разделены
на
непересекающиеся
подмножества
и
у
каждого
из
этих
подмножеств
есть
своя
главная
задача
(
рис
. 11).
Главные
задачи
подмножеств
управляются
одной
"
самой
главной
"
задачей
.
Рис. 11.
Иерархическая
схема
хозяин
/
работник
Децентрализованные схемы
В
этом
случае
главная
задача
отсутствует
.
Задачи
обмениваются
данными
друг
с
другом
,
придерживаясь
определенной
стратегии
(
рис
. 12).
Это
может
быть
случайный
выбор
объекта
коммуникации
или
взаимодействие
с
небольшим
числом
ближайших
соседей
.
В
гибридной
централизованно
-
распределенной
схеме
запрос
посылается
главной
задаче
,
а
она
передает
его
подчиненным
задачам
,
используя
метод
кругового
планирования
.
Динамически
сбалансированная
загрузка
может
быть
эффективно
реализована
,
если
учтены
следующие
соображения
:
•
если
каждый
процессор
выполняет
одну
подзадачу
,
длительность
выполнения
всей
программы
будет
определяться
самой
«
медленной
»
подзадачей
,
поэтому
оптимальная
производительность
достигается
,
если
все
подзадачи
имеют
одинаковый
размер
;
•
сбалансированность
может
быть
обеспечена
посредством
загрузки
каждого
процессора
несколькими
задачами
.
16
Рис. 12.
Децентрализованная
схема
Многопоточные программы
Поток
(
нить
)
представляет
собой
последовательный
поток
управления
(
последовательность
команд
)
в
рамках
одной
программы
.
При
создании
процесса
порождается
главный
поток
,
выполняющий
инициализацию
процесса
.
Он
же
начинает
выполнение
команд
.
Поток
и
процесс
соотносятся
следующим
образом
:
•
процесс
имеет
главный
поток
,
инициализирующий
выполнение
команд
процесса
;
•
любой
поток
может
порождать
в
рамках
одного
процесса
другие
потоки
;
•
каждый
поток
имеет
собственный
стек
;
•
потоки
,
соответствующие
одному
процессу
,
имеют
общие
сегменты
кода
и
данных
.
При
разработке
многопоточных
приложений
возникают
те
же
проблемы
,
что
и
при
разработке
параллельных
.
Это
:
•
гонки
за
данными
;
•
блокировки
;
•
активные
блокировки
;
•
несбалансированность
загрузки
.
Гонки за данными
Гонки
за
данными
являются
следствием
зависимостей
,
когда
несколько
потоков
модифицируют
содержимое
одной
и
той
же
области
памяти
.
Наличие
гонок
за
данными
не
всегда
является
очевидным
.
Они
могут
приводить
к
конфликтам
двух
типов
:
1.
конфликт
«
чтение
-
запись
»;
2.
конфликт
«
запись
-
запись
».
Имеются
два
способа
борьбы
с
гонками
за
данными
:
17
•
использование
преимущественно
локальных
по
отношению
к
потоку
,
а
не
разделяемых
переменных
;
•
управление
доступом
к
разделяемым
переменным
с
помощью
различных
средств
синхронизации
(
они
могут
быть
реализованы
с
помощью
семафоров
,
событий
,
критических
секций
,
взаимных
блокировок
-
мьютексов
).
Гонки
за
данными
могут
быть
скрыты
синтаксисом
языка
программирования
.
Некоторые
примеры
приведены
в
табл
. 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]
заменяется
раздельными
операциями
чтения
и
записи
Блокировки
Блокировка
(
тупик
)
возникает
,
если
поток
ожидает
выполнение
условия
,
которое
не
может
быть
выполнено
.
Обычно
возникновение
тупиковой
ситуации
является
следствием
конкуренции
потоков
за
ресурс
,
который
удерживается
одним
из
них
.
Условия
возникновения
тупика
:
•
доступ
к
ресурсу
эксклюзивен
(
возможен
только
одним
потоком
);
•
поток
может
удерживать
ресурс
,
запрашивая
другой
;
•
ни
один
из
конкурирующих
потоков
не
может
освободить
запрашиваемый
ресурс
.
Активной
блокировкой
называют
ситуацию
,
когда
поток
не
производит
вычислений
,
но
и
не
блокируется
.
Потоки
пытаются
преодолеть
помеху
,
создаваемую
другим
потоком
.
18
II. OpenMP
19
OpenMP
стандарт
программного
интерфейса
приложений
для
параллельных
систем
с
общей
памятью
.
Поддерживает
языки
C, C++,
Фортран
.
Модель программы в OpenMP
Рис. 12.
Модель
параллельной
программы
в
OpenMP
Модель
параллельной
программы
в
OpenMP
можно
сформулировать
следующим
образом
:
•
Программа
состоит
из
последовательных
и
параллельных
секций
(
рис
. 12).
•
В
начальный
момент
времени
создается
главная
нить
,
выполняющая
последовательные
секции
программы
.
•
При
входе
в
параллельную
секцию
выполняется
операция
fork,
порождающая
семейство
нитей
.
Каждая
нить
имеет
свой
уникальный
числовой
идентификатор
(
главной
нити
соответствует
0).
При
распараллеливании
циклов
все
параллельные
нити
исполняют
один
код
.
В
общем
случае
нити
могут
исполнять
различные
фрагменты
кода
.
•
При
выходе
из
параллельной
секции
выполняется
операция
join.
Завершается
выполнение
всех
нитей
,
кроме
главной
.
OpenMP
составляют
следующие
компоненты
:
•
Директивы
компилятора
-
используются
для
создания
потоков
,
распределения
работы
между
потоками
и
их
синхронизации
.
Директивы
включаются
в
исходный
текст
программы
.
•
Подпрограммы
библиотеки
времени
выполнения
-
используются
для
установки
и
определения
атрибутов
потоков
.
Вызовы
этих
подпрограмм
включаются
в
исходный
текст
программы
.
•
Переменные
окружения
-
используются
для
управления
поведением
параллельной
программы
.
Переменные
окружения
задаются
для
среды
выполнения
параллельной
программы
соответствующими
командами
(
например
,
командами
оболочки
в
операционных
системах
UNIX).
Использование
директив
компилятора
и
подпрограмм
библиотеки
времени
выполнения
подчиняется
правилам
,
которые
различаются
для
разных
языков
программирования
.
Совокупность
таких
правил
называется
привязкой
к
языку
.
20
Привязка к языку Fortran
В
программах
на
языке
Fortran
директивы
компилятора
,
имена
подпрограмм
и
переменных
окружения
начинаются
с
OMP
или
OMP_
.
Формат
директивы
компилятора
:
{!|C|*}$OMP директива [оператор_1[, оператор_2, …]]
Директива
начинается
в
первой
(
фиксированный
формат
записи
текста
языка
Fortran 77)
или
произвольной
(
свободный
формат
)
позиции
строки
.
Допускается
продолжение
директивы
в
следующей
строке
,
в
этом
случае
действует
стандартное
в
данной
версии
языка
правило
для
обозначения
строки
продолжения
(
непробельный
символ
в
шестой
позиции
для
фиксированного
формата
записи
и
амперсанд
для
свободного
формата
).
Пример программы на языке Fortran с использованием OpenMP
program omp_example
integer i, k, N
real*4 sum, h, x
print *, "Please, type in N:"
read *, N
h = 1.0 / N
sum = 0.0
C$OMP PARALLEL DO SCHEDULE(STATIC) REDUCTION(+:sum)
do i = 1, N
x = i * h
sum = sum + 1.e0 * h / (1.e0 + x**2)
enddo
print *, 4.0 * sum
end
Привязка к языку C
В
программах
на
языке
C
прагмы
,
имена
функций
и
переменных
окружения
OMP
начинаются
с
omp
,
omp_
или
OMP_
.
Формат
директивы
:
#pragma omp директива [оператор_1[, оператор_2, …]]
В
OpenMP-
программе
используется
заголовочный
файл
omp.h
.
Пример программы на языке С с использованием OpenMP
#include "omp.h"
#include <stdio.h>
double f(double x)
{
return 4.0 / (1 + x * x);
}
main () {
const long N = 100000;
long i;
double h, sum, x;
sum = 0;