Параллельное программирование на OpenCL

 Найти количество всех различных подстрок заданного размера в заданной строке с учетом порядка следования символов (например, строка xyxxz содержит подстроки x (3), y (1), z (1) размера 1, xy (1), xx (3), xz (3), yx (2), yz (1) размера 2, xyx (2) , xyz (1), xxx (1), xxz (3), yxz(2) размера 3, xyxx (1), xyxz (2), xxxz (1), yxxz (1) размера 4, xyxxz (1) размера 5; в скобках указано количество подстрок; других подстрок нет; таким образом, подстрок размера 1 ровно 5, размера 2 – 10, размера 3 – 9 и т.д.)

Все лабораторные работы должны быть выполнены с использванием языка программирования  C  (или  C ++) в среде  Linux  без графической оболочки (с использованием компилятора  gcc ). Предварительную отладку разрабатываемых программ можно вести с использованием  MS   Visual   Studio  (или других  IDE ), однако следует помнить о возможных несовместимостях с компилятором или библиотеками целевой среды, особенно вероятными в случае использования  C ++. Поэтому рекомендуется ограничиться чистым С.

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

Необходимо добиться того, чтобы параллельный вариант работал быстрее последовательного. Для каждой задачи должны быть проведены несколько вычислительных экспериментов (с различной степенью параллелизма или различными входными данными, …), их результаты должны быть отображены в расчетно-графической работе в форме графиков или таблиц с объяснением характера зависимостей времени вычислений от варьируемых параметров.

Для измерения длительности временных интервалов НЕ следует использовать функцию clock(), это слишком грубый инструмент. Вместо нее нужно использовать либо omp_get_wtime() (это требует включения заголовочного файла omp.h), либо MPI_Wtime() (это требует включения заголовочного файла omp.h), либо clock_gettime() или gettimeofday() (имеющиеся в linux, но отсутствующие в MS Windows). Информацию по последним двум функциям студент должен самостоятельно найти в интернете.

Любые исходные данные должны задаваться в командной строке запуска программы и, возможно, считываться из указанного в ней файла (файлов), т.е. они не должны задаваться/определяться как константы в разрабатываемой программе. Для генерации исходных данных большого объема (матрицы, графы, системы коэффициентов уравнений и т.д.) следует использовать утилиту genData.exe, которую можно скачать с сайта дисциплины.

Объемные результаты вычислений должны выводиться в файл/файлы, для них также должно быть реализовано программное сравнение результатов последовательных и параллельных вычислений на совпадение Небольшие по объему результаты могут выводиться на консоль. Выводиться должны все данные, необходимые для проверки полученного результата. Например, если требуется найти два числа, имеющие одинаковое количество простых делителей, то кроме найденных чисел должны быть выведены и перечни их делителей. Для каждой задачи студент должен продумать, что и в каком виде он будет выводить в качестве результата работы программы. Не следует выводить большие избыточные объемы данных.

Каждая параллельная программа должна автоматически настраиваться на максимально доступное (или задаваемое при ее запуске) количество потоков/узлов/ядер/ветвей/…

При решении задач, связанных с целыми числами, следует работать в 64-разрядном диапазоне (использовать типы данных unsigned long long или __int64).