Министерство образования Российской Федерации

Московский государственный технический университет им. Н.Э. Баумана

Факультет "Информатика и системы управления"

Кафедра ИУ-3

Методические указания к лабораторной работе

Москва 2011 г.

Содержание

1. Цель работы.

2. Задание для домашней подготовки.

3. Задание на лабораторную работу.

4. Содержание отчета.

5. Контрольные вопросы.

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

7. Приложение.

1. Введние.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   4. Решение систем линейных уравнений

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Цель работы.

Изучение и исследование студентами параллельных алгоритмов решения сложных вычислительных задач на примере системы Параллельная Лаборатория (сокращенное наименование – ПараЛаб http://www.software.unn.ac.ru/ccam/GCC_Kozinov/Applet1.html ).

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

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

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

2. Задание для домашней подготовки.

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

Изучуть теоретический материал по программе параЛаб:

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

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

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

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

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

   4. Решение систем линейных уравнений

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

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

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

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

3. Задание на лабораторную работу. Сортировка.

1. Установите производительность процессоров и их количество, в соответствии с вариантом.

2. Установите топологию сети, в соответствии с вариантом.

3. Выберите метод сортировки в соответсвии с вариантом.

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

Номер варианта	1	2	3	4	5	6	7	8	9
Производительность процессоров(Gflops)	0,5	1,0	1,5	2,0	2,5	3,0	3,5	4,0	4,5
Кол-во процессоров	5	10	20	5	10	20	5	10	20
Метод сортировки**	1	1	1	1	1	1	1	1	1
Топология сети*	1	1	1	2	2	2	3	3	3
Размер массива (нижний предел)	500	1000	1500	2000	2500	3000	3500	4000	4500
Размер массива (верхний предел)	2500	3000	3500	4000	4500	5000	5500	6000	6500
Номер варианта*	10	11	12	13	14	15	16	17	18
Производительность процессоров(Gflops)	0,5	1,0	1,5	2,0	2,5	3,0	3,5	4,0	4,5
Кол-во процессоров	2	4	8	5	10	20	5	10	20
Метод сортировки**	1	1	1	1	1	1	2	2	2
Топология сети*	4	4	4	5	5	5	4	4	4
Размер массива (нижний предел)	500	1000	1500	2000	2500	3000	3500	4000	4500
Размер массива (верхний предел)	2500	3000	3500	4000	4500	5000	5500	6000	6500

*топология сети обозначается следующими вариантами:

1)линейка

2) кольцо

3)решетка

4)гиперкуб

5)полный граф

**Метод сортировки обозначается следующими вариантами:

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

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