Project Euler — некоммерческий проект, демонстрирующий, как математика помогает писать качественные и быстрые программы. По-моему, если к математике добавить векторизованный код, результат будет интереснее.
Давайте взглянем на первую, самую простую задачу проекта и посмотрим, какие дополнительные уроки мы сможем извлечь.
Условие: найдите сумму всех натуральных чисел меньших 1000 и кратных 3 или 5.
У меня под рукой оказалась система с процессором RISC-V, поддерживающим векторное расширение системы команд (RVV). На ней и будем экспериментировать.
Первая, примитивная версия программы выглядит вот так:
В цикле просматриваем натуральные числа, находим остатки от деления на 3 и 5, и, если хоть один из них равен нулю, прибавляем число к сумме нарастающим итогом.
Посмотрим на машинный код, сгенерированный компилятором:
Нас поджидает парочка сюрпризов.
Во-первых, компилятор автоматически векторизовал цикл. Все машинные инструкции, начинающиеся с буквы v — векторные. Это обычная история: как правило, я начинаю свою работу не с чистого листа, а с кода, над которым уже поработал оптимизирующий компилятор, и, вполне возможно, квалифицированный программист.
Во-вторых, в машинном коде отсутствует команда деления. Деление – очень долгая и энергозатратная операция. Поскольку машинное представление целых чисел имеет ограниченную разрядность и склонно к переполнению, эффект переполнения можно использовать для замены операции деления на константу умножением. Что и проделал компилятор.
Хорошее описание алгоритма замены деления умножением для 64-разрядных чисел попалось мне в статье Даниэля Лемара.
Если нам заранее известен делитель d, то при компиляции программы вычислим константу:
Тогда частное от деления произвольного 64-разрядного числа на d можно вычислить с помощью умножения:
Имея частное, легко получить остаток с помощью еще одного умножения и вычитания. Но Лемар пошел дальше и первым вывел признак делимости на d:
Таким образом, можно проверить делимость n на d с помощью всего одного умножения. Вооруженные этим знанием, мы можем превзойти компилятор в оптимизации:
RVV относится в векторным системам команд называемых Vector Length Agnostic, что можно перевести как длинонезависимые. То есть, длина вектора может быть любой степенью двойки, умноженной на 128. Программу можно (и нужно) писать исходя из факта, что длина вектора нам заранее неизвестна и выясняется только в момент выполнения программы, в нашем случае, в строке 7.
Стандартный заголовок векторного цикла представлен в строках 13-14.
Строка 19 – прекрасный пример хитрой инструкции RVV с двумя масками, булевым предикатом и целочисленной маской длины.
В строках 24-25 происходит редукция частичных сумм в окончательный результат. Это пример нелюбимых мной, но зачастую неизбежных горизонтальных операций, которые производят не поэлементное действие над значениями, хранящимися в векторе, а затрагивают одновременно все элементы вектора. Такие операции выполняются долго, требуют сложных и энергозатратных пересылок данных в процессоре и тормозят конвейер выполнения инструкций. Мы с ними организованно боремся, но повторюсь, иногда без них не обойтись. В нашем случае хотя бы удалось вытащить горизонтальную операцию из тела цикла, а ведь разработчики явно затачивали инструкцию под выполнение в цикле, это ясно из набора параметров команды.
Посмотрим на машинный код:
Он компактнее и работает быстрее.
>Попробуем улучшить этот результат. Числа кратные 3, 5 или 15 образуют арифметическую прогрессию. Число членов прогрессии до n исключительно равно
Используя формулу суммы арифметической прогрессии, выведем формулу для решения задачи:
Третье слагаемое, вернее, вычитаемое, нужно, чтобы числа, делящиеся одновременно на 3 и на 5 не были учтены дважды.
Теперь возможно решить задачу, не используя цикл:
Это и есть оптимальное решение, которое подразумевает Project Euler. Но мы пойдем дальше. Поскольку три компоненты суммы вычисляются с применением одних и тех же операций, векторизуем быстрое решение:
Результаты теста на производительность не радуют.
Векторное решение работает медленнее быстрого скалярного. В чем же дело?
Во-первых, векторное решение настолько короткое, что не позволяет ускорения за счет внеочередного выполнения инструкций.
Во-вторых, инициализация векторной машинерии в процессоре отнимает некоторое время, которое не окупается при решении столь крохотной задачи.
В-третьих, схемотехника процессоров RISC-V, в особенности экзотического модуля векторных вычислений, пока далека от совершенства. Для сравнения, аналогичный векторный код для процессора Intel Ice Lake с архитектурой AVX512 показывает куда лучший результат.
Несмотря на временные трудности с RISC-V, я убежден, что математика вкупе с векторизацией позволяет добиваться лучших результатов, чем просто математика.
На том и стоим.