МФТИ, 3 курс

«Параллельное программирование»

Весенний семестр 2011

Вопросы:

1. Виды многопроцессорных систем.

2. Многопроцессорные вычислительные системы с общей памятью.

3. Многопроцессорные вычислительные системы с раздельной памятью.

4. Внутренний параллелизм, степень параллелизма. Закон Амдаля.

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

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

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

8. Метод сдваивания. Метод каскадного сдваивания.

9. Ускорение и эффективность параллельных алгоритмов.

10. Статическая балансировка загрузки.

11. Динамическая балансировка загрузки.

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

13. Методы синхронизации последовательных процессов.

14. Каналы межпроцессорной связи.

15. Методы передачи сообщений.

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

17. Взаимная блокировка последовательных процессов.

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

19. Легковесные процессы (треды).

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

21. Параллельные алгоритмы сортировки данных. Сети сортировки.
Четно-нечетные перестановки. Четно-нечетное слияние Бетчера.

22. Параллельные алгоритмы интегрирования одномерных функций.

23. Декомпозиция сеток. Критерии и методы.

Задачи:

24. Построение сети сортировки-слияния на основе метода Бетчера.

25. Параллельный алгоритм сложения n-разрядных целых чисел.

26. Параллельный алгоритм определения суммы конечного ряда.

27. Построение барьера на основе синхронных обменов.

28. Построение барьера на основе семафоров.