УДК 004.272
ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ПОИСКА СТРОК
В.
Северо-Казахстанский государственный университет им. М. Козыбаева, Петропавловск
Научный руководитель –
Цель данной работы – путем распараллеливания существующих алгоритмов, добиться увеличения производительности поиска информации.
Были отобраны 10 наиболее распространенных алгоритмов поиска строк, которые представлены в таблице. Вычисления произведены на видеокарте с использованием технологии NVIDIA CUDA, предназначенной для разработки приложений для массивно-параллельных вычислительных устройств. На сегодняшний момент поддерживаемыми устройствами являются все GPU компании NVIDIA, начиная с серии GeForce8, а также специализированные для решения расчетных задач GPU семейства Tesla.
Основные преимущества CUDA: простота (все программы пишутся на «расширенном» языке С), наличие хорошей документации, набор готовых инструментов, включающих профайлер, набор готовых библиотек, кроссплатформенность (поддерживаются Microsoft Windows, Linux и Mac OS X).
CUDA строится на концепции, что GPU (называемый устройством, device) выступает в роли массивно-параллельного сопроцессора к CPU (называемому host). Программа на CUDA задействует как CPU, так и GPU. При этом обычный (последовательный, то есть непараллельный) код выполняется на CPU, а для массивно-параллельных вычислений соответствующий код выполняется на GPU как набор одновременно выполняющихся нитей (потоков, threads).
Таким образом, GPU рассматривается как специализированное вычислительное устройство, которое:
• является сопроцессором к CPU;
• обладает собственной памятью;
• обладает возможностью параллельного выполнения огромного количества отдельных нитей.
Важным моментом является то, что хотя подобный подход очень похож на работу с SIMD-моделью, есть и принципиальные отличия (компания NVIDIA использует термин SIMT – Single Instruction, Multiple Thread). Нити разбиваются на группы по 32 нити, называемые warps. Только нити в пределах одного warp выполняются физически одновременно. Нити из разных warp могут находиться на разных стадиях выполнения программы.
Для решения задач CUDA использует очень большое количество параллельно выполняемых нитей, при этом обычно каждой нити соответствует один элемент вычисляемых данных. Все запущенные на выполнение нити организованы в следующую иерархию (рисунок).
Верхний уровень иерархии – сетка (grid) – соответствует всем нитям, выполняющим данное ядро. Верхний уровень представляет из себя одномерный или двухмерный массив блоков (block). Каждый блок – это одномерный, двухмерный или трехмерный массив нитей (thread). При этом все блоки имеют одинаковую размерность и размер [1].
Поскольку модель вычислений, используемая в CUDA похожа на модель SIMD, т. е. параллелизм на уровне данных, то напрашивается следующий принцип параллельного выполнения алгоритмов: исходная строка разбивается на множество мелких подстрок, затем каждый вычислительный поток ищет образец в своей подстроке, используя последовательный алгоритм.
Все алгоритмы тестированы на текстовом файле размером 100 Мбайт, в конце файла находится искомая строка, длиной 6 символов.
Если алгоритм требует предварительных вычислений перед началом поиска, то все предвычисления выполняются на процессоре, даже в параллельном варианте алгоритма, поэтому время предвычислений будем игнорировать, т. к. оно будет одинаковым в обоих случаях. Также не будем учитывать время необходимое на загрузку файла в оперативную память (оно одинаково). Итак, замеряем время работы непосредственно алгоритмов поиска, Рисунок 1. Иерархия нитей в CUDA без «накладных расходов».
Однако следует учесть, что специфика вычислений на видеокарте требует, чтобы обрабатываемые данные находились во внутренней памяти видеокарты, поэтому для получения достоверных результатов следует к основному времени выполнения алгоритма на видеокарте суммировать время загрузки и выгрузки данных.
Для измерения времени работы последовательных версий алгоритмов использовался профилировщик Intel VTune, а для параллельных алгоритмов – NVIDIA Compute Visual Profiler.
Чтобы оценить степень влияния оптимизирующего компилятора, все программы будем компилировать в режимах debug (неоптимизированный) и release (оптимизированный).
Итоговые результаты приведены в таблице (время измерялось в миллисекундах).
Таблица 1
Алгоритм | Последовательный | Параллельный | ||
Debug | Release | Debug | Release | |
Грубой силы | 834 | 461 | 295 | 291 |
Рабина-Карпа | 1078 | 454 | 464 | 478 |
ДКА | 910 | 599 | 283 | 278 |
Морриса-Пратта | 1343 | 525 | 318 | 288 |
Кнута-Морриса-Пратта | 1412 | 543 | 309 | 291 |
Бойера-Мура | 443 | 246 | 286 | 164 |
Бойера-Мура-Хорспула | 432 | 285 | 138 | 137 |
Быстрый поиск | 341 | 181 | 162 | 167 |
Райта | 369 | 261 | 137 | 146 |
Обращения сегмента | 363 | 192 | 140 | 141 |
Оптимизация дает значительный прирост производительности для последовательных алгоритмов, однако для параллельных она практически не имеет смысла.
В среднем, прирост производительности для параллельных алгоритмов составляет 2.9 для неоптимизированного варианта, и 1.6 для оптимизированного. Из этого следует, что использование параллельных вычислений для поиска строк оправдывает себя.
Литература
1. , Харламов работы с технологией CUDA. – М.: ДМК пресс, 2010, 232 c.
