JEP 414: Vector API (Second Incubator)

Аннотация

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

История

Vector API был предложен в JEP 338 и включён в Java 16 как API в статусе Incubator. Здесь мы предлагаем внести улучшения с учётом отзывов, а также улучшения производительности и другие существенные улучшения реализации. В него входят следующие заметные изменения:

• Улучшения API для поддержки операций над символами, например для декодирования символов UTF-8. В частности, мы добавляем методы копирования символов между векторами short и массивами char, а также новые операторы сравнения векторов для беззнакового сравнения целочисленных векторов.

• Улучшения API для преобразования векторов byte в массивы boolean и обратно.

• Intrinsic-поддержка трансцендентных и тригонометрических операций над дорожками (lanewise) на x64 с помощью библиотеки Intel Short Vector Math Library (SVML).

• Общие улучшения производительности реализаций для Intel x64 и ARM NEON.

Цели

• Понятный и лаконичный API — API должен позволять ясно и лаконично выражать широкий спектр векторных вычислений, состоящих из последовательностей векторных операций внутри циклов и, возможно, с управляющими конструкциями. Должна быть возможность выразить вычисление, обобщённое относительно размера вектора, то есть числа дорожек (lanes) в векторе, чтобы такие вычисления были переносимы между оборудованием с разными размерами векторов.

• Независимость от платформы — API не должен зависеть от архитектуры процессора, чтобы его можно было реализовать на разных архитектурах, поддерживающих векторные инструкции. Как обычно для API Java, если оптимизация под платформу и переносимость вступают в конфликт, предпочтение будет отдано переносимости API, даже если из-за этого некоторые платформенно-зависимые идиомы нельзя будет выразить в переносимом коде.

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

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

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

• Улучшение существующего алгоритма автовекторизации в HotSpot не является целью.

• Поддержка векторных инструкций на архитектурах процессоров, отличных от x64 и AArch64, не является целью. Однако важно указать, как сказано в целях, что API не должен исключать такие реализации.

• Поддержка компилятора C1 не является целью.

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

Мотивация

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

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

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

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

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

Описание

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

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

Поддерживаемые формы соответствуют размерам векторов 64, 128, 256 и 512 бит, а также max бит. Форма размером 512 бит может упаковать значения byte в 64 дорожки или значения int в 16 дорожек, и вектор такой формы может обрабатывать 64 значения byte за раз или 16 значений int за раз. Форма в max бит поддерживает максимальный размер вектора текущей архитектуры. Это даёт поддержку платформы ARM SVE, реализации которой могут поддерживать любой фиксированный размер от 128 до 2048 бит с шагом 128 бит.

Мы считаем, что эти простые формы достаточно универсальны, чтобы быть полезными на всех актуальных платформах. Однако по мере экспериментов с будущими платформами, пока этот API находится в статусе Incubator, мы можем и дальше менять устройство параметра формы. Такая работа не входит в начальный объём этого проекта, но эти возможности отчасти определяют нынешнюю роль форм в Vector API. (Подробнее см. раздел о дальнейшей работе ниже.)

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

Операции над векторами делятся на поэлементные (lane-wise) и междорожечные (cross-lane).

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

• Междорожечная (cross-lane) операция применяется ко всему вектору целиком. Результат междорожечной операции — либо скаляр, либо вектор, возможно, другой формы. Междорожечные операции также делятся на операции перестановки и редукции.

Чтобы уменьшить поверхность API, мы определяем коллективные методы для каждого класса операций. Эти методы принимают на вход константы операторов; эти константы являются экземплярами класса VectorOperator.Operator и определены в статических final-полях класса VectorOperators. Для удобства мы определяем отдельные методы, которые можно использовать вместо обобщённых, для некоторых распространённых полносервисных (full-service) операций, таких как сложение и умножение.

Некоторые операции над векторами, например преобразование и переинтерпретация, по своей природе меняют форму (shape-changing), то есть порождают векторы, формы которых отличаются от форм входных векторов. Операции, меняющие форму, в векторном вычислении могут отрицательно сказаться на переносимости и производительности. Поэтому API определяет для каждой операции, меняющей форму, сохраняющий форму (shape-invariant) вариант, если это применимо. Для наилучшей производительности разработчикам следует по возможности писать код, сохраняющий форму, с использованием операций, сохраняющих форму. Операции, меняющие форму, помечены как таковые в спецификации API.

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

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

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

Как и в случае векторов, экземпляры VectorMask<E> являются экземплярами непубличных конкретных подклассов, определённых для каждого сочетания типа элементов и длины. Экземпляр VectorMask<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:

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

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;
    }
}

Сначала мы получаем из FloatVector предпочтительный вид (species), форма которого оптимальна для текущей архитектуры. Мы сохраняем его в поле static final, чтобы компилятор времени выполнения рассматривал значение как константу и поэтому мог лучше оптимизировать векторное вычисление. Затем основной цикл проходит по входным массивам с шагом, равным длине вектора, т. е. длине вида. Он загружает векторы float заданного вида из массивов a и b по соответствующему индексу, в текучем стиле выполняет арифметические операции и затем сохраняет результат в массив c. Если после последней итерации остаются элементы массива, результаты для этих хвостовых элементов вычисляются обычным скалярным циклом.

Эта реализация достигает оптимальной производительности на больших массивах. Компилятор HotSpot C2 генерирует на процессоре 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. В этих горячих участках сгенерированного машинного кода хорошо видно преобразование в векторные регистры и векторные инструкции. Мы отключили развёртку циклов, чтобы преобразование было нагляднее; иначе HotSpot развернул бы этот код с помощью существующих оптимизаций циклов C2. Все выделения памяти под объекты Java устранены.

Компиляция во время выполнения

У Vector API две реализации. Первая реализует операции на Java, поэтому она работоспособна, но не оптимальна. Вторая определяет встроенные (intrinsic) векторные операции для компилятора времени выполнения HotSpot C2, чтобы он мог компилировать векторные вычисления в соответствующие аппаратные регистры и векторные инструкции, когда они доступны.

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

Мы ожидаем, что в конечном счёте векторные классы будут объявлены как primitive classes, как предложено проектом Valhalla в JEP 401 (Primitive Objects). Пока же Vector<E> и его подклассы считаются value-based classes, поэтому следует избегать операций над их экземплярами, зависящих от идентичности. Хотя экземпляры векторов абстрактно состоят из элементов в дорожках (lanes), C2 не разбивает эти элементы на скаляры: значение вектора рассматривается как единое целое, подобно int или long, и отображается на векторный регистр соответствующего размера. C2 обрабатывает экземпляры векторов особым образом, чтобы обойти ограничения анализа выхода (escape analysis) и избежать упаковки (boxing).

Встроенные функции Intel SVML для трансцендентных операций

Vector API поддерживает поэлементные (lanewise) трансцендентные и тригонометрические операции над векторами с плавающей точкой. На x64 мы используем библиотеку Intel Short Vector Math Library (SVML), чтобы предоставить оптимизированные встроенные реализации таких операций. Встроенные операции обладают теми же численными свойствами, что и соответствующие скалярные операции, определённые в java.lang.Math.

Исходные файлы на ассемблере для операций SVML находятся в исходном коде модуля jdk.incubator.vector, в каталогах для конкретных ОС. Процесс сборки JDK компилирует эти исходные файлы для целевой операционной системы в разделяемую библиотеку, предназначенную для SVML. Эта библиотека довольно велика: её размер чуть меньше мегабайта. Если образ JDK, собранный с помощью jlink, не включает модуль jdk.incubator.vector, то библиотека SVML не будет скопирована в образ.

Пока реализация поддерживает только Linux и Windows. Поддержку macOS мы рассмотрим позже, поскольку подготовка исходных файлов на ассемблере с нужными директивами требует немалого объёма работы.

Среда выполнения HotSpot попытается загрузить библиотеку SVML и, если она есть, связать операции из библиотеки SVML с именованными процедурами-заглушками (stub routines). Компилятор C2 генерирует код, вызывающий соответствующую процедуру-заглушку в зависимости от операции и вида вектора (т. е. типа элементов и формы).

Если в будущем проект Panama расширит поддержку нативных соглашений о вызовах на векторные значения, реализация Vector API, возможно, сможет загружать библиотеку SVML из внешнего источника. Если такой подход не повлияет на производительность, то включать SVML в виде исходного кода и собирать её в составе JDK больше не понадобится. До тех пор мы считаем описанный выше подход приемлемым с учётом возможного выигрыша в производительности.

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

• Как упоминалось выше, мы ожидаем, что в конечном счёте векторные классы будут объявлены как primitive classes. Кроме того, мы рассчитываем использовать обобщённую специализацию primitive classes из проекта Valhalla, чтобы экземпляры Vector<E> могли быть примитивными значениями, конкретные типы которых являются примитивными типами. Это упростит оптимизацию и запись векторных вычислений. Подтипы Vector<E> для конкретных типов, например IntVector, могут оказаться ненужными, когда появится обобщённая специализация для primitive classes. Мы намерены развивать API в статусе Incubator на протяжении нескольких выпусков и адаптировать его по мере появления primitive classes и связанных с ними возможностей.

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

  void vectorComputation(float[] a, float[] b, float[] c) {
      for (int i = 0; i < a.length; i += SPECIES.length()) {
          // VectorMask<Float>  m;
          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);
      }
  }

• Мы намерены расширить API, чтобы загружать и сохранять векторы с помощью JEP 412 (Foreign Function & Memory API), когда этот API выйдет из статуса Incubator. Разметки памяти (memory layouts), описывающие виды векторов, могут оказаться полезными, например, для прохода с шагом по сегменту памяти, состоящему из векторных элементов.

• Мы планируем доработать реализацию, чтобы улучшить оптимизацию циклов с векторизованным кодом, поддержать платформу ARM SVE и в целом постепенно повышать производительность со временем.

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

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

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

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

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

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

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

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

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

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