JEP 338: Vector API (Incubator)

Аннотация

Предоставить первую итерацию модуля Incubator jdk.incubator.vector для записи векторных вычислений, которые во время выполнения надёжно компилируются в оптимальные векторные аппаратные инструкции на поддерживаемых архитектурах процессоров и за счёт этого работают быстрее эквивалентных скалярных вычислений.

Цели

• Ясный и лаконичный API: API должен позволять ясно и лаконично выражать широкий спектр векторных вычислений, состоящих из последовательности векторных операций, которые часто объединены в циклы и могут содержать управляющие конструкции. Должна быть возможность записать вычисление, не зависящее от размера вектора (или числа дорожек в векторе), чтобы такие вычисления были переносимы между аппаратными платформами с разными размерами векторов (подробнее см. следующую цель).

• Независимость от платформы: API должен быть независимым от архитектуры, чтобы допускать реализации среды выполнения на разных архитектурах процессоров, поддерживающих векторные аппаратные инструкции. Как обычно для API Java, там, где оптимизация под платформу и переносимость противоречат друг другу, предпочтение будет отдаваться переносимости Vector API, даже если некоторые платформенно-зависимые идиомы нельзя напрямую выразить в переносимом коде. Следующая цель, касающаяся производительности на x64 и AArch64, отражает уместные цели производительности на всех платформах, где поддерживается Java. Особый интерес в этом отношении представляет ARM Scalable Vector Extension (SVE): нужно обеспечить, чтобы API мог поддерживать эту архитектуру, хотя на момент написания неизвестно ни одной её аппаратной реализации, выпускаемой серийно.

• Надёжная компиляция во время выполнения и производительность на архитектурах x64 и AArch64: среда выполнения Java, а именно компилятор C2 в HotSpot, должна на подходящих архитектурах x64 компилировать последовательность векторных операций в соответствующую последовательность векторных аппаратных инструкций, например поддерживаемых расширениями Streaming SIMD Extensions (SSE) и Advanced Vector Extensions (AVX), и тем самым генерировать эффективный и производительный код. Программист должен быть уверен, что записанные им векторные операции будут надёжно и близко отображаться на соответствующие аппаратные векторные инструкции. То же должно относиться и к подходящим архитектурам ARM AArch64 при компиляции в последовательность векторных аппаратных инструкций, поддерживаемых Neon.

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

Что не является целью

• Улучшение поддержки автовекторизации в HotSpot не является целью.

• Поддержка в HotSpot векторных аппаратных инструкций на архитектурах процессоров, отличных от x64 и AArch64, не является целью. Такая поддержка оставлена для последующих JEP. Однако важно подчеркнуть, как сказано в целях, что API не должен исключать такие реализации. Кроме того, выполненная работа может естественным образом использовать и расширять существующие в HotSpot абстракции векторной поддержки для автовекторизации, что облегчит такую задачу.

• Поддержка компилятора C1 в этой и будущих итерациях не является целью. Мы ожидаем, что компилятор Graal будет поддержан в дальнейшей работе.

• Поддержка строгих вычислений с плавающей точкой, определяемых ключевым словом Java strictfp, не является целью. Результаты операций с плавающей точкой над скалярами с плавающей точкой могут отличаться от результатов эквивалентных операций с плавающей точкой над векторами скаляров с плавающей точкой. Однако это не исключает возможностей выразить или контролировать нужную точность или воспроизводимость векторных вычислений с плавающей точкой.

Мотивация

Векторные вычисления состоят из последовательности операций над векторами. Вектор представляет собой (как правило) фиксированную последовательность скалярных значений, число которых соответствует числу векторных дорожек, определённому аппаратурой. Бинарная операция, применённая к двум векторам с одинаковым числом дорожек, для каждой дорожки применяет эквивалентную скалярную операцию к соответствующим двум скалярным значениям из каждого вектора. Обычно это называют Single Instruction Multiple Data (SIMD).

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

HotSpot поддерживает автовекторизацию, при которой скалярные операции преобразуются в операции superword, которые затем отображаются на векторные аппаратные инструкции. Набор преобразуемых скалярных операций ограничен, а само преобразование чувствительно к изменениям формы кода. Кроме того, может использоваться лишь часть доступных векторных аппаратных инструкций, что ограничивает производительность сгенерированного кода.

Разработчику, который хочет писать скалярные операции, надёжно преобразуемые в операции superword, нужно понимать поддержку автовекторизации в HotSpot и её ограничения, чтобы получить надёжную и стабильную производительность.

В некоторых случаях разработчик может вообще не суметь написать преобразуемые скалярные операции. Например, HotSpot не преобразует простые скалярные операции вычисления хэш-кода массива (см. реализации метода Arrays::hashCode в исходном коде JDK) и не может автовекторизовать код лексикографического сравнения двух массивов (именно поэтому для лексикографического сравнения был добавлен intrinsic, см. 8033148).

Vector API призван решить эти проблемы: он даёт механизм для написания сложных векторных алгоритмов на Java, используя уже существующую в HotSpot поддержку векторизации, но с пользовательской моделью, которая делает векторизацию гораздо более предсказуемой и надёжной. Написанные вручную векторные циклы могут выражать высокопроизводительные алгоритмы (например, векторизованный hashCode или специализированное сравнение массивов), которые автовекторизатор, возможно, никогда не оптимизирует. Есть множество областей, где может пригодиться этот API явной векторизации, например машинное обучение, линейная алгебра, криптография, финансы, а также использование внутри самого JDK.

Описание

Вектор будет представлен абстрактным классом Vector<E>. Переменная типа E соответствует обёрточному типу скалярных примитивных целочисленных типов элементов или типов элементов с плавающей точкой, которые охватывает вектор. У вектора также есть форма, определяющая размер вектора в битах. Форма вектора будет определять, как экземпляр Vector<E> отображается на векторный аппаратный регистр при компиляции векторных вычислений компилятором C2 в HotSpot (отображение экземпляров на векторные регистры x64 см. ниже). Длина вектора (число дорожек или элементов) будет равна размеру вектора, делённому на размер элемента.

Поддерживаемый набор типов элементов (E) будет состоять из Byte, Short, Integer, Long, Float и Double, соответствующих скалярным примитивным типам byte, short, int, long, float и double.

Поддерживаемый набор форм будет соответствовать размерам векторов 64, 128, 256 и 512 бит. Форма размером 512 бит может упаковать byte в 64 дорожки или int в 16 дорожек, а вектор такой формы может обрабатывать 64 значения byte или 16 значений int за раз.

Примечание: мы считаем, что эти простые формы достаточно универсальны, чтобы быть полезными на всех платформах, поддерживающих Vector API. Однако по мере экспериментов с будущими платформами во время инкубации этого JEP мы можем изменить устройство параметра формы. Такая работа не входит в начальный объём этого JEP, но эти возможности отчасти определяют нынешнюю роль форм в Vector API. См. раздел «Дальнейшая работа» ниже.

Сочетание типа элементов и формы определяет вид (species) вектора, представленный VectorSpecies<E>

Экземпляр Vector<E> неизменяем и является value-based-типом, который по умолчанию сохраняет инварианты Identity (идентичность объекта) (об ослаблении этих инвариантов см. ниже).

Операции над векторами можно разделить на поэлементные (lane-wise) и междорожечные (cross-lane). Поэлементные операции, в свою очередь, делятся на унарные, бинарные, тернарные и операции сравнения. Междорожечные операции делятся на перестановки, преобразования и редукции. Чтобы уменьшить поверхность API, мы определим для каждого класса операций общие методы, которые принимают оператор на вход. Поддерживаемые операторы являются экземплярами класса Operator и определены как статические final-поля в классе VectorOperators. Для некоторых распространённых операций (например, add, mul), называемых полносервисными, будут выделенные методы, которые можно использовать вместо обобщённых.

Некоторые операции над векторами, например поэлементное приведение (cast) и переинтерпретация (reinterpret), по своей природе меняют форму. Наличие меняющих форму операций в векторном вычислении может непреднамеренно повлиять на переносимость и производительность. Поэтому везде, где это применимо, API будет определять дополнительный вариант такой операции, не меняющий форму. Пользователям рекомендуется писать не зависящий от формы код, используя не меняющие форму варианты операций. Кроме того, операции, меняющие форму, будут явно отмечены в Javadoc.

Vector<E> объявляет набор методов для распространённых векторных операций, поддерживаемых всеми типами элементов. Для поддержки операций, специфичных для типа элементов, есть шесть абстрактных подклассов Vector<E>, по одному для каждого поддерживаемого типа элементов: ByteVector, ShortVector, IntVector, LongVector, FloatVector и DoubleVector. Эти подклассы определяют дополнительные операции, привязанные к типу элементов, поскольку сигнатура метода ссылается на тип элементов (или соответствующий тип массива), например операции редукции (скажем, суммирование всех элементов в скалярное значение) или сохранение элементов вектора в массив. Они также определяют дополнительные полносервисные операции, специфичные для целочисленных подтипов, например побитовые операции (скажем, логическое «или»), и операции, специфичные для типов с плавающей точкой, например математические операции (скажем, трансцендентные функции, такие как pow()).

Эти классы, в свою очередь, расширяются конкретными подклассами, определёнными для разных форм (размеров) векторов.

Конкретные подклассы не являются публичными, поскольку нет необходимости предоставлять операции, специфичные для сочетания типа и формы. Так поверхность API сводится к сумме аспектов, а не к их произведению. Как следствие, экземпляры конкретных классов Vector нельзя создать напрямую. Вместо этого экземпляры получают через фабричные методы, определённые в базовом классе Vector<E> и его подклассах для конкретных типов. Эти методы принимают на вход вид нужного экземпляра вектора. Фабричные методы дают разные способы получить экземпляры векторов, например экземпляр вектора, элементы которого инициализированы значениями по умолчанию (нулевой вектор), или вектор из массива, а также обеспечивают каноническую поддержку преобразования между векторами разных типов или форм (например, приведение).

Для поддержки управления потоком выполнения соответствующие векторные операции будут дополнительно принимать маски, представленные публичным абстрактным классом VectorMask<E>. Каждый элемент маски, булево значение или бит, соответствует дорожке вектора. Когда маска подаётся на вход операции, она определяет, применяется ли операция к каждой дорожке: операция применяется, если бит маски для дорожки установлен (равен true). Если бит маски не установлен (равен false), выполняется альтернативное поведение. Как и в случае с векторами, экземпляры VectorMask<E> являются экземплярами (закрытого) конкретного подкласса, определённого для каждого сочетания типа элемента и длины. Экземпляр VectorMask<E>, используемый в операции, должен иметь тот же тип и ту же длину, что и экземпляр(ы) Vector<E>, участвующие в операции. Операции сравнения создают маски, которые затем можно передать на вход другим операциям, чтобы выборочно отключить операцию на определённых дорожках и тем самым эмулировать управление потоком выполнения. Другой способ создания масок — статические фабричные методы в VectorMask<E>.

Мы ожидаем, что маски, вероятно, будут играть важную роль в разработке векторных вычислений, обобщённых по форме. (Это ожидание основано на ключевой роли регистров предикатов, эквивалента масок, как в ARM Scalable Vector Extensions, так и в Intel AVX-512.)

Пример

Вот простое скалярное вычисление над элементами массивов:

void scalarComputation(float[] a, float[] b, float[] c) {
   for (int i = 0; i < a.length; i++) {
        c[i] = (a[i] * a[i] + b[i] * b[i]) * -1.0f;
   }
}

(Мы предполагаем, что аргументы-массивы будут одного размера.)

Явный способ реализовать эквивалентное векторное вычисление с помощью Vector API выглядит так:

// Example 1

static final VectorSpecies<Float> SPECIES = FloatVector.SPECIES_256;

void vectorComputation(float[] a, float[] b, float[] c) {

    for (int i = 0; i < a.length; i += SPECIES.length()) {
        var m = SPECIES.indexInRange(i, a.length);
		// FloatVector va, vb, vc;
        var va = FloatVector.fromArray(SPECIES, a, i, m);
        var vb = FloatVector.fromArray(SPECIES, b, i, m);
        var vc = va.mul(va).
                    add(vb.mul(vb)).
                    neg();
        vc.intoArray(c, i, m);
    }
}

В этом примере вид (species) для векторов значений float шириной 256 бит получается из FloatVector. Вид хранится в поле static final, поэтому JIT-компилятор будет рассматривать значение поля как константу и, следовательно, сможет лучше оптимизировать векторное вычисление.

Векторное вычисление содержит ядро основного цикла, которое проходит по массивам с шагом, равным длине вектора (т. е. длине вида). Статический метод fromArray() загружает векторы float заданного вида из массивов a и b по соответствующему индексу. Затем выполняются операции, записанные в текучем стиле, и наконец результат сохраняется в массив c.

Мы используем маски, созданные indexInRange(), чтобы не допустить чтения и записи за пределами длины массива. Первые floor(a.length / SPECIES.length()) итераций будут иметь маску, в которой установлены все дорожки. Только последняя итерация, если a.length не кратно SPECIES.length(), будет иметь маску, в которой установлены первые a.length % SPECIES.length() дорожек.

Поскольку маска используется во всех итерациях, приведённая выше реализация может не достигать оптимальной производительности для массивов большой длины. То же вычисление можно реализовать без масок следующим образом:

// Example 2

static final VectorSpecies<Float> SPECIES = FloatVector.SPECIES_256;

void vectorComputation(float[] a, float[] b, float[] c) {
    int i = 0;
    int upperBound = SPECIES.loopBound(a.length);
    for (; i < upperBound; i += SPECIES.length()) {
        // FloatVector va, vb, vc;
        var va = FloatVector.fromArray(SPECIES, a, i);
        var vb = FloatVector.fromArray(SPECIES, b, i);
        var vc = va.mul(va).
                    add(vb.mul(vb)).
                    neg();
        vc.intoArray(c, i);
    }

    for (; i < a.length; i++) {
        c[i] = (a[i] * a[i] + b[i] * b[i]) * -1.0f;
    }
}

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

При работе с большими массивами приведённая выше реализация достигает оптимальной производительности.

Для этого второго примера компилятор HotSpot на процессоре Intel x64 с поддержкой AVX должен сгенерировать машинный код, похожий на следующий:

0.43%  / │  0x0000000113d43890: vmovdqu 0x10(%r8,%rbx,4),%ymm0
  7.38%  │ │  0x0000000113d43897: vmovdqu 0x10(%r10,%rbx,4),%ymm1
  8.70%  │ │  0x0000000113d4389e: vmulps %ymm0,%ymm0,%ymm0
  5.60%  │ │  0x0000000113d438a2: vmulps %ymm1,%ymm1,%ymm1
 13.16%  │ │  0x0000000113d438a6: vaddps %ymm0,%ymm1,%ymm0
 21.86%  │ │  0x0000000113d438aa: vxorps -0x7ad76b2(%rip),%ymm0,%ymm0
  7.66%  │ │  0x0000000113d438b2: vmovdqu %ymm0,0x10(%r9,%rbx,4)
 26.20%  │ │  0x0000000113d438b9: add    $0x8,%ebx
  6.44%  │ │  0x0000000113d438bc: cmp    %r11d,%ebx
         \ │  0x0000000113d438bf: jl     0x0000000113d43890

Это реальный вывод JMH-микробенчмарка для тестируемого кода примера, полученный с использованием прототипа Vector API и его реализации (ветка vectorIntrinsics репозитория разработки проекта Panama). Здесь показаны горячие участки машинного кода, сгенерированного C2. Хорошо видна трансляция в векторные регистры и векторные аппаратные инструкции. (Развёртывание циклов было отключено, чтобы трансляция была нагляднее; в противном случае HotSpot должен суметь развернуть цикл с помощью существующих техник оптимизации циклов C2.) Все выделения памяти под объекты Java устранены.

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

Однако у этого конкретного векторного вычисления есть несколько проблем:

1. Цикл жёстко привязан к конкретной форме вектора, поэтому вычисление не может динамически подстраиваться под максимальную форму, поддерживаемую архитектурой, которая может быть меньше или больше 256 бит. Поэтому код менее переносим и может быть менее производительным.

2. Вычисление верхних границ цикла, хотя здесь оно и простое, может быть частым источником ошибок программирования.

3. В конце требуется скалярный цикл, что дублирует код.

Первые две проблемы мы решим в этом JEP. Можно получить предпочтительный вид, форма которого оптимальна для текущей архитектуры, затем написать векторное вычисление с обобщённой формой, а метод вида может округлить длину массива вниз, например:

static final VectorSpecies<Float> SPECIES = FloatVector.SPECIES_PREFERRED;

void vectorComputation(float[] a, float[] b, float[] c,
        VectorSpecies<Float> species) {
    int i = 0;
    int upperBound = species.loopBound(a.length);
    for (; i < upperBound; i += species.length()) {
        //FloatVector va, vb, vc;
        var va = FloatVector.fromArray(species, a, i);
        var vb = FloatVector.fromArray(species, b, i);
        var vc = va.mul(va).
                    add(vb.mul(vb)).
                    neg();
        vc.intoArray(c, i);
    }

    for (; i < a.length; i++) {
        c[i] = (a[i] * a[i] + b[i] * b[i]) * -1.0f;
    }
}

vectorComputation(a, b, c, SPECIES);

Третья проблема в этом JEP будет решена не полностью и станет предметом дальнейшей работы. Как показано в первом примере, можно использовать маски, чтобы реализовать векторное вычисление без обработки хвоста. Мы ожидаем, что такие циклы с масками будут хорошо работать на ряде архитектур, включая x64 и ARM, но потребуют дополнительной поддержки со стороны JIT-компилятора для генерации максимально эффективного кода. Такая работа над циклами с масками, хотя и важна, выходит за рамки этого JEP.

Подробности о компиляторе HotSpot C2

Для достижения целей этого JEP у Vector API есть две реализации. Первая реализует операции на Java, поэтому она функциональна, но не оптимальна. Вторая делает эти операции intrinsic-функциями компилятора HotSpot C2 с особой обработкой типов Vector API. Это обеспечивает корректную трансляцию в аппаратные регистры и инструкции в случаях, когда существуют поддержка архитектуры и реализация такой трансляции.

Чтобы избежать лавинообразного роста числа intrinsic-функций, добавляемых в C2, будет определён набор intrinsic-функций, соответствующих видам операций, таким как бинарные, унарные, операции сравнения и так далее, которым передаются константные аргументы, описывающие особенности операции. Для поддержки intrinsic-реализации всех частей API потребуется около двадцати новых intrinsic-функций.

Экземпляры Vector являются value-based, то есть по сути значениями, для которых следует избегать операций, зависящих от Identity. Кроме того, хотя экземпляры векторов абстрактно состоят из элементов в дорожках, C2 не скаляризует эти элементы. Векторное значение рассматривается как единое целое, как int или long, которое отображается на аппаратный векторный регистр соответствующего размера. Для inline-типов потребуются некоторые связанные улучшения, чтобы векторное значение рассматривалось как единое целое.

Пока inline-типы недоступны, C2 будет особым образом обрабатывать экземпляры Vector, чтобы обойти ограничения escape-анализа и избежать упаковки (boxing). Поэтому следует избегать операций над векторами, зависящих от Identity.

Дальнейшая работа

Vector API значительно выиграет от value-типов, когда они будут готовы (см. проект Valhalla). Экземпляры Vector<E> смогут быть значениями, конкретные классы которых являются inline-типами. Это упростит оптимизацию и запись векторных вычислений. Подтипы Vector<E> для конкретных типов, такие как IntVector, могут оказаться не нужны при обобщённой специализации по inline-типам и объявлении методов, специфичных для типа.

Поэтому, как отмечено выше, будущая версия Vector API будет использовать inline-типы и улучшенные обобщённые типы (generics). В связи с этим API будет оставаться в статусе Incubator на протяжении нескольких выпусков JDK и будет адаптироваться по мере появления inline-типов.

Мы расширим API, чтобы загружать и сохранять векторы с помощью возможностей JEP 370 Foreign-Memory Access API, когда этот API перестанет быть инкубируемым. Кроме того, могут оказаться полезными раскладки памяти для описания видов векторов, например для прохода с шагом по сегменту памяти, состоящему из элементов.

Мы планируем улучшить реализацию следующим образом:

• добавить поддержку векторизованных трансцендентных операций (таких как логарифм и тригонометрические функции),

• улучшить оптимизацию циклов, содержащих векторизованный код,

• оптимизировать векторные операции с масками на поддерживающих их платформах и

• внести изменения для больших размеров векторов (например, поддерживаемых ARM SVE).

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

Альтернативы

Альтернативный подход — автовекторизация в HotSpot, но она потребовала бы значительной работы. Более того, по сравнению с Vector API она, вероятно, всё равно осталась бы хрупкой и ограниченной, поскольку автовекторизацию при сложном потоке управления выполнить очень трудно.

В целом, даже после десятилетий исследований (особенно для циклов по массивам в FORTRAN и C), похоже, что автовекторизация скалярного кода не является надёжной тактикой оптимизации произвольных циклов, написанных пользователем, если только пользователь не уделяет необычайно пристальное внимание неписаным соглашениям о том, какие именно циклы компилятор готов автовекторизовать. Слишком легко написать цикл, который не удастся автовекторизовать по причине, которую может обнаружить оптимизатор, но не человек, читающий код. Годы работы над автовекторизацией, даже в HotSpot, оставили нам множество механизмов оптимизации, которые срабатывают лишь в особых случаях. Мы хотим пользоваться этими механизмами чаще!

Тестирование

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

Мы также разработаем тесты производительности, чтобы убедиться, что цели по производительности достигнуты и векторные вычисления эффективно отображаются на векторные аппаратные инструкции. Скорее всего, это будут JMH-микробенчмарки, но потребуются и более реалистичные примеры полезных алгоритмов. Поначалу такие тесты могут находиться в отдельном репозитории проекта. Учитывая количество тестов и способ их генерации, перед интеграцией в основной репозиторий, вероятно, потребуется их отбор.

В дополнение к тестам производительности мы можем создать тесты по методу белого ящика, которые заставят JIT сообщать нам, что исходный код с Vector API действительно привёл к векторизации.

Риски и допущения

Существует риск, что API будет смещён в сторону SIMD-функциональности, поддерживаемой на архитектурах x64, но этот риск снижается благодаря поддержке AArch64. Это касается в основном явно фиксированного набора поддерживаемых форм, который препятствует написанию алгоритмов в обобщённом по форме стиле. Большинство остальных операций Vector API, по нашему мнению, склоняют к переносимым алгоритмам. Чтобы снизить этот риск, мы будем учитывать и другие архитектуры, в частности архитектуру ARM Scalar Vector Extension, модель программирования которой динамически подстраивается под единственную фиксированную форму, поддерживаемую оборудованием. Мы приветствуем и поощряем участие в этой работе участников OpenJDK, работающих над частями HotSpot, специфичными для ARM.

Vector API использует типы-обёртки (такие как Integer) в качестве заместителей примитивных типов (таких как int). Это решение вынужденное: его диктуют текущие ограничения обобщённых типов Java, враждебных к примитивным типам. Когда проект Vahalla в конечном итоге представит более мощные обобщённые типы, текущее решение будет выглядеть неудачным и, возможно, его придётся изменить. Мы предполагаем, что такие изменения будут возможны без чрезмерной потери обратной совместимости.