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

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

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

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

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

5

6

7 2.1 TFLOPs FP TFLOPs FP32

8 Внешний вид

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

10

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

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

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

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

15

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

17

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

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

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

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

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

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

24