WWW.DISSERS.RU

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

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

Pages:     | 1 ||

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

-- [ Страница 2 ] --

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

минимального веса до множества VT ;

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

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

вспомогательных величин di, 1 i n. В алгоритме Дейкстры эти Длительность такой операции передачи данных на полном графе величины означают суммарный вес пути от начальной вершины до равна:

всех остальных вершин графа. Как результат, после выбора очередной - при пересылке сообщений:

вершины t графа для включения в множество выбранных вершин VT, значения величин di, 1 i n, пересчитываются в соответствии с T = tн +, новым правилом:

R i VT di = min{di,dt + w(t,i)}.

- при пересылке пакетов:

V С учетом измененного правила пересчета величин di, 1 i n, T = tн + ;

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

кратчайших путей всем процессорам.

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

выполнении (n -1) итерации алгоритма Дейкстры;

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

включенных в состав дерева кратчайших путей;

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

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

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

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

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

н 1 n F p p R T = ;

F p 98 9. Использование системы ПараЛаб в 3, 3 учебном процессе 2, теория Основной сферой использования системы ПараЛаб является практика учебное применение студентами и преподавателями вузов для 1, исследований и изучения параллельных алгоритмов решения сложных вычислительных задач в рамках лабораторного практикума по 0, различным учебным курсам в области параллельного программирования. Система ПараЛаб может использоваться также и 50 100 при проведении научных исследований для оценки эффективности количество вершин параллельных вычислений.

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

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

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

процессорах от количества вершин в графе.

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

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

использованием алгоритма Дейкстры поиска кратчайших путей.

• Проведение экспериментов в режиме имитации вычислений;

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

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

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

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

оценка времени решения задач в зависимости от размерности задачи и количества процессоров;

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

100 врем • Проведение экспериментов в режиме реальных параллельных вычислений;

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

удаленный доступ к многопроцессорной вычислительной системе (кластеру);

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

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

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

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

• наглядную демонстрацию средствами цветной дисплейной графики сложных понятий и процессов;

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

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

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

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

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

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

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

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

10. Тематика предлагаемых учебных • изменение темпа демонстрации;

занятий • изменение способа отображения обмена данными;

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

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

отдельном окне.

Задание 4. Изучение параллельных методов решения задачи 10.1 Общее знакомство с возможностями матричного умножения.

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

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

управления при помощи манипулятора мышь. Способы получения справочной информации.

Задание 5. Изучение параллельных методов решения задач обработки графов.

Задание 2. Освоение способов формирования вычислительной системы.

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

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

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

10.3. Сравнение результатов имитационных 10.2. Изучение параллельных методов решения экспериментов с результатами реальных сложных вычислительных задач экспериментов Задание 3. Изучение параллельных методов решения задачи сортировки. Задание 6. Выполнение реальных экспериментов.

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

характеристик и количества итераций с пузырьковым методом и Задание 7. Сравнение результатов реальных и имитационных методом Шелла.

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

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

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

• Начало работы, • Основной режим работы, • Режим выполнения эксперимента, • Режим пошагового выполнения эксперимента, • Режим выполнения серии экспериментов.

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

106 • Загрузить Начало работы Чтение из архива системы запомненного ранее пакета заданий по решению задач при помощи параллельных алгоритмов. Переход к основному Выполнить Закрыть меню.

В активном окне новый все окна • Завершить Во всех окнах эксперимент Завершение работы системы.

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

• О программе Остановить Получение общей информации о системе.

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

Закрыть • Создать новый Выполнить серию Создание нового окна эксперимента.

• Загрузить Команда чтения данных из архива системы.

Режим выполнения • Сохранить серии Закрыть Команды записи данных в архив системы.

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

Ниже следует описание наборов (меню) команд для каждого • Настройка принтера режима работы системы.

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

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

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

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

108 новки задачи.

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

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

Команда, которая указывает, что эксперимент • Матричное умножение будет проводиться в режиме эмуляции.

Если этот пункт меню активен, текущей • Кластер задачей в активном окне является задача Команда, которая указывает, что эксперимент матричного умножения.

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

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

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

момент времени активным может быть только один.

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

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

Выбор параметров задачи (для сортировки – • Количество процессоров выбор объема исходных данных).

Выбор количества процессоров в рамках • Формирование графа выбранной топологии.

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

вычислительную систему, обладают одинаковым • Метод быстродействием).

Выбор метода решения задачи из числа • Характеристики сети реализованных в системе.

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

Выбор метода передачи данных и задание его параметров. • Настройка цвета Выбор цветов для отображения данных и цвета Задача выделения процессора.

Пункт меню содержит команды для поста 110 эксперимента.

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

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

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

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

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

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

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

эксперимента.

Записать • Во всех окнах Запись результатов последнего выполненного Одновременное решение задач во всех эксперимента в журнал экспериментов.

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

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

• Выполнить серию Автозапись Переход к режиму выполнения серии.

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

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

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

Получение списка разделов справочной информации, имеющейся в системе.

Эксперимент • О программе Пункт меню содержит команды для создания и Получение общей информации о системе.

управления окнами в рабочей области системы.

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

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

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

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

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

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

Справка • Закрыть все Получение справочной информации о правилах Закрытие всех окон рабочей области системы.

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

Переход к начальному меню.

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

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

системы в качестве установок эксперимента в Закрыть активном окне.

Завершение выполнения серии и переход к основному • Копировать во все окна режиму работы.

114 Справка Получение справочной информации о правилах ЛИТЕРАТУРА выполнения серии экспериментов.

1. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород: ННГУ им. Н.И. Лобачевского, 2001.

2. Богачев К.Ю. Основы параллельного программирования. - М.:

БИНОМ. Лаборатория знаний, 2003.

3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.:

БХВ-Петербург, 2002.

4. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем — СПб.: БХВ Петербург, 2002.

5. Березин И.С., Жидков И.П. Методы вычислений. - М.: Наука, 1966.

6. Дейтел Г. Введение в операционные системы. Т.1.- М.: Мир, 1987.

7. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. - М.: Мир, 1981.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНТО, 1999.

9. Корнеев В.В.. Параллельные вычислительные системы. - М.:

Нолидж, 1999.

10. Корнеев В.В. Параллельное программирование в MPI. Москва Ижевск: Институт компьютерных исследований, 2003.

11. П.Тихонов А.Н., Самарский А.А. Уравнения математической физики. -М.:Наука, 1977.

12. Хамахер К., Вранешич З., Заки С. Организация ЭВМ. - СПб: Питер, 2003.

13. Шоу А. Логическое проектирование операционных систем. - М.:

Мир, 1981.

14. Andrews G.R. Foundations of Multithreading, Parallel and Distributed Programming. Addison-Wesley, 2000 (русский перевод Эндрюс Г.Р.

Основы многопоточного, параллельного и распределенного программирования. - М.: Издательский дом "Вильяме", 2003) 15. Barker, M. (Ed.) (2000). Cluster Computing Whitepaper http://www.dcs.port.ac.uk/~mab/tfcc/WhitePaper/.

16. Braeunnl Т. Parallel Programming. An Introduction.- Prentice Hall, 1996.

116 17. Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., McDonald Информационные ресурсы сети Интернет J. Parallel Programming in OpenMP. - Morgan Kaufinann Publishers, 2000 33. Информационно-аналитические материалы по параллельным 18. Dimitri P. Bertsekas, John N. Tsitsiklis. Parallel and Distributed вычислениям (http://www.parallel.ru) Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, 34. Информационные материалы Центра компьютерного моделиро New Jersey, 1989. вания Нижегородского университета им. Н.И.Лобачевского 19. Fox G.C. et al. Solving Problems on Concurrent Processors. - Prentice (http://www.software.unn.ac.ru/ccam) Hall, Englewood Cliffs, NJ, 1988. 35. Информационные материалы рабочей группы IEEE по кластерным 20. Geist G.A., Beguelin A., Dongarra J., Jiang W., Manchek В., Sunderam вычислениям (http://www.ieeetfcc.org) V. PVM: Parallel Virtual Machine - A User's Guide and Tutorial for 36. Introduction to Parallel Computing (Teaching Course) Network Parallel Computing. MIT Press, 1994. (http://www.ece.nwu.edu/~choudhar/C58/) 21. Group W, Lusk E, Skjellum A. Using MPI. Portable Parallel 37. Foster I. Designing and Building Parallel Programs. — Addison Programming with the Message-Passing Interface. - MIT Press, Wesley, 1994.(http://www.mcs.anl.gov/dbpp) 1994.(htp://www.mcs.anl.gov/mpi/index.html) 22. Hockney R. W., Jesshope C.R. Parallel Computers 2. Architecture, Programming and Algorithms. - Adam Hilger, Bristol and Philadelphia, 1988. (Русский перевод 1 издания: Р.Xокни, К.Джессхоуп.

Параллельные ЭВМ. Архитектура, программирование и алгоритмы.

- М.: Радио и связь, 1986) 23. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc., 24. Miller R., Boxer L. A Unified Approach to Sequential and Parallel Algorithms. Prentice Hall, Upper Saddle River, NJ. 2000.

25. Pacheco, S. P. Parallel programming with MPI. Morgan Kaufmann Publishers, San Francisco. 1997.

26. Parallel and Distributed Computing Handbook. / Ed. A.Y. Zomaya. McGraw-Hill, 1996.

27. Pfister, G. P. In Search of Clusters. Prentice Hall PTR, Upper Saddle River, NJ 1995. (2nd edn., 1998).

28. Quinn M. J. Designing Efficient Algorithms for Parallel Computers. - McGraw-Hill, 1987. 29.Rajkumar Buyya. High Performance Cluster Computing. Volume l: Architectures and Systems. Volume 2:

Programming and Applications. Prentice Hall PTR, Prentice-Hall Inc., 1999. 30.Roosta, S.H. Parallel Processing and Parallel Algorithms:

Theory and Computation. Springer-Verlag, NY. 2000.

31. Xu, Z., Hwang, K. Scalable Parallel Computing Technology, Architecture, Programming. McGraw-Hill, Boston. 1998.

32. Wilkinson В., Allen M. Parallel programming. - Prentice Hall, 1999.

118 Графические формы наблюдение вычислений Предметный указатель область А Выполнение эксперимента Алгоритм Результат обработки графа матричного умножения Результат умножения матриц Фокса 25, Текущее состояние массива Кэннона 25, отображение пересылки данных ленточный 24, последовательный Ж обработки графов Журнал экспериментов Дейкстры поиска кратчайших путей (параллельный) 92 использование См. Правила использования системы Дейкстры поиска кратчайших путей (последовательный) З Прима поиска минимального охватывающего дерева Задача (параллельный) исходные данные Прима поиска минимального охватывающего матричного умножения дерева (последовательный) сортировки метод решения быстрой (параллельный) обработки графов быстрой (последовательный) постановка Шелла сортировки пузырьком (параллельный) К Кластер 6, пузырьком (последовательный) Л В Латентность коммуникационной среды Визуализация алгоритма Фокса М алгоритма Кэннона Матрица инцидентности быстрой сортировки Минимальное охватывающее дерево ленточного алгоритма матричного умножения Метод пузырьковой сортировки 40 передачи данных сортировки Шелла 40 передачи пакетов Вычислительный эксперимент См. Эксперимент, вычислительный передачи сообщений решения сложной вычислительной задачи Г 120 Многопроцессорная вычислительная система 9 удаление данных количество процессоров 11 завершение работы системы запоминание результатов метод передачи данных запись данных параметры коммуникационной среды чтение данных топология запуск системы копирование в другие программы О Окно копирование журнала экспериментов проведения вычислительного эксперимента копирование окна системы ПараЛаб активное копирование таблицы результатов наблюдения вычислений копирование параметров задачи между окнами П системы между окнами Параметры задача задачи определение метода решения задачи вычислительной системы определение параметров задачи Правила использования системы окна визуализация создание окна выбор темпа демонстрации управление окнами изменение способа отображения пересылки данных печать изменение шага визуализации всех журналов экспериментов настройка цветовой палитры графической формы листа графиков графы журнала экспериментов открытие существующего графа окна редактора графов Переход в режим редактирования графа окон экспериментов Редактирование веса ребра графа таблицы результатов экспериментов Редактирование графа результаты экспериментов Создание нового графа восстановление эксперимента по записи в таблице итогов Сохранение графа выделение нескольких строк в таблице результатов Формирование графа при помощи случайного механизма выделение строки в таблице результатов журнал экспериментов изменение вида зависимости на листе графиков демонстрация журнала изменение масштаба на листе графиков запись в журнал копирование листа графиков в буфер обмена режим автозаписи общие результаты 122 печать листа графиков 48 Решение задачи печать таблицы итогов 48 временные оценки 3, удаление записи С система Система ПараЛаб задание количества процессоров возможности определение метода передачи данных использование в учебном процессе определение производительности процессора назначение определение характеристик коммуникационной среды области применения сравнение план проведения учебных занятий журналов экспериментов итогов экспериментов Т эксперимент Топология вычислительной системы имитационный пошаговый режим Э приостановка решения Эксперимент, вычислительный выполнение серии экспериментов проведение вычислительного эксперимента одновременное выполнение нескольких экспериментов проведение экспериментов во всех окнах последовательное выполнение продолжение решения пошаговое выполнение реальный задание количества вычислительных узлов (процессоров) переход в режим реального выполнения эксперимента проведение реального эксперимента Производительность процессора Пропускная способность сети Р Результаты экспериментов демонстрация таблицы результатов запоминание в журнале экспериментов наблюдение в процессе решения 7, общие перенос в другие программы печать 124 Задания и упражнения.................. Содержание 3.3. Обработка графов................................ Правила использования системы ПараЛаб Введение.........................................

1. Переход в режим редактирования графа... 1. Общая характеристика системы.......................

2. Создание нового графа.................. 2. Формирование модели вычислительной системы.........

3. Открытие существующего графа......... 2.1. Выбор топологии сети............................

4. Сохранение графа...................... Правила использования системы ПараЛаб 5. Редактирование графа................... 1. Запуск системы....................

6. Формирование графа при помощи случай- 2. Выбор топологии вычислительной ного механизма........................ системы..................................

7. Редактирование веса ребра графа......... 2.2. Задание количества процессоров....................

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

охватывающего дерева................................ 2. Определение производительности 3.3.2. Алгоритм Дейкстры поиска кратчайших путей процессора........................

Задания и упражнения......................... 2.3. Задание характеристик сети.......................

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

Правила использования системы ПараЛаб 2. Определение метода передачи данных 1. Изменение способа отображения пере- 3. Завершение работы системы..........

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

3. Изменение шага визуализации........... Правила использования системы ПараЛаб 4. Настройка цветовой палитры............. 1. Выбор задачи..........................

4.2. Область "Текущее состояние массива"............... 2. Определение параметров задачи..........

4.3. Область "Результат умножения матриц".............. 3. Определение метода решения задачи......

4.4. Область "Результат обработки графа"................ 3.1. Сортировка данных...............................

4.5. Выбор процессора............................... 3.1.1. Пузырьковая сортировка....................

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

сортировки Шелла........................................ 3.1.2. Сортировка Шелла........................

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

4.7. Визуализация быстрой сортировки.................. 3.1.3. Быстрая сортировка........................

4.8. Визуализация ленточного алгоритма умножения Задания и упражнения..................

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

4.9. Визуализация алгоритмов Фокса и Кэннона умножения 3.2.1. Ленточный алгоритм.......................

матриц................................................. Задания и упражнения..................

Задания и упражнения......................... 3.2.2. Алгоритмы Фокса и Кэннона................

5. Накопление и анализ результатов экспериментов......... 126 5.1. Общие результаты экспериментов................... 44 1. Создание окна......................... 5.2. Просмотр итогов................................. 44 2. Управление окнами..................... Правила использования системы ПараЛаб 3. Проведение экспериментов во всех окнах.. 1. Общие результаты...................... 46 4. Копирование параметров задачи и вычис- 2. Выделение строки в таблице результатов.. 46 лительной системы между окнами........ 3. Выделение нескольких строк в таблице 5. Сравнение итогов экспериментов......... результатов........................... 47 6. Сравнение журналов экспериментов...... 4. Восстановление эксперимента по записи в Задания и упражнения......................... таблице итогов......................... 47 6.4. Выполнение серии экспериментов.................. 5. Печать таблицы итогов................. 47 Правила использования системы ПараЛаб 6. Удаление записи....................... 47 1. Выполнить серию...................... 7. Удаление результатов.................. 47 6.5. Выполнение реальных вычислительных экспериментов 8. Изменение вида зависимости на листе Правила использования системы ПараЛаб графиков.............................. 47 1. Переход в режим реального выполнения 9. Изменение масштаба на листе графиков... 48 эксперимента.......................... 10. Копирование листа графиков в буфер 2. Задание количества вычислительных узлов обмена............................... 48 (процессоров)......................... 11. Печать листа графиков.................. 48 3. Проведение реального эксперимента...... Задания и упражнения......................... 48 7. Использование результатов экспериментов: запоминание, 5.3. Журнал экспериментов............................ 48 печать и перенос в другие программы................... Правила использования системы ПараЛаб 7.1. Запоминание результатов.......................... 1. Записать в журнал...................... 49 Правила использования системы ПараЛаб 2. Демонстрация журнала.................. 49 1. Запись данных......................... 3. Удаление данных...................... 50 2. Чтение данных......................... 4. Режим автозаписи...................... 50 Задания и упражнения......................... Задания и упражнения......................... 50 7.2. Печать результатов экспериментов.................. 6. Выполнение вычислительных экспериментов............ 52 Правила использования системы ПараЛаб 6.1. Последовательное выполнение экспериментов........ 52 1. Печать таблицы результатов эксперимен- Правила использования системы ПараЛаб тов................................... 1. Проведение вычислительного 2. Печать графической формы листа графиков эксперимента.......................... 52 3. Печать журнала экспериментов........... 2. Приостановка решения.................. 53 4. Печать всех журналов экспериментов..... 3. Продолжение решения.................. 53 5. Печать окон экспериментов.............. Задания и упражнения......................... 53 6. Печать окна редактора графов............ 6.2. Выполнение экспериментов по шагам............... 53 Задания и упражнения......................... Правила использования системы ПараЛаб 7.3. Копирование результатов в другие программы........ 1. Пошаговый режим..................... 54 Правила использования системы ПараЛаб 6.3. Выполнение нескольких экспериментов.............. 54 1. Копирование таблицы результатов........ Правила использования системы ПараЛаб 2. Копирование журнала экспериментов..... 128 3. Копирование окна системы ПараЛаб Задания и упражнения........................ 8. Описание параллельных методов решения сложных вычислительных задач................................ 8.1. Сортировка данных............................... 8.1.1. Алгоритм пузырьковой сортировки........... Задания и упражнения..................... 8.1.2. Алгоритм сортировки Шелла................ Задания и упражнения..................... 8.1.3. Алгоритм быстрой сортировки............... Задания и упражнения..................... 8.2. Матричное умножение............................ 8.2.1. Ленточный алгоритм умножения матриц Задания и упражнения..................... 8.2.2. Алгоритм Фокса........................... Задания и упражнения..................... 8.2.3. Алгоритм Кэннона......................... Задания и упражнения..................... 8.3. Обработка графов................................ 8.3.1. Алгоритм Прима нахождения минимального охватывающего дерева............................... Задания и упражнения..................... 8.3.2. Алгоритм Дейкстры поиска кратчайших путей Задания и упражнения..................... 9. Использование системы ПараЛаб в учебном процессе..... 10. Тематика предлагаемых учебных занятий................ 10.1. Общее знакомство с возможностями системы........ 10.2. Изучение параллельных методов решения сложных вычислительных задач.................................... 10.3. Сравнение результатов имитационных экспериментов с результатами реальных экспериментов..................... Приложение. Описание команд системы ПараЛаб......... 1. Начальное меню системы..................... 2. Основное меню............................. 3. Меню выполнения эксперимента............... 4. Меню пошагового выполнения эксперимента.... 5. Меню выполнения серии экспериментов........ Литература.......................................... Предметный указатель................................ 130 Виктор Павлович Гергель, Анна Андреевна Лабутина ПараЛаб Программная система для изучения и исследования методов параллельных вычислений Учебное пособие Редактор Е.В. Тамберг Формат 60х84 1/16. Бумага офсетная № 1. Печать офсетная.

Гарнитура Таймс. Усл. печ. л. 7,3. Уч. изд. л. 7, Тираж 300 экз. Заказ.

Издательство Нижегородского государственного университета им. Н.И. Лобачевского 603590, Н. Новгород, пр. Гагарина, Типография ННГУ: 603000, Н. Новгород, ул. Б. Покровская, 132

Pages:     | 1 ||



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

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