|
|
|
|
Microsoft HPC RussiaОбучениеУчебные курсыТеория и практика параллельных вычислений |
|
|
Теория и практика параллельных вычислений
Задачи и упражнения
Принципы построения параллельных вычислительных систем
-
Приведите дополнительные примеры параллельных
вычислительных систем.
-
Выполните рассмотрение дополнительных способов
классификации компьютерных систем.
-
Рассмотрите способы обеспечения когерентности кэшей в
системах с общей разделяемой памятью.
-
Подготовьте обзор программных библиотек,
обеспечивающих выполнение операций передачи данных для систем с распределенной
памятью.
-
Рассмотрите топологию сети передачи данных в виде
двоичного дерева.
-
Выделите эффективно реализуемые классы задач для
каждого типа топологий сети передачи данных.
Модели вычислений и методы анализа эффективности
- Разработайте модель и выполните оценку показателей
ускорения и эффективности параллельных вычислений:
- для задачи скалярного произведения двух векторов,
- для задачи поиска максимального и минимального
значений для заданного набора числовых данных,
- для задачи
нахождения среднего значения для заданного набора числовых данных
-
Выполните в соответствии с законом Амдаля оценку
максимально достижимого ускорения для задач п. 1.
-
Выполните оценку ускорения масштабирования для задач
п.1.
-
Выполните построение функций изоэффективности для
задач п. 1.
-
(*) Разработайте модель и выполните полный анализ
эффективности параллельных вычислений (ускорение, эффективность, максимально
достижимое ускорение, ускорение масштабирования, функция изоэффективности) для
задачи умножения матрицы на вектор.
Анализ коммуникационной трудоемкости параллельных алгоритмов
-
Разработайте алгоритмы выполнения основных операций
передачи данных для топологии сети в виде 3-мерной решетки.
-
Разработайте алгоритмы выполнения основных операций
передачи данных для топологии сети в виде двоичного дерева.
-
Примените модель B из подраздела 3.4 для оценки
временной сложности операций передачи данных. Сравните получаемые показатели.
-
Примените модель C из подраздела 3.4 для оценки
временной сложности операций передачи данных. Сравните получаемые показатели.
-
Разработайте алгоритмы логического представления
двоичного дерева для различных физических топологий сети.
Технология разработки параллельных программ
для многопроцессорных систем с распределенной памятью (стандарт передачи
сообщений MPI)
-
Разработайте программу для нахождения минимального
(максимального) значения среди элементов вектора.
-
Разработайте программу для вычисления скалярного
произведения двух векторов.
-
Разработайте программу, в
которой два процесса многократно обмениваются сообщениями длиной n
байт. Выполните эксперименты и оцените зависимость времени выполнения операции
данных от длины сообщения. Сравните с теоретическими оценками, построенными по
модели Хокни.
-
Подготовьте варианты ранее разработанных программ с
разными режимами выполнения операций передачи данных. Сравните времена
выполнения операций передачи данных при разных режимах работы.
-
Подготовьте варианты ранее разработанных программ с
использованием неблокирующего способа выполнения операций передачи данных.
Оцените необходимое количество вычислительных операций, для того чтобы
полностью совместить передачу данных и вычисления. Разработайте программу, в
которой бы полностью отсутствовали задержки вычислений из-за ожидания
передаваемых данных.
-
Выполните задание 3 с использованием операции
одновременного выполнения передачи и приема данных. Сравните результаты
вычислительных экспериментов.
-
Разработайте программу-пример для каждой имеющейся в
MPI коллективной операции.
-
Разработайте реализации коллективных операций при
помощи парных обменов между процессами. Выполните вычислительные эксперименты
и сравните времена выполнения разработанных программ и функций MPI для
коллективных операций.
-
Разработайте программу, выполните эксперименты и
сравните результаты для разных алгоритмов реализации операции сбора, обработки
и рассылки данных всех процессам (функция MPI_Allreduce).
-
Разработайте программу-пример для каждого имеющегося
в MPI способа конструирования производных типов данных.
-
Разработайте программу-пример с использованием
функций упаковки и распаковки данных. Выполните эксперименты и сравните с
результатами при использовании производных типов данных.
-
Разработайте производные типы данных для строк,
столбцов, диагоналей матриц.
-
Разработайте программу-пример для каждой из
рассмотренных функций для управления процессами и коммуникаторами.
-
Разработайте программу для представления множества
процессов в виде прямоугольной решетки. Создайте коммуникаторы для каждой
строки и столбца процессов. Выполните коллективную операцию для всех процессов
и для одного из созданных коммуникаторов. Сравните время выполнения операции.
-
Изучите самостоятельно и разработайте
программы-примеры для передачи данных между процессами разных коммуникаторов.
-
Разработайте программу-пример для декартовой
топологии.
-
Разработайте программу-пример для топологии графа.
-
Разработайте подпрограммы для создания некоторого набора
дополнительных виртуальных топологий (звезда, дерево и др.).
Принципы разработки параллельных методов
- Выполните реализацию каскадной схемы вычисления суммы последовательности числовых значений (см.
раздел 2) и сравните время выполнения выполненной реализации и функции MPI_Bcast библиотеки MPI.
-
Выполните реализацию рассмотренных способов
выполнения обобщенной операции сбора данных и сравните время их выполнения.
Сопоставьте получаемые временные характеристики с имеющими теоретическими
оценками. Выполните сравнение со временем выполнения функции MPI_Allgather
библиотеки MPI.
-
Разработайте схему параллельных вычислений,
используя рассмотренную в разделе методику проектирования и разработки
параллельных методов:
- для задачи поиска максимального значения среди
минимальных элементов строк матрицы
(такая задача имеет место для решения
матричных игр) (обратите особое внимание на ситуацию, когда число
процессоров превышает порядок матрицы, т.е. p>N),
- для задачи вычисления определенного интеграла с
использованием метода прямоугольников
(описание методов интегрирования дано,
например, в Kahaner, Moler and Nash (1988)).
-
Выполните реализацию разработанных параллельных
методов для задач п. 3.
-
Разработайте схему параллельных вычислений для
задачи умножения матрицы на вектор, используя рассмотренную в разделе методику
проектирования и разработки параллельных методов.
Параллельные численные алгоритмы для
решения типовых задач вычислительной математики (матрично-векторное
умножение)
-
Выполните реализацию параллельного алгоритма,
основанного на ленточном разбиении матрицы на вертикальные полосы. Постройте
теоретические оценки времени работы этого алгоритма с учетом параметров
используемой вычислительной системы. Проведите вычислительные эксперименты.
Сравните результаты реальных экспериментов с ранее подготовленными
теоретическими оценками.
-
Выполните реализацию параллельного алгоритма,
основанного на разбиении матрицы на блоки. Постройте теоретические оценки
времени работы этого алгоритма с учетом параметров используемой вычислительной
системы. Проведите вычислительные эксперименты. Сравните результаты реальных
экспериментов с ранее подготовленными теоретическими оценками.
Параллельные численные алгоритмы для
решения типовых задач вычислительной математики (матричное
умножение)
-
Выполните реализацию двух ленточных алгоритмов
умножения матриц. Сравните времена выполнения этих алгоритмов.
-
Выполните реализацию алгоритма Кэннона. Постройте
теоретические оценки времени работы этого алгоритма с учетом параметров
используемой вычислительной системы. Проведите вычислительные эксперименты.
Сравните результаты реальных экспериментов с ранее полученными теоретическими
оценками.
-
Выполните реализацию блочных алгоритмов умножения
матриц, которые могли бы быть выполнены для прямоугольных процессорных решеток
общего вида.
-
Выполните реализацию матричного умножения с
использованием ранее разработанных программ умножения матрицы на
вектор.
Параллельные численные алгоритмы для
решения типовых задач вычислительной математики (решение систем линейных
уравнений)
-
Выполните анализ эффективности параллельных
вычислений в отдельности для прямого и обратного этапов метода Гаусса.
Оцените, на каком этапе происходит большее снижение показателей.
-
Выполните разработку параллельного варианта метода
Гаусса при вертикальном разбиении матрицы по столбцам. Постройте теоретические
оценки времени работы этого алгоритма с учетом параметров используемой
вычислительной системы. Проведите вычислительные эксперименты. Сравните
результаты выполненных экспериментов с ранее полученными теоретическими
оценками.
-
Выполните реализацию параллельного метода сопряженных
градиентов. Постройте теоретические оценки времени работы этого алгоритма с
учетом параметров используемой вычислительной системы. Проведите
вычислительные эксперименты. Сравните результаты выполненных экспериментов с
ранее полученными теоретическими оценками.
-
Выполните разработку параллельных вариантов
методов Якоби и Зейделя решения систем линейных уравнений (см. например
Бахвалова и др. (1987), Kumar, et al. (1994), Quinn (2004)). Постройте
теоретические оценки времени работы этого алгоритма с учетом параметров
используемой вычислительной системы. Проведите вычислительные эксперименты.
Сравните результаты выполненных экспериментов с ранее полученными
теоретическими оценками.
Параллельные численные алгоритмы для
решения типовых задач вычислительной математики (сортировка данных)
-
Выполните реализацию параллельного алгоритма
пузырьковой сортировки. Проведите эксперименты. Постройте теоретические оценки
показателей эффективности параллельных вычислений. Сравните получаемые
теоретические оценки с результатами экспериментов.
-
Выполните реализацию параллельного алгоритма быстрой
сортировки по одной из приведенных схем. Определите значения параметров
латентности, пропускной способности и времени выполнения базовой операции для
используемой вычислительной системы и получите оценки показателей ускорения и
эффективности для реализованного метода параллельных вычислений.
-
Разработайте параллельную
схему вычислений для широко известного алгоритма сортировки слиянием (подробное
описание метода может быть получено, например, в работах Кнута (1981) или Кормена,
Лейзерсона и Ривеста (1999)). Выполните реализацию разработанного алгоритма и
постройте все необходимые теоретические оценки сложности метода. Сравните
получаемые теоретические оценки с результатами экспериментов.
Параллельные численные алгоритмы для
решения типовых задач вычислительной математики (обработка графов)
-
Используя приведенный программный код, выполните
реализацию параллельного алгоритма Флойда. Проведите вычислительные
эксперименты. Постройте теоретические оценки с учетом параметров используемой
вычислительной системы. Сравните полученные оценки с экспериментальными
данными.
-
Выполните реализацию параллельного алгоритма Прима.
Проведите вычислительные эксперименты. Постройте теоретические оценки с учетом
параметров используемой вычислительной системы. Сравните полученные оценки с
экспериментальными данными.
-
Разработайте программную реализацию алгоритма Кернигана –
Лина. Дайте оценку возможности распараллеливания этого
алгоритма.
Параллельные численные алгоритмы для
решения типовых задач вычислительной математики (уравнения в частных
производных)
-
Выполните реализацию первого и второго вариантов
параллельного алгоритма Гаусса-Зейделя. Сравните время выполнения
разработанных программ.
-
Выполните реализации параллельного алгоритма на
основе волновой схемы вычислений и параллельного алгоритма, в котором
реализуется блочный подход к методу волновой обработки данных. Сравните время
выполнения разработанных программ.
-
Выполните реализацию очереди заданий параллельных
вычислений для систем с общей памятью. При реализации необходимо
обеспечить возможность обработки близких блоков на одних и тех же процессорах.
<< вернуться |
Документ от: 04.09.2007 13:57
|
|
| |
|
|
Новости
26.12.2007
25.12.2007
24.12.2007
17.12.2007
17.12.2007
|
|
|
|
|
|