Сравнение FLOP и времени выполнения

Первоначально опубликовано на https://deci.ai/are-all-flops-created-equal-a-comparison-of-flops-vs-run-time/

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

Анализ эффективных моделей, которые начали появляться в последние годы, часто предполагает, что операции с плавающей запятой (FLOP) могут служить точным показателем любой эффективности, включая время выполнения. Это предположение явно неверно в контексте последовательных и параллельных вычислений; когда доступно N рабочих, выкопать ров (задача, которую можно идеально распараллелить) в 1/N быстрее, чем вырыть колодец (последовательная задача по своей сути). Аналогичным образом, благодаря высоким возможностям распараллеливания графического процессора, распараллеливаемые операции будут выполняться быстрее, чем нераспараллеливаемые. Но соображения параллелизма — это еще не все, и в этом посте давайте рассмотрим нетривиальный пример, показывающий, что FLOPS недостаточно для измерения времени выполнения в контексте вычислений на GPU.

В нашем числовом примере мы используем стандартные библиотеки CuPy и PyTorch для выполнения умножения матриц на GPU и CPU. Мы показываем, что одно и то же количество FLOP может привести к разным временам выполнения. Наш пример имитирует операцию на одном уровне сети, где мы исследуем два матричных умножения. Первый продукт умножает матрицу NxN на вектор Nx1. Второй — это внешнее произведение двух векторов, а именно произведение матрицы Nx1 на матрицу 1xN, в результате чего получается матрица NxN. Затем, чтобы получить одинаковое количество FLOP в обоих случаях, после выполнения внешнего произведения мы суммируем каждый из столбцов матрицы, используя N-1 сложений для каждого столбца. Диаграмма на рисунке 1 схематически изображает эти две операции.

Каждая из этих операций потребляет 2xNxN-N FLOP, которые разбиваются на NxN умножений с плавающей запятой (FP) и NxN-N сложений FP.

Теперь мы рассматриваем возможность ускорения этих вычислений с помощью графического процессора (см. код Python ниже). Графики на рис. 2 отображают время выполнения по сравнению с FLOP, измеренными для двух операций. Эти графики были созданы путем применения каждого из продуктов с возрастающими значениями N и усреднения по нескольким запускам.

Хотя количество FLOP в каждом сценарии одинаково, время их выполнения существенно различается. Более того, разница увеличивается по мере увеличения N (количества элементов в матрицах). Например, на кривой CuPy видно, что при размере вектора/матрицы N=20 000 внешний продукт занимает примерно в 1,5 раза больше времени, чем умножение матрицы. При использовании PyTorch при N=20 000 разница увеличивается более чем в 2 раза.

Вот несколько распространенных объяснений значительных различий во времени выполнения операций.

Низкоуровневое представление вычислений графического процессора

Чтобы понять, что может отличать FLOP от времени выполнения, нам нужно сначала понять, как GPU выполняет вычисления. За кулисами есть два вида операций при вычислении значения слоя в глубокой нейронной сети:

Умножение и накопление (MAC) — эта операция принимает три входа: ядро ​​(или информацию о ядре), входные данные и частичную сумму, вычисленную из предыдущей итерации. Эти три входа передаются через арифметико-логическое устройство (АЛУ), которое выполняет побитовые операции умножения и сложения. Результатом операции является частичная сумма, которая хранится в отдельной ячейке памяти.

Доступ к памяти — эта операция берет частичную сумму, вычисленную для каждой операции MAC, и сохраняет ее в назначенном блоке памяти, в зависимости от ее размера. Грубо говоря, существует четыре (иногда больше) типа блоков памяти: память регистрового файла (РФ), в которой хранится небольшой объем данных (до 1Кб); процессор обработки (PE), который хранит немного больше данных; буферный блок; и ДРАМ. По мере увеличения размера блока памяти увеличивается и время, потребляемое этим блоком. В худшем случае чтение и запись в DRAM может быть очень дорогостоящей и выполняться более чем в 200 раз по сравнению с хранением в RF.

Когда мы подсчитываем FLOP, мы на самом деле не различаем MAC и операции доступа к памяти. Однако они могут сильно отличаться от времени выполнения. Последовательность MAC-адресов, требующих большого объема памяти DRAM, может занять гораздо больше времени, чем такое же количество MAC-адресов, которые вообще не используют DRAM.

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

Возвращаясь к нашему числовому примеру, можно объяснить разницу во времени выполнения двумя факторами: параллелизмом и доступом к памяти. Тем не менее, пользовательская реализация может уменьшить разницу во времени выполнения; следовательно, эта разница сильно зависит от конкретной реализации используемой платформы. Мы смогли определить конкретные узкие места доступа к памяти и параллелизма с помощью инструмента NVIDIA под названием Nsight system. Оставим эту тему для следующего поста.

Программирование, ориентированное на память, может ускорить вычисления

Несмотря на значительные пробелы, которые мы наблюдаем на рисунке 2, мы хотели бы проиллюстрировать влияние структуры на результаты. При использовании высокоуровневых фреймворков (например, CuPy, PyTorch, TensorFlow и т. д.) мы фактически используем предопределенный алгоритм. В разных случаях использования разные алгоритмы демонстрируют разную производительность. Например, CuPy-реализация двумерного массива реализуется путем переиндексации записей одномерного массива. Это означает, что при попытке извлечь элементы из двумерного массива соседние элементы в строке будут извлечены быстрее, чем соседние элементы в столбце. По этой причине мы можем ожидать, что общий алгоритм будет выполнять суммирование быстрее по строкам, чем по столбцам. Напомним, что в результатах на рисунке 2 мы выполнили суммирование с помощью CuPy по столбцам. Теперь мы покажем, что, изменив размерность суммирования, мы можем (почти) сделать время выполнения двух операций равным. Это видно на рисунке 3:

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

Вывод

На конкретном примере матричного/векторного произведения мы продемонстрировали, что когда дело доходит до времени выполнения, FLOP нельзя использовать в качестве универсального показателя эффективности. Часто этот факт упускается из виду даже в некоторых научных работах. Мы использовали CuPy и PyTorch, чтобы продемонстрировать, как два матричных/векторных умножения, которые потребляют одинаковое количество FLOP, могут иметь радикально различное время выполнения. Мы также кратко обсудили причины этих различий.

Код CuPy

import cupy as cp
import time
import os
import numpy as np
import matplotlib.pyplot as plt
from cupy import cuda
import pickle

def cp_Matmul(x, y, iterations):
    for i in range(iterations): 
      q = cp.matmul(x, y, out=None)   
    return q

def cp_Vecmul(x,y,iterations):
    for i in range(iterations):
        q = cp.matmul(x,y,out=None)
        q = cp.sum(q,axis=1)      
    return q

xmin = 1000
xmax = 20000
jump = 500
lim = range(xmin,xmax,jump)

Matrix_result = []
Vector_result = []
iterations = 1000

for k in lim:
    N = k

    vec_outer_1 = cp.random.rand(N,1)
    vec_outer_2 = cp.random.rand(1,N)

    matrix = cp.random.rand(N,N)
    vec_matrix = cp.random.rand(N,1)


    start_event = cp.cuda.stream.Event()
    stop_event = cp.cuda.stream.Event()
    start_event.record()
    q = cp_Vecmul(vec_outer_1,vec_outer_2,iterations)
    stop_event.record()
    stop_event.synchronize()
    Vector_time = cp.cuda.get_elapsed_time(start_event, stop_event)/1000
Matrix_result.append(Matrix_time)
print('Total run time matrices', Matrix_time)

Код PyTorch

import os
import numpy as np
import matplotlib.pyplot as plt
import torch
import pickle

def tr_Matmul(a, b, iterations):
    for i in range(iterations):
        q = torch.mm(a, b, out=None).to(device=cuda0)
    return q

def tr_Vecmul(a,b,iterations):
    for i in range(iterations):
        q = torch.mm(a,b,out=None).to(device=cuda0)
        q = torch.sum(q,dim=0).to(device=cuda0)
    return q

xmin = 1000
xmax = 20000
jump = 500
lim = range(xmin,xmax,jump)

Matrix_result = []
Vector_result = []
iterations = 1000

for k in lim:
    N = k
    cuda0 = torch.device(device='cuda')

    vec_outer_1 = torch.rand(N,1).to(device=cuda0)
    vec_outer_2 = torch.rand(1,N).to(device=cuda0)

    matrix = torch.rand(N,N).to(device=cuda0)
    vec_matrix = torch.rand(N,1).to(device=cuda0)


    start_event = torch.cuda.Event(enable_timing=True)
    stop_event = torch.cuda.Event(enable_timing=True)
    start_event.record()

    q = tr_Vecmul(vec_outer_1,vec_outer_2,iterations)
    stop_event.record()
    torch.cuda.synchronize()
    Vector_time = start_event.elapsed_time( stop_event)/1000
    Vector_result.append(Vector_time)
    print('Total run time vectors',Vector_time)

    start_event = torch.cuda.Event(enable_timing=True)
    stop_event = torch.cuda.Event(enable_timing=True)
    start_event.record()
   
    q = tr_Matmul(matrix, vec_matrix, iterations)
    stop_event.record()
    torch.cuda.synchronize()
    Matrix_time =  start_event.elapsed_time( stop_event)/1000
    Matrix_result.append(Matrix_time)
    print('Total run time matrices', Matrix_time)