Устранив скрытую неэффективность, учёные придумали новый способ умножения больших матриц, который работает быстрее, чем когда-либо.
Учёные, занимающиеся информатикой, — это требовательная группа. Им недостаточно получить правильный ответ — цель почти всегда состоит в том, чтобы получить ответ как можно эффективнее.
Возьмем, к примеру, умножение матриц или массивов чисел. В 1812 году французский математик Жак Филипп Мари Бине разработал базовый набор правил, которым мы до сих пор обучаем студентов. Это работает прекрасно, но другие математики нашли способы упростить и ускорить процесс умножения матриц. Эта задача лежит на стыке математики и информатики, и исследователи продолжают совершенствовать процесс её решения — хотя в последние десятилетия достижения были довольно скромными. С 1987 года численные улучшения в умножении матриц были «небольшими и… чрезвычайно трудными для достижения», — сказал Франсуа Ле Галль, учёный из Нагойского университета.
Теперь трое исследователей — Ран Дуань и Рэньфэй Чжоу из Университета Цинхуа и Хунсюнь Ву из Калифорнийского университета в Бёркли — сделали большой шаг вперед в решении этой извечной проблемы. По словам Ле Галля, их новые результаты, представленные в ноябре прошлого года на конференции «Основы компьютерных наук», базируются на неожиданной новой методике. Хотя само по себе улучшение было относительно небольшим, Ле Галль назвал его «концептуально бо́льшим, чем предыдущие».
Этот метод открывает ранее неизвестный и, следовательно, неиспользованный источник потенциальных улучшений, и он уже принес свои плоды: вторая статья, опубликованная в январе, основывается на первой и показывает, как можно ещё больше ускорить умножение матриц.
«Это крупный технический прорыв, — сказал Уильям Кушмаул, учёный в области теоретической информатики из Гарвардского университета. — Это самое большое улучшение в матричном умножении, которое мы видели более чем за десятилетие».
Вход в Матрицу
Это может показаться незначительной проблемой, но умножение матриц — фундаментальная вычислительная операция. Она включена в большую часть алгоритмов, которые люди используют каждый день для самых разных задач: от отображения более четкой компьютерной графики до решения логистических задач в теории сетей. И, как и в других областях вычислений, скорость имеет первостепенное значение. Даже небольшие улучшения могут в конечном итоге привести к значительной экономии времени, вычислительной мощности и денег. Но на данный момент теоретики в основном заинтересованы в том, чтобы выяснить, насколько быстрым в принципе может быть этот процесс.
Традиционный способ умножения двух матриц размером n на n — путем умножения чисел из каждой строки первой матрицы на числа в столбцах второй — требует n3 отдельных умножений. Для матриц 2 на 2 это означает 23 или 8 умножений.
В 1969 году математик Фолькер Штрассен открыл более сложную процедуру, позволяющую умножать матрицы 2 на 2 всего за семь умножений и 18 сложений. Два года спустя учёный Шмуэль Виноград продемонстрировал, что семь умножений действительно являются абсолютным минимумом для матриц 2 на 2.
Штрассен использовал ту же идею, чтобы показать, что все большие матрицы размером n на n также можно умножить менее чем за n3 шагов. Ключевым элементом этой стратегии является процедура, называемая декомпозицией. Так называют разбиение большой матрицы на последовательно меньшие подматрицы, которые в конечном итоге могут оказаться размером всего 2 на 2 или даже 1 на 1 (это просто отдельные числа).
По мнению Вирджинии Василевской Уильямс, специалиста по информатике из Массачусетского технологического института и соавтора второй статьи, причина разделения гигантского массива на крошечные части довольно проста. «Человеку трудно взглянуть на большую матрицу (скажем, порядка 100 на 100) и придумать наилучший возможный алгоритм», — сказала Василевска Уильямс. Даже матрицы 3 на 3 ещё не решены полностью. «Тем не менее можно использовать быстрый алгоритм, который уже разработан для маленьких матриц, чтобы получить быстрый алгоритм и для больших матриц».
Ключом к скорости, как определили исследователи, является сокращение количества шагов умножения, максимальное снижение показателя степени n3 (для стандартного метода). Наименьшее возможное значение, n2, по сути, равно числу шагов, необходимому только для написания ответа. Учёные называют этот показатель омегой, ω, где nω — это наименьшее количество возможных шагов, необходимых для успешного умножения двух матриц размером n на n, когда n становится очень большим. «Цель этой работы, — сказал Чжоу, который также является соавтором статьи, опубликованной в январе 2024 года, — состоит в том, чтобы увидеть, насколько близко к 2 вы можете подойти, и можно ли этого достичь в теории».
Применяем лазерный метод
В 1986 году Штрассен совершил ещё один большой прорыв, когда представил так называемый лазерный метод умножения матриц. Штрассен использовал его, чтобы установить верхнее значение омеги в 2,48. Хотя этот метод является лишь одним из этапов умножения больших матриц, он является одним из наиболее важных, поскольку исследователи продолжают его совершенствовать.
Год спустя Виноград и Дон Копперсмит представили новый алгоритм, который прекрасно дополнил лазерный метод. Эта комбинация инструментов использовалась практически во всех последующих попытках ускорить умножение матриц.
Вот упрощённый способ мышления о том, как эти различные элементы сочетаются друг с другом. Начнём с двух больших матриц A и B, которые вы хотите перемножить. Сначала вы разлагаете их на множество более мелких подматриц или блоков, как их иногда называют. Далее вы можете использовать алгоритм Копперсмита и Винограда в качестве своего рода инструкции по обработке и, в конечном итоге, сборке блоков. «Он говорит мне, что умножать, что добавлять и какие записи куда направлять в итоговой матрице C, — сказала Василевска Уильямс. — Это просто рецепт создания C из A и B».
Однако есть одна загвоздка: иногда у вас возникают блоки, имеющие общие записи. Оставить их в результате было бы всё равно, что посчитать эти записи дважды, поэтому вам нужно избавиться от этих дублирующихся записей, называемых перекрытиями. Исследователи делают это, «убивая» блоки, в которых они находятся, — устанавливая их компоненты равными нулю, чтобы исключить их из расчета.
Вот здесь-то и вступает в действие лазерный метод Штрассена. «Лазерный метод обычно работает прекрасно и как правило находит хороший способ уничтожить подмножество блоков, чтобы устранить перекрытие», — сказал Ле Галль. После того, как лазер устранил или «сжёг» все перекрытия, вы можете построить конечную матрицу C.
Объединение этих методов приводит к алгоритму умножения двух матриц с небольшим количеством умножений в целом — по крайней мере, в теории. Лазерный метод не претендует на практичность; это просто способ подумать об идеальном процессе умножения матриц. «Мы никогда не запускаем этот метод на компьютере, — сказал Чжоу. — Мы его анализируем».
И именно этот анализ привёл к самому большому улучшению омеги за более чем десятилетие.
Обнаруженная потеря
В статье, опубликованной прошлым летом Дуанем, Чжоу и Ву, показано, что процесс Штрассена всё ещё можно значительно ускорить. Всё это произошло из-за концепции, которую они назвали скрытой потерей, заложенной глубоко в предыдущих анализах — «результате непреднамеренного уничтожения слишком большого количества блоков», — сказал Чжоу.
Лазерный метод заключается в маркировке перекрывающихся блоков как мусора, предназначенного для утилизации; остальные блоки считаются ценными и сохраняются. Однако процесс отбора несколько рандомизирован. Блок, оценённый как мусор, на самом деле может оказаться полезным. Это не было полной неожиданностью, но, изучив многие из этих случайных вариантов, команда Дуана определила, что лазерный метод систематически недооценивает блоки: нужно сохранять больше блоков и меньше выбрасывать. И, как это обычно бывает, меньше отходов приводит к большей эффективности.
«Возможность хранить больше блоков без перекрытия приводит к… более быстрому алгоритму умножения матриц», — сказал Ле Галль.
Доказав существование этой потери, команда Дуана изменила способ маркировки блоков лазерным методом, существенно сократив количество отходов. В результате они установили новую верхнюю границу омеги на отметке в 2,371866 — улучшение по сравнению с предыдущей верхней границей в 2,3728596, установленной в 2020 году Джошем Алманом и Василевской Уильямс. Это может показаться скромным изменением: граница снижается примерно на 0,001. Но это самое большое улучшение, которое учёные наблюдали с 2010 года. Для сравнения: результат Василевской Уильямс и Алмана за 2020 год улучшился по сравнению с его предшественником только на 0,00001.
Но больше всего исследователей волнует не новый рекорд, который просуществовал недолго. Важнее то , что эта статья открыла новый путь к улучшению, который до этого оставался совершенно незамеченным. По словам Ле Галля, на протяжении почти четырех десятилетий все полагались на один и тот же лазерный метод. «А потом они обнаружили, что мы можем добиться большего».
В статье, опубликованной в январе 2024 года, этот новый подход был усовершенствован, что позволило Василевской Уильямс, Чжоу и их соавторам ещё больше сократить скрытые потери. Это привело к дополнительному улучшению верхней границы омеги, снизив ее до 2,371552. Авторы также обобщили эту же технику для улучшения процесса умножения прямоугольных (n на m) матриц — процедуры, которая находит применение в теории графов, машинном обучении и других областях.
Некоторый дальнейший прогресс в этом направлении почти неизбежен, но есть пределы. В 2015 году Ле Галль и двое его соавторов доказали, что нынешний подход — лазерный метод в сочетании с алгоритмом Копперсмита-Винограда — не может дать омегу ниже 2,3078. Чтобы внести какие-либо дальнейшие улучшения, сказал Ле Галль, «необходимо улучшить первоначальный подход Копперсмита и Винограда, который практически не изменился с 1987 года». Но пока лучшего способа никто не придумал. Возможно, его даже не будет.
«Улучшение омеги на самом деле является частью понимания этой проблемы, — сказал Чжоу. — Если мы сможем хорошо понять проблему, мы сможем разработать для неё лучшие алгоритмы. И мы всё ещё находимся на самых ранних этапах понимания этой старой проблемы».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
Комментарии (50)
mahairod
21.05.2024 10:49+4Насколько я понял из статьи, эти алгоритмы не дают никакого улучшения для общего случая, т.е. когда все элементы различны.
Ну и для таких случаев обычный алгоритм будет как правило оптимизирован в техническом плане: будут учтены кэши памяти, предзагрузка, порядок элементов. Алгоритмы же, нарушающие последовательный доступ, на практике будут только снижать производительность, иногда весьма значительно.
Deosis
21.05.2024 10:49+10Статья вообще похожа на наукообразный бред:
Раньше они разбивали матрицы на блоки, часть из которых "сжигали" лазером (wtf?)
Теперь они выяснили, что если сжигать лазером меньше блоков, то умножение будет быстрее (wtf?x2)
HomoLuden
21.05.2024 10:49+7В статье вообще огромное количество воды. Вся как будто из кликбейтных тизеров состоит.
Seraphimt
21.05.2024 10:49Сжигать лазером конечно же в переносном смысле, там упомянуто, что это просто зануление блока. Почему быстрее, если меньше занулять - из текста непонятно, из других источников нашёл, что вроде как матрицу перегоняют в тензор и вот для тензоров уже есть эффективные алгоритмы перемножения. И видимо где-то тут и играет роль уменьшение сжигания.
На хабре уже была статья от 2021 года об этом, там подробнее расписано, только нет результатов последних лет, естественно.
unreal_undead2
21.05.2024 10:49Там ещё проблемы в константе перед n^<что то> (где то видел, что она в этих продвинутых алгоритмах в районе 10^500).
GospodinKolhoznik
21.05.2024 10:49+6Ну не то, чтобы прямо прорыв. Новый результат, да. Как вариант новый подход. Прорыв это что-то, за чем следует лавинообразный поток каких то других новшеств. Открытие транзистора это прорыв. Алгоритм Диффи-Хеллмана тоже прорыв. А тут как то не ощущается хлынувший на нас поток инноваций.
kovalensky
21.05.2024 10:49Вы на Хабре, тут уже давно надо было поставить маркировку на статьи с больными заголовками
plFlok
21.05.2024 10:49так есть слова-маркеры, которые говорят, что статья будет журналистской, а не технической.
типа: "энтузиаст перешёл на отечественные аналоги прорывов"
HomoLuden
21.05.2024 10:49+2Автор бы уделил побольше внимания следующим моментам:
Все эти проверки на мусорность - это же много IF? Сколько на них тратится тактов ЦП? Или мы только умножения FP считаем?
Разбитие на блоки - насколько это перспективно с точки зрения TensoFlow и пр. технологий GPGPU.
Хотя бы псевдокодом ключевые алгоритмы представили бы.
-
Без этих трёх моментов статья ну совсем вода водой. А хотелось бы пива склеивающего попу со стулом.
Seraphimt
21.05.2024 10:49+2Не уделил, тк, насколько я понимаю, это всё чисто математические результаты пока что. Они интересны и важны для теории, но с точки зрения практики уменьшение степени на пару тысячных вообще ни на что не влияет, увы.
Gay_Lussak
21.05.2024 10:49Да тут даже проблема не в малом приросте производительности. Эти методы в целом нереализуемы на практике - там константа требует памяти больше, чем есть на всей планете.
domix32
21.05.2024 10:49это же много IF
ообще не факт. сам автор рассматривает алгоритм вцелом, не конкретные примеры кода. Реализация вполне может иметь какой-нибудь branchless приём, которые сведётся к паре дополнительных сложений.
Разбитие на блоки
вроде уже используется т.к. в среднем оптимальнее иных подходов. Но может зависеть от данных, их количества и железа на котором оно запускается. Это примерно как с FFT и сложением супер больших чисел - профит появляется, когда числа в районе гугла (10^100).
nv13
21.05.2024 10:49Очень эээ... интересно, конечно, но у меня не сходится что то. Первый случай перемножения - 8 умножений и 4 сложения, может выполняться, мне кажется, за 12 циклов. Улучшенный способ 7 умножений и 18 сложений, возможно, уложится в 20.
domix32
21.05.2024 10:49Лимит обычно имеет амортизированное значение, то есть если взять n значений и начать выполнять алгоритм, а потом количество операций поделить на это самое n, то оно в теории должно сойтись к тому самому n^w. Основная проблема, что вся эта проихводительность теоретическая, то бишь в сравнении со специализированными алгоритмами реальное превосходство начинается на очень больших данных. Ну то есть в примере там матрица 2х2, а чтобы почувствовать что асимптота даёт ощутимый выигрыш вам надо, например, минимум 100х100. И насколько я понял из собственно работы оно работает не просто для матриц, а для тензоров, то бишь для профита может понадобиться не просто 100х100, а ещё х100. Аналогичная ситуация с быстрым умножением целых чисел: алгоритм Карацубы начинает становиться более эффективным для чисел >
, алгоритм Шёнхаге-Штрассена показывает улушения на цифрах длинее
-
. Самый оптимальный алгоритм с
начинает превосходить остальные алгоритмы при размере чисел в
бит, при том что количество частиц в наблюдаемой вселенной оценивается пример в
. То есть сам алгоритм самый оптимальный, но на малых данных можно иметь лучшую асимптотику через специализированные алгоритмы. Аналогично и с перемножением матриц.
nv13
21.05.2024 10:49Так они и пытались ускорить алгоритм уменьшением количества умножений, но это привело к росту операций сложения. Для 60х это было актуально, с конца 90х уже не очень. То есть прямое перемножение будет быстрее, чем "оптимизированное".
domix32
21.05.2024 10:49Опять же - если в матрицах 2х2 ничего не поменялось, не значит что на больших размерах профит не растёт. Возможно, оно будет работать более эффективно (как в случае с оптимизациями от AI), возможно не будет, потому что лимиты слишком больший. Не факт, что в исследовании есть какие-то оценки применимости всего этого и вероятно стоит ждать докладов от каких-нибудь других исследователей, которые расскажут будет ли профит для ML, например.
nv13
21.05.2024 10:49Так они же N пытаются свести к 2, а для размерности 2 эффект в минус одном умножении. Но замена одного умножения 14 сложениями да ещё с нерегулярным по памяти расположением операндов может привести не к ускорению, а к существенному замедлению.
Это как с БПФ - большинство знает, что это быстрей, чем ДПФ, но на практике иногда получают лишь ухудшение от его применения.
Deosis
21.05.2024 10:49Замена одного умножения на несколько сложений выгодна для больших матриц, так как одно умножение на порядки дольше одного сложения
nv13
21.05.2024 10:49Это очень большое заблуждение. Операция умножения с добавлением результата к аккумулятору и инкрементом регистра косвенной адресации может осуществляться за один цикл на некоторых архитектурах.
Balling
21.05.2024 10:49Это из-за того, что в процессорах используется алгоритм Карацуба, а то и Шёнхаге — Штрассена. Причем там на очень больших числах уже не аппаратный код, а алгоритм в библиотеке GMP из многих разных операций. Кроме того, алгоритм Фюрера на FFT тоже уже есть.
Кроме того, если мы берем (3, 3, 3) то есть 3x3 x 3x3, то там уже интереснее. Мы до сих пор не знаем оптимальный алгоритм. Мы только знаем, что умножений должно быть 19 или больше. Оптимальный алгоритм открытый в 2019 имеет 21 умножение. https://arxiv.org/abs/1904.07683
До этого лучший результат был 22 https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=4056&option_lang=eng
nv13
21.05.2024 10:49Это не из за этого. Это из за того, что критерий оптимальности или эффективности в приведённых рассуждениях - количество умножений, относится к прошлому веку. Для современных процессоров следует учитывать операции сложения, адресации и ветвлений
unreal_undead2
21.05.2024 10:49+1На современных процессорах комбинация сложения и умножения выполняется за один такт (если FMA юнитов несколько, то можно и несколько векторов за такт обработать), у отдельных операций сложения и умножения throughput одинаковый.
Deosis
21.05.2024 10:49Это на каком процессоре умножение произвольных матриц выполняется за один такт?
unreal_undead2
21.05.2024 10:49+1Речь про элементарные операции над небольшим вектором, на которых и строится умножение матриц. Главное - что цена сложения и умножения одинаковая (на Broadwell вообще была забавная ситуация - latency комбинации сложения и умножения была меньше, чем у сложения; throughput, правда, одинаковый).
knstqq
21.05.2024 10:49Грубо говоря, смотрите, это нужно рассматривать не как умножения чисел, а как умножения под-матриц. Чтобы перемножить 2 матрицы 100x100 вам нужно сделать 1000.000 умножений чисел классическим способом.
Используя умножение Виноградова - вы вместо умножения двух матриц 100x100 умножаете 8 матриц размера 50x50. Если это делать классическим способом - получится всё те же 1000.000 умножений чисел. Но метод виноградова - экономит одну из 8 операций умножения -> то есть 8 * 50 * 50 * 50 = 100 * 100 * 100 превращается в 7 * 50 * 50 * 50 < 100 * 100 * 100
Давайте теперь матрицы 50x50 умножать "умно". Вместо 8 * 25 * 25 * 25 = 50 * 50 * 50 умножений мы сделаем 7 * 25 * 25 * 25 < 50 * 50 * 50
за две итерации мы снизили количество умножений с 8 * 8 = 64 до 7 * 7 = 49
для матрицы размером 100x100 общий размер экономии будет 8 * 8 * 8 * 8 * 8 * 8 / (7 * 7 * 7 * 7 * 7 * 7) = 262144 / 117649 - то есть вдвое меньше умножений итого.
Значит для матрицы 100x100 нам удалось сократить количество операций вдвое. Заметьте, что количество сложений тоже уменьшается на каждом этапе рекурсии, потому что мы говорим не о сложении чисел, а аналогично о сложении матриц.
nv13
21.05.2024 10:49Какая то эквиллибристика Виноградом) Я рассматриваю то, что написано автором - перемножение двух матриц 2×2. Даже для этого примера некорректным является игнорирование сложения как затратной операции и полное отсутствие затрат на адресацию. Ну посчитаете вы умножения, уверены, что станет быстрее? Я вот сильно сомневаюсь, что задача в такой постановке до сих пор актуальна.
mynameco
21.05.2024 10:49Мне кажется это достижение бессмысленно. Умножение матриц, очень хорошо параллелится. Чем и пользуются. Умножая все паралельно. Почти за два такта. И блоки одинаковые. Можно улучшать и оптимизировать в железе.
А всякие улучшатели, добавляют ветвления. И больше шагов делают. Выгодно только там где нужно экономить энергию. Не думаю, что это нужно ученым.
knstqq
21.05.2024 10:49алгоритмы приведённые в статье работают быстрее только для матриц размера, скажем, 10 миллиардов строк на 10 миллиардов столбцов. Для матриц в тысячи или десятки тысяч строк они не практичны, ничего нового с года эдак 1990го практичного не придумали что можно было бы использовать на практике.
p.s. Если вы матрицу такого размера распаралелите на 1000000 ядер, то всего лишь за 10 миллионов лет дождётесь результата. Увы, но эти алгоритмы (упомянутые в статье) тоже не слишком-уж и быстрые; поэтому ищут грааль-алгоритм, который даст значительное улучшение по сравнению со всеми приведёнными статьями. посмотрим что получится, пока не доказано что такого алгоритма не существует
domix32
Я-то понадеялся алгоритм покажут, а тут миллион ссылок и все за пэйволом.
Imaginarium
Ха, добро пожаловать в сайнс)
Представляете, как непросто делать сейчас актуальную науку? С каждым днём мир уходит всё дальше и дальше. И я сам заплатил бы за свежие статьи, но как? Я уже молчу про публикации в Open Access самому: $ 3k+ -- это за гранью понимания рядового исследователя без крупных грантов на руках (да и с ними, опять же, попробуй заплати им).
Ababaj
Здесь нет актуальной науки!?
Imaginarium
Я этого не сказал. Я лишь указал на то, насколько трудно её стало делать.
Ababaj
Логика?!: делать трудно - актуальную науку.
Flux
Логика в том что кое-кто придумал и пролоббировал "замечательную" систему которая хоть и убивает науку, но приносит стабильный гешефт кому надо.
mpetrunin
Там скорее всего не будет явного алгоритма, которым можно воспользоваться.
Впрочем, выше есть ссылка на саму статью на arxiv: [2210.10173] Faster Matrix Multiplication via Asymmetric Hashing
domix32
Часть на SciHub нашлась.
Imaginarium
Сайхаб уже мемориальный проект, свежих статей в нём нет и, наверное, уже не будет. Хорошо хоть что-то нашлось.
Brrastak
А что случилось?
ramyalexis
Элбакян пошла на принцип. Ждёт, что скажет суд в Индии (там на сцихаб подали в суд). И от этого результата откроет скачивание новых статей или нет. Суд пока "собирает сведения". В сцихабе нет статей новее 2021 года.
Можно следить за процессом - https://www.reddit.com/r/scihub/comments/lofj0r/announcement_scihub_has_been_paused_no_new/
artemerschow
При всей моей нелюбви к Элбакян, как к публичной персоне и её "походам на принцип", тут сложно её не поддержать. Очень обидно, что такой проект так тихо и вяло поддерживается, и что за него боятся громко вступиться более или менее заметные публичные фигуры.
h45h47
Если статьи нет на SciHub, то можно попробовать написать в чат SciArticle: t.me/SciArticleChat, мне там частенько помогали найти нужную статью.
domix32
Коротко - копирайтеры. Многие считают, что статьи спирачены со всеми вытекающими. Не знаю насколько проект действительно мёртв в плане свежих статей, однако 88 лямов статей в индексе это в принципе достаточно приятная цифра. Где-то было дело про то что можно запросить конкретные DOI, но я на почту не писал, не пробовал. Последняя явная временная метка на сайте от автора была за 2020 год, со статьями хз.
Balling
Заменили на телеграмный Nexus. Там все статьи есть.
Imaginarium
Нет, далеко и далеко не все.
Balling
А их можно пропросить. :)
samozvet
Рэньфэй Чжоу помог найти новый метод умножения матриц, работающий быстрее, чем все предыдущие
В этой стране б уже третью ходку чалился ...
BeMySlaveDarlin
Вас заждались в тцк