Часть 3 Базовые алгоритмы

Вопросы к экзамену по дисциплине «Технологии программирования, алгоритмы и структуры данных -2» 2018/19

Часть 1 Анализ параллельных алгоритмов и методы их разработки

1.Каковы тенденции в развитии платформ параллельных вычислений?

2. Какие используются режимы доступа к общей памяти, и каковы возможности моделирования системы CRCW с помощью системы EREW?

3. Как оценивается эффективность параллельного алгоритма? Привести пример.

4. Каковы оценки времени выполнения и эффективности каскадной схемы суммирования?

5. Каковы оценки времени выполнения и асимптотически ненулевой эффективности модифицированной каскадной схемы суммирования?

6. Как оценивается максимально достижимый параллелизм?

7. Как оценивается масштабируемость параллельных вычислений?

8. Как оценивается трудоёмкость операций передачи данных для кластеров?

9. В чём состоят принципы разработки параллельных алгоритмов и каково содержание этапов разработки параллельных алгоритмов?

Часть 2 Технологии параллельного программирования

10. Каковы основные компоненты среды OpenMP и модель выполнения OpenMP-программы?

11. Как используются директивы parallel, sections в среде программирования OpenMP?

12. Как используются директивы master, single в среде программирования OpenMP?

13. Каковы режимы (опции) использования данных в среде программирования OpenMP?

14. Как осуществляется синхронизация в среде программирования OpenMP?

15. Как программируется параллельное выполнение и синхронизация циклов в среде программирования OpenMP?

16. Как осуществляется распределение итераций между потоками в среде программирования OpenMP?

17. Какова структура простейшей MPI-программы?

18. Как используются  количество процессов и ранг процесса MPI-программы, и каким образом контролируется правильность выполнения функций и определяется время выполнения MPI-программы?

19. Какими командами реализуется простейший обмен сообщениями MPI-программы?

20. Как программируется передача данных от одного процесса MPI-программы всем процессам и передача данных от всех процессов MPI-программы одному процессу (операция редукции)?

21. Как осуществляется синхронизация параллельных процессов и обработка особых ситуаций MPI-программы?

22. Какие существуют режимы передачи данных между двумя процессами MPI-программы?

23. Как реализуется управление коммуникаторами MPI-программы?

24. Почему программирование параллельных вычислений с использованием графических процессоров становится всё более актуальным?

25. Как спецификаторы функций в CUDA С определяют вид функции? Для каждого из видов функций укажите, откуда он вызывается, где выполняется и каким ограничениям должен удовлетворять.

26. Какие виды памяти существуют в CUDA, и как используются спецификаторы переменных в CUDA С?

27. Как осуществляется конфигурирование исполнения ядер и синхронизация потоков CUDA?

28. Как при использовании технологии  CUDA реализуется  управление памятью устройства и передача данных между оперативной памятью и памятью GPU?

29. Каковы основные этапы программирования вычислений с использованием технологии CUDA?

30. Какие модели обеспечивают универсальность технологии OpenCL?

31. Каковы этапы разработки параллельной программы с использованием OpenCL?

32. Как программируются ядра с использованием OpenCL?

33. Как создаются и инициируются объекты памяти при программировании с использованием OpenCL?

34. Каковы особенности и средства программирования технологии OpenAcc?

 

Часть 3 Базовые алгоритмы

35. Как осуществляется параллельный алгоритм поиска заданного элемента на общей памяти и каковы его временная сложность и ускорение?

36. Как осуществляется параллельный алгоритм поиска максимального элемента на общей памяти и каковы его временная сложность и ускорение?

37. Как одним и тем же алгоритмом осуществляется обход графа «в глубину» и «в ширину» какова его временная сложность?

38. Как осуществляется выделение компонент связности?

39. Как осуществляется выделение компонент сильной связности?

40. Как реализуется параллельный алгоритм Прима, и какова временная сложность этого алгоритма?

41. Как определяется минимальный остов с помощью алгоритма Крускала, и какова его временная сложность?

42. Как используется алгоритм Дейкстры для определения минимального пути из одной вершины графа в другую вершину, и какова его временная сложность этого алгоритма?

43. Как реализуется параллельный алгоритм определения длин минимальных путей между всеми парами вершин (алгоритм Флойда) и каковы его временная сложность и ускорение?

44. Как реализуется параллельный метод Фокса, и каковы его временная сложность и ускорение?

45. Как реализуется параллельный метод Кэннона, и каковы его временная сложность и ускорение?

46. Как реализуется параллельный метод Гаусса, и каковы его временная сложность и ускорение?

47. Как реализуется параллельный метод сопряжённых градиентов, и каковы его временная сложность и ускорение?

48. Как реализуется параллельный алгоритм сортировки с использованием чётно-нечётной перестановки, и каковы его временная сложность и ускорение?

49. Как реализуется параллельный алгоритм быстрой сортировки, и каковы его временная сложность и ускорение?

50. Как реализуется параллельный алгоритм сортировки с использованием регулярного набора образцов и каковы его временная сложность и ускорение?

51. Как реализуется параллельный алгоритм Прима, и каковы его временная сложность и ускорение?

52. В чем состоит постановка задачи поиска минимального разбиения вершин взвешенного графа и какова ее связь с балансировкой распределенных вычислений?

53. Как реализуется поиск минимального разбиения вершин взвешенного графа?

54. Как реализуется параллельный алгоритм поиска минимального разбиения вершин взвешенного графа, и каковы его временная сложность и ускорение?

55. Как осуществляется балансировка вычислительной нагрузки при параллельном решении задачи о рюкзаке с использованием полного перебора?

56. В чем состоит метод «Встреча посередине» и как достигается ускорение при его параллельной реализации?

57. В чем состоит метод «Встреча на случайном дереве» и как достигается ускорение при его параллельной реализации?

58. В чем состоит метод радужных таблиц: его преимущества и недостатки?

Часть 4. Задачи

1. Выполнить 5 первых итераций алгоритма генерации характеристических векторов  разбиений на ... подмножеств для множества, состоящего из … элементов.

2. Определить ускорение для заданного разбиения вершин взвешенного графа.

3. Выполнить моделирование обхода вершин графа в глубину.

4. Выполнить моделирование обхода вершин графа по уровням.

5. Выполнить моделирование выделения компонент сильной связности графа.

6. Выполнить моделирование алгоритма Прима (построение минимального остова) для графа, заданного матрицей смежности вершин.

7. Выполнить моделирование алгоритма Крускала (построение минимального остова) для графа, заданного матрицей смежности вершин.

8. Выполнить моделирование алгоритма нахождение кратчайших путей от выделенной вершины до заданной  вершины графа (алгоритм Дейкстры).

9. Выполнить моделирование алгоритма нахождение кратчайших путей между всеми парами вершин (алгоритм Флойда).

10. Выполнить моделирование параллельного алгоритма Фокса (умножение матриц) для заданных матриц.

11. Выполнить моделирование параллельного алгоритма Кэннона (умножение матриц) для заданных матриц.

12. Выполнить моделирование алгоритма решения систем линейных уравнений методом сопряжённых градиентов для заданной системы

13. Выполнить моделирование параллельного алгоритма быстрой сортировки (по возрастанию или по убыванию) для заданной последовательности с использованием 4 процессоров.

14. Выполнить моделирование параллельного алгоритма сортировки с использованием регулярного набора образцов (по возрастанию или по убыванию) для заданной последовательности с использованием 3 процессоров.

15. Выполнить моделирование параллельного алгоритма четно-нечетной сортировки на общей памяти.

16. Выполнить моделирование параллельного алгоритма сортировки на линейных сетях.

17. Как программируется вывод на экран каждым потоком сообщения «Работает поток» с указанием номера потока в среде программирования OpenMP?

18. Составить MPI-программу: каждый поток выводит на экран свой идентификационный номер (ранг) и количество заказанных параллельных процессов.

19. В OpenMP-программе применить комбинацию параллельного цикла и редуцированной операции по всем процессам. Главный процесс должен выводить на экран значение sum.

main (){int i, n; float a[100], b[100], sum;

n = 100; for (i=0; i < n; i++) a[i] = b[i] = i * 1.0;

sum = 0.0; for (i=0; i < n; i++) sum = sum + (a[i] * b[i]);

printf(" Sum = %f\n",sum);}

20. Составить OpenMP –программу: каждый поток выводит на экран свой идентификационный номер и количество заказанных параллельных процессов.

21. Распараллелить код умножения матрицы на вектор средствами технологии OpenMP по виткам i:

main (){float A[M][M], b[M], c[M];int i, j, rank;

for (i=0; i < M; i++) {for (j=0; j < M; j++) A[i][j] = (j+1) * 1.0;

b[i] = 1.0 * (i+1); c[i] = 0.0; }

for (i=0; i < M; i++){for (j=0; j < M; j++) c[i] += (A[i][j] * b[j]);

printf(" rank= %d i= %d c[%d]=%.2f\n", rank,i,c[i]); } }

22. Распараллелить код средствами технологии OpenMP:

double f(double y) { return(4.0/(1.0+y*y)); }

int main() { double w,x,sum,pi; int i; int n = 1000;w = 1.0/n; sum = 0.0;

for(i=0; i < n; i++) { x = w*(i-0.5); sum = sum + f(x);}

pi = w*sum; printf("pi = %f\n",pi); return(0); }

23. Составить программу  функции-ядра на CUDA С, реализующую поэлементную сумму двух матриц.

24. С использованием MPI-технологии составить фрагмент программы, осуществляющей широковещательную рассылку числового вектора, вычисление каждым потоком частичных сумм, сбор с помощью редукции частичных сумм и получение общей суммы на главном потоке.

25. Пусть  MPI- программой в коммутаторе MPI_COMM_WORLD создано 9 потоков, которые образуют виртуальную решетку 3×3. Составить фрагмент программы, реализующий создание коммутатора для каждой строки решетки.

26. Составить MPI- программу параллельного вычисления квадратов всех натуральных чисел в диапазоне от 1 до MAX.

27. Пусть алфавит (s=). Определить вероятность успешного поиска ру с использованием радужной таблицы, если минимальная и максимальная длина открытого текста n1= n2=,  число открытых текстов n=.

28. Пусть алфавит (s=). Определить объём памяти, который займёт радужная таблица, если минимальная и максимальная длина открытого текста n1=n2=, вероятность успешного поиска ру=.