Это перевод апноута Atmel "AVR201: Using the AVR® Hardware Multiplier" [1], посвященного использованию команд умножения ассемблера микроконтроллеров AVR.

Общие возможности аппаратного перемножителя AVR, описанные в этом апноуте, включают в себя:

• 8- и 16-bit реализации.
• Подпрограммы для знаковых (Signed) и беззнаковых (Unsigned) чисел.
• Дробное (Fractional) знаковых (Signed) и беззнаковых (Unsigned) чисел.
• Пример выполняемых программ.

[Введение]

Термин megaAVR относится к сериям относительно новых устройств микроконтроллеров семейства AVR RISC, которое включает в себя, помимо других новых улучшений, также и аппаратный перемножитель. Этот перемножитель может перемножать два 8-битных числа, выдавая 16-битный результат только за 2 тактовых цикла. Перемножитель может обработать числа со знаком, и числа без знака, и дробные числа без уменьшения скорости и без лишних затрат кода. Первая секция этого документа даст некоторые примеры по использованию перемножителя в 8-битной арифметике.

Чтобы можно было использовать перемножитель, в систему команд AVR были добавлены 6 новых инструкций:

• MUL, умножение целых чисел без знака (unsigned integer).
• MULS, умножение целых чисел со знаком (signed integer).
• MULSU, умножение signed integer на unsigned integer.
• FMUL, умножение дробных чисел без знака (unsigned fractional).
• FMULS, умножение дробных чисел со знаком (signed fractional).
• FMULSU, умножение signed fractional на unsigned fractional.

Отдельные инструкции MULSU и FMULSU добавлены для улучшения скорости и плотности кода при умножении 16-битных операндов. Во второй секции будут показаны примеры, как эффективно использовать умножитель для 16-bit арифметики.

Компонентом, который делает выделенный цифровой сигнальный процессор специально предназначенным для обработки сигналов, является так называемый узел умножения с добавлением (Multiply-Accumulate unit, MAC). Этот узел функционально эквивалентен перемножителю, напрямую соединенному с узлом арифметики и логики (Arithmetic Logic Unit, ALU). Микроконтроллеры megaAVR разработаны так, чтобы предоставить семейству AVR возможность эффективно выполнять такую же multiply-accumulate операцию. В этом апноуте будут рассмотрены примеры реализации операции MAC.

Операция Multiply-Accumulate (которая иногда называется как multiply-add) имеет один критический недостаток. Когда добавляются несколько значений к одному значению результата, даже когда положительные и отрицательные значения могут компенсировать друг друга, имеется риск переполнения результата, что становится очевидным. То есть, добавляя к примеру единицу к signed переменной-байту, которая содержит +127, результат вдруг станет -128, вместо того чтобы стать +128. Один из способов, который часто используется для решения этой проблемы, вовлекает использование дробных чисел, например чисел, которые меньше 1 и больше или равны -1. В последней секции будут рассмотрены некоторые проблемы, касающиеся использования дробных чисел.

В дополнение к новой инструкции умножения, к ядру megaAVR добавлены и несколько других изменений и улучшений. Одно из них - удобная в некоторых случаях новая инструкция MOVW (копирование регистрового слова, Copy Register Word), которая выполняет копирование одной регистровой пары в другую регистровую пару.

Файл AVR201.asm содержит исходный код для этого апноута, где применяется 16-битное умножение. Список всех реализаций алгоритмов с указанием их быстродействия приведен в следующих таблицах.

[8-разрядное умножение (8-bit Multiplication)]

8-битное умножение с использованием аппаратного перемножителя выполняется просто, что хорошо показывают примеры в этой секции. Просто загрузите операнды в два регистра (или только один для возведения в квадрат), и выполните одну из нескольких инструкций умножения. Результат будет помещен в регистровую пару R1:R0. Однако имейте в виду, что только инструкция MUL не имеет ограничений на использование регистров. На рисунке 1 показаны допустимые варианты использования регистров в качестве операндов для каждой их инструкций умножения.

Рис. 1. Допустимое использование регистров для инструкций умножения.

Пример 1 - базовое использование инструкции умножения

В этом примере приведен код ассемблера, который читает входное значение из порта B, умножает его на константу 5, и затем сохраняет результат в регистровой паре R17:R16.

1
2
3
4
5

      in r16,PINB          ; Прочитать значение из логических уровней
                           ; выводов ножек микроконтроллера порта B.
      ldi r17,5            ; Загрузить константу 5 в регистр r17.
      mul r16,r17          ; r1:r0 = r17 * r16
      movw r17:r16,r1:r0   ; Переместить результат в регистровую пару r17:r16.

Обратите внимание, что здесь используется новая инструкция MOVW. Этот пример допустим для всех инструкций умножения.

Пример 2 – специальные случаи

Этот пример показывает некоторые особые случаи допустимого применения инструкции MUL.

1
2
3
4
5
6

;Переменные A и B находятся в ячейках памяти SRAM.
      lds r0,variableA     ; Загрузка в r0 значения переменной A.
      lds r1,variableB     ; Загрузка в r1 значения переменной B.
      mul r1,r0            ; r1:r0 = variable A * variable B
      lds r0,variableA     ; Загрузка в r0 значения переменной A.
      mul r0,r0            ; r1:r0 = square(variable A) - квадрат A.

Даже если операнд помещен в регистровую пару R1:R0 (которая используется для результата умножения), операция умножения все равно даст корректный результат, поскольку значения R1 и R0 будут захвачены по первому циклу тактов, и результат операции будет сохранен обратно на втором цикле тактов.

Пример 3 - операция MAC

Последний пример в этой секции показывает реализацию операции multiply-accumulate (умножение с накоплением). Основная формула для этой операции может быть написана следующим образом:

c(n) = a(n) * b + c(n – 1)

Вот код, который выполняет операцию MAC:

1
2
3
4
5
6

      in r18,PINB       ; Прочитать значение из логических уровней
                        ; выводов ножек микроконтроллера порта B.
      ldi r19,b         ; Загрузить константу b в регистр r19.
      muls r19,r18      ; r1:r0 = variable A * variable B
      add r16,r0        ; r17:r16 += r1:r0
      adc r17,r1        ; r17:r16 = r18 * r19 + r17:r16

Обычное применение операции multiply-accumulate - вычисления для фильтров FIR (Finite Impulse Response) и IIR (Infinite Impulse Response), регуляторы PID и FFT (Fast Fourier Transform) [3]. Для этих приложений может быть удобной инструкция FMULS. Главный выигрыш использования инструкции FMULS вместо MULS в том, что 16-битный результат операции FMULS всегда может быть аппроксимирован к (четко определенному) 8-битному формату. Это будет обсуждаться далее в секции "Использование дробных чисел (Fractional Numbers)".

[16-разрядное умножение (16-bit Multiplication)]

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

На рис. 2 схематически проиллюстрирован основной алгоритм умножения двух 16-bit чисел с получением 32-bit результата (C = A • B). AH обозначает старший байт и AL младший байт операнда A. CMH обозначает средний старший байт и CML средний младший байт результата C. Аналогичные нотации используются и для остальных байт.

Рис. 2. Основной алгоритм 16-разрядного умножения.

Алгоритм является базовым для всех умножений. Все отдельные 16-битные результаты сдвигаются и складываются друг с другом. Знаковое расширение (sign ext) нужно только для чисел со знаком (signed), однако имейте в виду, что распространение бита переноса (carry) должно быть учтено для беззнаковых чисел (unsigned).

Операция 16-bit * 16-bit = 16-bit

Эта операция допустима и для чисел unsigned, и для чисел signed, даже если нужна только инструкция беззнакового умножения (MUL). Это иллюстрируется на рис. 3. Математическое объяснение следующее: когда A и B являются положительными числами, или как минимум одно из них равно 0, алгоритм полностью корректен, предоставляя результат C = A • B меньше 2^16, если результат пользуется как число unsigned, или меньше 2^15, если результат используется как число signed. Если оба множителя отрицательны, то используется нотация дополнения до двух (two’s complement); A = 2^16 - |A| и B = 2^16 - |B|:

C = A • B = (2^16 - |A|) • (216 - |B|) = |A • B| + 2^32 - 2^16 • (|A| + |B|)

В данном случае учитываются только 16 младших бит; последняя часть суммы отбрасывается, и мы получим корректный результат C = C = |A • B|.

Рис. 3. 16-битное умножение, 16-битный результат.

Когда один множитель отрицательный и другой положительный, например A отрицательный и B положительный:

C = A • B = (2^16 - |A|) • |B| = (2^16 • |B|) - |A • B| = (2^16 - |A • B|) + 2^16 • (|B| - 1)

Старшие биты будут отброшены и корректный результат с нотацией дополнения до двух будет C = 2^16 - |A • B|.

Полученный результат будет в диапазоне 0 .. 2^16 при использовании чисел unsigned, и в диапазоне -2^15 .. 2^15-1 при использовании чисел signed.

Этим показано, как реализовано внутри целочисленное умножение на языке C. Алгоритм может быть расширен для умножения 32-bit чисел с получением 32-bit результата.

Операция 16-bit * 16-bit = 24-bit

Функционал подпрограммы иллюстрируется на рис. 4. Для 24-bit версии подпрограмм умножения результат представлен в регистрах r18:r17:r16. Алгоритм дает корректный результат C = A • B, когда он меньше 2^24 при использовании умножения unsigned, и меньше чем ±2^23 при использовании умножения signed.

Рис. 4. 16-битное умножение, 24-битный результат.

Операция 16-bit * 16-bit = 32-bit

Пример 4 - базовое использование умножения целых чисел 16-bit * 16-bit = 32-bit. Ниже приведен пример, как вызывать подпрограмму умножения 16 x 16 = 32. Это также проиллюстрировано на рис. 5.

1
2
3
4
5

      ldi R23,HIGH(672)
      ldi R22,LOW(672)     ; Число 672 загружено в пару r23:r22.
      ldi R21,HIGH(1844)
      ldi R20,LOW(184)     ; Число 1844 загружено в пару r21:r20.
      call mul16x16_32     ; Вызов подпрограммы умножения.

Рис. 5. 16-битное умножение, 32-битный результат.

32-bit результат умножения unsigned чисел 672 и 1844 will теперь будет сохранен в регистрах R19:R18:R17:R16. Если будет вызвана muls16x16_32 вместо mul16x16_32, то будет выполнено умножение signed. Если будет вызвана mul16x16_16, то результат будет иметь длину только 16 бит, и сохранен в пару регистров R17:R16. Для данного примера значений чисел 16-bit результат будет некорректен.

Операция 16-бит MAC (16-bit multiply-accumulate)

Рис. 6. 16-битное умножение, 32-битный результат с накоплением.

[Использование дробных чисел (Fractional Numbers)]

Беззнаковые (unsigned) 8-битные дробные (fractional) числа используют формат, где допустимы числа в диапазоне 0 .. < 2. Биты 6 .. 0 представляют дробную часть числа, и бит 7 представляет целую часть числа (0 или 1), т. е. получается формат 1.7. Инструкция FMUL выполняет ту же самую работу, что и инструкция MUL, за исключением того, что результат получается сдвинутым влево на 1 бит, так что старший байт двухбайтного результата будет иметь тот же 1.7 формат, что и операнды (вместо формата 2.6). Имейте в виду, что если результат равен или больше 2, то он некорректен.

Для полного понимания формата дробных чисел полезно сравнить его с форматом целого числа: таблица показывает два 8-bit формата чисел unsigned. Дробные числа со знаком (signed fractional), как и целые числа со знаком (signed integer), используют знакомый формат числа с дополнением до 2 (two’s complement format). В этом формате могут быть представлены числа в диапазоне -1 .. < 1.

Если байт 10110010 интерпретировать как unsigned integer, то он будет равен 128 + 32 + 16 + 2 = 178. Иначе он может быть интерпретирован как unsigned fractional, тогда он равен 1 + 0.25 + 0.125 + 0.015625 = 1.390625. Если подразумевается, что это целое число signed integer, тогда он равен 178 - 256 = -122. Если же это число signed fractional, то 1.390625 - 2 = -0.609375.

Использование инструкций FMUL, FMULS и FMULSU не должно быть более сложным, чем инструкций MUL, MULS и MULSU. Однако, одна потенциальная проблема состоит в присваивании значений дробных переменных простым способом. Например, дробь 0.75 (= 0.5 + 0.25) будет 0110 0000, если использовать 8 бит.

Для конвертации положительного дробного числа в диапазоне 0 .. < 2 (например 1.8125) в формат, используемый в AVR, должен использоваться следующий алгоритм:

Есть ли "1" в числе?
Да, 1.8125 больше или равно 1.
   Байт теперь будет 1xxxxxxx
Имеется ли в остатке 0.5?
0.8125/0.5 = 1.625
Да, 1.625 больше или равно 1.
   Байт теперь будет 11xxxxxx
Имеется ли в остатке 0.25?
0.625/0.5 = 1.25
Да, 1.25 больше или равно 1.
   Байт теперь будет 111xxxxx
Имеется ли в остатке 0.125?
0.25/0.5 = 0.5
Нет, 0.5 меньше 1.
   Байт теперь будет 1110xxxx
Имеется ли в остатке 0.0625?
0.5/0.5 = 1
Да, 1 больше или равно 1.
   Байт теперь будет 11101xxx

Поскольку у нас не осталось больше остатка, остальные 3 бита будут равны 0, и конечный результат будет равен 11101000, где 1 + 0.5 + 0.25 + 0.0625 = 1.8125.

Для конвертации отрицательного дробного числа (negative fractional number) сначала добавьте 2 к числу, а потом используйте тот же самый алгоритм.

16-bit дробные числа используют тот же формат, что и 8-bit дробные числа; старшие 8 бит имеют точно такой же формат, как и у дробных чисел 8-bit. Младшие 8 бит увеличивают точность 8-bit формата; если формат 8-bit имеет точность of ±2^-8, то формат 16-bit имеет точность ±2^-16. Аналогично 32-bit дробные числа также увеличивают точность 16-bit дробных чисел. Обратите внимание на важное отличие между integer и fractional числами по использованию дополнительных байт: для дробных чисел увеличивается точность, а для целых чисел увеличивается диапазон.

Как было уже упомянуто ранее, использование чисел signed fractional в диапазоне -1 .. < 1 имеет преимущество по сравнению с использованием integer: когда умножаются два числа в диапазоне -1 .. < 1, то результат будет в диапазоне -1 .. 1, и в приближении (старшие байты) результата могут быть сохранены в том же количестве байт, что и множители, с одним лишь исключением: когда оба множителя равны -1, результат умножения должен быть равен 1, по поскольку число 1 не может быть представлено в этом дробном формате числа, то инструкция FMULS поместит вместо этого число -1 в паре регистров R1:R0. Таким образом, пользователь должен при использовании FMULS гарантировать, что по крайней мере хотя бы один из операндов не равен -1. Умножение 16-bit * 16-bit дробных чисел также имеет это ограничение.

Пример 5 – базовое использование умножения дробных чисел со знаком (Signed Fractional) 8-bit * 8-bit = 16-bit

Этот пример показывает код ассемблера, который читает входное значение из порта B, умножает его на дробную константу (-0.625), и затем сохраняет результат в регистровой паре R17:R16.

1
2
3
4

      in r16,PINB          ; Прочитать значение из ножек микроконтроллера.
      ldi r17,$B0          ; Загрузить -0.625 в регистр r17.
      fmuls r16,r17        ; r1:r0 = r17 * r16
      movw r17:r16,r1:r0   ; Переместить результат в r17:r16.

Обратите внимание, что использование инструкций FMULS (и FMUL) точно так же просто, как и использование MULS и MUL.

Пример 6 - операция MAC

Пример ниже использует данные из ADC (аналого-цифровой преобразователь) для данных операции multiply accumulate (MAC, сложение с накоплением). ADC должен быть предварительно сконфигурирован, чтобы формат результата ADC был совместим с дробным форматом с дополнением до 2 (fractional two’s complement format). Для ATmega83/163 это означает установку бита ADLAR в I/O регистре ADMUX, и использование дифференциального канала (тогда результат ADC будет нормализован к 1).

1
2
3
4
5

      ldi r23,$62       ; Загрузка старшего байта дроби 0.771484375
      ldi r22,$C0       ; Загрузка младшего байта дроби 0.771484375
      in r20,ADCL       ; Получение младшего байта преобразования ADC
      in r21,ADCH       ; Получение старшего байта преобразования ADC
      call fmac16x16_32 ; Вызов подпрограммы для дробной операции MAC.

Регистры R19:R18:R17:R16 будут инкрементированы результатом умножения 0.771484375 на значение, считанное из ADC (это может быть, к примеру, выборка звукового сигнала, над которым выполняется цифровая обработка). В этом примере результат преобразования ADC рассматривается как дробное число со знаком (signed fraction number). Мы могли бы рассматривать его как целое число со знаком (signed integer), и тогда для этого нужно вызвать mac16x16_32 вместо fmac16x16_32. В этом случае число 0.771484375 должно быть заменено на целое число (integer).

[Комментарии к реализациям]

Все 16-bit * 16-bit = 32-bit функции, реализованные здесь, начинают работу с очистки регистра R2, который просто используется как "dummy" регистр (заглушка) в операциях "сложение с переносом" (add with carry, ADC) и "вычитание с заёмом" (subtract with carry, SBC). Эти операции не изменяют значение регистра R2. Если регистр R2 не используется где-нибудь в коде, то не нужно очищать каждый раз R2 при вызове этих функций, но только один раз перед первым вызовом одной из этих функций.

[Ссылки]

1. AVR201: Using the AVR® Hardware Multiplier site:atmel.com.
2. Файл AVR201.asm, документация.
3. AVR223: Digital Filters with AVR (цифровые фильтры на AVR).