Контрольная работа

Вопросы теоретического опроса
1. Критерии оценки производительности многопроцессорных вычислительных систем.
2. В каких величинах проводится оценки производительности многопроцессорных вычислительных систем.
3. Какие существуют основные тесты производительности компьютеров?
4. В чем заключаются основные способы достижения параллелизма?
5. В чем могут состоять различия параллельных вычислительных сис-тем?
6. Что положено в основу классификации Флинна?
7. В чем особенность кластерных вычислительных систем?
8. Какие преимущества предоставляет пользователям вычислительных систем с суперкомпьютерным уровнем кластерная архитектура .
9. Оценки времени передачи сообщений по Хокни.
10. Закон Амдала и его следствия.
11. В чем отличие кластерных вычислительных систем от "мэйнфреймов"?
12. Какие вычислительные системы относятся к grid системам?
13. Какие принципы технической реализации вычислительных систем (ВС) относятся к базовым?
14. Каким требованиям удовлетворяют вычислительные системы, основанные на принципах модульности и близкодействия?
15. Какие архитектурные свойства присущи вычислительным системам?
16. Назовите основополагающие принципы в основе параллельных вычислительных систем.
17. Назовите важнейшие свойства архитектуры ВС.
18. Чем достигается децентрализованность управления ВС?
19. Что понимается под масштабируемостью (Scalability) вычислительных систем?
20. Назовите основные виды реконфигурируемость (Programmability) вычислительных систем и их свойства.
21. Этапы разработки параллельных алгоритмов
22. В чем состоит принцип разделения многопроцессорных систем на мультипроцессоры и мультикомпьютеры?
23. Какие классы систем известны для мультипроцессоров?
24. Какое ускорение вычислений может достигаться для процессоров с поддержкой одновременной многопотоковости?
25. Как определяется расписание для распределения вычислений между процессорами?
26. Как определяется время выполнения параллельного алгоритма?
27. Какое расписание является оптимальным?
28. Как определить минимально возможное время решения задачи?
29. Что понимается под паракомпьютером и для чего может оказаться полезным данное понятие?
30. Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?
31. Как определить минимально возможное время параллельного решения задачи по графу «операнды–операции»?
32. Какие зависимости могут быть получены для времени параллельного решения задачи при увеличении или уменьшения числа используемых процессоров?
33. При каком числе процессоров могут быть получены времена вы-полнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?
34. Как определяются понятия ускорения и эффективности?
35. Возможно ли достижений сверхлинейного ускорения?
36. В чем состоит противоречивость показателей ускорения и эффек-тивности?
37. Как определяется понятие стоимости вычислений?
38. В чем состоит понятие стоимостно-оптимального алгоритма?
39. В чем заключается проблема распараллеливания последователь-ного алгоритма суммирования числовых значений?
40. Какие основные характеристики используются для оценки топологии сети передачи данных? Приведите значения характеристик для конкретных типов коммуникационных структур (полный граф, линейка, решетка и др.).
41. Какие основные методы применяются при маршрутизации передаваемых данных по сети?
42. В чем состоят основные методы передачи данных? Приведите для этих методов аналитические оценки времени выполнения.
43. Какие операции передачи данных могут быть выделены в качестве основных?
44. В чем состоят алгоритмы выполнения передачи данных от одного процессора всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.
45. В чем состоят алгоритмы выполнения передачи данных от всех процессоров всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.
46. Имеют ли подзадачи после масштабирования одинаковую вычислительную и коммуникационную сложность?
47. Зависят ли параметрически правила масштабирования от количества процессоров?
48. Что означает функциональный параллелизм?
49. Какие регулярные структуры базовых подзадач получаются после декомпозиции данных?
50. Какие компьютерные платформы относятся к числу вычислительных систем с общей памятью?
51. Какие подходы используются для разработки параллельных программ?
52. В чем состоят основы технологии OpenMP?
53. В чем состоит важность стандартизации средств разработки параллельных программ?
54. В чем состоят основные преимущества технологии OpenMP?
55. Что понимается под параллельной программой в рамках технологии OpenMP?
56. Что понимается под понятием потока (thread)?
57. Какие проблемы возникают при использовании общих данных в
параллельно выполняемых потоках?
58. Какой формат записи директив OpenMP?
59. В чем состоит назначение директивы parallel?
60. В чем состоят понятия фрагмента, области и секции параллельной программы?
61. Какой минимальный набор директив OpenMP позволяет начать разработку параллельных программ?
62. Как определить время выполнения OpenMP программы?
63. Как осуществляется распараллеливание циклов в OpenMP? Какие условия должны выполняться, чтобы циклы могли быть распараллелены?
64. Какие возможности имеются в OpenMP для управления распреде­лением итераций циклов между потоками?
65. Как определяется порядок выполнения итераций в распараллеливаемых циклах в OpenMP?
66. Какие правила синхронизации вычислений в распараллеливаемых циклах в OpenMP?
67. Как определяются общие и локальные переменные потоков?
68. Что понимается под операцией редукции?
69. Какие способы организации взаимоисключения могут быть ис­пользованы в OpenMP?
70. Что понимается под атомарной (неделимой) операцией?
71. Как определяется критическая секция?
72. Какие операции имеются в OpenMP для переменных семафорного типа (замков)?
73. В каких ситуациях следует применять барьерную синхрониза­цию?
74. Как осуществляется в OpenMP распараллеливание по задачам (директива sections)?
75. Как определяются однопотоковые участки параллельных фраг­ментов (директивы single и master)?
76. Как осуществляется синхронизация состояния памяти (директива
flush)?
77. Как используются постоянные локальные переменные потоков (директивы threadprivate и copyin)?
78. Какой минимальный набор функций MPI позволяет начать разработку параллельных программ?
79. Как определить время выполнения MPI программы?
80. В чем различие парных и коллективных операций передачи данных?
81. Какая функция MPI обеспечивает передачу данных от одного процесса всем процессам?
82. Какие режимы передачи данных поддерживаются в MPI?
83. Как организуется неблокирующий обмен данными в MPI?
84. В чем состоит понятие тупика? В каких ситуациях функция одновременного выполнения передачи и приема гарантирует отсутствие тупиковых ситуаций?
85. Какие коллективные операции передачи данных предусмотрены в MPI?
86. Что понимается под производным типом данных в MPI?
87. Какие способы конструирования типов имеются в MPI?
88. Что понимается в MPI под коммуникатором?
89. Что понимается в MPI под виртуальной топологией?
90. Какие виды топологий предусмотрены в MPI?
91. Напишите программу вывода натурального числа в параллельной области всеми нитями; главной нитью; любой нитью.
92. Напишите программу суммирования ряда из n натуральных чисел. Если n<500 программа должна выполняться последовательно, если n=>500 программа должна выполняться параллельно (применение опции if директивы parallel).
93. Напишите программу скалярного произведения двух векторов. При инициализации параллельной области явно укажите количество используемых нитей 4.
94. Напишите программу скалярного произведения двух векторов. При инициализации параллельной области явно укажите количество используемых нитей 4. Вывод результата скалярного произведения произвела главная нить; первая, завершившая вычисления нить.
95. Дан одномерный массив A из n элементов, расположенный в общей памяти. Написать программу подсчет суммы элементов массива A. (Примечание: использование опции reduction директивы parallel).
96. Дан одномерный массив A из n элементов, расположенный в общей памяти. Написать программу определения маскимального и минимального элементов массива A. (Примечание: использование опции reduction директивы parallel).
97. Дан одномерный массив A из n элементов, расположенный в общей памяти. Написать программу, в которой нити с четными номерами выводят на экран четные элементы массива A, а нити с нечетными номерами выводят на экран нечетные элементы массива A. (Примечание: использование опции if директивы parallel).
98. Дан одномерный массив A из n элементов, расположенный в общей памяти. Написать программу подсчет суммы элементов массива A. Если n меньше 100, то программа выполняется последовательно только главной нитью. Если n больше 100, то подсчет суммы выполняется всеми нитями. Если n равно 100, то программа аварийно завершается. (Примечание: использование опций if, reduction директивы parallel).
99. Дан одномерный массив A из n элементов, расположенный в общей памяти. Написать программу подсчет суммы элементов массива A, количество нитей задается опцией num_threads. (Примечание: использование опций num_threads, reduction директивы parallel).
100. Дан одномерный массив A из n элементов, расположенный в общей памяти. Написать программу подсчета количества нулевых элементов массива A. (Примечание: использование опции reduction директив parallel, for (do)).
101–104. Написать и реализовать параллельную программу на 4-х ядерном процессоре умножения квадратной матрицы на вектор при разделении данных по строкам. Размерность массивов N = № пароля *100. Использовать OpenMP.
105–107. Написать и реализовать параллельную программу перемножения квадратных матриц на 4-х ядерном процессоре. Размерность массивов N = № пароля *100. Использовать OpenMP.
108–110. Написать и реализовать программу параллельного решения систем линейных уравнений методом Гаусса на 4-х ядерном процессоре. Размерность массивов N = № пароля *100.Использовать OpenMP.
111–115. Написать программу параллельного решения СЛАУ методом Гаусса. Распределение данных - горизонтальными полосами. Запуск задачи на 8-ми компьютерах. Размерность массивов N = № пароля *100. Использовать MPI.
116–120. Написать программу параллельного решения задачи Дирихле методом Гаусса-Зейделя для 4-х процесcорной ВС. Размерность массивов N = № пароля *100. Использовать MPI.
=============================================

ЛАБОРАТОРНАЯ РАБОТА № 1 «Изучение работы с нитями в OpenMP»

Цель лабораторной работы – знакомство с библиотекой OpenMP и получение первичных навыков параллельного программирования.

ЛАБОРАТОРНАЯ РАБОТА №2 «Создание параллельных областей в OpenMP»

Цель лабораторной работы – рассмотреть Условия выполнения параллельных областей. Распределение выполняемой программой работы между главно нитью и остальными.

2.1.Обзор директив разделения задач

Упражнения

1. Напишите программу вывода натурального числа в параллельной области всеми нитями; главной нитью; любой нитью.
2. Напишите программу суммирования ряда из n натуральных чисел. Если n<500 программа должна выполняться последовательно, если n=>500 программа должна выполняться параллельно (применение опции if директивы parallel).
3. В предыдущей программе замерите время суммирования ряда в параллельном и последовательном варианте. Сделайте вывод о том, при каком n параллельная программа будет выполняться эффективно?
4. Напишите программу скалярного произведения двух векторов. При инициализации параллельной области явно укажите количество используемых нитей 2 или 4.
5. Предыдущую программу измените так, чтобы вывод результата скалярного произведения произвела главная нить; первая, завершившая вычисления нить.

ЛАБОРАТОРНАЯ РАБОТА №2 «Создание параллельных областей в OpenMP»

Цель лабораторной работы – рассмотреть Условия выполнения параллельных областей. Распределение выполняемой программой работы между главно нитью и остальными.

2.1.Обзор директив разделения задач

Упражнения

1. Напишите программу вывода натурального числа в параллельной области всеми нитями; главной нитью; любой нитью.
2. Напишите программу суммирования ряда из n натуральных чисел. Если n<500 программа должна выполняться последовательно, если n=>500 программа должна выполняться параллельно (применение опции if директивы parallel).
3. В предыдущей программе замерите время суммирования ряда в параллельном и последовательном варианте. Сделайте вывод о том, при каком n параллельная программа будет выполняться эффективно?
4. Напишите программу скалярного произведения двух векторов. При инициализации параллельной области явно укажите количество используемых нитей 2 или 4.
5. Предыдущую программу измените так, чтобы вывод результата скалярного произведения произвела главная нить; первая, завершившая вычисления нить.

ЛАБОРАТОРНАЯ РАБОТА №3 «Параллельные циклы В OpenMP »

3.1.Опции директивы parallel

Директива parallel – инициализирует параллельную область и создает группу из OMP_NUM_THREADS нитей. Определение и задание переменной OMP_NUM_THREADS будет дано в следующем параграфе.

Упражнения

1. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу подсчет суммы элементов массива A. (Примечание: использование опции reduction директивы parallel).
2. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу определения маскимального и минимального элементов массива A. (Примечание: использование опции reduction директивы parallel).
3. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу, в которой нити с четными номерами выводят на экран четные элементы массива A, а нити с нечетными номерами выводят на экран нечетные элементы массива A. (Примечание: использование опции if директивы parallel).
4. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу подсчет суммы элементов массива A. Если n меньше 100, то программа выполняется последовательно только главной нитью. Если n больше 100, то подсчет суммы выполняется всеми нитями. Если n равно 100, то программа аварийно завершается. (Примечание: использование опций if, reduction директивы parallel).
5. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу подсчет суммы элементов массива A, количество нитей задается опцией num_threads. (Примечание: использование опций num_threads, reduction директивы parallel).
6. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу подсчета количества нулевых элементов массива A. (Примечание: использование опции reduction директив parallel, for (do)).
7. Даны два одномерных массива A и B из n элементов, рассположеных в общей памяти. Элементы массива A задаются по следующей формуле a(i)=i, где i – индекс цикла, а элементы массива B по формуле b(i)=thread_num, где thread_num – номер нити. Опцией schedule директивы for (do) задается следующие типы разбиений: static, dynamic, guided. Размер блока chunk равен 1, 2, 4, 8. Программа заполняет массивы A и B, замеряет время выполнения цикла, выводит массивы A, B и время на экран (в файл). Требуется провести анализ времени выполнения программы, определить эффективный тип разбиения массива. (Примечание: количество элементов n более 100, использование опции schedule директив parallel, for (do)).
8. Даны два двумерных массива A и B из NxN элементов, рассположеных в общей памяти. Дано программа запускается на двух нитях. Написать программу заполнения массивов A и B, при условии, что первых массив заполняет первая нить, второй – вторая нить. (Примечание: использование директивы sections).
9. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Элементы массива A задаются по следующей формуле a(i)=i, где i – индекс цикла. Написать программу вывода массива A на экран (в файл) при условии, что вывод выполняется в параллельной области, данные выводятся только один раз. (Примечание: использование директивы single).
10. Дан одномерный массив A из n элементов, рассположеный в общей памяти. Написать программу подсчет суммы элементов массива A. (Примечание: использование комбинированной директивы parallel for(do)).

Вопросы (увеличить количество)

1. В каких случаях может быть необходимо использование опции if директивы parallel?
2. В каких случаях может быть необходимо использование директивs single?
3. Может ли нить-мастер выполнить область, ассоциированную с директивой single?
4. Определите, сколько процессоров доступно в вашей системе для выполнения параллельной части программы, и займите каждый из доступных процессоров выполнением одной нити в рамках общей параллельной области?
5. При помощи трёх уровней вложенных параллельных областей породите 8 нитей (на каждом уровне параллельную область должны исполнять 2 нити). Посмотрите, как будет исполняться программа, если запретить вложенные параллельные области?