[sasamy 1]

On 11/8/2023 at 12:22 PM, sasamy said:

надо будет потом попробовать свой собрать в буилдрут  может ещё быстрей будет

наоборот медленней на  ~1-2 кадра, но собирал gcc 12

собрал gcc 10.4 в buildroot и он оказался быстрей чем армовская сборка но незначительно в пределах погрешности измерений/округлений

arm-buildroot-linux-musleabihf-gcc.br_real (Buildroot 2022.08.1) 10.4.0

Quote

bsize: 5952, fsize: 4784
Encode: 33 FPS   Decode: 15 FPS
Encode: 33 FPS   Decode: 15 FPS
Encode: 33 FPS   Decode: 15 FPS

  

получается Linux примерно на 25% быстрей работает

(33−26)÷26×100=26,92
(15−12)÷12×100=25

Изменено 9 ноября, 2023 пользователем sasamy

[repstosw 18]

On 11/8/2023 at 6:38 PM, sasamy said:

на Linux быстрей работает

Мне удалось сделать 14,96 FPS декодирование и 39 FPS кодирование.

Процедура остатка от деления - вместо константы NN,  добавил переменную, в которой присвоено значение NN.   Хитрость в том, что вместо двух инструкций вычитания IMMEDIATE,  делается одна инструкция вычитания регистра.  И местами цикл будет длинным - 2/3 итерации.

unsigned int nn=NN;

static inline unsigned int modnn2(unsigned int x)
{
 while(x>=nn)
 {
  x-=nn;
  x=(x>>MM)+(x&nn);
 }
 return x;
}

static inline unsigned int gf_sub(unsigned int x,unsigned int y)
{
 y=x-y;
 return y+(y>x)*NN; 
}

#define gf_add(x,y) gf_sub(x,NN-(y))

В кодировании выбросил проверку элементов полинома Gg[ i ] на значение A0.  Но с этим надо быть аккуратнее - вначале проверить. Потому что я заменил полином на другой, который как раз позволил выкинуть эту проверку.

#elif(MM == 16)
  int Pp[MM+1] = { 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1 }; //the best of speed

void encode_rs(dtype *data)
{
 dtype *bb=&data[K];

 CLEAR(bb,EE);

 for(int i=K-1;i>=0;i--)
 {
  gf feedback=data[i]^bb[EE-1];

  if(feedback) /* feedback term is non-zero */
  {
   feedback=Index_of[feedback];
   for(int j=EE-1;j>0;j--)bb[j]=bb[j-1]^Alpha_to[gf_add(Gg[j],feedback)]; //здесь Gg[j] никогда не будет A0 - проверил
                          bb[0]=        Alpha_to[gf_add(Gg[0],feedback)];
  }
  else /* feedback term is zero. encoder becomes a single-byte shifter */
  {
   for(int j=EE-1;j>0;j--)bb[j]=bb[j-1];
                          bb[0]=0;
  }
 }
}

 

Но это всё мелочи.   Виноград и Китайская теорема об остатках - способны ускорить этот алгоритм.  Но придётся курить матан, так как имплементации на Си не нашёл.

65535 - это 3*5*17*257.  Можно применить 4-х этапное преобразование Винограда,  свернув большой  цикл (0..65535) в четыре мелких (3, 5 , 17, 257)

Изменено 9 ноября, 2023 пользователем repstosw

[sasamy 1]

On 11/9/2023 at 5:27 PM, repstosw said:

Мне удалось сделать 14,96 FPS декодирование и 39 FPS кодирование.

за точность цифр что получились у меня не могу поручиться - эти счётчики зависят от реализации, так что они примерные

On 11/9/2023 at 5:27 PM, repstosw said:

Но это всё мелочи.   Виноград и Китайская теорема об остатках - способны ускорить этот алгоритм. 

а почему не подходит GF(2^^12) ? мне кажется он в разы быстрей будет, надо только битовый  буфер раскидать на слова с 12 значащами битами - сдвигами можно очень быстро раскидывать 3 байта на 2 слова по 12 бит, а потом обратно сериализовать уже с добавленными избыточными символами для передачи, приём тоже самое раскидать принятый буфер на слова, восстановить и снова в битовый буфер сериализовать.

Изменено 9 ноября, 2023 пользователем sasamy

[repstosw 18]

18 hours ago, sasamy said:

а почему не подходит GF(2^^12) ? мне кажется он в разы быстрей будет, надо только битовый  буфер раскидать на слова с 12 значащами битами - сдвигами можно очень быстро раскидывать 3 байта на 2 слова по 12 бит, а потом обратно сериализовать уже с добавленными избыточными символами для передачи, приём тоже самое раскидать принятый буфер на слова, восстановить и снова в битовый буфер сериализовать.

Потому что с GF(2^12) производительность декодера ещё меньше - 12 FPS.

Исходные данные:  весь пакет максимально 5952 байт. Из них 1168 байт максимально на проверку ошибок.

Для GF(2^16) это укороченый RS код (2976,2392) символа (16 бит,  2 байта на 1 символ).

Для GF(2^12) этим условиям соответствует укороченный RS код  (3968,3190) символа (12 бит, 3 байта на 2 символа).

Скорость кодирования немного выросла (40+ FPS), но вот декодирование упало (до 12 FPS).

Основная проблема - промахи кеша данных при хаотичных обращениях к таблицам Alpha_to и Index_of, которые нужны для расчёта арифметики Галуа: первая таблица возводит в степень, вторая - логарифмирует.

Их использование ускоряет вычисления в GF: сложение, вычитание, умножение, возведение в степень.

 

20 hours ago, repstosw said:

Можно применить 4-х этапное преобразование Винограда,  свернув большой  цикл (0..65535) в четыре мелких (3, 5 , 17, 257)

Удалось раскурить этот матан для поля GF(2^4) - сделал программную имплементацию 3-точечного преобразования: цикл нахождения синдромов длиной 15 итераций сжался до длины 5 итераций.    Нахождение синдромов ошибок - самая ресурсоёмкая часть в декодере RS.

Результаты сравниваю  с результатами расчётов, выполеннных по старому методу.

По вот этой статье делал:  https://ipnpr.jpl.nasa.gov/progress_report/42-43/43Q.PDF

 

На русском языке более-менее понятную статью про свёрточное преобразование нашел здесь: https://habr.com/ru/articles/477718/

Но она не применима к моим задачам, но дала понять общий принцип.

 

Изменено 10 ноября, 2023 пользователем repstosw

[sasamy 1]

On 11/10/2023 at 2:01 PM, repstosw said:

Основная проблема - промахи кеша данных при хаотичных обращениях к таблицам Alpha_to и Index_of, которые нужны для расчёта арифметики Галуа: первая таблица возводит в степень, вторая - логарифмирует.

Для MM = 16 эти таблицы содержат 65536 элементов, для MM = 12 количество элементов 4096

Quote

#define MM  16  /* RS code over GF(2**MM) - change to suit */

#define NN ((1 << MM) - 1)
* index->polynomial form conversion table */
gf Alpha_to[NN + 1] __attribute__ ((aligned (64)));

/* Polynomial->index form conversion table */
gf Index_of[NN + 1] __attribute__ ((aligned (64)));

мне казалось что это должно ускорить доступ а у вас он парадоксально замедлился 🙂

On 11/10/2023 at 2:01 PM, repstosw said:

Потому что с GF(2^12) производительность декодера ещё меньше - 12 FPS.

Исходные данные:  весь пакет максимально 5952 байт. Из них 1168 байт максимально на проверку ошибок.

Для GF(2^16) это укороченый RS код (2976,2392) символа (16 бит,  2 байта на 1 символ).

Для GF(2^12) этим условиям соответствует укороченный RS код  (3968,3190) символа (12 бит, 3 байта на 2 символа).

 

[repstosw 18]

1 hour ago, sasamy said:

Для MM = 16 эти таблицы содержат 65536 элементов, для MM = 12 количество элементов 4096

мне казалось что это должно ускорить доступ а у вас он парадоксально замедлился 🙂

Потому что увеличилось число проверочных символов. А цикла там два - вложенные: один по K+E, второй по E.

В итоге сложность вычислений выросла квадратично.  И во столько же раз - количество обращений к таблицам.

На таблицах там реальный прирост скорости, когда GF(2^8) и меньше (элемент таблиц - 1 байт).

 

Попробовал разогнать DDR, с дефолтных 792 МГц до 1008 МГц.   Ощутимого выигрыша не даёт - скорость декодирования увеличилась всего на +1 FPS.  Очевидно, включенный кеш данных и частота ядра значат больше, чем частота DDR.

 

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

Изменено 10 ноября, 2023 пользователем repstosw

[repstosw 18]

On 11/10/2023 at 11:12 PM, repstosw said:

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

Перешёл тренироваться в поле GF(2^8).  Освоил трёх-ступенчатое преобразование, которое по сравнению с 2-х ступенчатым дало выигрыш ещё больше.

Статья, как быстро считать синдромы, применяя много-ступенчатое преобразование: https://ipnpr.jpl.nasa.gov/progress_report2/42-52/52J.PDF

 

Отладил алгоритм на ПК,  затем перенёс на T113-s3. Ниже результаты, причём без оптимизации кода, изменён только алгоритм. FPS справедлив для одного блока 255 символов (GF 2^8 )

 

Результаты 2-ступенчатого преобразования (255 = 3 * 85 ) - выигрыш в скорости нахождения синдромов 1,6x :

Classic: 1040.4 FPS   Winograd: 1604.7 FPS   
Classic: 1041.1 FPS   Winograd: 1604.7 FPS   
Classic: 1039.3 FPS   Winograd: 1604.7 FPS   
Classic: 1040.4 FPS   Winograd: 1604.3 FPS   
Classic: 1039.7 FPS   Winograd: 1605.1 FPS   
Classic: 1037.9 FPS   Winograd: 1604.7 FPS   
Classic: 1042.6 FPS   Winograd: 1605.6 FPS   
Classic: 1040.8 FPS   Winograd: 1606.9 FPS   
Classic: 1041.1 FPS   Winograd: 1606.0 FPS   
Classic: 1043.1 FPS   Winograd: 1604.3 FPS   

 

Результаты 3-ступенчатого преобразования (максимальное разложение для 255 = 3 * 5 *17 ) - выигрыш  в скорости 5.6x :

Classic: 1037.9 FPS   Winograd: 5848.0 FPS   
Classic: 1039.1 FPS   Winograd: 5859.4 FPS   
Classic: 1039.1 FPS   Winograd: 5842.3 FPS   
Classic: 1039.3 FPS   Winograd: 5876.6 FPS   
Classic: 1037.9 FPS   Winograd: 5865.1 FPS   
Classic: 1040.0 FPS   Winograd: 5859.4 FPS   
Classic: 1039.5 FPS   Winograd: 5842.3 FPS   
Classic: 1038.2 FPS   Winograd: 5836.6 FPS   
Classic: 1040.0 FPS   Winograd: 5853.7 FPS   
Classic: 1039.7 FPS   Winograd: 5825.2 FPS   

 

Осталось теперь перейти в GF(2^16) и сделать 4-ступенчатое разложение:  2^16-1 = 65535 = 3 * 5 * 17 * 257

Изменено 11 ноября, 2023 пользователем repstosw

[repstosw 18]

Завершил оптимизацию кодека.

 

Что было:

Кодирование: 20.8 FPS

Декодирование(исправление максимального числа ошибок): 11.8 FPS

Поиск синдромов(декодирование при отсутствии ошибок): 19.1 FPS

Поиск Ченя: 59.4 FPS

 

Что стало:

Кодирование: 37.1 FPS

Поиск синдромов(без разложения):            25.0 FPS => Декодирование: 14.7 FPS
Поиск синдромов(4-ступенчатое разложение): 258.5 FPS => Декодирование: 31.6 FPS

Поиск Ченя: 67.8 FPS

 

Декодирование ускорено в 2.6 раз, кодирование - в 1.8 раз.

 

https://github.com/rep-stosw/reed-solomon

[sasamy 1]

On 11/15/2023 at 9:36 AM, repstosw said:

Кодирование: 37.1 FPS
Декодирование: 31.6 FPS

https://github.com/rep-stosw/reed-solomon

Quote

Compilation flags: -Ofast -marm -mcpu=cortex-a7 -mfloat-abi=hard -mfpu=vfpv4 -mfpu=neon -ftree-vectorize -fno-math-errno -ffunction-sections -fdata-sections

ещё с прошлого раза заметил что используете режим arm вместо штатного для armv7 thumb - с чем связано ? по-моим наблюдениям это причина тормозов, попробовал на Linux в режиме arm и показания сравнялись с вашими

-O3 -marm

Quote

RS GF(2^12)...
Encode: 37 FPS   Decode: 30 FPS
Encode: 37 FPS   Decode: 30 FPS
Encode: 37 FPS   Decode: 30 FPS

 

thumb используется по умолчанию если ничего не указвыать, или явно указать

-O3 -mthumb

Quote

RS GF(2^12)...
Encode: 45 FPS   Decode: 33 FPS
Encode: 45 FPS   Decode: 33 FPS
Encode: 45 FPS   Decode: 33 FPS

 

[mantech 48]

9 минут назад, sasamy сказал:

используете режим arm вместо штатного для armv7 thumb

Интересная мысль, всегда думал, что примерно одно и тоже, а тут вот оно как у вас получилось...

[repstosw 18]

33 minutes ago, sasamy said:

ещё с прошлого раза заметил что используете режим arm вместо штатного для armv7 thumb - с чем связано ?

Так сложилось исторически, когда только начинал осваивать Allwinner и GCC для него. С тех пор опции командной строки копипастились и изменялись по мере необходимости.

 

33 minutes ago, sasamy said:

thumb используется по умолчанию если ничего не указвыать, или явно указать -O3 -mthumb

Quote

RS GF(2^12)...
Encode: 45 FPS   Decode: 33 FPS

Спасибо!  Заменил на -mthumb, результат очень порадовал:

Encode: 45.8 FPS   Decode: 34.4 FPS
Encode: 45.9 FPS   Decode: 34.4 FPS
Encode: 45.9 FPS   Decode: 34.4 FPS
Encode: 45.8 FPS   Decode: 34.3 FPS

GCC v. 10.3

Используемые флаги:

CFLAGS=-DNDEBUG -Ofast -mthumb -mcpu=cortex-a7 -mfloat-abi=hard -mfpu=vfpv4 -mfpu=neon \ 
       -ftree-vectorize -fno-math-errno -fmax-errors=1 -ffunction-sections -fdata-sections

ASMFLAGS=-mcpu=cortex-a7 -mfloat-abi=hard -mfpu=vfpv4 -mfpu=neon

LINKFLAGS=-Wl,--gc-sections -Wl,--static -Wl,--strip-all -nostdlib -nostdinc -nostartfiles \
          -ffreestanding -specs=nosys.specs -specs=nano.specs -u_printf_float

 

Изменено 15 ноября, 2023 пользователем repstosw

[sasamy 1]

On 11/15/2023 at 1:42 PM, mantech said:

всегда думал, что примерно одно и тоже

теоретически arm быстрей должен работать а на практике промахи кеша инструкций в режиме arm намного сильней влияют и на практике все дистрибутивы Linux для armv7a по умолчнию используют thumb как и сборки gcc с сайта arm

[sasamy 1]

On 11/15/2023 at 2:01 PM, repstosw said:

CFLAGS=-DNDEBUG -Ofast -mthumb -mcpu=cortex-a7 -mfloat-abi=hard -mfpu=vfpv4 -mfpu=neon \ 
       -ftree-vectorize -fno-math-errno -fmax-errors=1 -ffunction-sections -fdata-sections

у меня на Linux простой -O3 вместо этой бороды даёт +1 fps

[mantech 48]

32 минуты назад, sasamy сказал:

теоретически arm быстрей должен работать а на практике промахи кеша инст

У меня не дает скомпилить под thumb

void IRQHandler()
{

__asm__ __volatile__ (

    "SUB      LR,LR,#+4\n"
        "SRSDB    #0x1F!\n"
        "CPS      #0x1F\n"
        "PUSH     {R0-R6,R12,LR}\n"
        "VMRS     R0,FPSCR\n"
        "PUSH     {R0}\n"
        "VPUSH    {D0-D7}\n"
        "VPUSH    {D16-D31}\n"
        "MOV      R0,SP\n"
        "SUB      SP,SP,#+4\n"
        "BIC      SP,SP,#0x7\n"
        "STR      R0,[SP, #+0]\n"

        "LDR      r1, =irq_handler\n"
        "BLX      r1\n"

        "LDR      SP,[SP, #0]\n"
        "VPOP     {D16-D31}\n"
        "VPOP     {D0-D7}\n"
        "POP      {R0}\n"
        "VMSR     FPSCR,R0\n"
        "POP      {R0-R6,R12,LR}\n"
        "RFEIA    SP!\n"
        );

}
 

пишет - Error: r13 not allowed here -- `bic SP,SP,#0x7'

[GenaSPB 11]

А как ыы заставить оьработчики в thumb делать?