Как GPU-вычисления буквально спасли меня на работе. Пример на Python

Автор оригинала: Abhishek Mungoli
  • Перевод
Привет, Хабр!

Сегодня мы затрагиваем актуальнейшую тему — Python для работы с GPU. Автор рассматривает пример, тривиальный в своей монструозности, и демонстрирует решение, сопровождая его обширными листингами. Приятного чтения!



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

В следующих разделах я детально опишу эту задачу. Также мы обсудим, как и когда использовать GPU для решения любых подобных задач. Итак, читаем внимательно – поверьте, вы не пожалеете. Сначала мы вникнем в детали задачи, затем освоимся с GPU и, наконец, воспользуемся GPU для решения этой задачи. Я буду пользоваться библиотекой Python Numba и графическим процессором Nvidia Volta V100 16GB GPU.

1. Подробное описание задачи


В сфере розничной торговли часто приходится искать похожие или наиболее близкие объекты. Мне дали список позиций, каждая из которых была представлена k латентными атрибутами. Итак, мне было поручено найти топ-3 наиболее схожих позиций к каждой из позиций списка. Метрикой схожести в данной задаче было выбрано косинусное сходство. Вот как выглядели мои данные.



Список позиций данных с 64-латентными признаками

Сложность задачи

Мне дали список, в котором было около 10⁵ позиций. Поиск 3 наиболее схожих позиций для каждой из них потребовал бы проверить косинусное сходство с каждым без исключения элементов в списке. Получалось бы n * k операций, где n – количество позиций, а k – атрибуты на каждую позицию. Потребовалось бы получить скалярное произведение данной позиции с каждой из остальных позиций в списке.

def top_3_similar_items(X,mindex): # X это список позиций, нам требуется найти топ-3 позиций, наиболее похожих на позицию с индексом 'mindex'
    SMALL = -9999.0 # Просто для инициализации, поскольку нам нужно найти позицию с максимальным уровнем сходства(косинусный показатель)
    first_best_val = SMALL # индекс первой по схожести позиции будет храниться здесь 
    first_best_index = -1 # косинусное сходство с первой по схожести позицией
    second_best_val = SMALL # индекс второй по схожести позиции будет храниться здесь
    second_best_index = -1 # косинусное сходство со второй по схожести позицией
    third_best_val = SMALL # индекс третьей по схожести позиции будет храниться здесь
    third_best_index = -1 # косинусное сходство с третьей по схожести позицией
    for j in range(n): # Всего n-позиций в списке
            if(mindex==j):
                continue
            tmp = np.dot(X[mindex],X[j])/(np.sqrt(np.sum(np.square(X[mindex]))) * np.sqrt(np.sum(np.square(X[j])))) # вычисление скалярного произведения
            if(tmp>=first_best_val):
                third_best_val = second_best_val
                third_best_index = second_best_index
                second_best_val = first_best_val
                second_best_index = first_best_index
                first_best_val = tmp
                first_best_index = j
            elif(tmp>=second_best_val):
                third_best_val = second_best_val
                third_best_index = second_best_index
                second_best_val = tmp
                second_best_index = j
            elif(tmp>third_best_val):
                third_best_val = tmp
                third_best_index = j
    return first_best_val,first_best_index,second_best_val,second_best_index,third_best_val,third_best_index # Возврат всех значений

Код для нахождения трех позиций, максимально подобных заданной

Теперь, при нахождении топ-3 схожих для всех позиций в списке, сложность умножается еще на n. Окончательная сложность оказывается равна O(n*n*k) = O(n²k).

def top_3_similar_all_items(X): # X это список позиций, из которого мы должны выбрать 3 наиболее схожих с каждой позицией
    SMALL = -9999.99 # Просто для инициализации, поскольку нам нужно найти позицию с максимальным уровнем сходства(косинусный показатель)
    first_best_index = np.zeros(n,dtype=int) # индекс первой по схожести позиции будет храниться здесь
    first_best_val = np.zeros(n,dtype=float) # косинусное сходство с первой по схожести позицией
    second_best_index = np.zeros(n,dtype=int) # индекс второй по схожести позиции будет храниться здесь
    second_best_val = np.zeros(n,dtype=float) # косинусное сходство со второй по схожести позицией
    third_best_index = np.zeros(n,dtype=int) # индекс третьей по схожести позиции будет храниться здесь
    third_best_val = np.zeros(n,dtype=float) # косинусное сходство с третьей по схожести позицией
    for i in range(n):
        # Initialisation
        first_best_val[i] = SMALL
        first_best_index[i] = -1
        second_best_val[i] = SMALL
        second_best_index[i] = -1
        third_best_val[i] = SMALL
        third_best_index[i] = -1
        for j in range(n):
            if(i==j):
                continue
            tmp = np.dot(X[i],X[j])/(np.sqrt(np.sum(np.square(X[i]))) * np.sqrt(np.sum(np.square(X[j])))) # вычисление скалярного произведения
            if(tmp>=first_best_val[i]):
                third_best_val[i] = second_best_val[i]
                third_best_index[i] = second_best_index[i]
                second_best_val[i] = first_best_val[i]
                second_best_index[i] = first_best_index[i]
                first_best_val[i] = tmp
                first_best_index[i] = j
            elif(tmp>=second_best_val[i]):
                third_best_val[i] = second_best_val[i]
                third_best_index[i] = second_best_index[i]
                second_best_val[i] = tmp
                second_best_index[i] = j
            elif(tmp>third_best_val[i]):
                third_best_val[i] = tmp
                third_best_index[i] = j
    return first_best_val,first_best_index,second_best_val,second_best_index,third_best_val,third_best_index # Возврат всех значений

Код для нахождения трех наиболее схожих позиций для каждой позиции в списке

Тестовый прогон и оценка времени

Я запустил код, попробовав найти 3 наиболее похожие позиции из подмножества, содержащего n = 10³ позиций с k = 64. На выполнение этой задачи при помощи Python потребовалось около 17 секунд со средней скоростью 3.7 *10⁶ операций в секунду. Код был хорошо оптимизирован с применением операций и массивов Numpy. Отмечу, что все эти операции последовательно выполняются на CPU.

%time first_best_val,first_best_index,second_best_val,second_best_index,third_best_val,third_best_index = top_3_similar_all_items(X)


Прогон для n = 10³ позиций



Вывод: время, потребовавшееся для n = 10³ позиций

Далее я увеличил тестовое подмножество до n =10⁴ позиций. Поскольку сложность равна O(n²k), длительность выполнения возросла в 100 раз (поскольку n возросла в 10 раз). На выполнение кода ушло 1700 секунд = 28,33 минуты.



Вывод: время, потребовавшееся на обработку n = 10⁴ позиций

Далее подходим к самому важному: оценке времени, которое потребуется на обработку полноценного списка из 10⁵ позиций. Посчитав, увидим, что временная сложность вновь возрастет в 100 раз, поскольку временная сложность алгоритма равна O(n²k).
Ориентировочное время = 1700 * 100 секунд = 2834 минуты = 47,2 часа ~ 2 дня.

О, Господи! Так долго!!!

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

2. Сравнение CPU и GPU


Центральный процессор (CPU), в сущности, является мозгом любого вычислительного устройства: он выполняет записанные в программе инструкции, осуществляя управляющие, логические операции, а также операции ввода/вывода.

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

В свою очередь, графический процессор (GPU) обладает более мелкими логическими ядрами, которых, однако, гораздо больше (речь идет об арифметико-логических устройствах (АЛУ), управляющих элементах и кэш-памяти), которые спроектированы с расчетом на параллельную обработку в целом идентичных и сравнительно простых операций.


У GPU больше арифметических логических устройств (ALU), чем у типичного CPU, поэтому повышена способность параллельной обработки простых операций


Рисунок: сравнение CPU и GPU ~ Источник изображения

3. Когда использовать вычисления на GPU


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

Представление об операциях с точки зрения GPU: возьмем, к примеру, операцию поиска слова в документе. Ее можно выполнить последовательно, перебрав одно за другим все слова в документе, либо параллельно, то есть, построчно, либо с поиском по конкретному слову.

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

4. Кратко о CUDA


CUDA – это платформа для параллельных вычислений и модель API, созданная компанией Nvidia. С помощью этого API можно использовать процессор с поддержкой CUDA-графики для широкого спектра вычислений. Такой подход получил название GPGPU (неспециализированные вычисления на графических процессорах). Здесь о них рассказано подробнеe.

NUMBA

Numba – это свободно распространяемый JIT-компилятор, транслирующий подмножество Python и NumPy в быстрый машинный код при помощи LLVM, это делается средствами пакета llvmlite на Python. В этом пакете предлагается ряд вариантов по распараллеливанию кода на Python для CPU и GPU, в самом коде при этом зачастую достаточно минимальных изменений. См. подробнеe.
Работая с процессором Nvidia Volta V100 16GB GPU, я пользовался библиотекой Numba.

Детали архитектуры ~ потоки, блоки и гриды

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

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

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

Грид: Это группа блоков. Между блоками отсутствует всякая синхронизация.



CUDA: потоки, блоки, гриды ~ Источник

Но где же именно выполняются потоки, блоки и гриды? В случае архитектуры G80 GPU от Nvidia, вычисления, по-видимому, распределены следующим образом:

Грид → GPU: Весь грид обрабатывается единственным GPU-процессором.
Блок → МП: Процессор GPU организован как коллекция мультипроцессоров, где каждый мультипроцессор отвечает за обработку одного или более блоков в гриде. Один блок никогда не делится между несколькими МП.
Поток → ПП: Каждый МП далее подразделяется на процессоры потоков (ПП), и каждый ПП обрабатывает один или более потоков в блоке.


Я позаимствовал некоторый материал из этой отлично написанной статьи. Рекомендую почитать ее внимательно.

5. Простая программа для сложения массивов на Python, использующая GPU


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

Допустим, у нас есть два массива, ‘a’ и ‘b’ размера ‘n’. Мы хотим сгенерировать массив ‘c’, такой, чтобы каждый элемент массива c являлся суммой элементов с теми же индексами из массивов ‘a’ и ‘b’. Но в данном случае для решения задачи мы применим не последовательные вычисления, а параллельные, которые делаются при помощи GPU.

Мы запустим n потоков/ядер. Индекс, под которым работает каждый конкретный поток, можно вывести из следующей формулы:

index = cuda.blockIdx.x * cuda.blockDim.x + cuda.threadIdx.x

В случае с двумерной матрицей в индексе присутствует два компонента, означающих строку и столбец, которые можно вывести следующим образом:

row = cuda.blockIdx.x * cuda.blockDim.x + cuda.threadIdx.x
col = cuda.blockIdx.x * cuda.blockDim.x + cuda.threadIdx.x


Также нам придется определить количество потоков на блок, скажем, tpb и блоков на грид, допустим bpg. Воспользуемся стандартными числами для них.

Здесь важно отметить еще одну важную концепцию: когда какие-либо вычисления должны быть выполнены на GPU, соответствующие данные должны быть перенесены в глобальную память GPU, а результаты вычислений после этого могут быть перенесены обратно на хост. Эти операции выполняются при помощи функций cuda.to_device() и copy_to_host(), предоставляемых в библиотеке Numba на Python.

Ниже приведены реализации данного решения как для CPU, так и для GPU. Посмотрите оба листинга, чтобы уловить разницу.

c = np.zeroes(n)
for i in range(n):
    c[i] = a[i] + b[i]
return c

Последовательная реализация для CPU.

from numba import cuda # Библиотека Nvidia для работы с GPU 
import numpy as np 

@cuda.jit('void(float32[:], float32[:], float32[:])') #Динамический компилятор Cuda 
def cuda_addition(a,b,c):
    """Поток будет выполнять эту функцию ядра."""
    i = cuda.blockIdx.x * cuda.blockDim.x + cuda.threadIdx.x # Отображение потока на индекс массива
    if i > c.size:
        return
    c[i] = a[i]+b[i] #Perform the addition
 
# Подробности об устройстве
device = cuda.get_current_device()

# Перенос с хоста на устройство
d_a = cuda.to_device(a)  # Перенос данных в глобальную память GPU
d_b = cuda.to_device(b)  # Перенос данных в глобальную память GPU
d_c = cuda.device_array_like(a)

tpb = device.WARP_SIZE       #blocksize или количество потоков на блок, стандартное значение = 32
bpg = int(np.ceil((n)/tpb))  # блоков на грид

cuda_addition[bpg, tpb](d_a, d_b, d_c) # вызов ядра

# Перенос вывода с устройства на хост
c = d_c.copy_to_host()
print(c)

Параллельная реализация для GPU

6. Нахождение 3 наиболее похожих позиций для каждой позиции в списке при помощи GPU


Хорошенько вникнув в теорию и практику, возвращаемся к исходно поставленной задаче: найти топ-3 похожих позиции для каждой позиции в списке при помощи вычислений на GPU.
В данном случае основная идея заключается в том, что у нас n позиций, и мы запустим n потоков. Каждый поток будет работать параллельно с остальными и независимо от них, вычисляя по 3 наиболее похожие позиции для каждой позиции в списке. За каждую позицию будет отвечать один поток.

from numba import cuda # Nvidia's GPU Library
import numpy as np 
import math #Выполнение математических вычислений, например, нахождение скалярного произведения, Numpy не поддерживается на GPU
import random

# Определение функции ядра                
@cuda.jit('void(float32[:,:],float32[:],int32[:],float32[:],int32[:],float32[:],int32[:])') # CUDA Just-in-time Compiler
def cuda_dist(X,first_best_val,first_best_index,second_best_val,second_best_index,third_best_val,third_best_index):
    """Поток будет выполнять эту функцию ядра."""
    # Отображение потока на строку
    row = cuda.blockIdx.x * cuda.blockDim.x + cuda.threadIdx.x;
    if ((row >= n)): # Принимать потоки только в границах матриц
        return
    first_best_val[row] = SMALL # косинусное сходство с первой по схожести позицией
    first_best_index[row] = -1 # индекс первой по схожести позиции будет храниться здесь
    second_best_val[row] = SMALL # косинусное сходство со второй по схожести позицией
    second_best_index[row] = -1 # индекс второй по схожести позиции будет храниться здесь
    third_best_val[row] = SMALL # косинусное сходство с третьей по схожести позицией
    third_best_index[row] = -1 # индекс третьей по схожести позиции будет храниться здесь
    for i in range(n):
        if(i==row): # Тот же элемент
            continue
        # Переменные для вычисления скалярного произведения, так как мы не можем использовать операции numpy в контексте GPU
        tmp = 0.0
        magnitude1 = 0.0
        magnitude2 = 0.0
        for j in range(k):
            tmp += X[row,j] * X[i,j]
            magnitude1 += (X[row,j]* X[row,j])
            magnitude2 += (X[i,j]* X[i,j])
        tmp /= (math.sqrt(magnitude1)*math.sqrt(magnitude2)) # Значение скалярного произведения Dot_product(a,b) = a.b/(|a|*|b|)
        if(tmp>=first_best_val[row]):
            third_best_val[row] = second_best_val[row]
            third_best_index[row] = second_best_index[row]
            second_best_val[row] = first_best_val[row]
            second_best_index[row] = first_best_index[row]
            first_best_val[row] = tmp
            first_best_index[row] = i
        elif(tmp>=second_best_val[row]):
            third_best_val[row] = second_best_val[row]
            third_best_index[row] = second_best_index[row]
            second_best_val[row] = tmp
            second_best_index[row] = i
        elif(tmp>third_best_val[row]):
            third_best_val[row] = tmp
            third_best_index[row] = i

# Подробности об устройстве
device = cuda.get_current_device()

d_x = cuda.to_device(X)
d_first_val = cuda.device_array_like(first_val)
d_first_index = cuda.device_array_like(first_index)
d_second_val = cuda.device_array_like(second_val)
d_second_index = cuda.device_array_like(second_index)
d_third_val = cuda.device_array_like(third_val)
d_third_index = cuda.device_array_like(third_index)


tpb = device.WARP_SIZE       # blocksize или количество потоков на блок
bpg = int(np.ceil((n)/tpb))  # блоков на грид

%time cuda_dist[bpg,tpb](d_x,d_first_val,d_first_index,d_second_val,d_second_index,d_third_val,d_third_index) # вызов ядра

# Перенос вывода с устройства на хост
first_val = d_first_val.copy_to_host()
print (first_val[:10]) # Первые 10 значений
# Перенос вывода с устройства на хост
first_index = d_first_index.copy_to_host()
print (first_index[:10]) # Первые 10 индексов

Реализация для GPU ~ Код для нахождения 3 позиций, наиболее похожих на данную

Затраченное время

Общее время, затраченное GPU для нахождения топ-3 схожих позиций для каждой позиции в списке, составило 481 мс (0,5 секунд). Еще 20 секунд потребовалось для копирования данных с устройства на хост и с хоста на устройство.

7. Вывод


Задача, решение которой на CPU потребовало бы около 2 дней, на GPU была решена за 20,5 секунд. Это оказалось возможно только благодаря природе задачи. Поиск 3 наиболее похожих позиций для ‘A’ не зависит от поиска 3 наиболее похожих позиций для ‘B’. Мы воспользовались этим фактом и применили параллелизм, предоставляемый GPU, для ускорения процесса. Также пример иллюстрирует, задачи какого типа удобнее всего решать при помощи могучего GPU.

8. Благодарности


Данное исследование было выполнено на MLP (платформе машинного обучения) компании Walmart Labs. Спасибо Аюшу Кумару за помощь в оптимизации рабочего процесса.

Комментарии 53

    +9

    Так изначальный код на питоне считал в один поток, я правильно понял листинг?

      0
      Так как основное тут матричное умножение, а 20 Гига сравнений могут выполниться на CPU быстро, можно просто сравнить Гигафлопсы на рынке и получить разницу 10-100 раз между CPU/GPU.
      Немного устаревший график
      image

        0

        Можно, но 20 секунд и 2 дня — это не 100 раз.
        Даже не 1000, а ближе к 10k, что намекает, что не в CPU дело.

      0

      Мне в аналогичой ситуации очень помог HNSW (было на Хабре: https://habr.com/en/company/mailru/blog/338360/), позиций было порядка 10^6, около 5000 признаков. Индекс строился около суток, но поиск потом был очень быстрым (и, более того, настраиваемо быстрым в обмен на качество). Формально корректные результаты, правда, были так себе, потому что исходные данные были так себе.

        0
        Есть еще библиотека annoy, которая строит индекс и позволяет быстро находить ближайших соседей с разными метриками. Работает с размерностью вектора до 1000, желательно чтобы индекс помещался в оперативку. Естественно, поиск соседей приближенный, это не прямой перебор, используется лес из kd-деревьев.
        +2
        Мда, функция top_3_similar_items(X,mindex) сходу ускоряется раза в 3. См. строчку, где вычисляется tmp. Ну нафига каждый раз длины векторов пересчитывать? Кстати, та же фигня и в последнем варианте кода.
          +4

          Там много такого. Он бы мог сразу отнормировать свои вектора вместо того, чтобы в цикле каждый раз нормировать. А по нормированным векторам можно сразу вычислять матрицу косинусных дистанций хорошо оптимизированным матричным умножением.
          Но сам посыл статьи эти ляпы не отменяют.


          Прочитал ваш комментарий еще раз — вы как раз и имели ввиду под пересчетом длины векторов нормировку.

            0
            Матрицу — фиг, слишком большой размер. Даже если половину хранить. Но, скорее всего, на симметрии все равно можно двойку по времени выиграть. Только придется промежуточные результаты для всех товаров хранить и корректировать по ходу дела.
              0

              Да, матрица с результатом целиком не влезет в память.
              Но у меня была похожая задача, я кусками по 5000 считал, отбирал каждый раз 1000 наиболее похожих. Наверное, тоже не самый оптимальный подход, но по сравнению с алгоритмом из этой статьи раз в 20 быстрее.

          0
          Неплохая статья как вводная.
          А карточка уже была своя или ее специально для задачи фирма купила или в облаке использовали? Ценник не так что бы дружелюбен для «купить что бы попробовать».
            0
            А карточка уже была своя или ее специально для задачи фирма купила или в облаке использовали?
            Так в самом конце статьи написано?
            +9
            Для решения задачи нахождения ближайших соседей есть гораздо более эффективные алгоритмы, чем обход всех точек. Можно было обойтись без GPU.
              0

              Этими алгоритмами можно пользоваться только если функция расстояния является метрикой, по крайней мере должно выполняться неравенство треугольника. Скалярное произведение (делённое на длины векторов) этому не удовлетворяет, например на двумерных векторах (0, 1), (0.5, 1), (0.5, 0). Если бы автор взял функцию, являющуюся метрикой, то действительно можно было бы обойтись без GPU.

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

                  Не просто монотонно, а линейно, то есть можно без особых проблем перевести одно в другое.

              +18
              Код был хорошо оптимизирован с применением операций и массивов Numpy. Отмечу, что все эти операции последовательно выполняются на CPU.

              Скалярное произведение на 64 признака — numpy, двойной цикл по 105 индексов — на питоне, код хорошо оптимизирован, да.


              Сдаётся, что с JIT-компиляцией без GPU вполне бы решалось всё за несколько десятков секунд, а автор в своём восхвалении либо лукавит, либо реально не понимает, в чём там дело.

                –2
                У меня тоже после слов «мой код на питоне исполнялся долго, но я...» в голове зазвучала песенка «Write in C».
                +1
                Тема хорошая, а пример посредственный.
                  0
                  Ничего так ситуация, дали 10^5 строк данных, а еще совершенно случайно Volta V100 откуда-то взялась, можно сказать ждала своего часа.
                    0
                    Человек, собравший приложение на CUDA, с использованием CUDA Toolkit, передал это приложение мне. Могу ли я запустить его без установки CUDA Toolkit (по-сути SDK), имея лишь CUDA-совместимое железо, и, возможно, «драйвер» — либу CUDA?
                      0
                      Смотрите зависимости приложения. Для «чистой» CUDA должно быть достаточно драйвера видеокарты (nvidia-xxx) и cuda-runtime соответствующей версии.
                      0
                      Задача нахождения косинусного расстояния сводится к перемножению матриц. Имеется масса стандартных библиотек, которые решают эту операцию как на CPU так и на GPU.
                      И отличие между CPU и GPU при этом будет на более десяти раз.
                        0

                        К сожалению, матрица 10^5 на 10^5 чисел с плавающей запятой будет занимать около 80 ГБ, так что просто перемножить матрицы нельзя.

                          0
                          Это не так. Существуют методы, которые эффективно работают и с такими большими матрицами (пример реализации умножения матриц, в нем добавляется еще один уровень иерархии — и можно умножать матрицы превышающие размер оперативной памяти).
                            0

                            И сколько же тогда займёт перемножение, если данные будут постоянно дёргаться с диска?

                              0
                              Вся соль блочного подхода в том, что при правильном порядке умножения матриц (вычислительная сложность: O^3, зависимость по данным: O^2) скорость всегда упирается в вычислительные ресурсы. При этом последовательно задействуются: регистры, кэш процессора 1 уровня, 2-го уровня, 3-его, оперативная память, SSD, HDD и т.п.
                                0

                                Можете подсказать библиотеки (желательно для Пайтона), которые реализовывают подобное умножение для стогигабайтных матриц через диск? Потому что писать это всё руками, сами понимаете, такой себе вариант.

                              0
                              О спасибо за пример.
                              +1

                              На одной моей прошлой работе были доступны сервера с 384-512 гигами памяти, и это было году в 2016-м.

                            +4

                            "Программист на Фортране на любом языке может писать на Фортране".


                            У меня максимально "влобным" и неэффективным подходом без JITa ушло 20 сек на 10^4 элементов (то есть где-то в 60 раз быстрее, чем у автора). Цикл for в distance_func тривиально параллелизируется, то есть если есть CPU на ~30 потоков (или какой там Тредриппер можно купить за цену одной Вольты), то никаких "двух суток" и близко не нужно.


                            Заголовок спойлера
                            items = np.random.randint(1, 1000, size=(10**4, 64))
                            
                            # normalize
                            items_norm = items / np.sqrt(np.sum(items**2, axis=1, keepdims=True))
                            
                            def three_closest(X, item) -> (int, int, int):
                                distances = np.sum(X[item, :] * X, axis=1)
                            
                                first = np.argmax(distances)
                                distances[first] = 0
                                second = np.argmax(distances)
                                distances[second] = 0
                                third = np.argmax(distances)
                                distances[third] = 0
                            
                                return first, second, third
                            
                            def distance_func(X):
                                all_items = {}
                            
                                for i in range(len(X)):        
                                    all_items[i] = three_closest(X, i)
                            
                                return all_items
                            
                            distance_func(items_norm)
                              0

                              Прошу прощения, прошляпил. В three_closest переменная first будет всегда иметь значение item, исправляется добавлением distances[item] = 0 перед первым argmax.

                              –1
                              Тоже удивлен двумя сутками. Мы получали ускорение где-то в 100+ раз на Titan Black по сравнению с однопоточным режимом на CPU (i7, чистый Си без ++). Но это был расчет интегралов, а интегралы очень хорошо параллелятся.
                                0
                                Можете еще посмотреть в сторону rapids.ai.
                                  0

                                  -

                                    +1

                                    Показательная статья как делать не надо.


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


                                    Не нужно использовать циклы для работы с матрицами. Все современные процессоры давно поддерживают Advanced Vector Extensions, которые позволяют существенно ускорить работу с матрицами.


                                    Если уж в статье упоминается про NumPy, то именно её и надо было использовать для вычислений. Под капотом она использует высокооптимизированный код, написанный на C, и, насколько я знаю, используется тот самый AVX. Все можно было свести к паре строчек кода и работало бы оно максимум раз в 10-15 медленее чем на видеокарте.


                                    Ну и как написали выше, есть более быстрые алгоритмы.

                                      0
                                      Есть библиотека rapids от Nvidia: rapids.ai которая реализует на GPU практически полный интерфейс pandas и, как бонус, поиск ближайших соседей в памяти GPU.
                                        0
                                        Считается именно 20 секунд, а не 0.5 секунд (на самом деле 0.5 мс будет выведено, перезапустил код локально). Автор посчитал затраченное время на асинхронный вызов.
                                        Также хочется отметить, число колонок 59 — очень неудачное. Если добавить ещё 5 (например, нулевых) до 64, то выполняться на gpu будет быстрее примерно в два раза.

                                        И, конечно, стоило бы воспользоваться готовой библиотекой для этой задачи. Например, при помощи faiss те же 10^5 векторов можно обработать за 25 секунд на TR 1920x (против 50 секунд для кода из статьи на 1080Ti). Результаты совпадают.
                                        Код
                                        import numpy as np
                                        import faiss
                                        
                                        
                                        n = 10**5
                                        k = 59
                                        batch_size = 18
                                        
                                        items = np.random.rand(n, k).astype(np.float32)
                                        items = items / np.sqrt(np.sum(items**2, axis=1, keepdims=True))
                                        bounds = np.linspace(0, n, n // batch_size + 1, dtype=np.int64)
                                        
                                        index = faiss.IndexFlatIP(59)
                                        index.add(items)
                                        
                                        distance = np.zeros((n, 4), dtype=np.float32)
                                        index_val = np.zeros((n, 4), dtype=np.int64)
                                        for lower, upper in zip(bounds[:-1], bounds[1:]):
                                            distance[lower:upper], index_val[lower:upper] = index.search(items[lower:upper], 4)
                                        assert np.sum(index_val[:, 0] != np.arange(n)) == 0
                                        distance = distance[:, 1:]
                                        index_val = index_val[:, 1:]
                                        

                                          +1
                                          Забавно, но перенесённой на Torch и немного оптимизированной версии решения от Physmatik уже требуется всего 0.5 секунды на GPU (1080Ti) и 10.5 секунд на CPU (TR 1920X) на обработку тех же 10^5 векторов. Учитывая возможность эффективного использования FP16 на карте V100, то на ней будет ещё быстрее.
                                          Код на Torch
                                          import torch
                                          
                                          n = 10**5
                                          k = 59
                                          batch_size = 10**3
                                          device = 'cuda:0' # 'cpu'
                                          nn_number = 3
                                          
                                          items = np.random.rand(n, k).astype(np.float32)
                                          items = items / np.sqrt(np.sum(items**2, axis=1, keepdims=True))
                                          
                                          def three_closest(X, indices):
                                              sample_n = indices.shape[0]
                                              index = torch.zeros((sample_n, nn_number), dtype=torch.int64, device=device)
                                              distances = X[indices, :] @ X.T
                                              ind_range = torch.arange(sample_n, device=device)
                                              distances[ind_range, indices] = 0
                                              for j in range(nn_number):
                                                  max_index = torch.argmax(distances, dim=1)
                                                  index[:, j] = max_index
                                                  distances[ind_range, max_index] = 0
                                              return index
                                          
                                          def distance_func(X):
                                              X = torch.from_numpy(X).to(device=device)
                                              all_items = torch.zeros((n, nn_number), dtype=torch.int64, device=device)
                                              for indices in torch.split(torch.arange(n, device=device), batch_size):        
                                                  all_items[indices] = three_closest(X, indices)
                                              return all_items.cpu().numpy()
                                          
                                          nearest_torch = distance_func(items)
                                          

                                          +1
                                          Надеюсь в скором будущем поддержка вычислений на GPU будет добалена в ОС.
                                            +1
                                            А зачем CUDA операционке? Что ей нужно такое большое обсчитывать?
                                              0
                                              А зачем операционке 3D?
                                                0
                                                Если ее интерфейс не отрисовывает что-то в 3D, то и 3D не нужен :)
                                                  0
                                                  Казалось бы. Но ускорение 2D происходит, насколько я понимаю, как одной из поверхностей 3D, т.е. чистых 2D ускорителей не делают. А работать с отключённым ускорением (например, при отсутствии драйвера видеокарты, т.е. «стандартный адаптер vga») тяжело.
                                                    0
                                                    Возможно так и происходит, но тем не менее это означает лишь что ей нужен 3D-ускоритель, а не 3D вообще :)
                                                    Хотя вроде в видеокартах с развитием 3D не отказывались и от 2D-операций…
                                                0
                                                Точно не знаю, но как-то нерационально иметь железо и не использовать его. Будет возможность-наверняка и напишут софт для этого. Хотя бы джипеги жать:)
                                                  0
                                                  Возможность-то уже давно есть, CUDA не вчера появилась :) А вот необходимости в ней у ОС нет :)
                                              0
                                              10 секунд переносим данные к gpu, полсекунды считаем, 10 секунд переносим данные обратно.
                                              нвидия, это же какой-то каменный век.
                                                0
                                                Это не нвидия каменный век, а нужно понимать что именно делается инструментом. Там выше уже написали про асинхронность вызовов, по сути вычисления лениво выполняются только тогда, когда хост их забирает, т.е. 20 секунд и есть время выполнения.
                                                  0

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

                                                    0
                                                    У вольты вполне себе нвлинк может быть. Уже менее тормозной. А что делать? Это фундаментальная проблема — чем дальше данные перемещать, тем медленнее это будет (и дороже с точки зрения энергии).

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

                                              Самое читаемое