Недавняя публикация о векторном расширении RISC-V архитектуры, подтолкнула меня к мысли написать небольшую заметку об использовании данного расширения в задаче, имеющей практическое применение. После появления векторного расширения, в сети начали публиковаться статьи о применении RISC-V ядер с данным расширением в задачах, ранее в которых безальтернативно использовались только процессоры ЦОС. В данной статье рассматривается тест, в котором используется алгоритм декодирования Витерби - задача, требующая значительных вычислительных ресурсов. Исходный код теста Вы можете скачать по ссылке. Для выполнения теста я использую RISC-V ядро поддерживающее систему команд RV32GCBV. В качестве отладочного инструмента использую среду отладки от Syntacore.
Структура теста.
В качестве входных данных используется массив констант input_message[], который содержит два сообщения, каждое длиной 240 бит. Известно, что данные закодированы свёрточным кодом с параметрами К=7, rate=1/2. Каждый информационный бит сообщения кодируется 2-мя передаваемыми битами, а количество состояний кодера равно 64. Кроме того, биты сообщения перетасованы. Декодирование выполняется с помощью алгоритма Витерби.
Принятые 240 бит переставляются определенным образом (дескрэмблируются), и полученная последовательность бит пропускается через декодер. В данном тесте мы имеем дело с вариантом декодирования Витерби, которое в литературе называется «hard decision». Декодирование включает в себя фазы инициализации декодера, обработку сообщения на решетке состояний, вычисление результирующих значений.После получения двух сообщений по 120 бит, они склеиваются в одно общее, для которого вычисляется контрольная сумма. В случае совпадения контрольной суммы с принятой в сообщении, тест печатает число 5 как признак успешного выполнения. Попутно, для каждого из сообщений вычисляется количество тактов, затраченное на полную обработку и на самую трудоемкую функцию - v27_update_*().
Причём для второго сообщения количество тактов немного больше за счет дополнительного подсчета контрольной суммы, поэтому далее я буду приводить цифры тактов для декодирования второго сообщения c вычислением CRC.
Си версия кода.
В целом, код теста основывается на функциях декодера, приведенных в этом проекте. Вместе с тем, в исходный код были внесены некоторые изменения, оптимальные для рассматриваемого случая. После компиляции проекта с уровнем оптимизации –О2 и прогона теста на процессорном ядре, была получена цифра в 84 172(78 760) тактов для второго сообщения. Напомню, что цифра 78 760 относится к затратам на самую трудоемкую функцию декодирования v27_update_С(), а 84 172 включает в себя дополнительное обслуживание декодера.
Использование ассемблера.
Используемое RISC-V ядро представляет собой суперскаляр с возможностью исполнения до 2-х инструкций за один такт. В данном случае может иметь место вопрос: «насколько оптимально компилятор генерирует код для используемого ядра?». Я решил реализовать на ассемблере самую трудоемкую часть декодирования - функцию v27_update_С(), которая использует макрос BFLY для 32-х бабочек декодера. Как следует из ранее полученных результатов, эта функция занимает 94% времени обработки. В основе функции макрос
#define BFLY(i) {\
unsigned int metric,m0,m1,decision;\
metric = (v->poly->c0[i] ^ sym0) +
(v->poly->c1[i] ^ sym1);\
m0 = v->old_metrics[i] + metric;\
m1 = v->old_metrics[i+32] + (PK*2 - metric);\
decision = (signed int)(m0-m1) > 0;\
v->new_metrics[2*i] = decision ? m1 : m0;\
wl |= decision << i;\
m0 -= (metric+metric-PK*2);\
m1 += (metric+metric-PK*2);\
decision = (signed int)(m0-m1) > 0;\
v->new_metrics[2*i+1] = decision ? m1 : m0;\
wh |= decision << i;\
}
Предполагая, что с помощью ассемблера не получится сильно ускориться, я решил сэкономить хотя бы размер кода и реализовал алгоритм с помощью кода одной бабочки, циклически исполняемого 32 раза. При этом цикл получился такой, что практически каждый такт процессор исполняет 2 команды. Бабочка на ассемблере в функции v27_update_sasm():
Немного ассемблерного кода
.align 3 // align next code to 8 bytes
rep_btf_i:
xor s0,s0,a2 # (v->poly->c1[i] ^ sym1)
xor t1,a4,t1 # (v->poly->c0[i] ^ sym0)
add t1,t1,s0 # metric
addi s5,s5,-1 # can be delete!!!
add t4,t1,-510 # -(510-metric)
addi a7,a7,1 # v->poly->c_[i] next state
add s9,t3,t1 # m0 = v->old_metrics[i] + metric;
sub s8,t2,t4 # m1 = v->old_metrics[i+32] +
(510 - metric);
sub t3,t3,t4 # m0 += (510-metric);
slt s2,s8,s9 # decision = (signed int)(m0-m1) > 0;
add t1,t1,t2 # m1 += metric;
sll s2,s2,s3 # decision << ((2*i)&31) 0,2,4,,
lbu s0,32(a7) # v->poly->c1[i]
or s6,s6,s2 # d->w[0] |= decision << ((2*i)&31);
min s1,s8,s9 # metrics[2*i] = decision ? m1 : m0;
sw s1,0(a3) # metrics[2*i] = decision ? m1 : m0;
slt t2,t1,t3 # decision = (signed int)(m0-m1) > 0;
min t3,t1,t3 # metrics[2*i+1] = decision ? m1 : m0;
lbu t1,0(a7) # v->poly->c0[i]
addi a6,a6,4 # v->old_metrics[i]
sw t3,4(a3) # metrics[2*i+1] = decision ? m1 : m0;
sll t3,t2,s3 # << (2*i+1) 1,3,5,
lw t2,128(a6) # m1 = v->old_metrics[i+32]
or s7,s7,t3 # d->w[0] |= decision << ((2*i+1)&31);
lw t3,0(a6) # m0 = v->old_metrics[i]
addi a3,a3,8 # v->new_metrics[2*i]
addi s3,s3,1
bnez s5,rep_btf_i
Экономия кода, по сравнению с исходным вариантом функции v27_update_С(), около 3 Кбайт. Полученное число тактов на ассемблерной версии составило 66 633 (61 243). Удалось ускорить алгоритм на 20% за счет оптимального для данного процессорного ядра расположения команд, а также за счет использования команды MIN из В-расширения. В Си версии компилятор не догадался использовать команду минимума.
Векторное расширение RISC-V.
Суперскалярное RISC-V ядро имеет 9 стадий конвейера. Векторный сопроцессор встроен в конвейер процессора таким образом, что добавляет к скалярному конвейеру еще 5 стадий. При этом векторная команда считается выполненной, с точки зрения скалярного процессора, когда она передается с 9-й стадии конвейера на 10-ю. Это позволяет скалярной части процессора исполнять следующий код, в то время пока векторный ускоритель исполняет векторную команду. Данный векторный сопроцессор можно назвать минимальным (учебным). Он использует 32 векторных регистра длиной 128 бит. Тракт обработки имеет ширину 64 бита. Шина данных для обмена с памятью 64 разряда. Ускоритель может исполнять в одном такте только одну команду. Векторные команды загрузки и сохранения используют те же стадии конвейера, что и скалярные команды загрузки-сохранения. Для них совмещение операций со скалярными командами невозможно. При длине векторного регистра 128 бит и тракте обработки в 64 бита, команда, использующая всю длину векторного регистра, будет исполняться за 2 такта. Тем не менее, на данном ускорителе возможно совмещение выполнения векторных команд. Например, векторная арифметическая команда может исполняться одновременно со следующей за ней векторной командой загрузки или сохранения.
Алгоритм декодирования с помощью векторного расширения реализован в функции v27_update_vasm(). Цикл обработки одной пары бит принятого сообщения приведен ниже:
Ещё немного ассемблерного кода
.balign 8
rep_i:
lbu a4,0(a1) # sym0 = *syms++;
lbu a2,1(a1) # sym1 = *syms++;
addi a1,a1,2
vsetvli x0, s5, e8,m2
vxor.vx v6,v2,a4
vxor.vx v8,v4,a2
vadd.vv v10,v6,v8 # metrics
vadd.vx v8,v10,t6 # metrics -(PK-metric)
vwadd.wv v24,v16,v10 # m0
vwsub.wv v28,v20,v8 # m1
vwsub.wv v16,v16,v8 # m0 -= -(PK - metric);
vwadd.wv v20,v20,v10 # m1 += metric;
vsetvli x0, s5, e16,m4
vmslt.vv v0,v28,v24 # decision = (signed int)(m0-m1) > 0;
vmin.vv v28,v28,v24 # new_metrics[2*i]=decision ? m1 : m0;
vmslt.vv v1,v20,v16 # decision = (signed int)(m0-m1) > 0;
vmin.vv v24,v20,v16 # metrics[2*i+1] = decision ? m1 : m0;
# new metrics with mixed words
# VLEN >= 128 bits
li t2,16
vsetvli x0, t2, e16,m4
vslidedown.vx v8, v28, t2
vslidedown.vx v12, v24, t2
vsetvli x0, t2, e32, m4 # 16 SEW32
vzext.vf2 v20, v8
vzext.vf2 v16, v28
li t0,0x8000
vsetvli x0, t2, e16, m2 # 16 SEW16
vwmaccus.vx v16, t0, v24
vwmaccus.vx v16, t0, v24
vwmaccus.vx v20, t0, v12
vwmaccus.vx v20, t0, v12
# end mix
vmv.x.s t0, v28
vsetivli x0, 1, e32,m1
vse32.v v0,(a5)
addi a5,a5,4
vse32.v v1,(a5)
addi a5,a5,4
beq a1,t5,loop_exit # while(nbits--)
slli t0,t0,16
lui t1,0x40000
bge t1,t0,rep_i
Несмотря на минималистский характер ускорителя, 32-х регистров по 128 разряда оказалось достаточно чтобы разместить данные внутри регистрового файла и не выполнять их загрузку и сохранение на каждой стадии. Также в векторных регистрах хранятся и константы полиномов. Очень полезными оказались команды сложения и вычитания, использующие разный размер операндов. Очень неожиданной проблемой, с которой я столкнулся, оказалась реализация смешивания двух полученных векторов вычисленных метрик. Каких только вариантов я не перепробовал в поиске более быстрой реализации для данного ускорителя. В итоге остановился на приведенном в тексте проекта смешивании через умножение с накоплением. Приветствуется подсказка более быстрого решения.
С помощью векторной ассемблерной реализации v27_update_vasm() тест исполнился за 20 612 (15 072) тактов (2-е сообщение). Ускорение в 3.2 раза по сравнению со скалярным ассемблерным вариантом. Здесь стоит отметить один не совсем честный прием, которым я воспользовался, дабы получить более быстрые цифры. В исходной варианте для хранения метрик использовались 32-разрядные числа. Если остановиться на таком подходе и сделать аналогичную векторную реализацию, то на данном ускорителе результат будет быстрее не более чем в 2 раза. Поэтому, опробовав данный случай, для окончательного теста я выбрал вариант, когда для векторной реализации используются метрики разрядностью 16 бит. Для скалярной реализации такой выбор не дает преимуществ в производительности, а вот для векторной ускорение лучше. Можно обратить внимание, что с ускорением процесса декодирования возрастает вес окружающих вспомогательных функций. Если изначально они занимали 6 % от общего времени выполнения, то с векторным расширением уже 27%. И если реально функция декодирования ускорилась в 4 раза, то общий алгоритм только в 3.2.
В векторной реализации я старался использовать такие решения, чтобы они не зависели от длины векторного регистра (требование VLEN>= 128 ). Это немного увеличило время декодирования. Так, если предполагать, что длина векторного регистра всегда будет равна 128 бит, то можно улучшить алгоритм смешивания.
# VLEN = 128 bits only!!!
vsetvli x0, s5, e32, m8 # 32 SEW32
vzext.vf2 v16, v28
li t0,0x8000
vsetvli x0, s5, e16, m4 # 32 SEW16
vwmaccus.vx v16, t0, v24
vwmaccus.vx v16, t0, v24
В данном случае используется тот факт, что вторая половина вектора точно находится в регистре v20. С таким вариантом цифры тактов уже 19 571 (13 869).
Итоги.
Из полученных результатов можно сделать вывод о хорошем эффекте от использования векторного расширения для выбранной задачи. С использованием векторного расширения для данного ядра получено 13869/120 => 116 /32 = 3.625 такта на бабочку.
RV32GCB | RV32GCB(+asm) | RV32GCBV | |
|---|---|---|---|
Viterbi | 78 760 | 61 243 | 13 869 |
Viterbi+service | 84 172 | 66 633 | 19 571 |
Надеюсь, у меня получился интересный тест для процессора архитектуры RISC-V и любой желающий может попробовать его на своем RISC-V ядре и получить удовольствие от более быстрых цифр. При этом Си вариант теста доступен для ядра любой архитектуры.