10
правок
Изменения
Ссылки и оформление
Следует выделить следующие виды параллелизма:
* Параллелизм на уровне инструкций ([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]): несколько инструкций исполняются одновременно.* Параллелизм типа одна инструкция множество данных ([https://ru.wikipedia.org/wiki/SIMD SIMD]): одна операция применяется к множеству данных
* Многопоточный параллелизм: несколько независимых рабочих потоков взаимодействуют через абстракцию совместно используемой памяти.
* Распределенные вычисления: несколько независимых рабочих компьютеров взаимодействуют по сети. ([https://spark.apache.org/mllib/ MLlib ] на Spark, [https://mahout.apache.org/ Mahout ] на Hadoop)
== Идеи используемые для ускорения вычислений в ML ==
Такая оптимизации часто встречаются в библиотеках машинного обучения.
=== Параллелизм [[Кросс-валидация | кросс-валидации]] ===Полная [[Кросс-валидация | кросс-валидация]], k-fold, t×k-fold, Leave-One-Out легко распараллеливаются на несколько потоков, каждый из которых работает на своем разбиении данных
[[Файл:ParallelCrossValidation.png|500px]]
Фреймворки машинного обучения, такие как TensorFlow, PyTorch и MxNet используют эти возможности через библиотеки от компаний производителей графических ускорителей и открытые фреймворки:
* [https://developer.nvidia.com/cuda-toolkit CUDA] - — язык параллельного программирования/вычислительная платформа для вычислений общего назначения на графическом процессоре* [https://developer.nvidia.com/cublas cuBLAS] - — библиотека представляет собой реализацию BLAS (базовых подпрограмм линейной алгебры) поверх среды выполнения CUDA.* [https://www.khronos.org/opencl/ OpenCL] - — фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA
Пример перемножения матриц на cuBLAS
Можно запустить внешний цикл [[Стохастический градиентный спуск|стохастического градиентного спуска (SGD)]] параллельно в пуле потоков и использовать конструкции синхронизации, такие как блокировки, чтобы предотвратить состояние гонки. Однако из-за накладных расходов на синхронизацию ускорение может получиться маленьким.
Еще более интересная идея называется асинхронным SGD или Hogwild<ref>[https://arxiv. org/abs/1106.5730 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 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 Parallel Search of k-Nearest Neighbors with Synchronous Operations]</ref>.
=== Параллелизм в методе опорных веторов ===
Вычислительная сложность метода опорных векторов заключается в минимизации квадратичной функции. Первый вариант распараллеливания задачи - — добавление параллелизма в алгоритм в явном виде, например, параллельная оптимизация большего количества переменных в SMO<ref>[https://publikationen.uni-tuebingen.de/xmlui/bitstream/handle/10900/49015/pdf/tech_21.pdf Parallel Support Vector Machines]</ref>. Второй подход - — запись алгоритма через матричные операции, которые легко параллелизируемы<ref>[https://www.researchgate.net/publication/6265163_Multiplicative_Updates_for_Nonnegative_Quadratic_Programming Multiplicative Updates for Nonnegative Quadratic Programming]</ref>.
== Источники информации ==
