Изменения

* Параллелизм на уровне инструкций (англ. 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 машинном обучении ===== Параллелизм для ускорения линейной алгебры. ===

Иногда необходимо выполнить операцию с объектам имеющими разнаю размерностьНекоторые действия, выполняемые в цикле, но которые можно привести к одной записать как операции над матрицами, полученными повторением матриц меньшей размерности повторением одного из объектов вдоль одной или нескольких осей. Например, если нужно прибавить к сложение каждой строке строки матрицы вектор или домножить вектор на числос вектором {{---}} это сложение двух матриц, в одной из которых повторяются строки. В таком случае можно не писать цикл в явном видеБродкастинг (англ. 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 операциинеявно приводя их к одной. При этом из пользовательского кода исчезают циклы, а задача оптимизации переходит к разработчику библиотеки, который может обеспечить лучший параллелизм операций за счет доступа к внутренностям библиотеки.

* Broadcast операции Бродкастинг вместо циклов.* Распараллеленные реализации некоторых специальных операций (таких как свертки для [[Сверточные нейронные сети | CNNсверточных сетей]]).

* 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) {

Пример перемножения матриц на питоне с использованием PyCUDA:

Наивная реализация перемножения матриц на OpenCL:

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

Второй подход {{---}} запись алгоритма через матричные операции, которые легко параллелизируемы, например, можно обновлять вектор из оптимизируемых параметров через домножение умножение на матрицы<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>.