ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

МГУПИ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

Кафедра ‘Персональные компьютеры и сети’

В.М.Баканов

ПАРАЛЛЕЛЬНЫЕ

ВЫЧИСЛЕНИЯ

УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ

по выполнению лабораторных работ Москва 2010 УДК 681.3 Рекомендовано к изданию в качестве учебно-методического пособия редакционно-издательским советом МГУПИ Рецензент: профессор, к.т.н. Зеленко Г.В.

Баканов В.М.

Параллельные вычисления: учебно-методическое пособие по выполнению лабораторных работ. -M.: МГУПИ, 2010. – 53 c.

Рассматриваются вопросы выявления скрытого параллелизма в алгоритмах путем явного (построение ярусно-параллельной формы графа алгоритма) и неявного (методика потоковых - DATA-FLOW - вычислений), разработки параллельных программ в MPI-парадигме программирования и количественного исследования величины ускорения вычислений при параллелизации от параметров многопроцессорной вычислительной системы и качества параллельных программ.

Пособие имеет практическую направленность и может быть использовано студентами для подготовки к выполнению лабораторных и практических работ, курсовых и дипломных проектов. Создаваемые сетевые приложения работоспособны в многопроцессорной среде архитектуры MPP (Massively Parallel Processing); в частности, на Linux-вычислительном кластере кафедры ИТ-4 МГУПИ. Перед проведением работ желательно ознакомиться с конспектом лекций по дисциплине ‘Параллельные вычисления’.

Подготовлено в соответствии Государственным стандартом для учебной дисциплины ‘Параллельные вычисления’.

© Баканов В.М., © МГУПИ, Содержание Стр.

Введение

1 Лабораторная работа 1. Представление графа алгоритма в ярусно-параллельной форме ……………….…………………………... 2 Лабораторная работа 2. Решение задач на симуляторе потокового (DATA-FLOW) вычислителя………………………………… 3 Лабораторная работа 3. Определение параметров коммуникационной сети вычислительного кластера…………………………….... 4 Лабораторная работа 4. Простые MPI-программы (численное интегрирование)…………………………………………………………. 5 Лабораторная работа 5. Исследование зависимости производительности многопроцессорной вычислительной системы от числа вычислительных узлов и размера обрабатываемых данных ………… Список использованной литературы

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

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

Одним из методов выявления параллелизма является представление алгоритма в т.н. ярусно-параллельной форме (ЯПФ); при этом на отдельном ярусе (слое) располагаются операторы, зависимые (по исходным данным для выполнения - операндам) только от результатов операций, находящихся уровнем выше. Операция представления алгоритма в ЯПФ может быть выполнена программно или аппаратно (с использованием вычислительной системы cо специализированной архитектурой; http://burcom.ru).

MPI (Message Passing Interface, http://www.mpi-forum.org) является технологией создания параллельно выполняющихся программ, основанной на передаче сообщений между процессами (сами процессы могут выполняться как на одном, так и на различных вычислительных узлах). MPI-технология является типичным примером императивной (основанной на полном управлении программистом последовательностью вычислений, распределения данных и обменов информацией между процессами) технологии создания программ для параллельного выполнения [1,2]. Заметим, что сейчас и в дальнейшем всегда будем говорить ‘процесс’ (но не ‘процессор’), памятуя, что современные многоядерные процессоры могут выполнять несколько независимых процессов одновременно.

Формально MPI-подход основан на включении в программные модули вызовов функций специальной библиотеки (заголовочные и библиотечные файлы для языков С/С++ и Fortran) и загрузчика параллельно исполняемого кода в вычислительные узлы (ВУ). Подобные библиотеки имеются практически для все платформ, поэтому написанные с использованием технологии MPI взаимодействия ветвей параллельного приложения программы независимы от машинной архитектуры (могут исполняться на однопроцессорных и многопроцессорных c общей или разделяемой памятью ЭВМ), от расположения ветвей (выполнение на одном или разных процессорах) и от API (Application Program Interface) конкретной операционной системы (ОС).

Основными отличиями стандарта MPI-2 являются: динамическое порождение процессов, параллельный ввод/вывод, интерфейс для C++, расширенные коллективные операции, возможность одностороннего взаимодействия процессов (см. [3] и http://www.mpi-forum.org). В настоящее время MPI-2 нечасто; существующие реализации поддерживают версии MPI-1.

MPI является (довольно) низкоуровневым инструментом программиста; c помощью MPI созданы рассчитанные на численные методы специализированные библиотеки (например, включающая решение систем линейных уравнений, обращение матриц, ортогональные преобразования, поиск собственных значений и т.п. библиотеки ScaLAPACK, http://www.netlib.org/scalapack и AZTEC, http://www.cs.sandia.gov/CRF/aztec1.html для плотнозаполненных и разреженных матриц соответственно). MPI не обеспечивает механизмов задания начального размещения процессов по вычислительным узлам (процессорам); это должен явно задать программист или воспользоваться неким сторонним механизмом.

1 Лабораторная работа 1. Представление графа алгоритма в яруснопараллельной форме 1.1 Цель работы Целью работы является получение навыков в представлении произвольных алгоритмов в ярусно-параллельной форме c целью выявления групп операторов, могущих быть выполненными независимо (фактически параллельно).

Работа может быть рекомендована в качестве самостоятельной (домашней).

1.2 Теоретическая часть Выявление параллелизма в произвольном алгоритме – нетривиальная задача. Дело в том, что параллелизм обычно является скрытым (для нетренированного ума). Однако существуют формальные процедуры, позволяющие выявить скрытый параллелизм в алгоритме; одна из них – представление алгоритма в ярусно-параллельной форме (ЯПФ).

Давно известен и применяем метод представления алгоритма в виде графовой структуры. Граф G обычно обозначается G=(V,E), где V – множество вершин (vertex), E – множество ребер (edge), ребро между вершинами i и j обозначается как e(i,j). В общем случае вершины графа соответствуют некоторым действиям программы, а ребра – отношениям между этими действиями.

Простейший граф такого рода описывает информационные зависимости алгоритма (вершины графа соответствуют отдельным операциям алгоритма, наличие ребра между вершинами i,j говорит о необходимости при выполнении операции j наличия аргументов (операндов), выработанных операцией i;

в случае независимости выполнения операций i и j дуга между вершинами отсутствует). Такой граф называют графом алгоритма (вычислительной моделью ‘операторы - операнды’). Даже при отсутствии условных операторов (что маловероятно) число выполненных операций (а следовательно, и общее число вершин графа и, соответственно, число ребер) зависит от размеров входных данных, т.е. граф алгоритма (ГА) является параметризованным по размеру входных данных. Ацикличность ГА следует из невозможности определения любой величины в алгоритме через саму себя. ГА также является ориентированным (все ребра направлены). Различают детерминированный ГА (программа не содержит условных операторов) и недетерминированный ГА (в противном случае). Для недерминированного ГА не существует взаимно-однозначного соответствия между операциями описывающей его программы и вершинами графа при всех наборах входных параметрах; поэтому чаще всего рассматриваются детерминированные алгоритмы. Не имеющие ни одного входящего или выходящего ребра вершины ГА называются входными или выходными вершинами соответственно. Построение ГА не является трудоемкой операцией (чего нельзя сказать о процедурах анализа графа) – любой компилятор (интерпретатор) строит (явно или неявно) его при анализе каждого выражения языка программирования высокого уровня На рис.1.1 в общем виде представлен алгоритм вычислений по формуле r=a b+a/c. Исходными данными для вычисления являются константы a,b,c, результат – r. В общем случае преобразование r a,b,c требует 3 действий (операторов) – a b, a/c и a b+a/c. Исходными данными (операндами) для первого оператора являются a,b; для второго – a,c; для третьего – результаты вычислений a b и a/c (см. осуществляющее преобразование r a,b,c ‘облако вычислений’, показанное рис.1.1a).

Рисунок 1.1 — Методы преобразования r a,b,c : a) - представление алгоритма в виде ‘облака вычислений’ (порядок выполнения не определен), б) - последовательного выполнения, в) – ярусно-параллельная форма алгоритма Для последовательного вычислителя порядок выполнения операторов лежит на поверхности – сначала вычисляются a b и a/c (причем в любой последовательности), далее a b+a/c (рис.1.1б). Т.к. выполнение a b и a/c не зависит друг от друга (говорят, что они ортогональны по операндам), легко получить ЯПФ для этого случая – рис.1.1в); часто из нумерации ярусов исключают самый первый и последний (исходные данные и результаты соответственно, ибо на них не происходит собственно вычислений). В результате становится ясно, что данный алгоритм при параллельной обработке можно вычислить за 2 шага (ab и a/c одновременно, затем a b+a/c последовательно) вместо 3-х при последовательной (один за другим a b, a/c и a b+a/c);

причем на первом ярусе необходима работа двух арифметических процессоров (действия ‘умножение’ и ‘деление’), на втором – одного (действие – ‘сложение’). При последовательной обработке общее время выполнения алгоритма будет равно сумме 3-х действий ta b + ta/c + ta b+a/c, при параллельной – max(ta b, ta/c) + ta b+a/c (в случае ta b = ta/c = ta b+a/c получаем выигрыш по скорости в полтора раза).

Фактически при преобразовании графа алгоритма в ЯПФ проводится анализ внутренней структуры алгоритма с целью поиска групп операторов, могущих быть выполненными параллельно. Заметим, что количество ярусов определяет длину критического пути.

Вообще говоря, ‘операторами’ можно считать законченные действия любой сложности по преобразованию данных – от единичного выражения (строки) или группы строк в языке программирования высокого уровня до единичной машинной (процессорной) инструкции. Однако между этими указанными крайними случаями есть существенная разница в числе операндов (для оператора языка высокого уровня число операндов может достигать десятков/сотен, а для инструкции процессора обычно один/два). Конечно, осуществлять подобные вышеописанным преобразования с операциями, имеющими 1 2 операнда, много проще, чем при десятках операндов.

Рассмотрим чуть более сложный пример – разрешение корней x1,x2 полного квадратного уравнения а x +b x+c=0 посредством (предложенного индийским математиком Брахмагуптой в VII столетии н.э.) алгоритма в виде алгебраической формулы x1,2=(-b ± sqr(b -4 a c))/(2 a), где a,b,c – постоянные, sqr - операция извлечения квадратного корня. Последовательность вычислений (один из вариантов) нахождения корней приведена в табл.1.1 и требует около десятка операций (сложение, вычитание, умножение, деление, изменение знака, вычисление квадратного корня).

Таблица 1.1. — Последовательность вычисления значений корней полного 2 b_neg neg(b) b_neg – рабочая переменная; neg – операция изменение знака (‘унарный минус’) При последовательном вычислении граф алгоритма (рис.1.2) полностью копирует последовательность действий табл.1.1; имеет 3 входных вершины (соответствующие вводу коэффициентов a,b и c), две выходные вершины (вычисленные корни x1,x2 исходного уравнения) и 11 вершин, соответствующих операторам алгоритма.

Рисунок 1.2 — Граф алгоритма (зависимость ‘операции – операнды’) нахождения корней полного квадратного уравнения для последовательного выполнения Тот же граф представлен на рис.1.3 в ЯПФ – в каждом ярусе собраны операторы, требующие для своего выполнения значений (операндов), вычисляемых только на предыдущих ярусах (всего на рис.1.3 выделено 6 ярусов);

т.о. параллельная обработка данного алгоритма требует последовательного 6разового выполнения блоков параллельных операций (в каждом из которых запускаются 4,1,1,1,2,2 независимых процесса соответственно, причем ярусы 2,3,4 вынужденно вырождаются в последовательное выполнение).

Анализ графа рис.1.3 позволяет уже сделать некоторые конкретные выводы об альтернативах распараллеливания. Заметим, что ярус 1 перегружен операциями (3 умножения и 1 изменение знака), часть из них (кроме операции 2) можно перенести на более нижние ярусы (варианты: операцию 4 на ярус 2, операцию на ярусы 2,3 или 4, операцию 1 на ярусы 2,3,4 или 5); конкретный вариант должен выбираться исходя из дополнительных данных (например, время выполнения конкретных операций, число задейство- Рисунок 1.3 — Граф алгоритма (зависимость ‘опеванных вычислительных мо- рации - операнды’) для нахождения корней полдулей, минимизация времени ного квадратного уравнения с группировкой операций по ярусам (в ЯПФ) обменов данными между модулями). Оптимизация графа вычислений - весьма трудоемкая (сравнимая с трудоемкости самих вычислений по программе) операция; некоторые постановки проблемы приведены в работе [3].

Выявление этих ярусов представляет собой один из уровней анализа внутренней структуры алгоритма. При большом количестве операторов вышеуказанное преобразование ГА в ЯПФ провести непросто, для этого используют специальные программные средства.

Нижеприведена упрощенная последовательность действий по выявлению могущих выполняться параллельно ярусов графа алгоритма (вдумчивый читатель самостоятельно произведет необходимые уточнения и оптимизацию):

а) Задать список вершин, зависящих только Начальные данные для работы алот входных данных; занести его в список горитма задаются вручную б) Найти вершины, зависимые по ребрам от Наиболее трудоемкий пункт, тревершин, входящих только в список list_1 бующий просмотра матрицы и предыдущие списки (если они есть); смежности для каждого элемента в) Если список list_2 не пуст, скопировать Цикл по ярусам, пока оные могут его в list_1 и идти к пункту б); иначе за- быть выявлены Вариант (с целью достижения наибольшей прозрачности оптимизации не производилось) реализации алгоритма на языке С приведен ниже (исходные данные - квадратная булева матрица смежности MS[ ][ ] размерности N_MS, одномерные целочисленные массивы LIST_1[ ] и LIST_2[ ] длиной N_L1 и N_L соответственно):

002 N_L2=0;