assembly - Lenguaje ensamblador(x86): cómo crear un bucle para calcular la secuencia de Fibonacci

masm irvine32

Question

Estoy programando lenguaje ensamblador (x86) en MASM usando Visual Studio 2013 Ultimate. Estoy tratando de usar una matriz para calcular una secuencia de Fibonacci para n elementos usando una matriz. En otras palabras, estoy tratando de ir a un elemento de matriz, obtener los dos elementos anteriores, sumarlos y almacenar el resultado en otra matriz.

Tengo problemas para configurar los registros de índice para que esto funcione.

Tengo la configuración de mi programa así:

TITLE fibonacci.asm
INCLUDE Irvine32.inc
.data
fibInitial BYTE 0, 1, 2, 3, 4, 5, 6
fibComputed BYTE 5 DUP(0)
.code
main PROC
MOVZX si, fibInitial
MOVZX di, fibComputed
MOV cl, LENGTHOF fibInitial
L1:
MOV ax, [si - 1]
MOV dx, [si - 2]
MOV bp, ax + dx
MOV dl, TYPE fibInitial
MOVZX si, dl
MOV [edi], bp
MOV dh, TYPE fibComputed
MOVZX di, dl
loop L1
exit
main ENDP
END main

No puedo compilar esto debido a un mensaje de error que dice "error A2031: debe ser índice o registro base" para la línea MOV ebp, ax + dx . Sin embargo, estoy seguro de que hay otros errores lógicos que estoy pasando por alto.

Answer 1

Teniendo en cuenta que fib (93) = 12200160415121876738 es el valor más grande que cabe en un entero sin signo de 64 bits, puede que no tenga mucho sentido tratar de optimizar esto, a menos que se calcule un módulo de fib (n) algún número (generalmente primo) para n grande .

Hay una manera de calcular directamente fib (n) en las iteraciones log2 (n), utilizando un método de secuencia de lucas o un método de matriz para fibonacci. La secuencia de lucas es más rápida y se muestra a continuación. Estos podrían modificarse para realizar el módulo matemático algún número.

/* lucas sequence method */
uint64_t fibl(int n) {
uint64_t a, b, p, q, qq, aq;
a = q = 1;
b = p = 0;
while(1){
if(n & 1) {
aq = a*q;
a = b*q + aq + a*p;
b = b*p + aq;
}
n >>= 1;
if(n == 0)
break;
qq = q*q;
q = 2*p*q + qq;
p = p*p + qq;
}
return b;
}

Answer 2

relacionado: Code-golf imprime los primeros 1000 dígitos de Fib (10 ** 9): mi respuesta asm x86 utiliza un bucle adc precisión extendida y convierte binarios en cadenas. El bucle interno está optimizado para la velocidad, otras partes para el tamaño.

Calcular una secuencia de Fibonacci solo requiere mantener dos partes de estado: el elemento actual y el anterior. No tengo idea de lo que está tratando de hacer con fibInitial , aparte de contar su longitud. Esto no es perl donde lo haces for $n (0..5) .

Sé que solo estás aprendiendo asm, pero todavía voy a hablar sobre el rendimiento. No hay muchas razones para aprender asm sin saber qué es rápido y qué no . Si no necesita rendimiento, deje que un compilador haga el asm por usted, de fuentes C. Consulte también los otros enlaces en https://.com/tags/x86/info

El uso de registros para su estado simplifica el problema de tener que mirar a[-1] al calcular a[1] . Empiezas con curr=1 , prev=0 , y comienzas con a[0] = curr . Para producir la secuencia "moderna" que comienza con cero de los números de Fibonacci , comience con curr=0 , prev=1 .

Afortunadamente para ti, estaba pensando en un bucle eficiente para el código de Fibonacci recientemente, así que me tomé el tiempo para escribir una función completa. Vea a continuación una versión desenrollada y una vectorizada (guarda las instrucciones de la tienda, pero también hace que los 64 bits sean rápidos incluso cuando se compila para una CPU de 32 bits):

; fib.asm
;void fib(int32_t *dest, uint32_t count);
; not-unrolled version. See below for a version which avoids all the mov instructions
global fib
fib:
; 64bit SysV register-call ABI:
; args: rdi: output buffer pointer. esi: count (and you can assume the upper32 are zeroed, so using rsi is safe)
;; locals: rsi: endp
;; eax: current edx: prev
;; ecx: tmp
;; all of these are caller-saved in the SysV ABI, like r8-r11
;; so we can use them without push/pop to save/restore them.
;; The Windows ABI is different.
test esi, esi ; test a reg against itself instead of cmp esi, 0
jz .early_out ; count == 0.
mov eax, 1 ; current = 1
xor edx, edx ; prev = 0
lea rsi, [rdi + rsi * 4] ; endp = &out[count]; // loop-end pointer
;; lea is very useful for combining add, shift, and non-destructive operation
;; this is equivalent to shl rsi, 4 / add rsi, rdi
align 16
.loop: ; do {
mov [rdi], eax ; *buf = current
add rdi, 4 ; buf++
lea ecx, [rax + rdx] ; tmp = curr+prev = next_cur
mov edx, eax ; prev = curr
mov eax, ecx ; curr=tmp
;; see below for an unrolled version that doesn''t need any reg->reg mov instructions
; you might think this would be faster:
; add edx, eax ; but it isn''t
; xchg eax, edx ; This is as slow as 3 mov instructions, but we only needed 2 thanks to using lea
cmp rdi, rsi ; } while(buf < endp);
jb .loop ; jump if (rdi BELOW rsi). unsigned compare
;; the LOOP instruction is very slow, avoid it
.early_out:
ret

Una condición de bucle alternativo podría ser

 dec esi ; often you''d use ecx for counts, but we had it in esi
jnz .loop

Las CPU AMD pueden fusionar cmp / branch, pero no dec / branch. Las CPU Intel también pueden macro-fuse dec/jnz . (O con signo menor que cero / mayor que cero). dec/inc no actualiza el indicador Carry, por lo que no puede usarlos con ja/jb sin firmar arriba / abajo. Creo que la idea es que podría hacer un adc (agregar con carry) en un bucle, usando inc/dec para que el contador de bucle no altere el indicador de acarreo, pero la desaceleración de los indicadores parciales hace que esto sea malo en las CPU modernas .

lea ecx, [eax + edx] necesita un byte adicional (prefijo de tamaño de dirección), por eso utilicé un destino de 32 bits y una dirección de 64 bits. (Esos son los tamaños de operando predeterminados para lea en modo de 64 bits). Sin impacto directo en la velocidad, solo indirecto a través del tamaño del código.

Un cuerpo de bucle alternativo podría ser:

 mov ecx, eax ; tmp=curr. This stays true after every iteration
.loop:
mov [rdi], ecx
add ecx, edx ; tmp+=prev ;; shorter encoding than lea
mov edx, eax ; prev=curr
mov eax, ecx ; curr=tmp

Desenrollar el bucle para hacer más iteraciones significaría menos barajado. En lugar de instrucciones mov , simplemente realiza un seguimiento de qué registro contiene qué variable. es decir, maneja las tareas con una especie de cambio de nombre de registro.

.loop: ;; on entry: ; curr:eax prev:edx
mov [rdi], eax ; store curr
add edx, eax ; curr:edx prev:eax
.oddentry:
mov [rdi + 4], edx ; store curr
add eax, edx ; curr:eax prev:edx
;; we''re back to our starting state, so we can loop
add rdi, 8
cmp rdi, rsi
jb .loop

Lo que ocurre con el desenrollado es que necesita limpiar las iteraciones extrañas que quedan. Los factores de desenrollamiento de potencia de dos pueden hacer que el ciclo de limpieza sea un poco más fácil, pero agregar 12 no es más rápido que agregar 16. (Vea la revisión anterior de esta publicación para una versión tonta de desenrollar por 3 usando lea para producir curr + prev en un tercer registro, porque no me di cuenta de que realmente no necesitas una temperatura. Gracias a rcgldr por atrapar eso).

Vea a continuación una versión completa y desenrollada que funciona y que maneja cualquier conteo.

Interfaz de prueba (nuevo en esta versión: un elemento canario para detectar errores de asm que se escriben más allá del final del búfer).

// fib-main.c
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
void fib(uint32_t *buf, uint32_t count);
int main(int argc, const char *argv[]) {
uint32_t count = 15;
if (argc > 1) {
count = atoi(argv[1]);
}
uint32_t buf[count+1]; // allocated on the stack
// Fib overflows uint32 at count = 48, so it''s not like a lot of space is useful
buf[count] = 0xdeadbeefUL;
// uint32_t count = sizeof(buf)/sizeof(buf[0]);
fib(buf, count);
for (uint32_t i ; i < count ; i++){
printf("%u ", buf[i]);
}
putchar(''/n'');
if (buf[count] != 0xdeadbeefUL) {
printf("fib wrote past the end of buf: sentinel = %x/n", buf[count]);
}
}

Este código funciona y se prueba por completo (a menos que no haya copiado un cambio en mi archivo local de nuevo en la respuesta>. <):

peter@tesla:~/src/SO$ yasm -f elf64 fib.asm && gcc -std=gnu11 -g -Og fib-main.c fib.o
peter@tesla:~/src/SO$ ./a.out 48
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 512559680

versión desenrollada

Gracias de nuevo a rcgldr por hacerme pensar en cómo manejar el conteo impar y el par en la configuración del bucle, en lugar de con una iteración de limpieza al final.

Fui por el código de configuración sin ramas, que agrega 4 * recuento% 2 al puntero de inicio. Eso puede ser cero, pero agregar cero es más barato que ramificar para ver si deberíamos o no. La secuencia de Fibonacci desborda un registro muy rápidamente, por lo que es importante mantener el código de prólogo ajustado y eficiente, no solo el código dentro del bucle. (Si estamos optimizando en absoluto, nos gustaría optimizar para muchas llamadas de corta duración).

 ; 64bit SysV register-call ABI
; args: rdi: output buffer pointer. rsi: count
;; locals: rsi: endp
;; eax: current edx: prev
;; ecx: tmp
;; all of these are caller-saved in the SysV ABI, like r8-r11
;; so we can use them without push/pop to save/restore them.
;; The Windows ABI is different.
;void fib(int32_t *dest, uint32_t count); // unrolled version
global fib
fib:
cmp esi, 1
jb .early_out ; count below 1 (i.e. count==0, since it''s unsigned)
mov eax, 1 ; current = 1
mov [rdi], eax
je .early_out ; count == 1, flags still set from cmp
;; need this 2nd early-out because the loop always does 2 iterations
;;; branchless handling of odd counts:
;;; always do buf[0]=1, then start the loop from 0 or 1
;;; Writing to an address you just wrote to is very cheap
;;; mov/lea is about as cheap as best-case for branching (correctly-predicted test/jcc for count%2==0)
;;; and saves probably one unconditional jump that would be needed either in the odd or even branch
mov edx, esi ;; we could save this mov by using esi for prev, and loading the end pointer into a different reg
and edx, eax ; prev = count & 1 = count%2
lea rsi, [rdi + rsi*4] ; end pointer: same regardless of starting at 0 or 1
lea rdi, [rdi + rdx*4] ; buf += count%2
;; even count: loop starts at buf[0], with curr=1, prev=0
;; odd count: loop starts at buf[1], with curr=1, prev=1
align 16 ;; the rest of this func is just *slightly* longer than 16B, so there''s a lot of padding. Tempting to omit this alignment for CPUs with a loop buffer.
.loop: ;; do {
mov [rdi], eax ;; *buf = current
; on loop entry: curr:eax prev:edx
add edx, eax ; curr:edx prev:eax
;.oddentry: ; unused, we used a branchless sequence to handle odd counts
mov [rdi+4], edx
add eax, edx ; curr:eax prev:edx
;; back to our starting arrangement
add rdi, 8 ;; buf++
cmp rdi, rsi ;; } while(buf < endp);
jb .loop
; dec esi ; set up for this version with sub esi, edx; instead of lea
; jnz .loop
.early_out:
ret

Para producir la secuencia que comienza con cero, haga

curr=count&1; // and esi, 1
buf += curr; // lea [rdi], [rdi + rsi*4]
prev= 1 ^ curr; // xor eax, esi

en lugar de la actual

curr = 1;
prev = count & 1;
buf += count & 1;

También podemos guardar una instrucción mov en ambas versiones usando esi para mantener prev , ahora que prev depende del count .

 ;; loop prologue for sequence starting with 1 1 2 3
;; (using different regs and optimized for size by using fewer immediates)
mov eax, 1 ; current = 1
cmp esi, eax
jb .early_out ; count below 1
mov [rdi], eax
je .early_out ; count == 1, flags still set from cmp
lea rdx, [rdi + rsi*4] ; endp
and esi, eax ; prev = count & 1
lea rdi, [rdi + rsi*4] ; buf += count & 1
;; eax:curr esi:prev rdx:endp rdi:buf
;; end of old code
;; loop prologue for sequence starting with 0 1 1 2
cmp esi, 1
jb .early_out ; count below 1, no stores
mov [rdi], 0 ; store first element
je .early_out ; count == 1, flags still set from cmp
lea rdx, [rdi + rsi*4] ; endp
mov eax, 1 ; prev = 1
and esi, eax ; curr = count&1
lea rdi, [rdi + rsi*4] ; buf += count&1
xor eax, esi ; prev = 1^curr
;; ESI:curr EAX:prev (opposite of other setup)
;;

 ;; optimized for code size, NOT speed. Prob. could be smaller, esp. if we want to keep the loop start aligned, and jump between before and after it.
;; most of the savings are from avoiding mov reg, imm32,
;; and from counting down the loop counter, instead of checking an end-pointer.
;; loop prologue for sequence starting with 0 1 1 2
xor edx, edx
cmp esi, 1
jb .early_out ; count below 1, no stores
mov [rdi], edx ; store first element
je .early_out ; count == 1, flags still set from cmp
xor eax, eax ; movzx after setcc would be faster, but one more byte
shr esi, 1 ; two counts per iteration, divide by two
;; shift sets CF = the last bit shifted out
setc al ; curr = count&1
setnc dl ; prev = !(count&1)
lea rdi, [rdi + rax*4] ; buf+= count&1
;; extra uop or partial register stall internally when reading eax after writing al, on Intel (except P4 & silvermont)
;; EAX:curr EDX:prev (same as 1 1 2 setup)
;; even count: loop starts at buf[0], with curr=0, prev=1
;; odd count: loop starts at buf[1], with curr=1, prev=0
.loop:
...
dec esi ; 1B smaller than 64b cmp, needs count/2 in esi
jnz .loop
.early_out:
ret

vectorizado:

La secuencia de Fibonacci no es particularmente paralelizable. No hay una manera simple de obtener F (i + 4) de F (i) y F (i-4), o algo así. Lo que podemos hacer con los vectores es menos tiendas en la memoria. Empezar con:

a = [f3 f2 f1 f0 ] -> store this to buf
b = [f2 f1 f0 f-1]

Entonces a+=b; b+=a; a+=b; b+=a; a+=b; b+=a; a+=b; b+=a; produce:

a = [f7 f6 f5 f4 ] -> store this to buf
b = [f6 f5 f4 f3 ]

Esto es menos tonto cuando se trabaja con dos entradas de 64 bits empaquetados en un vector de 128b. Incluso en el código de 32 bits, puede usar SSE para hacer cálculos enteros de 64 bits.

Una versión anterior de esta respuesta tiene una versión de vector de 32 bits sin terminar que no maneja correctamente el count%4 != 0 . Para cargar los primeros 4 valores de la secuencia, usé pmovzxbd así que no necesitaba 16B de datos cuando solo podía usar 4B. Obtener los primeros valores -1 .. 1 de la secuencia en registros vectoriales es mucho más fácil, porque solo hay un valor distinto de cero para cargar y barajar.

;void fib64_sse(uint64_t *dest, uint32_t count);
; using SSE for fewer but larger stores, and for 64bit integers even in 32bit mode
global fib64_sse
fib64_sse:
mov eax, 1
movd xmm1, eax ; xmm1 = [0 1] = [f0 f-1]
pshufd xmm0, xmm1, 11001111b ; xmm0 = [1 0] = [f1 f0]
sub esi, 2
jae .entry ; make the common case faster with fewer branches
;; could put the handling for count==0 and count==1 right here, with its own ret
jmp .cleanup
align 16
.loop: ; do {
paddq xmm0, xmm1 ; xmm0 = [ f3 f2 ]
.entry:
;; xmm1: [ f0 f-1 ] ; on initial entry, count already decremented by 2
;; xmm0: [ f1 f0 ]
paddq xmm1, xmm0 ; xmm1 = [ f4 f3 ] (or [ f2 f1 ] on first iter)
movdqu [rdi], xmm0 ; store 2nd last compute result, ready for cleanup of odd count
add rdi, 16 ; buf += 2
sub esi, 2
jae .loop ; } while((count-=2) >= 0);
.cleanup:
;; esi <= 0 : -2 on the count=0 special case, otherwise -1 or 0
;; xmm1: [ f_rc f_rc-1 ] ; rc = count Rounded down to even: count & ~1
;; xmm0: [ f_rc+1 f_rc ] ; f(rc+1) is the value we need to store if count was odd
cmp esi, -1
jne .out ; this could be a test on the Parity flag, with no extra cmp, if we wanted to be really hard to read and need a big comment explaining the logic
;; xmm1 = [f1 f0]
movhps [rdi], xmm1 ; store the high 64b of xmm0. There is no integer version of this insn, but that doesn''t matter
.out:
ret

No tiene sentido desenrollar esto aún más, la latencia de la cadena dep limita el rendimiento, por lo que siempre podemos promediar el almacenamiento de un elemento por ciclo. La reducción de la sobrecarga del bucle en uops puede ayudar a hyperthreading, pero eso es bastante menor.

Como puede ver, manejar todos los casos de esquina, incluso cuando se desenrolla por dos, es bastante complejo de seguir. Requiere una sobrecarga de inicio adicional, incluso cuando intentas optimizar eso para mantenerlo al mínimo. Es fácil terminar con muchas ramas condicionales.

principal actualizado:

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#ifdef USE32
void fib(uint32_t *buf, uint32_t count);
typedef uint32_t buftype_t;
#define FMTx PRIx32
#define FMTu PRIu32
#define FIB_FN fib
#define CANARY 0xdeadbeefUL
#else
void fib64_sse(uint64_t *buf, uint32_t count);
typedef uint64_t buftype_t;
#define FMTx PRIx64
#define FMTu PRIu64
#define FIB_FN fib64_sse
#define CANARY 0xdeadbeefdeadc0deULL
#endif
#define xstr(s) str(s)
#define str(s) #s
int main(int argc, const char *argv[]) {
uint32_t count = 15;
if (argc > 1) {
count = atoi(argv[1]);
}
int benchmark = argc > 2;
buftype_t buf[count+1]; // allocated on the stack
// Fib overflows uint32 at count = 48, so it''s not like a lot of space is useful
buf[count] = CANARY;
// uint32_t count = sizeof(buf)/sizeof(buf[0]);
if (benchmark) {
int64_t reps = 1000000000 / count;
for (int i=0 ; i<=reps ; i++)
FIB_FN(buf, count);
} else {
FIB_FN(buf, count);
for (uint32_t i ; i < count ; i++){
printf("%" FMTu " ", buf[i]);
}
putchar(''/n'');
}
if (buf[count] != CANARY) {
printf(xstr(FIB_FN) " wrote past the end of buf: sentinel = %" FMTx "/n", buf[count]);
}
}

Actuación

Para un recuento justo por debajo de 8192, la versión no vectorizada desenrollada por dos se ejecuta cerca de su rendimiento teórico máximo de 1 tienda por ciclo (3.5 instrucciones por ciclo), en mi Sandybridge i5. 8192 * 4B / int = 32768 = tamaño de caché L1. En la práctica, veo ~ 3.3 a ~ 3.4 insn / ciclo. Sin embargo, estoy contando todo el programa con perf Linux, no solo el ciclo cerrado.

De todos modos, en realidad no tiene ningún sentido desenrollarse más. Y obviamente esto dejó de ser una secuencia de Fibonacci después de contar = 47, ya que usamos uint32_t. Sin embargo, para un count grande, el rendimiento está limitado por el ancho de banda de la memoria, hasta ~ 2.6 insn / ciclo. En este punto, básicamente estamos viendo cómo optimizar memset.

La versión vectorial de 64 bits se ejecuta en 3 insns por ciclo (una tienda de 128b por dos relojes) hasta un tamaño de matriz de aproximadamente 1,5 veces el tamaño de caché L2. (es decir ./fib64 49152 ). A medida que el tamaño de la matriz aumenta a fracciones más grandes del tamaño de caché L3, el rendimiento disminuye a ~ 2 insn por ciclo (una tienda por 3 relojes) a 3/4 del tamaño de caché L3. Se nivela a 1 tienda por 6 ciclos en tamaños> caché L3.

Por lo tanto, almacenar con vectores funciona mejor cuando encajamos en caché L2 pero no en L1.

Answer 3

.386
.model flat, stdcall
.stack 4096
ExitProcess proto, dwExitCode:dword
.data
fib word 1, 1, 5 dup(?);you create an array with the number of the fibonacci series that you want to get
.code
main proc
mov esi, offset fib ;set the stack index to the offset of the array.Note that this can also be set to 0
mov cx, lengthof fib ;set the counter for the array to the length of the array. This keeps track of the number of times your loop will go
L1: ;start the loop
mov ax, [esi]; move the first element to ax ;move the first element in the array to the ax register
add ax, [esi + type fib]; add the second element to the value in ax. Which gives the next element in the series
mov[esi + 2* type fib], ax; assign the addition to the third value in the array, i.e the next number in the fibonacci series
add esi, type fib;increment the index to move to the next value
loop L1; repeat
invoke ExitProcess, 0
main endp
end main