Задание 3. Работа с разделяемой памятью

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

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

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

Варианты:

1. Вычислите матрицу Грама для системы длинных векторов-изображений.
2. Посчитайте сумму по строкам матрицы, которая хранится по строкам.
3. Произведите поворот матрицы изображения, хранящегося по столбцам, на 90 градусов вправо
4. Реализуйте подсчет количества нулей в каждой строке высокой матрицы, хранящейся по строками.
5. Произведите поворот матрицы изображения, хранящегося по строчкам, на 90 градусов влево
6. Реализуйте умножение длинной матрицы, хранящейся по столбцам, на длинный вектор
7. Реализуйте умножение высокой матрицы, хранящейся по строкам, на короткий вектор
8. Реализуйте пакетное возведение в квадрат массива небольших матриц, хранящихся в памяти друг за другом (размерами от 2 до 10)
9. Для каждого элемента большого массива структур типа: struct{ char m1; float p1; ... char m16; float p16;} вычислите результат сложения с маской: m1*p1+...+m16*p16
10. Реализуйте поиск заданного символа в тексте из большого числа строк одинаковой длины. Программа должна возвращать набор номеров строк, где символ был найден.
11. Реализуйте сортировку большого числа маленьких массивов одинаковой длины. Массивы хранятся в памяти друг за другом.
12. На очень высоком и узком черно-белом рисунке изображен выпуклый объект.  Требуется посчитать ширину объекта для каждого значения высоты y. Изображение хранится в памяти по строкам.
13. Создайте детектор вертикальных границ на изображении (в градациях серого). Функция должна для каждой строки считать количество точек, в которых производная цвета по горизонтали больше заданного значения. Все изображения хранятся в памяти по строкам.
14. Заданы две высокие узкие матрицы A и B, хранящиеся в памяти по строкам. Известно, что матрица B получена из A циклической перестановкой столбцов. Реализуйте быструю функцию расчета всех значений циклического сдвига, с которыми можно получить B из A.
15. Задано большое количество маленьких наборов точек одинакового размера (хранятся в памяти один набор после другого). Выясните, на какой из наборов больше похож заданный.
16. Реализуйте быстрый расчет решения дифференциального уравнения dy/dx = sin((x+y)/a), y(0)=y0, x=0..1 методом Эйлера для заданного большого массива значений параметра a. Результат запишите в матрицу, каждая строка которой соответствует одному значению параметра a. Матрица хранится в памяти по строкам.
17. Граф задан матрицей инцидентности, хранящейся в памяти по столбцам-ребрам графа. Требуется построить по матрице список ребер.
18. Для каждой строки изображения оценить количество пикселей заданного цвета с учетом допуска. Изображения хранится в памяти по строчкам.
19. Реализуйте расчет количества транспозиций рядом стоящих коэффициентов матрицы в строке, т.е. для каждой строки i количества таких j, что Ai,j > Ai,j+1. Матрица хранится в памяти по строкам (кол-во столбцов - около 1000).