Многопоточность в машинном обучении

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Следует выделить следующие виды параллелизма:

  • Параллелизм на уровне инструкций (англ. instruction-level parallelism, ILP[1]): несколько инструкций исполняются одновременно.
  • Параллелизм типа одна инструкция множество данных (англ. single instruction, multiple data, SIMD[2]): одна операция применяется к множеству данных.
  • Многопоточный параллелизм: несколько независимых рабочих потоков взаимодействуют через абстракцию совместно используемой памяти.
  • Распределенные вычисления: несколько независимых рабочих компьютеров взаимодействуют по сети (MLlib[3] на Spark, Mahout[4] на Hadoop).

Идеи используемые для ускорения вычислений в машинном обучении

Параллелизм для ускорения линейной алгебры

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

Некоторые действия, выполняемые в цикле, можно записать как операции над матрицами, полученными повторением матриц меньшей размерности. Например, сложение каждой строки матрицы с вектором — это сложение двух матриц, в одной из которых повторяются строки. Бродкастинг (англ. broadcasting[5][6]) позволяет выполнять операции с аргуметами разных размерностей, неявно приводя их к одной. При этом из пользовательского кода исчезают циклы, а задача оптимизации переходит к разработчику библиотеки, который может обеспечить лучший параллелизм операций за счет доступа к внутренностям библиотеки.

Примеры оптимизаций:

  • Высоко оптимизированные тензорные библиотеки для арифметики.
  • Алгоритмы в терминах матричных операций, а не векторных операций, насколько это возможно.
  • Бродкастинг вместо циклов.
  • Распараллеленные реализации некоторых специальных операций (таких как свертки для сверточных сетей).

Параллелизм в оптимизации гиперпараметров

Для параллельной оптимизации гиперпараметров можно использовать поиск по решётке или случайный поиск в которых мы можем оценить параметры независимо. Такая оптимизации часто встречаются в библиотеках машинного обучения.

Параллелизм кросс-валидации

Полная кросс-валидация, k-fold, t×k-fold, Leave-One-Out легко распараллеливаются на несколько потоков, каждый из которых работает на своем разбиении данных

ParallelCrossValidation.png

Параллелизм GPU[7]

Графические процессоры позволяют применять одну и ту же операцию параллельно к десяткам тысяч элементов за счет большого числа потоков.

Фреймворки машинного обучения, такие как TensorFlow, PyTorch и MxNet используют эти возможности через библиотеки от компаний производителей графических ускорителей и открытые фреймворки:

  • CUDA[8] — язык параллельного программирования/вычислительная платформа для вычислений общего назначения на графическом процессоре
  • cuBLAS[9] — библиотека представляет собой реализацию базовых подпрограмм линейной алгебры (англ. Basic Linear Algebra Subprograms, BLAS) поверх среды выполнения CUDA.
  • OpenCL[10] — фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также программируемых пользователем вентильных матрицах (ППВМ, англ. field-programmable gate array, FPGA[11]).

Пример перемножения матриц на C с использованием 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[12]. SGD запускается параллельно в несколько потоков без какой-либо синхронизации. Теперь состояния гонки могут возникнуть, но во многих случаях это хорошо, потому что они просто немного изменяют шум и ошибки уже присутствующие из-за случайного выбора градиента.

Параллелизм в методе k ближайших соседей

Основное время работы метода k ближайших соседей составляет поиск ближайших соседей. Так как расстояния до разных объектов независимы, то можно разбить объекты на группы, параллельно решить задачу во всех группах, а потом объединить результат[13]. Альтернативный подход — параллельная сортировка всех объектов, например, с использованием битонной сортировки[14].

Параллелизм в методе опорных векторов

Вычислительная сложность метода опорных векторов заключается в минимизации квадратичной функции. Первый вариант распараллеливания задачи — добавление параллелизма в алгоритм в явном виде, например, параллельная оптимизация большего количества переменных в SMO[15]. Второй подход — запись алгоритма через матричные операции, которые легко параллелизируемы, например, можно обновлять вектор из оптимизируемых параметров через умножение на матрицы[16].

Параллелизм в линейной регрессии

При использовании метода наименьших квадратов поиск коэффициентов регрессии сводится к нахождению псевдообратной матрицы. Хотя псевдообратную матрицу можно вычислить через обратную и для этого существуют параллельные алгоритмы, такой подход остается непрактичным. Более популярный способ, основанный на сингулярном разложении, можно сделать параллельным, если в процессе использовать метод Якоби для собственных значений и на каждом шаге обрабатывать несколько строк и столбцов[17]. Также можно использовать параллельный алгоритм для QR-разложения как это сделано в ScaLAPACK[18].

См. также

Примечания

  1. ↑ ILP
  2. ↑ SIMD
  3. ↑ MLlib
  4. ↑ Mahout
  5. ↑ Broadcasting — NumPy v1.19 Manual
  6. ↑ Broadcasting (GNU Octave (version 6.1.0))
  7. ↑ GPU
  8. ↑ CUDA
  9. ↑ cuBLAS
  10. ↑ OpenCL
  11. ↑ Программируемая пользователем вентильная матрица
  12. ↑ Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright (2011) HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
  13. ↑ Ahmed S. J. Abu Hammad (2019) Implementation of a Parallel K-Nearest Neighbor Algorithm Using MPI
  14. ↑ Nikos Sismanis, Nikos P. Pitsianis, Xiaobai Sun (2012) Parallel Search of k-Nearest Neighbors with Synchronous Operations
  15. ↑ Dominik Brugger (2006) Parallel Support Vector Machines
  16. ↑ Fei Sha, Yuanqing Lin, Lawrence K. Saul, Daniel D. Lee (2006) Multiplicative Updates for Nonnegative Quadratic Programming
  17. ↑ Handbook of Parallel Computing and Statistics: Parallel Algorithms for the Singular Value Decomposition
  18. ↑ ScaLAPACK — Linear Least Squares Problems

Источники информации

  1. Principles of Large-Scale Machine Learning
  2. cuBLAS library user guide
  3. Matrix multiplication on GPU using CUDA with CUBLAS
  4. A short notice on performing matrix multiplications in PyCUDA
  5. CUDA C++ Programming Guide
  6. OpenCL SGEMM tuning for Kepler
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Многопоточность_в_машинном_обучении&oldid=84919»