Цель нашей работы - рассмотреть вычислительные методы, которые можно успешно перенести на GPU, и оценить возможное получаемое ускорение. Алгоритмы, которые были изучены в процессе работы приведены на слайде.

Задача выравнивание последовательностей встает при нахождении новых генов.

Задача заключается в том, чтобы осуществить выравнивание двух последовательностей – последовательности запроса и последовательности ссылки. Последовательность ссылка – это длинная последовательность, например, ДНК какого-нибудь живого организма. Последовательность запрос – это искомый ген или совокупность генов.

На GPU последовательность ссылка переносится в виде суффиксного дерева построенного по алгоритму Укконена, а последовательность запрос разбивается на блоки. После переноса данных на GPU выполняется ядро алгоритма – выравнивание последовательностей.

Каждый из мультипроцессоров выполняет алгоритм выравнивания для своего множества блоков запросов оптимально используя кэш.

Ускорение достигается за счет переупорядочивания данных в памяти. Каждый мультипроцессор загружает в кэш свой блок запросов, вследствие этого обращении к нему происходит очень быстро.

Так же используется особая техника загрузки суффикс дерева на GPU. Оно загружается «широкими» и «высокими» блоками, в зависимости от глубины. Это позволяет при обращении к дереву загружать в кэш один блок и ускорить обращение к нему.

В результате переноса алгоритма на GPU для больших наборов коротких запросов, которые начинают доминировать при упорядочивание генома, получаем ускорение до 10 раз.

В настоящее время широко применяется математическое моделирование различных физических процессов, которые модно описать дифференциальными уравнениями в частных производных (ДУЧП).

На слайде приведено рассматриваемое двумерное уравнение с граничными условиями.

Решение искалось в узлах равномерной сетки с постоянным шагом h.

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

Для параллельной реализации метода Зейделя используется прием , который заключается в разделении узлов сетки на «красные» и «черные» как можно видеть на рисунке. Сначала ищется новое приближение к решению в узлах одного цвета, затем в узлах другого цвета. Значение в узле зависит от текущего значения в самом узле и в соседних с ним узлах.

На графическом процессоре распараллеливание происходит следующим образом. Значения функций в узлах хранятся в виде матрицы размером n х m , в одной матрице хранятся как значения внутренних, так и граничных узлов. Вычисления происходят в n/2 блоках независимо и параллельно, в каждом блоке m-2 потоков.

Как видно из графика, при 420 узлах сетки (и допустимой погрешности 10^-4), достигается ускорение примерно в 58 раз.

Разрывный метод Галёркина применяется для решения различных прикладных задач, например, задач теплопроводности или электродинамики.

На слайде слева вы видите электромагнитное поле самолета и справа - электромагнитное поле, создаваемое телефоном, приложенным к уху.

Метод Галёркина заключается в следующем.

Ищется приближенное решение гиперболической системы дифференциальных уравнений при заданных граничных условиях. Если мы решаем задачу электродинамики, то в качестве уравнений берутся уравнения Максвелла.

Идея метода состоит в том, чтобы разбить область на конечные элементы и искать решение отдельно на каждой подобласти. Выбирается произвольная пробная функция «Фи, на которую домножаются уравнения исходной системы. И берется интеграл по каждой подобласти. Далее на каждой подобласти выбирается система базисных функций, например, в качестве такой системы можно использовать полиномы Лагранжа. И для каждого момента времени t ищется приближенное решение как элемент этого конечномерного пространства в виде линейной комбинации базисных функций. Произведя необходимые преобразования, сводим исходную задачу к системе обыкновенных дифференциальных уравнений, для решения которой используется явный метод Рунге-Кутты.

Разрывный метод Галёркина легко распараллелить за счет того, что вычисления в каждой подобласти можно производить независимо. Каждый поток считает свой элемент. Потоки необходимо объединять в блоки таким образом, чтобы минимизировать число обращений к глобальной памяти.

Число операций в секунду зависит от степени базисных полиномов. График зависимости приведен на слайде. Оптимальным считается выбор 3-ей или 4-ой степени.

Также на слайде приведены качественные результаты для вычисления электромагнитного поля от телефона. Как можно видеть, получаем ускорение почти в 30 раз.

На основании рассмотренных методов, можно сделать вывод, что при полном или частичном переносе вычислений на GPU, в частности при использовании архитектуры CUDA, можно получить значительное ускорение. На разных задачах время работы сократилось до 50 раз.