Comments 58
Я-то понадеялся алгоритм покажут, а тут миллион ссылок и все за пэйволом.
Ха, добро пожаловать в сайнс)
Представляете, как непросто делать сейчас актуальную науку? С каждым днём мир уходит всё дальше и дальше. И я сам заплатил бы за свежие статьи, но как? Я уже молчу про публикации в Open Access самому: $ 3k+ -- это за гранью понимания рядового исследователя без крупных грантов на руках (да и с ними, опять же, попробуй заплати им).
Там скорее всего не будет явного алгоритма, которым можно воспользоваться.
Впрочем, выше есть ссылка на саму статью на arxiv: [2210.10173] Faster Matrix Multiplication via Asymmetric Hashing
Часть на SciHub нашлась.
Сайхаб уже мемориальный проект, свежих статей в нём нет и, наверное, уже не будет. Хорошо хоть что-то нашлось.
А что случилось?
Элбакян пошла на принцип. Ждёт, что скажет суд в Индии (там на сцихаб подали в суд). И от этого результата откроет скачивание новых статей или нет. Суд пока "собирает сведения". В сцихабе нет статей новее 2021 года.
Можно следить за процессом - https://www.reddit.com/r/scihub/comments/lofj0r/announcement_scihub_has_been_paused_no_new/
При всей моей нелюбви к Элбакян, как к публичной персоне и её "походам на принцип", тут сложно её не поддержать. Очень обидно, что такой проект так тихо и вяло поддерживается, и что за него боятся громко вступиться более или менее заметные публичные фигуры.
Если статьи нет на SciHub, то можно попробовать написать в чат SciArticle: t.me/SciArticleChat, мне там частенько помогали найти нужную статью.
Коротко - копирайтеры. Многие считают, что статьи спирачены со всеми вытекающими. Не знаю насколько проект действительно мёртв в плане свежих статей, однако 88 лямов статей в индексе это в принципе достаточно приятная цифра. Где-то было дело про то что можно запросить конкретные DOI, но я на почту не писал, не пробовал. Последняя явная временная метка на сайте от автора была за 2020 год, со статьями хз.
Заменили на телеграмный Nexus. Там все статьи есть.
Рэньфэй Чжоу помог найти новый метод умножения матриц, работающий быстрее, чем все предыдущие
В этой стране б уже третью ходку чалился ...
Вот эта ссылка без пейволла.
Насколько я понял из статьи, эти алгоритмы не дают никакого улучшения для общего случая, т.е. когда все элементы различны.
Ну и для таких случаев обычный алгоритм будет как правило оптимизирован в техническом плане: будут учтены кэши памяти, предзагрузка, порядок элементов. Алгоритмы же, нарушающие последовательный доступ, на практике будут только снижать производительность, иногда весьма значительно.
Статья вообще похожа на наукообразный бред:
Раньше они разбивали матрицы на блоки, часть из которых "сжигали" лазером (wtf?)
Теперь они выяснили, что если сжигать лазером меньше блоков, то умножение будет быстрее (wtf?x2)
В статье вообще огромное количество воды. Вся как будто из кликбейтных тизеров состоит.
Сжигать лазером конечно же в переносном смысле, там упомянуто, что это просто зануление блока. Почему быстрее, если меньше занулять - из текста непонятно, из других источников нашёл, что вроде как матрицу перегоняют в тензор и вот для тензоров уже есть эффективные алгоритмы перемножения. И видимо где-то тут и играет роль уменьшение сжигания.
На хабре уже была статья от 2021 года об этом, там подробнее расписано, только нет результатов последних лет, естественно.
Там ещё проблемы в константе перед n^<что то> (где то видел, что она в этих продвинутых алгоритмах в районе 10^500).
Ну не то, чтобы прямо прорыв. Новый результат, да. Как вариант новый подход. Прорыв это что-то, за чем следует лавинообразный поток каких то других новшеств. Открытие транзистора это прорыв. Алгоритм Диффи-Хеллмана тоже прорыв. А тут как то не ощущается хлынувший на нас поток инноваций.
Ожидал упоминание AlphaTensor в статье.
Автор бы уделил побольше внимания следующим моментам:
Все эти проверки на мусорность - это же много IF? Сколько на них тратится тактов ЦП? Или мы только умножения FP считаем?
Разбитие на блоки - насколько это перспективно с точки зрения TensoFlow и пр. технологий GPGPU.
Хотя бы псевдокодом ключевые алгоритмы представили бы.
Без этих трёх моментов статья ну совсем вода водой. А хотелось бы пива склеивающего попу со стулом.
Не уделил, тк, насколько я понимаю, это всё чисто математические результаты пока что. Они интересны и важны для теории, но с точки зрения практики уменьшение степени на пару тысячных вообще ни на что не влияет, увы.
это же много IF
ообще не факт. сам автор рассматривает алгоритм вцелом, не конкретные примеры кода. Реализация вполне может иметь какой-нибудь branchless приём, которые сведётся к паре дополнительных сложений.
Разбитие на блоки
вроде уже используется т.к. в среднем оптимальнее иных подходов. Но может зависеть от данных, их количества и железа на котором оно запускается. Это примерно как с FFT и сложением супер больших чисел - профит появляется, когда числа в районе гугла (10^100).
Очень эээ... интересно, конечно, но у меня не сходится что то. Первый случай перемножения - 8 умножений и 4 сложения, может выполняться, мне кажется, за 12 циклов. Улучшенный способ 7 умножений и 18 сложений, возможно, уложится в 20.
Лимит обычно имеет амортизированное значение, то есть если взять n значений и начать выполнять алгоритм, а потом количество операций поделить на это самое n, то оно в теории должно сойтись к тому самому n^w. Основная проблема, что вся эта проихводительность теоретическая, то бишь в сравнении со специализированными алгоритмами реальное превосходство начинается на очень больших данных. Ну то есть в примере там матрица 2х2, а чтобы почувствовать что асимптота даёт ощутимый выигрыш вам надо, например, минимум 100х100. И насколько я понял из собственно работы оно работает не просто для матриц, а для тензоров, то бишь для профита может понадобиться не просто 100х100, а ещё х100. Аналогичная ситуация с быстрым умножением целых чисел: алгоритм Карацубы начинает становиться более эффективным для чисел > , алгоритм Шёнхаге-Штрассена показывает улушения на цифрах длинее
-
. Самый оптимальный алгоритм с
начинает превосходить остальные алгоритмы при размере чисел в
бит, при том что количество частиц в наблюдаемой вселенной оценивается пример в
. То есть сам алгоритм самый оптимальный, но на малых данных можно иметь лучшую асимптотику через специализированные алгоритмы. Аналогично и с перемножением матриц.
Так они и пытались ускорить алгоритм уменьшением количества умножений, но это привело к росту операций сложения. Для 60х это было актуально, с конца 90х уже не очень. То есть прямое перемножение будет быстрее, чем "оптимизированное".
Опять же - если в матрицах 2х2 ничего не поменялось, не значит что на больших размерах профит не растёт. Возможно, оно будет работать более эффективно (как в случае с оптимизациями от AI), возможно не будет, потому что лимиты слишком больший. Не факт, что в исследовании есть какие-то оценки применимости всего этого и вероятно стоит ждать докладов от каких-нибудь других исследователей, которые расскажут будет ли профит для ML, например.
Так они же N пытаются свести к 2, а для размерности 2 эффект в минус одном умножении. Но замена одного умножения 14 сложениями да ещё с нерегулярным по памяти расположением операндов может привести не к ускорению, а к существенному замедлению.
Это как с БПФ - большинство знает, что это быстрей, чем ДПФ, но на практике иногда получают лишь ухудшение от его применения.
Замена одного умножения на несколько сложений выгодна для больших матриц, так как одно умножение на порядки дольше одного сложения
Это очень большое заблуждение. Операция умножения с добавлением результата к аккумулятору и инкрементом регистра косвенной адресации может осуществляться за один цикл на некоторых архитектурах.
Это из-за того, что в процессорах используется алгоритм Карацуба, а то и Шёнхаге — Штрассена. Причем там на очень больших числах уже не аппаратный код, а алгоритм в библиотеке 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
На современных процессорах комбинация сложения и умножения выполняется за один такт (если FMA юнитов несколько, то можно и несколько векторов за такт обработать), у отдельных операций сложения и умножения throughput одинаковый.
Грубо говоря, смотрите, это нужно рассматривать не как умножения чисел, а как умножения под-матриц. Чтобы перемножить 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 нам удалось сократить количество операций вдвое. Заметьте, что количество сложений тоже уменьшается на каждом этапе рекурсии, потому что мы говорим не о сложении чисел, а аналогично о сложении матриц.
Какая то эквиллибристика Виноградом) Я рассматриваю то, что написано автором - перемножение двух матриц 2×2. Даже для этого примера некорректным является игнорирование сложения как затратной операции и полное отсутствие затрат на адресацию. Ну посчитаете вы умножения, уверены, что станет быстрее? Я вот сильно сомневаюсь, что задача в такой постановке до сих пор актуальна.
так для матрицы 2*2 нет ничего быстрее чем сделать 8 умножений и всё. их ещё можно векторно все 8 сделать, на условном вычислителе чуть-ли не со скоростью умножения 2 вещественных чисел получить результат умножения матриц. Матрицы размера 4*4, которые уже можно рекурсивно умножать - ну что ж, там возможно прирост уже будет не нулевой, но скорее всего нет. А вот матрицы размера 100x100 - там уже значимое ускорение
За счёт чего там будет ускорение? По умножениям да, так же как и в примере 2х2, а по всем операциям?
За счёт того, что в алгоритме умножаются не числа а подматрицы, как в алгоритме Карацубы
Матрица 2×2 состоит из подматриц 1×1, при стоимости умножения равного сложению эти алгоритмы дают проигрыш по количеству операций. Вы хоть в смысл вникните, за счёт чего сокращается одно умножение и заменяется несколькими сложениями..
Нет. Матрица 10000x10000 и субматрицы типо 10x10.
Если 3000x3000 берем 3x3 и там 23 умножения оптимально. Хотя есть в 21 умножение этот алгоритм некуммутативен (это значит по обе стороны от операции умножения стоят элементы обеих матриц), а значит не может быть использован для ускорения.
А матрица 10000×10000 состоит из подматриц 5000×5000. И алгоритм предлагает одно умножение матриц 5000×5000 заменить на несколько сложений матриц того же размера.
Мне кажется это достижение бессмысленно. Умножение матриц, очень хорошо параллелится. Чем и пользуются. Умножая все паралельно. Почти за два такта. И блоки одинаковые. Можно улучшать и оптимизировать в железе.
А всякие улучшатели, добавляют ветвления. И больше шагов делают. Выгодно только там где нужно экономить энергию. Не думаю, что это нужно ученым.
алгоритмы приведённые в статье работают быстрее только для матриц размера, скажем, 10 миллиардов строк на 10 миллиардов столбцов. Для матриц в тысячи или десятки тысяч строк они не практичны, ничего нового с года эдак 1990го практичного не придумали что можно было бы использовать на практике.
p.s. Если вы матрицу такого размера распаралелите на 1000000 ядер, то всего лишь за 10 миллионов лет дождётесь результата. Увы, но эти алгоритмы (упомянутые в статье) тоже не слишком-уж и быстрые; поэтому ищут грааль-алгоритм, который даст значительное улучшение по сравнению со всеми приведёнными статьями. посмотрим что получится, пока не доказано что такого алгоритма не существует
Коментарий к переводу: в китайском языке не произносят "р" за исключением слогов с эризацией. Если написано Renfei то это не Рэньфэй а Жэньфэй. Если написано Ran, то это Жань. Разумеется, никто не говорит "ж" в словах вроде ér или diǎnr, но конкретно в данном случае перевод некорректен.
Новый прорыв приближает умножение матриц к идеалу