Немнюгин С.А. Средства программирования для многопроцессорных вычислительных систем

Подождите немного. Документ загружается.

Санкт-Петербургский государственный университет

С.А. Немнюгин

Средства программирования для

многопроцессорных вычислительных систем

Intel Multicore Curriculum Initiative

Санкт-Петербург

2007

Данное пособие предназначено для использования в учебных курсах, посвященных

средствам параллельного программирования для многопроцессорных вычислительных

систем. Дается краткое введение в параллельное программирование, приводится описание

моделей параллельного программирования и специфики проектирования параллельных

алгоритмов и программ. Значительная часть пособия содержит основные сведения об

инструментальных средствах параллельного программирования



OpenMP и MPI.

Описание строится по следующей схеме: модель параллельной программы, привязки к

языкам программирования Фортран и C, описание программного интерфейса. Дается

краткий обзор языка программирования Фортран 90.

Пособие предназначено для студентов, аспирантов, а также всех тех, кто планирует

использование данной технологии для решения своих задач. Оно может использоваться в

качестве справочника по средствам параллельного программирования.

Оглавление

I Введение 4

II OpenMP 18

III MPICH 31

IV Фортран 90 75

V Литература 88

I. Введение

Последовательная и параллельная модели программирования

Модель программирования  это совокупность приемов программирования, отвечающих

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

класса алгоритмов. Модель программирования основана на определенном представлении о

логической организации компьютера, его архитектуре. Существуют различные архитектуры,

и одной из схем их классификации является таксономия Флинна, основанная на описании

работы компьютера с потоками команд и данных (рис. 1 - 5).

Рис. 1. Параметры классификации Флинна

Рис. 2. Архитектура SISD (Single Instruction Stream  Single Data Stream)  один поток

команд и один поток данных

Рис. 3. Архитектура SIMD (Single Instruction Stream  Multiple Data Stream)  один поток

команд и несколько потоков данных

Рис. 4. Архитектура MISD (Multiple Instruction Stream  Single Data Stream)  несколько

потоков команд и один поток данных

Рис. 5. Архитектура MIMD (Multiple Instruction Stream  Multiple Data Stream)  несколько

потоков команд и несколько потоков данных

Взаимодействие данных и команд может быть представлено информационным графом.

Информационный граф описывает последовательность выполнения операций и взаимную

зависимость между различными макрооперациями или блоками операций. Узлами

информационного графа являются макрооперации, а однонаправленными дугами  каналы

обмена данными (рис. 6).

Рис. 6. Информационный граф программы

Каждый узел можно охарактеризовать парой (n, s), где n  имя узла, s  его размер. Размер

узла определяется количеством элементарных операций, входящих в его состав. Дуга

характеризуется парой (v, d), где v  пересылаемые данные, а d  время, затрачиваемое на

ее пересылку.

Информационный граф содержит линейные участки, а также многосвязные фрагменты

(циклы). Предельные случаи информационного графа, топологически эквивалентные

линейной последовательности макроопераций и лесу линейных последовательностей

(рис. 7), соответствуют чистым последовательной и параллельной моделям вычислений.

Рис. 7. Предельные случай информационного графа программы

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

• относительно невысокая производительность;

• применение стандартных языков программирования;

• хорошая переносимость программ на уровне исходного кода.

Параллельная модель программирования характеризуется:

• возможностью добиться более высокой производительности программ;

• применением специальных приемов программирования;

• применением специальных инструментов программирования;

• более высокой трудоемкостью программирования;

• проблемами с переносимостью программ.

При разработке параллельных приложений возникают и специфические для параллельной

модели программирования проблемы:

• управление работой множества процессов;

• организация межпроцессных пересылок данных;

• вероятность тупиковых ситуаций (взаимных блокировок). Блокировки возникают,

если процесс или поток ожидает доступ к ресурсу, заблокированному другим

процессом, блокируя, в свою очередь, доступ к ресурсу, требуемому для продолжения

работы второго процесса или потока;

• нелокальный и динамический характер ошибок. Процессы или потоки выполняются

на разных процессорах или ядрах. Загрузка вычислительных узлов изменяется с

течением времени, поэтому для обеспечения корректной работы параллельной

программы может потребоваться явная синхронизация;

• утрата детерминизма (предсказуемого поведения программы в процессе ее

исполнения). Параллельная программа может давать разные результаты при

повторных запусках даже без модификации кода и исходных данных. Это является

следствием «гонок за данными» - одновременного и асинхронного доступа разных

процессов или потоков к общим переменным;

• необходимость заботиться о масштабируемости программы (масштабируемость –

это свойство вычислительной системы, компьютерной сети или процесса/процессов,

которое заключается в сохранении способности эффективно работать при

возрастании их сложности);

• необходимость заботиться о сбалансированной загрузке вычислительных узлов.

Модели параллельного программирования

В рамках параллельной модели программирования существуют различные подходы,

ориентированные на разные архитектуры высокопроизводительных вычислительных систем

и различные инструментальные средства. Перечислим некоторые из них.

Модель передачи сообщений

Основные особенности данного подхода:

• Программа порождает несколько задач.

• Каждой задаче присваивается свой уникальный идентификатор.

• Взаимодействие осуществляется посредством отправки и приема сообщений.

• Новые задачи могут создаваться во время выполнения параллельной программы,

несколько задач могут выполняться на одном процессоре.

Модель параллелизма данных

Основные особенности данного подхода:

• Одна операция применяется к множеству элементов структуры данных. Программа

содержит последовательность таких операций.

• "Зернистость" вычислений мала.

• Программист должен указать транслятору, как данные следует распределить между

задачами.

Модель общей памяти

В модели общей (разделяемой) памяти задачи обращаются к общей памяти, имея общее

адресное пространство и выполняя операции считывания/записи. Управление доступом к

памяти осуществляется с помощью разных механизмов, таких, например, как семафоры. В

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

Это упрощает программирование. Вместе с тем особое внимание приходится уделять

соблюдению детерминизма, таким явлениям, как «гонки за данными» и т. д.

Законы Амдала

Законы Амдала составляют теоретическую основу оценок достижимой производительности

параллельных программ. Они сформулированы для некоторой идеализированной модели

параллельных вычислений, в которой, например, не учитывается латентность (конечное

время передачи данных) коммуникационной среды и т. д.

1-й закон

Производительность вычислительной системы, состоящей из связанных

между собой устройств, определяется самым медленным компонентом.

2-й закон

Пусть время выполнения алгоритма на последовательной машине T

причем T

 время выполнения последовательной части алгоритма, а T



параллельной. Тогда при выполнении той же программы на идеальной

параллельной машине, содержащей N процессорных элементов

коэффициент ускорения:

s p

T T

T P

= = =

где

s p

T T

s p

T T

 относительные доли последовательной и

параллельной частей (S + P = 1). Графическое представление закона

Амдала дано на рис. 8.

3-й закон

Пусть система состоит из N простых одинаковых процессорных элементов,

тогда при любом режиме работы

≤

Рис. 8.

Зависимость

ускорения

от

доли

параллельного

кода

числа

процессоров

законе

Амдала

Две парадигмы параллельного программирования

На

рис

. 9

представлен

информационный

граф

показывающий

что

общем

случае

программе

присутствуют

как

параллелизм

данных

так

параллелизм

задач

Рис. 9.

Параллелизм

задач

параллелизм

данных

Параллелизм данных

Наличие

нескольких

стрелок

связывающих

соседние

вершины

информационного

графа

означает

применение

одной

операции

сразу

нескольким

элементам

данных

(

массиву

Различные

фрагменты

такого

массива

могут

обрабатываться

на

векторном

процессоре

или

на

разных

процессорах

параллельной

вычислительной

системы

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

или

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

рамках

данного

подхода

выполняются

во

время

трансляции

этом

случае

при

разработке

параллельного

приложения

от

программиста

требуется

•

задание

опций

векторной

или

параллельной

оптимизации

транслятору

;

•

задание

директив

параллельной

компиляции

;

•

использование

специализированных

языков

параллельных

вычислений

библиотек

подпрограмм

специально

разработанных

учетом

конкретной

архитектуры

компьютера

оптимизированных

для

этой

архитектуры

Основные

особенности

данного

подхода

перечислены

ниже

•

обработкой

данных

управляет

одна

программа

;

•

пространство

имен

является

глобальным

;

•

параллельные

операции

над

элементами

массива

выполняются

одновременно

на

всех

доступных

данной

программе

процессорах

При

программировании

на

основе

параллелизма

данных

часто

используются

специализированные

языки

или

надстройки

над

языками

 DVM Fortran, HPF (High

Perfomance Fortran)

другие

Реализация

модели

параллелизма

данных

требует

поддержки

параллелизма

на

уровне

транслятора

Такую

поддержку

могут

обеспечивать

•

препроцессоры

использующие

существующие

последовательные

трансляторы

специализированные

библиотеки

реализациями

параллельных

алгоритмических

конструкций

;