Изменения
→Параллелизм для ускорения линейной алгебры: Переписан параграф про бродкастинг
Для применения машинного обучения на практике часто нужно обработать большое количество данных и на это уходит много времени. Использование многопоточности и других видов параллелизма позволяет значительно ускорить вычисления, иногда даже без изменения самого алгоритма.
Следует выделить следующие виды параллелизма:
* Параллелизм на уровне инструкций (англ. instruction-level parallelism, ILP<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D0%B8%D0%B7%D0%BC_%D0%BD%D0%B0_%D1%83%D1%80%D0%BE%D0%B2%D0%BD%D0%B5_%D0%BA%D0%BE%D0%BC%D0%B0%D0%BD%D0%B4 ILP]</ref>): запускать несколько инструкций исполняются одновременно.* Параллелизм типа одна инструкция множество данных(англ. single instruction, multiple data, SIMD<ref>[https://ru.wikipedia.org/wiki/SIMDSIMD]</ref>): одна инструкция работает с вектором чиселоперация применяется к множеству данных.
* Многопоточный параллелизм: несколько независимых рабочих потоков взаимодействуют через абстракцию совместно используемой памяти.
* Распределенные вычисления: несколько независимых рабочих компьютеров взаимодействуют по сети(MLlib<ref>[https://spark.apache. (org/mllib/ MLlib ]</ref> на Spark, Mahout <ref>[https://mahout.apache.org/ Mahout]</ref> на Hadoop).
== Идеи используемые для ускорения вычислений в ML машинном обучении ===== Параллелизм для ускорения линейной алгебры. ===Мы можем значительно повысить производительность, создав ядра Многие операции линейной алгебры (, например, умножение матриц, векторное сложение , произведение матриц и твычисление нормы состоят из большого количества независимых операций.д.)Поэтому можно сильно повысить их производительность как за счёт ILP и SIMD параллелизма для маленьких данных, которые используют параллелизм так и за счёт многопоточности для больших данных. От ускорения линейной алгебры особенно выигрывают нейронные сети, так как большую часть времени их работызанимает умножение матриц. Поскольку умножение Некоторые действия, выполняемые в цикле, можно записать как операции над матрицами, полученными повторением матриц занимает большую часть времени обучения нейронных сетейменьшей размерности. Например, сложение каждой строки матрицы с вектором {{---}} это может привести сложение двух матриц, в одной из которых повторяются строки. Бродкастинг (англ. broadcasting<ref>[https://numpy.org/doc/stable/user/basics.broadcasting.html Broadcasting {{---}} NumPy v1.19 Manual]</ref><ref>[https://octave.org/doc/v6.1.0/Broadcasting.html Broadcasting (GNU Octave (version 6.1.0))]</ref>) позволяет выполнять операции с аргуметами разных размерностей, неявно приводя их к значительному сквозному ускорению обучающего конвейераодной. В основе этого лежит параллелизм ILPПри этом из пользовательского кода исчезают циклы, SIMD а для больших матриц также задача оптимизации переходит к разработчику библиотеки, который может использоваться многопоточностьобеспечить лучший параллелизм операций за счет доступа к внутренностям библиотеки.
Примеры оптимизаций:
* Высоко оптимизированные тензорные библиотеки для арифметики.
* Алгоритмы в терминах матричных операций, а не векторных операций, насколько это возможно.
* Broadcast операции, а не циклыБродкастинг вместо циклов.* Распараллеленные реализации некоторых специальных операций (таких как свертки для [[Сверточные нейронные сети | CNNсверточных сетей]]). ==== Параллелизм broadcast операций ====Просмотрите код наивной реализации поэлементное произведение двух векторов на Python def elementwise_product(x, y): assert(len(x) == len(y)) z = numpy.zeros(len(x)) for i in range(len(x)): z[i] = x[i] * y[i] return z Такой код лучше заменять на broadcast операции из numpy, которые выигрывают от векторизации и ILP. Также такой код может быть легко распараллелен для больших векторов
=== Параллелизм в оптимизации гиперпараметров ===
Такая оптимизации часто встречаются в библиотеках машинного обучения.
=== Параллелизм [[Кросс-валидация | кросс-валидации]] ===Полная [[Кросс-валидация | кросс-валидация]], k-fold, t×k-fold, Leave-One-Out легко распараллеливаются на несколько потоков, каждый из которых работает на своем разбиении данных
[[Файл:ParallelCrossValidation.png|500px]]
=== Параллелизм GPU <ref>[https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D1%80 GPU]</ref> ===Типичное число потоков обработки графического процессора - десятки тысяч, что позволяет вычислять Графические процессоры позволяют применять одну и ту же операцию параллельно на множестве к десяткам тысяч элементовза счет большого числа потоков.
Фреймворки машинного обучения, такие как TensorFlow, PyTorch и MxNet используют эти возможности через библиотеки от компаний производителей графических ускорителей и открытые фреймворки:
* [https://developer.nvidia.com/cublas cuBLAS] - библиотека от Nvidia позволяющая эффективно перемножать матрицы.* CUDA<ref>[https://developer.nvidia.com/cuda-toolkit CUDA] </ref> {{- --}} язык параллельного программирования/вычислительная платформа для вычислений общего назначения на графическом процессоре* cuBLAS<ref>[https://developer.nvidia.com/cublas cuBLAS]</ref> {{---}} библиотека представляет собой реализацию базовых подпрограмм линейной алгебры (англ. Basic Linear Algebra Subprograms, BLAS) поверх среды выполнения CUDA.* OpenCL<ref>[https://www.khronos.org/opencl/ OpenCL] </ref> {{-- -}} фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также программируемых пользователем вентильных матрицах (ППВМ, англ. field-programmable gate array, FPGA<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D1%83%D0%B5%D0%BC%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D0%B5%D0%BC_%D0%B2%D0%B5%D0%BD%D1%82%D0%B8%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0 Программируемая пользователем вентильная матрица]</ref>).
Пример перемножения матриц на C с использованием cuBLAS: <font color="#B00040">void</font> <font color="#0000FF">gpu_blas_mmul</font>(cublasHandle_t &handle, <font color="#008000">'''const'''</font> <font color="#B00040">float</font> *A, <font color="#008000">'''const'''</font> <font color="#B00040">float</font> *B, <font color= Параллелизм SGD "#B00040">float</font> *C, <font color="#008000">'''const'''</font> <font color="#B00040">int</font> m, <font color="#008000">'''const'''</font> <font color="#B00040">int</font> k, <font color="#008000">'''const'''</font> <font color="#B00040">int</font> n) {Запускаем внешний цикл [[Стохастический градиентный спуск|SGD]] параллельно в пуле потоков и используем конструкции синхронизации <font color="#B00040">int</font> lda = m, такие как блокировкиldb = k, чтобы предотвратить состояние гонки. Но это может работать медленно из-за накладных расходов на синхронизацию. ldc = m; <font color="#008000">'''const'''</font> <font color="#B00040">float</font> alf = 1; <font color="#008000">'''const'''</font> <font color="#B00040">float</font> bet = 0; <font color="#008000">'''const'''</font> <font color="#B00040">float</font> *alpha = &alf; <font color="#008000">'''const'''</font> <font color="#B00040">float</font> *beta = &bet; <font color="#408080">''// Do the actual multiplication''</font> cublasSgemm(handle, CUBLAS_OP_N, CUBLAS_OP_N, m, n, k, alpha, A, lda, B, ldb, beta, C, ldc); }
Наивная реализация перемножения матриц на OpenCL:
<font color="#408080">''// First naive implementation''</font>
__kernel <font color="#B00040">void</font> myGEMM1(<font color="#008000">'''const'''</font> <font color="#B00040">int</font> M, <font color="#008000">'''const'''</font> <font color="#B00040">int</font> N, <font color="#008000">'''const'''</font> <font color="#B00040">int</font> K,
<font color="#008000">'''const'''</font> __global <font color="#B00040">float</font> *A,
<font color="#008000">'''const'''</font> __global <font color="#B00040">float</font> *B,
__global <font color="#B00040">float</font> *C) {
<font color="#408080">''// Thread identifiers''</font>
<font color="#008000">'''const'''</font> <font color="#B00040">int</font> globalRow = get_global_id(0); <font color="#408080">''// Row ID of C (0..M)''</font>
<font color="#008000">'''const'''</font> <font color="#B00040">int</font> globalCol = get_global_id(1); <font color="#408080">''// Col ID of C (0..N)''</font>
<font color="#408080">''// Compute a single element (loop over K)''</font>
<font color="#B00040">float</font> acc = 0.0f;
<font color="#008000">'''for'''</font> (<font color="#B00040">int</font> k = 0; k < K; k++) {
acc += A[k * M + globalRow] * B[globalCol * K + k];
}
<font color="#408080">''// Store the result''</font>
C[globalCol * M + globalRow] = acc;
}
=== Параллелизм в стохастическом градиентном спуске ===
Можно запустить внешний цикл [[Стохастический градиентный спуск|стохастического градиентного спуска (SGD)]] параллельно в пуле потоков и использовать конструкции синхронизации, такие как блокировки, чтобы предотвратить состояние гонки. Однако из-за накладных расходов на синхронизацию ускорение может получиться маленьким.
Еще более интересная идея называется асинхронным SGD или Hogwild<ref>[https://arxiv.org/abs/1106.5730 Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright (2011) HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent]</ref>.
SGD запускается параллельно в несколько потоков без какой-либо синхронизации. Теперь состояния гонки могут возникнуть, но во многих случаях это хорошо, потому что они просто немного изменяют шум и ошибки уже присутствующие из-за случайного выбора градиента.
=== Параллелизм в методе k ближайших соседей ===
Основное время работы [[Метрический классификатор и метод ближайших соседей|метода k ближайших соседей]] составляет поиск ближайших соседей.
Так как расстояния до разных объектов независимы, то можно разбить объекты на группы, параллельно решить задачу во всех группах, а потом объединить результат<ref>[http://ceres-journal.eu/download.php?file=2019_01_01.pdf Ahmed S. J. Abu Hammad (2019) Implementation of a Parallel K-Nearest Neighbor Algorithm Using MPI]</ref>.
Альтернативный подход {{---}} параллельная сортировка всех объектов, например, с использованием битонной сортировки<ref>[https://users.cs.duke.edu/~nikos/reprints/knn-TR-CS-2012-03.pdf Nikos Sismanis, Nikos P. Pitsianis, Xiaobai Sun (2012) Parallel Search of k-Nearest Neighbors with Synchronous Operations]</ref>.
=== Параллелизм в методе опорных векторов ===
Вычислительная сложность [[Метод опорных векторов (SVM)|метода опорных векторов]] заключается в минимизации квадратичной функции.
Первый вариант распараллеливания задачи {{---}} добавление параллелизма в алгоритм в явном виде, например, параллельная оптимизация большего количества переменных в SMO<ref>[https://publikationen.uni-tuebingen.de/xmlui/bitstream/handle/10900/49015/pdf/tech_21.pdf Dominik Brugger (2006) Parallel Support Vector Machines]</ref>.
Второй подход {{---}} запись алгоритма через матричные операции, которые легко параллелизируемы, например, можно обновлять вектор из оптимизируемых параметров через умножение на матрицы<ref>[https://www.researchgate.net/publication/6265163_Multiplicative_Updates_for_Nonnegative_Quadratic_Programming Fei Sha, Yuanqing Lin, Lawrence K. Saul, Daniel D. Lee (2006) Multiplicative Updates for Nonnegative Quadratic Programming]</ref>.
=== Параллелизм в линейной регрессии ===
При использовании [[Линейная регрессия | метода наименьших квадратов]] поиск коэффициентов регрессии сводится к нахождению псевдообратной матрицы. Хотя псевдообратную матрицу можно вычислить через обратную и для этого существуют параллельные алгоритмы, такой подход остается непрактичным. Более популярный способ, основанный на сингулярном разложении, можно сделать параллельным, если в процессе использовать метод Якоби для собственных значений и на каждом шаге обрабатывать несколько строк и столбцов<ref>[https://www.irisa.fr/sage/bernard/publis/SVD-Chapter06.pdf Handbook of Parallel Computing and Statistics: Parallel Algorithms for the Singular Value Decomposition]</ref>. Также можно использовать параллельный алгоритм для QR-разложения как это сделано в ScaLAPACK<ref>[https://web.archive.org/web/20181004072955/http://www.netlib.org/scalapack/slug/node45.html#1004 ScaLAPACK {{---}} Linear Least Squares Problems]</ref>.
==См. также==
*[[Стохастический градиентный спуск]]
*[[Кросс-валидация]]
*[[Настройка гиперпараметров]]
*[[Метод опорных векторов (SVM)]]
*[[Метрический классификатор и метод ближайших соседей]]
== Примечания ==
<references/>
== Источники информации ==
# [http://www.cs.cornell.edu/courses/cs4787/2019sp/notes/lecture1.pdf Principles of Large-Scale Machine Learning]
# [https://docs.nvidia.com/cuda/pdf/CUBLAS_Library.pdf cuBLAS library user guide]# [https://solarianprogrammer.com/2012/05/31/matrix-multiplication-cuda-cublas-curand-thrust/ Matrix multiplication on GPU using CUDA with CUBLAS]# [https://medium.com/@CIulius/a-short-notice-on-performing-matrix-multiplications-in-pycuda-cbfb00cf1450 A short notice on performing matrix multiplications in PyCUDA]# [https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html CUDA C++ Programming Guide]# [https://cnugteren.github.io/tutorial/pages/page1.html OpenCL SGEMM tuning for Kepler]
[[Категория: Машинное обучение]]
