118
правок
Изменения
Нет описания правки
Следует выделить следующие виды параллелизма:
* Параллелизм на уровне инструкций 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>): несколько инструкций исполняются одновременно.* Параллелизм типа одна инструкция множество данных (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 ==
Фреймворки машинного обучения, такие как TensorFlow, PyTorch и MxNet используют эти возможности через библиотеки от компаний производителей графических ускорителей и открытые фреймворки:
* CUDA<ref>[https://developer.nvidia.com/cuda-toolkit CUDA]</ref> — язык параллельного программирования/вычислительная платформа для вычислений общего назначения на графическом процессоре* cuBLAS<ref>[https://developer.nvidia.com/cublas cuBLAS]</ref> — библиотека представляет собой реализацию BLAS (базовых подпрограмм линейной алгебры) поверх среды выполнения CUDA.* OpenCL<ref>[https://www.khronos.org/opencl/ OpenCL]</ref>— фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA
Пример перемножения матриц на cuBLAS
Можно запустить внешний цикл [[Стохастический градиентный спуск|стохастического градиентного спуска (SGD)]] параллельно в пуле потоков и использовать конструкции синхронизации, такие как блокировки, чтобы предотвратить состояние гонки. Однако из-за накладных расходов на синхронизацию ускорение может получиться маленьким.
Еще более интересная идея называется асинхронным SGD или HogwildA Lock-Free Approach to Parallelizing Stochastic Gradient Descent<ref>[https://arxiv.org/abs/1106.5730 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 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 Parallel Search of k-Nearest Neighbors with Synchronous Operations]</ref>.
=== Параллелизм в методе опорных веторов ===
Вычислительная сложность [[Метод опорных векторов (SVM)|метода опорных векторов]] заключается в минимизации квадратичной функции.
Первый вариант распараллеливания задачи — добавление параллелизма в алгоритм в явном виде, например, параллельная оптимизация большего количества переменных в SMOParallel Support Vector Machines<ref>[https://publikationen.uni-tuebingen.de/xmlui/bitstream/handle/10900/49015/pdf/tech_21.pdf Parallel Support Vector Machines]</ref>. Второй подход — запись алгоритма через матричные операции, которые легко параллелизируемыMultiplicative Updates for Nonnegative Quadratic Programming<ref>[https://www.researchgate.net/publication/6265163_Multiplicative_Updates_for_Nonnegative_Quadratic_Programming Multiplicative Updates for Nonnegative Quadratic Programming]</ref>.
==См. также==
*[[Стохастический градиентный спуск]]
