Tarea de aritmética

Lyoshenka, Lyoshenka, ¡hazme un favor!
¡Aprende, Alyoshenka, la tabla de multiplicar!
Agnia Barto


Primera tarea para un alumno de primer grado. Se da algún número positivo. Debe multiplicar por otro número, desconocido de antemano. La pregunta es, ¿cómo aconsejarán los nobles Dons hacer esto? Un desarrollador experimentado seguramente dirá, dicen hombre, pon el multiplicador y no te preocupes por mi cerebro. ¡Y quizás será fundamentalmente incorrecto! Además de los monstruos de Alterra y Xilinx, también hay una familia tan maravillosa como el iCE-40 de Lattice . Ultra micro consumo. Muy barato Sí, el problema es que son dolorosamente pequeños y, por desgracia, no hay multiplicadores allí. Me encontré con esto hace aproximadamente 4 años cuando porté cierto códec ADPCM del ensamblador adsp-2185 a un cristal de este tipo.

No, sin un multiplicador de propósito general (para dos variables) ciertamente no podría haberlo hecho. Tuve que hacerlo con bolígrafos y él tomó la mitad del cristal. El problema es que trilló en cada paso, es decir No hay ventanas en absoluto. Y además de la multiplicación de variables en el algoritmo, había coeficientes fijos, que también tenían que multiplicarse. Y no había forma de usar el multiplicador para esto, simplemente no quedaba ninguna ventana. Y dado que la lucha en el proyecto pasó por cada celda, por supuesto, estaba muy interesado en cómo esquivar, y el uso de las propiedades de estos coeficientes hizo que el esquema óptimo de multiplicación por ellos (¡no un multiplicador de propósito general, sino un dispositivo de multiplicación por un número dado!). Bueno, como un sueño completo hecho realidad, para que los esquemas de multiplicación por diferentes coeficientes aprovechen al máximo algunos recursos cristalinos comunes.

Entonces, de la tarea para el alumno de primer grado, pasamos sin problemas a la tarea para el ingeniero y el matemático. ¿Cómo construir un esquema de multiplicación óptimo para un número específico dado?

Recordemos un poco cómo generalmente multiplicamos el número A por B.

1. Para empezar, establezca el resultado en cero.
2. Repasemos los bits A.
3. Si en la descarga 0, no hacemos nada.
4. Si en el bit 1, desplazamos B por el número correspondiente de bits y sumamos al resultado.

Total, cuantas menos unidades A estén en los dígitos, más fácil será multiplicar por ellas. Multiplicar por 2, 4 u 8 es fácil. Solo se necesita un cambio. Un poco más difícil de multiplicar por 3, 5 o 10. Se necesitará una adición. Aún más difícil de multiplicar por 11. Cuantas más unidades, más difícil.

Bueno, ¿qué hay de multiplicar por 255? Hasta 8 unidades, una tarea de pesadilla, ¿verdad? ¡Y aquí están las figuras! Hagamos una finta engañosa con nuestros oídos. Multiplique nuestra B por 256 (es decir, cámbiela por 8 dígitos) y reste del resultado. Resulta que a pesar del aspecto formidable, multiplicar por 255 es tan fácil como multiplicar por 10. Es igual de fácil multiplicar por 254, y por 240, y por 224 (si lo desea, ¡marque!).

En total, la resta ayuda a la multiplicación. Recuerda este valioso pensamiento. Mientras tanto, llamamos a la dificultad de un número el número mínimo de operaciones de suma (o resta) necesarias para multiplicar por él. Los turnos no se tienen en cuenta. En el contexto del problema (¡tenemos circuitos, no programación!) Se obtienen por nada. Formulemos una declaración obvia pero útil:

La dificultad de un número es menor o igual que el número de unidades en su notación binaria.
De hecho, si sinceramente multiplicamos sin restar trucos, como enseñamos en la escuela, el número de sumas será igual al número de unidades en binario A. Y si comenzamos a engañar y, además, tenemos suerte, entonces reduciremos el número de operaciones.

Una consecuencia interesante de esta afirmación:
La dificultad de cualquier número de n bits siempre es estrictamente menor que n .
Después de todo, el mayor número de unidades en un número de n dígitos es n , para un número como 255. Por otro lado, está claro que el enfoque, como con la multiplicación por 255, puede repetirse para números de cualquier profundidad de bits. Esto abre perspectivas para optimizar los multiplicadores de propósito general.

Démosle a nuestro razonamiento un aspecto más regular. Para empezar, tengamos algún tipo de esquema de multiplicación por A. Tomamos como la unidad. Luego, todos los términos se mueven, suman y restan de tal manera que el resultado sea el mismo A. Total, nuestro esquema de multiplicación por A no es más que una representación del número A como la suma de las potencias de dos en las que los términos pueden ser tanto con el signo + como con el signo - . Y puede agrupar los términos positivos y negativos, y decir que el esquema se describe por la diferencia de algunos números A + y A- , igual a A. Esto es malo ... Los miembros de la diferencia pueden ser arbitrariamente grandes. Pensemos si hay alguna consideración para limitarlos.
En primer lugar, notamos que cada potencia de dos puede ingresar al circuito solo una vez. De hecho, si ella ingresa dos veces con el mismo signo, esto puede ser reemplazado por una potencia de dos por una unidad de mayor. Si ella entra dos veces con diferentes signos, se restan mutuamente. En total, el esquema es muy similar a la representación binaria habitual de A. La única diferencia es que sus "bits" (en adelante los llamaremos trits ) no pueden tomar dos, sino tres valores: 1, 0 y -1.

Total Si A es un número binario de n bits, el esquema de multiplicación por él se describe mediante la suma:

$$

$$A = {t_m} 2 ^ m + {t_ {m-1}} 2 ^ {m-1} + .... + {t_1} 2 + {t_0}$$

donde $$${t_i}$- trits, tomando los valores 1, 0 y -1, ym es un número desconocido.

En lo que sigue, llamaremos a tal expresión un esquema ternario o simplemente un esquema o un esquema de multiplicación para el número A.

Tratemos de encontrar m . Como se puede ver en el ejemplo con multiplicación por 255, m no es de ninguna manera menor que n . Veamos si puede ser igual a n + 1 .
Sea A, como antes, un número positivo de n dígitos. Entonces el esquema de multiplicación se define como:

$$

$$A = {t_ {n + 1}} 2 ^ {n + 1} + {t_ {n}} 2 ^ {n} + {t_ {n-1}} 2 ^ {n-1} .... + {t_1} 2 + {t_0}$$

Recordemos que $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$
Por lo tanto, el trit más alto no puede ser de ninguna manera igual a -1. De hecho, incluso si todos los demás son 1, la suma seguirá siendo -1. Y por la condición A es positiva. Ahora deje que el trit superior sea 1. Pero en este caso, el trit siguiente debería ser -1. De lo contrario, la cantidad será demasiado grande. De hecho, si el siguiente trit es 0, la suma no será inferior a $$$2 ^ {n + 1} - (2 ^ {n-1} + ... + 1) = 2 ^ {n + 1} - (2 ^ n - 1) = 2 ^ n + 1$
Mientras que n -bit A no es más $$$2 ^ n - 1$. Pero si el trit superior es 1 y el siguiente -1, entonces la suma de los dos miembros principales es $$$2 ^ {n + 1} -2 ^ n = 2 ^ n$. Entonces el trit superior es 0.

Por lo tanto, se demuestra una afirmación importante: m = n .

En otras palabras, para representar cualquier esquema de multiplicación por un n bit A , n + 1 potencias de dos son suficientes, de 0 a n (uno más que la representación binaria), lo que nos salva inmediatamente del infinito.

Ahora puede intentar calcular las dificultades (ver arriba) de cualquier número específico. Lo más simple es hacer lo que hacemos escribiendo números binarios en orden. Solo en primer lugar, aquí no tenemos bits sino tritos (tres valores posibles), en segundo lugar, algunas combinaciones de tritos dan números negativos y deben descartarse, en tercer lugar, algunas combinaciones pueden dar números coincidentes. Esto significa que para tal número hay varios esquemas.

Escribiremos en python. No porque sea tan fanático de él, sino porque es extremadamente conveniente trabajar con él en cuadernos Jupyter. Para comenzar, escribimos la clase TriScheme que funciona con los esquemas ternarios presentados anteriormente, la función allSchemes, que calcula con todos los esquemas para números de un tamaño de bit dado mediante una enumeración simple, y la función printSchemes que imprime el resultado:


Calculamos los esquemas para todos los números de 4 bits:

0 0 1 [00000]
1 1 5 [0000+, 000 + -, 00 + -, 0 + ---, + ----]
2 1 4 [000 + 0, 00 + -0, 0 + - 0, + --- 0]
3 2 7 [000 ++, 00 + - +, 00 + 0-, 0 + - +, 0 + -0-, + --- +, + - 0-]
4 1 3 [00 + 00, 0 + -00, + - 00]
5 2 8 [00 + 0 +, 00 ++ -, 0 + -0 +, 0 + - + -, 0 + 0--, + - 0+, + - + -, + -0--]
6 2 5 [00 ++ 0, 0 + - + 0, 0 + 0-0, + - + 0, + -0-0]
7 2 7 [00 +++, 0 + - ++, 0 + 0- +, 0 + 00-, + - ++, + -0- +, + -00-]
8 1 2 [0 + 000, + -000]
9 2 7 [0 + 00 +, 0 + 0 + -, 0 ++ -, + -00 +, + -0 + -, + - + -, +0 ---]
10 2 5 [0 + 0 + 0, 0 ++ - 0, + -0 + 0, + - + - 0, + 0-0]
11 3 8 [0 + 0 ++, 0 ++ - +, 0 ++ 0-, + -0 ++, + - + - +, + - + 0-, +0 - +, + 0-0 -]
12 2 3 [0 ++ 00, + - + 00, + 0-00]
13 3 7 [0 ++ 0 +, 0 +++ -, + - + 0+, + - ++ -, + 0-0 +, +0 - + -, + 00--]
14 2 4 [0 +++ 0, + - ++ 0, + 0- + 0, + 00-0]
15 2 5 [0 ++++, + - +++, +0 - ++, + 00- +, + 000-]

Aquí, al comienzo de la línea, hay un número, seguido de su dificultad (el número mínimo de elementos distintos de cero en el circuito), luego el número de circuitos y, finalmente, una lista de circuitos.

En el esquema, + denota 1, 0 - 0 y - - -1. El trit mayor de la izquierda (como en la ortografía habitual de los números).

La tabla muestra, en primer lugar, que solo los números 13 y 11 tienen dificultad 3 (el máximo para números de 4 bits, como se demostró anteriormente). Y en segundo lugar, que el número de esquemas diferentes para cada número es bastante grande. Esto sugiere, en primer lugar, que la multiplicación es más frecuente, la operación es mucho más simple de lo que nos enseñaron en la escuela. Y en segundo lugar, que para la implementación de dispositivos para multiplicar por varias constantes utilizando recursos de cristal comunes, la elección de los circuitos es bastante grande. Aún más interesantes son los datos sobre números más largos. Entonces, para números de 14 bits, la dificultad máxima es 8. Y el número máximo de circuitos es 937.

Todo estaría bien, pero el algoritmo anterior es demasiado caro. Su complejidad crece a medida que $$$3 ^ n$dependiendo de la longitud de los números n . Para 8 dígitos cuenta al instante. Por 14 minutos. Por 16 horas. Si necesita leer los circuitos PARA TODOS los números de n bits, por desgracia, no se puede hacer nada más que reescribirlo en C y tomar una computadora más potente. Sin embargo, el algoritmo está perfectamente paralelo y ciertamente puede ejecutarse en la GPU o en el clúster.

Para el diseño de piezas de hierro específicas, generalmente se requieren listas de esquemas para números específicos. Y TODO es deseable, y no solo óptimo. Para cuál elegir puede depender de las circunstancias (por ejemplo, un dispositivo para multiplicar por varias constantes). Y aquí puedes ofrecer un algoritmo mucho más humano. Una vez más, recordamos la notable igualdad: $$$2 ^ k + 2 ^ {k-1} + .... + 2 + 1 = 2 ^ {k + 1} -1$.

En el contexto de la tarea, esto significa lo siguiente. Supongamos que se conocen varios esquemas de trit senior. Todos los trits menores que comienzan en la posición k son desconocidos y anteriormente se consideraban iguales a cero. Luego, cambiando los trits desconocidos de cualquier manera, cambiaremos el valor del circuito en no más de más / menos $$$2 ^ {k + 1} -1$. Además, con el avance a los trits más bajos, el valor de esta incertidumbre disminuye. Esto le permite buscar esquemas por aproximaciones sucesivas, trit tras trit.

Deje que se dé un número positivo A. Necesitamos encontrar todos los esquemas para ello entre los números de n bits. El valor absoluto de la diferencia entre A y el valor de cierto circuito se llama error del circuito. Para comenzar, tomamos un esquema de n + 1- bits que describe números de n bits, todos los cuales son desconocidos y se establecen inicialmente iguales a cero. Y comencemos a definir trits, uno por uno, comenzando por el más antiguo. En la posición k- ésima, el circuito puede generar tres nuevos patrones, con valores del k- ésimo trit 1, 0 y -1. Dejamos en la lista de esquemas para continuar solo aquellos cuyo error no excede $$$2 ^ k-1$. Con la lista resultante de circuitos, pasemos al paso en la posición k-1 . Por lo tanto, en la lista resultante (en la posición 0) habrá TODOS los esquemas posibles cuyo valor sea A. Escribamos tal función calcSchemes.


Y finalmente, la venta prometida de sueños.

En ese proyecto, había dos coeficientes que debían multiplicarse: 16351 y 16318. Usando calcSchemes, encontramos los esquemas para estos coeficientes:


Tenemos suerte! Ambos factores tienen dificultad 3. Elegimos los esquemas óptimos para ambos:
Para 16318 + 0000000-0000-0 y para 16351 - + 00000000-0000- . ¡Tuvimos suerte de nuevo! Presta atención a las colas de los esquemas. Para 16318 y 16351 difieren solo por un desplazamiento a la izquierda en una posición. Entonces, el dispositivo que se multiplica por 16318 y 16351 incluye solo un multiplexor adicional, que cambia el operando desplazado y no desplazado en la entrada del sumador.

Veamos el resultado. Escribimos en veril tres opciones para el dispositivo de multiplicación por 16318 y 16351:

1. Opción "Escuela" (solo adiciones y turnos)
2. Circuito óptimo
3. Esquema óptimo utilizando recursos compartidos.

Para las tres opciones, realizamos la síntesis y vemos cuántos recursos de cristal se gastarán en cada una de ellas.


Las tres opciones funcionan correctamente, multiplicándose en 0 en la entrada s por 16318, y en 1 en 16351. Al mismo tiempo, yosys da 488 celdas para la versión escolar, 206 para la versión óptima y 202 para la variante con recursos compartidos. se optimiza, aunque todavía hay una diferencia en 4 celdas. Como puede ver, la diferencia con la opción de escuela es muy decente.

Bueno, por fin. Quizás, parecería innecesario que alguien cercara un jardín así, solo para darse cuenta de que 16318 = 16384-64-2 y 16351 = 16384-32-1. Sin embargo, en primer lugar, los números pueden ser más complicados. En segundo lugar, si el dispositivo debe multiplicar varios números, no es obvio que se tomen esquemas óptimos. Tuve suerte en ese proyecto. En general, un programa de búsqueda de circuitos puede ayudar mucho. Espero que el artículo sea útil para alguien. Y el que lo leyó, espero que no entre en pánico si necesita multiplicar, pero no hay multiplicador.