Информационно-аналитический портал
Высокопроизводительные
вычисления на WINDOWS-кластерах
   

 
 
  Главная
  Новости
  Как создать Windows-кластер
  Компьютеры
  Технологии
  Параллельное программирование
  Библиотеки, пакеты, приложения
  Метакомпьютинг, GRID
  Обучение
  Учебные курсы  
  Исследования
 
  
Логин:    
Пароль:    
Запомнить:
 Забыли пароль? Регистрация 
  
 
Microsoft HPC RussiaОбучениеУчебные курсыТеория и практика параллельных вычислений
 

Теория и практика параллельных вычислений

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

Принципы построения параллельных вычислительных систем

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

Модели вычислений и методы анализа эффективности

  1. Разработайте модель и выполните оценку показателей ускорения и эффективности параллельных вычислений:
    • для задачи скалярного произведения двух векторов,
       
    • для задачи поиска максимального и минимального значений для заданного набора числовых данных,
       
    • для задачи нахождения среднего значения для заданного набора числовых данных
  2. Выполните в соответствии с законом Амдаля оценку максимально достижимого ускорения для задач п. 1.
  3. Выполните оценку ускорения масштабирования для задач п.1.
  4. Выполните построение функций изоэффективности для задач п. 1.
  5. (*) Разработайте модель и выполните полный анализ эффективности параллельных вычислений (ускорение, эффективность, максимально достижимое ускорение, ускорение масштабирования, функция изоэффективности) для задачи умножения матрицы на вектор.

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

  1. Разработайте алгоритмы выполнения основных операций передачи данных для топологии сети в виде 3-мерной решетки.
  2. Разработайте алгоритмы выполнения основных операций передачи данных для топологии сети в виде двоичного дерева.
  3. Примените модель B из подраздела 3.4 для оценки временной сложности операций передачи данных. Сравните получаемые показатели.
  4. Примените модель C из подраздела 3.4 для оценки временной сложности операций передачи данных. Сравните получаемые показатели.
  5. Разработайте алгоритмы логического представления двоичного дерева для различных физических топологий сети.

Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI)

  1. Разработайте программу для нахождения минимального (максимального) значения среди элементов вектора.
  2. Разработайте программу для вычисления скалярного произведения двух векторов.
  3. Разработайте программу, в которой два процесса многократно обмениваются сообщениями длиной n байт. Выполните эксперименты и оцените зависимость времени выполнения операции данных от длины сообщения. Сравните с теоретическими оценками, построенными по модели Хокни.
  4. Подготовьте варианты ранее разработанных программ с разными режимами выполнения операций передачи данных. Сравните времена выполнения операций передачи данных при разных режимах работы.
  5. Подготовьте варианты ранее разработанных программ с использованием неблокирующего способа выполнения операций передачи данных. Оцените необходимое количество вычислительных операций, для того чтобы полностью совместить передачу данных и вычисления. Разработайте программу, в которой бы полностью отсутствовали задержки вычислений из-за ожидания передаваемых данных.
  6. Выполните задание 3 с использованием операции одновременного выполнения передачи и приема данных. Сравните результаты вычислительных экспериментов.
  7. Разработайте программу-пример для каждой имеющейся в MPI коллективной операции.
  8. Разработайте реализации коллективных операций при помощи парных обменов между процессами. Выполните вычислительные эксперименты и сравните времена выполнения разработанных программ и функций MPI для коллективных операций.
  9. Разработайте программу, выполните эксперименты и сравните результаты для разных алгоритмов реализации операции сбора, обработки и рассылки данных всех процессам (функция MPI_Allreduce).
  10. Разработайте программу-пример для каждого имеющегося в MPI способа конструирования производных типов данных.
  11. Разработайте программу-пример с использованием функций упаковки и распаковки данных. Выполните эксперименты и сравните с результатами при использовании производных типов данных.
  12. Разработайте производные типы данных для строк, столбцов, диагоналей матриц.
  13. Разработайте программу-пример для каждой из рассмотренных функций для управления процессами и коммуникаторами.
  14. Разработайте программу для представления множества процессов в виде прямоугольной решетки. Создайте коммуникаторы для каждой строки и столбца процессов. Выполните коллективную операцию для всех процессов и для одного из созданных коммуникаторов. Сравните время выполнения операции.
  15. Изучите самостоятельно и разработайте программы-примеры для передачи данных между процессами разных коммуникаторов.
  16. Разработайте программу-пример для декартовой топологии.
  17. Разработайте программу-пример для топологии графа.
  18. Разработайте подпрограммы для создания некоторого набора дополнительных виртуальных топологий (звезда, дерево и др.).

Принципы разработки параллельных методов

  1. Выполните реализацию каскадной схемы вычисления суммы последовательности числовых значений (см. раздел 2) и сравните время выполнения выполненной реализации и функции MPI_Bcast библиотеки MPI.
  2. Выполните реализацию рассмотренных способов выполнения обобщенной операции сбора данных и сравните время их выполнения. Сопоставьте получаемые временные характеристики с имеющими теоретическими оценками. Выполните сравнение со временем выполнения функции MPI_Allgather библиотеки MPI.
  3. Разработайте схему параллельных вычислений, используя рассмотренную в разделе методику проектирования и разработки параллельных методов:
    • для задачи поиска максимального значения среди минимальных элементов строк матрицы

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

      (описание методов интегрирования дано, например, в Kahaner, Moler and Nash (1988)).
  4. Выполните реализацию разработанных параллельных методов для задач п. 3.
  5. Разработайте схему параллельных вычислений для задачи умножения матрицы на вектор, используя рассмотренную в разделе методику проектирования и разработки параллельных методов.

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

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

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

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

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

  1. Выполните анализ эффективности параллельных вычислений в отдельности для прямого и обратного этапов метода Гаусса. Оцените, на каком этапе происходит большее снижение показателей.
  2. Выполните разработку параллельного варианта метода Гаусса при вертикальном разбиении матрицы по столбцам. Постройте теоретические оценки времени работы этого алгоритма с учетом параметров используемой вычислительной системы. Проведите вычислительные эксперименты. Сравните результаты выполненных экспериментов с ранее полученными теоретическими оценками.
  3. Выполните реализацию параллельного метода сопряженных градиентов. Постройте теоретические оценки времени работы этого алгоритма с учетом параметров используемой вычислительной системы. Проведите вычислительные эксперименты. Сравните результаты выполненных экспериментов с ранее полученными теоретическими оценками.
  4. Выполните разработку параллельных вариантов методов Якоби и Зейделя решения систем линейных уравнений (см. например Бахвалова и др. (1987), Kumar, et al. (1994), Quinn (2004)). Постройте теоретические оценки времени работы этого алгоритма с учетом параметров используемой вычислительной системы. Проведите вычислительные эксперименты. Сравните результаты выполненных экспериментов с ранее полученными теоретическими оценками.

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

  1. Выполните реализацию параллельного алгоритма пузырьковой сортировки. Проведите эксперименты. Постройте теоретические оценки показателей эффективности параллельных вычислений. Сравните получаемые теоретические оценки с результатами экспериментов.
  2. Выполните реализацию параллельного алгоритма быстрой сортировки по одной из приведенных схем. Определите значения параметров латентности, пропускной способности и времени выполнения базовой операции для используемой вычислительной системы и получите оценки показателей ускорения и эффективности для реализованного метода параллельных вычислений.
  3. Разработайте параллельную схему вычислений для широко известного алгоритма сортировки слиянием (подробное описание метода может быть получено, например, в работах Кнута (1981) или  Кормена, Лейзерсона и Ривеста (1999)). Выполните реализацию разработанного алгоритма и постройте все необходимые теоретические оценки сложности метода. Сравните получаемые теоретические оценки с результатами экспериментов.

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

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

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

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

<< вернуться  |   Документ от: 04.09.2007 13:57
 

Новости

26.12.2007
25.12.2007
24.12.2007
17.12.2007
17.12.2007
 

   

© ННГУ, Центр компетенции в области высокопроизводительных вычислений на основе технологий Майкрософт, 2007