16битная математика для 8051 / ADuC847. Обычная и стандартная задача, встречающаяся сплошь и рядом. Просто? Давайте посмотрим.
Пусть у нас есть два 16битных беззнаковых числа во внутренней памяти: U1:U0 и V1:V0. Нужно вычислить их произведение, результат сложить в регистрах R0-R3.
R3:R2:R1:R0 = U1:U0 * V1:V0
Рассмотрим классический алгоритм вычисления этого произведения «в столбик»:
U1:U0 * V1:V0 ----------- + U0*V0 + V0*V1 + U1*V0 +U1*V1 ----------- R3:R2:R1:R0
Теперь закодируем его «в лоб», и подсчитаем число циклов, требующиеся для вычисления:
| Classic | Classic+ | ||||
|---|---|---|---|---|---|
| Code | 8051 | ADuC847 | Code | 8051 | ADuC847 |
| MOV A, U1 | 1 | 2 | MOV R4, #0 | 1 | 2 |
| MOV B, V1 | 2 | 3 | MOV A, U1 | 1 | 2 |
| MUL AB | 4 | 4 | MOV B, V1 | 2 | 3 |
| MOV R2, A | 1 | 1 | MUL AB | 4 | 4 |
| MOV R3, B | 2 | 2 | MOV R2, A | 1 | 1 |
| MOV A, U1 | 1 | 2 | MOV R3, B | 2 | 2 |
| MOV B, V0 | 2 | 3 | MOV A, U1 | 1 | 2 |
| MUL AB | 4 | 4 | MOV B, V0 | 2 | 3 |
| MOV R1, A | 1 | 1 | MUL AB | 4 | 4 |
| MOV A, R2 | 1 | 1 | MOV R1, A | 1 | 1 |
| ADD A, B | 1 | 2 | MOV A, R2 | 1 | 1 |
| MOV R2, A | 1 | 1 | ADD A, B | 1 | 2 |
| MOV A, R3 | 1 | 1 | MOV R2, A | 1 | 1 |
| ADDC A, #0 | 1 | 2 | MOV A, R3 | 1 | 1 |
| MOV R3, A | 1 | 1 | ADDC A, R4 | 1 | 1 |
| MOV A, U0 | 1 | 2 | MOV R3, A | 1 | 1 |
| MOV B, V1 | 2 | 3 | MOV A, U0 | 1 | 2 |
| MUL AB | 4 | 4 | MOV B, V1 | 2 | 3 |
| ADD A, R1 | 1 | 1 | MUL AB | 4 | 4 |
| MOV R1, A | 1 | 1 | ADD A, R1 | 1 | 1 |
| MOV A, R2 | 1 | 1 | MOV R1, A | 1 | 1 |
| ADDC A, B | 1 | 2 | MOV A, R2 | 1 | 1 |
| MOV R2, A | 1 | 1 | ADDC A, B | 1 | 2 |
| MOV A, R3 | 1 | 1 | MOV R2, A | 1 | 1 |
| ADDC A, #0 | 1 | 2 | MOV A, R3 | 1 | 1 |
| MOV R3, A | 1 | 1 | ADDC A, R4 | 1 | 1 |
| MOV A, U0 | 1 | 2 | MOV R3, A | 1 | 1 |
| MOV B, V0 | 2 | 3 | MOV A, U0 | 1 | 2 |
| MUL AB | 4 | 4 | MOV B, V0 | 2 | 3 |
| MOV R0, A | 1 | 1 | MUL AB | 4 | 4 |
| MOV A, R1 | 1 | 1 | MOV R0, A | 1 | 1 |
| ADD A, B | 1 | 2 | MOV A, R1 | 1 | 1 |
| MOV R1, A | 1 | 1 | ADD A, B | 1 | 2 |
| MOV A, R2 | 1 | 1 | MOV R1, A | 1 | 1 |
| ADDC A, #0 | 1 | 2 | MOV A, R2 | 1 | 1 |
| MOV R2, A | 1 | 1 | ADDC A, R4 | 1 | 1 |
| MOV A, R3 | 1 | 1 | MOV R2, A | 1 | 1 |
| ADDC A, #0 | 1 | 2 | MOV A, R3 | 1 | 1 |
| MOV R3, A | 1 | 1 | ADDC A, R4 | 1 | 1 |
| 56 | 71 | MOV R3, A | 1 | 1 | |
| 57 | 69 | ||||
Итак, на классическом ядре 8051 этот алгоритм потребует 56 циклов по 12 тактов каждый = 672 такта, что при осциляторе 11059200 составит 60.76 микросекунд.
У однотактового ядра ADuC847 некоторые операции требуют больше циклов, но каждый цикл = 1 такту. Так что 71 цикл = 71 такт. При стандартном часовом осциляторе 32768 и стандартном множителе в 48 (1.57 мегагерца) время вычисления составит 45 микросекунд. На максимальной скорости (множитель 384, 12.58 мегагерца) время вычисления будет 5.64 микросекунды.
Быстро? Очень быстро. Но если мы возьмём вместо операции ADDC A, #0 (2 цикла) операцию ADDC A, R4 (1 цикл), и предварительно обнулим R4, то в случае ADuC847 удастся сэкономить еще 2 цикла (колонка Classic+) если R4 придётся обнулить в этом месте, и 4 цикла, если он уже был обнулен где-то выше.
А можно ли быстрее? Часто встречающийся 8051Math считает именно таким образом. Во всех проектах, что я писал — вычислялось именно так. Но… Порядок имеет значение. Рассмотрим вот этот код:
| Opt1 | Opt1+ | ||||
|---|---|---|---|---|---|
| Code | 8051 | ADuC847 | Code | 8051 | ADuC847 |
| MOV A, U1 | 1 | 2 | MOV A, U1 | 1 | 2 |
| MOV B, V1 | 2 | 3 | MOV B, V1 | 2 | 3 |
| MUL AB | 4 | 4 | MUL AB | 4 | 4 |
| MOV R2, A | 1 | 1 | MOV R2, A | 1 | 1 |
| MOV R3, B | 2 | 2 | MOV R3, B | 2 | 2 |
| MOV A, U0 | 1 | 2 | MOV A, U0 | 1 | 2 |
| MOV B, V0 | 2 | 3 | MOV B, V0 | 2 | 3 |
| MUL AB | 4 | 4 | MUL AB | 4 | 4 |
| MOV R0, A | 1 | 1 | MOV R0, A | 1 | 1 |
| MOV R1, B | 2 | 2 | MOV R1, B | 2 | 2 |
| MOV A, U1 | 1 | 2 | MOV R4, #0 | 1 | 2 |
| MOV B, V0 | 2 | 3 | MOV A, U1 | 1 | 2 |
| MUL AB | 4 | 4 | MOV B, V0 | 2 | 3 |
| ADD A, R1 | 1 | 1 | MUL AB | 4 | 4 |
| MOV R1, A | 1 | 1 | ADD A, R1 | 1 | 1 |
| MOV A, R2 | 1 | 1 | MOV R1, A | 1 | 1 |
| ADDC A, B | 1 | 2 | MOV A, R2 | 1 | 1 |
| MOV R2, A | 1 | 1 | ADDC A, B | 1 | 2 |
| MOV A, R3 | 1 | 1 | MOV R2, A | 1 | 1 |
| ADDC A, #0 | 1 | 2 | MOV A, R3 | 1 | 1 |
| MOV R3, A | 1 | 1 | ADDC A, R4 | 1 | 1 |
| MOV A, U0 | 1 | 2 | MOV R3, A | 1 | 1 |
| MOV B, V1 | 2 | 3 | MOV A, U0 | 1 | 2 |
| MUL AB | 4 | 4 | MOV B, V1 | 2 | 3 |
| ADD A, R1 | 1 | 1 | MUL AB | 4 | 4 |
| MOV R1, A | 1 | 1 | ADD A, R1 | 1 | 1 |
| MOV A, R2 | 1 | 1 | MOV R1, A | 1 | 1 |
| ADDC A, B | 1 | 2 | MOV A, R2 | 1 | 1 |
| MOV R2, A | 1 | 1 | ADDC A, B | 1 | 2 |
| MOV A, R3 | 1 | 1 | MOV R2, A | 1 | 1 |
| ADDC A, #0 | 1 | 2 | MOV A, R3 | 1 | 1 |
| MOV R3, A | 1 | 1 | ADDC A, R4 | 1 | 1 |
| 50 | 62 | MOV R3, A | 1 | 1 | |
| 51 | 62 | ||||
Вуаля! 50 циклов вместо 56 для классического ядра (600 тактов, 54 микросекунды) и 62 цикла (от 39.4 до 4.9 микросекунд) для ADuC847. 10% ускорение просто за счет смены порядка операций: вычисляем сперва старшую половину, которую можно сохранить просто через MOV, вычисляем младшую половину, которую так же можно просто сохранить через MOV, и потом две средних половины. В результате, вместо 3х длинных сложений – остаётся два. К тому же, так как сложений осталось только два, исчезла разница между сложением с прямым нулём или регистром. Сэкономить на ADuC847 можно только если уже есть какой-либо нулевой регистр Rn.
Вспомним еще о методике быстрого умножения. При этом, для вычисления U*V используется такая формула:
U*V = (22n+2n)*(U1*V1)+2n*(U1-U0)*(V0-V1)+(2n+1)*U0*V0
В отличие от классической
U*V = 22n*U1*V1+2n*U1*V0+2n*U0*V1+U0*V0
В ней требуется только 3 умножения. Однако схема не применима для случая 16битной арифметики на ядре 51го процессора:
R3:R2:R1:R0 = 0
R3:R2 += U1*V1
R2:R1 += U1*V1
R2:R1 += U0*V0
R1:R0 += U0*V0
R2:R1 += (U1-U0)*(V0-V1) ! Signed
X=|U1-U0| sX=sign(U1-U0)
Y=|V0-V1| sY=sign(V0-V1)
sX=sY ? R2:R1 += XY
sX!=sY ? R2:R1 -= XY
Как видим, при вычислении потребуется одно _знаковое_ умножение, которое реализуется исключительно через вычисление модуля и знака по отдельности, сравнения знаков и сложения или вычитания результата.
| Fast1 | ||
|---|---|---|
| Code | 8051 | ADuC847 |
| MOV A, U1 | 1 | 2 |
| MOV B, V1 | 2 | 3 |
| MUL AB | 4 | 4 |
| MOV R2, A | 1 | 1 |
| MOV R3, B | 2 | 2 |
| MOV R1, A | 1 | 1 |
| MOV A, R2 | 1 | 1 |
| ADD A, B | 1 | 2 |
| MOV R2, A | 1 | 1 |
| MOV A, R3 | 1 | 1 |
| ADDC A, #0 | 1 | 2 |
| MOV R3, A | 1 | 1 |
| MOV A, U0 | 1 | 2 |
| MOV B, V0 | 2 | 3 |
| MUL AB | 4 | 4 |
| MOV R0, A | 1 | 1 |
| ADD A, B | 1 | 2 |
| MOV F0, C | 2 | 2 |
| ADD A, R1 | 1 | 1 |
| MOV R1, A | 1 | 1 |
| MOV A, R2 | 1 | 1 |
| ORL C, F0 | 2 | 2 |
| ADDC A, B | 1 | 2 |
| MOV R2, A | 1 | 1 |
| MOV A, R3 | 1 | 1 |
| ADDC A, #0 | 1 | 2 |
| MOV R3, A | 1 | 1 |
| CLR C | 1 | 1 |
| MOV A, U1 | 1 | 2 |
| SUBB A, U0 | 1 | 2 |
| MOV F0, C | 2 | 2 |
| JNC L1 | 2 | 3 |
| CPL A | 1 | 1 |
| INC A | 1 | 1 |
| CLR C | 1 | 1 |
| L1: MOV B, A | 1 | 2 |
| MOV A, V0 | 1 | 2 |
| SUBB A, V1 | 1 | 2 |
| JNC L2 | 2 | 3 |
| CPL A | 1 | 1 |
| INC A | 1 | 1 |
| JC AA | 2 | 3 |
| ANL C, /F0 | 1 | 2 |
| JMP BB | 2 | 3 |
| AA: ORL C, F0 | 1 | 2 |
| BB: MOV F0, C | 2 | 2 |
| MUL AB | 4 | 4 |
| JB F0, Lsub | 2 | 4 |
| ADD A, R1 | 1 | 1 |
| MOV R1, A | 1 | 1 |
| MOV A, R2 | 1 | 1 |
| ADDC A, B | 1 | 2 |
| MOV R2, A | 1 | 1 |
| MOV A, R3 | 1 | 1 |
| ADDC A, #0 | 1 | 2 |
| MOV R3, A | 1 | 1 |
| JMP END | 2 | 3 |
| Lsub: | ||
| XCH A, R1 | 1 | 1 |
| SUBB A, R1 | 1 | 1 |
| MOV R1, A | 1 | 1 |
| MOV A, B | 2 | 2 |
| XCH A, R2 | 1 | 1 |
| SUBB A, R2 | 1 | 1 |
| MOV R2, A | 1 | 1 |
| MOV A, R3 | 1 | 1 |
| SUBB A, #0 | 1 | 2 |
| MOV R3, A | 1 | 1 |
| END: | ||
| 80 | 104 | |
Как видим, одно умножение — это 4 такта. Одно знаковое умножение — гораздо больше. Поэтому, заменив два беззнаковых умножения одним знаковым, потери составили 30 циклов для 8051 (32.5 микросекунды) и 42 цикла для ADuC847 (от 26.7 до 3.3 микросекунд).
Мораль сей басни такова: порядок имеет значения, и не всегда прямой лучше кривого. Экономьте с нами! :)
