Использование графических ускорителей при решении задач обработки текстов Афонин С.А. Сыроватский Д.А МГУ им.М.В.Ломоносова

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

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

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

2.1 TFLOPs FP TFLOPs FP32

Внешний вид

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

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

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

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

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

Персональная для элемента блока * 32bit byte 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: тысячи точек за секунды