WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     || 2 |
-- [ Страница 1 ] --

Министерство образования Российской Федерации Нижегородский государственный университет им. Н.И. Лобачевского В.П. Гергель, А.А. Лабутина ПАРАЛАБ ПРОГРАММНАЯ СИСТЕМА ДЛЯ ИЗУЧЕНИЯ И ИССЛЕДОВАНИЯ

МЕТОДОВ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Учебное пособие Нижний Новгород Издательство Нижегородского госуниверситета 2004 УДК 004.421.2 ББК 32.973.26-018.2 Введение Г 37 Программная система Параллельная Лаборатория (сокращенное наименование ПараЛаб) обеспечивает возможность проведения Г 37 Гергель В.П., Лабутина А.А. ПараЛаб. Программная вычислительных экспериментов с целью изучения и исследования система для изучения и исследования методов параллельных параллельных алгоритмов решения сложных вычислительных задач.

вычислений. Учебное пособие – Нижний Новгород: Изд-во ННГУ им.

Система может быть использована для организации лабораторного Н.И. Лобачевского, 2003. 125 с.

практикума по различным учебным курсам в области параллельного программирования, в рамках которого обеспечивается возможность В учебном пособии описывается учебно-исследовательская • моделирования многопроцессорных вычислительных систем с система ПараЛаб для проведения вычислительных экспериментов с различной топологией сети передачи данных;

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

• получения визуального представления о вычислительных Использование системы ПараЛаб в лабораторном практикуме процессах и операциях передачи данных, происходящих при обеспечивает возможность моделирования многопроцессорных параллельном решении разных вычислительных задач;

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

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

управлением операционных систем MS Windows 2000 или MS Учебное пособие предназначено для широкого круга студентов, Windows XP (режим многозадачной имитации параллельных аспирантов и специалистов, желающих изучить и практически вычислений). Кроме режима имитации, в системе ПараЛаб использовать параллельные компьютерные системы для решения обеспечивается удаленный доступ к имеющейся многопроцессорной вычислительно трудоемких задач.

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

В целом система ПараЛаб представляет собой интегрированную. ББК 32.973.26-018. среду для изучения и исследования параллельных алгоритмов решения сложных вычислительных задач. Широкий набор имеющихся средств ISBN 5-85746-738- визуализации процесса выполнения эксперимента и анализа полученных результатов позволяет изучить эффективность использования тех или иных алгоритмов на разных вычислительных системах, сделать выводы о масштабируемости алгоритмов и определить возможное ускорение процесса параллельных вычислений.

Реализуемые системой ПараЛаб процессы изучения и © Гергель В.П., Лабутина А.А., 2003 исследований ориентированы на активное освоение основных теоретических положений и способствуют формированию у пользователей своих собственных представлений о моделях и методах 2 параллельных вычислений путем наблюдения, сравнения и сопоставления широкого набора различных визуальных графических 1. Общая характеристика системы форм, демонстрируемых в ходе выполнения вычислительного эксперимента.

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

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

при проведении научных исследований для оценки эффективности • определить топологию параллельной вычислительной параллельных вычислений.

системы для проведения экспериментов, задать число процессоров в Пользователи, начинающие знакомиться с проблематикой этой топологии, установить производительность процессоров, параллельных вычислений, найдут систему ПараЛаб полезной для выбрать характеристики коммуникационной среды и способ освоения методов параллельного программирования, опытные коммуникации;

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

которой в составе системы ПараЛаб имеются реализованные параллельные алгоритмы решения, выполнить задание параметров задачи;

• выбрать параллельный метод для решения выбранной задачи;

• установить параметры визуализации для выбора желаемого темпа демонстрации, способа отображения пересылаемых между процессорами данных, степени детальности визуализации выполняемых параллельных вычислений;

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

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

одновременное выполнение эксперимента для нескольких заданий позволяет наглядно сравнивать динамику решения задачи различными методами, на разных топологиях, с разными параметрами исходной задачи. При выполнении серии экспериментов, требующих длительных вычислений, в системе имеется возможность их проведения в автоматическом режиме с запоминанием результатов в журнале 4 экспериментов для организации последующего анализа полученных вычислений [1-3]. Для реальных экспериментов на данных;

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

• накапливать и анализировать результаты выполненных Любой из проведенных ранее экспериментов может быть восстановлен экспериментов;

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

эффективности) от параметров задачи и вычислительной системы.

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

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

на одном процессоре без использования каких-либо специальных программных средств типа библиотек передачи сообщений. Кроме Демонстрационный пример того, в рамках системы ПараЛаб обеспечивается возможность следующих способов проведения реального вычислительного Для выполнения примера, имеющегося в комплекте поставки эксперимента:

системы:

• на одном компьютере, где имеется библиотека передачи • выберите пункт меню Начало и выполните команду сообщений MPI (многопоточное выполнение эксперимента);

для Загрузить;

данной библиотеки имеются общедоступные реализации, которые • выберите строку first.prl в списке имен файлов и нажмите могут быть получены в сети Интернет и установлены на компьютере кнопку Открыть;

под управлением операционных систем MS Windows 2000 или MS • выберите пункт меню Выполнение и выполните команду В Windows XP (требование данного типа операционных систем активном окне.

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

• в режиме удаленного доступа к вычислительному кластеру.

В области "Выполнение эксперимента" представлены процессоры Если проводится реальный эксперимент на многопроцессорной вычислительной системы и структура линий коммутации. Рядом с вычислительной системе или в режиме удаленного доступа, система каждым процессором изображены те данные, которые он обрабатывает ПараЛаб предоставляет возможность выбора типов вычислительных в каждый момент выполнения алгоритма (для ленточного алгоритма узлов (например, кластер Нижегородского университета состоит из умножения матриц - это несколько последовательных строк матрицы однопроцессорных рабочих станций и многопроцессорных серверов с А и несколько последовательных столбцов матрицы В). При помощи общей памятью).

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

выполненных в режиме имитации, используются теоретические В области "Результат умножения матриц" изображается текущее оценки в соответствии с имеющимися моделями параллельных состояние матрицы – результата умножения. Поскольку результатом 6 перемножения полос исходных матриц А и В является блок матрицы С, получаемая результирующая матрица имеет блочную структуру.

2. Формирование модели Темно-синим цветом обозначены уже вычисленные блоки, голубым цветом выделены блоки, еще подлежащие определению.

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

2.1. Выбор топологии сети Топология сети передачи данных определяет структуру линий коммутации между процессорами вычислительной системы. В системе ПараЛаб обеспечивается поддержка следующих типовых топологий [3]:

• полный граф (completely-connected graph or clique)– система, в которой между любой парой процессоров существует прямая линия связи;

как результат, данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой Рис. 1. Окно вычислительного эксперимента при большом количестве процессоров;

В списке "Выполняемая задача" представлены параметры • линейка (linear array or farm) – система, в которой каждый решаемой задачи: название, метод решения, объем исходных данных. процессор имеет линии связи только с двумя соседними (с В списке "Вычислительная система" приводятся атрибуты выбранной предыдущим и последующим) процессорами;

такая схема является, с вычислительной системы: топология, количество и одной стороны, просто реализуемой, а с другой стороны, производительность процессоров, характеристики сети. соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных Ленточный индикатор "Эксперимент" отображает текущую вычислений);

стадию выполнения алгоритма. В строках "Общие затраты времени" и • кольцо (ring) – данная топология получается из линейки "Затраты на передачу данных" представлены временные процессоров соединением первого и последнего процессоров линейки;

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

• решетка (mesh) – система, в которой граф линий связи После выполнения эксперимента (восстанавливается главное образует прямоугольную двухмерную сетку;

подобная топология меню системы) можно завершить работу системы. Для этого выберите может быть достаточно просто реализована и, кроме того, может быть пункт меню Архив и выполните команду Завершить.

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

мыши на пиктограмме нужной топологии или внизу в области соответствующей круглой кнопки выбора (радиокнопки). При нажатии • гиперкуб (hypercube) – данная топология представляет кнопки Помощь можно получить справочную информацию о частный случай структуры N-мерной решетки, когда по каждой реализованных топологиях. Нажмите кнопку ОК для подтверждения размерности сетки имеется только два процессора (т.е. гиперкуб выбора и кнопку Отмена для возврата в основное меню системы содержит 2N процессоров при размерности N);

данный вариант ПараЛаб.

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

- два процессора имеют соединение, если двоичное представление их номеров имеет только одну различающуюся позицию;

- в N-мерном гиперкубе каждый процессор связан ровно с N соседями;

- N-мерный гиперкуб может быть разделен на два (N-1) мерных гиперкуба (всего возможно N различных таких разбиений);

- кратчайший путь между двумя любыми процессорами имеет длину, совпадающую с количеством различающихся битовых Рис. 2. Диалоговое окно для выбора топологии значений в номерах процессоров (данная величина известна как расстояние Хэмминга).

2.2. Задание количества процессоров Правила использования системы ПараЛаб Для выбранной топологии система ПараЛаб позволяет установить необходимое количество процессоров. Выполняемый при этом выбор 1.Запуск системы.

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

эксперимент (пункт меню Начало) и нажмите в диалоговом окне Под производительностью процессора в системе ПараЛаб Название эксперимента кнопку ОК (при желании до нажатия кнопки понимается количество операций с плавающей запятой, которое ОК может быть изменено название создаваемого окна для проведения процессор может выполнить за секунду (floating point operations per экспериментов).

second – flops). Важно отметить, что при построении оценок времени выполнения эксперимента предполагается, что все машинные команды 2. Выбор топологии вычислительной системы.

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

Для выбора топологии вычислительной системы следует выполнить команду Топология пункта меню Система. В 10 Правила использования системы ПараЛаб Задание количества процессоров.

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

Рис. 4. Диалоговое окно для задания производительности процессора 2.3. Задание характеристик сети Время передачи данных между процессорами определяет коммуникационную составляющую (communication latency) длительности выполнения параллельного алгоритма в многопроцессорной вычислительной системе. Основной набор параметров, описывающих время передачи данных, состоит из следующего ряда величин:

- латентность (tн) - время начальной подготовки, которое характеризует длительность подготовки сообщения для передачи, Рис. 3. Диалоговое окно для задания числа процессоров поиска маршрута в сети и т.п.;

- пропускная способность сети (R) – определяется как Нажмите кнопку ОК для подтверждения выбора или кнопку максимальный объем данных, который может быть передан за Отмена для возврата в основное меню системы ПараЛаб без некоторую единицу времени по одному каналу передачи данных.

изменения числа процессоров.

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

2. Определение производительности процессора.

К числу реализованных в системе ПараЛаб методов передачи данных относятся следующие два широко известных способа Для задания производительности процессоров, составляющих коммуникации [3]. Первый из них ориентирован на передачу многопроцессорную вычислительную систему, следует выполнить сообщений (МПС) как неделимых (атомарных) блоков информации команду Производительность Процессора пункта меню Система.

(store-and-forward routing or SFR). При таком подходе процессор, Далее в появившемся диалоговом окне (рис. 4) при помощи бегунка содержащий исходное сообщение, готовит весь объем данных для задать величину производительности. Для подтверждения выбора передачи, определяет транзитный процессор, через который данные нажмите кнопку ОК (или клавишу Enter). Для возврата в основное могут быть доставлены целевому процессору, и запускает операцию меню системы ПараЛаб без изменений нажмите кнопку Отмена (или пересылки данных. Процессор, которому направлено сообщение, в клавишу Escape).

12 первую очередь осуществляет прием полностью всех пересылаемых Определение характеристик коммуникационной среды.

данных и только затем приступает к пересылке принятого сообщения Для определения характеристик сети выполните команду далее по маршруту. Время пересылки данных tпд для метода передачи Характеристики сети пункта меню Система. В открывшемся сообщения размером m по маршруту длиной l определяется диалоговом окне (рис. 5) при помощи бегунков можно задать выражением:

время начальной подготовки данных (латентность) в микросекундах и пропускную способность каналов сети (Мбит/с).

tпд = tн +(m R) l.

Для подтверждения выбора нажмите кнопку ОК. Для возврата в основное меню системы ПараЛаб без изменения этих параметров Второй способ коммуникации основывается на представлении нажмите кнопку Отмена.

пересылаемых сообщений в виде блоков информации меньшего размера (пакетов), в результате чего передача данных может быть сведена к передаче пакетов (МПП). При таком методе коммуникации (cut-through routing or CTR) транзитный процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Количество передаваемых при этом пакетов равно m n = +1, V -V где V есть размер пакета, а величина V0 определяет объем служебных данных, передаваемых в каждом пакете (заголовок пакета). Как Рис. 5. Диалоговое окно для задания характеристик сети результат, время передачи сообщения в этом случае составит V l m = tн + V + n -1) tпд = tн + + (l 2 Определение метода передачи данных.

V -V0 R R Для определения метода передачи данных, который будет использоваться при проведении вычислительного эксперимента и (скобки обозначают операцию приведения к целому с избытком).

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

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

метода передачи данных и его параметров нажмите кнопку ОК.

Правила использования системы ПараЛаб 14 3. Постановка вычислительной задачи и выбор параллельного метода решения Для параллельного решения тех или иных вычислительных задач процесс вычислений должен быть представлен в виде набора независимых вычислительных процедур, допускающих выполнение на Рис. 6. Диалоговое окно для задания метода передачи данных независимых процессорах.

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

3. Завершение работы системы.

• разделение процесса вычислений на части, которые могут Для завершения работы системы ПараЛаб следует выполнить быть выполнены одновременно;

команду Завершить (пункт меню Архив).

• распределение вычислений по процессорам;

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

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

• разработка новых параллельных алгоритмов;

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

Условия эффективности параллельных алгоритмов:

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

• низкая интенсивность взаимодействия процессоров (независимость).

В системе ПараЛаб реализованы широко применяемые параллельные алгоритмы для решения ряда сложных вычислительных задач из разных областей научно-технических приложений: алгоритмы сортировки данных, матричного умножения и обработки графов.

16 Правила использования системы ПараЛаб Выбор задачи.

Для выбора задачи из числа реализованных в системе выберите пункт меню Задача и выделите левой клавишей мыши одну из строк: Сортировка, Матричное умножение, Обработка графов. Выбранная задача станет текущей в активном окне.

Рис. 8. Диалоговое окно задания параметров задачи в случае решения задачи матричного умножения 3. Определение метода решения задачи.

Для выбора метода решения задачи выполните команду Метод Рис. 7. Выбор задачи пункта меню Задача. В появившемся диалоговом окне (рис. 9) выделите мышью нужный метод, нажмите ОК для подтверждения выбора, нажмите Отмена для возврата в основное меню системы 2. Определение параметров задачи.

ПараЛаб.

Основным параметром задачи в системе ПараЛаб является объем исходных данных. Для задачи сортировки - это размер массива, для задачи матричного умножения – размерность исходных матриц, для задачи обработки графов – число вершин в графе. Для выбора параметров задачи необходимо выполнить команду Параметры задачи пункта меню Задача. В появившемся диалоговом окне (рис. 8) следует при помощи бегунка задать необходимый объем исходных данных. Нажмите ОК (Enter) для подтверждения задания параметра.

Для возврата в основное меню системы ПараЛаб без сохранения изменений нажмите Отмена (Escape).

Рис. 9. Диалоговое окно выбора метода в случае решения задачи матричного умножения.

3.1. Сортировка данных Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов 18 неупорядоченного набора значений 3.1.1. Пузырьковая сортировка.

S = {a1, a2,..., an} Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания: сравнение пар соседних элементов в порядке монотонного возрастания или убывания происходит строго последовательно. Параллельный вариант алгоритма ' ' ' ' ' ' S ~ S'= {(a1, a2,..., an ) : a1 a2... an} основывается на методе чет – нечетной перестановки [23], для которого на нечетной итерации выполнения сравниваются элементы Вычислительная трудоемкость процедуры упорядочивания пар является достаточно высокой. Так, для ряда известных простых методов (пузырьковая сортировка, сортировка включением и др.) (a3, a4) (an-1, an ) (a1, a2 ),, …,.

количество необходимых операций определяется квадратичной Если пара не упорядочена, то ее элементы переставляются. На четной зависимостью от числа упорядочиваемых данных итерации упорядочиваются пары T1 ~ n2.

(a2, a3) (a4, a5) (an-2, an-1),, …,.

Для более эффективных алгоритмов (сортировка слиянием, После n- кратного повторения подобных итераций массив оказывается сортировка Шелла, быстрая сортировка) трудоемкость определяется отсортированным. Более подробная информация о параллельном величиной варианте алгоритма приводится в разделе 8.

T1 ~ n log2 n.

Данное выражение дает также нижнюю оценку необходимого Задания и упражнения количества операций для упорядочивания набора из n значений;

1. Запустите систему ПараЛаб и создайте новый эксперимент.

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

текущей задачей является задача сортировки. Откройте диалоговое Ускорение сортировки может быть обеспечено при использовании окно выбора метода и посмотрите, какие алгоритмы сортировки могут нескольких (p, p>1) процессоров. Исходный упорядочиваемый набор в быть выполнены на текущей топологии. Так как при создании этом случае разделяется между процессорами;

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

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

правой нижней части окна.

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

изложены во многих изданиях (см., например, [7]), способы их параллельного выполнения излагаются в разделе 8 пособия.

20 3.1.2. Сортировка Шелла. упорядоченности между элементами сортируемого набора, расположенными на процессорах, соседних в структуре гиперкуба. В Параллельный алгоритм сортировки Шелла может быть разделе 8 Вы можете найти подробное описание алгоритма быстрой получен как обобщение метода параллельной пузырьковой сортировки.

сортировки. Основное различие состоит в том, что на первых итерациях алгоритма Шелла происходит сравнение пар элементов, которые в исходном наборе данных находятся далеко друг от друга Задания и упражнения (для упорядочивания таких пар в пузырьковой сортировке может 1. Запустите систему ПараЛаб. В появившемся окне понадобиться достаточно большое количество итераций). Подробное вычислительного эксперимента установите топологию гиперкуб и описание параллельного обобщения алгоритма сортировки Шелла количество процессоров, равное восьми.

можно найти в разделе 8.

2. Выполните три последовательных эксперимента с использованием трех различных алгоритмов сортировки: сортировки пузырьком, сортировки Шелла и быстрой сортировки. Сравните Задания и упражнения временные характеристики алгоритмов, которые отображаются в 1. Запустите систему ПараЛаб. Выберите топологию кольцо и правой нижней части окна. Убедитесь в том, что у быстрой сортировки установите количество процессоров, равное восьми. Проведите наименьшее время выполнения алгоритма и время передачи данных.

эксперимент по выполнению алгоритма пузырьковой сортировки.

3. Измените объем исходных данных (выполните команду 2. Установите в окне вычислительного эксперимента топологию Параметры задачи пункта меню Задача). Снова проведите гиперкуб и число процессоров, равное восьми.

эксперименты. Сравните временные характеристики алгоритмов.

3. Откройте диалоговое окно выбора метода и посмотрите, какие 4. Измените количество процессоров (выполните команду алгоритмы сортировки могут быть выполнены на этой топологии.

Количество процессоров пункта меню Система). Проведите Выберите метод сортировки Шелла. Закройте окно.

вычислительные эксперименты и сравните временные характеристики.

4. Проведите вычислительный эксперимент. Сравните количество итераций, выполненных при решении задачи при помощи метода Шелла, с количеством итераций алгоритма пузырьковой сортировки (количество итераций отображается справа в строке 3.2. Матричное умножение состояния). Убедитесь в том, что при выполнении эксперимента с Задача умножения матрицы на матрицу определяется использованием алгоритма Шелла, для сортировки массива соотношениями:

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

n 5. Проведите эксперимент с использованием метода Шелла cij = bkj,1 i, j n aik несколько раз. Убедитесь, что количество итераций не является k= постоянной величиной и зависит от исходного массива.

(для простоты изложения материала будем предполагать, что перемножаемые матрицы A и B являются квадратными и имеют порядок n n ). Как следует из приведенных соотношений, 3.1.3. Быстрая сортировка.

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

последовательном разделении сортируемого набора данных на блоки Основу возможности параллельных вычислений для матричного меньшего размера таким образом, что между значениями разных умножения составляет независимость расчетов для получения блоков обеспечивается отношение упорядоченности. При элементов cij результирующей матрицы C. Тем самым все элементы параллельном обобщении алгоритма обеспечивается отношение 22 3.2.1. Ленточный алгоритм.

матрицы C могут быть вычислены параллельно при наличии n При ленточной схеме разделения данных исходные матрицы процессоров, при этом на каждом процессоре будет располагаться по одной строке матрицы A и одному столбцу матрицы B. При меньшем разбиваются на горизонтальные (для матрицы A) и вертикальные (для количестве процессоров подобный подход приводит к ленточной матрицы B) полосы. Получаемые полосы распределяются по процессорам, при этом на каждом из имеющегося набора процессоров схеме разбиения данных, когда на процессорах располагаются по несколько строк и столбцов (полос) исходных матриц. располагается только по одной полосе матриц A и B. Перемножение Другой широко используемый подход для построения полос (а выполнение процессорами этой операции может быть выполнено параллельно) приводит к получению части блоков параллельных способов выполнения матричного умножения состоит в использовании блочного представления матриц, при котором результирующей матрицы C. Для вычисления оставшихся блоков матрицы C сочетания полос матриц A и B на процессорах должны быть исходные матрицы A, B и результирующая матрица C изменены. В наиболее простом виде это может быть обеспечено, рассматриваются в виде наборов блоков (как правило, квадратного например, при кольцевой топологии вычислительной сети (при числе вида некоторого размера m m ). Тогда операцию матричного процессоров, равном количеству полос) – в этом случае необходимое умножения матриц A и B в блочном виде можно представить для матричного умножения изменение положения данных может быть следующим образом:

обеспечено циклическим сдвигом полос матрицы B по кольцу. После многократного выполнения описанных действий (количество A11A12...A1k B11B12...B1k C11C12...C1k необходимых повторений является равным числу процессоров) на L L = L, каждом процессоре получается набор блоков, образующий горизонтальную полосу матрицы C.

Ak1Ak 2...Akk Bk1Bk 2...Bkk Ck1Ck 2...Ckk Рассмотренная схема вычислений позволяет определить где каждый блок Cij матрицы C определяется в соответствии с параллельный алгоритм матричного умножения при ленточной схеме разделения данных как итерационную процедуру, на каждом шаге выражением:

которой происходит параллельное выполнение операции k перемножения полос и последующего циклического сдвига полос Cij = Ail Blj.

одной из матриц по кольцу. Подробное описание ленточного l= алгоритма приводится в разделе 8 пособия.

Полученные блоки Cij также являются независимыми и, как результат, возможный подход для параллельного выполнения Задания и упражнения вычислений может состоять в выделении для расчетов, связанных с 1. Создайте в системе ПараЛаб новое окно вычислительного получением отдельных блоков Cij, на разных процессорах.

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

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

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

метода (алгоритмы Фокса и Кэннона) для блочно-представленных Изучите зависимость времени выполнения алгоритма от объема матриц. исходных данных и от количества процессоров.

24 3.2.2. Алгоритмы Фокса и Кэннона. эксперименты с использованием метода Фокса и метода Кэннона.

Сравните временные характеристики этих экспериментов.

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

для блочно представленных матриц состоят в следующем:

Как результат, многие теоретические и реальные прикладные задачи • Каждый из процессоров решетки отвечает за вычисление могут быть решены при помощи тех или иных процедур анализа одного блока матрицы C.

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

обработки графов [8].

• При выполнении итераций алгоритмов блоки матрицы А В системе ПараЛаб реализованы параллельные алгоритмы последовательно сдвигаются вдоль строк процессорной решетки, а решения двух типовых задач на графах: алгоритм Прима поиска блоки матрицы B - вдоль столбцов решетки. минимального охватывающего дерева, алгоритм Дейкстры поиска кратчайших путей.

• В результате вычислений на каждом из процессоров вычисляется блок матрицы С, при этом общее количество итераций Правила использования системы ПараЛаб алгоритма равно p (где р – число процессоров).

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

методов Фокса и Кэннона для умножения блочно-представленных При выборе задачи Обработка графов в системе ПараЛаб матриц.

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

Заметим, что команда доступна только в том случае, когда текущей 1. В активном окне вычислительного эксперимента системы задачей является задача обработки графов.

ПараЛаб установите топологию Решетка. Выберите число процессоров, равное девяти. Сделайте текущей задачей этого окна задачу матричного умножения.

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

3. Выберите алгоритм Кэннона матричного умножения и выполните вычислительный эксперимент. Пронаблюдайте различные маршруты передачи данных при выполнении алгоритмов. Сравните временные характеристики алгоритмов.

4. Измените число процессоров в топологии Решетка на шестнадцать. Последовательно выполните вычислительные 26 3. Открытие существующего графа.

Для загрузки графа из файла выберите пункт меню Файл и выполните команду Загрузить (или щелкните левой кнопкой мыши на иконке панели инструментов). В появившемся диалоговом окне выберите имя файла (файлы графов ПараЛаб имеют расширение.plg) и нажмите кнопку Открыть.

4. Сохранение графа.

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

5. Редактирование графа.

С графом, расположенным в рабочей области окна, можно производить следующие операции:

• Для того, чтобы добавить к графу одну или несколько новых вершин, выберите пункт меню Редактирование и выполните команду Рис. 10. Окно встроенного редактора графов Добавить вершину (или щелкните левой кнопкой мыши на иконке панели инструментов). При этом вид курсора изменится, над После выполнения команды Формирование графа на экране указателем появится символическое изображение вершины. Рабочая дисплея появляется новое окно (рис. 10), в рабочей области которого область окна представляет собой сетку. Щелкая левой кнопкой мыши отображается граф активного эксперимента. Если граф в эксперимент в различных клетках сетки, Вы можете добавлять в граф новые не был загружен, то рабочая область окна пуста.

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

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

выберите пункт меню Редактирование и выполните команду Добавить ребро (или щелкните левой кнопкой мыши на иконке 2. Создание нового графа.

панели инструментов). После этого курсор изменит форму, под Для создания нового пустого графа выберите пункт меню Файл и указателем появится изображение двух вершин, соединенных ребром.

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

измененный граф в файл.

Вес ребра определяется случайным образом. Если между первой и 28 второй вершинами до редактирования существовало ребро, то оно закрепления изменений щелкните мышкой в любой точке рабочей будет удалено. области или нажмите любую клавишу.

• Для того, чтобы переместить вершину графа, выберите пункт 8. Выход из режима редактирования.

меню Редактирование и выполните команду Переместить вершину Для загрузки текущего графа в активный эксперимент, нажмите (или щелкните левой кнопкой мыши на иконке панели кнопку ОК. Для выхода без сохранения изменений нажмите кнопку инструментов). После этого курсор изменит форму, примет вид, Отмена.

изображенный на кнопке панели инструментов. Выделите одну из вершин графа, щелкнув на ней левой кнопкой мыши. Цвет вершины изменится на темно-красный. Перемещайте курсор мыши по рабочей области окна – Вы увидите, что вершина перемещается вслед за 3.3.1. Алгоритм Прима поиска минимального охватывающего курсором. Щелкните на любой пустой клетке рабочей области, и дерева.

выделенная вершина переместится в эту точку.

Охватывающим деревом (или остовом) неориентированного графа G называется подграф графа G, который является деревом и • Для того, чтобы удалить вершину графа, выберите пункт T меню Редактирование и выполните команду Удалить вершину (или содержит все вершины из G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, тогда под минимально щелкните левой кнопкой мыши на иконке панели инструментов).

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

построения локальной сети персональных компьютеров с Для выхода из любого из режимов (Добавление вершины, прокладыванием наименьшего количества соединительных линий Удаление вершины, Перемещение вершины, Добавление ребра) связи.

щелкните левой кнопкой мыши на иконке панели инструментов.

Дадим краткое описание алгоритма решения поставленной задачи, известного под названием метода Прима (Prim). Алгоритм 6. Формирование графа при помощи случайного механизма.

начинает работу с произвольной вершины графа, выбираемого в качестве корня дерева, и в ходе последовательно выполняемых Граф можно задавать случайным образом. Для этого в редакторе, итераций расширяет конструируемое дерево до МОД. Распределение расположенном на панели инструментов, укажите число вершин данных между процессорами вычислительной системы должно графа, далее выберите пункт меню Редактирование и выполните обеспечивать независимость перечисленных операций алгоритма команду Случайное формирование.

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

вершиной информацией.

Цвет ребер графа имеет разную интенсивность. Чем темнее цвет, С учетом такого разделения данных итерация параллельного тем больше вес ребра. Для того, чтобы приблизительно определить вес варианта алгоритма Прима состоит в следующем:

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

30 • эта вершина включается в состав МОД.

4. Определение графических форм наблюдения за процессом 3.3.2. Алгоритм Дейкстры поиска кратчайших путей.

Задача поиска кратчайших путей на графе состоит в нахождении параллельных вычислений путей минимального веса от некоторой заданной вершины s до всех имеющихся вершин графа. Постановка подобной проблемы имеет Для наблюдения за процессом выполнения вычислительного важное практическое значение в различных приложениях, когда веса эксперимента по параллельному решению сложных вычислительно дуг означают время, стоимость, расстояние, затраты и т.п. трудоемких задач в рамках системы ПараЛаб предусмотрены различные формы графического представления результатов Возможный способ решения поставленной задачи, известный как выполняемых параллельных вычислений.

алгоритм Дейкстры, практически совпадает с методом Прима.

Различие состоит лишь в интерпретации и в правиле оценки расстояний. В алгоритме Дейкстры эти величины означают суммарный вес пути от начальной вершины до всех остальных вершин графа. Как результат, на каждой итерации алгоритма выбирается очередная вершина, расстояние от которой до корня дерева минимально, и происходит включение этой вершины в дерево кратчайших путей.

Задания и упражнения 1. Запустите систему ПараЛаб. В активном окне вычислительного эксперимента установите топологию Полный граф.

Текущей задачей этого окна сделайте задачу обработки графов.

2. Выполните команду Формирование графа пункта меню Задача. В появившемся редакторе графов сформируйте случайным образом граф с десятью вершинами.

3. Выполните вычислительный эксперимент по поиску минимального охватывающего дерева с помощью алгоритма Прима (выполните команду Метод пункта меню Задача, в появившемся Рис. 11. Вид окна вычислительного эксперимента диалоговом окне выберите метод Прима).

Для представления сведений о ходе выполнения эксперимента в 4. Проведите несколько экспериментов, изменяя количество рабочей области системы ПараЛаб для каждого эксперимента процессоров. Изучите зависимость временных характеристик выделяется прямоугольный участок экрана – окно вычислительного алгоритма Прима от количества процессоров.

эксперимента. В левой части окна выделена область “Выполнение 5. Проведите аналогичную последовательность экспериментов эксперимента”, где изображаются процессоры многопроцессорной для изучения временных характеристик метода Дейкстры.

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

данными между процессорами системы. В правой верхней части окна Если эксперимент состоит в изучении какого-либо параллельного отображается область с информацией о текущем состоянии объекта, алгоритма сортировки, то рядом с процессором изображается часть являющегося результатом выполняемого эксперимента. В зависимости сортируемого массива. Каждый элемент массива изображается от того, какой эксперимент выполняется, эта область носит название вертикальной линией. Высота и интенсивность цвета линии характеризуют величину элемента (чем выше и темнее линия, тем • “Текущее состояние массива” при выполнении алгоритма больше элемент). Если эксперимент заключается в изучении сортировки;

алгоритмов матричного умножения, то рядом с каждым процессором • “Результат умножения матриц” при выполнении матричного изображен силуэт матрицы, на котором цветом выделены части умножения;

исходных данных, располагаемых на процессоре (предполагаем, что • “Результат обработки графа” при выполнении алгоритмов на исходные матрицы A и B квадратные размерности nn). Синим цветом графах.

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

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

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

характеристики.

Дополнительно в отдельном окне могут быть более подробно • режим “Выделение каналов” - выделяется красным та линия визуально представлены вычисления, которые производит один из коммутации, по которой происходит обмен;

имеющегося набора процессор (задание режима высветки этого окна и выбор наблюдаемого процессора осуществляется пользователем • режим “Движение пакетов” - визуализация обмена при системы). помощи движущегося от одного процессора к другому конверта. Если изучаются параллельные алгоритмы матричного умножения, то на конверте изображается номер блока, который пересылается.

4.1. Область "Выполнение эксперимента" В этой области окна изображены процессоры многопроцессорной При выполнении алгоритмов на графах все итерации вычислительной системы, соединенные линиями коммутации в ту или параллельного алгоритма однотипны и число их велико (равно числу иную топологию. Процессоры в топологии пронумерованы. Для того вершин в графе). Для отображения всех итераций понадобится чтобы узнать номер процессора, достаточно навести на него указатель достаточно много времени. Поэтому в системе ПараЛаб реализована мыши. Вид указателя изменится и появится подсказка с номером возможность отображать не все итерации, а лишь некоторые.

процессора. Если при этом дважды щелкнуть левой клавишей мыши на изображении процессора, то появится окно “Демонстрация работы процессора”, где будет детально отображаться деятельность этого процессора.

Около каждого процессора схематически изображаются данные, 34 Нажмите ОК (Enter) для подтверждения выбора темпа Правила использования системы ПараЛаб демонстрации. Для возврата в основное меню системы ПараЛаб без сохранения изменений нажмите Отмена (Escape).

Изменение способа отображения пересылки данных.

3. Изменение шага визуализации.

1. Для задания способа отображения коммуникации процессоров выполните команду Пересылка данных пункта Для того чтобы в рабочей области системы ПараЛаб отображалась меню Графика. В появившемся списке выделите название не каждая итерация, а лишь некоторые из них, выполните команду желаемого способа отображения.

Шаг визуализации пункта меню Графика (команда доступна только в случае, когда текущей задачей активного окна вычислительного эксперимента является задача обработки графов). В появившемся диалоговом окне установите при помощи ползунка желаемую частоту отображения итераций. Для выбора шага визуализации нажмите OK (Enter), для возврата в основное меню системы ПараЛаб нажмите Отмена (Escape) Рис. 12. Выбор способа отображения пересылки данных 4. Настройка цветовой палитры.

Для изменения цветов, которые используются в системе ПараЛаб 2. Выбор темпа демонстрации.

для визуализации процесса решения задач, выполните команду Настройка цвета пункта меню Графика. В появившемся диалоговом Для выбора темпа демонстрации необходимо выполнить команду окне (рис. 14) Вы увидите прямоугольник с линейным перетеканием Темп Демонстрации пункта меню Графика. В появившемся более светлого цвета в более темный и квадрат, залитый цветом диалоговом окне (рис. 13) предоставляется возможность выбора выделения. При выполнении алгоритмов сортировки более светлый величины задержки между итерациями алгоритма и скорости (левый) цвет используется для отображения минимальных элементов движения пакетов (времени выделения канала) при отображении сортируемого массива, а более темный – для отображения коммуникации процессоров.

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

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

Рис. 13. Диалоговое окно выбора темпа демонстрации 36 располагаются, образуют результирующий массив. После выполнения сортировки блоки массива на каждом процессоре должны быть отсортированы и, кроме того, элементы, находящиеся на процессоре с меньшим номером, не должны превосходить элементов, находящихся на процессоре с большим номером.

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

Рис. 14. Диалоговое окно настройки цветовой палитры 4.3. Область «Результат умножения матриц» Чтобы изменить эти цвета, щелкните левой клавишей мыши на Эта область находится в правой верхней части окна и отображает кнопке, расположенной слева или справа под шкалой перетекания. В состояние матрицы – результата в процессе выполнения результате появится стандартное диалоговое окно выбора цвета параллельного алгоритма матричного умножения.

операционной системы Windows. В этом окне выберите цвет и Матрица C представляется разбитой на квадратные блоки. Каждый нажмите кнопку OK. Цвет будет изменен. Для того чтобы изменить процессор многопроцессорной вычислительной системы отвечает за цвет выделения, щелкните левой клавишей мыши на отображающем вычисление одного (алгоритмы Фокса и Кэннона) или нескольких этот цвет квадрате. При помощи стандартного диалогового окна (ленточный алгоритм) блоков результирующей матрицы С.

задайте необходимый цвет.

При выполнении ленточного алгоритма умножения темно-синим Для изменения цветовой палитры нажмите кнопку ОК (Enter) в цветом закрашиваются те блоки, которые уже вычислены к данному диалоговом окне “Настройка цвета”. Для возврата в основной режим моменту.

работы системы ПараЛаб нажмите Отмена (Escape).

Если же выполняется алгоритм Фокса или алгоритм Кэннона, то все блоки матрицы С вычисляются одновременно, ни один из блоков не может быть вычислен раньше, чем будут выполнены все итерации алгоритма. Поэтому в области “Результат умножения матриц” 4.2. Область «Текущее состояние массива» отображается динамика вычисления того блока результирующей матрицы, который расположен на активном процессоре (этот Эта область расположена в правой верхней части окна и процессор в области “Выполнение эксперимента” выделен синим отображает последовательность элементов сортируемого массива.

цветом). Вычисленные к этому моменту слагаемые написаны темно Каждый элемент, как и в области “Выполнение эксперимента”, синим цветом, вычисляемое на данной итерации – цветом выделения.

отображается вертикальной линией. Высота и интенсивность цвета линии дают представление о величине элемента: чем выше и темнее линия, тем больше элемент.

Все параллельные алгоритмы используют идею разделения исходного массива между процессорами. Блоки, выстроенные один за другим в порядке возрастания номеров процессоров, на которых они 38 Рис. 15. Область “Результат умножения матриц” при выполнении алгоритма Фокса 4.4. Область “Результат обработки графа” Эта область расположена в правой верхней части окна Рис. 16. Вид окна демонстрации работы процессора вычислительного эксперимента и отображает текущее состояние графа. Вершины графа имеют такое же взаимное расположение, как и Один из способов выбора процессора – выполнить команду в режиме редактирования графа. Дуги графа изображаются разными Наблюдение Вычислений пункта меню Графика. В появившемся цветами: чем темнее цвет, тем больший вес имеет дуга. диалоговом окне при помощи бегунка укажите номер процессора и нажмите ОК (Enter). Для возврата в основное меню системы и отказа В процессе выполнения алгоритмов на графах цветом выделения от выбора процессора нажмите Отмена (Escape).

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

Далее в появившемся окне “Демонстрация работы процессора” 4.5. Выбор процессора будет детально изображаться ход вычислений.

Для более детального наблюдения за процессом выполнения эксперимента в системе ПараЛаб предусмотрена возможность 4.6. Визуализация алгоритмов пузырьковой отображения вычислений одного из процессоров системы в отдельном сортировки и сортировки Шелла окне.

Согласно параллельным алгоритмам пузырьковой сортировки и сортировки Шелла, первоначально на каждом процессоре располагается неотсортированный блок исходного массива. Он отображается в первой строке окна “Демонстрация работы процессора”.

Далее на каждом процессоре происходит внутренняя сортировка полученного блока. Она может выполняться при помощи любого 40 алгоритма сортировки. В системе ПараЛаб при проведении 4.7. Визуализация быстрой сортировки экспериментов используется алгоритм быстрой сортировки. Во второй Согласно параллельному алгоритму быстрой сортировки, строке изображается блок массива после сортировки.

первоначально на процессоре располагается неотсортированный блок Далее выполняется алгоритм чет – нечетной перестановки блоков.

исходного массива. Он отображается в первой строке окна На каждой итерации этого алгоритма выбранный процессор “Демонстрация работы процессора”.

осуществляет операцию слияния двух упорядоченных массивов – На следующих итерациях обмениваются данными процессоры, своего и полученного от следующего или предыдущего (в зависимости соседние в структуре гиперкуба. В таком обмене принимают участие от четности номера итерации). Соответственно в окне “Демонстрация два процессора:

работы процессора” отображается:

• выбирается ведущий элемент;

• блок массива, который находился на процессоре перед началом итерации (изображается синим цветом);

• блоки процессоров, участвующих в обмене, разбиваются на две части: в первой части находятся элементы, меньшие чем ведущий, • блок, полученный от соседа (изображается желтым цветом);

во второй - большие значения;

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

наоборот, отсылает первую часть своего блока процессору с меньшим В последней строке изображен блок массива, который номером.

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

меньшие.

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

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

В последней строке изображается блок процессора после выполнения последней итерации алгоритма – локальной сортировки 2. Проведите вычислительный эксперимент с использованием блока.

алгоритма сортировки пузырьком. Затем – с использованием сортировки Шелла. Сравните порядок обменов данными между процессорами.

4.8. Визуализация ленточного алгоритма умножения матриц Согласно ленточному алгоритму умножения матриц, в каждый момент вычислений на процессоре располагается одна горизонтальная 42 полоса матрицы A и одна вертикальная полоса матрицы B. В окне умножения в отдельном окне “Демонстрация работы процессора” на каждой итерации изображаются силуэты матриц A и B. Темно-синим цветом выделены Алгоритм выполнен, если выполнено p операций умножения и те полосы матриц, которые в данный момент находятся на выбранном сложения матричных блоков.

процессоре (полоса матрицы A всегда одна и та же, полоса матрицы B получена на предыдущем шаге от процессора, следующего в структуре кольца).

При перемножении полос матриц получается один блок матрицы • Задания и упражнения С. Он отображен на сетке матрицы С (правая часть равенства) темно 1. В активном окне эксперимента выберите топологию Решетка, синим квадратом.

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

умножения при помощи алгоритма Кэннона.

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

пересылки данных, задайте медленный темп показа и проведите вычислительный эксперимент. Обратите внимание на изменение цвета слагаемых, которые отображаются в области “Результат умножения 4.9. Визуализация алгоритмов Фокса и Кэннона матриц”.

умножения матриц 3. Сделайте активным седьмой процессор системы. Включите Согласно алгоритмам Фокса и Кэннона, в каждый момент режим отображения вычислений этого процессора в отдельном окне.

выполнения вычислений на процессоре находится один блок матрицы Выполните эксперимент. Сравните, как отображаются итерации A и один блок матрицы B. Каждый процессор вычисляет один блок параллельного алгоритма в области “Результат умножения матриц” и в матрицы С.

окне “Демонстрация работы процессора”.

На каждой итерации алгоритма происходит перемножение блоков матриц A и B и прибавление результата такого умножения к результирующему блоку матрицы С.

В окне “Демонстрация работы процессора” изображены блоки матриц, расположенные на этом процессоре (рис 17, блоки (2)) и состояние результирующего блока (рис 17, блок (1)). Справа отображается номер итерации.

Рис. 17. Отображение блочных алгоритмов матричного 44 5.2. Просмотр итогов 5. Накопление и анализ результатов Для отображения итогов экспериментов в системе ПараЛаб существует окно, содержащее Таблицу итогов и Лист графиков.

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

левом верхнем и нижнем правом углу листа графиков. Можно Эти эксперименты могут быть выполнены на различных построить зависимости времени выполнения эксперимента и многопроцессорных вычислительных системах, разными методами, ускорения от объема исходных данных, количества процессоров, для различных исходных данных. Для возможности сравнения производительности процессора и характеристик сети. Выделяя результатов выполненных численных экспериментов система ПараЛаб различные строки таблицы, Вы можете просматривать графики, содержит различные средства для их накапливания и обеспечивает соответствующие различным экспериментам.

разнообразные способы представления этих данных в виде форм, удобных для проведения анализа.

Следует отметить, что при построении графиков для экспериментов, проведенных в режиме имитации, используются необходимые аналитические зависимости (см. раздел 8). Для экспериментов, проведенных на вычислительном кластере, 5.1. Общие результаты экспериментов используется набор полученных к данному моменту результатов реальных экспериментов.

Накопление итогов экспериментов производится системой ПараЛаб автоматически. О каждом проведенном эксперименте При выделении нескольких строк в таблице результатов на листе хранится исчерпывающая информация: дата и время проведения, графиков отображается несколько зависимостей. Цвет линии графика детальное описание вычислительной системы и решаемой задачи, соответствует тому цвету, которым выделена левая ячейка строки, по время, потребовавшееся для выполнения эксперимента. Следует которой построена эта зависимость.

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

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

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

При переходе к выполнению экспериментов, результаты которых При сохранении текущего эксперимента в файле происходит не могут быть сопоставлены с итогами ранее проведенных сохранение всех записанных результатов. вычислений, в системе ПараЛаб предусмотрена возможность очистить список итогов.

46 2. Выделение строки в таблице результатов.

Каждая строка таблицы представляет один выполненный эксперимент. Для выделения строки наведите указатель мыши на нужную строчку и нажмите левую клавишу. Также можно воспользоваться курсорными стрелками вверх и вниз (выделенной строкой станет соответственно предыдущая или следующая строка).

Если выделенная строчка одна, то на листе графиков отображается только зависимость, соответствующая выделенной строке.

3. Выделение нескольких строк в таблице результатов.

Чтобы выделить несколько подряд идущих строк в таблице итогов, нажмите Shift и выделите мышью первую и последнюю строчку желаемого диапазона. Для выделения нескольких строк, не образующих непрерывную последовательность, нажмите Ctrl и выделяйте строки в произвольном порядке. Для того, чтобы выделить несколько строк при помощи курсорных клавиш, нажмите Shift и перемещайтесь по таблице при помощи клавиш вверх и вниз. При выделении нескольких строк в таблице результатов на листе графиков отображается несколько зависимостей. Цвет линии графика соответствует тому цвету, которым выделена левая ячейка строки, по Рис. 18. Анализ результатов экспериментов которой построена эта зависимость.

Правила использования системы ПараЛаб 4. Восстановление эксперимента по записи в таблице итогов.

Как уже отмечалось выше, запись в таблице итогов содержит 1. Общие результаты.

исчерпывающую информацию о вычислительном эксперименте. Для восстановления эксперимента по записи необходимо выделить эту Для демонстрации накопленных результатов экспериментов запись одним из перечисленных способов, щелкнуть правой кнопкой следует выбрать пункт меню Результаты, выделить команду Итоги и мыши в области списка итогов и выполнить команду Восстановить выполнить одну из двух команд: Из активного окна или Из всех эксперимент появившегося контекстного меню. Эксперимент будет окон. При выполнении первой команды будут отображены восстановлен в активном окне.

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

экспериментов представлен на рис. 18. Это окно содержит таблицу Для печати списка итогов на печатающем устройстве щелкните результатов и лист графиков.

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

48 6. Удаление записи. 11. Печать листа графиков.

Для удаления выделенной записи выполните команду Удалить Для печати листа графиков на печатающем устройстве выполните контекстного меню списка итогов.

команду Печать контекстного меню.

7. Удаление результатов.

Для удаления накопленных результатов и перехода к построению Задания и упражнения новых оценок выполните команду Очистить список контекстного меню списка итогов. Выполните несколько экспериментов с одним и тем же методом умножения матриц, изменяя объем исходных данных и количество процессоров. Используя окно итогов экспериментов, проанализируйте 8. Изменение вида зависимости на листе графиков.

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

листе графиков, выберите нужные значения в списках, расположенных слева вверху и справа внизу от листа графиков. Нижний правый список позволяет выбрать аргумент зависимости, а левый верхний – 5.3. Журнал экспериментов функцию.

Для сохранения результатов решения конкретных сложных 9. Изменение масштаба на листе графиков.

вычислительных задач система ПараЛаб содержит специальную область памяти, называемую далее журналом экспериментов. Данные, Для того чтобы увеличить область листа графиков, выполните записываемые в журнал экспериментов, включают:

команду Увеличить масштаб контекстного меню листа графиков • характеристики вычислительной системы (топология, (при этом масштаб будет увеличен в 2 раза, отображаться будет количество процессоров, производительность процессора, время геометрический центр области) или выделите эту область: нажмите начальной подготовки данных, пропускная способность сети, метод левую клавишу мыши в левом верхнем углу интересующей области и, передачи данных);

не отпуская левую клавишу, переместите указатель в правый нижний • постановку задачи (размер исходных данных, метод решения);

угол области. Для возвращения к исходному масштабу щелкните • время выполнения эксперимента.

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

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

10. Копирование листа графиков в буфер обмена.

Правила использования системы ПараЛаб Для копирования графического изображения листа графиков в буфер обмена Windows выполните команду Копировать в буфер обмена контекстного меню.

50 1. Записать в журнал.

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

Для записи результатов последнего выполненного эксперимента • кнопка Помощь – для получения дополнительной справочной в журнал экспериментов выполните последовательно команды:

информации.

РезультатыЖурнал экспериментовЗаписать. Следует отметить, что повторная запись результатов одного и того же эксперимента не 3. Удаление данных.

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

следует выполнить последовательно команды: РезультатыЖурнал экспериментовОбнулить.

4. Режим Автозаписи.

Для автоматической записи результатов выполняемых экспериментов в журнал экспериментов следует выполнить последовательно команды: РезультатыЖурнал экспериментовАвтозапись (признаком фиксации данного режима является высветка метки перед командой Автозапись). Результаты экспериментов заносятся в журнал экспериментов в момент окончания решения задачи. Для отмены режима необходимо повторно выполнить команду Автозапись.

Рис. 19. Окно с табличной формой представления данных из Задания и упражнения журнала экспериментов Выполните следующие задания для освоения правил работы с журналом экспериментов:

2. Демонстрация журнала.

• установите режим Автозаписи и выполните несколько Для демонстрации журнала экспериментов выполните вычислительных экспериментов по изучению зависимости времени последовательно команды: РезультатЖурнал решения задачи сортировки при помощи метода Шелла от числа экспериментовПоказатьИз активного окна (или Из всех окон).

процессоров;

В окне показа журнала (см. рис. 19) предоставляется возможность • проанализируйте результаты экспериментов, записанных в выполнения следующих действий:

журнал;

выделите эксперимент, в котором были получены наилучшие • кнопка ОК – для завершения просмотра журнала (наихудшие) временные оценки, и рассмотрите топологию вычисли экспериментов;

тельной системы в таких экспериментах;

• кнопка Просмотр – для просмотра параметров эксперимента, • выполните печать журнала экспериментов.

соответствующего выделенной строке таблицы;

• кнопка Копировать – для записи данных (в текстовом формате) из журнала экспериментов в буфер обмена системы Windows;

52 6. Выполнение вычислительных экспериментов В рамках системы ПараЛаб допускаются разные схемы организации вычислений при проведении экспериментов по изучению и исследованию параллельных алгоритмов решения сложных вычислительных задач. Решение задач может происходить в режиме последовательного исполнения или в режиме разделения времени с возможностью одновременного наблюдения итераций алгоритмов во всех окнах вычислительных экспериментов. Проведение серийных экспериментов, требующих длительных вычислений, может происходить в автоматическом режиме с возможностью запоминания результатов решения для организации последующего анализа полученных данных. Выполнение экспериментов может осуществляться и в пошаговом режиме.

Рис. 20. Просмотр записи в журнале экспериментов 6.1. Последовательное выполнение экспериментов В общем случае цель проведения вычислительных экспериментов состоит в оценке эффективности параллельного метода при решении сложных вычислительных задач в зависимости от параметров многопроцессорной вычислительной системы и от объема исходных данных. Выполнение таких экспериментов может сводиться к многократному повторению этапов постановки и решения задач. При решении задач в рамках системы ПараЛаб процесс может быть приостановлен в любой момент времени (например, для смены графических форм наблюдения за процессом решения) и продолжен далее до получения результата. Результаты решения вычислительных задач могут быть записаны в журнал экспериментов и представлены в виде, удобном для проведения анализа.

Правила использования системы ПараЛаб 54 Проведение вычислительного эксперимента.

6.2. Выполнение экспериментов по шагам 1. Для выполнения вычислительного эксперимента выберите Для более детального анализа итераций параллельного алгоритма пункт меню Выполнение и выполните команду В активном в системе ПараЛаб предусмотрена возможность пошагового окне. Решение задачи осуществляется без останова до выполнения вычислительных экспериментов. В данном режиме после получения результата. В ходе выполнения эксперимента выполнения каждой итерации происходит приостановка основное меню системы заменяется на меню с командой параллельного алгоритма. Это дает исследователю возможность Остановить;

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

меню системы восстанавливается.

2. Приостановка решения.

Правила использования системы ПараЛаб Для приостановки процесса выполнения эксперимента следует 1. Пошаговый режим.

выполнить в строке меню команду Остановить (команда доступна только до момента завершения решения).

Для задания режима приостановки вычислительного эксперимента после выполнения каждой итерации следует выполнить 3. Продолжение решения.

команду Пошаговый режим пункта меню Выполнение. После выполнения этой команды основное меню системы ПараЛаб Для продолжения ранее приостановленного процесса выполнения заменяется на меню пошагового выполнения эксперимента с эксперимента следует выполнить команду Продолжить пункта меню командами:

Выполнение (команда может быть выполнена только в случае, если после приостановки процесса поиска не изменялись постановка задачи • команда Шаг - выполнить очередную итерацию поиска;

и параметры вычислительной системы;

при невозможности • команда Без Остановки - продолжить выполнение продолжения ранее приостановленного процесса выполнения эксперимента без остановки;

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

• команда Закрыть - приостановить выполнение эксперимента и вернуться к выполнению команд основного меню.

Задания и упражнения • 1. В активном окне вычислительного эксперимента установите 6.3. Выполнение нескольких экспериментов топологию Кольцо, число процессоров, равное десяти. Сделайте текущей задачей задачу сортировки с использованием пузырькового Последовательное выполнение экспериментов затрудняет алгоритма.

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

ПараЛаб позволяет демонстрировать на экране дисплея одновременно результаты всех сравниваемых экспериментов. Для этого экран 3. Измените темп демонстрации и способ отображения дисплея может разделяться на несколько прямоугольных областей пересылки данных.

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

пользователь системы ПараЛаб может создать новое окно для 56 выполнения нового эксперимента. При этом итоги экспериментов и 1. Создание окна.

журнал экспериментов формируются раздельно для каждого Для создания окна для проведения экспериментов следует имеющегося окна. При визуализации окна экспериментов могут выполнить команду Создать новый пункта меню Эксперимент.

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

выполняется последовательно во всех имеющихся окнах. Используя этот режим, исследователь может наблюдать за динамикой 2. Управление окнами.

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

принятыми в системе Windows способами (максимизация, минимизация, изменение размеров при помощи мыши). Для одновременного показа всех имеющихся окон без перекрытия можно использовать команду Показать все пункта меню Эксперимент;

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

3. Проведение экспериментов во всех окнах.

Для выполнения вычислительных экспериментов во всех имеющихся окнах в режиме разделения времени (т.е. при переходе к выполнению следующей итерации только после завершения текущей во всех имеющихся окнах) следует применить команду Во всех окнах пункта меню Выполнение. Управление процессом вычислений осуществляется так же, как и при использовании единственного окна Рис. 21. Пример демонстрации нескольких окон экспериментов (приостановка выполнения алгоритмов по команде Остановить, продолжение вычислений по команде Продолжить пункта меню Следует отметить, что итоги экспериментов, проведенных в Выполнение).

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

системы между окнами.

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

58 3. В обоих окнах установите режим автозаписи результатов в • сделать активным окно, задачу (систему) которого журнал экспериментов.

предполагается скопировать;

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

4. Выполните вычислительные эксперименты одновременно в обоих окнах;

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

Эксперимент, в появившемся диалоговом окне следует выбрать, производится ли запоминание задачи или вычислительной системы;

5. Получите сводную таблицу итогов экспериментов и объединенный журнал экспериментов. Сравните временные • сделать активным окно, в которое необходимо скопировать характеристики алгоритмов пузырьковой сортировки и сортировки задачу (систему);

Шелла.

• выполнить команду Взять образец пункта меню Эксперимент.

Если же одна задача (система) должна быть установлена во всех 6.4. Выполнение серии экспериментов имеющихся окнах, возможен иной – более быстрый – способ выполнения этой операции. Для этого следует сделать активным окно, ПараЛаб обеспечивает возможность автоматического (без участия задачу (систему) которого предполагается скопировать, и выполнить пользователя) выполнения длительных серий экспериментов, команду Копировать во все окна пункта меню Эксперимент.

требующих проведения длительных вычислений. При задании этого режима работы системы пользователь должен выбрать окно, в котором 5. Сравнение итогов экспериментов.

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

количество процессоров). Результаты экспериментов могут быть запомнены в списке итогов и журнале экспериментов, а в 6. Сравнение журналов экспериментов. последующем проанализированы.

Для того, чтобы одновременно просмотреть все данные, записанные в журналах экспериментов всех окон, выполните последовательность команд: РезультатыЖурнал Правила использования системы ПараЛаб экспериментовПоказатьИз всех окон.

1. Выполнить серию.

Переход в режим выполнения последовательности экспериментов Задания и упражнения осуществляется при помощи команды Выполнить Серию пункта 1. Откройте второе окно вычислительного эксперимента, меню Выполнение. При выполнении команды может быть задано установите режим показа окон без перекрытия.

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

установка автозаписи результатов экспериментов в журнал 60 экспериментов (Команда Автозапись пункта меню Журнал экспериментов в режиме удаленного доступа к вычислительному Экспериментов). кластеру. При выборе этого режима выполнения эксперимента необходимо поставить задачу и выбрать нужное количество процессоров для ее решения. После выполнения имитационных и реальных экспериментов пользователь ПараЛаб может сравнить результаты и оценить точность используемых в системе теоретических моделей времени выполнения параллельных алгоритмов. Результаты реальных экспериментов автоматически заносятся в таблицу итогов, кроме того, они могут быть запомнены в журнале экспериментов.

Рис. 22. Диалоговое окно задания параметров серии При выполнении серии экспериментов основное меню системы ПараЛаб заменяется на меню управления данным режимом вычислений, команды которого позволяют:

• команда Пуск - выполнить последовательность экспериментов;

Рис. 23. Окно для выполнения реального вычислительного эксперимента • команда Закрыть - приостановить выполнение данного режима и вернуться к выполнению команд основного меню;

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

то, что выполняется эксперимент в режиме удаленного доступа к кластеру, и указывается число процессоров. Режим пошагового При решении серии поставленных задач (после выполнения выполнения эксперимента недоступен.

команды Пуск) выполнение эксперимента может быть приостановлено в любой момент времени при помощи команды Остановить.

Правила использования системы ПараЛаб 6.5. Выполнение реальных вычислительных 1. Переход в режим реального выполнения эксперимента.

экспериментов Для перехода в режим выполнения реальных вычислительных Помимо выполнения экспериментов в режиме имитации, в экспериментов в режиме удаленного доступа к вычислительному системе ПараЛаб предусмотрена возможность проведения реальных кластеру выберите пункт меню Система и выделите мышью команду 62 Кластер. Подтверждением того, что данный режим активен, является значок слева от надписи. После выбора этого режима топология 7. Использование результатов вычислительной системы автоматически заменяется на топологию Полный граф, так как последняя соответствует топологии кластера.

экспериментов: запоминание, печать Постановка задачи осуществляется так же, как и при выполнении и перенос в другие программы экспериментов в режиме имитации.

2. Задание количества вычислительных узлов (процессоров).

7.1. Запоминание результатов Для выбора числа процессоров выполните команду Количество процессоров пункта меню Система. В появившемся диалоговом окне В любой момент результаты выполненных в активном окне при помощи бегунка задайте нужное число процессоров. Нажмите ОК вычислительных экспериментов могут быть сохранены в архиве (Enter) для подтверждения выбора или Отмена (Escape) для возврата в системы ПараЛаб. Данные, сохраняемые для окна проведения основное меню системы без изменений.

эксперимента, включают:

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

Рис. 24. Окно выбора количества вычислительных узлов Данные, сохраненные в архиве системы, в любой момент могут быть восстановлены из архива и, тем самым, пользователь может 3. Проведение реального эксперимента.

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

Для проведения реального вычислительного эксперимента Кроме того, в рамках системы ПараЛаб исследователю выполните команду В активном окне пункта меню Выполнение.

предоставляется возможность сохранения в архиве и чтения из архива сформированных графов специального вида (см. раздел 3).

Правила использования системы ПараЛаб 1. Запись данных.

Для сохранения результатов выполненных экспериментов следует выполнить команду Сохранить пункта меню Архив. При выполнении 64 записи в диалоговом окне Сохранить файл как следует задать имя Для печати результатов экспериментов могут быть использованы файла, в котором будут сохранены данные. Расширение имени файла также стандартные возможности печати системы Windows при может не указываться. Файлы с параметрами вычислительных помощи копирования содержимого экрана.

экспериментов имеют расширение.prl.

2. Чтение данных.

Правила использования системы ПараЛаб Для чтения параметров экспериментов, записанных ранее в архив системы ПараЛаб, следует выбрать пункт меню Архив и указать 1. Печать таблицы результатов экспериментов.

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

экспериментов (выполнить последовательность команд:

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

которых состоит в следующем:

1. Выполните какой-либо эксперимент и сохраните параметры 2. Печать графической формы листа графиков.

выполненного эксперимента в архиве системы.

Для печати листа графиков следует открыть окно представления 2. Завершите выполнение системы.

итогов экспериментов, вызвать контекстное меню листа графиков и 3. Выполните повторный запуск системы и загрузите выполнить команду Печать.

запомненные параметры эксперимента из архива.

3. Печать журнала экспериментов.

Для печати результатов, запомненных в журнале экспериментов 7.2. Печать результатов экспериментов активного окна, следует последовательно выполнить команды:

РезультатыЖурнал экспериментовПоказатьИз активного При выполнении экспериментов в системе ПараЛаб получаемые окна и в появившемся диалоговом окне Журнал экспериментов результаты могут быть напечатаны в виде разнообразных графических нажать кнопку Печать.

и табличных форм. Пользователь системы может напечатать:

• таблицы результатов, сформированные по набору 4. Печать всех журналов экспериментов.

накопленных итогов экспериментов;

Для печати результатов из всех имеющихся окон, запомненных в • таблицы данных, сохраненных в журнале экспериментов;

журналах экспериментов, следует последовательно выполнить • графические формы, являющиеся точными копиями команды: РезультатыЖурнал экспериментовПоказатьИз содержимого окон проведения экспериментов;

всех окон и в появившемся диалоговом окне Журнал экспериментов • графические формы листа графиков из формы представления нажать кнопку Печать.

итогов экспериментов;

• графические формы, представляющие окно редактора графов.

66 5. Печать окон экспериментов.

Для печати содержимого активного окна эксперимента следует Правила использования системы ПараЛаб выполнить команду Печать пункта меню Архив.

1. Копирование таблицы результатов.

6. Печать окна редактора графов.

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

вызвать контекстное меню, связанное с таблицей результатов, и выполнить команду Копировать в буфер обмена.

Задания и упражнения 2. Копирование журнала экспериментов.

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

в буфер обмена системы Windows откройте диалоговое окно, представляющее журнал экспериментов в табличной форме, и нажмите кнопку Копировать.

7.3. Копирование результатов в другие 3. Копирование окна системы ПараЛаб.

программы Для копирования графического представления окна системы При выполнении вычислительных экспериментов в системе ПараЛаб в буфер обмена системы Windows следует последовательно ПараЛаб получаемые результаты могут быть скопированы в буфер выполнить команды: АрхивКопировать в буфер обмена.

обмена системы Windows в текстовом и графическом форматах и могут, тем самым, быть перемещены в любые другие программы Задания и упражнения системы Windows для последующего анализа и обработки. В буфер обмена могут быть скопированы: Выполните вычислительные эксперименты, план проведения которых состоит в следующем:

• таблицы результатов, сформированные по итогам всех проведенных экспериментов (в текстовом формате);

1. Выполните несколько вычислительных экспериментов.

2. Скопируйте данные журнала экспериментов в буфер обмена.

• таблицы результатов, сформированные по данным из журнала экспериментов (в текстовом формате);

3. Запустите текстовый редактор Word и вставьте в текстовый документ результаты экспериментов из буфера.

• графическое представление окна вычислительного эксперимента системы ПараЛаб.

4. Запустите систему обработки электронных таблиц Excel и вставьте в таблицу результаты экспериментов из буфера.

Результаты экспериментов, скопированные в буфер обмена в Преобразуйте средствами системы Excel скопированные данные из текстовом формате, могут быть далее перенесены в текстовый текстового формата в числовую форму.

редактор Word или систему обработки электронных таблиц Excel.

Графическое представление окон экспериментов может быть далее 5. Скопируйте в системе ПараЛаб графическое представление использовано в графических редакторах типа Paint, Photoshop или окна эксперимента в буфер обмена.

Corel Draw.

68 6. Запустите графический редактор Paint и вставьте в рабочую область редактора содержимое буфера обмена.

8. Описание параллельных методов решения сложных вычислительных задач 8.1. Сортировка данных Общая схема параллельных вычислений при сортировке данных (см. раздел 3 пособия) состоит в разделении исходного упорядочиваемого набора на блоки и их распределения между процессорами, в ходе сортировки блоки пересылаются между процессорами и содержащиеся в них данные сравниваются между собой для упорядочения. Результирующий (отсортированный) набор, как правило, также разделен между процессорами;

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

В системе ПараЛаб в качестве методов упорядочения данных представлены пузырьковая сортировка, сортировка Шелла, быстрая сортировка.

8.1.1. Алгоритм пузырьковой сортировки Напомним кратко общую схему данного метода упорядочения данных [1]. Алгоритм основан на применении базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки:

// операция "сравнить и переставить" if ( a[i] > a[j] ) { temp = a[i];

a[i] = a[j];

a[j] = temp;

70 } в кольцо и элементы ai расположены на процессорах pi (i=1, 2,..., n).

Тогда сравнение пары значений ai и ai+1, 1 i < n, располагаемых На первой итерации алгоритма осуществляется последовательное сравнение всех соседних элементов;

в результате прохода по на процессорах Pi и Pi+1 соответственно, можно организовать упорядочиваемому набору данных в последнем (верхнем) элементе следующим образом:

оказывается максимальное значение ("всплывание пузырька");

далее - выполнить взаимообмен имеющихся на процессорах Pi и для продолжения сортировки этот уже упорядоченный элемент не рассматривается и действия алгоритма повторяются:

Pi+1 значений (с сохранением на этих процессорах исходных // пузырьковая сортировка элементов);

for ( i=1;

i

i++ ){ - сравнить на каждом процессоре Pi и Pi+1 получившиеся for ( j=0;

j

j++ ) <сравнить и переставить элементы (a[j],a[j+1])> одинаковые пары значений ( ai, ai+1 );

результаты сравнения } используются для разделения данных между процессорами – на одном процессоре (например, Pi ) остается меньший элемент, другой Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания: сравнение пар соседних элементов процессор (т.е. Pi+1 ) запоминает для дальней обработки большее происходит строго последовательно. Для организации параллельных значение пары вычислений обычно используется модификация алгоритма ai' = min(ai, ai+1), ai' = max(ai, ai+1).

пузырьковой сортировки – метод чет-нечетной перестановки [23].

+ Суть модификации состоит в том, что в алгоритм сортировки вводятся Рассмотренная параллельная схема может быть надлежащим два разных правила выполнения итераций метода – в зависимости от образом адаптирована и для случая p < n, когда количество четности или нечетности номера итерации сортировки для обработки процессоров является меньшим числа упорядочиваемых значений. В выбираются элементы с четными или нечетными индексами данной ситуации каждый процессор будет содержать уже не соответственно, сравнение выделяемых значений всегда единственное значение, а часть (блок размера n / p ) сортируемого осуществляется с их правыми соседними элементами, т.е. на всех нечетных итерациях сравниваются пары:

набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого (a1, a2 ), (a3, a4),…, (an-1, an ) (при четном n ), либо быстрого алгоритма (предварительная стадия параллельной на четных итерациях обрабатываются элементы сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров Pi и Pi+1 для совместного (a2, a3), (a4, a5),…, (an-2,an-1).

упорядочения содержимого блоков Ai и Ai+1 может быть После n -кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным. осуществлено следующим образом:

Параллельное обобщение этого алгоритма не вызывает - выполнить взаимообмен блоков между процессорами Pi и затруднений, так как сравнение элементов в парах происходит Pi+1 ;

независимо и может выполняться одновременно. Сначала рассмотрим схему вычислений, когда на каждый процессор приходится один - объединить блоки Ai и Ai+1 на каждом процессоре в один элемент исходного массива. Предположим, что процессоры соединены отсортированный блок двойного размера (при исходной 72 упорядоченности блоков Ai и Ai+1 процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

- разделить полученный двойной блок на две равные части и № и тип итерации Процессоры оставить одну из этих частей (например, с меньшими значениями 1 2 3 данных) на процессоре Pi, а другую часть (с большими значениями Исходные данные 2 3 3 8 5 6 1 соответственно) – на процессоре Pi+ 1 нечет 2 3 3 8 5 6 1 (1,2),(3.4) 2 3 3 8 1 4 5 [Ai Ai+1]сорт = Ai' Ai' : ai' Ai',ai' Ai' ai' ai' +1 +1 +1 + 2 чет 2 3 3 8 1 4 5.

(2,3) 2 3 1 3 4 8 5 Следует отметить, что сформированные в результате такой процедуры 3 нечет 2 3 1 3 4 8 5 блоки на процессорах Pi и Pi+1 совпадают по размеру с исходными (1,2),(3.4) 1 2 3 3 4 5 6 блоками Ai и Ai+1 и все значения, расположенные на процессоре Pi, 4 чет 1 2 3 3 4 5 6 (2,3) являются меньшими значений на процессоре Pi+1.

1 2 3 3 4 5 6 Рассмотренная процедура обычно именуется в литературе как Рис. 25. Пример сортировки данных параллельным операция "сравнить и разделить" (compare-split). Для пояснения методом чет-нечетной перестановки такого параллельного способа сортировки на рис. 25 приведен пример Коммуникационная трудоемкость алгоритма определяется в упорядочения данных при n = 8, p = 4 (т.е. блок значений на зависимости от метода передачи данных:

каждом процессоре содержит n / p = 2 элементов). В первом столбце • Метод передачи сообщений:

таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняется операция - время передачи данных "сравнить и разделить";

взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки n p показано состояние упорядочиваемого набора данных до и после Tпд = p tн +, R выполнения итерации.

Вычислительная трудоемкость алгоритма определяется - общее время выполнения алгоритма выражением:

1 n p Tp = 6(n / p)2 + 2n.

T = (6(n p) + 2n)+ ptн + ;

F R Первая часть выражения определяет сложность начальной сортировки блоков с использованием алгоритма пузырьковой сортировки. Вторая • Метод передачи пакетов:

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

74 алгоритма от размера сортируемого массива и от количества (n процессоров. Для одной и той же вычислительной системы проследите tн V p), Tпд = p + R (V -V0) последовательно за вычислениями, которые производят процессоры с четным и нечетным номером.

- общее время выполнения алгоритма 8.1.2. Алгоритм сортировки Шелла 1 V (n p) Параллельный алгоритм сортировки Шелла может быть получен T = (6(n p) + 2n)+ p tн + F R (V -V0 ) как обобщение метода параллельной пузырьковой сортировки.

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

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

Для алгоритма Шелла может быть предложен параллельный аналог метода, если топология коммуникационный сети имеет структуру N-мерного гиперкуба (т.е. количество процессоров равно практика p=2N). Выполнение сортировки в таком случае может быть разделено на два последовательных этапа. На первом этапе (N итераций) 30 теория осуществляется взаимодействие процессоров, являющихся соседними в структуре гиперкуба (но эти процессоры могут оказаться далекими при линейной нумерации;

для установления соответствия двух систем нумерации процессоров обычно используется код Грея). Второй этап состоит в реализации обычных итераций параллельного алгоритма 20000 50000 чет-нечетной перестановки. Итерации данного этапа выполняются до размер массива прекращения фактического изменения сортируемого набора и, тем самым, общее количество L таких итераций может быть различным - Рис. 26. Зависимость времени сортировки от размера массива от 2 до p. Трудоемкость параллельного варианта алгоритма Шелла определяется выражением:

Проведенные на реальной многопроцессорной вычислительной Tp = (n / p) log(n / p) + (2n / p) log p + L(2n / p), системе эксперименты доказывают справедливость теоретических временных оценок, приведенных выше. На графике представлены где вторая и третья части соотношения фиксируют вычислительную теоретическая и практическая зависимости времени сортировки сложность первого и второго этапов сортировки соответственно. Как массива от объема исходных данных при выполнении параллельного можно заметить, эффективность данного параллельного способа обобщения алгоритма пузырьковой сортировки.

сортировки оказывается лучше показателей обычного алгоритма чет нечетной перестановки при L

• Задания и упражнения Коммуникационная трудоемкость алгоритма:

Проведите вычислительные эксперименты с методом пузырьковой сортировки. Исследуйте зависимость временных характеристик • Метод передачи сообщений:

76 время сортировки размера таким образом, что между значениями разных блоков - время передачи данных обеспечивается отношение упорядоченности. На первой итерации n p метода осуществляется деление исходного набора данных на первые t Tпд = (N + L) +, н две части – для организации такого деления выбирается некоторый R ведущий элемент и все значения набора, меньшие ведущего элемента, переносятся в первый формируемый блок, все остальные значения - общее время выполнения алгоритма образуют второй блок набора. На второй итерации сортировки описанные правила применяются последовательно для обоих 1 n p t T = ((n p)log(n p)+ (N + L)2n p)+ (N + L) + сформированных блоков и т.д. После выполнения log(n) итераций н F R исходный массив данных оказывается упорядоченным (при ;

оптимальном выборе ведущих элементов).

Параллельное обобщение алгоритма быстрой сортировки наиболее • Метод передачи пакетов:

простым способом может быть получено для вычислительной системы с топологией в виде N-мерного гиперкуба (т.е. p=2N). Пусть, как и - время передачи данных ранее, исходный набор данных распределен между процессорами блоками одинакового размера n/p;

результирующее расположение V n p Tпд = (N + L)tн + блоков должно соответствовать нумерации процессоров гиперкуба.

V, R -V Возможный способ выполнения первой итерации параллельного метода при таких условиях может состоять в следующем:

- общее время выполнения алгоритма • выбрать каким-либо образом ведущий элемент и разослать его по всем процессорам системы;

1 V n p T = ((n p)log(n p)+ (N + L)2n p)+ (N + L)tн + • разделить на каждом процессоре имеющийся блок данных на V F R -V две части с использованием полученного ведущего элемента;

. • образовать пары процессоров, для которых битовое представление номеров отличается только в позиции N, и осуществить • Задания и упражнения взаимообмен данными между этими процессорами;

в результате таких пересылок данных на процессорах, для которых в битовом Убедитесь в том, что алгоритм сортировки Шелла может быть представлении номера бит позиции N равен 0, должны оказаться части выполнен только в том случае, когда топология вычислительной блоков со значениями, меньшими ведущего элемента;

процессоры с системы – гиперкуб. Пронаблюдайте за последовательностью обменов номерами, в которых бит N равен 1, должны собрать, соответственно, данными между процессорами. Проверьте на практике, что для все значения данных, превышающие значение ведущего элемента.

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

набор оказывается разделенным на две части, одна из которых (со значениями меньшими, чем значение ведущего элемента) 8.1.3. Алгоритм быстрой сортировки располагается на процессорах, в битовом представлении номеров которых бит N равен 0. Таких процессоров всего р/2 и, таким образом, Алгоритм быстрой сортировки [7] основывается на последова исходный N-мерный гиперкуб оказывается разделенным на два тельном разделении сортируемого набора данных на блоки меньшего 78 гиперкуба размерности (N-1). К этим подкубам, в свою очередь, может - время передачи данных быть параллельно применена описанная выше процедура. После N кратного повторения подобных итераций для завершения сортировки V n 2 p 1+ достаточно упорядочить блоки данных, получившиеся на каждом Tпд = N 2tн + V -V0, R отдельном процессоре вычислительной системы. Эффективность параллельного метода быстрой сортировки, как и в последовательном варианте, во многом зависит от успешности выбора значений ведущих - общее время выполнения алгоритма элементов. Определение общего правила для выбора этих значений является достаточно трудной задачей;

сложность такого выбора может 1 V n 2 p 1+ T = (N (2n p)+ (n p)log(n p))+ N 2tн + быть снижена, если выполнить упорядочение локальных блоков V F R -V процессоров перед началом сортировки и обеспечить однородное распределение сортируемых данных между процессорами.

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

0, Вычислительная сложность параллельного алгоритма быстрой сортировки определяется выражением:

0, 0, 2n n n Tp = N + log 0, теория p p p, практика 0, где первая часть определяет общую трудоемкость всех операций 0, выбора ведущего элемента и разделения блоков согласно этому 0, элементу, а вторая – трудоемкость локальной сортировки блоков на последней итерации алгоритма.

Коммуникационная трудоемкость, как и в предыдущих случаях, 20000 50000 зависит от выбранного метода передачи информации:

размер массива • Метод передачи сообщений:

- время передачи данных Рис. 27. Зависимость времени выполнения параллельного алгоритма быстрой сортировки от размера массива (n 2 p)+ 2t Tпд = N +, н Проведенные на реальной многопроцессорной вычислительной R системе эксперименты доказывают справедливость теоретических - общее время выполнения алгоритма временных оценок, приведенных выше. На графике представлены теоретическая и практическая зависимости времени сортировки 1 (n 2 p)+ 2t массива от объема исходных данных при выполнении параллельного T = (N (2n p)+ (n p)log(n p))+ N + н F R алгоритма быстрой сортировки на четырех процессорах.

;

• Метод передачи пакетов:

Задания и упражнения 80 время сортировки Проведите вычислительные эксперименты с алгоритмом быстрой должны быть изменены. В наиболее простом виде это может быть сортировки. Изучите зависимость времени и ускорения от объема обеспечено, например, при кольцевой топологии вычислительной сети исходных данных и от количества процессоров. Пронаблюдайте за (при числе процессоров равном количеству полос) – в этом случае вычислениями отдельно взятого процессора. Сопоставьте временные необходимое для матричного умножения изменение положения оценки алгоритма быстрой сортировки с оценками алгоритмов данных может быть обеспечено циклическим сдвигом полос матрицы сортировки пузырьком и сортировки Шелла. B по кольцу. После многократного выполнения описанных действий (количество необходимых повторений является равным числу процессоров) на каждом процессоре получается набор блоков, образующий горизонтальную полосу матрицы C.

8.2. Матричное умножение Рассмотренная схема вычислений позволяет определить Как уже отмечалось ранее в разделе 3 пособия, возможность параллельный алгоритм матричного умножения при ленточной схеме организации параллельных вычислений для матричного умножения разделения данных как итерационную процедуру, на каждом шаге обеспечивается независимостью расчетов для получения элементов которой происходит параллельное выполнение операции результирующей матрицы. В предельном случае (при наличии n перемножения полос и последующего циклического сдвига полос процессоров) все элементы матрицы C могут быть вычислены одной из матриц по кольцу.

параллельно, при меньшем количестве процессоров объем обрабатываемых данных на каждом из процессоров увеличивается и применяемые при этом способы разделения данных, в большинстве случаев, сводятся либо к ленточной, либо к блочной схемам представления матриц. В системе ПараЛаб представлены оба способа разделения данных и обеспечивается возможность проведения вычислительных экспериментов с параллельным алгоритмом умножения матриц при ленточной схеме разделения данных и двумя Рис. 28. Разбиение данных при выполнении ленточного алгоритма методами (алгоритмы Фокса и Кэннона) для блочно-представленных матриц.

Временные характеристики этого алгоритма:

8.2.1. Ленточный алгоритм умножения • Метод передачи сообщений:

матриц - время передачи данных При ленточной схеме разделения данных исходные матрицы разбиваются на горизонтальные (для матрицы A) и вертикальные (для 32 n p матрицы B) полосы (см. рис. 27). Получаемые полосы распределяются Tпд = (p -1)tн +, по процессорам, при этом на каждом из имеющегося набора R процессоров располагается только по одной полосе матриц A и B.

- общее время выполнения алгоритма Перемножение полос (а выполнение процессорами этой операции может быть выполнено параллельно) приводит к получению части (n3 p2)+ (p -1)tн + 32 n p блоков результирующей матрицы C. Для вычисления оставшихся T = p ;

блоков матрицы C сочетания полос матриц A и B на процессорах F R 82 Проведите вычислительные эксперименты с ленточным • Метод передачи пакетов:

алгоритмом умножения матриц. Наблюдайте за последовательностью - время передачи данных обмена данными между процессорами. Определите, на каких топологиях вычислительной системы, кроме кольца, возможна V n p реализация ленточного алгоритма матричного умножения. Исследуйте Tпд = (p -1)tн +, V зависимость времени выполнения алгоритма от количества R -V процессоров и от объема исходных данных. Оцените, какое максимальное ускорение можно получить при использовании этого - общее время выполнения алгоритма алгоритма. Определите, при каких параметрах вычислительной системы оно достигается.

(n3 p2)+ (p -1) tн + V n p T = p.

V F R - V 8.2.2. Алгоритм Фокса Для организации параллельных вычислений при блочном 1, представлении матриц предположим, что процессоры образуют 1, логическую прямоугольную решетку размером kk (обозначим через 1, pij процессор, располагаемый на пересечении i строки и j столбца теория решетки). Основные положения параллельного метода, известного как 0, алгоритм Фокса (Fox) [23], состоят в следующем:

практика 0, 0, • каждый из процессоров решетки отвечает за вычисление 0, одного блока матрицы C;

• в ходе вычислений на каждом из процессоров pij располагается 100*100 200*200 500* четыре матричных блока:

размер матрицы - блок Cij матрицы C, вычисляемый процессором;

Рис. 29. Зависимости времени выполнения ленточного алгоритма - блок Aij матрицы A, размещенный в процессоре перед умножения матриц от их размерности началом вычислений;

- блоки Aij’, Bij’ матриц A и B, получаемые процессором в ходе Проведенные на вычислительном кластере эксперименты выполнения вычислений.

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

зависимости времени умножения матриц от объема их размерности при выполнении ленточного алгоритма умножения на четырех • этап инициализации, на котором на каждый процессор pij процессорах. передаются блоки Aij, Bij и обнуляются блоки Cij на всех процессорах;

Задания и упражнения 84 время умножения, с • этап вычислений, на каждой итерации l, 1 l k, которого 1 итерация выполняется: 1) 2) 3) 1 2 1 2 1 - для каждой строки i, 1 i k, процессорной решетки Aij A11 A11 Aij A11 A11 Aij A11 A блок Aij процессора pij пересылается на все процессоры той же Bij B11 B12 Bij B11 B12 Bij B21 B строки i ;

индекс j, определяющий положение процессора pij в Cij 0 0 Cij A11B11 A11B12 Cij A11B11 A11B строке, вычисляется по соотношению Aij A22 A22 Aij A22 A22 Aij A22 A, j = (i + l -1) modk + Bij B21 B22 Bij B21 B22 Bij B11 B ( есть операция получения остатка от целого деления);

mod Cij 0 0 Cij A22B21 A22B22 Cij A22B21 A22B - полученные в результате пересылок блоки Aij, Bij каждого процессора pij перемножаются и прибавляются к блоку Cij :

2 итерация 1) 2) 3) Рис. 30. Состояние блоков на каждом процессоре в ходе выполнения 1 2 1 2 1 итераций этапа вычислений A12 A12 A12 A12 A12 A Aij Aij Aij B21 B22 B21 B22 B21 B Bij Bij Bij Cij = Cij + Aij Bij ;

A11B Cij A11B11 Cij A11B11 + A11B12 + Cij A11B11 + A11B12 + - блоки Bij каждого процессора pij пересылаются A12B21 A12B22 A12B21 A12B процессорам pij, являющимися соседями сверху в столбцах A21 A Aij A21 A A21 A21 Aij Aij процессорной решетки (блоки процессоров из первой строки решетки B11 B Bij B11 B B11 B12 Bij Bij пересылаются процессорам последней строки решетки).

Cij A22B21 A22B Cij A22B21 + A22 B22 + Cij A22B21 + A22 B22 + A21B12 A21B11 A21B A21B Для пояснения приведенных правил параллельного метода на рис.

30 приведено состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений (для процессорной решетки 3 ).

2 2 V (n k) (n k) T = k + 2 (k -1)+.

F R V -V Время выполнения этого алгоритма:

• Метод передачи сообщений:

3 (n k) tн 8 (k -1)(n k) T = k + 2 +, F R • Метод передачи пакетов:

86 вычислительной системы. Начальное расположение блоков в 2,5 алгоритме Кэннона подбирается таким образом, чтобы располагаемые блоки на процессорах могли бы быть перемножены без каких-либо 2 дополнительных передач данных между процессорами. При этом подобное распределение блоков может быть организовано таким 1, образом, что перемещение блоков между процессорами в ходе теория вычислений может осуществляться с использованием более простых практика коммуникационных операций.

С учетом высказанных замечаний этап инициализации алгоритма 0, Кэннона включает выполнение следующих операций передач данных:

• на каждый процессор pij передаются блоки Aij, Bij;

100*100 200*200 500* • для каждой строки i процессорной решетки блоки матрицы A сдвигаются на (i-1) позиций влево;

размер матрицы • для каждого столбца j процессорной решетки блоки матрицы B сдвигаются на (j-1) позиций вверх.

Рис. 31. Зависимость времени перемножения квадратных матриц от их размерности при выполнении алгоритма Фокса Для демонстрации получаемого распределения данных на рис. показан пример расположения блоков для процессорной решетки Эксперименты, проведенные на реальной многопроцессорной размера 4х4.

вычислительной системе, доказывают справедливость приведенных выше теоретических временных оценок. На графике (рис. 31) представлены теоретическая и практическая зависимости времени A11, B11 A12, B22 A13, B33 A14, B перемножения квадратных матриц nn от размерности этих матриц n A22, B21 A23, B32 A24, B43 A21, B при выполнении Алгоритма Фокса на четырех процессорах.

A33, B31 A34, B42 A31, B13 A32, B A44, B41 A41, B12 A42, B23 A43, B Задания и упражнения Рис. 32. Начальное распределение блоков в алгоритме Кэннона Проведите несколько вычислительных экспериментов с для процессорной решетки 4х использованием алгоритма Фокса умножения матриц. Убедитесь в том, что полученные на практике зависимости времени и ускорения от В ходе вычислений на каждой итерации алгоритма Кэннона каждый параметров вычислительной системы и задачи удовлетворяют блок матрицы A сдвигается на один процессор влево по решетке, а теоретическим зависимостям, приведенным выше.

каждый блок матрицы B - на один процессор вверх.

Временные характеристики алгоритма:

8.2.3. Алгоритм Кэннона • Метод передачи сообщений:

Отличие алгоритма Кэннона от представленного в предыдущем разделе метода Фокса состоит в изменении схемы начального распределения блоков перемножаемых матриц между процессорами 88 время умножения, с инцидентности A=(aij), 1 i, j n, ненулевые значения элементов (n p) n, которой соответствуют дугам графа T = p + 2tн +( p -1)pn + + (2 p -1) tн p R F R w(vi,v ), если (vi,v ) R, j j • Метод передачи пакетов: ai j = 0, если i = j,, иначе 3 (n p) (n p) V.

Использование матрицы инцидентности позволяет применять T = p +(2 p +1)tн + p -1+ F R -V V также при реализации вычислительных процедур для графов матричные алгоритмы обработки данных. Более широко способы представления графов рассмотрены, например, в [8].

Задания и упражнения В системе ПараЛаб в качестве примеров задач обработки графов Проведите несколько вычислительных экспериментов с рассматриваются проблемы нахождения минимального использованием алгоритма Кэннона для умножения матриц. Сравните охватывающего дерева и поиска минимальных путей, решаемые при порядок обмена данными между процессорами при выполнении помощи алгоритмов Прима и Дейкстры.

алгоритма Фокса и алгоритма Кэннона. Исследуйте, какой из алгоритмов матричного умножения обладает наилучшими временными характеристиками.

8.3.1. Алгоритм Прима нахождения минимального охватывающего дерева 8.3. Обработка графов Охватывающим деревом (или остовом) неориентированного графа G называется подграф Т графа G, который является деревом и Для описания графов известны различные способы задания. Пусть содержит все вершины из G. Определив вес подграфа для взвешенного G есть граф графа как сумму весов входящих в подграф дуг, тогда под минимально G = (V, R), охватывающим деревом (МОД) Т будем понимать охватывающее дерево минимального веса. Содержательная интерпретация задачи для которого набор вершин vi, 1 i n, задается множеством V, а нахождения МОД может состоять, например, в практическом примере список дуг графа построения локальной сети персональных компьютеров с rj = (vs,vt ), 1 j k, прокладыванием наименьшего количества соединительных линий j j связи.

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

При малом количестве дуг в графе (т.е. k<

5 - включение выбранной вершины t в VT.

После выполнения n -1 итераций метода МОД будет сформировано;

вес этого дерева может быть получен при помощи выражения n Рис. 33. Ненаправленный взвешенный граф и его минимальное WT =.

di охватывающее дерево i= Дадим краткое описание алгоритма решения поставленной задачи, Трудоемкость нахождения МОД характеризуется квадратичной известного под названием метода Прима (Prim). Алгоритм начинает зависимостью от числа вершин графа G работу с произвольной вершины графа, выбираемого в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет T1 ~ n2.

конструируемое дерево до МОД. Пусть VT есть множество вершин, На рис. 34 представлен процесс нахождения МОД при помощи уже включенных алгоритмом в МОД, а величины di, 1 i n, алгоритма Прима. В левом столбце изображается текущее состояние характеризуют дуги минимальной длины от вершин, еще не графа;

жирными линиями выделены те ребра графа, которые уже включенных в дерево, до множества VT, т.е.

включены в состав МОД. В правом столбце отображается массив величин d[i] (эти величины вычисляются заново на каждой итерации) i VT di = min{w(i,u) :u VT,(i,u) R} и матрица инцидентности графа G (не изменяется в ходе выполнения вычислений).

(если для какой либо вершины i VT не существует ни одной дуги в VT, значение di устанавливается в ). При начале работы алгоритма выбирается корневая вершина МОД s и полагается VT = {s}, ds = 0.

Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:

- определяются значения величин di для всех вершин, еще не включенные в состав МОД;

- выбирается вершина t графа G, имеющая дугу минимального веса до множества VT 92 Окончательное минимальное охватывающее дерево Исходный граф. В качестве корня МОД выбираем вершину B A d[] a b c d e f 1 0 2 1 1 A d[] a b c d e f 1 1 0 5 1 a 0 1 3 B 1 2 C F b 1 0 5 1 a 0 1 3 c 3 5 0 2 5 B C b 1 0 5 1 1 F d 1 2 0 c 3 5 0 2 e 1 4 0 1 5 d 1 2 0 E D f 2 5 e 1 4 0 f 2 5 E D Рис. 34. Алгоритм Прима поиска минимального охватывающего дере ва. Минимальное охватывающее дерево имеет корень в вершине B.

Значение переменных после того, как выбрано первое ребро Оценим возможности для параллельного выполнения A d[] a b c d e f рассмотренного алгоритма нахождения минимально охватывающего дерева. Итерации метода должны выполняться последовательно и, тем 1 0 2 1 самым, не могут быть распараллелены. С другой стороны, выполняе 1 мые на каждой итерации алгоритма действия являются независимыми a 0 1 3 B и могут реализовываться одновременно. Так, например, определение C b 1 0 5 1 F c 3 5 0 2 1 величин di может осуществляться для каждой вершины графа в 1 5 d 1 2 0 отдельности, нахождение дуги минимального веса может быть e 1 4 0 реализовано по каскадной схеме и т.д.

f 2 5 E D Распределение данных между процессорами вычислительной системы должно обеспечивать независимость перечисленных операций алгоритма Прима. В частности, это может быть обеспечено, Значение переменных после того, как выбрано второе ребро если каждая вершина графа располагается на процессоре вместе со A d[] a b c d e f всей связанной с вершиной информацией. Соблюдение данного 1 0 2 1 4 принципа приводит к тому, что при равномерной загрузке каждый 1 процессор Pj, 1 j p, будет содержать набор вершин a 0 1 3 B C F b 1 0 5 1 1 Vj = {vi +1,vi +2,...,vi +k}, ij = k( j -1), k = n / p, c 3 5 0 2 j j j 1 d 1 2 0 e 1 4 0 соответствующий этому набору блок из k величин di, 1 i n, и E D f 2 5 94 вертикальную полосу матрицы инцидентности графа G из k V T = tн + ;

соседних столбцов, а также общую часть набора Vj и формируемого в R процессе вычислений множества вершин VT.

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

С учетом такого разделения данных итерация параллельного варианта алгоритма Прима состоит в следующем:

Получение МОД обеспечивается при выполнении (n -1) итерации алгоритма Прима;

как результат, общая трудоемкость метода • определяются значения величин di для всех вершин, еще не определяется соотношением:

включенных в состав МОД;

данные вычисления выполняются • Метод передачи сообщений:

независимо на каждом процессоре в отдельности;

трудоемкость такой операции ограничивается сверху величиной 1 n2 n(n - 2) + (n -1) + t T = +, 1 n н - T = ;

F p p R F p • Метод передачи пакетов:

(на первой итерации алгоритма необходим перебор всех вершин, что 1 n 1 n2 n(n - 2) + (n -1) + V t требует вычислений порядка T = );

T = +.

н F p F p p R • выбирается вершина t графа G, имеющая дугу Задания и упражнения минимального веса до множества VT ;

для выбора такой вершины Проведите последовательность вычислительных экспериментов с необходимо осуществить поиск минимума в наборах величин di, алгоритмом Прима поиска минимального охватывающего дерева. При имеющихся на каждом из процессоров (количество параллельных помощи встроенного редактора графов задавайте различные виды графов (дерево, цикл, граф, сформированный при помощи случайного операций n / p ), и выполнить сборку полученных значений.

механизма) и наблюдайте за процессом построения МОД. Изучите Длительность такой операции передачи данных на полном графе зависимости временных характеристик выполнения алгоритма от равна:

параметров задачи и вычислительной системы.

- при пересылке сообщений:

T = tн + ;

8.3.2. Алгоритм Дейкстры поиска R кратчайших путей - при пересылке пакетов:

Pages:     || 2 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.