c++ - resta - Algoritmo de multiplicación más rápido de 16 bits para MCU de 8 bits
algoritmo para multiplicar dos numeros binarios (6)
Bueno, la mezcla de LUT y shift por lo general funciona.
Algo a lo largo de la línea, multiplicando entidades de 8 bits. Vamos a considerarlos compuestos por dos quads.
uint4_t u1, l1, u2, l2;
uint8_t a = 16*u1 + l1;
uint8_t b = 16*u2 + l2;
product = 256*u1*u2 + 16*u1*l2 + 16*u2*l1 + l1*l1;
inline uint4_t hi( uint8_t v ) { return v >> 4; }
inline uint4_t lo( uint8_t v ) { return v & 15; }
inline uint8_t LUT( uint4_t x, uint4_t y ) {
static uint8_t lut[256] = ...;
return lut[x | y << 4]
}
uint16_t multiply(uint8_t a, uint8_t b) {
return (uint16_t)LUT(hi(a), hi(b)) << 8 +
((uint16_t)LUT(hi(a), lo(b)) + (uint16_t)LUT(lo(a), hi(b)) << 4 +
(uint16_t)LUT(lo(a), lo(b));
}
simplemente llena lut [] con los resultados de la multiplicación. En su caso, dependiendo de la memoria, puede ir con quads (256 LUT) o con bytes (65536 tamaño LUT) o cualquier cosa entre
Estoy buscando un algoritmo para multiplicar dos números enteros que sea mejor que el siguiente. ¿Tienes una buena idea sobre eso? (La MCU - AT Tiny 84/85 o similar - donde se ejecuta este código no tiene operador mul / div)
uint16_t umul16_(uint16_t a, uint16_t b)
{
uint16_t res=0;
while (b) {
if ( (b & 1) )
res+=a;
b>>=1;
a+=a;
}
return res;
}
Este algoritmo, cuando se compila para AT Tiny 85/84 usando el compilador avr-gcc, es casi idéntico al algoritmo __mulhi3 que genera avr-gcc.
algoritmo avr-gcc:
00000106 <__mulhi3>:
106: 00 24 eor r0, r0
108: 55 27 eor r21, r21
10a: 04 c0 rjmp .+8 ; 0x114 <__mulhi3+0xe>
10c: 08 0e add r0, r24
10e: 59 1f adc r21, r25
110: 88 0f add r24, r24
112: 99 1f adc r25, r25
114: 00 97 sbiw r24, 0x00 ; 0
116: 29 f0 breq .+10 ; 0x122 <__mulhi3+0x1c>
118: 76 95 lsr r23
11a: 67 95 ror r22
11c: b8 f3 brcs .-18 ; 0x10c <__mulhi3+0x6>
11e: 71 05 cpc r23, r1
120: b9 f7 brne .-18 ; 0x110 <__mulhi3+0xa>
122: 80 2d mov r24, r0
124: 95 2f mov r25, r21
126: 08 95 ret
umul16_ algoritmo:
00000044 <umul16_>:
44: 20 e0 ldi r18, 0x00 ; 0
46: 30 e0 ldi r19, 0x00 ; 0
48: 61 15 cp r22, r1
4a: 71 05 cpc r23, r1
4c: 49 f0 breq .+18 ; 0x60 <umul16_+0x1c>
4e: 60 ff sbrs r22, 0
50: 02 c0 rjmp .+4 ; 0x56 <umul16_+0x12>
52: 28 0f add r18, r24
54: 39 1f adc r19, r25
56: 76 95 lsr r23
58: 67 95 ror r22
5a: 88 0f add r24, r24
5c: 99 1f adc r25, r25
5e: f4 cf rjmp .-24 ; 0x48 <umul16_+0x4>
60: c9 01 movw r24, r18
62: 08 95 ret Editar: El conjunto de instrucciones está disponible here .
El compilador podría producir un código más corto utilizando el operador ternario para elegir si agregar ''a'' a su acumulador, depende del costo de la prueba y la rama, y cómo su compilador genera código.
Intercambia los argumentos para reducir el conteo de bucles.
uint16_t umul16_(uint16_t op1, uint16_t op2)
{
uint16_t accum=0;
uint16_t a, b;
a=op1; b=op2;
if( op1<op2 ) { a=op2; b=0p1; } //swap operands to loop on smaller
while (b) {
accum += (b&1)?a:0;
b>>=1;
a+=a;
}
return accum;
}
Hace muchos años, escribí "sucesivamente", que promovía un enfoque de cálculo en lugar de ramificación, y eso sugiere elegir qué valor usar,
Puede usar una matriz para evitar la prueba por completo, lo que probablemente su compilador puede usar para generar una carga desde el desplazamiento. Defina una matriz que contenga dos valores, 0 y a, y actualice el valor de a al final del bucle,
uint16_t umul16_(uint16_t op1, uint16_t op2)
{
uint16_t accum=0;
uint16_t pick[2];
uint16_t a, b;
a=op1; b=op2;
if( op1<op2 ) { a=op2; b=0p1; } //swap operands to loop on smaller
pick[0]=0;
pick[1]=a;
while (b) {
accum += pick[(b&1)]; //avoid test completely
b>>=1;
pick[1] += pick[1]; //(a+=a);
}
return accum;
}
Si maldad Pero normalmente no escribo código así.
Editar: revisado para agregar swap a loop en el op1 u op2 más pequeño (menos pases). Eso eliminaría la utilidad de probar un argumento = 0.
Un enfoque es desenrollar el bucle. No tengo un compilador para la plataforma que está utilizando, por lo que no puedo ver el código generado, pero un enfoque como este podría ayudar.
El rendimiento de este código depende menos de los datos: usted va más rápido en el peor de los casos al no verificar si está en el mejor de los casos. El tamaño del código es un poco más grande, pero no el tamaño de una tabla de búsqueda.
(Anote el código que no se ha probado, en la parte superior de mi cabeza. ¡Tengo curiosidad sobre cómo se ve el código generado!)
#define UMUL16_STEP(a, b, shift) /
if ((b) & (1U << (shift))) result += ((a) << (shift)));
uint16_t umul16(uint16_t a, uint16_t b)
{
uint16_t result = 0;
UMUL16_STEP(a, b, 0);
UMUL16_STEP(a, b, 1);
UMUL16_STEP(a, b, 2);
UMUL16_STEP(a, b, 3);
UMUL16_STEP(a, b, 4);
UMUL16_STEP(a, b, 5);
UMUL16_STEP(a, b, 6);
UMUL16_STEP(a, b, 7);
UMUL16_STEP(a, b, 8);
UMUL16_STEP(a, b, 9);
UMUL16_STEP(a, b, 10);
UMUL16_STEP(a, b, 11);
UMUL16_STEP(a, b, 12);
UMUL16_STEP(a, b, 13);
UMUL16_STEP(a, b, 14);
UMUL16_STEP(a, b, 15);
return result;
}
Actualizar:
Dependiendo de lo que haga su compilador, la macro UMUL16_STEP puede cambiar. Una alternativa podría ser:
#define UMUL16_STEP(a, b, shift) /
if ((b) & (1U << (shift))) result += (a); (a) << 1;
Con este enfoque, el compilador podría utilizar la instrucción sbrc para evitar las ramas.
Supongo que el ensamblador debería verse por bit, r0: r1 es el resultado, r2: r3 es a y r4: r5 es b :
sbrc r4, 0
add r0, r2
sbrc r4, 0
addc r1, r3
lsl r2
rol r3
Esto debería ejecutarse en tiempo constante sin una rama. Pruebe los bits en r4 y luego pruebe los bits en r5 para los ocho bits más altos. Esto debería ejecutar la multiplicación en 96 ciclos según mi lectura del manual del conjunto de instrucciones.
Un ensamblador tinyARM ( documento web ) que no responde, en lugar de C ++ o C. Modifiqué multiply-by-squares-lookup bastante genérica de multiply-by-squares-lookup para la velocidad (<50 ciclos excluyendo los gastos generales de llamadas y devoluciones) al costo de solo encajar en los AVR con no menos que 1KByte de RAM, usando 512 bytes alineados para una tabla de la mitad inferior de los cuadrados. A 20 MHz, eso cumpliría bien con el límite de tiempo de 2 max 3 usec aún no aparece en la pregunta correcta, pero Sergio Formiggini quería 16 MHz. A partir de 2015/04, solo hay un ATtiny de Atmel con esa cantidad de RAM, y eso se especifica hasta 8 MHz ... (Rodando su "propio" (por ejemplo, desde OpenCores ), su FPGA probablemente tenga un montón de multiplicadores rápidos (18 × 18 bits parece popular), si no son núcleos de procesador.)
Para probar el rápido cambio y adición, eche un vistazo al cambio y agregue, desplace el factor hacia la izquierda, desenrolle 16 × 16 → 16 y / o mejore en él ( publicación de wiki ). (Podrías crear la respuesta de la wiki de la comunidad que se pide en la pregunta).
.def a0 = r16 ; factor low byte
.def a1 = r17
#warning two warnings about preceding definitions of
#warning r16 and r17 are due and may as well be ignored
.def a = r16 ; 8-bit factor
.def b = r17 ; 8-bit factor ; or r18, rather?
.def b0 = r18 ; factor low byte
.def b1 = r19
.def p0 = r20 ; product low byte
.def p1 = r21
; "squares table" SqTab shall be two 512 Byte tables of
; squares of 9-bit natural numbers, divided by 4
; Idea: exploit p = a * b = Squares[a+b] - Squares[a-b]
init:
ldi r16, 0x73
ldi r17, 0xab
ldi r18, 23
ldi r19, 1
ldi r20, HIGH(SRAM_SIZE)
cpi r20, 2
brsh fillSqTable ; ATtiny 1634?
rjmp mpy16T16
fillSqTable:
ldi r20, SqTabH
subi r20, -2
ldi zh, SqTabH
clr zl
; generate sqares by adding up odd numbers starting at 1 += -1
ldi r22, 1
clr r23
ser r26
ser r27
fillLoop:
add r22, r26
adc r23, r27
adiw r26, 2
mov r21, r23
lsr r21 ; get bits 9:2
mov r21, r22
ror r21
lsr r21
bst r23, 1
bld r21, 7
st z+, r21
cp zh, r20
brne fillLoop
rjmp mpy16F16
; assembly lines are marked up with cycle count
; and (latest) start cycle in block.
; If first line in code block, the (latest) block start cycle
; follows; else if last line, the (max) block cycle total
;**************************************************************
;*
;* "mpy16F16" - 16x16->16 Bit Unsigned Multiplication
;* using table lookup
;* Sergio Formiggini special edition
;* Multiplies two 16-bit register values a1:a0 and b1:b0.
;* The result is placed in p1:p0.
;*
;* Number of flash words: 318 + return =
;* (40 + 256(flash table) + 22(RAM init))
;* Number of cycles : 49 + return
;* Low registers used : None
;* High registers used : 7+2 (a1:a0, b1:b0, p1:p0, sq;
;* + Z(r31:r30))
;* RAM bytes used : 512 (squares table)
;*
;**************************************************************
mpy16F16:
ldi ZH, SqTabH>>1;1 0 0 squares table>>1
mov ZL, a0 ; 1 1
add ZL, b0 ; 1 2 a0+b0
rol ZH ; 1 3 9 bit offset
ld p0, Z ; 2 4 a0+b0l 1
lpm p1, Z ; 3 6 9 a0+b0h 2
ldi ZH, SqTabH ; 1 0 9 squares table
mov ZL, a1 ; 1 0 10
sub ZL, b0 ; 1 1 a1-b0
brcc noNegF10 ; 1 2
neg ZL ; 1 3
noNegF10:
ld sq, Z ; 2 4 a1-b0l 3
sub p1, sq ; 1 6 7
mov ZL, a0 ; 1 0 17
sub ZL, b1 ; 1 1 a0-b1
brcc noNegF01 ; 1 2
neg ZL ; 1 3
noNegF01:
ld sq, Z ; 2 4 a0-b1l 4
sub p1, sq ; 1 6 7
mov ZL, a0 ; 1 0 24
sub ZL, b0 ; 1 1 a0-b0
brcc noNegF00 ; 1 2
neg ZL ; 1 3
noNegF00:
ld sq, Z ; 2 4 a0-b0l 5
sub p0, sq ; 1 6
lpm sq, Z ; 3 7 a0-b0h 6*
sbc p1, sq ; 1 10 11
ldi ZH, SqTabH>>1;1 0 35
mov ZL, a1 ; 1 1
add ZL, b0 ; 1 2 a1+b0
rol ZH ; 1 3
ld sq, Z ; 2 4 a1+b0l 7
add p1, sq ; 1 6 7
ldi ZH, SqTabH>>1;1 0 42
mov ZL, a0 ; 1 1
add ZL, b1 ; 1 2 a0+b1
rol ZH ; 1 3
ld sq, Z ; 2 4 a0+b1l 8
add p1, sq ; 1 6 7
ret ; 49
.CSEG
.org 256; words?!
SqTableH:
.db 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
.db 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
.db 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
.db 0, 0, 1, 1, 1, 1, 1, 1, 1, 1
.db 1, 1, 1, 1, 1, 1, 2, 2, 2, 2
.db 2, 2, 2, 2, 2, 2, 3, 3, 3, 3
.db 3, 3, 3, 3, 4, 4, 4, 4, 4, 4
.db 4, 4, 5, 5, 5, 5, 5, 5, 5, 6
.db 6, 6, 6, 6, 6, 7, 7, 7, 7, 7
.db 7, 8, 8, 8, 8, 8, 9, 9, 9, 9
.db 9, 9, 10, 10, 10, 10, 10, 11, 11, 11
.db 11, 12, 12, 12, 12, 12, 13, 13, 13, 13
.db 14, 14, 14, 14, 15, 15, 15, 15, 16, 16
.db 16, 16, 17, 17, 17, 17, 18, 18, 18, 18
.db 19, 19, 19, 19, 20, 20, 20, 21, 21, 21
.db 21, 22, 22, 22, 23, 23, 23, 24, 24, 24
.db 25, 25, 25, 25, 26, 26, 26, 27, 27, 27
.db 28, 28, 28, 29, 29, 29, 30, 30, 30, 31
.db 31, 31, 32, 32, 33, 33, 33, 34, 34, 34
.db 35, 35, 36, 36, 36, 37, 37, 37, 38, 38
.db 39, 39, 39, 40, 40, 41, 41, 41, 42, 42
.db 43, 43, 43, 44, 44, 45, 45, 45, 46, 46
.db 47, 47, 48, 48, 49, 49, 49, 50, 50, 51
.db 51, 52, 52, 53, 53, 53, 54, 54, 55, 55
.db 56, 56, 57, 57, 58, 58, 59, 59, 60, 60
.db 61, 61, 62, 62, 63, 63, 64, 64, 65, 65
.db 66, 66, 67, 67, 68, 68, 69, 69, 70, 70
.db 71, 71, 72, 72, 73, 73, 74, 74, 75, 76
.db 76, 77, 77, 78, 78, 79, 79, 80, 81, 81
.db 82, 82, 83, 83, 84, 84, 85, 86, 86, 87
.db 87, 88, 89, 89, 90, 90, 91, 92, 92, 93
.db 93, 94, 95, 95, 96, 96, 97, 98, 98, 99
.db 100, 100, 101, 101, 102, 103, 103, 104, 105, 105
.db 106, 106, 107, 108, 108, 109, 110, 110, 111, 112
.db 112, 113, 114, 114, 115, 116, 116, 117, 118, 118
.db 119, 120, 121, 121, 122, 123, 123, 124, 125, 125
.db 126, 127, 127, 128, 129, 130, 130, 131, 132, 132
.db 133, 134, 135, 135, 136, 137, 138, 138, 139, 140
.db 141, 141, 142, 143, 144, 144, 145, 146, 147, 147
.db 148, 149, 150, 150, 151, 152, 153, 153, 154, 155
.db 156, 157, 157, 158, 159, 160, 160, 161, 162, 163
.db 164, 164, 165, 166, 167, 168, 169, 169, 170, 171
.db 172, 173, 173, 174, 175, 176, 177, 178, 178, 179
.db 180, 181, 182, 183, 183, 184, 185, 186, 187, 188
.db 189, 189, 190, 191, 192, 193, 194, 195, 196, 196
.db 197, 198, 199, 200, 201, 202, 203, 203, 204, 205
.db 206, 207, 208, 209, 210, 211, 212, 212, 213, 214
.db 215, 216, 217, 218, 219, 220, 221, 222, 223, 224
.db 225, 225, 226, 227, 228, 229, 230, 231, 232, 233
.db 234, 235, 236, 237, 238, 239, 240, 241, 242, 243
.db 244, 245, 246, 247, 248, 249, 250, 251, 252, 253
.db 254, 255
; word addresses, again?!
.equ SqTabH = (high(SqTableH) << 1)
.DSEG
RAMTab .BYTE 512
Resumen
- Considere intercambiar
ayb(propuesta original) - Tratando de evitar saltos condicionales (Optimización no exitosa)
- Reformado de la fórmula de entrada (ganancia estimada del 35%)
- Eliminando turnos duplicados
- Desenrollando el bucle: el montaje "óptimo"
- Convenciendo al compilador para dar el montaje óptimo.
a y b Una mejora sería primero comparar a y b, e intercambiarlos si a<b : debe usar como b el más pequeño de los dos, de modo que tenga el número mínimo de ciclos. Tenga en cuenta que puede evitar el intercambio duplicando el código ( if (a<b) luego salte a una sección de código duplicado), pero dudo que valga la pena.
Tratar:
uint16_t umul16_(uint16_t a, uint16_t b)
{
///Here swap if necessary
uint16_t accum=0;
while (b) {
accum += ((b&1) * uint16_t(0xffff)) & a; //Hopefully this multiplication is optimized away
b>>=1;
a+=a;
}
return accum;
}
De los comentarios de Sergio, esto no trajo mejoras.
3. Remodelación de la fórmula de entrada.Teniendo en cuenta que la arquitectura de destino tiene básicamente solo instrucciones de 8 bits, si separa los 8 bits superior e inferior de las variables de entrada, puede escribir:
a = a1 * 0xff + a0;
b = b1 * 0xff + b0;
a * b = a1 * b1 * 0xffff + a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0
Ahora, lo bueno es que podemos deshacernos del término a1 * b1 * 0xffff , porque 0xffff envía fuera de su registro .
(16bit) a * b = a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0
Además, el término a0*b1 y a1*b0 se puede tratar como multiplicaciones de 8 bits, debido al 0xff : cualquier parte que exceda de 256 se enviará fuera del registro .
¡Hasta ahora emocionante! ... Pero, aquí llega la realidad: a0 * b0 debe tratarse como una multiplicación de 16 bits, ya que deberá mantener todos los bits resultantes. a0 tendrá que mantenerse en 16 bits para permitir turnos de turno. Esta multiplicación tiene la mitad de las iteraciones de a * b , está en la parte 8bit (debido a b0), pero aún debe tener en cuenta las multiplicaciones de 2 8bit mencionadas anteriormente y la composición del resultado final. ¡Necesitamos más remodelación!
Así que ahora colecciono b0 .
(16bit) a * b = a0 * b1 * 0xff + b0 * (a0 + a1 * 0xff)
Pero
(a0 + a1 * 0xff) = a
Así obtenemos:
(16bit) a * b = a0 * b1 * 0xff + b0 * a
Si N eran los ciclos del original a * b , ahora el primer término es una multiplicación de 8 bits con N / 2 ciclos, y el segundo una multiplicación de 16 bits * 8 bits con N / 2 ciclos. Considerando M el número de instrucciones por iteración en el original a*b , la iteración de 8bit * 8bit tiene la mitad de las instrucciones, y el 16bit * 8bit aproximadamente el 80% de M (una instrucción de cambio menos para b0 en comparación con b). En conjunto, tenemos una complejidad N/2*M/2+N/2*M*0.8 = N*M*0.65 , por lo que se espera un ahorro de ~ 35% con respecto a la N*M original. Suena prometedor .
Este es el código:
uint16_t umul16_(uint16_t a, uint16_t b)
{
uint8_t res1 = 0;
uint8_t a0 = a & 0xff; //This effectively needs to copy the data
uint8_t b0 = b & 0xff; //This should be optimized away
uint8_t b1 = b >>8; //This should be optimized away
//Here a0 and b1 could be swapped (to have b1 < a0)
while (b1) {///Maximum 8 cycles
if ( (b1 & 1) )
res1+=a0;
b1>>=1;
a0+=a0;
}
uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it''s not even a copy!
//Here swapping wouldn''t make much sense
while (b0) {///Maximum 8 cycles
if ( (b0 & 1) )
res+=a;
b0>>=1;
a+=a;
}
return res;
}
Además, la división en 2 ciclos debería duplicar, en teoría, la posibilidad de saltear algunos ciclos: N / 2 podría ser una ligera sobreestimación.
Una pequeña mejora adicional consiste en evitar el último cambio innecesario para las variables. Nota al margen pequeña: si b0 o b1 son cero, esto causa 2 instrucciones adicionales. Pero también guarda la primera comprobación de b0 y b1, que es la más costosa porque no puede verificar el estado del zero flag de la operación de cambio para el salto condicional del bucle for.
uint16_t umul16_(uint16_t a, uint16_t b)
{
uint8_t res1 = 0;
uint8_t a0 = a & 0xff; //This effectively needs to copy the data
uint8_t b0 = b & 0xff; //This should be optimized away
uint8_t b1 = b >>8; //This should be optimized away
//Here a0 and b1 could be swapped (to have b1 < a0)
if ( (b1 & 1) )
res1+=a0;
b1>>=1;
while (b1) {///Maximum 7 cycles
a0+=a0;
if ( (b1 & 1) )
res1+=a0;
b1>>=1;
}
uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it''s not even a copy!
//Here swapping wouldn''t make much sense
if ( (b0 & 1) )
res+=a;
b0>>=1;
while (b0) {///Maximum 7 cycles
a+=a;
if ( (b0 & 1) )
res+=a;
b0>>=1;
}
return res;
} 4. Eliminando turnos duplicados
¿Todavía hay espacio para mejorar? Sí , ya que los bytes en a0 se desplazan dos veces . Así que debería haber un beneficio en la combinación de los dos bucles. Puede ser un poco difícil convencer al compilador de que haga exactamente lo que queremos, especialmente con el registro de resultados.
Entonces, procesamos en el mismo ciclo b0 y b1 . Lo primero que se debe manejar es, ¿cuál es la condición de salida del bucle? Hasta ahora, usar el estado de b0 / b1 borrado ha sido conveniente porque evita el uso de un contador. Además, después del cambio a la derecha, es posible que ya se haya establecido un indicador si el resultado de la operación es cero, y este indicador podría permitir un salto condicional sin más evaluaciones.
Ahora la condición de salida del bucle podría ser la falla de (b0 || b1) . Sin embargo, esto podría requerir costosos cálculos. Una solución es comparar b0 y b1 y saltar a 2 secciones de código diferentes: si b1 > b0 la condición en b1 , de lo contrario, b1 la condición en b0 . Prefiero otra solución, con 2 bucles, la primera salida cuando b0 es cero, la segunda cuando b1 es cero. Habrá casos en los que haré cero iteraciones en b1 . El punto es que en el segundo bucle sé que b0 es cero, por lo que puedo reducir el número de operaciones realizadas.
Ahora, olvidemos la condición de salida e intentemos unir los 2 bucles de la sección anterior.
uint16_t umul16_(uint16_t a, uint16_t b)
{
uint16_t res = 0;
uint8_t b0 = b & 0xff; //This should be optimized away
uint8_t b1 = b >>8; //This should be optimized away
//Swapping probably doesn''t make much sense anymore
if ( (b1 & 1) )
res+=(uint16_t)((uint8_t)(a && 0xff))*256;
//Hopefully the compiler understands it has simply to add the low 8bit register of a to the high 8bit register of res
if ( (b0 & 1) )
res+=a;
b1>>=1;
b0>>=1;
while (b0) {///N cycles, maximum 7
a+=a;
if ( (b1 & 1) )
res+=(uint16_t)((uint8_t)(a & 0xff))*256;
if ( (b0 & 1) )
res+=a;
b1>>=1;
b0>>=1; //I try to put as last the one that will leave the carry flag in the desired state
}
uint8_t a0 = a & 0xff; //Again, not a real copy but a register selection
while (b1) {///P cycles, maximum 7 - N cycles
a0+=a0;
if ( (b1 & 1) )
res+=(uint16_t) a0 * 256;
b1>>=1;
}
return res;
}
Gracias Sergio por proporcionar el ensamblaje generado (-Frast). A primera vista, teniendo en cuenta la escandalosa cantidad de mov en el código, parece que el compilador no interpretó, ya que quería que las sugerencias que le di para interpretar los registros.
Las entradas son: r22, r23 y r24,25.
Conjunto de instrucciones AVR: here , documentación detallada
sbrs //Tests a single bit in a register and skips the next instruction if the bit is set. Skip takes 2 clocks.
ldi // Load immediate, 1 clock
sbiw // Subtracts immediate to *word*, 2 clocks
00000010 <umul16_Antonio5>:
10: 70 ff sbrs r23, 0
12: 39 c0 rjmp .+114 ; 0x86 <__SREG__+0x47>
14: 41 e0 ldi r20, 0x01 ; 1
16: 00 97 sbiw r24, 0x00 ; 0
18: c9 f1 breq .+114 ; 0x8c <__SREG__+0x4d>
1a: 34 2f mov r19, r20
1c: 20 e0 ldi r18, 0x00 ; 0
1e: 60 ff sbrs r22, 0
20: 07 c0 rjmp .+14 ; 0x30 <umul16_Antonio5+0x20>
22: 28 0f add r18, r24
24: 39 1f adc r19, r25
26: 04 c0 rjmp .+8 ; 0x30 <umul16_Antonio5+0x20>
28: e4 2f mov r30, r20
2a: 45 2f mov r20, r21
2c: 2e 2f mov r18, r30
2e: 34 2f mov r19, r20
30: 76 95 lsr r23
32: 66 95 lsr r22
34: b9 f0 breq .+46 ; 0x64 <__SREG__+0x25>
36: 88 0f add r24, r24
38: 99 1f adc r25, r25
3a: 58 2f mov r21, r24
3c: 44 27 eor r20, r20
3e: 42 0f add r20, r18
40: 53 1f adc r21, r19
42: 70 ff sbrs r23, 0
44: 02 c0 rjmp .+4 ; 0x4a <__SREG__+0xb>
46: 24 2f mov r18, r20
48: 35 2f mov r19, r21
4a: 42 2f mov r20, r18
4c: 53 2f mov r21, r19
4e: 48 0f add r20, r24
50: 59 1f adc r21, r25
52: 60 fd sbrc r22, 0
54: e9 cf rjmp .-46 ; 0x28 <umul16_Antonio5+0x18>
56: e2 2f mov r30, r18
58: 43 2f mov r20, r19
5a: e8 cf rjmp .-48 ; 0x2c <umul16_Antonio5+0x1c>
5c: 95 2f mov r25, r21
5e: 24 2f mov r18, r20
60: 39 2f mov r19, r25
62: 76 95 lsr r23
64: 77 23 and r23, r23
66: 61 f0 breq .+24 ; 0x80 <__SREG__+0x41>
68: 88 0f add r24, r24
6a: 48 2f mov r20, r24
6c: 50 e0 ldi r21, 0x00 ; 0
6e: 54 2f mov r21, r20
70: 44 27 eor r20, r20
72: 42 0f add r20, r18
74: 53 1f adc r21, r19
76: 70 fd sbrc r23, 0
78: f1 cf rjmp .-30 ; 0x5c <__SREG__+0x1d>
7a: 42 2f mov r20, r18
7c: 93 2f mov r25, r19
7e: ef cf rjmp .-34 ; 0x5e <__SREG__+0x1f>
80: 82 2f mov r24, r18
82: 93 2f mov r25, r19
84: 08 95 ret
86: 20 e0 ldi r18, 0x00 ; 0
88: 30 e0 ldi r19, 0x00 ; 0
8a: c9 cf rjmp .-110 ; 0x1e <umul16_Antonio5+0xe>
8c: 40 e0 ldi r20, 0x00 ; 0
8e: c5 cf rjmp .-118 ; 0x1a <umul16_Antonio5+0xa> 5. Desenrollar el bucle: el ensamblaje "óptimo"
Con toda esta información, intentemos comprender cuál sería la solución "óptima" dadas las restricciones de la arquitectura. "Óptimo" se cita porque lo que es "óptimo" depende mucho de los datos de entrada y de lo que queremos optimizar. Supongamos que queremos optimizar el número de ciclos en el peor de los casos . Si vamos por el peor de los casos, el desenrollado de bucle es una opción razonable: sabemos que tenemos 8 ciclos, y eliminamos todas las pruebas para comprender si terminamos (si b0 y b1 son cero). Hasta ahora utilizamos el truco "cambiamos, y comprobamos el indicador cero" para comprobar si tuvimos que salir de un bucle. Eliminado este requisito, podemos usar un truco diferente: cambiamos, y verificamos el bit de acarreo (el bit que enviamos fuera del registro al cambiar) para comprender si debo actualizar el resultado . Dado el conjunto de instrucciones, en el código "narrativo" del ensamblaje, las instrucciones se convierten en las siguientes.
//Input: a = a1 * 256 + a0, b = b1 * 256 + b0
//Output: r = r1 * 256 + r0
Preliminary:
P0 r0 = 0 (CLR)
P1 r1 = 0 (CLR)
Main block:
0 Shift right b0 (LSR)
1 If carry is not set skip 2 instructions = jump to 4 (BRCC)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Shift right b1 (LSR)
5 If carry is not set skip 1 instruction = jump to 7 (BRCC)
6 r1 = r1 + a0 (ADD)
7 a0 = a0 + a0 (ADD)
8 a1 = a1 + a1 + carry from prev. (ADC)
[Repeat same instructions for another 7 times]
La bifurcación toma 1 instrucción si no se produce ningún salto, 2 de lo contrario. Todas las demás instrucciones son de 1 ciclo. Entonces, el estado b1 no tiene influencia en el número de ciclos, mientras que tenemos 9 ciclos si b0 = 1, y 8 ciclos si b0 = 0. Contando la inicialización, 8 iteraciones y saltando la última actualización de a0 y a1, en el peor de los casos (b0 = 11111111b), tenemos un total de 8 * 9 + 2 - 2 = 72 ciclos . No sabría qué implementación de C ++ convencería al compilador para que la genere. Tal vez:
void iterate(uint8_t& b0,uint8_t& b1,uint16_t& a, uint16_t& r) {
const uint8_t temp0 = b0;
b0 >>=1;
if (temp0 & 0x01) {//Will this convince him to use the carry flag?
r += a;
}
const uint8_t temp1 = b1;
b1 >>=1;
if (temp1 & 0x01) {
r+=(uint16_t)((uint8_t)(a & 0xff))*256;
}
a += a;
}
uint16_t umul16_(uint16_t a, uint16_t b) {
uint16_t r = 0;
uint8_t b0 = b & 0xff;
uint8_t b1 = b >>8;
iterate(b0,b1,a,r);
iterate(b0,b1,a,r);
iterate(b0,b1,a,r);
iterate(b0,b1,a,r);
iterate(b0,b1,a,r);
iterate(b0,b1,a,r);
iterate(b0,b1,a,r);
iterate(b0,b1,a,r); //Hopefully he understands he doesn''t need the last update for variable a
return r;
}
Pero, dado el resultado anterior, para obtener realmente el código deseado, ¡realmente se debe cambiar al ensamblaje!
Finalmente, también se podría considerar una interpretación más extrema del desenrollado del bucle: las instrucciones sbrc / sbrs permiten probar en un bit específico de un registro. Por lo tanto, podemos evitar desplazar b0 y b1, y en cada ciclo verificar un bit diferente. El único problema es que esas instrucciones solo permiten omitir la siguiente instrucción, y no para un salto personalizado. Entonces, en el "código narrativo" se verá así:
Main block:
0 Test Nth bit of b0 (SBRS). If set jump to 2 (+ 1cycle) otherwise continue with 1
1 Jump to 4 (RJMP)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Test Nth bit of (SBRC). If cleared jump to 6 (+ 1cycle) otherwise continue with 5
5 r1 = r1 + a0 (ADD)
6 a0 = a0 + a0 (ADD)
7 a1 = a1 + a1 + carry from prev. (ADC)
Mientras que la segunda sustitución permite ahorrar 1 ciclo, no hay una ventaja clara en la segunda sustitución. Sin embargo, creo que el código C ++ podría ser más fácil de interpretar para el compilador. Considerando 8 ciclos, la inicialización y la omisión de la última actualización de a0 y a1, ahora tenemos 64 ciclos .
Código C ++:
template<uint8_t mask>
void iterateWithMask(const uint8_t& b0,const uint8_t& b1, uint16_t& a, uint16_t& r) {
if (b0 & mask)
r += a;
if (b1 & mask)
r+=(uint16_t)((uint8_t)(a & 0xff))*256;
a += a;
}
uint16_t umul16_(uint16_t a, const uint16_t b) {
uint16_t r = 0;
const uint8_t b0 = b & 0xff;
const uint8_t b1 = b >>8;
iterateWithMask<0x01>(b0,b1,a,r);
iterateWithMask<0x02>(b0,b1,a,r);
iterateWithMask<0x04>(b0,b1,a,r);
iterateWithMask<0x08>(b0,b1,a,r);
iterateWithMask<0x10>(b0,b1,a,r);
iterateWithMask<0x20>(b0,b1,a,r);
iterateWithMask<0x40>(b0,b1,a,r);
iterateWithMask<0x80>(b0,b1,a,r);
//Hopefully he understands he doesn''t need the last update for a
return r;
}
Tenga en cuenta que en esta implementación, 0x01, 0x02 no son un valor real, sino solo una sugerencia al compilador para saber qué bit probar. Por lo tanto, la máscara no se puede obtener desplazándose a la derecha: a diferencia de todas las demás funciones que se han visto hasta ahora, esta no tiene realmente una versión de bucle equivalente.
Un gran problema es que
r+=(uint16_t)((uint8_t)(a & 0xff))*256;
Debe ser solo una suma del registro superior de r con el registro inferior de a . No se interpreta como quisiera. Otra opción:
r+=(uint16_t) 256 *((uint8_t)(a & 0xff)); 6. Convencer al compilador para dar el montaje óptimo.
También podemos mantener a constante y, en cambio, cambiar el resultado r . En este caso procesamos b partir del bit más significativo. La complejidad es equivalente, pero podría ser más fácil de digerir para el compilador. Además, esta vez tenemos que tener cuidado de escribir explícitamente el último bucle, que no debe hacer un cambio adicional hacia la derecha para r .
template<uint8_t mask>
void inverseIterateWithMask(const uint8_t& b0,const uint8_t& b1,const uint16_t& a, const uint8_t& a0, uint16_t& r) {
if (b0 & mask)
r += a;
if (b1 & mask)
r+=(uint16_t)256*a0; //Hopefully easier to understand for the compiler?
r += r;
}
uint16_t umul16_(const uint16_t a, const uint16_t b) {
uint16_t r = 0;
const uint8_t b0 = b & 0xff;
const uint8_t b1 = b >>8;
const uint8_t a0 = a & 0xff;
inverseIterateWithMask<0x80>(b0,b1,a,r);
inverseIterateWithMask<0x40>(b0,b1,a,r);
inverseIterateWithMask<0x20>(b0,b1,a,r);
inverseIterateWithMask<0x10>(b0,b1,a,r);
inverseIterateWithMask<0x08>(b0,b1,a,r);
inverseIterateWithMask<0x04>(b0,b1,a,r);
inverseIterateWithMask<0x02>(b0,b1,a,r);
//Last iteration:
if (b0 & 0x01)
r += a;
if (b1 & 0x01)
r+=(uint16_t)256*a0;
return r;
}
Por fin, una respuesta, si es descarada: no pude (todavía) obtener el compilador AVR-C del GCC, encajarlo en el código 8K. (Para una copia de ensamblador, vea Multiplicación de AVR: No Holds Barred ).
El enfoque es lo que todos los que usaron el dispositivo de Duff intentaron un segundo intento:
usar un interruptor. Usando macros, el código fuente parece completamente inofensivo, si se realiza un masaje:
#define low(mp) case mp: p = a0 * (uint8_t)(mp) << 8; break
#define low4(mp) low(mp); low(mp + 1); low(mp + 2); low(mp + 3)
#define low16(mp) low4(mp); low4(mp + 4); low4(mp + 8); low4(mp + 12)
#define low64(mp) low16(mp); low16(mp + 16); low16(mp + 32); low16(mp + 48)
#if preShift
# define CASE(mp) case mp: return p + a * (mp)
#else
# define CASE(mp) case mp: return (p0<<8) + a * (mp)
#endif
#define case4(mp) CASE(mp); CASE(mp + 1); CASE(mp + 2); CASE(mp + 3)
#define case16(mp) case4(mp); case4(mp + 4); case4(mp + 8); case4(mp + 12)
#define case64(mp) case16(mp); case16(mp + 16); case16(mp + 32); case16(mp + 48)
extern "C" __attribute__ ((noinline))
uint16_t mpy16NHB16(uint16_t a, uint16_t b)
{
uint16_t p = 0;
uint8_t b0 = (uint8_t)b, b1 = (uint8_t)(b>>8);
uint8_t a0 = (uint8_t)a, p0;
switch (b1) {
case64(0);
case64(64);
case64(128);
case64(192);
}
#if preShift
p = p0 << 8;
#endif
#if preliminaries
if (0 == b0) {
p = -a;
if (b & 0x8000)
p += a << 9;
if (b & 0x4000)
p += a << 8;
return p;
}
while (b0 & 1) {
a <<= 1;
b0 >>= 1;
}
#endif
switch (b0) {
low64(0);
low64(64);
low64(128);
low64(192);
}
return ~0;
}
int main(int ac, char const *const av[])
{
char buf[22];
for (uint16_t a = 0 ; a < a+1 ; a++)
for (uint16_t m = 0 ; m <= a ; m++)
puts(itoa(//shift4(ac)+shift3MaskAdd((uint16_t)av[0], ac)
// +shift4Add(ac, (uint16_t)av[0])
// + mpy16NHB16(ac, (ac + 105))
mpy16NHB16(a, m), buf, 10));
}