Задания 3 и 4. Работа с разделяемой памятью
В данном задании требуется представить 2 варианта программы для видеокарты: 1) максимально простой и короткий; и 2) быстрый, использующий разделяемую память.
Запрограммируйте генерацию случайных входных данных для алгоритма и автоматическую проверку корректности работы программы.
Выполните теоретическую оценку производительности обоих вариантов алгоритма. Укажите в отчете, насколько теоретическая оценка отличается от практической.
Рекомендуемый план выполнения задания: сделать максимально простую и короткую программу; выполнить ее теоретическую оценку производительности и понять из-за чего она не так быстро работает, как должна и зачем здесь может пригодится разделяемая память; запрограммировать более сложный вариант с разделяемой памятью и выполнить его теоретическую оценку производительности.
Варианты:
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, что Ai,j > Ai,j+1. Матрица хранится в памяти по строкам (кол-во столбцов - около 1000).
20. Реализуйте пакетный расчет максиминного элемента в большом количестве маленьких матриц (размерами от 2 до 10). В каждой матрице нужно вычислить max_i min_j a_ij. Матрицы хранятся в памяти друг за другом.
21. Реализуйте пакетный расчет матриц Грама для большого количества систем векторов маленького размера (количество векторов и размерность вектора равны n = 2..10). Системы векторов и матрицы Грама хранятся в памяти друг за другом.