Использование нумерации для оптимизации алгоритма Нидлмана-Вунша на GPU

Введение

Оптимизация алгоритма часто сводится к поиску компромисса между временем работы алгоритма и размером требуемой памяти. Так в [1] представлен способ оптимизации алгоритма Нидлмана-Вунша для выравнивания биологических последовательностей на GPU. Суть оптимизации заключалась в переупорядочивании элементов матрицы динамического программирования так, чтобы вычислимые одновременно элементы матрицы находились в одной строке. В этом случае производится объединение транзакций в глобальной памяти [2], что ускоряет работу программы. Однако размер глобальной памяти, которая требуется программе, в два раза больше, чем у неоптимизированного алгоритма.

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

Постановка задачи

Недостатком алгоритма, предложенного в [1], является то, что часть глобальной памяти остается неиспользованной. Так на рис. 1 показана схема размещения элементов матрицы для последовательностей длины 5.

Рис. 1. Размещение элементов матрицы

Не закрашенные ячейки не используются, что приводит к увеличению требуемой памяти.

Если перенести элементы матрицы из нижнего правого угла в верхний правый (рис. 2), то можно сэкономить глобальную память GPU.

Рис. 2. Оптимальное размещение элементов матрицы

Если длины последовательностей различны, то перенос элементов матрицы производится в несколько шагов (рис 3).

Рис. 3. Размещение элементов матрицы для последовательностей разной длины

Таким образом мы избавились от неиспользуемых элементов матрицы.

Нумерация элементов матрицы

В [1] предложена нумерация , где  и , приводящая к ускорению работы алгоритма:

                                                                                                                      (1)

И обратная :

                                                                                                                     (2)

Для того чтобы привести матрицу к виду, представленному на рис. 2 и рис. 3, необходимо модифицировать данную нумерацию. Так прямая нумерация  примет вид:

                                                                                                          (3)

где n число строк матрицы.

А обратная нумерация :

                                                                                                          (4)

где n число строк матрицы.

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

Реализация алгоритмов

Рассмотрим различные реализации алгоритма Нидлмана-Вунша на GPU на языке CUDA:

-       без применения нуменации;

-       с использованием нумерации n по формулам (1), (2);

-       с использованием нумерации µ по формулам (3), (4).

При использовании нумерации µ будет использоваться блочная схема разделения данных, предложенная в [3].

Так например для последовательностей из 16-и элементов и размером блока 4x4 схема вычисления для нумерации n представлена на рис 4.

Рис. 4. Блочная схема вычислений для нумерации n

Элементы матрицы, обозначенные одинаковыми числами, вычисляются в одном блоке. Эти же числа задают последовательность вычисления блоков.

Для нумерации µ для аналогичных последовательностей схема вычисления представлена на рис. 5.

Рис. 5. Блочная схема вычислений для нумерации µ

Отличие схемы на рис. 5 от схемы на рис. 4 состоит в том, что блоки с нижней части матрицы перенесены наверх в неиспользуемую область матрицы.

Исходный код программы расположен в git-репозитории по адресу https://bitbucket.org/apotapoff/sequence_alignment.git версия 0.0.2. Эксперименты проведены на платформе NVIDIA GeForce GTX 460.

Каждая реализация алгоритма протестирована на последовательностях длины от 1000 до 10000 элементов и с размерами блоков 32x32, 64x64, 128x128, 256x256, 512x512 и 1024x1024 и измерено время заполнения матрицы. Результаты экспериментов представлены в таблице 1.

Таблица 1

Время выполнения алгоритмов

Время заполнения матрицы для блока 256x256 различными реализациями алгоритма показано на рис. 6.

Рис. 6. Время работы алгоритмов для размера блока 256x256

Время работы алгоритмов с различными типами нумерации примерно одинаковое. Однако, при использовании нумерации µ размер требуемой глобальной памяти такой же как и без использования нумерации. Это позволяет обойти ограничение нумерации n на размер глобальной памяти GPU.

Вывод

В статье рассмотрен способ переупорядочивания элементов матрицы с помощью нумерации, позволяющий оптимизировать обращение к глобальной памяти GPU, посредством объединения транзакций. При этом не требуется выделения дополнительной памяти для матрицы. Проведены эксперименты, доказывающие, что использование нумерации ускоряет работу алгоритма.

Литература:

1.      Потапов А. Н. Оптимизация алгоритма выравнивания биологических последовательностей на GPU [Текст] / А. Н. Потапов, Е. А. Кольчугина // Молодой ученый. — 2014. — № 3. — С. 75–83

2.      Боресков А. В. «Параллельные вычисления на GPU. Архитектура и программная модель CUDA: учеб. пособие» — М.: Издательство Московского университета, 2012–336 с.

3.      S. Che, M. Boyer, J. Meng, D. Tarjan, J. W. Sheaffer, and K.Skadron. A performance study of general-purpose applications on graphics processors using cuda. [Online]. Available:http://citeseerx.ist.psu.edu/viewdoc/summary?oi=10.1.1.143.4849