Изменения
Исправление замечаний
Для применения машинного обучения на практике часто нужно обработать большое количество данных и на это уходит много времени. Использование многопоточности и других видов параллелизма позволяет значительно ускорить вычисления, иногда даже без изменения самого алгоритма.
Следует выделить следующие виды параллелизма:
* Параллелизм на уровне инструкций (англ. 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 операции<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 операции вместо циклов.
* Распараллеленные реализации некоторых специальных операций (таких как свертки для [[Сверточные нейронные сети | 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;
}
Пример перемножения матриц на питоне с использованием 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">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,
Альтернативный подход {{---}} параллельная сортировка всех объектов, например, с использованием битонной сортировки<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>.
==См. также==
