Комментарии 114
![Впечатляет. Особенно"Эльбрус" - на 2 порядка Впечатляет. Особенно"Эльбрус" - на 2 порядка](https://habrastorage.org/getpro/habr/upload_files/ed5/b6d/299/ed5b6d2995018c22e78499387bcc86e2.png)
И пугает... Хоть что-то где-то не учёл и Эльбрус тебя штрафует так, что мало не покажется. Интел, так сказать, более дуракоустойчив.
Кажется, основная ценность интелов именно в перекладывании всех этих ювелирных оптимизаций на процессор. Аппаратура "для дураков" побеждает, в итоге, экономя время программистов. Тщательно притирать софт к харду могут себе позволить не многие (за неделю новую фичу выкатил, потом пол года оптимизируешь и борешься с регрессом).
Да ладно бы была возможность "бороться с регрессом", а если это "просто jit обновился"? Причём JDK/NetCore jit ни фига не такой ювелирный, как в C/C++ - у него просто времени и памяти нет на "вдумчивые оптимизации".
Да, выглядит очень хрупкой вся эта возня, не для "живой" разработки платформа, а для "потратил год на оптимизацию и закатал весь софт в бетон, чтобы ничего не изменилось". Кажется, всё это должно быть спрятано от прикладного программиста под капотом. Возможно, компилятор все эти оптимизации должен уметь сам проделывать, пусть даже через нейронки и отбор различных вариантов через тесты, но чтобы сам (да, пусть увеличив время компиляции с 10 минут до пары часов :)).
Перекладывание на плечи программистов этих оптимизационных проблем, кажется, путь в никуда, чисто экономически. Похожим образом (из-за своей сложности для разработчиков) умерла Sega Saturn, помнится, хотя теоретически была мощнее конкурентов. Программисты не любят, когда им на ровном месте подводные камни залетают в спицы (а для сложения двух чисел нужно знать 14 видов возможных ситуаций, чтобы не сломать поток вычислений) :).
Вряд ли уж так совсем. Оптимизировали какой-то сервис, алгоритм под конкретную машину и пользуйтесь потом. Вряд ли Вам придется постоянно этим заниматься. Самое главное, что данная оптимизация универсальна(!), те оптимизация происходит для всего оборудования, а не так, что типа Элика оптимизировали Интел регрессировал. Поэтому, такие люди, как автор, всегда будут в цене - оптимизация и оптимизация, хоть там, хоть этам.
В том и дело, что такие программисты, как автор, будут в цене - и в дефиците :). А неизменяемые сервисы ("забетонированная" кодовая база) не так уж востребованы на конкурентном рынке, увы. Ценность современных архитектур - именно в их подвижности, расширяемости.
Вроде и так и не так.
"забетонированная база" оптимизирована для всех рассматриваемых случаев. Если менять железо, то... не так и часто - можно "полирнуть".
Понимаете, ведь цифирки, которые написаны в реализациях, не просто цифирки, но дофигилиарды сожженых энергорессурсов: дата-центры - это как металлургические комбинаты, поэтому ...
Вы в своём сценарии забыли процесс добавления прикладных фич для пользователя, кажется :).
Если менять железо, то… не так и часто — можно «полирнуть».Тут алгоритм на 200 строчек, и автор его вылизывал целый день или больше. А что будет, если дать ему исходники браузера, это ж в голове не поместится. После таких оптимизаций любое внесение изменений подразумевает откат к начальной версии, и всё начинай заново.
Давайте уточним что "на два порядка"="в сто раз". (если мы говорим о десятичных порядках)
Давайте уточним. Порядки: единицы, десятки, сотни... От сотен до единиц 2 порядка.
С другой стороны, было три разряда слева от разделителя, стал один.
На два разряда стало быстрее.
ну да, когда говорят, например, что сложность логарифмическая, то не считают же 2log(n) или 3log(n), если это не n*log(n) )
В приведённой выше табличке Эльбрус отстает от других процессоров:
В базовой реализации - в 15 и в 5 раз.
С уменьшенной нагрузкой на память - можно сказать в 1,5 раза и в 1,5 раза.
Где-то в другой табличке была разница в 20 раз - но это всё ещё "На порядок".
Если уж мы говорим о логарифмах, log(10)=1; log(31,62)=1,5; log(100)=2.
И граница между одним порядком и двумя должна быть где-то в районе 31.
А не могли бы Вы привести еще и количество шагов по X и Y? Хочется оценить количество неизвестных. Просто если их немного, то систему линейных уравнений можно решить в "лоб". Если много, воспользоваться каким-нибудь методом Ньютона-Крылова, и это в обоих случаях будет заметно быстрее рассматриваемого способа. Да еще воспользоваться готовой MKL библиотекой. А вот как поведут себя всякие BLAS'ы и lapack'и на Эльбрусе? Можно ли будет их так же заметно ускорить?
В статье это сказано: рассматривается разностная схема с сеткой размера 1000x1000, то есть по 1000 точек на каждом направлении. Количество шагов итерационного процесса для этой сетки до выполнения условия останова составляет примерно 428000. О применимости других методов я, честно говоря, не слышал и быстро найти не смог. Если Вас не затруднит, был бы рад ссылкам на литературу с обоснованием возможности получить приближённое решение требуемой точности.
Мне неизвестно о существовании нужных функций в библиотеках типа MKL. Подчеркну, что сложность одной итерации в этом методе O(MN), то есть здесь нет умножения матриц или "обычного" решения СЛАУ.
Касательно библиотек для Эльбруса: есть оптимизированная EML, отвественность за её разработку лежит на МЦСТ, соответственно, там применены более продвинутые техники, можете почитать в Руководстве.
1000x1000
О, тут я не искал.
Количество шагов итерационного процесса для этой сетки до выполнения условия останова составляет примерно 428000
Ой.
Если Вас не затруднит, был бы рад ссылкам на литературу с обоснованием возможности получить приближённое решение требуемой точности.
Мне неизвестно о существовании нужных функций в библиотеках типа MKL
Все даже чуть проще. Тут все линейное - хватит GMRES. И он есть в MKL:
Но проще, наверное, сначала в Питоне поиграться: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.gmres.html
А, понял. Я прошу прощения, это было недопонимание с моей стороны, успел забыть некоторые вещи. По сути, у меня и есть реализация метода наименьших невязок (который MINRES как частный случай GMRES, только здесь с более мягким условием останова).
В рамках учебной задачи, естественно, нужно было реализовывать самому. Спасибо за наводку, интересно будет сравнить, как соотносится ручной вариант с использованием оптимизированных библиотек.
Для GMRES, особенно если с preconditioner'ом поиграть, число итераций будет очень сильно меньше. Естественно, сами итерации сложнее.
Я уж было дернулся на Питоне проверить, но не понял, почему у Вас в функции F_border() в вычислениях участвует 1/DX, 1/DY (run_config->inv_h1, run_config->inv_h2)?
Они появляются после выполнения преобразований над аппроксимацией граничных условий. Формула корректна, я проверял её. Сейчас не могу подробно написать, но вечером готов выписать формулы и обоснование.
Спасибо, просто добавьте, если можно, формулы прямо в статью. Может, кто еще захочет с Вами посоревноваться.
Вышла небольшая заминка по времени, но теперь наконец добавил пример для правой границы под спойлер. Для остальных границ получается аналогично, в коде у меня по сути отражена та же самая формула, просто написанная не в TeX.
Да, кстати, пока писал, задумался о том, что "просто так" выразить задачу в матричном виде не получится: из-за шаблона "крест" придётся рассматривать неизвестный вектор размера MN, а матрица будет иметь размер MNxMN. Интересно, как справится общий метод при таких размерах.
Спасибо. А матрица сильно разреженная, т.е. максимум 5 ненулевых элементов в строке, столбце...
Вдогонку... Не нравится мне, что Вы с граничным условием сделали. Если бы просто написали (это для левой границы) аппроксимацию второго порядка, хотя это и лишнее, на самом деле:
но Вы вторую производную по X взяли из уравнения Лапласа (чтобы за границы массива не выйти?), но оно же на границе не работает, тут именно граничное условие справедливо! Ну и в углах беда.
P.S. И в одномерном случае ваш фокус невозможен.
Детали сейчас не помню, но без "фокуса с разложением в ряд" не получается второй порядок аппроксимации. Я, естественно, это всё сам не изобретал, а делал по описанию в задании, которое полностью соответствовало рассказанному на курсе по численным методам несколько лет назад. В одной из книг видел простое описание, сейчас быстро не нашёл, так что пока могу только предложить посмотреть страницу 190 из приведенной в статье книги, вроде это оно.
Автор просто Мозг... человечество гордится такими людьми. Дай бог вам здоровья
К автору несколько вопросов/комментариев есть:
Шаг "Векторизация" пропущен для Intel и Power. Кажется тут нужно добавить свидетельства, что компилятор успешно смог использовать AVX2 (ну или хотя бы SSE) и AltiVec соответственно.
Даже если на (1) компилятор на первый взгляд справился на x86/ppc, то было бы неплохо посмотреть и оценить, насколько это хорошо сделано (проделать ту же работу, которая была сделана для Эльбруса).
В целом, правила хорошего тона для публикации бенчмарков - публиковать краткую информацию как ими пользоваться. Это полезно, чтобы любой читатель мог пойти и воспроизвести результаты работы и независимым образом их проверить (или добавить еще машин для сравнения). В целом сюда же еще и ожидаемый вывод было бы неплохо приложить, чтобы у пользователя через эн лет на каком-нибудь совершенно другом железе не возникло вопросов "как проверить, что код до сих пор работает корректно?".
Также правило хорошего тона - выкладывать открытый код для таких бенчмарков. Тут важно понимать, что пока у кода нет явной лицензии, он является собственностью разработчика и технически - проприетарным. Его использование где либо - крайне затруднительно (в том числе очень спорно, можно ли его в принципе даже читать и запускать). Если есть сложности выбрать лицензию - есть сервисы, вкратце рассказывающие про них или сделавшие простенькие wizard'ы.
Так ведь всё написано: "Заметим, что на рассматриваемых процессорах Intel и IBM нет требований к выравниванию данных, а потому компиляторы ещё на предыдущих этапах смогли справиться с векторизацией всех циклов". Думаю, из флагов оптимизации под текущий процессор (-xHost, -O5) понятно, что использовались AVX2 и 128-битные регистры на Power (не помню, как точно они сейчас называются, поэтому не пишу AltiVec).
Много чего было бы неплохо сделать, но статья посвящена конкретно рассмотрению Эльбруса и ориентирована на него. Уверен, материалов по Intel и IBM можно найти намного больше и более полных.
Это не бенчмарк, прошу материал в таком качестве не рассматривать. Что же касается запуска и ожидаемых результатов, эта информация будет оформлена в файле readme, который появится позднее.
Спасибо, полностью согласен, это недосмотр с моей стороны! Добавил файл с лицензией.
Флаг компиляции никоим образом не гарантирует, что компилятор что-то векторизовал, тем более Intel C++ Compiler Classic это не самый популярный компилятор с не самыми очевидными наборами флагов (который тем более предлагается заменить на oneAPI C++ Compiler на базе LLVM), например я попросту не помню какие флаги там включают возможность использования AVX, так как последний раз с ним сталкивался лет 5 назад.
Также с Power - флаги сборки не гарантируют что компилятор успешно векторизовал цикл, пока не доказано обратного. Ну и AVX2 - они таки 256-и битные регистры должен использвать.В таком случаи к статье фундаментальная претензия иного рода - вы потратили сколько-то (с виду не мало) времени на оптимизацию кода под одну платформу, но при этом не проделали такой же работы с другими. Без явного указания этих моментов (что статья не преследовала цели сравнить оптимизации на каждой платформе) создается ложное ощущение, что вы считаете код под PPC и Intel эквивалентно оптимизированным. То есть тут либо проделать такую же работу по ним, либо disclaimer в начало. Ну и ценность статьи соответственно падает.
Хм... Это опять же не очевидно, так как в материале код явно используется как бенчмарк и сравнения платформ приводятся параллельно в одной сводной таблице.
Спасибо за файл с лицензией.
Немного дополню почему я спрашиваю про векторизацию - я попробовал погонять код на ноутбуке (понятно, что сравнение не совсем корректно) и чуть-чуть поиграть с флагами сборки, как раз чтобы проверить векторизацию кода. Да, у меня на ноуткбе clang, а не Intel'овский компилятор, но у него в более подробном выводе про векторизацию циклов (-Rpass-analysis=loop-vectorize -Rpass=loop-vectorize -Rpass-missed=loop-vectorize) видно что не все из них векторизуются на -O3 и на Ofast ситуация чуть лучше (на O3 итерация занимает 2.9 секунды, на Ofast - 1.6с, без каких либо дополнительных изменений в коде и при сохранении того же самого вывода, то есть предполагаю что в таком случаи задача все же корректна решена).
Отсюда вопрос, в том как хорошо интеловский компилятор векторизовал написанный код (это опуская вопрос почему был выбран Compiler Classic вместо их нового, да и в целом почему не сравнивали с gcc или llvm, которые немного более распространены среди простых людей)
Я рассчитывал, что мне можно поверить на слово :) Собственно, никакого секрета здесь нет: наличие векторизации на ymm регистры я проверил по ассемблерному коду (есть вхождение тела цикла, соответствующее обработке по 4 элемента в ymm регистре), на IBM есть замечательная опция -qlistfmt, по ней создаётся подробный отчёт, в котором видно, что цикл был успешно векторизован и раскручен (на 2, если я правильно помню).
Классический компилятор — это известный инструмент, с которым было понятно, как работать (в частности, касательно использования MPI), он продолжает поддерживаться, обновляться и поставляться в составе набора для HPC применений.
Если честно, Вы хотите слишком многого от меня. Ещё раз повторюсь, было бы интересно всё происследовать и проверить, но статья не о сравнении компиляторов, а о методах оптимизации с прицелом на Эльбрус. Если бы я начал сравнивать с другими компиляторами, мне бы пришлось то же самое провернуть на POWER (как минимум, сравнить с gcc — он тоже есть на машине, к которой у меня доступ) и на Эльбрусе. Ну и во что превратилась бы статья?.. Выбор же icc как дающего лучшие результаты обоснован личным опытом и рядом других факторов. Ни в коем разе не претендую на абсолютную справедливость сделанного выбора.
Я рассчитывал, что мне можно поверить на слово :)
Если это в статье не упомянуто, то как я могу знать что вы это проверяли? Опять же, пример на базе эксперимента выше (да, с clang'ом) я привел - то есть я еще и дополнительно видел что не все что стоит векторизуется корректно с тем что привдено (правда да, на другом компиляторе, но у меня нет под рукой систем на разумном по новизне Intel'е).
Если честно, Вы хотите слишком многого от меня.
У меня это общая претензия к статьям подобного рода. Ваша - не первая. Я считаю что уровень материала претендует на интересность, но недостаточно высокий в целом, в виду недостаточных времязатрат на исследование. И чтобы оно было интереснее - нужно провести подобного уровня исследование и для x86 и в данном случаи для ppc. Исследование выбора компилятора тоже полезное свойство.
Иначе, статья производит обманчивое впечатление сравнени за счет того что вы в ней сравниваете результат с другими параллельно с вашим приключением по оптимизации. Тут либо посыл менять, либо делать нормальное сравнение.
Может конечно у меня просто высокие требования к материалам, но я не вижу принципиальных проблем адрессовать комментарии, которые я оставил за разумное время.
Ну как же не упомянуто? Я уже и в комментарии Вам процитировал, вот ещё раз приведу выдержку из текста статьи: "компиляторы ещё на предыдущих этапах смогли справиться с векторизацией всех циклов".
Давайте сойдёмся на том, что я не претендовал на "достаточно высокий в целом" уровень материала, и не будем говорить о недостаточности объёма трудозатрат. Объём определялся тем, что мне интересно, о чём я хотел поделиться, и соответствием теме статьи.
Вроде из названия и текста чётко видно, что речь идёт о подходах к оптимизации на Эльбрусе. Что результаты на двух других архитиктурах приведены для "контроля адекватности" и демонстрации универсальности применяемых подходов, а не являются бенчмарком или сравнением процессоров/компиляторов. Хорошо, обещаю в следующий раз постараться не вводить Вас в заблуждение.
интересно, какой у вас процессор в ноутбуке, какие итоговые параметры сборки?
P. S. любопытно, что комментарии единственного человека, который попробовал запустить у себя код, сразу заминусовали.
интересно, какой у вас процессор в ноутбуке, какие итоговые параметры сборки?\
Конкретно в этом - Apple M1 Max - и собственно то что результаты получились лучше чем у автора скорее подтверждают предположения что код банально упирается в память (разница как раз раза в 2 с небольшим по пропускной способности на 1 ядро между моим ноутом и тем на чем гонял автор).
В итоге я не очень игрался, просто взял "-Ofast -mtune=native" и несколько флагов просто для получения диагностики про векторизацию ("-Rpass-analysis=loop-vectorize -Rpass=loop-vectorize -Rpass-missed=loop-vectorize")
Собственно начал я с -O3, получил 2.9 секунды, но решил посмотреть что там с векторизацией и увидел что там некоторые циклы clang считает как неэффективные для векторизации, на Ofast у него чуть иной cost-model и он больше векторизует, в итоге получил 1.6 секунды.
Ради интереса я еще пару минут поигрался с флагами, но больше результатов не получал на последнем коммите. Потом прогнал тест на всех коммитах начиная с первого (чтоб проверить что часть претензий про время проверки вообще разумно). Пришлось правда тащить мелкий патчик потому что у автора было изначально вывод результатов раз в 100 итераций и простое умножение на 10 добавляло погрешность в 10% по сравнению с выводом раз в 1000. Получилось такое (во всех случаях "-Ofast -mtune=native", Apple Clang 13.0.0 из последнего xcode'а, mpi из brew, clang также используется как mpicc:
Вариант 0 - 6.48 +- 0.01с
Вариант 1 - 3.30 +- 0.01с
Вариант 2 - 3.18 +- 0.01с
Вариант 3 - 1.85 +- 0.01с
Вариант 4 - 1.85 +- 0.01с
Вариант 5 - 1.84 +- 0.01с
Вариант 6 - 1.84 +- 0.01с
Вариант 7 - 1.72 +- 0.01с
Вариант 8 - 1.62 +- 0.01с
В принципе все это можно автоматизировать за пару минут и прогон 8-и вариантов суммарно занимает меньше 10 минут. Собственно после чего автору и предъявил претензию о выборе компилятора и бездоказательности векторизации (недостаточно проделанной работе по оптимизации под другие системы или доказательства, что такая оптимизация уже делается компилятором).
А да, проверка корректности, так как на момент как я это все гонял, автор не привел ожидаемый вывод при корректной работе, делалась в сравнении с x86 десктопом где код собирался clang'ом и отдельно gcc с консервативным -O2 и я просто убедился зрительно, что вывод не поменялся и на маке с Ofast такой же.
UPD: делал буквально так (версия mpi естественно может поменяться в зависимости от системы и времени когда кто-то будет пытаться это снова запустить):
make clean && make CC=clang MPICC=clang CFLAGS="-Ofast -mtune=native -Rpass-analysis=loop-vectorize -Rpass=loop-vectorize -Rpass-missed=loop-vectorize -I/opt/homebrew/Cellar/open-mpi/4.1.2/include" LDFLAGS="-L/opt/homebrew/Cellar/open-mpi/4.1.2/lib -lmpi" && ./prog -n 1000 -m 1000
P. S. любопытно, что комментарии единственного человека, который попробовал запустить у себя код, сразу заминусовали.
Это вполне ожидаемо, минусы коменту накидали либо те, кому Эльбрус нравится, либо те кто считают что я за качество материала на автора наехал незаслуженно (по другим метрикам я предполагаю что первых было большинство).
Apple M1 Max — и собственно то что результаты получились лучше чем у автора скорее подтверждают предположения что код банально упирается в память
проверил на ryzen и epyc, производительность на гигагерц получилась примерно одинаковая (≈1.62 при частоте 4.7 vs ≈2.32 при частоте 3.5), так что число каналов памяти не решает.
компилировал с -Ofast -march=native -mtune=native
P. S. результат m1 впечатляет, конечно.
А какой именно Ryzen? У меня просто десктоп - ryzen 3900x, я на нем получаю цифры крайне близкие к тому что у автора на его i7-9700k.
M1 всех обгоняет за счет скорости работы памяти, которая в 4 раза быстрее
«скорость памяти» — это слишком общее понятие, которое не может быть выражено одним числом.
есть как минимум пропускная способность и задержки.
влияние пропускной способности на эту задачу я не смог обнаружить, epyc с 8 каналами памяти выдал производительность на мегагерц немного ниже, чем ryzen с 2 (ядро и там, и там zen 3)
по задержкам, на epyc регистровая ddr4-3200, на ryzen небуферизованная ddr4-2666, скорее всего, преимущество тоже на стороне epyc.
честно говоря, не знаю, почему ryzen оказался примерно на 7% быстрее на мегагерц.
ничего удивительного во всех задача требующих больших объёмов данных он будет опережать конкурентов
вы шутите?
в задачах, требующих больших объёмов памяти, ему с 16 гигабайтами памяти делать нечего.
M1 всех обгоняет за счет скорости работы памяти, которая в 4 раза быстрее, так что тут ничего удивительного во всех задача требующих больших объёмов данных он будет опережать конкурентов (особенно заметно при компиляции c++).
Там не так просто.
Во первых у простого М1 скорость памяти не так сильно отличается от типичных x86. У M1 Pro - где-то в 4 раза больше чем у типичных x86, у M1 Max общая ПСП - в 8, но только CPU часть не может эффективно его использовать и максимум что можно получить - примерно 250 ГБ в секунду. Но и тут не так просто - потому что с 1 перф кластера ты получаешь не более 100 с небольшим гигабайт в секунду пропускной способности, а с эффективного - около 50-и сверху.
Во вторых, компиляция в ПСП не настолько и упирается. Собственно на примере линейки видно что скорость компиляции на равном количестве ядер (если взять допустим 4 перф ядра) совсем не меняется при переходе с М1 на М1 Макс, хотя казалось бы.
Плюс это не объясняет почему мой M1 Max дает именно в сборке софта те же результаты (лишь чуть больше) чем мой же десктоп на Ryzen 3900X, хотя у меня доступная процессору ПСП на ноуте в 250 ГБ в секунду, а на десктопе всего лишь 51.6 (память у меня 3200MHz всего лишь). Я это проверял на сборке двух довольно больших проектов и получил что M1 конечно быстрее, но всего процентов на 10.
при совсем произвольном
Тут я бы хотел увидеть что такое "совсем произвольный". Чтение по 1 байту из случайных мест? Ну тут ты не сможешь прыгнуть выше головы, это правда (со своими ~80-120ns доступа ты просто физически больше чем 10**9/время_доступа операций за секунду не сделаешь - в данном случаи я в целом, а не конкретно о M1). Даже 100-150 мегабайт это для "совсем случайного" доступа слишком много, кстати.
Тут я бы хотел увидеть что такое «совсем произвольный»Только поставьте Test(1024*MB) вместо 128: ideone.com/D6Kb43
Ну вот не совсем соглашусь - на первый взгляд кажется, что чтение идет по sizeof(void*) байт за раз, я бы сказал что "совсем произвольное" это по байту. Не то чтобы это принципиально но все таки (результаты по байту скорее всего будут ровно пропорционально хуже). В принципе если поделить на sizeof(void*) то будет очень близко к 10**9/latency, что вполне ожидаемо (на m1 у меня вышло около 60 МБ в секунду - то есть примерно соответствует задеркже в 128нс, в реальности там около 110, на десктопе у меня вышло 86 МБ/с, то есть по задержкам выходит около 93нс, что тоже похоже на правду, у памяти у меня около 85-и в реальности).
Так для последовательного чтения результаты очень сильно занижены еще. По хорошему последовательный код должен быть другим (см. подход в STREAM).
Мне лень портировать те два бенчмарка, что имеют ассемблерные вставки и используют интринсики на ARM, а без него выходят довольно так себе, если честно.
Для последовательного STREAM дает очень близкие к теоретически возможным результаты.
Я может быть не совсем корректно выразился. Я вчера так и сделал (там еще надо в main'е одну строку закоментировать, так как она не под ifdef'ом) на M1, получил крайне посредственный результат, примерно на порядок хуже чем дает STREAM на 1 потоке. Так как на ryzen'е я тогда прогнать не мог, то я предположил что оптимизированные функции должны дать лучше производительность (честно, код не особо читал).
На Ryzen'е разница не такая драматическая - всего в 4 раза (1 поток дает чуть-чуть меньше 40 ГБ в секунду у меня, 1 поток в тесте по твоей ссылке - чуть меньше 10).
Поучительно.
Результат показал, что суперскалярная архитектура на порядок эффективней VLIW и экономит дорогой ресурс — рабочее время квалифицированных разработчиков, позволяя заменять их малоквалифицированными.
В целом, история напоминает известный анекдот про вырезание аппендицита автогеном через анальное отверстие — можно, но трудно и требует высокой квалификации.
Вы как-то одним махом отбросили замечательный (без сарказма, речь о многопоточной работе и SMT8) суперскалярный IBM, который изначально был всего в 5 раз быстрее. Он ускорился в 13 раз, это сложно назвать "экономит". Да даже разница в 4 раза в случае Intel может вылиться Вам в неприятный сюрприз по стоимости времени работы на вычислительном кластере.
Кстати, предлагаю посчитать, сколько рабочего времени квалифицированных разработчиков нужно, чтобы исправить поделия малоквалифицированных, когда это становится нужно.
Ерунду пишете, т.к. на практике оптимизировать сложно и под интел и под ибм. Да и приведённые автором оптимизации для Эльбруса не какие-то там эвристики, а вполне обычные методы оптимизации кода, вспоминаем MKL, openblas, второй достоверно известно оптимизирован самым неприятным путём - написанием штучных реализаций на ассемблере.
Круто, было бы ещё интересно посмотреть (спортивный интерес) на №0 с -O0
Оттюнили алгоритм для решения на матрицах размера 1000х1000, отлично. А завтра прилетят матрицы 1001х1001 или 1500х1500 - снова тюнить? А потом приедут симметричные, треугольные или разреженные матрицы со своими лэйаутами хранения данных в памяти - для них тоже отдельные пляски устраивать?
Очень печально, что вы даже не попытались разобраться ни с решаемой задачей, ни с идеей статьи. Уверенно это заявляю, так как в противном случае вы бы начали с вопросов ("А как Ваши подходы применимы к другим размерам задачи?"), ну и тон был бы менее агрессивным.
Итак, во-первых, все представленные оптимизации являются универсальными для размеров сетки, скажем, от 100x100. На сильно меньших размерах вряд ли понадобится запускать: при запуске в один процесс количество точек решения будет недостаточным, при запуске на много процессов возрастут накладные расходы на обмен данными. Где-нибудь сказано, что существенно используется размер сетки? В определённых местах можно было потребовать чётный размер, например, но этого не сделано, сохранён общий алгоритм. Вообще, все представленные оптимизации направлены на ускорение самой вычислительно объёмной части, которая в рамках одного шага метода составляет O(MN) для сетки размера MxN.
Во-вторых, какое обоснование вас бы удовлетворило? Сделать запуски на всех размерах от 1001x1001 до 1500x1500? Это немного не научно.
В-третьих, о каких таких матрицах особого вида вы здесь говорите? Я честно не понимаю. У меня разностная схема для уравнения Пуассона в двумерной области и метод наименьших невязок. А что вы придумали в качестве "решаемой в статье" задачи — решение обычной СЛАУ?
В-четвёртых, да, если в какой-либо (любой, не этой) задаче появляются матрицы особого вида, то к ним применяют другие подходы. Начиная с асимптотически менее сложных алгоритмов, использующих структуру матриц, и заканчивая отдельными реализациями, эффективно работающими с представлением в памяти.
Итак, во-первых, все представленные оптимизации являются универсальными для размеров сетки, скажем, от 100x100.
Даже в такой формулировке --- конечно же нет.
Можно начать с того, чтобы посчитать размеры обрабатываемых массивов и сравнить с размерами кэшей. В исходной формулировке используются 2 массива даблов по 1млн элементов. Они занимают чуть меньше 16MB, что сравнимо с размерами L3, точнее несколько больше 12MB L3 i7-9700K, равно L3 Э-8СВ и меньше L3 Power8. Соответственно, оптимизация "предвычисления q, F", удваивая размер обрабатывемых данных, существенно меняет ситуацию. Матрица же 100x100 это всего лишь 10тыс. элементов общим размером 160KB -- всё локализуется в L2.
Кроме написанного, есть масса других более тонких кэшевых эффектов. Например, ассоциативность. Возьмите размер матрицы, кратный большой степени двойки (2^N) -- и увидете эффект сами. Сравнивать с 2^N +- <маленькое простое число>
Спасибо за внимательность! Действительно, граничный случай размеров кэша я не учёл, когда писал, что это всё универсальные оптимизации. Тем не менее, при запуске расчётов имеет смысл подбирать размер задачи так, чтобы она полностью помещалась в кэш, да и желательно L2. Например, это как раз верно при размере сетки 100x100 и результат применения предвычислений положительный как на Эльбрусе, так и на Intel (хоть и небольшой, 5%). Вероятно, именно это объясняет, почему при исходных замерах на Intel было замедление.
Вопрос ассоциативности — это уже более глубокое погружение и необходимость задумываться о свойствах конкретного процессора. Предлагаемый пример опять же можно отнести на этап подбора размера задачи. Например, кажется, что нет ничего плохого в том, чтобы увеличить количество точек до степени 2, если это позволит считать быстрее. Попробую на досуге проверить на этой задаче, хоть тут и может быть сложно подобрать подходящее разложение MxN (иначе вылезут и другие эффекты).
Выглядит так, как будто компилятор для Эльбруса дубовый. Компилятор от Intel банально более крутой. Еще когда я в 2007 году в Летней Школе Intel, он тогда за счет оптимизаций рвал всех. Кстати наверно, если ты учишься - то тебе будет полезно и интересно туда попасть. https://russia-students.ru/
Itanium они своим компилятором (экспертизой в компиляторах) не спасли, рынок так и не прожевал VLIW. Может, сейчас и правда новое время, какой-нибудь LLVM уже дорос до возможностей реализации автоматических оптимизаций приемлемого уровня на подобных процессорах, или даже нейросетки какие-нибудь. Но, кажется, тут надо вложить в разработку компилятора сильно больше ресурсов, чем в сам процессор.
Интел в свое время всю команду компиляторщиков МЦСТ переманил. Не помогло. Ну и сейчас такой тип статической параллелизации не в тренде, производительность набирают специализированными исполняющими устройствами.
Тем печальнее выглядят перспективы. Может, им перед своим VLIW-ядром припаять блок декодера-транслятора x86-команд? (Ну ладно, я помогал как мог, дальше пусть сами.)
Он там уже есть, эльбрус умеет выполнять х86 код, хоть и очень медленно.
Сдаюсь :).
Думаете уже ничто не поможет? :)
Эльбрус просто не надо позиционировать как универсальный. Надо "он отлично подойдет для того, сего, этого и еще 100500 пунктов". Но по каждому надо провести подготовительную работу по оптимизации и подгонке. Покупать отечественное так или иначе заставят, это уже понятно, но чтобы не портить репутацию не надо его ставить там, где простой пользователь без технической подготовки заметит очевидную разницу и там где могут запускать индусский код. Код тоже должен быть русским!
Смотрел интервью с разными представителями МЦСТ, позиционируется именно как универсальная платформа в том числе для самых офисных нужд, и да, основной мотив его использования видится именно в запретах на импорт (с несоблюдением которого они и борятся сейчас).
Возможность запускать индусский код - это плюс, а не минус (хотя думаю, что это у вас был сарказм об "русском коде"). Надеяться на Великих Программистов (о которых, конечно, в ближайшее время мы услышим ещё много саг и легенд) в вопросах развития отрасли страны совершенно точно не стОит. Иначе у нас не процессоры будут, а автоматы Кемпелена, и теплопакет устройства будет рассчитываться с учётом заваривания трёх пачек доширака в день.
Универсальный процессор должен уметь хорошо и быстро перемалывать универсальный код. Универсальный код в моем представлении очень близок к рандомному - там в любых пропорциях встречается что угодно. Как это сочетается с жестко заданным на момент написания/компилирования параллелизмом кода я не понимаю.
Но если мы ограничиваем круг задач, то для этого ограниченного набора становится возможным провести оптимизацию с распараллеливанием. И получить вполне годный результат. Потихоньку-помаленьку можно закрыть очень широкий круг решаемых задач, но сильно сомневаюсь, что поделки на питончике с жаваскриптом когда нибудь войдут в этот список.
В 20м веке выбирали архитектуры, в нулевых растили частоту, в десятых наращивали параллелизм. Из этих подходов выжали почти все, что могли. И как распараллелить реальные "универсальные" программы тоже исследовали. Следующий этап, который уже вовсю применяется, - специализация. Процессор не должен быть универсальной молотилкой, он должен надежно и быстро связывать специализированные вычислительные блоки. Короче меня risc v приложило.
Это всё так идеилистически и абстрагированно звучит, что на реальность это всё ещё нужно постараться спроецировать :). А реальность, на мой взгляд, заключается в следующем: на фоне дефицита технических кадров и общего развала (отставания) отрасли в ней сформировались тренды, мало связанные с реальностью (экономикой), культивировался авторитаризм Бабаяна (бога церкви "неулучшаемых архитектур") и возникла сложность "продажи" "верхам" более прагматичных и практичных направлений разработки (если такие попытки вообще осуществлялись). RISC V, ARM, x86 стратегически неверно будет брать на роль архитектуры "национального процессора", но их подходы (и историю набивания шишек) совершенно точно стОило бы учесть.
Конечно, это всё диванная аналитика, сам я совершенно не в теме и сужу только по нескольким интервью (и по очень поверхностному пониманию процессоростроения). Но сложилось ощущение, что перспективы Эльбруса в риторике где-то "в верхах" очень сильно преувеличиваются. Такое ощущение, что основная ценность Эльбруса заключается в "аналоговнет".
Бабаян между прочим почетный работник Интела! У нас еще есть Байкалы с ARMом и комдивы с MIPSом уже в кремнии. На подходе первые risc-v.
Уникальная ISA тянет за собой уникальную экосистему - компиляторы, среды разработки, библиотеки, операционные системы и т.п. Просто для начала разработки прикладных программ. Создать все это на должном уровне тоже не просто и не дешево. А без всего это процессор просто дорогой кусок кремния, каким бы он ни был.
Да, про Бабаяна я в курсе, оттого его аторитет ещё более устрашающ. И почему же сразу "уникальная" ISA, не надо сильно уникальничать. И уж точно это можно сделать менее уникальным, чем уникальность Эльбруса сейчас (он "уникален" именно из-за недостатка качественных компиляторов, и наращивать это качество Эльбрус обречён в одиночестве).
Я не о покупке чужого, а о разработке своего (в интервью в том числе рассказывали об проблемах лицензирования и ARM, и x86, и даже бесплатного RISC-v для своих процессоров).
Я не о покупке (лицензировании) чужого, а о разработке своего. RISC-V, как я понимаю, тоже получится не свой, а MIPS, возможно, устарел морально (или с ним тоже лицензионные проблемы, на которые Китай просто забивает). Но я сварщик не настоящий, если что, и более предметно вряд ли смогу что-то сказать :).
Смысл - в технологической и экономической независимости. И ещё в некоторых критериях про национальную безопасность (контроль технологических цепочек с точки зрения ИБ), там лучше послушать представителей МЦСТ, они вполне доходчиво этот вопрос раскрывают. И этот смысл вполне себе объективный, конкурировать и на мировой арене имеет смысл даже в уже существующих дисциплинах, имеет смысл завязывать на себе производственные процессы и разработку. Свободная лицензия - это тоже лицензия. Тоже отсутсвие контроля над развитием отрасли и риск "распыления" стандартов. Китай это всё уже понял.
Глобализация - она только в комиксах такая, где добрые американцы (и связанные капиталы) раздают технологические плюшки, выстраданные кровью и пОтом, остальным голодранцам "во имя добра" :).
Но я не могу поддержать этот разговор на более предметном уровне, и так уже от вопросов "VLIW vs RISC/CISC", в которых у меня мало компетенций, меня затащили в глобально-политические, в которых их ещё меньше :).
Вы озвучиваете какие-то поверхностные и субъективные оценки и слегка наивно персонализируете стороны. Я не смогу поддержать этот разговор. Вряд ли мы с вами родим тут новые истины или повлияем на развитие проектов МЦСТ хоть каким образом :).
Я стараюсь вообще не оценивать эмоционально, для меня Эльбрус не хороший или плохой, просто вот есть такой. Это не хорошо или плохо, мне от этого никак, я с ним не пересекаюсь ни по работе, ни в быту. А советы куда там лучше или хуже потратить силы МЦСТ (которые, конечно, им очень нужны :)) - уже высказал с дивана, с "высоты" своего понимания функций государства и устройства процессоров :). Мнение не совпадает с вашим, судя по всему, ну, такое вот мнение, и бох с ним :).
Там была проблема выбора. Весь этот зоопарк очень дорого поддерживать. Даже Intel(!) была не в состоянии по деньгам поддерживать одновременно x86, x86_64, Itanium и ARM проекты.
У Интела был прекрасный Итаниум, у Интела был прекрасный XScale ARM.
Первый угробили в угоду x86_64, XScale угробили в угоду Silverthorne (который стал называться Atom). В 2007 году казалось что Silverthorne возьмет всю мобильную нишу. Нишу графических адаптеров возьмёт Larrabee (поэтому у стажеров тогда NDA был на три года). Т.е. абсолютно везде будет x86 )))
В итоге эти наполеоновские планы не сбылись. Atom взял нишу нетбуков/субноутбуков, ARM стал подавлющей архитектурой на мобилке, а лидерство в графических адаптерах захватила NVidia
сейчас понабегут фаны эльбруса, пересчитают все на мегагерцы и заявят, что эльбрус круче всех.
Могу предположить, что минусуют вас за форму подачи и бессодержательность первого комментария. Написали бы сразу развёрнуто, был бы разговор, а то я вот просто проигнорировал первый комментарий, так как уже давал развёрнутый ответ на похожий. Теперь же мне есть, чем дополнить.
Всего в алгоритме участвует 5 основных матриц, так что кажется справедливым смотреть на то, чтобы они все поместились в кэш одного уровня. При размере 1000x1000 это 38 МБ, не помещается в L3 ни на Intel, ни на Эльбрусе.
Т.е. 42800*1000*1000*8/5c ~ 637Gb/s а такая скорость только у кэшей, у памяти на порядок меньше.
Вынужден обвинить вас в тотальной невнимательности. Полные исходники размещены на github, об этом сказано в статье, дана ссылка, потом внизу ссылка продублирована. А дальше ещё хуже: я пишу, что замеряется время выполнения 1000 шагов, а вы мне сейчас приводите непонятный расчёт скорости памяти. Мне кажется, лучше сначала читать статью, а потом идти в комментарии (да-да, только в комментариях упоминается 428000, это вас выдаёт).
Очевидно, что Эльбрус в существующем виде без существенной переработки компилятора будет показывать очень слабые результаты в смысле производительности. Ручная оптимизация при массовом применении процессора представляет серьёзную проблему. Практически плохо решаемую.
Потому что одного компилятора для современной разработки очень мало. Что пишут на "голом" Си или С++ в блокноте? Как у Эльбруса с инфраструктрой обстоят дела? Со стеком разработки?
Линукс портирован, значит C/С++, GNU make должны работать. В приниципе после этого можно портировать какой-то стек. Возникет закономерный вопрос. . Где потребители этой продукции. И зачем этим вообще заниматься.
линукс + gсс + x86 и уже можно как-то работать. А хочется не как-то, а нормально или даже хорошо. В специализированном применении можно и нужно оптимизировать определенный набор софта под конкретную платформу, и работать с этим будет специально обученый человек. А в универсальном применении пользователь айфонами избалованан, нужно чтобы минимум нормально работало "из коробки". До этого как до луны пешком.
Возможно на специализированных серверах оптимизируют и поднимут определенное ПО. Но цену системы в комплексе все эти действия поднимают существенно - и железо дорогое, и софт дорогой, и поддержка дорогая, да еще по скорости не ахти.
Платформа в целом уже не кокурентноспособна. Так что дешевле взять другой процессор, менее уникальный. Но это будет другой процессор и, скорее всего, из другой страны родом. Попытка производить микроэлектронику в натуральном феодальном поместье выглядит довольно нелепо.
Микроэлетроника в современном мире стратегически важный ресурс. Развить и поднять отрасль - не так уж просто, это всем понятно. И сам по себе эльбрус не плох, но пока на звание универсального не тянет.
Сейчас модно хендмейдом заниматься. Частные лица хлебопечки заводят да смеси для них покупают. Буханка раз в 5 дороже выходит. А у государства масштаб покрупнее - заводики для выпекания микропроцессоров. Тенденция такая, мировая.
Для тестовых замеров будем смотреть на время выполнения 1000 шагов итерационного метода на одном ядре процессора
Сила современных процессоров — в их многоядерности и взаимодействии между ядрами и кэшем. Распараллелив вычисления между всеми ядрами, разница между процессорами будет совершенно другой.
А если провести обратный эксперимент и попробовать код оптимизировать для любого из 2х других процессоров, вот это будет интересно)
Как мне кажется задача упирается прежде всего в пропускную способнось памяти, а не в вычислительные возможности процессора. Intel Core i7-9700K имеет теоретическую производительность 50 GFLOPS на ядро (FP64) для FMA. В вашем цикле порядка 10 операций умножения и сложения. Значит теоретически он может выполняться раз в 10 быстрее (~500 мс). Все упирается в пропускную способность памяти, а не в векторизацию и т.п. Это к стати ответ, почему Эльбрус почти догнал гораздо более высокочастоный Intel и Power.
Да, конечно, именно этому посвящён предпоследний раздел: демонстрируется, что то же количество арифметики при отказе от одной загрузки из памяти работает быстрее. Я показал это на примере Эльбруса, такое же поведение на Intel. Только IBM выбился: при наличии бесполезной арифметической операции и отказе от загрузки из памяти он ускорился (время было около 4 с), но ещё большее ускорение получилось после того, как убрал лишнюю арифметику (итоговые 3.8 с, вошедшие в таблицу).
Тем не менее, явно нельзя отрицать, что от векторизации и прочих шагов есть положительный эффект. В общем-то, именно они привели к состоянию, когда на первый план вышла память. С удовольствием продемонстировал бы что-нибудь ещё на тему памяти, но в этой теме у меня пока нет достаточного опыта, чтобы поделиться им.
Примечательно, что на Эльбрусе, который имеет фиксированные и
относительно большие штрафы за вызов функций, ускорение составляет 2.2
раза, а на Intel и IBM — 2.9 и 1.5 раза, соответственно. Так что на
предсказатель переходов и внеочередное исполнение надейся, а сам не
плошай
Тут некорректное сравнение. Инлайн функции в Интеле (про IBM не знаю) позволил сделать автовекторизацию, отчего и получился такой привар почти в 3 раза. Т.е. если хочется померять ускорение непосредственно от инлайна для Интел, надо выключить опциями векторизацию. Либо тогда уже сравнивать все улучшения от оптимизаций для Эльбруса вплоть до векторизации (т.к. без инлайна они всё равно были бы невозможны), что будёт равно 223.6/6.19 =~ 36 раз
В целом, хотя статья очевидно направлена на описание оптимизаций Эльбруса и требовать таких же заоптимизаций для x86/IBM неправильно, но приведённые таблички могут легко ввести в заблуждение неподготовленного читателя. Например, как приведённый пример с векторизацией. Исходя из табличек может сложиться впечатление, что векторизация на том же Интеле вообще ничего не даёт (3.67->3.67), хотя в реальности векторизация применилась на шаге инлайна.
Также было бы здорово привести хотя бы конечные версии ассемблерного кода для x86/IBM. Потому что лезть пересобирать, запускать и т.д. уже как-то облом, а вот беглый взгляд на ассемблер может дать много ответов на интересующие вопросы. Например, у меня есть подозрение, что у Интела не включилось fma, но исходя из данных в статье это сложно установить.
Т.е. если хочется померять ускорение непосредственно от инлайна
Возможна, у меня не самая удачная формулировка получилась, но цели измерять ускорение непосредственно от подстановки функции не стояло. Когда хочется ускорить вычисления, не совсем важно, как именно получено ускорение, намного важнее, что нужно сделать, чтобы его получить. Идея здесь в том, что возможность подстановки функции открывает дорогу другим важным оптимизациям, которые невозможны просто за счёт предсказателя переходов. Ну и, конечно, я не пытаюсь теоретизировать на общих основаниях, это пока не мой уровень, здесь речь только о классе вычислительных задач, в том или ином виде подобных этой.
может сложиться впечатление, что векторизация на том же Интеле вообще ничего не даёт
Да, нехорошо получилось. Приписал, что это "ручная векторизация", теперь недопонимания вроде не должно возникнуть.
Также было бы здорово привести хотя бы конечные версии ассемблерного кода для x86/IBM.
Не хотелось загромождать статью, но вот только сейчас пришла идея, что будет вполне удобным для всех решением оформить это дело в виде файлов в репозитории. Так что чуть позже добавлю, а сейчас приведу основной цикл на AMD64 (его я проверял глазами, а вот аналога -fverbose-asm на IBM я не нашёл и не знаком с его ассемблером, так что не могу ничего сказать). FMA, естественно, есть, иначе бы пришлось что-то с этим делать, потому что это было бы совсем не честно.
Векторизованный [alpha != 0] цикл из calc_aw_b:
..B3.14: # Preds ..B3.14 ..B3.13
# Execution count [4.20e+00]
vmovupd 16(%rdi,%r15,8), %ymm10 #218.27
vmovupd 32(%rax,%r15,8), %ymm5 #219.27
vmovupd 24(%rdi,%r15,8), %ymm7 #218.27
vaddpd %ymm10, %ymm10, %ymm9 #223.51
vaddpd (%r9,%r15,8), %ymm5, %ymm6 #223.40
vaddpd 8(%rdi,%r15,8), %ymm7, %ymm8 #224.55
vsubpd %ymm9, %ymm6, %ymm11 #223.51
vsubpd %ymm9, %ymm8, %ymm12 #224.55
vfmadd213pd 16(%r10,%r15,8), %ymm4, %ymm11 #224.55
vfmsub231pd 16(%r8,%r15,8), %ymm10, %ymm11 #224.55
vfnmadd213pd %ymm11, %ymm3, %ymm12 #224.55
vmovupd %ymm12, 16(%r11,%r15,8) #224.13
addq $4, %r15 #217.9
cmpq %r14, %r15 #217.9
jb ..B3.14 # Prob 82% #217.9
но цели измерять ускорение непосредственно от подстановки функции не стояло
Да, это очевидно. Если бы не было отсылки к битью линейкой по пальцам, даже поленился бы написать комментарий.
Идея здесь в том, что возможность подстановки функции открывает дорогу другим важным оптимизациям, которые невозможны просто за счёт предсказателя переходов
Тут предсказатель переходов непричём, но не суть, далеко за рамки статьи уже уйдём.
FMA, естественно, есть
Ок, отлично. Просто с применением FMA есть определённые нюансы на Интеле, из-за того, что операция сделана отдельным расширением, и люди часто с этим промахиваются.
Ну а так, можно согласиться с одним из комментаторов выше - похоже мы сели на пропускную способность кэшей. Там в L1/L2 скорость подкачки данных 64/32 байта соответственно. А здесь в итерацию цикла идёт загрузка 7*32 = 224 байта. Т.е. скорее всего мы где-то на уровне 7 тактов на итерацию сидим из-за скорости подкачки в L2. Но это я всё умозрительно прикинул, внутреннее устройство ОоО ядра куда сложнее, чтобы делать прикидки без проверок.
Используйте -qopt-subscript-in-range для странных счетчиков с интеловским компилятором и будет вам счастье
Замечательная статья. Читал запоем! Спасибо. :)
Война с компилятором и собой: об оптимизациях вещественной арифметики на Эльбрусе