Как выполнить транспонирование матрицы с помощью RVV1.0?

Описание

Я новичок в RVV и переписываю некоторые функции сборки, используя RVV1.0. Теперь я столкнулся с некоторыми проблемами, связанными с транспонированием матрицы. Arm NEON предоставляет инструкции vtrn, помогающие выполнить транспонирование:

# element wide = 8
.macro TRANSPOSE4x4 r0 r1 r2 r3
    vtrn.16         \r0, \r2
    vtrn.16         \r1, \r3
    vtrn.8          \r0, \r1
    vtrn.8          \r2, \r3
.endm

# element wide = 16
.macro TRANSPOSE4x4_16  d0 d1 d2 d3
    vtrn.32     \d0, \d2
    vtrn.32     \d1, \d3
    vtrn.16     \d0, \d1
    vtrn.16     \d2, \d3
.endm

# element wide = 8
.macro TRANSPOSE8x8 r0 r1 r2 r3 r4 r5 r6 r7
    vtrn.32         \r0, \r4
    vtrn.32         \r1, \r5
    vtrn.32         \r2, \r6
    vtrn.32         \r3, \r7
    vtrn.16         \r0, \r2
    vtrn.16         \r1, \r3
    vtrn.16         \r4, \r6
    vtrn.16         \r5, \r7
    vtrn.8          \r0, \r1
    vtrn.8          \r2, \r3
    vtrn.8          \r4, \r5
    vtrn.8          \r6, \r7
.endm

Но в РВВ я не нахожу инструкций типа vtrn, почему в РВВ этого не предусмотрено? Если у меня есть матрица 4*4, каждая строка которой хранится в v1, v2, v3, v4 соответственно и SEW=16, точно так же, как

TRANSPOSE4x4_16

в руке НЕОН, как его транспонировать?

Я пытался использовать некоторые методы в этом блоге, но не получилось. Что касается транспонированной формы, необходимы 4x4 и 8x8, и я хочу знать, повлияет ли SEW на конкретную реализацию?

Некоторый контекст

Я переписываю библиотеку видеокодеков с именем x264, которая имеет функцию сборки с именем sub4x4_dct:

.macro SUMSUB_AB sum, diff, a, b
    vadd.s16    \sum,  \a, \b
    vsub.s16    \diff, \a, \b
.endm

.macro DCT_1D d0 d1 d2 d3  d4 d5 d6 d7
    SUMSUB_AB       \d1, \d6, \d5, \d6
    SUMSUB_AB       \d3, \d7, \d4, \d7
    vadd.s16        \d0, \d3, \d1
    vadd.s16        \d4, \d7, \d7
    vadd.s16        \d5, \d6, \d6
    vsub.s16        \d2, \d3, \d1
    vadd.s16        \d1, \d4, \d6
    vsub.s16        \d3, \d7, \d5
.endm

function sub4x4_dct_neon
    mov             r3, #FENC_STRIDE
    mov             ip, #FDEC_STRIDE
    vld1.32         {d0[]}, [r1,:32], r3
    vld1.32         {d1[]}, [r2,:32], ip
    vld1.32         {d2[]}, [r1,:32], r3
    vsubl.u8        q8,  d0,  d1
    vld1.32         {d3[]}, [r2,:32], ip
    vld1.32         {d4[]}, [r1,:32], r3
    vsubl.u8        q9,  d2,  d3
    vld1.32         {d5[]}, [r2,:32], ip
    vld1.32         {d6[]}, [r1,:32], r3
    vsubl.u8        q10, d4,  d5
    vld1.32         {d7[]}, [r2,:32], ip
    vsubl.u8        q11, d6,  d7

    DCT_1D          d0, d1, d2, d3, d16, d18, d20, d22
    TRANSPOSE4x4_16 d0, d1, d2, d3
    DCT_1D          d4, d5, d6, d7, d0, d1, d2, d3
    vst1.64         {d4-d7}, [r0,:128]
    bx              lr
endfunc

и реализация C:

// dctcoef : int16_t
// pixel: uint8_t
static inline void pixel_sub_wxh( dctcoef *diff, int i_size,
                                  pixel *pix1, int i_pix1, pixel *pix2, int i_pix2 )
{
    for( int y = 0; y < i_size; y++ )
    {
        for( int x = 0; x < i_size; x++ )
            diff[x + y*i_size] = pix1[x] - pix2[x];
        pix1 += i_pix1;
        pix2 += i_pix2;
    }
}

static void sub4x4_dct( dctcoef dct[16], pixel *pix1, pixel *pix2 )
{
    dctcoef d[16];
    dctcoef tmp[16];

    pixel_sub_wxh( d, 4, pix1, FENC_STRIDE, pix2, FDEC_STRIDE );

    for( int i = 0; i < 4; i++ )
    {
        int s03 = d[i*4+0] + d[i*4+3];
        int s12 = d[i*4+1] + d[i*4+2];
        int d03 = d[i*4+0] - d[i*4+3];
        int d12 = d[i*4+1] - d[i*4+2];

        tmp[0*4+i] =   s03 +   s12;
        tmp[1*4+i] = 2*d03 +   d12;
        tmp[2*4+i] =   s03 -   s12;
        tmp[3*4+i] =   d03 - 2*d12;
    }

    for( int i = 0; i < 4; i++ )
    {
        int s03 = tmp[i*4+0] + tmp[i*4+3];
        int s12 = tmp[i*4+1] + tmp[i*4+2];
        int d03 = tmp[i*4+0] - tmp[i*4+3];
        int d12 = tmp[i*4+1] - tmp[i*4+2];

        dct[i*4+0] =   s03 +   s12;
        dct[i*4+1] = 2*d03 +   d12;
        dct[i*4+2] =   s03 -   s12;
        dct[i*4+3] =   d03 - 2*d12;
    }
}

Вот что я реализовал TRANSPOSE4x4_16 с помощью vslide:

    # TRANSPOSE4x4_16 v24, v25, v26, v27
    lui     t1, 11
    addi    t1, t1, -1366
    vsetivli        zero, 4, e16, m1, tu, mu
    vmv.s.x v0, t1
    lui     t1, 5
    addi    t1, t1, 1365
    vmv.s.x v12, t1
    vmv1r.v v15, v24
    vslideup.vi     v15, v25, 1, v0.t
    vmv1r.v v14, v26
    vslideup.vi     v14, v27, 1, v0.t
    vmv1r.v v0, v12
    vslidedown.vi   v25, v24, 1, v0.t
    vslidedown.vi   v27, v26, 1, v0.t
    vmv1r.v v12, v15
    vslideup.vi     v12, v14, 2
    vmv1r.v v13, v25
    vslideup.vi     v13, v27, 2
    vsetivli        zero, 2, e16, m1, tu, ma
    vslidedown.vi   v14, v15, 2
    vslidedown.vi   v27, v25, 2
    vmv1r.v v15, v27
    vmv1r.v v24, v12
    ....
    ....
      
    ret
endfunc

В конце концов я получил неправильный ответ. Я обнаружил, что что-то неправильно понял с регистраторами рук, и исправляю это.

Позже успею нормально ответить, а пока не могли бы вы поделиться, в каком контексте нужно транспонировать матрицы? Я спрашиваю, потому что не уверен, нужно ли это делать в векторных регистрах или по памяти. И какие размеры для вас актуальны? Например. решение 4x4 будет сильно отличаться от NxN. Вам нужно транспонировать одну матрицу или несколько матриц?

camel-cdr 19.04.2024 12:31

Конечно! Я обновлю вопрос, добавив немного предыстории.

Noney 22.04.2024 04:33
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
2
257
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Я реализовал транспонирование матрицы 4x4, используя инструкции vrgather_vv, vslideup_vx и vmerge_vvm. Однако производительность была неудовлетворительной! Похоже, что обмен данными между векторными регистрами обходится довольно дорого.

Ответ принят как подходящий

Поскольку RVV имеет масштабируемую длину вектора, не всегда возможно получить оптимальную производительность с помощью одной реализации, когда алгоритм имеет фиксированное ограничение размера. Это относится к рассматриваемому алгоритму, поскольку очень немногие реализации осуществляют диспетчеризацию на основе VL, и это приведет к тому, что реализация VLEN>=128 будет выполнять ненужную работу.

При транспонировании матрицы NxN вы можете, например, загрузите блок элементов VLx32 и используйте сегментированные хранилища для хранения транспонированной версии этого блока. Это позволит масштабируемо использовать полные векторные регистры во всех реализациях.

Еще один хороший случай — когда вам нужно/можно перенести много меньших, например. 4х4, матрицы сразу. Затем вы можете загрузить каждый n-й элемент матриц VL в n-й векторный регистр и переключить операнд векторного регистра последующих операций.

Приведенный выше подход может работать с вашим кодом sub4x4_dct, но для этого потребуется, чтобы вызов вел себя по-другому, поэтому я не думаю, что его можно использовать для x264.

Я вижу два-три практических варианта для вашего варианта использования:

  1. Использование одного LMUL=4 vrgather.vv для перестановки элементов на места. Его производительность сомнительна, поскольку современные процессоры имеют очень медленную реализацию LMUL=4 vrgather.vv (C908 , C920). Другие процессоры могут не иметь этого недостатка. Это также не совсем вписывается в вашу структуру кода, поскольку вы не можете выделить регистр LMUL=4 с индексами, поэтому вам придется каждый раз загружать их из памяти.

  2. Использование сегментированной загрузки или сохранения в рабочий буфер. Это отлично работает, потому что вы можете просто использовать dctcoef dct[16] в качестве рабочего места. Реализация dav1d AV1 также использует этот подход.

  3. (это было добавлено позже) Использование двукратного застегивания верхней и нижней половины матрицы. Сжатие a и b будет означать создание вектора a0,b0,a1,b1,..., применение этого дважды эквивалентно транспонированию всех матриц 4x4, хранящихся в векторном регистре. zip можно реализовать с помощью инструкций vwmaccu.vx и vwaddu.vv, , как предлагает topperc .

Я протестировал три реализации на C908, и реализация vrgather оказалась в 3 раза медленнее, чем другие подходы, а реализация zip немного быстрее, чем подход с сегментированной загрузкой/сохранением (vsseg: 0.277785 seconds, vrgather.vv 1.545038 seconds, zip 0.249973 seconds).

Вот код для транспонирования матрицы 4x4 из 16-битных элементов:

    vsetivli x0, 8, e16, m1, ta, ma
    vwaddu.vv       v2, v0, v1
    vwmaccu.vx      v2, a2, v1
    vwaddu.vv       v0, v2, v3
    vwmaccu.vx      v0, a2, v3

Обратите внимание, что здесь матрица 4x4 хранится только в двух векторных регистрах. Предполагается, что VLEN равен 128, и это не вписывается в ваш окружающий код, поэтому вам, вероятно, следует использовать другой подход. Он также работает до VLEN=1024, если вы установите соответствующий дробный LMUL и добавите vslide для перемещения двух половин в отдельные регистры.

Вот как можно реализовать макросы TRANSPOSE, используя сегментированную загрузку/сохранение:

.macro TRANSPOSE4x4 buf, bstride, v0, v1, v2, v3
    vssseg4e8.v \v0, (\buf), \bstride
    vle8.v \v0, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v1, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v2, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v3, (\buf)
.endm

.macro TRANSPOSE4x4_16 buf, bstride, v0, v1, v2, v3
    vssseg4e16.v \v0, (\buf), \bstride
    vle16.v \v0, (\buf)
    add \buf, \buf, \bstride
    vle16.v \v1, (\buf)
    add \buf, \buf, \bstride
    vle16.v \v2, (\buf)
    add \buf, \buf, \bstride
    vle16.v \v3, (\buf)
.endm

.macro TRANSPOSE8x8 buf, bstride, v0, v1, v2, v3, v4, v5, v6, v7
    vssseg8e8.v \v0, (\buf), \bstride
    vle8.v \v0, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v1, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v2, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v3, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v4, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v5, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v6, (\buf)
    add \buf, \buf, \bstride
    vle8.v \v7, (\buf)
.endm

Обратите внимание, что bstride должен быть регистром, в котором хранится шаг в байтах, а buf записывается деструктивно. Вы должны иметь возможность использовать для этого a0, но обязательно сделайте резервную копию для последнего магазина.

Вот краткий пример, который я использовал для тестирования реализации:

# asm.S
.global trans2
trans2: # a0 = uint16_t buf[16]
    vsetvli t0, x0, e16, m8, tu, mu
    vid.v v0
    vsetivli t0, 4, e16, m1, tu, mu
    mv t0, a0
    li t1, 8
    TRANSPOSE4x4_16 t0, t1, v0, v1, v2, v3
    mv t0, a0
    TRANSPOSE4x4_16 t0, t1, v0, v1, v2, v3
    ret
// main.c
#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint16_t buf[16] = {0};
    void trans2(uint16_t b[16]);
    trans2(buf);
    for (size_t i = 0; i < 4; ++i) {
        for (size_t j = 0; j < 4; ++j)
            printf("%02x ", buf[j+i*4]);
        puts("");
    }
    puts("");
}

Два транспонирования должны привести к исходному значению, и, как и ожидалось, на машине с VLEN=128 результат будет следующим:

00 01 02 03
08 09 0a 0b
10 11 12 13
18 19 1a 1b

Кстати, последняя строка вашего sub4x4_dct_rvv, вероятно, должна содержать четыре обычных магазина, что отражает четыре загрузки в начале. Я также не уверен, что вы используете правильные векторные регистры в каждом вычислении, они, похоже, не соответствуют выбору кода NEON.

Спасибо большое за подробный ответ и за вашу доброту, это было очень полезно! Я проверю свою реализацию позже. Кстати, знаете ли вы какие-нибудь хорошие примеры RVV, подходящие для новичков? Мне недостаточно одной лишь спецификации, чтобы писать хорошие rvv-коды, думаю, мне нужно больше практики.

Noney 23.04.2024 04:38

У меня есть еще один вопрос. Если у меня есть матрица 4x8, хранящаяся в четырех векторах, с SEW = 16, и я хочу транспонировать левую матрицу 4x4 и правую матрицу 4x4 соответственно. В этом случае хранилище сегментов, похоже, больше не работает, но vtrn по-прежнему работает хорошо, я все еще могу просто использовать тот же макрос TRANSPOSE4x4_16, просто заменив d-вектор на q-вектор. Есть ли элегантный способ решить эту проблему? Почему у RVV нет инструкции vtrn?

Noney 25.04.2024 13:06

Насколько я понимаю, вы можете сделать это с помощью vrgather или через сегментированное хранилище, загрузив его в 8 регистров, vslideup и vmerge, чтобы объединить их обратно в 4 регистра. Причина, по которой в RVV нет инструкции vtrn, заключается в том, что вы не можете определить ее работу независимо от длины вектора. сегментированная загрузка/сохранение близки к этому, но, как вы видели, они не соответствуют вашему варианту использования 1:1. vrgather дает вам полный контроль над перестановками, но из-за этого может работать медленно, особенно при пересечении полос движения.

camel-cdr 25.04.2024 18:05

Когда вы говорите: «Вы не можете определить, чтобы он работал независимо от длины вектора», что вы имеете в виду? В моем аспекте его можно спроектировать так же, как vle8.v/ vle16.v/..., например trn8.vv/ vtrn16.vv/..., количество затрагиваемых элементов можно гибко контролировать в соответствии с различными vl, установленными инструкция setvli. Почему эта операция должна работать независимо от длины вектора?

Noney 26.04.2024 04:16

Но как это будет работать? У вас всего 32 векторных регистра, но n элементов, или вы имеете в виду транспонирование n матриц 4x4 в 4 векторных регистра? Это кажется очень специализированной операцией, хотя vrgather уже позволяет вам это сделать. Я не думаю, что реализация, реализующая такую ​​скорость, будет намного дешевле, чем реализация, в которой есть быстрая полоса движения, пересекающая vrgather.vv.

camel-cdr 26.04.2024 23:02

В процессе портирования x264 я столкнулся со многими инструкциями vtrn и не знаю, как элегантно реализовать их с помощью RVV. Операция vslide обычно подходит для случаев, когда vl относительно невелика; чаще мне нужно использовать хранилище сегментов, но это должно оценивать буфер. И если vrgather сможет решить проблемы с производительностью оборудования в будущем, как мне использовать его для замены инструкции vtrn? Где мне следует разместить свой индекс? Я подумываю о сохранении его в памяти, но означает ли это, что мне нужно извлекать индекс из памяти каждый раз, когда я вызываю vrgather? Не будет ли это слишком дорого?

Noney 28.04.2024 10:27

Не могли бы вы предоставить мне рукописный пример сборки того, как использовать инструкцию vrgather для реализации транспонирования матрицы 4x4, если это возможно? Я хотел бы знать, как настраиваются индексы.

Noney 28.04.2024 10:35

Вот, это транспонирует все матрицы 4x4 в 4 векторных регистра для любого VLEN: godbolt.org/z/a97eqad91 Я написал это с помощью встроенных функций, но полученная сборка по сути является тем, что вы бы написали вручную. Идея состоит в том, чтобы установить индекс для сбора вектора N равным (i&3)*vl+(i&~3u)+N, где i — индекс элемента, полученный с помощью vid.v. Для создания вектора LMUL=4 с индексами требуется 8 инструкций LMUL=1, но вы все равно захотите поместить его за пределы горячего цикла.

camel-cdr 28.04.2024 22:12

Извините, я увидел только ваш последний комментарий и пропустил тот, что выше. Посмотрите, как x86 выполняет транспозицию, насколько я могу судить, для этого также требуется несколько инструкций. Если вы не можете вывести создание индекса за пределы цикла, я бы оставил все как есть. Это должно быть запланировано довольно хорошо. Я ожидаю, что 8 инструкций LMUL=1 займут примерно то же количество циклов, что и vrgather LMUL=4 в хорошей реализации. Кстати, глядя на модель расписания llvm SiFive P670 и XiangShan, мы указываем на тех, у кого есть хорошие реализации vrgather, и мы должны это увидеть.

camel-cdr 29.04.2024 12:00

Это здорово, спасибо! Я проведу дополнительные исследования.

Noney 30.04.2024 04:29

Извините за беспокойство, я столкнулся с другой проблемой. Мне нужно транспонировать матрицу 4x16 с элементами шириной 16 бит. Я считаю, что использование vrgather - хороший выбор, поэтому я предпринял следующую попытку: ``` всетивли ноль, 16, е8, m1, ta, ma vid.v v16 vand.vi v17, v16, 3 vmul.vx v17, v17 , t0 ванд.vi v16, v16, -4 vadd.vv v20, v17, v16 vadd.vi v21, v20, 1 vadd.vi v22, v20, 2 vadd.vi v23, v20, 3 всетвли ноль, ноль, е16, m4, ta, ma vrgather.vv v16, v4, v20 vmv.v.v v4, v16 '''

Noney 27.05.2024 04:22

Но, похоже, не работает. Четыре строки матрицы хранятся в v4, v5, v6, v7. Я думаю, что этот индекс всегда меньше 255, поэтому я использую vrgather.vv. Но результат vrgather.vv v16, v4, v20 устанавливает v4 и v5 в ноль, почему дошло до этого?

Noney 27.05.2024 04:30

@Noney Вы проверяли, что длина вашего вектора >=256, поскольку 16*16=256? Я подозреваю, что это проблема с вашим кодом. Кстати, разве транспонирование матрицы 4x16 не будет работать с сегментированной загрузкой/сохранением?

camel-cdr 30.05.2024 22:45

Ах да, длина моего вектора равна 128, и моя цель — поддерживать длину вектора >= 128. Меня смущает, зачем мне нужна длина вектора >= 128? Причина, по которой я предпочитаю использовать vrgather вместо сегментированной загрузки/сохранения, заключается в том, что аргументы этой функции не предоставляют подходящее буферное пространство, и мне приходится вручную защищать данные в этом пространстве от уничтожения операцией транспонирования. Думаю, это приведет к дополнительным затратам. Как вы говорите, vrgather, возможно, будет хорошо работать в будущем, поэтому я стараюсь использовать vrgather.

Noney 03.06.2024 04:50

О, я знаю, зачем мне длина вектора >= 256. Я проверю, спасибо!

Noney 03.06.2024 05:07

Теперь я могу получить правильные результаты с помощью vrgather, но у меня также есть проблемы с производительностью. Другая причина, по которой я не хочу использовать сегментированную загрузку/сохранение, заключается в том, что когда форма матрицы равна 4x16, я думаю, что мне нужно 16 векторов для хранения временных данных, загруженных из буфера, и объединения их с помощью vslides, это очень раздражает. И есть также некоторые проблемы в vrgather, когда форма матрицы становится большой, например, 8x16, возможно, мне нужно 3 группы регистров LMUL=8 для выполнения перестановки, но в реальных приложениях всегда недостаточно подходящих групп регистров LMUL=8, ожидающих для меня.

Noney 03.06.2024 09:17

@Noney Я добавил к ответу еще один подход, который быстрее, чем другой на C908. Однако он работает только при VLEN=128 для случая 16-битного элемента 4x4 и плохо интегрируется с окружающим кодом, поэтому вы, вероятно, не сможете его использовать, хотя он все равно должен быть интересным. Для большего VLEN вам придется использовать дробный LMUL.

camel-cdr 28.06.2024 19:56

Спасибо, я рад видеть другой подход. Хотя он работает только с VLEN = 128, он все равно стоит дорого, потому что мы можем выполнять некоторые рукописные ассемблерные задания на некоторых конкретных VLEN, чтобы добиться максимальной производительности, как вы говорите: «RVV имеет масштабируемую длину вектора, это не всегда возможно». чтобы получить оптимальную производительность с помощью одной реализации». Кстати, подойдет ли это к другим формам? Например, 8x8 или 8x16.

Noney 29.06.2024 07:24

@Noney, с дополнительным почтовым индексом вы должны получить транспонирование матрицы 8x8. 8x16 не работает напрямую, но если рассматривать его как две матрицы 8x8, то можно транспонировать обе сразу. Это могло бы быть промежуточным шагом транспонирования матрицы 8х16, но я еще не продумал это.

camel-cdr 29.06.2024 09:06

Да, это становится сложным и трудным для понимания. Я по-прежнему предпочитаю использовать такие инструкции, как trn1 и trn2 из aacrh64. В моем недавнем анализе горячих точек x264 я обнаружил, что некоторые из самых горячих функций в x264 (satd) интенсивно используют trn1 и trn2. Я не уверен, есть ли в алгоритме улучшения, которые позволят riscv добиться такой же высокой производительности без использования аналогичных инструкций. В противном случае riscv однозначно будет отставать от aarch64 по части кодирования.

Noney 01.07.2024 08:34

Другие вопросы по теме