• Objetivos de la sesión:
  • 🚧 TODO 🚧

• Introducción
• Multiplicación: Algoritmo básico
• Macros de acceso a la pila: stack.h
  • Creación de la pila
  • Liberación de la pila
  • Almacenamiento y recuperación en pila de 16 bytes
  • Almacenamiento y recuperación en pila de 32 bytes
• Tests unitarios
  • Biblioteca unittest.s
  • Macros de pruebas: unittest.h
  • Pruebas unitarias de la función mul_basic()
  • Ejecutando todos los tests desde la consola
• Multiplicación: Algoritmo avanzado
  • Midiendo el algoritmo básico de multiplicación
  • Ejemplo 2: Multiplicación de números grandes
  • Algoritmo avanzado
  • Ejemplo 3: Tabla del 9
  • Pruebas unitarias
  • Ejemplo 4: Números grandes
  • Cuándo usar el básico, y cuándo el avanzado
• Desplazamiento de un número de 64 bits
• División: Algoritmo básico

🚧 TODO 🚧

Para programar los sistemas empotrados desde cero, lo primero que necesitamos en un sistema de entrada/salida de bajo nivel, que nos permite enviar caracteres a la consola y recibir datos a través del teclado. Esto ya lo tenemos solucionado en la sesión anterior, y tenemos las funciones puts() y gets() en la biblioteca stdio.s

Para seguir ampliando esta biblioteca necesitamos primero implementar las operaciones de multiplicación y división. Si estamos trabajando con un RV32IM, disponemos de las instrucciones mul y div. PERO si tenemos un RV32I, no disponemos de ellas, y por tanto hay que implementarlas por software. Ese es el objetivo principal de esta sesión. Estas funciones, junto a alguna más, las situaremos en la biblioteca math.s

Aprovecharemos también para crear funciones de verificación de estas operaciones. Es lo que denominamos tests unitarios. Desarrollaremos la biblioteca unittest.s para este propósito

Por el camino introduciremos el fichero stack.h que incluye macros muy útiles para trabajar con la pila y las funciones intermedias. Nos será de mucha utilidad en las sesiones siguientes

Vamos a realizar una primera implementación de la multiplicación basada en la definición. La expresión n.v, donde n y v son dos números enteros de 32 bits, significa que hay que sumar v consigo mismo n veces. Es decir, que $$nv=v+v+...+v$$ (n veces). Como la multiplicación es conmutativa, esa misma definición es válida para v.n

Por tanto, para hacer la multiplicación basta con implementar un bucle que se repita n veces, donde en cada pasada se agrege v al resultado parcial. Este es el algoritmo:

1. Inicializar el resultado parcial: $$m = 0$$
2. Si $$n == 0$$, saltar al paso 6
3. Actualizar el resultado parcial: $$m = m + v$$
4. Decrementar n: $$n = n - 1$$
5. Repetir desde el punto 2
6. El resultado de la multiplicación está en m

El bucle principal se repite n veces. Pero como la multiplicación es conmutativa, también podría repetirse v veces y en cada pasada sumar n. Nos interesa que este bucle tarde lo menos posible por lo que lo podemos mejorar si usamos como n el valor mínimo entre los dos operandos. Así, antes de realizar la multiplicación $$a.b$$ añadimos estos pasos:

i. Si $$a < b, n=a, v=b$$
ii. En caso contrario, $$n=b, v=a$$
iii. Continuar por el paso 1 del algoritmo

Esta multiplicación se implementa en la función mul_basic dentro del fichero math.s

    .text
mul_basic:
 #----------------------------------------------------------------
 #-- mul_basic(a,b): Multiplicación de numeros enteros
 #--
 #--   * si --> Single Integer (32 bits)
 #--   * 3 --> Un total de 3 operandos: 2 entradas + resultado
 #--
 #--  ENTRADA:
 #--    - a0 (a): Operador 1
 #--    - a1 (b): Operador 2
 #--
 #--  SALIDA:
 #--    - a0: Resultado (truncado a 32 bits)
 #--
 #-- Algoritmo basico de multiplicacion
 #----------------------------------------------------------------
    .global mul_basic

    #-- Implementacion 1: Basado en la definicion de multiplicacion
    #-- a.b = b + b +...+ b (a veces) = a + a +...+ a + a (b veces)

    #-- De forma generica lo ponemos asi:
    #--  n: Numero de repeticiones
    #--  v: Valor a sumar
    #-- n.v = v + v + v + ... + v (n veces)

    #-- Como la multiplicacion es conmutativa, elegimos la expresión
    #-- en la que hay que realizar menos sumas
    #-- Usamos n como el min(a,b)

    #-- Algoritmo:
    #-- Si a < b, n = a, v = b
    blt a0, a1, caso1

    #-- else
    #-- caso 2:
    #-- t0 = n = b
    mv t0, a1
    #-- t1 = v = a
    mv t1, a0
    j mul_basic_cont

 caso1:
 
    #-- caso 1:
    #-- t0 = n = a
    mv t0, a0
    #-- t1 = v = b
    mv t1, a1

 mul_basic_cont:

    #-- Resultado parcial = 0
    li t2, 0

    #--- Bucle principal
 mul_basic_loop:

    #-- Si n es 0, hemos terminado
    beq t0, zero, mul_basic_end

    #-- resultado = resultado + v
    add t2, t2, t1

    #-- n = n - 1
    addi t0, t0, -1

    #-- Repetir
    j mul_basic_loop

 mul_basic_end:

    #-- Devolver resultado
    mv a0, t2
    ret

Como ejemplo para probar la multiplicación vamos a hacer un programa que implemente la tabla de multplicar del 9

• Fichero: Ej01-tabla-del-9.s

#-- Ejemplo de prueba de multiplicacion
#-- Implementacion de la tabla del 9

	.include "so.h"
	.include "stdio.h"
	
	.text
	
	#-- Inicializar contador
	li s0, 0
	
	PRINT_STRINGI("Tabla del 9\n")
	PRINT_STRINGI("-----------\n")
	
bucle:
	#-- Multiplicar 9 * n
	li a0, 9
	mv a1, s0
	jal mul_basic
	mv t0, a0
	
	PRINT_INTI(9)
	PRINT_STRINGI(" * ")
	PRINT_INTR(s0)
	PRINT_STRINGI(" = ")
	PRINT_INTR(t0)
	PRINT_CHARI('\n')
	
	#-- Si n==10, terminar
	li t0, 10
	beq s0, t0, fin
	
	#-- n = n + 1
	addi s0, s0, 1
	
	#-- Repetir
	j bucle
	
fin:
	
	EXIT

Este es el resultado:

Todas las funciones intermedias tienen que crear la pila para guardar la dirección de retorno, y luego recupearla y liberar la pila. Es decir, que esta operación de crear y liberar la pila la tenemos que hacer con mucha frecuencia. Por ello, resulta muy cómodo llevarlo a macros

Este es el objetivo del fichero stack.h: contener todas las macros relacionadas con el acceso a la pila. La utilización de macros es opcional. Como estamos programando directamente en ensamblador y es una operación a realizar con mucha frecuencia, es preferible usar las macros. Pero se podría perfectamente implementar las funciones sin estas macros

El tamaño de la pila depende de la cantidad de información que necesitemos guardar (incluida la dirección de retorno: registro ra). Típicamente hemos usados dos tamaños, pilas de 16 (4 palabras) y 32 (8 palabras). En ambas hay que guardar la dirección de retorno en los offsets 12 y 28 respectivamente. Estas operaciones las hacemos con las macros STACK16 y STACK32:

#-------------------------------------------------------
#-- Crear una pila de 16 bytes
#-- Espacio para 4 registros (offsets 0 - 8)
#-- La direccion de retorno se guarda en el offset 12
#-------------------------------------------------------
.macro STACK16
  addi sp, sp, -16
  sw ra, 12(sp)
.end_macro

#-------------------------------------------------------
#-- Crear una pila de 32 bytes
#-- Espacio para 8 registros (offsets 0 - 24)
#-- La direccion de retorno se guarda en el offset 28
#-------------------------------------------------------
.macro STACK32
  addi sp, sp, -32
  sw ra, 28(sp)
.end_macro

Para realizar la operación inversa: recuperar la dirección de retorno y liberar la pila, utilizamos las macros UNSTACK16 y UNSTACK32. Además, en estas funciones también se retorna:

#----------------------------------------
#-- Liberar la pila de 16 bytes
#-- Recuperar la direccion de retorno
#-- RETORNAR DE LA FUNCION!
#----------------------------------------
.macro UNSTACK16
  lw ra, 12(sp)
  addi sp, sp, 16
  ret
.end_macro

#----------------------------------------
#-- Liberar la pila de 32 bytes
#-- Recuperar la direccion de retorno
#-- RETORNAR DE LA FUNCION!
#----------------------------------------
.macro UNSTACK32
  lw ra, 28(sp)
  addi sp, sp, 32
  ret
.end_macro

En las pilas de 16 bytes tenemos espacio sólo para 3 palabras, que se deben situar en los offsets 0, 4 y 8. Para simplificar el depósito de reigostros en esas posiciones, utilizamos las macros PUSH1, PUSH2 y PUSH3. La primera se usa cuando sólo guardamos 1 registros. La segunda si hay que guardar 2. Y la tercera 3. Para recuperar los registros usamos POP1, POP2 y POP3

Estas son las definiciones:

#-----------------------------------
#-- Meter en la pila SOLO 1 registro
#--   Se gudarda en offset 0
#-----------------------------------
.macro PUSH1(%reg)
  sw %reg, 0(sp)
.end_macro

#------------------------------------------
#-- Recuperar de la pila SOLO 1 registro
#--   Se recupera del offset 0
#------------------------------------------
.macro POP1(%reg)
  lw %reg, 0(sp)
.end_macro

#----------------------------------------
#-- Meter en la pila 2 registros
#--   Offsets 0 y 4
#----------------------------------------
.macro PUSH2(%reg0, %reg1)
  sw %reg0, 0(sp)
  sw %reg1, 4(sp)
.end_macro

#-----------------------------------------
#-- Sacar de la pila 2 registros
#-- Offsets 0 y 4
#-----------------------------------------
.macro POP2(%reg0, %reg1)
  lw %reg0, 0(sp)
  lw %reg1, 4(sp)
.end_macro

#----------------------------------------
#-- Meter en la pila 3 registros
#--   Offsets 0, 4 y 8
#----------------------------------------
.macro PUSH3(%reg0, %reg1, %reg2)
  sw %reg0, 0(sp)
  sw %reg1, 4(sp)
  sw %reg2, 8(sp)
.end_macro

#-----------------------------------------
#-- Sacar de la pila 3 registros
#-- Offsets 0, 4 y 8
#-----------------------------------------
.macro POP3(%reg0, %reg1, %reg2)
  lw %reg0, 0(sp)
  lw %reg1, 4(sp)
  lw %reg2, 8(sp)
.end_macro

Para el caso de una pila de 32 bytes podemos almacenar hasta 7 registros. Según el número de registros a guardar también usamos, PUSH1/POP1, PUSH2/POP2 y PUSH3/POP3. Pero a partir de 4 registros colocamos el prefijo STACK32 para poner de manifiesto que es OBLIGATORIO crear una pila de 32 (y si tenemos una creada de 16 entonces se podroducirán errores!!). Así tenemos estas macros: STACK32_PUSH4/STACK32_POP4, STACK32_PUSH5/STACK32_POP5...

#----------------------------------------
#-- Meter en la pila 4 registros
#--   Offsets 0, 4, 8 y 12
#-- WARNING: Solo es compatible STACK32!
#----------------------------------------
.macro STACK32_PUSH4(%reg0, %reg1, %reg2, %reg3)
  sw %reg0, 0(sp)
  sw %reg1, 4(sp)
  sw %reg2, 8(sp)
  sw %reg3, 12(sp)
.end_macro

#-----------------------------------------
#-- Sacar de la pila 4 registros
#-- Offsets 0, 4, 8 y 12
#-- WARNING: Solo es compatible con STACK32!
#-----------------------------------------
.macro STACK32_POP4(%reg0, %reg1, %reg2, %reg3)
  lw %reg0, 0(sp)
  lw %reg1, 4(sp)
  lw %reg2, 8(sp)
  lw %reg3, 12(sp)
.end_macro

#----------------------------------------
#-- Meter en la pila 5 registros
#--   Offsets 0, 4, 8, 12, 16
#-- WARNING: Solo es compatible STACK32!
#----------------------------------------
.macro STACK32_PUSH5(%reg0, %reg1, %reg2, %reg3, %reg4)
  sw %reg0, 0(sp)
  sw %reg1, 4(sp)
  sw %reg2, 8(sp)
  sw %reg3, 12(sp)
  sw %reg4, 16(sp)
.end_macro

#-----------------------------------------
#-- Sacar de la pila 5 registros
#-- Offsets 0, 4, 8, 12, 16
#-- WARNING: Solo es compatible con STACK32!
#-----------------------------------------
.macro STACK32_POP5(%reg0, %reg1, %reg2, %reg3, %reg4)
  lw %reg0, 0(sp)
  lw %reg1, 4(sp)
  lw %reg2, 8(sp)
  lw %reg3, 12(sp)
  lw %reg4, 16(sp)
.end_macro

#----------------------------------------
#-- Meter en la pila 6 registros
#--   Offsets 0, 4, 8, 12, 16, 20
#-- WARNING: Solo es compatible STACK32!
#----------------------------------------
.macro STACK32_PUSH6(%reg0, %reg1, %reg2, %reg3, %reg4, %reg5)
  sw %reg0, 0(sp)
  sw %reg1, 4(sp)
  sw %reg2, 8(sp)
  sw %reg3, 12(sp)
  sw %reg4, 16(sp)
  sw %reg5, 20(sp)
.end_macro

#-----------------------------------------
#-- Sacar de la pila 6 registros
#-- Offsets 0, 4, 8, 12, 16, 20
#-- WARNING: Solo es compatible con STACK32!
#-----------------------------------------
.macro STACK32_POP6(%reg0, %reg1, %reg2, %reg3, %reg4, %reg5)
  lw %reg0, 0(sp)
  lw %reg1, 4(sp)
  lw %reg2, 8(sp)
  lw %reg3, 12(sp)
  lw %reg4, 16(sp)
  lw %reg5, 20(sp)
.end_macro

Siempre que construimos funciones necesitamos un procedimiento para garantizar que funcionan correctamente. Lo que hacemos es crear una o varias funciones nuevas, que llamamos funciones de test o tests unitarios, que llamen a la función original y comprueben si los resultados devueltos son correctos

Por ejemplo, para probar la función de multiplicación mul_basic, hemos usado un programa de ejemplo que calcula la tabla del 9. ¿Cómo sabemos que la multiplicación ha funcionado? Ejecutamos el programa, se genera la tabla del 9 y mediante inspección visual comprobamos que los valores son correctos. La idea detrás de los test unitarios es la de automatizar este proceso, y que sea el propio programa de prueba el que nos diga si ha funcionado o no

Si en el futuro hacemos un cambio en esta función, basta con pasar los test para comprobar si hemos roto algo o no

Para realizar las pruebas unitarias de las funciones de la biblioteca math.s necesitamos comprobar si la salida devuelta por ellas es la esperada. Utilizamos la función assert_equal(result, result_expected) donde se le pasando dos valores enteros de 32 bits: Uno es el resultado de la operación, devuelto por la función, y el otro el valor esperado. Estos valores se comparan y si son diferentes significa que el test ha fallado

Así por ejemplo, una prueba podría ser comprobar el valor generado por mul_basic(9,9), que sabemos que debe 81. Si el valor devuelto es diferente a 81, sabemos que NO ha funcionado

Son prácticas de buena programación el hacer test unitarios para todas las funciones que tengamos en nuestros proyectos. Cada vez que detectemos un problema, hay que añadir el test correspondiente para garantizar que no vuelta a aparecer. Nuestros proyectos son así más robustos y más fáciles de mantener. También nos permite realizar integración continua: cada vez que se hace un cambio y se sube al repositorio, se pasan automáticamente todo los tests para saber de inmediato si este cambio ha roto algo

Las funciones para comprobar los resultados de las pruebas las agrupamos dentro del fichero unittest.s

De momento, para comprobar las funciones de math.s lo que necesitamos son las función de comparar números sin signo de 32 y 64 bits:

• assert_equal(val1, val2): Comprobar valores de 32 bits. El valor devuelto por la función (val1) debe ser igual al valor esperado (val2)
• assert_equal_64(v0, v1, w0, w1): Comparar los valores v y w de 64 bits. v0 y w0 son los 32 bits de menor peso, y v1 y w1 los 32 bits de mayor peso

En este fichero iremos añadiendo, en el futuro, nuevas funciones para realizar las comprobaciones futuras bibliotecas

Para facilitar la creación de los test unitarios, definimos la macro ASSERT_EQUAL(%reg, %val) donde le pasamos como parámetros las dos valores: el devuelto y el esperado. El devuelto se obtiene en un registros (que típicamente será el a0), mientras que el esperado es un valor literal. Así por ejemplo, para verificar que la multiplicación 8x9 es correcta escribimos ASSERT_EQUAL(a0, 72)

También definimos la macro ASSERT_EQUAL_64(%reg1, %reg0, %w1, %w0) para comprobar resultados de 64 bits

Estas macros están definidas en unittest.h

• Fichero: unittest.h

#----------------------------------------------------
#-- Compara que dos valores sean iguales
#-- El valor izquierdo es el devuelto por la funcion
#--   ES UN REGISTRO
#-- El valor derecho es el valor esperado. Es una
#--   constante
#----------------------------------------------------
.macro ASSERT_EQUAL(%reg, %val)
	mv a0, %reg
	li a1, %val
	jal assert_equal
.end_macro

#-----------------------------------------------------
#-- Comparar que dos valores de 64 bits son iguales
#--  Valores izquierdos: son los generados por la funcion
#--  Valores derechos: Son los resultados esperados
#------------------------------------------------------
.macro ASSERT_EQUAL_64(%reg1, %reg0, %w1, %w0)
	mv a0, %reg0
	mv a1, %reg1
	li a2, %w0
	li a3, %w1
	jal assert_equal_64
.end_macro

Las pruebas unitarias de las funciones de la biblioteca math.s las situamos en el fichero test-math.s. Dado que hay que realizar varias pruebas para cada función, resulta más cómodo utilizar macros. Así, para cada función de math.s, definimos su propia macro para facilitar su llamada. Estas macros las situamos en math.h

Para el caso de la función mul_basic(a,b) definimos la macro MUL_BASIC (%a, %b), en el fichero math.h:

.macro MUL_BASIC (%a, %b)
    li a0, %a
    li a1, %b
    jal mul_basic
.end_macro

Para las pruebas unitarias hay que elegir pares de valores a comprobar: resultado y valor esperado

unittest_mul_basic:

    STACK16

    TEST_TITTLE("----- MUL_BASIC() --------\n")

    #------- MUL_BASIC(0, 1) = 0
	TEST_NAME("1")
    MUL_BASIC(0, 1)
	ASSERT_EQUAL(a0, 0)

    #------- MUL_BASIC(1, 0) = 0
	TEST_NAME("2")
    MUL_BASIC(1, 0)
	ASSERT_EQUAL(a0, 0)

    #------- MUL_BASIC(1, 1) = 1
	TEST_NAME("3")
    MUL_BASIC(1, 1)
	ASSERT_EQUAL(a0, 1)

    #------- MUL_BASIC(3, 100) = 300
	TEST_NAME("4")
    MUL_BASIC(3, 100)
	ASSERT_EQUAL(a0, 300)

    #------- MUL_BASIC(200, 100) = 20000
	TEST_NAME("5")
    MUL_BASIC(200, 100)
	ASSERT_EQUAL(a0, 20000)

    #------- MUL_BASIC(256, 256) = 65536
	TEST_NAME("5")
    MUL_BASIC(256, 256)
	ASSERT_EQUAL(a0, 65536)

    #------- MUL_BASIC(1024, 2048) = 2097152
	TEST_NAME("6")
    MUL_BASIC(1024, 2048)
	ASSERT_EQUAL(a0, 2097152)

    #------- MUL_BASIC(0x40000000, 2) = 0x80000000
	TEST_NAME("7")
    MUL_BASIC(0x40000000, 2)
	ASSERT_EQUAL(a0, 0x80000000)

    UNSTACK16

Este es el resultado al ejecutar este test:

Además de este test, se ejecutan los tests del resto de funciones, pero aquí sólo se muestra el del mul_basic()

Para ejecutar los tests unitarios resulta muy cómodo hacerlo desde la consola, en vez de tener que abrir el RARs y cargar los módulos uno a uno. Para automatizar esta tarea creamos el script unittests.sh:

#!/bin/bash

java -jar rars1_6.jar test-math.s math.s stdio.s unittest.s io_rars_so.s

Esto es lo que obtenemos al ejecutarlo directamente desde la termina. Sólo se muestran los resultados de la prueba para mul_basic():

¿Cómo de bueno es el algoritmo que hemos empleado para multiplicar? El criterio que se usa es el del rendimiento. El mejor algoritmo será el que nos produzca un mayor rendimiento. Es decir, es aquél que hace que los programas se ejecuten más rápidamente. Con el RARs lo que medimos es el número de ciclos totales. Cuanto menos ciclos tarde, mejor será el rendimiento

Para medir el rendimiento utilizamos programas de prueba. El primero que medimos es el del ejemplo 1: La tabla del nueve. Lo ejecutamos y nos vamos a la pestaña de Control and Status. Ahí podemos ver que el número de ciclos es de 619

Repetimos el experimento para los test unitarios. Si ejecutamos sólo los test de mul_basic(), tarda un total de 7231 ciclos

¿A qué se debe esta diferencia tan grande? Si nos fijamos en el algoritmo, observamos que el bucle principal realiza tantas iteraciones como indica uno de sus operandos. Es decir, que la multiplicación de a*b TARDA UN TIEMPO VARIABLE. Si el min(a,b) es un número pequeño, tardará poco, pero si es un número grande tardará mucho. El tiempo depende de uno de los operandos

Esto lo podemos comprobar fácilmente con el programa del ejemplo 2

Los números más grandes que podemos multiplicar sin producir desbordamiento son 0xFFFF y 0x10000. Vamos a multiplicarlos para comprobar cuántos ciclos se tarda

Este es el ejemplo:

• Fichero: Ej02-numero-grande.s

#-- Ejemplo de prueba de multiplicacion
#-- de un numero grande

	.include "so.h"
	.include "stdio.h"
	
	.text
	
	#-- Numeros a multiplicar
	li s0, 0x10000
	li s1, 0xFFFF
	
	#-- Imprimir operacion a realizar
	PRINT_INT_HEXR(s0)
	PRINT_STRINGI(" * ")
	PRINT_INT_HEXR(s1)
	PRINT_STRINGI(" = ")
	
	#-- Realizar la multiplicacion
	mv a0, s0
	mv a1, s1
	jal mul_basic
	mv t0, a0
	
	#-- Imprmir resultado
	PRINT_INT_HEXR(t0)
	PRINT_CHARI('\n')
	
	EXIT

Lo ejecutamos y medimos los ciclos:

El programa tarda 262177 ciclos. ¡Son muchos ciclos para una única multiplicación!

¿Podemos hacer esta operación de números grandes en menos ciclos? Sí. Esta es la razón por la que necesitamos un algoritmo mejor

Este algoritmo se basa en el modo en el que se realiza la multiplicación en binario manualmente. La multiplicación se realiza entre los operandos a y b. Estos son los pasos a seguir:

1. Inicializar el resultado parcial: R=0
2. Inicializar el contador de bits: N=32 (Tamaño de los operandos)
3. Bucle principal
   3.1. Si N > 0, saltar al punto 4 (Terminar)
   3.2. Obtener el bit0 del operando b (b0)
   3.3. Si b0==0, saltar al punto 3.5
   3.4. Actualizar resultado parcial: R = R + a
   3.5. Desplazar a un bit a la izquierda: a = a << 1
   3.6. Desplazar b un bit a la derecha: b = b >> 1
   3.7. Decrementar contador de bits: N = N - 1
   3.8. Repetir el bucle
4. Devolver resultado: R
5. Fin

Ya vemos una cosa de este algoritmo: siempre realiza 32 iteraciones del bucle con independencia de los operandos. Es decir, que los ciclos de multiplicación SIEMPRE SON LOS MISMOS, y no dependen en absoluto de los operandos utilizados

La implementación se realiza en la función _mul(). Utilizamos el guión bajo _ como prefijo para diferenciarlo de la instrucción mul que multiplica dos registro en los RV32IM. Si la función la llamamos mul, se produce un error de ensamblado

#----------- _mul(a,b) --------------
_mul:
 #-----------------------------------------------------
 #-- _mul(a,b): Multiplicacion de dos numeros enteros
 #--
 #-- ENTRADAS:
 #--  -a0 (a): Operando 1
 #--  -a1 (b): Operando 2
 #-----------------------------------------------------
    .global _mul

    #-- t0: Resultado parcial
    li t0, 0

    #-- t1: Contador de bits (tamaño de los operandos)
    li t1, 32

    #-- Bucle principal
 _mul_loop:

    #-- Si contador de bits es 0, terminar
    beq t1, zero, _mul_end

    #-- t2: bit 0 de operando b
    andi t2, a1, 1

    #-- Si el bit es 0, continuar con el algoritmo
    beq t2, zero, _mul_cont

    #-- El bit es 1: Actualizar el resultado parcial
    add t0, t0, a0

 _mul_cont:

    #-- Desplazar operando 1 un bit a la izquierda
    #-- a = a << 1
    slli a0, a0, 1

    #-- Desplazar operando 2 un bit a la derecha
    #-- b = b >> 1
    srli a1, a1, 1

    #-- Decrementar contador de bits
    addi t1, t1, -1

    #-- Repetir
    j _mul_loop

 _mul_end:
    #-- Devolver resultado
    mv a0, t0
    ret

Repetimos el mismo ejemplo 1, que calcula la tabla del 9, PERO utilizando llamadas a la función _mul() en vez de a mul_basic()

• Fichero: Ej03-tabla-del-9.s

#-- Ejemplo de prueba de multiplicacion
#-- Implementacion de la tabla del 9

	.include "so.h"
	.include "stdio.h"
	
	.text
	
	#-- Inicializar contador
	li s0, 0
	
	PRINT_STRINGI("Tabla del 9\n")
	PRINT_STRINGI("-----------\n")
	
bucle:
	#-- Multiplicar 9 * n
	li a0, 9
	mv a1, s0
	jal _mul
	mv t0, a0
	
	PRINT_INTI(9)
	PRINT_STRINGI(" * ")
	PRINT_INTR(s0)
	PRINT_STRINGI(" = ")
	PRINT_INTR(t0)
	PRINT_CHARI('\n')
	
	#-- Si n==10, terminar
	li t0, 10
	beq s0, t0, fin
	
	#-- n = n + 1
	addi s0, s0, 1
	
	#-- Repetir
	j bucle
	
fin:
	
	EXIT

Lo probamos y medimos los ciclos:

¡¡Tarda 2851 ciclos!!. ¡¡Más que con el algoritmo básico!!. ¿Qué está pasando?

Cuando uno de los operandos es pequeño, el algoritmo básico gana. En el caso de la tabla del 9, el dígito usado para las iteraciones (n) es siempre menor o igual a 9. Es decir, se hacen pocas iteraciones

Sin embargo, con el algoritmo avanzado, SIEMPRE se hacen 32 iteraciones, con independencia de si los operandos son grandes o pequeños

Este resultado se puede mejorar. Si sabemos que se usan números pequeños, se pueden representar con menos bits, y por tanto, en el algoritmo avanzando no hace falta iterar 32 veces, sino el número real de bits usados. Para el ejemplo de la tabla del 9, con establecer 4 iteraciones (ya que todos los operandos se pueden representar con 4 bits), se mejora muchísimo. Pasamos de 2851 a 696, que está mucho más cerca de los 619 del algoritmo básico. Aún así, sigue siendo ligeramente mejor el básico

La tabla del 9 está bien, pero es mejor tener unas pruebas unitarias que automáticamente nos indiquen si se pasa el test o no. Vamos a hacer dos funciones de pruebas. En la primera se prueban los mismos casos que para mul_basic(). Esto nos permitirá comparar el rendimiento:

unittest_mul:

    STACK16

    TEST_TITTLE("----- MUL() I --------\n")

    TEST_NAME("1")
    _MUL(0, 1)
    ASSERT_EQUAL(a0, 0)

    TEST_NAME("2")
    _MUL(1, 0)
    ASSERT_EQUAL(a0, 0)

    TEST_NAME("3")
    _MUL(1, 1)
    ASSERT_EQUAL(a0, 1)

    TEST_NAME("4")
    _MUL(3, 100)
    ASSERT_EQUAL(a0, 300)

    TEST_NAME("5")
    _MUL(200, 100)
    ASSERT_EQUAL(a0, 20000)

    TEST_NAME("5")
    _MUL(256, 256)
    ASSERT_EQUAL(a0, 65536)

    TEST_NAME("6")
    _MUL(1024, 2048)
    ASSERT_EQUAL(a0, 2097152)

    TEST_NAME("7")
    _MUL(0x40000000, 2)
    ASSERT_EQUAL(a0, 0x80000000)

    UNSTACK16

Lo probamos. Este es el resultado:

Tarda 3437 ciclos. Mucho menos que los 7231 ciclos del algoritmo básico. Claro, en estas pruebas unitarias se han probado números más grandes, por eso el algoritmo avanzado gana

Además añadimos otra batería de pruebas unitarias, en la función unittest_mul_II, para realizar más pruebas:

unittest_mul_II:
    STACK16

    TEST_TITTLE("----- MUL() II--------\n")

    #------- MUL(1, 0) = 0
	TEST_NAME("1")
    _MUL(1, 0)
	ASSERT_EQUAL(a0, 0)

    #------- MUL(0, 1) = 0
	TEST_NAME("2")
    _MUL(0, 1)
	ASSERT_EQUAL(a0, 0)

    #------- MUL(1, 1) = 1
	TEST_NAME("3")
    _MUL(1, 1)
	ASSERT_EQUAL(a0, 1)

    #------- MUL(2, 1) = 2
	TEST_NAME("4")
    _MUL(2, 1)
	ASSERT_EQUAL(a0, 2)

    #------- MUL(1, 2) = 2
	TEST_NAME("5")
    _MUL(1, 2)
	ASSERT_EQUAL(a0, 2)

    #------- MUL(2, 2) = 4
	TEST_NAME("6")
    _MUL(2, 2)
	ASSERT_EQUAL(a0, 4)

    #------- MUL(3, 2) = 6
	TEST_NAME("7")
    _MUL(3, 2)
	ASSERT_EQUAL(a0, 6)

    #------- MUL(3, 3) = 9
    TEST_NAME("8")
    _MUL(3, 3)
	ASSERT_EQUAL(a0, 9)

    #------- MUL(4, 5) = 20
    TEST_NAME("9")
    _MUL(4, 5)
	ASSERT_EQUAL(a0, 20)

    #------- MUL(7, 7) = 49
    TEST_NAME("10")
    _MUL(7, 7)
	ASSERT_EQUAL(a0, 49)

    #------- MUL(15, 10) = 150
    TEST_NAME("11")
    _MUL(15, 10)
	ASSERT_EQUAL(a0, 150)

    #------- MUL(256, 200) = 51200
    TEST_NAME("12")
    _MUL(256, 200)
	ASSERT_EQUAL(a0, 51200)

    #------- MUL(0x1000, 0x2000) = 0x2000000
    TEST_NAME("13")
    _MUL(0x1000, 0x2000)
	ASSERT_EQUAL(a0, 0x2000000)

    #------- MUL(0x40000000, 0x2) = 0x80000000
    TEST_NAME("14")
    _MUL(0x40000000, 0x2)
	ASSERT_EQUAL(a0, 0x80000000)

    UNSTACK16

Este es el resultado de las pruebas unitarias para la función _mul()

Repetimos el mismo ejemplo de multiplicación de números grandes, pero usando la función _mul():

#-- Ejemplo de prueba de multiplicacion
#-- de un numero grande

	.include "so.h"
	.include "stdio.h"
	
	.text
	
	#-- Numeros a multiplicar
	li s0, 0x10000
	li s1, 0xFFFF
	
	#-- Imprimir operacion a realizar
	PRINT_INT_HEXR(s0)
	PRINT_STRINGI(" * ")
	PRINT_INT_HEXR(s1)
	PRINT_STRINGI(" = ")
	
	#-- Realizar la multiplicacion
	mv a0, s0
	mv a1, s1
	jal _mul
	mv t0, a0
	
	#-- Imprmir resultado
	PRINT_INT_HEXR(t0)
	PRINT_CHARI('\n')
	
	EXIT

Lo probamos. Este es el resultado:

¡Tarda 274 ciclos frente a 262177 ciclos del básico!. Es 3 órdenes de magnitud mejor!!

Para saber exactamente cuándo compensa usar un algoritmo u otro, vamos a hacer un experimento. Partimos de los ejemplos 2 y 4, de la multiplicación de números grades. Hacemos la multiplicación aplicando la restricción a = b. Así sabemos exactamente las iteraciones del algoritmo básico. Cuando hacemos la multiplicación 56*56, Los dos algoritmos tarda exactamente los mismos ciclos. Los ejemplos 2 y 4 tardan 259

Es decir, que si el operando mínimo es mayor o igual a 56, compensa más usar el algortimo básico. Pero si el mínimo operando es mayor a 56, compensa usar el avanzado

Por supuesto que esto se puede mejorar, porque si se sabe que el operando mínimo es menor a 56, podemos modificar el algoritmo avanzado para realizar sólo 6 iteraciones ya que 56 cabe en 6 bits. En ese caso gana el avanzado por mucho

La operación de desplazar un número de 64 bits un bit hacia la izquierda se utiliza en muchos algoritmos. En un RISV-V de 32 bits hay que realizarlo usando dos registros. Uno que contiene la parte baja y otro la parte alta

La función que realiza esta operación es: shift_left1_64(r0, r1, bit). El primer parámetro es la parte baja, el segundo la alta, y el tercero es el bit que se introduce por la derecha, que puede ser 0 ó 1

Esta función la metemos dentro de math.s

shift_left1_64:
 #----------------------------------------------------
 #-- shift_left1_64(r0,r1, bit):
 #--
 #--    Desplazar un bit a la izquierda un registro de 64-bits
 #--
 #--      r1 <-- r0 <-- bit 
 #--
 #--  ENTRADA:
 #--   -a0 (r0): Registro 0 (menor peso)
 #--   -a1 (r1): Registro 1 (mayor peso)
 #--   -a2 (bit): Bit que se introduce por la derecha
 #--
 #--  SALIDA:
 #--   -a0: (r0) Parte baja desplazada
 #--   -a1: (r1) Parte alta desplazada
 #----------------------------------------------------
    .global shift_left1_64

    #-- t0: bit de mayor peso de r0
    slt t0, a0, zero

    #-- r1 << 1
    slli a1, a1, 1

    #-- Añadir el bit t0
    or a1, a1, t0

    #-- r0 << 1
    slli a0, a0, 1

    #-- Añadir el bit
    or a0, a0, a2
    ret

Creamos la macro SHIFT_LEFT1_64(%val1, %val0, %bit) para utilizarla en las pruebas unitarias, que son estas:

unittest_shift_left1_64:
    STACK16

    TEST_TITTLE("----- SHIFT_LEFT1_64() --------\n")

    #------- SHIFT_LEFT1_64(0x00, 0x00, 1)
	TEST_NAME("1")
    SHIFT_LEFT1_64(0x00, 0x00, 1)
	ASSERT_EQUAL_64(a1, a0, 0x00, 0x01)

    #------- SHIFT_LEFT1_64(0x00, 0x01, 0)
	TEST_NAME("2")
    SHIFT_LEFT1_64(0x00, 0x01, 0)
	ASSERT_EQUAL_64(a1, a0, 0x00, 0x02)

    #------- SHIFT_LEFT1_64(0x00, 0xFFFFFFFF, 0)
	TEST_NAME("3")
    SHIFT_LEFT1_64(0x00, 0xFFFFFFFF, 0)
	ASSERT_EQUAL_64(a1, a0, 0x01, 0xFFFFFFFE)

    #------- SHIFT_LEFT1_64(0x00, 0xFFFFFFFF, 1)
	TEST_NAME("4")
    SHIFT_LEFT1_64(0x00, 0xFFFFFFFF, 1)
	ASSERT_EQUAL_64(a1, a0, 0x01, 0xFFFFFFFF)

    #------- SHIFT_LEFT1_64(0x80000000, 0x80000000, 1)
	TEST_NAME("5")
    SHIFT_LEFT1_64(0x80000000, 0x80000000, 1)
	ASSERT_EQUAL_64(a1, a0, 0x01, 0x01)

    #------- SHIFT_LEFT1_64(0x80000000, 0x80000000, 0)
	TEST_NAME("5")
    SHIFT_LEFT1_64(0x80000000, 0x80000000, 0)
	ASSERT_EQUAL_64(a1, a0, 0x01, 0x00)

    UNSTACK16

Y que por supuesto las pasa:

Los dos mensajes de OK que aparecen asociados a un mismo test es debido a que la función de desplazamiento devuelve 2 registros: uno con el resultado bajo, y otro el alto. Cada OK se corresponde con cada uno de ellos

🚧 DEBUG 🚧

• Algoritmo de Euclides de restas sucesivas https://es.wikipedia.org/wiki/Algoritmo_de_Euclides

🚧 TODO 🚧

• Divisiones: Algoritmo mejorado