Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

46

Московский Государственный Университет

имени М.В. Ломоносова

Факультет вычислительной математики и кибернетики

Параллельное программирование на языке C-DVM

(Методическое пособие по практикуму для студентов 2-4 курсов)

Москва, 2002 год

1 Введение 4

2 Модель параллелизма DVM 4

3 Распараллеливание программ на языке C-DVM 5

3.1 Абстрактная модель распараллеливания 5

3.2 Распределение данных. Директивы DISTRIBUTE и REDISTRIBUTE 6

3.3 Локализация данных. Директивы ALIGN и REALIGN 7

3.4 Распределение витков параллельного цикла. Директива PARALLEL 8

3.5 Удаленные данные. Их типы и спецификация 10

3.5.1 Локализация данных 10

3.5.2 Удаленные данные типа SHADOW 11

3.5.3 Удаленные данные типа ACROSS 12

3.5.4 Удаленные данные типа REMOTE 12

3.5.5 Удаленные данные типа REDUCTION 12

3.6 Копирование секций массивов 12

3.7 Многомерные массивы 13

3.8 Процедуры 14

3.9 Ввод/вывод 14

3.10 Ограничения на использование языка СИ 15

4 Компиляция, выполнение и отладка DVM-программ 16

4.1 Что такое DVM-программа? 16

4.2 Настройка DVM-системы 16

4.3 Методика отладки DVM-программ 17

4.3.1 Функциональная отладка программы 17

4.3.1.1 Последовательное выполнение и отладка средствами стандартного компилятора с языка Си . 17

4.3.1.2 Компиляция. Получение готовой программы. 17

4.3.1.3 Динамический контроль DVM-указаний 18

4.3.1.4 Сравнение результатов выполнения 19

4.3.2 Отладка эффективности DVM-программы 21

4.3.2.1 Основные характеристики производительности 22

4.3.2.2 Представление программы в виде иерархии интервалов. Выполнение со сбором статистики. 23

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

4.3.2.4 Рекомендации по анализу характеристик 25

5 Пример задачи на C-DVM 26

Алгоритм Якоби 26

6. Литература. 28

Приложение 1. Синтаксис директив C-DVM 28

Приложение 2. Сообщения компилятора C-DVM 30

1 . Фатальные ошибки 30

2 . Диагностики сканнера и парсера 30

3 . Ошибки файлового уровня и операторов 30

4 . Описания 31

5. Объявление и использование DVM-объектов 32

6. DISTRIBUTE, ALIGN, TEMPLATE 33

7. Доступ к распределенным данным 34

8 . Цикл PARALLEL 34

9 . SHADOW 35

10 . REDUCTION 35

11. Процедуры 35

11 . Трассировка данных 36

12 Разное 36

Приложение 3. Диагностические сообщения динамического отладчика 36

1. Динамический контроль 37

2. Накопление и сравнение трассировки 38

3. Структура конфигурационного файла трассировки 39

4. Структура трассировки вычислений 39

Приложение 4. Сообщения об ошибках системы поддержки 41

1 . Ошибки запуска и завершения 42

2 . Ошибки вида "... is not a DVM object" 42

3 . Ошибки вида "[the object] is not a/the …" 43

4 . Ошибки вида "…has not been aligned/mapped" и "…has already been aligned/mapped"; "…does not exist" и "…already exists" 43

5 . Ошибки индексации и значений 44

6 . Другие семантические ошибки 45

7. Ошибки запроса памяти и количества объектов 45

8. Ошибки нижнего уровня передачи сообщений 45

Приложение 5. Сообщения при сборе статистики. 46

1

2Введение

Предлагаемое методическое пособие предназначено для студентов 2-го, 3-го и 4-го курсов. Целью практикума является знакомство студентов с DVM-системой, приобретение ими навыков написания и отладки параллельных программ.

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

Язык C-DVM предоставляет возможность написать программу, которая может одновременно рассматриваться и как последовательная, и как параллельная. Основная работа по реализации модели выполнения параллельной программы (например, распределение данных и вычислений) осуществляется системой поддержки выполнения DVM-программ. Отладчик параллельных программ позволит провести функциональную отладку параллельной программы. Анализатор производительности предоставит возможность оценить эффективность параллельной программы.

Язык C-DVM - это расширение ANSI-C специальными аннотациями для спецификации параллельного выполнения программы. Эти аннотации называются DVM-директивами. В пособии дается описание только тех директив, которые необходимы для выполнения поставленной задачи.

Управление работой системы поддержки, работой динамического отладчика, сбором статистики осуществляется при помощи параметров. В пособии есть описание настройки DVM-системы и способы коррекции параметров, необходимых для работы.

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

3Модель параллелизма DVM

На первом этапе определяются массивы, которые могут быть распределены между процессорами (распределенные данные). Эти массивы специфицируются директивами отображения данных. Остальные переменные (распределяемые по умолчанию) отображаются по одному экземпляру на каждый процессор (размноженные данные). Размноженная переменная должна иметь одно и то же значение на каждом процессоре за исключением переменных в параллельном цикле .

Распределение данных определяет множество локальных или собственных переменных для каждого процессора. Множество собственных переменных определяет правило собственных вычислений: процессор присваивает значения только собственным переменным.

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

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

4Распараллеливание программ на языке C-DVM

4.1Абстрактная модель распараллеливания

Параллелизм последовательной программы описывается на языке C-DVM с помощью директив. Каждая директива оформляется в виде спецмакроса следующего вида:

DVM(<директива-DVM>)

Формальный синтаксис директив приведен в Приложении 1.

Распараллеливание программы в модели DVM можно разделить на два этапа.

1. Распределение данных (массивов) и вычислений (параллельных циклов) на массив виртуальных процессоров.

2. Определение и спецификация удаленных (общих) данных.

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

На первом этапе используются директивы DISTRIBUTE, ALIGN и PARALLEL. Если рассматривать эти директивы на абстрактном уровне, то они устанавливают соответствие между точками индексных (дискретных) пространств двух объектов. При этом используются индексные пространства следующих объектов:

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

A_i - индексное пространство i–го массива данных

L_j - индексное пространство j–го параллельного цикла. Параллельный цикл рассматривается как массив, элементом которого является виток цикла. Количество измерений этого массива определяется количеством заголовков цикла.

Директивы устанавливают соответствие между точками (элементами) следующих объектов:

ALIGN: A_i1  A_i2. Каждой точке (элементу массива) A_i2 ставится в соответствие подмножество точек (элементов массива) A_i1.

PARALLEL: L_j  A_i. Каждой точке (элементу массива) A_i ставится в соответствие подмножество точек (витков цикла) L_j.

DISTRIBUTE: A_i  P. Каждой точке (виртуальному процессору) P ставится в соответствие подмножество точек (элементов массива) A_i.

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

Данные и операторы, не специфицированные этими директивами, автоматически распределяются на каждый виртуальный процессор (размноженные данные и не распараллеливаемые вычисления).

Определение общих (удаленных) данных

Общими (удаленными) данными будем называть данные, вычисляемые на одном процессоре и используемые на других процессорах.

Выявление удаленных данных производится с помощью анализа операторов присваивания. Оператор присваивания всегда выполняется на том процессоре, где размещены данные его левой части. Если данные левой и правой частей оператора присваивания размещены на одном процессоре, то удаленных данных для этого оператора не существует. В противном случае необходимо определить тип и размер удаленных данных и описать их соответствующими директивами (см. раздел 3.5 ). Такой анализ будем называть анализом локализации данных.

Цель распараллеливания - максимальный параллелизм при минимизации удаленных данных (максимум локализации).

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

4.2Распределение данных. Директивы DISTRIBUTE и REDISTRIBUTE

Первоначальное распределение массива описывается следующей директивой

DVM( DISTRIBUTE f₁…f_k ) <описание-массива-на-языке-Си>

где f_i = [ BLOCK ] - распределение равными блоками

= [ ] - распределение целым измерением.

k - количество измерений массива.

Для каждого измерения массива задается формат распределения. Если задан формат [ BLOCK ], то измерение «разрезается» на равные блоки и распределяется по одному блоку на процессор. Такое измерение будем называть распределенным измерением. Если задан формат [ ], то на каждый процессор распределяется целое измерение (локальное измерение).

Количество форматов [ BLOCK ] определяет количество измерений массива виртуальных процессоров. Если мы пронумеруем форматы [ BLOCK ], как fb₁,…,fb_n, то измерение с форматом fb_i отображается на i–ое измерение массива виртуальных процессоров, а количество блоков определяется размером i–го измерения массива виртуальных процессоров. В этом случае при запуске программы на выполнение можно задавать любой n–мерный массив виртуальных процессоров.

Пример.

DVM(DISTRIBUTE [BLOCK] [ ] [BLOCK]) float A[N][N][N};

Такое описание указывает на то, что пользователь работает с двумерным массивом виртуальных процессоров (количество форматов [ BLOCK ] равно 2). Пусть при запуске программы на выполнение задан массив виртуальных процессоров P[M1][M2]. Тогда эта директива распределит первое измерение массива А на первое измерение P блоками размера N/M1, третье измерение А - на второе измерение P блоками размера N/M2, а второе измерение А будет целиком распределено на каждый виртуальный процессор.

Любой массив, который специфицирован директивой DISTRIBUTE можно перераспределить следующей директивой

DVM( REDISTRIBUTE f₁…f_k ) <идентификатор-массива>

4.3Локализация данных. Директивы ALIGN и REALIGN

Основным способом локализации данных (т.е. уменьшения удаленных данных) является совместное распределение нескольких массивов. Совместное распределение двух массивов А и В описывается следующей директивой выравнивания массивов.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов книги