1632
правки
Изменения
м
Иногда необходимо выполнить операцию с объектам имеющими разнаю размерностьНекоторые действия, выполняемые в цикле, но которые можно привести к одной записать как операции над матрицами, полученными повторением матриц меньшей размерности повторением одного из объектов вдоль одной или нескольких осей. Например, если нужно прибавить к сложение каждой строке строки матрицы вектор или домножить вектор на числос вектором {{---}} это сложение двух матриц, в одной из которых повторяются строки. В таком случае можно не писать цикл в явном видеБродкастинг (англ. 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>) позволяет выполнять операции с аргуметами разных размерностей, а использовать broadcast операциинеявно приводя их к одной. При этом из пользовательского кода исчезают циклы, а задача оптимизации переходит к разработчику библиотеки, который может обеспечить лучший параллелизм операций за счет доступа к внутренностям библиотеки.
rollbackEdits.php mass rollback
Для применения машинного обучения на практике часто нужно обработать большое количество данных и на это уходит много времени. Использование многопоточности и других видов параллелизма позволяет значительно ускорить вычисления, иногда даже без изменения самого алгоритма.
Следует выделить следующие виды параллелизма:
* Параллелизм на уровне инструкций (англ. 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/SIMD SIMD]</ref>): одна операция применяется к множеству данных.
* Многопоточный параллелизм: несколько независимых рабочих потоков взаимодействуют через абстракцию совместно используемой памяти.
* Распределенные вычисления: несколько независимых рабочих компьютеров взаимодействуют по сети. (MLlib<ref>[https://spark.apache.org/mllib/ MLlib]</ref> на Spark, Mahout<ref>[https://mahout.apache.org/ Mahout]</ref> на Hadoop).
== Идеи используемые для ускорения вычислений в ML машинном обучении ===== Параллелизм для ускорения линейной алгебры. ===
Многие операции линейной алгебры, например, векторное сложение, произведение матриц и вычисление нормы состоят из большого количества независимых операций. Поэтому можно сильно повысить их производительность как за счёт ILP и SIMD параллелизма для маленьких данных, так и за счёт многопоточности для больших данных. От ускорения линейной алгебры особенно выигрывают нейронные сети, так как большую часть времени их работы занимает умножение матриц.
Примеры оптимизаций:
* Высоко оптимизированные тензорные библиотеки для арифметики.
* Алгоритмы в терминах матричных операций, а не векторных операций, насколько это возможно.
* Broadcast операции Бродкастинг вместо циклов.* Распараллеленные реализации некоторых специальных операций (таких как свертки для [[Сверточные нейронные сети | CNNсверточных сетей]]).
=== Параллелизм в оптимизации гиперпараметров ===
Фреймворки машинного обучения, такие как TensorFlow, PyTorch и MxNet используют эти возможности через библиотеки от компаний производителей графических ускорителей и открытые фреймворки:
* CUDA<ref>[https://developer.nvidia.com/cuda-toolkit CUDA]</ref> — {{---}} язык параллельного программирования/вычислительная платформа для вычислений общего назначения на графическом процессоре* cuBLAS<ref>[https://developer.nvidia.com/cublas cuBLAS]</ref> — {{---}} библиотека представляет собой реализацию BLAS (базовых подпрограмм линейной алгебры(англ. 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="#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) { <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);
}
Пример перемножения матриц на питоне с использованием PyCUDA: <font color="#008000">'''import '''</font> <font color="#0000FF">'''pycuda.gpuarray '''</font> <font color="#008000">'''as '''</font> <font color="#0000FF">'''gpuarray'''</font> <font color="#008000">'''import '''</font> <font color="#0000FF">'''numpy '''</font> <font color="#008000">'''as '''</font> <font color="#0000FF">'''np'''</font> <font color="#008000">'''import '''</font> <font color="#0000FF">'''skcuda.linalg '''</font> <font color="#008000">'''as '''</font> <font color="#0000FF">'''linalg'''</font> <font color="#408080">''# --- Initializations''</font> <font color="#008000">'''import '''</font> <font color="#0000FF">'''pycuda.autoinit'''</font>
linalg.init()
C_gpu = linalg.dot(A_gpu, B_gpu)
<font color="#008000">print</font>(np.dot(A, B)) <font color="#008000">print</font>(C_gpu)
Наивная реализация перемножения матриц на 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 A Lock-Free Approach to Parallelizing Stochastic Gradient Descent<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 ближайших соседей]] составляет поиск ближайших соседей.
Так как расстояния до разных объектов независимы, то можно разбить объекты на группы, параллельно решить задачу во всех группах, а потом объединить результат Implementation of a Parallel K-Nearest Neighbor Algorithm Using MPI<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>. Альтернативный подход — {{---}} параллельная сортировка всех объектов, например, с использованием битонной сортировки Parallel Search of k-Nearest Neighbors with Synchronous Operations<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 Parallel Support Vector Machines<ref>[https://publikationen.uni-tuebingen.de/xmlui/bitstream/handle/10900/49015/pdf/tech_21.pdf Dominik Brugger (2006) Parallel Support Vector Machines]</ref>. Второй подход — {{---}} запись алгоритма через матричные операции, которые легко параллелизируемы Multiplicative Updates for Nonnegative Quadratic Programming, например, можно обновлять вектор из оптимизируемых параметров через умножение на матрицы<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>.
==См. также==
*[[Стохастический градиентный спуск]]
