Многопоточность в машинном обучении
Следует выделить следующие виды параллелизма:
- Параллелизм на уровне инструкций (ILP[1]): несколько инструкций исполняются одновременно.
- Параллелизм типа одна инструкция множество данных (SIMD[2]): одна операция применяется к множеству данных
- Многопоточный параллелизм: несколько независимых рабочих потоков взаимодействуют через абстракцию совместно используемой памяти.
- Распределенные вычисления: несколько независимых рабочих компьютеров взаимодействуют по сети. (MLlib[3] на Spark, Mahout[4] на Hadoop)
Идеи используемые для ускорения вычислений в ML
Параллелизм для ускорения линейной алгебры.
Многие операции линейной алгебры, например, векторное сложение, произведение матриц и вычисление нормы состоят из большого количества независимых операций. Поэтому можно сильно повысить их производительность как за счёт ILP и SIMD параллелизма для маленьких данных, так и за счёт многопоточности для больших данных. От ускорения линейной алгебры особенно выигрывают нейронные сети, так как большую часть времени их работы занимает умножение матриц.
Иногда необходимо выполнить операцию с объектам имеющими разнаю размерность, но которые можно привести к одной размерности повторением одного из объектов вдоль одной или нескольких осей. Например, если нужно прибавить к каждой строке матрицы вектор или домножить вектор на число. В таком случае можно не писать цикл в явном виде, а использовать broadcast операции. При этом задача оптимизации переходит к разработчику библиотеки, который может обеспечить лучший параллелизм операций за счет доступа к внутренностям библиотеки.
Примеры оптимизаций:
- Высоко оптимизированные тензорные библиотеки для арифметики.
- Алгоритмы в терминах матричных операций, а не векторных операций, насколько это возможно.
- Broadcast операции вместо циклов.
- Распараллеленные реализации некоторых специальных операций (таких как свертки для CNN).
Параллелизм в оптимизации гиперпараметров
Для параллельной оптимизации гиперпараметров можно использовать поиск по решётке или случайный поиск в которых мы можем оценить параметры независимо. Такая оптимизации часто встречаются в библиотеках машинного обучения.
Параллелизм кросс-валидации
Полная кросс-валидация, k-fold, t×k-fold, Leave-One-Out легко распараллеливаются на несколько потоков, каждый из которых работает на своем разбиении данных
Параллелизм GPU[5]
Графические процессоры позволяют применять одну и ту же операцию параллельно к десяткам тысяч элементов за счет большого числа потоков.
Фреймворки машинного обучения, такие как TensorFlow, PyTorch и MxNet используют эти возможности через библиотеки от компаний производителей графических ускорителей и открытые фреймворки:
- CUDA[6] — язык параллельного программирования/вычислительная платформа для вычислений общего назначения на графическом процессоре
- cuBLAS[7] — библиотека представляет собой реализацию BLAS (базовых подпрограмм линейной алгебры) поверх среды выполнения CUDA.
- OpenCL[8] — фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA
Пример перемножения матриц на cuBLAS
void gpu_blas_mmul(cublasHandle_t &handle, const float *A, const float *B, float *C, const int m, const int k, const int n) {
int lda = m, ldb = k, ldc = m;
const float alf = 1;
const float bet = 0;
const float *alpha = &alf;
const float *beta = &bet;
// Do the actual multiplication
cublasSgemm(handle, CUBLAS_OP_N, CUBLAS_OP_N, m, n, k, alpha, A, lda, B, ldb, beta, C, ldc);
}
Пример перемножения матриц на PyCUDA
import pycuda.gpuarray as gpuarray import numpy as np import skcuda.linalg as linalg # --- Initializations import pycuda.autoinit linalg.init() A = np.array(([1, 2, 3], [4, 5, 6])).astype(np.float64) B = np.array(([7, 8, 1, 5], [9, 10, 0, 9], [11, 12, 5, 5])).astype(np.float64) A_gpu = gpuarray.to_gpu(A) B_gpu = gpuarray.to_gpu(B) C_gpu = linalg.dot(A_gpu, B_gpu) print(np.dot(A, B)) print(C_gpu)
Наивная реализация перемножения матриц на OpenCL
// First naive implementation
__kernel void myGEMM1(const int M, const int N, const int K,
const __global float *A,
const __global float *B,
__global float *C) {
// Thread identifiers
const int globalRow = get_global_id(0); // Row ID of C (0..M)
const int globalCol = get_global_id(1); // Col ID of C (0..N)
// Compute a single element (loop over K)
float acc = 0.0f;
for (int k = 0; k < K; k++) {
acc += A[k * M + globalRow] * B[globalCol * K + k];
}
// Store the result
C[globalCol * M + globalRow] = acc;
}
Параллелизм в стохастическом градиентном спуске
Можно запустить внешний цикл стохастического градиентного спуска (SGD) параллельно в пуле потоков и использовать конструкции синхронизации, такие как блокировки, чтобы предотвратить состояние гонки. Однако из-за накладных расходов на синхронизацию ускорение может получиться маленьким.
Еще более интересная идея называется асинхронным SGD или Hogwild[9]. SGD запускается параллельно в несколько потоков без какой-либо синхронизации. Теперь состояния гонки могут возникнуть, но во многих случаях это хорошо, потому что они просто немного изменяют шум и ошибки уже присутствующие из-за случайного выбора градиента.
Параллелизм в методе k ближайших соседей
Основное время работы метода k ближайших соседей составляет поиск ближайших соседей. Так как расстояния до разных объектов независимы, то можно разбить объекты на группы, параллельно решить задачу во всех группах, а потом объединить результат[10]. Альтернативный подход — параллельная сортировка всех объектов, например, с использованием битонной сортировки[11].
Параллелизм в методе опорных веторов
Вычислительная сложность метода опорных векторов заключается в минимизации квадратичной функции. Первый вариант распараллеливания задачи — добавление параллелизма в алгоритм в явном виде, например, параллельная оптимизация большего количества переменных в SMO[12]. Второй подход — запись алгоритма через матричные операции, которые легко параллелизируемы, например, можно обновлять вектор из оптимизируемых параметров через домножение на матрицы[13].
Параллелизм в линейной регрессии
При использовании метода наименьших квадратов поиск коэффициентов регрессии сводится к нахождению псевдообратной матрицы. Хотя псевдообратную матрицу можно вычислить через обратную и для этого существуют параллельные алгоритмы, такой подход остается непрактичным. Более популярный способ, основанный на сингулярном разложении, можно сделать параллельным, если использовать в процессе метод Якоби для собственных значений и на каждом шаге обрабатывать несколько строк и столбцов[14]. Также можно использовать параллельный алгоритм для QR-разложения как это сделано в ScaLAPACK[15].
См. также
Примечания
- ↑ ILP
- ↑ SIMD
- ↑ MLlib
- ↑ Mahout
- ↑ GPU
- ↑ CUDA
- ↑ cuBLAS
- ↑ OpenCL
- ↑ Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright (2011) HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- ↑ Ahmed S. J. Abu Hammad (2019) Implementation of a Parallel K-Nearest Neighbor Algorithm Using MPI
- ↑ Nikos Sismanis, Nikos P. Pitsianis, Xiaobai Sun (2012) Parallel Search of k-Nearest Neighbors with Synchronous Operations
- ↑ Dominik Brugger (2006) Parallel Support Vector Machines
- ↑ Fei Sha, Yuanqing Lin, Lawrence K. Saul, Daniel D. Lee (2006) Multiplicative Updates for Nonnegative Quadratic Programming
- ↑ Handbook of Parallel Computing and Statistics: Parallel Algorithms for the Singular Value Decomposition
- ↑ ScaLAPACK — Linear Least Squares Problems
