Параллельные алгоритмы

МФТИ, весна 2023

Предварительный перечень тем, вопросов и задач

Теоретический минимум

1. Внутренний параллелизм, степень параллелизма (определение).

2. Оценка времени передачи данных между двумя процессорами, непосредственно соединённых каналом передачи данных.

3. Сверхлинейное ускорение (определение), возможные причины.

4. Ускорение, эффективность (определение).

5. Закон Амдаля.

6. Методы передачи данных (перечислить).

7. Барьер (определение).

8. Семафор (определение).

9. Виды балансировки загрузки процессоров (определение и характерные представители).

10. Критерии декомпозиции расчетных сеток (перечислить).

Вопросы

1. Причины возникновения многопроцессорных систем (МВС). Преимущества и недостатки МВС. Области применения многопроцессорных систем.

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

3. Виды многопроцессорных систем. МВС с общей памятью UMA, NUMA, ccNUMA.
МВС с распределенной памятью, гибридные, векторные.

4. Топологии вычислительных систем.

5. Свойства канала передачи данных. Оценка времени передачи данных через канал. Латентность и пропускная способность.

6. Когерентность кэш-памяти.

7. Внутренний параллелизм, степень параллелизма.

8. Ускорение, эффективность, масштабируемость. Закон Амдаля.

9. Сверхлинейное ускорение, возможные причины. Формальное преобразование параллельного алгоритма в последовательный.

10. Накладные расходы в параллельных алгоритмах.

11. Модель параллельной программы, выполняющейся на вычислительной системе с распределенной памятью.

12. Методы передачи данных.

13. Барьер. Схемы реализации и оценки времени выполнения. Реализация барьера на основе синхронных обменов. Реализация барьера на основе семафоров.

14. Модель параллельной программы, выполняющейся на вычислительной системе с общей памятью. Нити (легковесные процессы, threads).

15. Разделяемые ресурсы. Семафор, критическая секция, монитор.

16. Методы статической и динамической балансировки загрузки процессоров.

17. Метод сдваивания.

18. Метод геометрического параллелизма.

19. Метод коллективного решения.

20. Метод конвейерного параллелизма.

21. Метод диффузной балансировки загрузки.

23. Отладка параллельных приложений, выполнение которых сопровождается недетерминированным потоком сообщений.

24. Декомпозиция расчетных сеток. Критерии декомпозиции.

25. Иерархические алгоритмы разбиения графов. Локальное уточнение.

26. Алгоритм сложения чисел большой разрядности.

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

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

29. Иерархические алгоритмы разбиения графов. Геометрическая бисекция, спектральная бисекция, алгоритм инкрементного роста. Декомпозиция на основе фрактальных кривых.

30. Параллельные алгоритмы численного интегрирования.

31. Псевдослучайные числа для многопроцессорных систем. Требования к генераторам. Методы генерации.

32. Параллельные алгоритмы сортировки данных. Эффективность использования кеш памяти. Метод слияния. Сети сортировки. Производительность и масштабируемость алгоритмов.

33. Визуализация и ввод-вывод сеточных данных.

34. Архитектура вычислительного узла.

Примеры задач

1. Написать алгоритм для вычислительной системы с распределенной памятью, определяющий сумму элементов массива. Считайте, что массив уже распределен между mpi-процессами. Оцените ускорение и эффективность алгоритма в предположении, что время суммирования двух элементов равно TauC, а время пересылки одного числа между процессорами равно TauS.

2. Написать алгоритм для вычислительной системы с общей памятью, определяющий сумму элементов массива. Оцените ускорение и эффективность алгоритма в предположении, что время суммирования двух элементов равно TauC, а минимальное время обращения к семафору равно TauS.

3. Написать алгоритм барьера на основе синхронных обменов. Дать оценку зависимости времени выполнения от числа процессоров, в предположении, что время пересылки одного числа между процессорами равно TauS.

4. Написать алгоритм барьера на основе семафоров. Дать оценку зависимости времени выполнения от числа процессов, в предположении, что время обращения к семафору равно TauS

5. Написать алгоритм определения значения элемента номер 1061 последовательности двухразрядных двоичных чисел, формируемых генератором x^i mod (x^15+ x^3+ 1).

6. Определить период генератора u_(i+1)=(11u_i+5) mod 1024. Найти значение u_321 , при u_0=7.

7. Нарисовать сеть слияния Бэтчера двух упорядоченных массивов размера 3 и 2.

8. Нарисовать сеть сортировки Бэтчера массива размера 5.