Одним из экзаменационных вопросов факультативного курса параллельного программирования последнего года Стамбульского технического университета была реализация поиска наивных шаблонов с использованием MPI на бумаге. В этой статье я реализую этот простой алгоритм параллельно, используя OpenMP.
Простой поиск по шаблону в сериале
Наивный поиск по шаблону просто берет шаблон и просматривает текст, сравнивая части текста, чтобы найти соответствие. Давайте реализуем этот простой алгоритм, используя функцию strncmp из библиотеки String на языке C.
Простой поиск шаблонов в OpenMP
По сути, мы разбиваем текст на куски, и для каждого потока, который мы выполняем, мы назначаем разные куски, используя начальные и конечные индексы.
Давайте реализуем это на C, используя OpenMP.
Имейте в виду, что вам не нужна библиотека OMP для запуска последовательного кода. Тем не менее, я использовал функцию времени стены OMP для измерения времени, чтобы сравнить производительность.
Скомпилируйте вышеуказанные программы, используя следующие команды
gcc np_serial.c -fopenmp -o np_serial [-fopenmp для функциональности настенных часов]
gcc np_parallel.c -fopenmp -o np_parallel
Результаты испытаний ниже.
Имейте в виду, что в небольших тестовых примерах параллелизм не имеет преимущества. Он работает хуже, чем последовательный код, из-за накладных расходов на распараллеливание.
Сравнение производительности
Я протестировал обе программы, используя функцию OpenMP omp_get_wtime.
Ниже приведены результаты 5 последовательных запусков каждого кода для длины шаблона 8 и длины текста четыре миллиона символов.
Надеюсь, вам понравилась эта статья. Не забудьте подписаться на мой блог.
