Разреженные матрицы: как ученые ускорили машинное обучение на GPU
В начале декабря исследователи из OpenAI представили библиотеку инструментов, которая поможет ускорить обучение нейронных сетей на GPU от Nvidia за счет использования разреженных матриц. О том, с какими трудностями сталкиваются разработчики нейронных сетей и в чем основная идея решения от OpenAI, расскажем далее.
/ фото alantankenghoe CC
Трудности тренировки крупных нейронных сетей на GPU
Графические процессоры (GPU) лучше подходят для машинного обучения, чем центральные процессоры (CPU). Технические особенности помогают GPU выполнять одновременно множество матричных операций, которые используются для обучения нейронных сетей.
Чтобы добиться схожего результата на центральном процессоре, придется выстроить инфраструктуру из нескольких кластеров CPU, что очень дорого. Система Google для тренировки нейросетей на CPU стоила порядка 5 млрд долларов. Сегодня ученые из Стэнфорда построили систему с аналогичной вычислительной мощностью на GPU всего за 33 тыс. долларов.
Однако здесь есть трудности: использовать весь потенциал GPU на ресурсоемких задачах не так просто. Для обработки данные должны храниться в памяти GPU, однако её объем невелик, что затрудняет тренировку крупных моделей. Например, модель VGG-16 требует около 14 ГБ, в то время как объем памяти Nvidia Titan X составляет 12 ГБ. И эту карту Nvidia позиционирует как один из самых мощных GPU для глубокого обучения.
Как верно заметил EvilGenius18 в комментариях, 7 декабря компания Nvidia представила новую карту Titan V на архитектуре Volta. Она обладает вычислительной мощностью 110 TFLOPS на задачах глубокого обучения, что в 9 раз больше, чем у предшественницы.
При этом для эффективной тренировки крупных моделей нейронных сетей используют различные подходы. Один из них — обработка данных на графическом процессоре последовательными партиями, когда CPU выступает временным контейнером. Минус такого подхода — расходование ресурсов на перенос данных.
Возможно одновременное использование нескольких графических процессоров, но количество GPU на одном компьютере ограничено, поэтому требуется высокоскоростное соединение между вычислительными системами. Межкомпьютерный канал связи сказывается на скорости обучения, поскольку машины в таком случае тратят больше времени на «общение», чем на вычисления.
Есть и еще одно решение, которое применяется в машинном обучении для оптимизации, — разреженные матрицы. Это матрицы, которые в основном содержат нулевые элементы. Преимущество заключается в том, что нули в матричных операциях воспринимаются как пустые компоненты. Поэтому такие матрицы расходуют меньше памяти графического процессора. Это ускоряет процедуру машинного обучения, что важно для больших моделей.
Но есть проблема: решения Nvidia, главного поставщика GPU, не поддерживают работу с разреженными матрицами. Но в OpenAI нашли выход из этой ситуации.
Решение от OpenAI
Команда OpenAI разработала программное обеспечение, которое моделирует работу крошечных ядер, способных взаимодействовать с такими матрицами. Ядра опробовали на обучении сетей, анализирующих обзоры на сайтах Amazon и IMDB. Как сообщает команда, уровень ошибок в работе со сводом данных IMDB был снижен с 5,91% до 5,01%.
Ядра реализованы с использованием CUDA, программно-аппаратной архитектуры параллельных вычислений от Nvidia. Но модель OpenAI пока доступна только для TensorFlow. Скотт Грей (Scott Gray), член команды Open AI, сказал, что решение может быть распространено на другие архитектуры, кроме Google TPU2. Компания Nvidia уже знает о работе OpenAI и готова оптимизировать свои системы.
Альтернативные проекты
Концепция разреженных матриц получила свое воплощение в компиляторе с открытым исходным кодом под названием Taco. О проекте, над которым работает команда ученых из Массачусетского технологического института в партнерстве с Adobe Research, стало известно в ноябре. Разработчики искали способ автоматизировать процесс обработки чисел в разреженных матрицах. И использовали для этого тензоры.
О своих разработках в области машинного обучения в декабре отчиталась и компания IBM. Решение ИТ-гиганта — DuHL — предлагает новый метод переноса данных с CPU на GPU. Основная задача технологии — определить, какая информация наиболее важна для алгоритма обучения, и передать её сети в правильном порядке. Исследования показали, что новый подход на основе DuHL в 10 раз быстрее по сравнению с классическим методом последовательной передачи данных между процессорами. Следующая цель компании — предложить DuHL как услугу в облаке.
Но в IBM не первыми придумали переносить GPU-вычисления в облако. Подобные проекты, работающие в том числе по модели IaaS, уже известны. Изначально услугу vGPU предоставляла компания Nvidia. Сейчас этим занимаются и AMD, и Intel.
Об OpenAI
OpenAI — это некоммерческая исследовательская организация, основанная главой Tesla Илоном Маском. Она ставит своей задачей продвижение и развитие искусственного интеллекта на благо человечества. Организация плотно сотрудничает с другими учреждениями и исследователями, предоставляя открытый доступ к своим разработкам.
Разреженная матрица
Разреженная матрица — это матрица с преимущественно нулевыми элементами.
Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разреженной. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов [1] :
- есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
- в каждой строке не превышает 10 в типичном случае;
- ограничено
. - таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей [1] .
По существу, разреженность соответствует системам со слабыми связями. Можно представить линию шариков, соединенных один за другим пружинками — это пример разреженной системы. Для контраста, если эти же шарики будут соединены пружинками каждый с каждым, то такая система будет представлять собой плотную матрицу. Термин разреженности используется также в комбинаторике и таких прикладных областях как сетевой анализ, при определении малой плотности значимых данных или соединений [источник не указан 70 дней] .
Огромные разреженные матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.
При хранении и преобразовании разреженных матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разреженную структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, работают относительно медленно и требуют значительных объёмов памяти, когда применяются к большим разреженным матрицам. Разреженные данные по природе своей легко сжимаются, а учёт разреженности часто [источник не указан 70 дней] приводит к уменьшению требований к компьютерной памяти.
Содержание
Представление
Алгоритмы
Применение
Библиотеки программ
Для вычислений с разреженными матрицами создано несколько библиотек:
- SparseLib++ (C++) [2]
- uBLAS (C++, в составе Boost) [3]
- SPARSPAK (Fortran) [4]
- CSparse (C) [5]
Примечания
- ↑ 12Писсанецки, 1988, Введение
- ↑SparseLib++
- ↑uBLAS / Boost
- ↑Alan George, Esmond Ng A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — ISBN 978-1-4503-0245-6. — DOI:10.1145/1057931.1057933
- ↑T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006
Литература
- Reginald P. Tewarson Sparse Matrices. — Academic Press, 1973. — 160 с. — ISBN 0126856508 перевод: Тьюарсон Р. Разреженные матрицы = Sparse Matrices. — М .: Мир, 1977. — 191 с.
- Писсанецки С. Технология разреженных матриц = Sparse Matrix Technology. — М .: Мир, 1988. — 410 с. — ISBN 5-03-000960-4
- Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М .: Мир, 1984. — 333 с.
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
- Комбинаторика
- Типы матриц
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое «Разреженная матрица» в других словарях:
разреженная матрица — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN sparse matrix … Справочник технического переводчика
РАЗРЕЖЕННАЯ МАТРИЦА — матрица с малым числом ненулевых элементов. Системы линейных уравнений с такими матрицами возникают, в частности, при аппроксимации дифференциальных уравнений конечноразностными или вариационно разностными. Н. С. Бахвалов … Математическая энциклопедия
Матрица линейного оператора — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
Квадратная матрица — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
Список матриц — Структура матрицы Здесь собраны наиболее важные классы матриц, используемые в математике, науке (в целом) и прикладной науке (в частности). Под матрицей понимается прямоугольный массив чисел … Википедия
Перемножение матриц — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
Произведение матриц — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
Произведение матрицы на число — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
Разница матриц — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
Симплекс-метод — Не путать с «симплекс методом» методом оптимизации произвольной функции. См. Метод Нелдера Мида Симплекс метод алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в… … Википедия
Разреженная матрица
В численном анализе и научных вычислений , A разреженная матрица или разреженный массив является матрица , в которой большинство элементов равны нулю. [1] Не существует строгого определения того, сколько элементов должно быть нулевым, чтобы матрица считалась разреженной, но общий критерий состоит в том, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов отличны от нуля, матрица считается плотной . [1] Количество элементов с нулевым знаком, деленное на общее количество элементов (например, m × n для матрицы m × n), иногда называют разреженным матрицы.
Концептуально разреженность соответствует системам с небольшим количеством парных взаимодействий. Например, рассмотрим линию шаров, соединенных пружинами от одного к другому: это разреженная система, поскольку связаны только соседние шары. Напротив, если бы одна и та же линия шаров имела пружины, соединяющие каждый шар со всеми другими шарами, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ , которые обычно имеют низкую плотность важных данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных .
При хранении и манипулировании разреженными матрицами на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Специализированные компьютеры были созданы для разреженных матриц [2], поскольку они распространены в области машинного обучения. [3] Операции с использованием стандартных структур и алгоритмов с плотной матрицей являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. . Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов плотных матриц.
СОДЕРЖАНИЕ
Хранение разреженной матрицы [ править ]
Матрица обычно хранится как двумерный массив. Каждая запись в массиве представляет собой элемент a i , j матрицы и доступна по двум индексам i и j . Обычно i — это индекс строки, пронумерованный сверху вниз, а j — индекс столбца, пронумерованный слева направо. Для матрицы размером m × n объем памяти, необходимый для хранения матрицы в этом формате, пропорционален m × n (без учета того факта, что размеры матрицы также должны быть сохранены).
В случае разреженной матрицы существенное сокращение требований к памяти может быть реализовано путем сохранения только ненулевых элементов. В зависимости от количества и распределения ненулевых записей могут использоваться разные структуры данных, что дает огромную экономию памяти по сравнению с базовым подходом. Компромисс заключается в том, что доступ к отдельным элементам становится более сложным, и требуются дополнительные структуры, чтобы иметь возможность однозначно восстановить исходную матрицу.
Форматы можно разделить на две группы:
- Те, которые поддерживают эффективную модификацию, например DOK (Словарь ключей), LIL (Список списков) или COO (Список координат). Обычно они используются для построения матриц.
- Те, которые поддерживают эффективный доступ и матричные операции, такие как CSR (сжатая разреженная строка) или CSC (сжатый разреженный столбец).
Словарь ключей (DOK) [ править ]
ДОК состоит из словаря , который отображает (строка, столбец) — пары к значению элементов. Элементы, отсутствующие в словаре, считаются равными нулю. Формат хорош для постепенного построения разреженной матрицы в случайном порядке, но плохой для перебора ненулевых значений в лексикографическом порядке. Обычно в этом формате создается матрица, а затем преобразуется в другой, более эффективный формат для обработки. [4]
Список списков (LIL) [ править ]
LIL хранит по одному списку на строку, каждая запись содержит индекс столбца и значение. Обычно эти записи отсортированы по индексу столбца для более быстрого поиска. Это еще один формат, подходящий для построения инкрементальной матрицы. [5]
Список координат (COO) [ править ]
COO хранит список кортежей (строка, столбец, значение) . В идеале записи сортируются сначала по индексу строки, а затем по индексу столбца, чтобы сократить время произвольного доступа. Это еще один формат, который подходит для построения инкрементальной матрицы. [6]
Сжатая разреженная строка (формат CSR, CRS или Йельского университета) [ править ]
Сжатого разреженным строки (КСО) или сжатого хранения строк (СВК) или формат Йельского представляет собой матрицу M с помощью трех (одномерных массивов), которые соответственно содержат ненулевые значения, экстенты строк и столбцов индексов. Он похож на COO, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ к строке и умножение матрицы на вектор ( M x ). Формат CSR используется по крайней мере с середины 1960-х годов, а первое полное описание появилось в 1967 году [7].
Формат CSR хранит разреженную матрицу M размера m × n в виде строки с использованием трех (одномерных) массивов (V, COL_INDEX, ROW_INDEX) . Пусть NNZ обозначает число ненулевых элементов в М . (Обратите внимание, что здесь должны использоваться индексы , начинающиеся с нуля .)
- Массивы V и COL_INDEX имеют длину NNZ и содержат ненулевые значения и индексы столбцов этих значений соответственно.
- Массив ROW_INDEX имеет длину m + 1 и кодирует индекс в V и COL_INDEX, где начинается данная строка. Последний элемент — это NNZ , т. Е. Фиктивный индекс в V сразу после последнего действительного индекса NNZ — 1 . [8]
это 4 × 4 матрица с 4 ненулевых элементов, следовательно ,
предполагая язык с нулевым индексом.
Чтобы извлечь строку, мы сначала определяем:
Затем мы берем срезы из V и COL_INDEX, начиная с row_start и заканчивая row_end.
Чтобы извлечь строку 1 (вторую строку) этой матрицы, мы устанавливаем row_start=1 и row_end=2 . Затем делаем дольки V[1:2] = [8] и COL_INDEX[1:2] = [1] . Теперь мы знаем, что в строке 1 у нас есть один элемент в столбце 1 со значением 8.
В этом случае представление CSR содержит 13 элементов по сравнению с 16 в исходной матрице. Формат CSR сохраняет память только тогда, когда NNZ <( m ( n — 1) — 1) / 2 . Другой пример, матрица
это 4 × 6 матрица (24 записей) с 8 ненулевых элементов, так
Всего хранится 21 запись.
- ROW_INDEX разбивает массив V в строки: (10, 20) (30, 40) (50, 60, 70) (80) ;
- COL_INDEX выравнивает значения в столбцах: (10, 20, . ) (0, 30, 0, 40, . )(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80) .
Обратите внимание, что в этом формате первое значение ROW_INDEX всегда равно нулю, а последнее — всегда NNZ , поэтому они в некотором смысле избыточны (хотя в языках программирования, где длина массива должна быть явно сохранена, NNZ не будет избыточным). Тем не менее, это позволяет избежать необходимости обрабатывать исключительный случай при вычислении длины каждой строки, поскольку это гарантирует, что формула ROW_INDEX [ i + 1] — ROW_INDEX [ i ] работает для любой строки i . Более того, стоимость памяти этого избыточного хранилища, вероятно, незначительна для достаточно большой матрицы.
Форматы разреженных матриц Йельского университета (старые и новые) являются экземплярами схемы CSR. Старый формат Йельского университета работает точно так же, как описано выше, с тремя массивами; новый формат объединяет ROW_INDEX и COL_INDEX в единый массив и обрабатывает диагональ матрицы отдельно. [9]
Для матриц логической смежности массив данных может быть опущен, поскольку наличие записи в массиве строк достаточно для моделирования двоичного отношения смежности.
Он, вероятно, известен как Йельский формат, потому что он был предложен в отчете о пакете разреженных матриц Йельского университета 1977 года, подготовленном факультетом компьютерных наук Йельского университета. [10]
Сжатый разреженный столбец (CSC или CCS) [ править ]
CSC похож на CSR, за исключением того, что значения сначала считываются по столбцу, для каждого значения сохраняется индекс строки и сохраняются указатели столбцов. Например, CSC — это (val, row_ind, col_ptr) , где val — это массив (сверху вниз, затем слева направо) ненулевых значений матрицы; row_ind — это индексы строк, соответствующие значениям; и col_ptr — это список индексов val, с которых начинается каждый столбец. Название основано на том факте, что информация индекса столбца сжимается относительно формата COO. Обычно для построения используется другой формат (LIL, DOK, COO). Этот формат эффективен для арифметических операций, нарезки столбцов и произведений матрица-вектор. Видеть scipy.sparse.csc_matrix . Это традиционный формат для указания разреженной матрицы в MATLAB (через sparse функцию).
Особая структура [ править ]
Бандиты [ править ]
Важным специальным типом разреженных матриц является ленточная матрица , определяемая следующим образом. Нижняя полоса пропускания матрицы А является наименьшим числом р таким образом, что запись я , J обращается в нуль каждый раз , когда я > J + р . Точно так же верхняя ширина полосы — это наименьшее число p такое, что a i , j = 0 всякий раз, когда i < j — p ( Голуб и Ван Лоан 1996 , §1.2.1). Например, трехдиагональная матрица имеет нижнюю полосу пропускания 1 и верхнюю полосу пропускания 1 . В качестве другого примера следующая разреженная матрица имеет нижнюю и верхнюю полосы пропускания, равные 3. Обратите внимание, что для ясности нули представлены точками.
Матрицы с достаточно малой верхней и нижней полосой пропускания известны как матрицы полос и часто поддаются более простым алгоритмам, чем общие разреженные матрицы; или иногда можно применять алгоритмы с плотной матрицей и повысить эффективность, просто перебирая сокращенное количество индексов.
Путем переупорядочивания строк и столбцов матрицы A можно получить матрицу A ‘ с более низкой полосой пропускания. Ряд алгоритмов разработан для минимизации полосы пропускания .
Диагональ [ править ]
Очень эффективная структура для крайнего случая ленточных матриц, диагональной матрицы , заключается в хранении только элементов главной диагонали в виде одномерного массива , поэтому для диагональной матрицы размера n × n требуется только n элементов.
Симметричный [ править ]
Симметричный разреженная матрица возникает как смежности матрицы из с неориентированного графа ; его можно эффективно сохранить как список смежности .
Диагональ блока [ править ]
Блочно-диагональная матрица состоит из суб-матриц вдоль ее диагональных блоков. Блочно-диагональная матрица A имеет вид
где A k — квадратная матрица для всех k = 1, . n .
Уменьшение заполнения [ править ]
Принудительные матриц являются теми элементами , которые изменяются от начального нуля до ненулевого значения во время выполнения алгоритма. Чтобы уменьшить требования к памяти и количество арифметических операций, используемых во время алгоритма, полезно минимизировать заполнение путем переключения строк и столбцов в матрице. Символическое Cholesky разложение может быть использовано для расчета наихудших принудительный , прежде чем делать фактическое разложение Холецкого .
Существуют и другие методы, кроме разложения Холецкого . Методы ортогонализации (такие как QR-факторизация) распространены, например, при решении задач методом наименьших квадратов. Хотя теоретическая подстановка остается прежней, с практической точки зрения «ложные ненулевые значения» могут быть разными для разных методов. И символические версии этих алгоритмов могут использоваться таким же образом, как и символические версии Холецкого, для вычисления заполнения наихудшего случая.
Решение разреженных матричных уравнений [ править ]
Для решения разреженных матриц существуют итерационные и прямые методы.
Итерационные методы, такие как метод сопряженных градиентов и GMRES, используют быстрые вычисления произведений матрица-вектор , где матрица разреженная. Использование предобуславливателей может значительно ускорить сходимость таких итерационных методов. A x i <\displaystyle Ax_> A
Программное обеспечение [ править ]
Многие программные библиотеки поддерживают разреженные матрицы и предоставляют решатели для разреженных матричных уравнений. Следующие программы имеют открытый исходный код:
-
, набор алгоритмов разреженных матриц, направленных на прямое решение разреженных линейных систем. , большая библиотека C, содержащая множество различных решателей матриц для различных форматов хранения матриц. , большая библиотека C ++, с под-библиотеками, предназначенными для хранения плотных и разреженных матриц и решения соответствующих линейных систем. — это библиотека C ++, которая содержит несколько решателей разреженных матриц. Однако ни один из них не распараллелен . ( MU ltifrontal M assively P arallel sparse direct S olver), написанный на Fortran90, является фронтальным решателем . , библиотека конечных элементов, в которой также есть подбиблиотека для разреженных линейных систем и их решений. . . предоставляет удобную оболочку C ++ для BLAS и LAPACK. обеспечивает поддержку нескольких форматов разреженных матриц, линейной алгебры и решателей. R для разреженных матриц. Инструменты Wolfram Language для работы с разреженными массивами — это библиотека C ++ и C # с поддержкой разреженной линейной алгебры. Fortran 77 для диагонализации и обработки разреженных матриц с использованием алгоритма Арнольди Справочный (старый) пакет NIST для диагонализации (реальной или комплексной) разреженной матрицы Библиотека SLEPc для решения крупномасштабных линейных систем и разреженных матриц , генератор кода для конкретной предметной области и библиотека для решения линейных систем и задач квадратичного программирования.
История [ править ]
Термин разреженная матрица, возможно, был придуман Гарри Марковицем, который инициировал некоторую новаторскую работу, но затем покинул эту область. [11]