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

B@R5uk, по приведенной тобой картинке видно, что внутри МК в одном цикле "спрятано" 3 такта.
но как я выше сказал, снаружи мы эти такты видеть не можем. именно поэтому я и сказал, что называть цикл тактом - не правильно.

Размышлял я тут над тем, как бы всё-таки с помощью таблицы квадратов перемножить две четырёхбайтные величины. Ведь таблица в памяти уже есть, хотелось бы использовать ресурс по-полной. Даже составил шпаргалку:

Смотрю я на неё и думаю: многовато сложений и вычитаний, да ещё на каждое сложение надо извлечение из ПЗУ сделать, да на каждую разность модуль разности посчитать. Очень уж большое количество инструкций потребуется, а у меня ПЗУ 36% на всё про всё осталось. Умножение со сдвигами в цикле куда компактнее, хоть и медленнее.

И тут меня осенило: :idea:

а почему бы не организовать и здесь цикл??!! Вон, даже однотипные повторяющиеся (со сдвигом) блоки есть. Если ещё подключить ОЗУ со скользящим указателем, реально даже сделать процедуру, работающую с одним из сомножителей произвольной длины. А если пожертвовать производительностью и запилить два вложенных цикла, можно вообще перемножать оба сомножителя произвольной длины весьма компактным кодом. Такой простор для творчества!

Вложения

FourTimesFour.png: (6.67 KiB) Скачиваний: 544

Последний раз редактировалось B@R5uk Вт апр 12, 2022 11:36:26, всего редактировалось 1 раз.

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

Gudd-Head, разве не бывает ситуаций, когда надо находить произведение 32-битных чисел? Да вон хоть арифметика с плавающей точкой подразумевает умножение чисел разрядностью выше 16 бит.

Спойлер

В моём случае, как я уже писал, мне надо навести статистику поступающих трёхбайтных величин. Статистика — это среднее и среднеквадратичное отклонение:

μ = 1/N * Σ x_i
σ^2 = 1/N * Σ (x_i - μ)^2

Применение формул в лоб подразумевает хранение в памяти всех получаемых мной величин, а так же работа с плавающей точкой на всех этапах вычислений. На моём МК это нереализуемо практически (памяти всего то 128 байт). Поэтому я использую модернизированную формулу для расчётов среднеквадратичного отклонения:

(N σ)^2 = N * Σ x_i^2 - (Σ x_i)^2

В таком виде львиная доля вычислений производится в целочисленном виде, что, во-первых, позволяет сильно ускорить вычисления, а во-вторых, не приводит к потерям точности вследствие конечной разрядности числа с плавающей точкой (это особенно касается вычитания).

В итоге, я ищу сумму квадратов 3-байтных величин, получаю 7-байтную величину, умножаю её на 3-байтную (количество событий N), в силу ограничений на величины у меня получается 8-байтная величина, а не 10-байтная. Из неё я вычитаю квадрат 4-байтной величны. Дальше уже идёт арифметика с плавающей точкой.

Между тем, накатал набросок процедуры умножения 32-битной величины на 8N-битную (4 байта на N байт). Время работы: 113 * N + 50 циклов (502 цикла для N = 4). Шпаргалка к процедуре (для N = 4) двумя постами выше.

Спойлер

Код:: ;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-== ; Процедура умножает 4-байтную величину ABCD на N-байтную T...T ; Исходные ресурсы: ; - r16 - r19 - первый сомножитель (ABCD) ; - r20 - количество N байт 2-го сомножителя ; - X:(X+N-1) - второй сомножитель (в ОЗУ) ; - X - указатель на второй сомножитель в ОЗУ и буфер результата ; Возвращаемый результат: ; - r12 - r15 - старшие 4 байта произведения ; - (X+N):(X+2N-1) ; - младшие N байт произведения (в ОЗУ) ; Используемые ресурсы: ; - zero - глобальный (для всей программы) регистр с нулевым значением ; - r4 - r11 - квадраты байтов первого сомножителя ; - r21 - очередной байт 2-го сомножителя ; - r22, r23 - подгружаемые квадраты разностей и байтов 2-го сомножителя ; - r24 - рабочий регистр ; - r25 - счётчик итераций цикла ; - Z - указатель на таблицу квадратов в ПЗУ ; - STACK - 1 байт стека ; Размер процедуры 226 байт (113 инструкций) ; Время выполнения 113 * N + 50 циклов (включая rcall и ret) ;--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- mul_32x8N: ; Подгрузка из ПЗУ квадратов байтов первого сомножителя ldi ZH, HIGH(2*SquareTable1) mov ZL, r16 ; Байт D lpm r5, Z ; Старший байт D^2 ldi ZH, HIGH(2*SquareTable0) lpm r4, Z ; Младший байт D^2 mov ZL, r17 ; Байт C lpm r6, Z ; Младший байт C^2 ldi ZH, HIGH(2*SquareTable1) lpm r7, Z ; Старший байт C^2 mov ZL, r18 ; Байт B lpm r9, Z ; Старший байт B^2 ldi ZH, HIGH(2*SquareTable0) lpm r8, Z ; Младший байт B^2 mov ZL, r19 ; Байт A lpm r10, Z ; Младший байт A^2 ldi ZH, HIGH(2*SquareTable1) lpm r11, Z ; Старший байт A^2 ; Инициализация вспомогательных данных clr r12 ; Инициализация рабочих регистров clr r13 clr r14 clr r15 clr r24 mov r25, r20 ; Счётчик итераций mul_32x8N_1: ; Основной цикл процедуры ld r21, X ; Очередной байт T второго сомножителя ; Расчёт модулей первых двух разностей mov ZL, r18 ; Байт B sub ZL, r21 ; Разность B - T brcc mul_32x8N_2 neg ZL ; Модуль разности |B - T| mul_32x8N_2: push ZL ; Сохранение |B - T| в стек mov ZL, r16 ; Байт D sub ZL, r21 ; Разность D - T brcc mul_32x8N_3 neg ZL ; Модуль разности |D - T| mul_32x8N_3: ; Прогрузка и вычитание из результата квадратов первых двух разностей lpm r23, Z ; Старший байт (D - T)^2 ldi ZH, HIGH(2*SquareTable0) lpm r22, Z ; Младший байт (D - T)^2 sub r12, r22 sbc r13, r23 pop ZL ; Извлечение |B - T| из стека lpm r22, Z ; Младший байт (B - T)^2 ldi ZH, HIGH(2*SquareTable1) lpm r23, Z ; Старший байт (B - T)^2 sbc r14, r22 sbc r15, r23 sbc r24, zero ; Заём ; Добавление квадратов байтов первого сомножителя add r12, r4 ; Младший байт D^2 adc r13, r5 ; Старший байт D^2 adc r14, r8 ; Младший байт B^2 adc r15, r9 ; Старший байт B^2 adc r24, zero ; Перенос ; Подгрузка квадрата байта T второго сомножителя mov ZL, r21 ; Байт T ldi ZH, HIGH(2*SquareTable0) lpm r22, Z ; Младший байт T^2 ldi ZH, HIGH(2*SquareTable1) lpm r23, Z ; Старший байт T^2 ; Добавление квадрата байта T второго сомножителя add r12, r22 ; Младший байт T^2 adc r13, r23 ; Старший байт T^2 adc r14, r22 ; Младший байт T^2 adc r15, r23 ; Старший байт T^2 adc r24, zero ; Перенос ; Сдвиг разрядов на один байт с сохранением одного байта произведения add XL, r20 ; Сохранение в ОЗУ очередного байта st X+, r12 ; произведения и перевод указателя sub XL, r20 ; на следующий байт 2-го множителя mov r12, r13 mov r13, r14 mov r14, r15 mov r15, r24 clr r24 ; Инициализация старшего рабочего байта ; Добавление квадрата байта T второго сомножителя add r12, r22 adc r13, r23 adc r14, r22 adc r15, r23 adc r24, zero ; Перенос ; Добавление квадратов байтов первого сомножителя add r12, r6 ; Младший байт C^2 adc r13, r7 ; Старший байт C^2 adc r14, r10 ; Младший байт A^2 adc r15, r11 ; Старший байт A^2 adc r24, zero ; Перенос ; Расчёт модулей вторых двух разностей sub ZL, r19 ; Разность T - A brcc mul_32x8N_4 neg ZL ; Модуль разности |A - T| mul_32x8N_4: push ZL ; Сохранение |A - T| в стек mov ZL, r17 ; Байт C sub ZL, r21 ; Разность C - T brcc mul_32x8N_5 neg ZL ; Модуль разности |C - T| mul_32x8N_5: ; Прогрузка и вычитание из результата квадратов вторых двух разностей lpm r23, Z ; Старший байт (C - T)^2 ldi ZH, HIGH(2*SquareTable0) lpm r22, Z ; Младший байт (C - T)^2 sub r12, r22 sbc r13, r23 pop ZL ; Извлечение |A - T| из стека lpm r22, Z ; Младший байт (A - T)^2 ldi ZH, HIGH(2*SquareTable1) lpm r23, Z ; Старший байт (A - T)^2 sbc r14, r22 sbc r15, r23 sbc r24, zero ; Заём ; Декремент счётчика циклов и переход к следующей итерации dec r25 breq mul_32x8N_6 rjmp mul_32x8N_1 mul_32x8N_6: ; Деление результата на 2 для формирования искомого произведения add XL, r20 ; Указатель -- за N-й байт результата в ОЗУ lsr r24 ; Деление на 2 старших 4-х байт результата ror r15 ror r14 ror r13 ror r12 mul_32x8N_7: ; Деление младших N байт в ОЗУ на 2 ld r24, -X ; Сдвиг указателя и чтение очередного байта ror r24 ; Деление на 2 st X, r24 ; Сохранение байта на место dec r20 ; Декремент счётчика байтов brne mul_32x8N_7 ret ;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==

Что-то мне не очень нравится размер (11% от всего объёма ПЗУ). Надо бы написать для сравнения процедуру умножения двух 32-битных величин сдвигами и сложениями в цикле.

B@R5uk писал(а):

μ = 1/N * Σ x_i
σ^2 = 1/N * Σ (x_i - μ)^2

я использую модернизированную формулу для расчётов среднеквадратичного отклонения:

(N σ)^2 = N * Σ x_i^2 - (Σ x_i)^2

Чё, нормально. :shock:

Если не важен результат, а важен сам путь. :))

bollinger bands

Ну, не несёт в себе СКО от начала времён никакого смысла.

Тож, похоже, пустой вариант.
Я тебе столько времени сэкономил.
Охххххх
Тебе никто ничего не должен.

Сделал под копирку с 200-го дока процедуру перемножения 4-байтных величин:

Спойлер

Код:: ;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-== ; Процедура перемножает две 4-байтные величины ; Исходные ресурсы: ; - r16 - r19 - первый сомножитель (затирается в процессе работы) ; - r20 - r23 - второй сомножитель ; Возвращаемый результат: ; - r12 - r15 - Старшие 4 байта произведения ; - r16 - r19 - Младшие 4 байта произведения ; Используемые ресурсы: ; - r24 - счётчик итераций ; Размер процедуры 50 байт (25 инструкций) ; Время выполнения 431 + 3 * Sb циклов (максимум 527 циклов, включая rcall и ret), ; где Sb -- число единичных бит первого сомножителя ;--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- mul_32x32: clr r12 clr r13 clr r14 clr r15 ldi r24, 0x20 lsr r19 ror r18 ror r17 ror r16 mul_32x32_1: ; Основной цикл процедуры brcc mul_32x32_2 add r12, r20 adc r13, r21 adc r14, r22 adc r15, r23 mul_32x32_2: ror r15 ror r14 ror r13 ror r12 ror r19 ror r18 ror r17 ror r16 dec r24 brne mul_32x32_1 ret ;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==

Время выполнения 527 циклов максимум. Что-то у табличного подхода нет никакого выигрыша по сравнению с этой стандартной процедурой. Видать, надо всё таки формулу ab = ((a + b)^2 - (a - b)^2) / 4 использовать, а не формулу ab = (a^2 + b^2 - (a - b)^2) / 2. В полтора раза меньше сложений и операций чтения из ПЗУ.

Добавлено after 9 minutes 44 seconds:

akl писал(а):

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

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

Спойлер

Код:: ;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-== ; Процедура перемножает две 3-байтные величины ; Исходные ресурсы: ; - r16 - r18 - первый сомножитель (затирается в процессе работы) ; - r19 - r21 - второй сомножитель ; Возвращаемый результат: ; - r13 - r15 - Старшие 3 байта произведения ; - r16 - r18 - Младшие 3 байта произведения ; Используемые ресурсы: ; - r22 - счётчик итераций ; Размер процедуры 40 байт (20 инструкций) ; Время выполнения 277 + 2 * Sb циклов (максимум 325 циклов, включая rcall и ret), ; где Sb -- число единичных бит первого сомножителя ;--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- mul_24x24: ; Подготовка старших байт результата и счётчика итераций clr r13 clr r14 clr r15 ldi r22, 0x18 lsr r18 ror r17 ror r16 mul_24x24_1: ; Основной цикл процедуры brcc mul_24x24_2 add r13, r19 adc r14, r20 adc r15, r21 mul_24x24_2: ror r15 ror r14 ror r13 ror r18 ror r17 ror r16 dec r22 brne mul_24x24_1 ret ;==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==-==

Код, конечно, в 3 раза медленнее, чем возведение в квадрат табличным методом, но его компактность, расход регистров (на 1 меньше, можно сделать на 2 меньше, если воспользоваться стеком) и отсутствие таблицы в 25% памяти заставляют задуматься.

B@R5uk писал(а):Что-то мне кажется вы не правильно посчитали время работы. Ну не может быть так медленно, даже если код не самый оптимальный.

Считает авр-студия. А умножение неоптимальное от слова совсем. Это была первая попытка сделать программу для AT90S2313 где-то в 1999м.

B@R5uk писал(а):

В моём случае, как я уже писал, мне надо навести статистику поступающих трёхбайтных величин.

Тогда изначально был неправильно выбран МК

2 Starichok51. Про циклы и такты. Ещё когда начал изучать AVR, помнится с того времени, что при запуске МК первая команда выполняется несколько тактов. То ли 3, то ли 4 такта. Затем внутренняя логика МК встаёт как надо. И конвейер выполняет команды за количество тактов, указанное в документации.

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

Вы все не так поняли. Я говорил не о времени запуска МК. А о внутренней логике МК. О триггерах. Первые несколько тактов подготавливают конвейер команд, чтобы после этих первых нескольких тактов была возможность работать за один такт, у большинства команд. За исключением тех, которые выполняются за несколько тактов. Уточнять в даташите.
Используется многофазное тактирование. Отсюда, выполнение самой первой команды всегда будет выполняться несколько тактов. Более точно скажут только производители МК AVR.

Тут смотрите. Быстро, навскидку. Искать более конкретную информацию сейчас нет возможности. Речь идёт о выборке, декодировании команд конвейером.

Смотрите: Первый такт. Вычитка команды. Второй такт. Отправка в дешифратор. Третий такт. Выполнение команды. Четвертый такт. Запись результата в регистры. Пока выполняются эти самые первые такты, внутренняя логика принимает нужные состояния, чтобы в дальнейшем все последующие команды выполнялись за кол-во тактов соответствующее их битности и так далее и тому подобное. Грубо, приближенно, примерно так. Более точно ищите в литературе, материалах инета.

И это высший пилотаж инженерной мысли. Когда ты заранее создал условия для выполнения поставленной задачи. Готовь сани летом, телегу зимой. Приготовить рабочее место и инструмент, чтобы ты потом не бегал, не тратил время на суету.

нет в AVR конвейера команд.

Я сейчас быстро не найду, где я прочитал про AVR. Но в этом материале было подробно расписано, как была достигнута возможность выполнения команды за один такт. Лично мне нет надобности доказывать вам, мне достаточно, что я знаю об этой особенности. Что вы будете делать с этим, это ваше дело.
Можете задать вопрос на более профессиональных площадках.

Предлагаю опыт. МК AVR могут работать на самых минимальных частотах. Вплоть до отсутствия. Поэтому, делаем следующее. Фьюзами настраиваем МК на мгновенное включение. Внешнее тактирование. Тестовую программу пишем на ассемблере. Начинаем подавать импульсы, и смотрим, когда МК дернет лапкой. Код программы может быть одной командой.

sbi DDRx, x

Для окончательного убеждения последующие команды.

nop
cbi DDRx, x
nop
sbi DDRx, x

Все команды однотактные

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

Кхм. Рулим нижним ключом. По схеме открытый сток.

Вариант умножения двух 5-байтных величин. Используется младшая часть регистрового файла и один регистр старшей части.

mult40.txt: (861 байт) Скачиваний: 48

Я считаю, что все эти разговоры про "такты - циклы" - просто сотрясение воздуха. Открываем ДШ, находим .

Что такое #Clocks - смотрим соответствующий раздел System Clock с учётом System Clock Prescaler путём CLKPR. Всё. Неоднократно проверено практикой на Studio. И никаких тебе конвейеров, траволаторов и прочих транспортных средств.
Насчёт "первая команда выполняется дольше"... Включили оборудование, оно работает сутки, выполнены триллионы команд. И вдруг у нас тюкнуло: а самя-то первая после включения команда за сколько выполнилась?
Али я не прав?

Вложения

ISS.JPG: (9.39 KiB) Скачиваний: 179

С одной стороны ты прав. Не все ли равно, сколько тактов выполняется самая первая команда. Просто Старичок стал спорить. С одной стороны. С другой, знать, как разработчики МК добились выполнения большинства команд за один такт. Хотя бы для эрудиции

Вообще, опыт стоит провести. Просто нужно садиться и паять. А со временем сейчас не ахти. Тем более, дачный сезон начался. Либо на триггере импульсы соображать, либо брать ещё один тестовый МК, чтобы убрать дребезг кнопок, и выдавать импульсы с кнопки.

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

Я считаю - не нужная это затея. Так можно до отдельного транзистора дойти, а там - и до электрона/дырки. ДШ даёт нам достаточный для разработчика уровень абстракции. Разве что побороться с Микрощипами, сделать лучше, что особенно актуально в плане импортозамещения.

А в практическом смысле - дача важнее: запасаться картошкой, фруктами. Солью, дровами

в свете последних ситуёвин.

Demiurg писал(а):как разработчики МК добились выполнения большинства команд за один такт.

сколько можно повторять - не за один такт ,а за один ЦИКЛ!!!
а сколько там внутри "спрятано" тактов, мы не видим, потому этого не знаем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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