Алгоритм Дейкстры поиска кратчайших путей

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

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

Задания и упражнения

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

Алгоритм Гаусса

Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейный уравнений при помощи последовательного исключения неизвестных (при помощи эквивалентных преобразований) приводится к верхнему треугольному виду. На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д.

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

Для выполнения прямого хода метода Гаусса необходимо осуществить (n-1) итерацию по исключению неизвестных для преобразования матрицы коэффициентов A к верхнему треугольному виду.

Выполнение итерации i, 0i<n-1, прямого хода метода Гаусса включает ряд последовательных действий. Процессор, на котором расположена строка i матрицы, должен разослать ее и соответствующий элемент вектора b всем процессорам, которые содержат строки с номерами k, k>i. Получив ведущую строку, процессоры выполняют вычитание строк, обеспечивая тем самым исключение соответствующей неизвестной xi.

При выполнении обратного хода метода Гаусса процессоры выполняют необходимые вычисления для нахождения значения неизвестных. Как только какой-либо процессор определяет значение своей переменной xi, это значение должно быть разослано всем процессорам, которые содержат строки с номерами k, k<i. Далее процессоры подставляют полученное значение новой неизвестной и выполняют корректировку значений для элементов вектора b.

Задания и упражнения

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

Алгоритм Прима поиска минимального охватывающего дерева

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

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

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

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

Блочные алгоритмы Фокса и Кэннона

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

каждый из процессоров решетки отвечает за вычисление одного блока матрицы C;в ходе вычислений на каждом из процессоров располагается по одному блоку исходных матриц A и В;при выполнении итераций алгоритмов блоки матрицы А последовательно сдвигаются вдоль строк процессорной решетки, а блоки матрицы B — вдоль столбцов решетки;в результате вычислений на каждом из процессоров получается блок матрицы С, при этом общее количество итераций алгоритма равно (где р – число процессоров).

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

Задания и упражнения

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

Быстрая сортировка

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

Задания и упражнения

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

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

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

Краткий обзор лекции

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

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

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

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

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

Ленточный алгоритм

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

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

Задания и упражнения

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

Матричное умножение

Задача умножения матрицы на матрицу определяется соотношениями:

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

Основу возможности параллельных вычислений для матричного умножения составляет независимость расчетов для получения элементов сij результирующей матрицы C. Тем самым, все элементы матрицы C могут быть вычислены параллельно при наличии n2

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

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

где каждый блок Cij матрицы C определяется в соответствии с выражением:

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

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

Накопление и анализ результатов экспериментов

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

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

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

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

Область "Результат обработки графа"

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

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

Область "Результат решения системы уравнений"

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

Область "Результат умножения матриц"

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

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

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

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

Рис. 12.15.  Область "Результат умножения матриц" при выполнении алгоритма Фокса

Область "Результат умножения матрицы на вектор"

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

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

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

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

Область "Текущее состояние массива"

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

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

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

Область "Выполнение эксперимента"

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

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

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

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

Правила использования системы ПараЛаб

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

Рис. 12.12.  Выбор способа отображения пересылки данных

2. Выбор темпа демонстрации. Для выбора темпа демонстрации необходимо выполнить команду Темп демонстрации пункта меню Графика. В появившемся диалоговом окне (рис. 12.13) предоставляется возможность выбора величины задержки между итерациями алгоритма и скорости движения пакетов (времени цветового выделения канала) при отображении коммуникации процессоров.

Рис. 12.13.  Диалоговое окно выбора темпа демонстрации

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

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

Рис. 12.14.  Диалоговое окно настройки цветовой палитры

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

Для изменения цветовой палитры нажмите кнопку ОК (Enter) в диалоговом окне "Настройка цвета". Для возврата в основной режим работы системы ПараЛаб нажмите Отмена

(Escape).

Обработка графов

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

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

Правила использования системы ПараЛаб

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

Рис. 12.10.  Окно встроенного редактора графов

После выполнения команды Формирование графа на экране дисплея появляется новое окно (рис. 12.10), в рабочей области которого отображается граф активного эксперимента. Если граф в эксперимент не был загружен, то рабочая область окна пуста.

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

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

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

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

5. Редактирование графа. С графом, расположенным в рабочей области окна, можно производить различные операции.

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

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


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

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

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

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

8. Выход из режима редактирования. Для загрузки текущего графа в активный эксперимент нажмите кнопку ОК. Для выхода без сохранения изменений нажмите кнопку Отмена.

Общая характеристика системы

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

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

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

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

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

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

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

Демонстрационный пример

Для выполнения примера, имеющегося в комплекте поставки системы:

выберите пункт меню Содержание и выполните команду Загрузить;выберите строку first.prl в списке имен файлов и нажмите кнопку Открыть;выберите пункт меню Выполнение и выполните команду В активном окне.

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

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


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

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

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

Рис. 12.1.  Окно вычислительного эксперимента

Ленточный индикатор "Эксперимент" отображает текущую стадию выполнения алгоритма. В строках "Общие затраты времени" и "Затраты на передачу данных" представлены временные характеристики алгоритма.

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

Обзор литературы

Дополнительная информация по моделированию и анализу параллельных вычислений может быть получена, например, в [[2], [22]], полезная информация содержится также в [[51], [63]].

Подробное рассмотрение параллельных алгоритмов, реализованных в системе ПараЛаб, выполнено в [[26], [51], [63]], а также в [[3]].

Впервые модель Хокни параллельных вычислений была изложена в работе [[46]].

Систематическое изложение (на момент издания работы) вопросов моделирования и анализа параллельных вычислений приводится в [[77]].

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

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

Рис. 12.11.  Вид окна вычислительного эксперимента

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

"Текущее состояние массива" при выполнении алгоритма сортировки;"Результат умножения матриц" при выполнении матричного умножения;"Результат обработки графа" при выполнении алгоритмов на графах.

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

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

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

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

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

Правила использования системы ПараЛаб

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

Задания и упражнения

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

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

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

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

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

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

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

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

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

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

Правила использования системы ПараЛаб

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

Рис. 12.7.  Выбор задачи

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

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

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

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

Просмотр результатов

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

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

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

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

Рис. 12.17.  Анализ результатов экспериментов

Правила использования системы ПараЛаб

Общие результаты. Для демонстрации накопленных результатов экспериментов следует выбрать пункт меню Результаты, выделить команду Показать и выполнить одну из двух команд: Из активного окна или Из всех окон. При выполнении первой команды будут отображены результаты, накопленные в активном окне вычислительного эксперимента. При выполнении второй команды – результаты из всех открытых окон экспериментов. Вид окна с результатами экспериментов представлен на рис. 12.17. Это окно содержит таблицу результатов и лист графиков.Выделение строки в таблице результатов. Каждая строка таблицы представляет один выполненный эксперимент. Для выделения строки наведите указатель мыши на нужную строчку и нажмите левую кнопку мыши.
Также можно воспользоваться курсорными стрелками вверх и вниз (выделенной строкой станет соответственно предыдущая или следующая строка). Если выделенная строчка одна, то на листе графиков отображается только зависимость, соответствующая выделенной строке.Выделение нескольких строк в таблице результатов. Чтобы выделить несколько подряд идущих строк в таблице итогов, нажмите Shift и выделите мышью первую и последнюю строчку желаемого диапазона. Для выделения нескольких строк, не образующих непрерывную последовательность, нажмите Ctrl и выделяйте строки в произвольном порядке. Для того чтобы выделить несколько строк при помощи курсорных клавиш, нажмите Shift и перемещайтесь по таблице при помощи клавиш вверх и вниз. При выделении нескольких строк в таблице результатов на листе графиков отображается несколько зависимостей. Восстановление эксперимента по записи в таблице итогов. Как уже отмечалось выше, запись в таблице итогов содержит исчерпывающую информацию о вычислительном эксперименте. Для восстановления эксперимента по записи необходимо выделить эту запись одним из перечисленных способов, щелкнуть правой кнопкой мыши в области списка итогов и выполнить команду Восстановить эксперимент появившегося контекстного меню. Эксперимент будет восстановлен в активном окне.Удаление записи. Для удаления выделенной записи выполните команду Удалить контекстного меню списка итогов.Изменение вида зависимости на листе графиков. Для того чтобы изменить вид зависимости, изображенной на листе графиков, выберите нужные значения в списках, расположенных слева вверху и справа внизу от листа графиков. Нижний правый список позволяет выбрать аргумент зависимости, а левый верхний – вид зависимости.

Задания и упражнения

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

Пузырьковая сортировка

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

(a1,a2),(a3,a4),...,(an–1,an).

Если пара не упорядочена, то ее элементы переставляются. На четной итерации упорядочиваются пары

(a2,a3),(a4,a5),...,(an–2,an–1).

После n-кратного повторения подобных итераций массив оказывается отсортированным. Более подробная информация о параллельном варианте алгоритма приводится в лекции 9.

Задания и упражнения

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

систем линейных уравнений

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

Линейное уравнение с n неизвестными x0, x1, ..., xn-1 может быть определено при помощи выражения

a0x0+a1x1+...+an-1xn-1=b,

где величины a0, a1, ..., an-1 и b представляют собой постоянные значения.

Множество n линейных уравнений

a0,0x0 + a0,1x1 + ... + a0,n-1xn-1 = b0

a1,0x0 + a1,1x1 + ... + a1,n-1xn-1 = b1

. . . an-1,0x0 + an-1,1x1 + ... + an-1,n-1xn-1 = bn-1

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

Ax=b,

где A=(ai,j) есть вещественная матрица размера n?n, а векторы b и x состоят из n элементов.

Под задачей решения системы линейных уравнений для заданных матрицы А и вектора b понимается нахождение значения вектора неизвестных x, при котором выполняются все уравнения системы.

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

Сортировка данных

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

S={a1,a2,...,an}

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

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

T1~n2.

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

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

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

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

Сортировка Шелла

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

Задания и упражнения

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

Умножение матрицы на вектор

В результате умножения матрицы А размерности m?n и вектора b, состоящего из n элементов, получается вектор c размера m, каждый i-й элемент которого есть результат скалярного умножения i-й строки матрицы А (обозначим эту строчку ai) и вектора b:

Тем самым получение результирующего вектора c предполагает повторение m однотипных операций по умножению строк матрицы A и вектора b. Каждая такая операция включает умножение элементов строки матрицы и вектора b (n операций) и последующее суммирование полученных произведений (n-1 операций). Общее количество необходимых скалярных операций есть величина

T1=m·(2n-1).

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

Наиболее общие и широко используемые способы разделения матриц состоят в разбиении данных на полосы (по вертикали или горизонтали) или на прямоугольные фрагменты (блоки).

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

Умножение матрицы на вектор при блочном разделении данных

Рассмотрим теперь параллельный алгоритм умножения матрицы на вектор, который основан на ином способе разделения данных – на разбиении матрицы на прямоугольные фрагменты (блоки). При таком способе разделения данных исходная матрица A представляется в виде набора прямоугольных блоков. Вектор b также должен быть разделен на блоки. Блоки матрицы и блоки вектора распределены между процессорами вычислительной системы. Логическая (виртуальная) топология вычислительной системы в данном случае имеет вид прямоугольной двумерной решетки. Размеры процессорной решетки соответствуют количеству прямоугольных блоков, на которые разбита матрица A. На процессоре pi,j, находящемся на пересечении i-й строки и j-го столбца процессорной решетки, располагается блок Ai,j матрицы A и блок bj вектора b.

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

Задания и упражнения

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

Умножение матрицы на вектор при разделении данных по столбцам

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

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

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

Задания и упражнения

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

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

Программная система Параллельная Лаборатория (сокращенное наименование – ПараЛаб) обеспечивает возможность проведения вычислительных экспериментов с целью изучения и исследования параллельных алгоритмов решения сложных вычислительных задач. Система может быть использована для организации лабораторного практикума по различным учебным курсам в области параллельного программирования, в рамках которого обеспечивается возможность:
моделирования многопроцессорных вычислительных систем с различной топологией сети передачи данных;получения визуального представления о вычислительных процессах и операциях передачи данных, происходящих при параллельном решении разных вычислительных задач;построения оценок эффективности изучаемых методов параллельных вычислений.
Проведение такого практикума может быть организовано на "обычных" однопроцессорных компьютерах, работающих под управлением операционных систем MS Windows 2000 или MS Windows XP (режим многозадачной имитации параллельных вычислений). Кроме режима имитации, в системе ПараЛаб может быть обеспечен удаленный доступ к многопроцессорной вычислительной системе для выполнения экспериментов в режиме "настоящих" параллельных вычислений для сопоставления результатов имитации и реальных расчетов.
В целом система ПараЛаб представляет собой интегрированную среду для изучения и исследования параллельных алгоритмов решения сложных вычислительных задач. Широкий набор имеющихся средств визуализации процесса выполнения эксперимента и анализа полученных результатов позволяет изучить эффективность использования тех или иных алгоритмов на разных вычислительных системах, сделать выводы о масштабируемости алгоритмов и определить возможное ускорение процесса параллельных вычислений.
Реализуемые системой ПараЛаб процессы изучения и исследований ориентированы на активное усвоение основных теоретических положений и способствуют формированию у обучаемых собственных представлений о моделях и методах параллельных вычислений путем наблюдения, сравнения и сопоставления широкого набора различных визуальных графических форм, демонстрируемых в ходе выполнения вычислительного эксперимента.
Основной сферой использования системы ПараЛаб является учебное применение студентами и преподавателями вузов для исследования и изучения параллельных алгоритмов решения сложных вычислительных задач в рамках лабораторного практикума по различным учебным курсам в области параллельного программирования. Система ПараЛаб может применяться также и при проведении научных исследований для оценки эффективности параллельных вычислений.
Пользователи, начинающие знакомиться с проблематикой параллельных вычислений, найдут систему ПараЛаб полезной для освоения методов параллельного программирования, опытные вычислители могут использовать систему для оценки эффективности новых разрабатываемых параллельных алгоритмов.

Выбор процессора

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

Рис. 12.16.  Вид окна демонстрации работы процессора

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

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

Выбор топологии сети

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

полный граф (completely-connected graph или clique) – система, в которой между любой парой процессоров существует прямая линия связи; как результат, данная топология обеспечивает минимальные затраты при передаче данных, однако является сложно реализуемой при большом количестве процессоров;линейка (linear array или farm) – система, в которой каждый процессор имеет линии связи только с двумя соседними (с предыдущим и последующим) процессорами; такая схема является, с одной стороны, просто реализуемой, с другой стороны, соответствует структуре передачи данных при решении многих вычислительных задач (например, при организации конвейерных вычислений);кольцо (ring) – данная топология получается из линейки процессоров соединением первого и последнего процессоров линейки;решетка (mesh) – система, в которой граф линий связи образует прямоугольную двумерную сетку; подобная топология может быть достаточно просто реализована и, кроме того, может эффективно использоваться при параллельном выполнении многих численных алгоритмов (например, при реализации методов блочного умножения матриц);гиперкуб (hypercube) – данная топология представляет частный случай структуры N-мерной решетки, когда по каждой размерности сетки имеется только два процессора (т.е. гиперкуб содержит 2N

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

Правила использования системы ПараЛаб

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

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

Рис. 12.2.  Диалоговое окно для выбора топологии

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

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

Правила использования системы ПараЛаб

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

команда Шаг — выполнить очередную итерацию поиска;команда Без остановки — продолжить выполнение эксперимента без остановки;команда Закрыть — приостановить эксперимент и вернуться к выполнению команд основного меню.

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

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

Рис. 12.18.  Пример демонстрации нескольких окон экспериментов

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

Правила использования системы ПараЛаб

Создание окна. Для создания окна для проведения экспериментов следует выполнить команду Создать новый

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

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

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

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

Задания и упражнения

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

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

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

Рис. 12.20.  Окно для выполнения реального вычислительного эксперимента

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

Правила использования системы ПараЛаб

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

пункта меню Выполнение.

Выполнение серии экспериментов

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

Правила использования системы ПараЛаб

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

Рис. 12.19.  Диалоговое окно задания параметров серии

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

команда Пуск — выполнить последовательность экспериментов;команда Закрыть — приостановить выполнение данного режима и вернуться к выполнению команд основного меню;команда Справка — получить дополнительную справочную информацию.

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

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

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

Задание характеристик сети

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

латентность (tн) — время начальной подготовки, которое характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т.п.;пропускная способность сети (R) – определяется как максимальный объем данных, который может быть передан за некоторую единицу времени по одному каналу передачи данных. Данная характеристика измеряется, например, количеством переданных бит в секунду.

К числу реализованных в системе ПараЛаб методов передачи данных относятся два следующих широко известных способа коммуникации (см. [[51]]). Первый из них ориентирован на передачу сообщений (МПС) как неделимых (атомарных) блоков информации (store-and-forward routing или SFR). При таком подходе процессор, содержащий исходное сообщение, готовит весь объем данных для передачи, определяет транзитный процессор, через который данные могут быть доставлены целевому процессору, и запускает операцию пересылки данных. Процессор, которому направлено сообщение, в первую очередь осуществляет прием полностью всех пересылаемых данных и только затем приступает к пересылке принятого сообщения далее по маршруту. Время пересылки данных T для метода передачи сообщения размером m по маршруту длиной l определяется выражением:

T=(tн+(m/R))·l.

Второй способ коммуникации основывается на представлении пересылаемых сообщений в виде блоков информации меньшего размера (пакетов), в результате чего передача данных может быть сведена к передаче пакетов (МПП). При таком методе коммуникации (cut- through routing или CTR) транзитный процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Количество передаваемых при этом пакетов равно

где V есть размер пакета, а величина V0 определяет объем служебных данных, передаваемых в каждом пакете (заголовок пакета). Как результат, время передачи сообщения в этом случае составит
(скобки обозначают операцию приведения к целому с избытком).
Сравнивая полученные выражения, можно заметить, что в случае, когда длина маршрута больше единицы, метод передачи пакетов приводит к более быстрой пересылке данных; кроме того, данный подход снижает потребность в памяти для хранения пересылаемых данных для организации приема-передачи сообщений, а для передачи пакетов могут использоваться одновременно разные коммуникационные каналы.
Правила использования системы ПараЛаб
1. Определение характеристик коммуникационной среды. Для определения характеристик сети выполните команду Характеристики сети пункта меню Система. В открывшемся диалоговом окне (рис. 12.5) при помощи бегунков можно задать время начальной подготовки данных (латентность) в микросекундах и пропускную способность каналов сети (Мбит/с). Для подтверждения выбора нажмите кнопку ОК. Для возврата в основное меню системы ПараЛаб без изменения этих параметров нажмите кнопку Отмена.

Рис. 12.5.  Диалоговое окно для задания характеристик сети
2. Определение метода передачи данных. Для определения метода передачи данных, который будет использоваться при проведении вычислительного эксперимента и при построении временных характеристик, необходимо выполнить команду Метод передачи данных
пункта меню Система. В открывшемся диалоговом окне (рис. 12.6) следует щелкнуть левой клавишей мыши в области радиокнопки, которая соответствует желаемому методу передачи данных. Если выбран метод передачи пакетов, при помощи бегунков возможно задать длину пакета и длину заголовка пакета в байтах. Для подтверждения выбора метода передачи данных и его параметров нажмите кнопку ОК.

Рис. 12.6.  Диалоговое окно для задания метода передачи данных
3. Завершение работы системы. Для завершения работы системы ПараЛаб следует выполнить команду Завершить (пункт меню Архив).

Задание количества процессоров

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

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

Правила использования системы ПараЛаб

1. Задание количества процессоров. Для выбора числа процессоров необходимо выполнить команду Количество Процессоров

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

Рис. 12.3.  Диалоговое окно для задания числа процессоров

Нажмите кнопку ОК для подтверждения выбора или кнопку Отмена

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

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

Рис. 12.4.  Диалоговое окно для задания производительности процессора

Запоминание результатов

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

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

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

Кроме того, в рамках системы ПараЛаб исследователю предоставляется возможность сохранения в архиве и чтения из архива сформированных графов (см. п. 12.4.5).

Правила использования системы ПараЛаб

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

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

Задания и упражнения

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

Выполните какой-либо эксперимент и сохраните параметры выполненного эксперимента в архиве системы.Завершите выполнение системы.Выполните повторный запуск системы и загрузите запомненные параметры эксперимента из архива.

---

---