Использование графических ускорителей при решении задач обработки текстов

План
Что такое GPU и CUDA
Алгоритмы анализа данных
Задачи обработки текстов

GPU и CUDA
GPU = Graphic Processing Unit
CUDA = Computing Unified Device Architecture

Почему графические ускорители (GPU)?

Внешний вид

Графические процессоры

#2 in Top500: NEBULAE
1.27 PFlops Linpack 2.9 PFlops peak

CUDA – почти С
Единственное отличие – добавления для работы с потоками

Архитектура CUDA
SIMD мультипроцессоры (8 или 16 ядер)
Мультипроцессор имеет регистры и разделяемую (локальную) память
Задача разбивается на блоки, блоки — на потоки
Блоки назначаются на процессоры; выполненный блок невозможно запустить повторно

Общая для элементов блока
Персональная для
элемента блока

Персональная для
элемента блока
16384 * 32bit
16384 byte
65536 B

Алгоритмы анализа данных
Выявление ассоциативных зависимостей (Association rule mining, Apriori)
Классификация (KNN)
Кластеризация (K-means)
Уменьшение размерности данных

Выявление зависимостей
I={i1,...,im} — множество атрибутов
База данных — набор записей вида (TID, i1, ..., ip)
Частотный k-набор — k-подмножество I, элементы которого встречаются более чем в N записях
Задача: найти все частотные k-наборы
Зависимости: если набор содержит X, то от содержит и x' с вероятностью p

Алгоритм выявления
Найти все частотные 1-наборы
Для k=2,... и пока есть новые наборы
Построение k-кандидатов: объединение двух частотных (k-1)-наборов с общим (k-2)-префиксом
Фильтрация: к-кандидат удаляется, если он содержит не частотное (k-1) подмножество
Определение частотности кандидатов

Классификация
Метод ближайших соседей
Задана выборка объектов с приписанными метками
Для нового объекта вычисляется расстояние до всех объектов выборки
Метка нового объекта — самая частотная метка его K ближайших соседей из выборки

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

Производительность на GPU: тысячи точек за секунды