Обсуждаем контроллеры компании Atmel.
Ответить

Умножение и возведение в квадрат без аппаратной поддержки

Пт апр 08, 2022 18:34:01

Пишу на асме под ATtiny2313A.

Затребовалось мне посчитать сумму квадратов трёхбайтных величин. Я, в принципе, знаю один способ умножения столбиком. В нём произведение строится в цикле по битам одно сомножителя прямо на месте другого сомножителя (с добавлением дополнительных байт для хранения результата, разумеется). Соответствующая процедура очень компактна по коду и использует минимально возможное число регистров процессора (1 на счётчик, n на один множитель и n*m на результат и другой множитель, размер которого m байт). Но она жутко медленная, а мне нужно считать квадраты в прерывании быстро.

Я знаю другой способ, с использованием таблиц квадратов. Кто не знаком с ним, вот эту статью можно взять за отправную точку. Единственный минус подхода в статье заключается в том, что там используют сумму сомножителей, которая на один бит выходит за пределы размера сомножителей. Использование схемы ab = (a^2 + b^2 - (a - b)^2) / 2 более рационально в плане памяти, на мой взгляд. Особенно, если учесть, что таблица квадратов байта занимает в памяти 512 байт, что уже составляет 25% от всего ПЗУ моего МК.

Для построения программы составил себе шпаргалку:
Изображение
Теперь вот думаю, как бы это по-лучше всё складывать. Квадраты будут суммироваться в кумулятивную сумму, которую логично хранить в оперативке. Так как обращение к ней медленнее, чем к регистрам, то логично формировать каждый байт-разряд суммы залпом, один раз читая его в начале и один раз записывая его в конце. Чтение таблицы квадратов из ПЗУ тоже не быстрая операция, поэтому логично читать каждый квадрат один раз и хранить результат в регистре, пока в нём есть потребность. Чтобы не таскать перенос от сложения по всей сумме от текущего разряда до самого старшего, логично собирать все переносы в отдельный регистр и добавлять к следующему разряду суммы, только когда приступим к его формированию. В итоге требуется очень много регистров МК, чтобы процедура работала шустро. Возможно, где-то быстродействием стоит пожертвовать, чтобы сократить расход регистров, они и в других частях программы используются.

Кто-нибудь делал что-нибудь подобное? Какие могут быть советы/рекомендации?

Добавлено after 2 hours 5 minutes 53 seconds:

Как-то так выглядит умножение двух байт:

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

При этом важно, чтобы адрес таблицы в памяти был "круглым": заканчивался на 0x00 или 0x80.
Вложения
TribyteSquare.png
(2.93 KiB) Скачиваний: 683

Re: Умножение и возведение в квадрат без аппаратной поддержк

Пт апр 08, 2022 20:21:38

Как-то так выглядит умножение двух байт

Жесть :shock:
Может, не стоит изобретать велосипед?
Изображение
Вложения
Снимок экрана 2022-04-08 201901.png
(62.99 KiB) Скачиваний: 648

Re: Умножение и возведение в квадрат без аппаратной поддержк

Пт апр 08, 2022 21:46:47

B@R5uk, полностью поддерживаю Gudd-Head.
стандартное "тупое" умножение двух 1-байтных чисел с помощью сдвигов и сложения занимает 41 цикл вместе с rcall и ret. и вообще не требует никаких таблиц.
вот выдержка из файла, идущего в комплекте AvrStudio4:

что на 4 цикла быстрее твоего изобретенного "велосипеда".
и в AVR нет тактов, есть только циклы.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 08:48:56

Я знаком с двухсотым доком (давно это было, правда). Спасибо, что напомнили.


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

Добавлено after 1 hour 8 minutes 33 seconds:

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


Код под катом в 2 раза быстрее и меньше по размеру 200-доковской процедуры, оптимизированной под скорость, и в 3 раза быстрее компактной процедуры с циклом. С трёхбайтной величиной выигрыш, мне думается, будет ещё больше.

Шпаргалка к процедуре:

Изображение
Вложения
TwobyteSquare.png
(1.02 KiB) Скачиваний: 607
Последний раз редактировалось B@R5uk Сб апр 09, 2022 09:43:09, всего редактировалось 2 раз(а).

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 09:01:47

B@R5uk писал(а):...Затребовалось мне посчитать сумму квадратов трёхбайтных величин...
Блин. Старею что ли.
По мне, сумма квадратов выражается a²+b²+c² Хотелось бы узнать сколько в результате получится циклов при максимальных трехбайтных беззнаковых величин.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 09:31:24

akl, извиняюсь, что недостаточно ясно объяснил задачу. Одна трёх-байтна величина — это

65536 a + 256 b + c,

где a, b и c — это, соответственно, старший, средний и младший байты этой величины. У меня их много:

65536 a_i + 256 b_i + c_i;

каждую из них надо возвести в квадрат и просуммировать:

Σ (65536 a_i + 256 b_i + c_i)^2.

В формуле в первом посте разложен на компоненты квадрат лишь одного слагаемого.

...в AVR нет тактов, есть только циклы.
Изображение А в чём разница?

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 10:07:53


Линейная программа суммы квадратов максимальных беззнаковых трехбайтных величин занимает 2967 циклов. Результат в R23...R29 в формате старший младший. :)

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 10:43:54

B@R5uk писал(а):А в чём разница?
например, в самых первых МК 51-го семейства машинный цикл состоял из 12 машинных тактов. при дальнейшем развитии этого семейства цикл сократили до 6 тактов. и все эти такты можно было воочию наблюдать на выводах этих МК.
а что делается во время цикла в авровских МК, нам неизвестно, так как снаружи мы этого не видим.
и в документации на всё семейство AVR говорится только о циклах, о тактах даже упоминания нет.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 11:13:23

Starichok51, спасибо, теперь понятно.
...занимает 2967 циклов...
Три умножения за три тысячи тактов. Это по тысяче тактов на одно умножение. Как-то слишком уж медленно. Мне бы хотя бы раз в 5 бы быстрее.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 15:29:47

Может нужно начать от печки. Откуда начальные значения? Для чего нужно умножать и возводить в квадрат?

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 18:22:33

pyzhman, не стоит сильно уж оффтопить. Задача поставлена и сама по себе представляет интерес.

Сделал предварительный набросок процедуры для трёхбайтных данных (время выполнения 126 тактов):

Теперь бы надо как-то перетусовать операции, чтобы уменьшить расход регистром CPU до божеских 8-12 штук. Можно даже пожертвовать быстродействием немного, а так же позволить процедуре затереть исходную величину.

Кто-нибудь знает программу-оптимизатор ассемблерного кода, способную справиться с этой задачей?

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 19:13:00

Не знаю, что конкретно у Вас, но, может, эта формула поможет..
Изображение
Вложения
1.png
(29.11 KiB) Скачиваний: 474

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 19:59:18

Карбофос, сумма за пределы таблицы выходит. Искать квадрат (модуля) разности гораздо практичнее.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Сб апр 09, 2022 23:23:38

Рекуррентное вычисление квадрата. a - предыдущее значение, b - разница.

Добавлено after 3 hours 12 minutes 25 seconds:
Re: Умножение и возведение в квадрат без аппаратной поддержки
Допустим, прошло 256 тиков вашего таймера без событий - обновились.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Вс апр 10, 2022 06:52:34

Сделал предварительный набросок процедуры для трёхбайтных данных (время выполнения 126 тактов)...

Проверил. Очень понравилось. :beer:
Убрал обмен с памятью. Вместо 119 циклов стало 91.

Re: Умножение и возведение в квадрат без аппаратной поддержк

Вс апр 10, 2022 09:13:00

Кстати, а как эту задачу решит СИшный компилятор, смотрели?

Re: Умножение и возведение в квадрат без аппаратной поддержк

Вс апр 10, 2022 10:10:45

Gudd-Head, не-а. Хотя мне очень-очень интересно, что он выдаст.
По идее надо скомпилировать на скорость и экономию регистров вот такой код:
Если кому не лень скомпилить и поделиться со всеми, буду очень благодарен. :)

Шпаргалка к коду:
Вложения
TribyteSquareExtended.png
(1.62 KiB) Скачиваний: 109

Re: Умножение и возведение в квадрат без аппаратной поддержк

Вс апр 10, 2022 12:40:13

и в документации на всё семейство AVR говорится только о циклах, о тактах даже упоминания нет.

Может, у нас разные документации ? :?
Изображение
pyzhman, не стоит сильно уж оффтопить.

А мне не кажется таким уж офтопом. Одно из правил ТРИЗ гласит: при оптимизации операции первое, что надо рассмотреть: а нельзя ли вообще обойтись без этой операции. Конечно, ТСу виднее, обсуждать тут не резон, но квадраты 3-байтных чисел, да ещё в прерывании...
Правда, если частота прерываний - 50Гц, то можно успеть.
А задача утоптать алгоритм в 5 раз мне представляется маловероятой на данном железе. Уж выбачайце за пессимизм. Хотя самому приходилось бороться за каждую микросекунду... Вспомню - вздрогну.
Вложения
Циклы.JPG
(10.27 KiB) Скачиваний: 368

Re: Умножение и возведение в квадрат без аппаратной поддержк

Вс апр 10, 2022 13:38:21

Jack_A писал(а):Может, у нас разные документации ?
через букву "Т" обозначены не такты внутри цикла, а такты внешней тактовой частоты.
из этой картинки (в нижней части) прекрасно видно, время выполнения цикла равно одному такту внешней тактовой частоты.
у меня есть давно предположение, что внутри есть умножитель частоты, который и создает некоторое количество тактов внутри МК за 1 такт внешней тактовой частоты.
вот, если бы ты нашел картинку, где разрисованы процессы внутри цикла ...

Re: Умножение и возведение в квадрат без аппаратной поддержк

Вс апр 10, 2022 16:22:51

Правда, если частота прерываний - 50Гц, то можно успеть.
А задача утоптать алгоритм в 5 раз мне представляется маловероятой на данном железе.
Вот те пополам! Вы почитайте сообщения то по-внимательней! Представлен же вариант процедуры, которая в 8 раз быстрее! А чуть ниже (если отказаться от обращения к ОЗУ) то во все 11 раз!

Starichok51

Добавлено after 59 minutes 7 seconds:

Убрал обмен с памятью. Вместо 119 циклов стало 91.
Да, пожалуй это здравая мысля. Кумулятивная сумма обновляется каждое прерывание, поэтому её логичнее хранить в регистровом файле.

Отполировал немного свою процедуру. Пришлось добавить одно обращение к стеку (пара Push/pop), но за то теперь вместо 27 регистров задействовано только 18, причём 7 из них хранят кумулятивную сумму, а 3 (zero и указатель Z) являются расшаренным ресурсом. Экономия! Как-то более плотно упаковать вычисления мне что-то не видится возможным без заметной потери производительности. Время работы 102 цикла.
Если кто-то захочет покрутить вычисления, то тут надо обратить внимание на один тонкий момент. Для того, чтобы не таскать переносы по всем старшим разрядам, я аккумулирую их во временные коллекторы (регистры r18 и r19 в коде выше). При этом в эти же коллекторы идут и заёмы. Поскольку отрицательные заёмы и положительные переносы добавляются к конечной сумме совершенно по-разному, важно следить, чтобы содержимое этих коллекторов в момент сохранения не оказалось отрицательным, иначе придётся городить костыли, либо вычисления вообще окажутся некорректными. В коде выше это требование выполняется благодаря правильной группировке вычитаний и сложений. А именно, величина A^2 + B^2 - (A - B)^2 не смотря на наличие в ней вычитаемого никогда не оказывается отрицательной, то есть, если она и даёт перенос, то он будет положительным, и его можно будет без заморочек добавить к конечной сумме.

Шпаргалка к процедуре всё та же:
Изображение

Добавлено after 47 minutes 15 seconds:

Теперь мне требуется организовать возведение в квадрат 4-байтной величины и умножение 3-байтной на 7-байтную. С одной стороны, к этим процедурам уже нет требования на быстродействие, поэтому их, в принципе, можно было бы организовать обычным умножением сдвигами в цикле. А с другой, — моё внутреннее чувство перфекционизма корёжится от такой мысли. "Быть или не быть?" — вот в чём вопрос.
Вложения
TribyteSquareExt.png
(985 байт) Скачиваний: 321
Figure 4.5.png
(2.19 KiB) Скачиваний: 88
Ответить