10 ПРАКТИЧЕСКИХ ЗАДАНИЙ ПО КУРСУ
     "ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ СУПЕРКОМПЬЮТЕРНЫХ ВЫЧИСЛЕНИЙ"
     преподаватель: Коньшин Игорь Николаевич
 

Общие замечания:
- требуется выбрать и запрограммировать на MPI один из предложенных алгоритмов
(или представить свою собственную параллельную программу в рамках работы со своим
научным руководителем, рассказать о параллельных методах, которые вы использовали);
- проверить корректность получаемого решения;
- замерить время счета на 1,2,4,8,16,32 процессорах и вычислить реальное ускорение;
- теоретически оценить ускорение через вычислительные/коммуникационные затраты
и машиннозависимую характеристику tau (отношение скорости коммуникаций к
скорости арифметики), которую нужно измерить самому в зависимости от
использумых в программе операций и используемого вычислительного сегмента (xNNcore);
- построить графики ускорения и сравнить теорию с практикой;
- написать краткий отчет о работе.

 
(0) Тонкие характеристики обменов данными.
Исследовать зависимость времени инициализации обмена и скорости передачи данных
от всех возможных параметров.
Зависимость от:
(а) длины пересылки (см. Байдин-2008, тест 2),
(б) типа обмена (синхронного/асинхронного, блокирующего/неблокирующего),
(в) количества одновременных обменов,
(г) количества процессоров.

(1) Тесты по "стереотипам" параллельного программирования.
(см. Байдин-2008, тесты 1-5)
Свои выводы по результатам экспериментов.

(2) 2D игра "Жизнь".
Случайное начальное распределение живых клеток.
Периодические условия на границе с замыканием квадратной области в тор.
Контроль стационарности/периодичности состояния.
Исследовать несколько правил "оживания/умирания" клетки.
Интересуют правила, дающие наиболее длительные вариации состояния поля.
2D разбиение исходного поля по процессорам.
Самые смелые могут попробовать реализовать 3D вариант игры
(см. ссылки на https://en.wikipedia.org/wiki/3D_Life).

(3) Матфизика, 3D уравнение теплопроводности
du/dt - |a| Delta u = f
(холодные стенки фиксированной температуры,
в центре постоянный источник тепла).
Ввиду выполнения большинством из вас этой задачи в другом курсе,
просьба рассмотреть оптимизированный вариант, когда передача
данных соседям происходит не на каждом временном шаге, а через
несколько (q) шагов (при этом обмены будут примерно в q раз длиннее,
но зато в q раз реже - экономия на времени инициализации обменов).
(3a) 2D разбиение исходной 3D сетки по процессорам,
оптимизированные обмены (q>1).
(3b) если не получилось отладить оптимизированные обмены, то сделать
3D разбиение исходной сетки по процессорам,
обычные, неоптимизированные обмены (q=1);
(см. Корнеев: 3.4, стр.49-53; 9.3, стр.192-198)
 
(4) Матфизика, 3D уравнение диффузии:
dC/dt = div (D grad C) + f,
3D разбиение исходной сетки по процессорам.
Один из вариантов, аналогичных (3а) или (3b).
(см. Корнеев: 3.4, стр.49-53; 9.3, стр.192-198)

(5) Метод сопряженных градиентов для уравнения Пуассона.
2D сетка узлов, 5-и точечный шаблон дискретизации
(разреженная матрица с элементами: -1 -1 4 -1 -1),
предобусловливатель без перекрытий (блочный метод Якоби),
внутри процессора разложение IC0 (разложение в структуру
исходной матрицы), точное решение x*=1,
начальное приближение x0=0, до точности 1e-6.
 
(6) Метод сопряженных градиентов для системы с плотной матрицей.
Небольшое диагональное преобладание (симметричной!) матрицы,
предобусловливатель без перекрытий (блочный метод Якоби),
внутри процессора разложение Холецкого для своего центрального блока матрицы,
точное решение x*=1, начальное приближение x0=0, до точности 1e-6.
(см. Федотов: 1.2.4, стр.45-51)

(7) Умножение двух плотных матриц (A*B=C).
Плотные квадратные матрицы со случайными элементами.
Строчно-столбцовое распределение данных по процессорам
без дублирования начального и конечного распределения данных,
например, А и С по блочным строкам, В - по столбцам.
Дополнительно реализовать совместное MPI+OpenMP распараллеливание
(см. README.txt mix_daxpy.c qs_mix)
и для фиксированного общего количества ядер (например, 24 на x12core)
найти оптимальное соотношение процессов MPI и нитей OpenMP.
(см. Федотов: 1.2.5, стр.51-59)
(см. Корнеев: 2.1.1, стр.14-18; 9.2.1-9.2.3, стр.178-192)

(8) Параллельная сортировка (сортировки Бэтчера, битонная,
четно-нечетная, или другие) при ограниченной памяти.
Общая суммарная рабочая память - не более 3-х суммарных
длин вектора, причем полный вектор при параллельной реализации
на один процесс не собирается.
(см. Тулебаев: 3.4, стр.49-53)
(см. Корнеев: 9.6, стр.206-210)
(см. М.В.Якобовский: http://lira.imamod.ru/FondProgramm/Sort/ParallelSort.pdf)
 
(9) INMOST
Примеры заданий для параллельной платформы INMOST будут
объявлены дополнительно.
http://inmost.org


Замечание:
в каждой из предложенных задач имеется достаточный ресурс параллелизма
для получения хорошего ускорения:
(2-3-4-5) арифметические затраты пропорциональны количеству внутренних узлов,
а обмены - количеству граничных узлов;
(6) арифметические затраты пропорциональны N*N, а обмены - N;
(7) арифметические затраты пропорциональны N*N*N, а обмены - N*N;
(8) арифметические затраты пропорциональны N log N, а обмены - N,
где N обозначает размерность вектора.


Литература:
http://dodo.inm.ras.ru/konshin/HPC/bib/Bajdin-Stereotipy-2008.pdf
http://dodo.inm.ras.ru/konshin/HPC/bib/Tulebaev-ParProg.pdf
http://dodo.inm.ras.ru/konshin/HPC/bib/Fedotov-Priemy.pdf
http://dodo.inm.ras.ru/konshin/HPC/bib/Korneev-ParProg.pdf