Почему выражение вычислений в виде умножения матриц делает их быстрее?

18

В учебнике Google MNist с использованием TensorFlow показаны вычисления, в которых один шаг эквивалентен умножению матрицы на вектор. Сначала Google показывает картинку, на которой каждое числовое умножение и сложение, которое будет использовано для выполнения вычисления, записывается полностью. Затем они показывают картину, в которой вместо этого она выражается в виде умножения матриц, утверждая, что эта версия расчета является или, по крайней мере, может быть быстрее:

Если мы запишем это как уравнения, мы получим:

скалярное уравнение

Мы можем «векторизовать» эту процедуру, превратив ее в умножение матриц и сложение векторов. Это полезно для вычислительной эффективности. (Это также полезный способ думать.)

векторное уравнение

Я знаю, что подобные уравнения обычно пишутся в формате матричного умножения специалистами по машинному обучению и, конечно, могут видеть преимущества в этом с точки зрения краткости кода или понимания математики. Чего я не понимаю, так это утверждения Google о том, что преобразование из произвольной формы в матричную форму «полезно для вычислительной эффективности»

Когда, почему и как можно добиться повышения производительности программного обеспечения, выражая вычисления в виде умножения матриц? Если бы я, как человек, рассчитывал умножение матриц во втором (основанном на матрице) изображении сам, то делал бы это последовательно, выполняя каждое из отдельных вычислений, показанных на первом (скалярном) изображении. Для меня это не что иное, как две записи для одной и той же последовательности вычислений. Почему это отличается от моего компьютера? Почему компьютер сможет выполнять матричные вычисления быстрее, чем скалярные?

Марк Эмери
источник

Ответы:

19

Это может показаться очевидным, но компьютеры не выполняют формулы , они выполняют код , и время, которое занимает это выполнение, напрямую зависит от кода, который они выполняют, и только косвенно, от любой концепции, которую реализует этот код. Два логически идентичных фрагмента кода могут иметь очень разные характеристики производительности. Некоторые причины, которые могут возникнуть при умножении матриц, в частности:

  • Использование нескольких потоков. Практически нет современных ЦП, которые бы не имели многоядерных процессоров, у многих - до 8, а на специализированных машинах для высокопроизводительных вычислений можно было бы легко использовать 64 на нескольких сокетах. Написание кода очевидным способом на обычном языке программирования использует только один из них. Другими словами, он может использовать менее 2% доступных вычислительных ресурсов компьютера, на котором он работает.
  • Использование SIMD-инструкций (сбивает с толку, это также называется «векторизация», но в ином смысле, чем в текстовых кавычках в вопросе). По сути, вместо 4 или 8 или около того скалярных арифметических инструкций, дайте ЦПУ одну инструкцию, которая выполняет арифметику для 4 или 8 или около того регистров параллельно. Это может буквально сделать некоторые вычисления (когда они совершенно независимы и подходят для набора команд) в 4 или 8 раз быстрее.
  • Разумнее использовать кеш . Доступ к памяти происходит быстрее, если они согласованы по времени и пространству , то есть последовательный доступ осуществляется к близлежащим адресам, и при двойном доступе к адресу вы получаете доступ к нему дважды в быстрой последовательности, а не с длинной паузой.
  • Использование ускорителей, таких как графические процессоры. Эти устройства очень сильно отличаются от процессоров, и их эффективное программирование - это отдельная форма искусства. Например, они имеют сотни ядер, которые сгруппированы в группы из нескольких десятков ядер, и эти группы совместно используют ресурсы - они разделяют несколько килобайт памяти, что намного быстрее, чем обычная память, и когда любое ядро ​​группы выполняет ifЗаявление все остальные в этой группе должны ждать его.
  • Распределите работу по нескольким машинам (что очень важно для суперкомпьютеров!), Что создает огромный набор новых головных болей, но, конечно, может дать доступ к значительно большим вычислительным ресурсам
  • Умные алгоритмы. Для умножения матриц простой алгоритм O (n ^ 3), должным образом оптимизированный с помощью вышеприведенных приемов, часто быстрее, чем субкубические при разумных размерах матриц, но иногда они выигрывают. Для особых случаев, таких как разреженные матрицы, вы можете написать специализированные алгоритмы.

Многие умные люди написали очень эффективный код для обычных операций линейной алгебры , используя описанные выше приемы и многое другое, и обычно даже с глупыми приемами, специфичными для платформы. Следовательно, преобразование вашей формулы в умножение матриц и последующее выполнение этих вычислений путем вызова библиотеки зрелой линейной алгебры выигрывают от этих усилий по оптимизации. Напротив, если вы просто напишите формулу очевидным образом на языке высокого уровня, машинный код, который в конечном итоге будет сгенерирован, не будет использовать все эти приемы и не будет таким быстрым. Это также верно, если вы берете матричную формулировку и реализуете ее, вызывая подпрограмму умножения наивной матрицы, которую вы написали сами (опять же, очевидным образом).

Быстрое создание кода требует работы , а зачастую и большой работы, если вы хотите получить последнюю унцию производительности. Поскольку многие важные вычисления могут быть выражены как комбинация пары операций линейной алгебры, экономически выгодно создавать высоко оптимизированный код для этих операций. Ваш единый специализированный вариант использования? Никто не заботится об этом, кроме вас, поэтому оптимизировать его не экономно.

Сообщество
источник
4

(разреженный) Умножение матрицы на вектор очень параллелизуемо. Это очень удобно, если у вас большие данные и у вас есть ферма серверов.

Это означает, что вы можете разделить матрицу и вектор на куски и позволить отдельным машинам выполнять часть работы. Затем поделитесь некоторыми своими результатами друг с другом, а затем получите окончательный результат.

В вашем примере операции будут выглядеть следующим образом

  1. установить сетку процессоров, каждый из которых содержит Wx, y в соответствии с их координатами в сетке

  2. транслировать исходный вектор вдоль каждого столбца (стоимость O(log height))

  3. есть каждый процессор для умножения локально (стоимость O(width of submatrix * heightof submatrix))

  4. свернуть результат по каждой строке, используя сумму (стоимость O(log width))

Эта последняя операция действительна, потому что сумма ассоциативна.

Это также позволяет создавать избыточность и позволяет избежать необходимости размещать всю информацию на одном компьютере.

Для маленьких матриц 4х4, как вы видите на графике, это связано с тем, что процессор имеет специальную инструкцию и регистры для выполнения этих операций.

чокнутый урод
источник
-1

Наиболее поучительным было бы сравнить производительность вашего кода с производительностью уже реализованного матричного умножения.

Всегда есть оптимизация более низкого уровня, о которой вы не задумывались, здесь вы можете найти пример:

https://simulationcorner.net/index.php?page=fastmatrixvector

ThePunisher
источник