CS322. Программирование ускорителей параллельных вычислений

В данном задании требуется представить 2 варианта программы для видеокарты: 1) максимально простой и короткий; и 2) быстрый, использующий разделяемую память. 

Начните с простого и максимально короткого варианта программы. Запрограммируйте генерацию случайных входных данных для алгоритма и автоматическую проверку корректности работы программы. 

Используя формулу Roofline, выполните теоретическую оценку производительности простого алгоритма. На каком интервале Roofline находится ваша программа? Лежит ли она на кривой Roofline или гораздо ниже ее (обычно в этом задании гораздо ниже). Используя профилировку (см. файл профилировка.docx), попытайтесь выяснить причину замедления. Ответьте на вопрос: зачем здесь может пригодится разделяемая память.

Запрограммируйте более сложный вариант с разделяемой памятью и выполнить его профилировку и теоретическую оценку производительности с помощью Roofline.

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

Варианты:

1. Вычислите матрицу Грама для системы длинных векторов-изображений.
2. Посчитайте скалярное произведение всех соответствующих строк двух матриц, хранящихся в памяти по строкам.
3. Для заданной высокой и узкой (50000x1024) матрицы целых чисел int реализуйте проверку того, что ее строки симметричны относительно средней вертикальной линии. Матрица хранится в памяти по строкам. Функция должна возвращать вектор True/False, содержащий для каждой строки результат проверки на симметрию.
4. Реализуйте подсчет количества нулей в каждой строке высокой матрицы A таких, что в матрице B того же размера в соответствующей позиции также стоит 0. Матрицы хранятся по строками.
5. Для заданной текстовой строки длины M и текста из N строк одной той же длины M реализуйте функцию расчета количества строк в тексте, совпадающих с заданной. Текст на 95% состоит из пробелов, N - несколько сотен тысяч, M - несколько сотен.
6. Реализуйте умножение длинной матрицы (128 строк, 200 тыс столбцов), хранящейся по столбцам, на длинный вектор
7. Для двух высоких матриц A и B, хранящихся по строкам, реализуйте умножение максимума из них на короткий вектор v: sum(max(A_ij, B_ij)*v_j, j=1..n)
8. Реализуйте пакетное возведение в квадрат массива небольших матриц, хранящихся в памяти друг за другом (размерами от 2 до 10). Сделайте так, чтобы один параллельный поток полностью вычислял ровно одну матрицу результата.
9. Для каждой пары элементов двух больших массивов структур x и y типа: struct{ char m1; float p1; ... char m16; float p16;} вычислите результат сложения: x.m1*x.p1*y.m1*y.p1+...+x.m16*x.p16*y.m16*y.p16
10. Реализуйте сравнение строк в двух текстах. Оба текста состоят из одинакового большого числа строк. Все строки имеют одинаковую длину. Программа должна возвращать набор номеров строк, где обнаружены совпадающие символы (в соответствующих позициях) и количество совпадений в каждой строке.
11. Реализуйте сортировку большого числа маленьких массивов одинаковой длины. Массивы хранятся в памяти друг за другом.
12. На очень высоком и узком черно-белом рисунке изображен выпуклый объект.  Требуется посчитать ширину объекта для каждого значения высоты y. Изображение хранится в памяти по строкам.
13. Создайте детектор вертикальных границ на изображении (в градациях серого). Функция должна для каждой строки считать количество точек, в которых производная цвета по горизонтали больше заданного значения. Все изображения хранятся в памяти по строкам.
14. Заданы две высокие узкие матрицы A и B, хранящиеся в памяти по строкам. Известно, что некоторые строки матрицы B получены из соответствующих строк A циклической перестановкой столбцов. Реализуйте быструю функцию проверки, которая для каждой строки отвечает на вопрос, является ли заданное число shift циклическим сдвигом, с которым можно получить эту строку B из соответствующей строки A.
15. Задано большое количество маленьких наборов точек одинакового размера (хранятся в памяти один набор после другого). Выясните, на какой из наборов больше похож заданный.
16. Реализуйте быстрый расчет решения дифференциального уравнения dy/dx = sin((x+y)/a), y(0)=y0, x=0..1 методом Эйлера для заданного большого массива значений параметра a. Результат запишите в матрицу, каждая строка которой соответствует одному значению параметра a. Матрица хранится в памяти по строкам.
17. Граф задан матрицей инцидентности, хранящейся в памяти по столбцам-ребрам графа. Требуется построить по матрице список ребер.
18. Для каждой строки изображения оценить количество пикселей заданного цвета с учетом допуска. Изображения хранится в памяти по строчкам.
19. Реализуйте расчет количества транспозиций рядом стоящих коэффициентов матрицы в строке, т.е. для каждой строки i количества таких j, что A_i,j > A_i,j+1. Матрица хранится в памяти по строкам (кол-во столбцов - около 1000).
20. Реализуйте пакетный расчет максиминного элемента в большом количестве маленьких матриц (размерами от 2 до 10). В каждой матрице нужно вычислить max_i min_j a_ij. Матрицы хранятся в памяти друг за другом.
21. Реализуйте пакетный расчет матриц Грама для большого количества систем векторов маленького размера (количество векторов и размерность вектора равны n = 2..10). Системы векторов и матрицы Грама хранятся в памяти друг за другом.