Изменения

* Параллелизм на уровне инструкций (англ. 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). == Идеи используемые для ускорения вычислений в машинном обучении ===== Параллелизм для ускорения линейной алгебры ===Многие операции линейной алгебры, например, векторное сложение, произведение матриц и вычисление нормы состоят из большого количества независимых операций. Поэтому можно сильно повысить их производительность как за счёт ILP и SIMD параллелизма для маленьких данных, так и за счёт многопоточности для больших данных. От ускорения линейной алгебры особенно выигрывают нейронные сети, так как большую часть времени их работы занимает умножение матриц.

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

=== Параллелизм 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> ===Типичное число потоков обработки графического процессора - десятки тысяч, что позволяет вычислять Графические процессоры позволяют применять одну и ту же операцию параллельно на множестве к десяткам тысяч элементовза счет большого числа потоков.

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

Пример перемножения матриц на питоне с использованием 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>

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

<font color="#408080">''// Store the result''</font>

=== Параллелизм SGD в стохастическом градиентном спуске ===Запускаем Можно запустить внешний цикл [[Стохастический градиентный спуск|стохастического градиентного спуска (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>.

Еще более интересная идея (называемая асинхронным SGD или Hogwild): Несколько потоков запускают SGD параллельно без какой-либо синхронизации=== Параллелизм в линейной регрессии ===При использовании [[Линейная регрессия | метода наименьших квадратов]] поиск коэффициентов регрессии сводится к нахождению псевдообратной матрицы. Хотя псевдообратную матрицу можно вычислить через обратную и для этого существуют параллельные алгоритмы, такой подход остается непрактичным. Теперь условия гонки могут возникнутьБолее популярный способ, но оказываетсяоснованный на сингулярном разложении, что во многих случаях это хорошоможно сделать параллельным, шумесли в процессе использовать метод Якоби для собственных значений и на каждом шаге обрабатывать несколько строк и столбцов<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>.