Tuvimos la oportunidad de realizar un ejercicio táctico pequeño pero extremadamente interesante.
En el proceso de investigación de un nuevo MK de una empresa conocida basada en la arquitectura Cortex-M4 (definitivamente escribiré sobre esto más adelante), surgió la pregunta de qué tan rápido puede funcionar la operación de división entera en la implementación de hardware. El experimento a gran escala dio un resultado algo inesperado: dividir un número de 32 bits por un número de 32 bits se realiza en 3 ciclos de reloj de la frecuencia del procesador, bueno, no importa lo rápido que sea. Resultó que esto ocurre solo con ciertos operandos, pero estudios posteriores han demostrado que nunca el tiempo para completar la división no excede las 7 medidas. Los resultados obtenidos causaron un ligero apuro ("y esta no es una determinada forma de hablar, que no sabe lo que significa, sino un verbo muy específico" - Divov, como siempre, es incomparable).
Bueno, no puedes simplemente tomar y dividir rápidamente números tan largos, es extraño así, pero los hechos son obstinados. Me imaginé la imagen de que el presidente de la Federación de Rusia me llamaría a él mañana y me planteaba la tarea de hacer que MK no fuera peor que la de ARM (estoy de acuerdo en que la imagen es delirante, pero no sucede en el mundo), pero lo miro desconcertado y entiendo que No podré hacer una división de tales números en ese tiempo, y no cumpliré con las expectativas que se me imponen (bueno, de hecho, siempre puedo comprar una licencia silenciosamente de ARM y pretender que inventé todo yo mismo, muchos lo hacen, pero El PIB espera algo completamente diferente de mí, y luego, puedo engañarlo, pero es poco probable que lo haga).
Y estaba triste porque los muchachos de ARM son mucho más inteligentes que yo, y busqué ansiosamente en Internet para ver cómo lo hacen. No encontré ninguna información sobre el tiempo de ejecución en el sitio web de ARM, en uno de los materiales en STM32 se indicó que la división toma de 2 a 7 ciclos de reloj, que corresponde a las observaciones, pero no hay información sobre cómo se hace esto.
En general, el Internet omnipotente no ayudó mucho, hay trucos con división por constante, escribí sobre ellos en una de las publicaciones, pero tenemos una situación diferente, existe el algoritmo de Newton y su versión acelerada, pero claramente este no es el caso, hay un algoritmo basado en Transformada de Fourier, pero esto es para números muy grandes y es poco probable que se complete en 7 ciclos incluso en la arquitectura ARM. Tuve que idearlo yo mismo y se encontró una solución, tan simple y obvia que se vuelve un poco vergonzoso el hecho de que esto no se hizo inmediatamente después de que se formuló la tarea.
Antes de ver mi decisión, le sugiero que encuentre la suya y luego la compare con la mía, y si difieren, los espero en los comentarios.
Entonces, ¿cómo dividimos rápidamente (en no más de 7 ciclos) dos números de 32 bits para obtener un resultado de 32 bits.
Para empezar, recordamos cómo la división en aritmética binaria se lleva a cabo generalmente en
forma clásica El algoritmo es bastante simple y directo: restamos el divisor del dividendo. Si el resultado no es negativo (dividimos los números sin signo), entonces hacemos que el siguiente dígito del resultado sea igual a uno y consideremos el resultado como el próximo dividendo; de lo contrario, el siguiente bit del resultado es 0. Antes de la siguiente medida, dividimos a la mitad el divisor (ya sea desplazándolo hacia la derecha o desplazar el dividendo a la izquierda) y reducir el peso de la broca en 2 veces (por cambios similares). Por lo tanto, obtenemos un bit del resultado en un ciclo de reloj y toda la operación durará 32 ciclos de reloj. Todavía hay un cambio inicial en este proceso, pero no afecta la evaluación de la situación en su conjunto. Vamos a acelerar, pero ¿cómo?
Observamos que el algoritmo resultante se parece mucho al funcionamiento de un ADC con una aproximación secuencial y recordamos que existen otros métodos de conversión, mucho más rápidos: conversión paralela. ¿Y si ...
Restaremos del divisor no solo el dividendo, sino el dividendo * 2 y el dividendo * 3 (al mismo tiempo, en tres sumadores), luego obtendremos tres bits (signos de resultados) de la información, que toman 4 valores diferentes, por lo que puede extraer 2 bits de ellos a la vez resultado. A continuación, extrapolamos un enfoque similar para 3.4.5 bits del resultado.
Para obtener 5 bits de información por ciclo, necesitamos 31 sumadores, en cada uno de los cuales se realizará la operación Dividend-Divisor * n (1-31), los signos del resultado se pasan a través del codificador e inmediatamente recibiremos 5 bits del resultado. Luego cambiamos el dividendo por 5 dígitos a la izquierda y repetimos hasta que esté listo. Entonces necesitamos 32/5 = 6.4 => 7 medidas para completar la operación.
Para trabajar, necesitamos 31 + x sumadores, parece ser mucho, pero ya los tenemos, porque tenemos una operación de multiplicación de 32 * 32 por ciclo, y para implementarlo no podemos prescindir de 32 sumadores (bueno, creo que sí ... ), para que ya tengamos el equipo necesario, la única pregunta es construir un circuito de control y un montón de multiplexores para realizar un cambio rápido, pero esto es completamente solucionable.
Entonces, la tarea de dividir en 7 pasos se ha resuelto, la pregunta sigue siendo: ¿cómo puede reducirse este tiempo? Porque en el MK estudiado puede ser menor que 7. La solución es determinar el número del dígito más significativo del dividendo (C) y el divisor (C) en la etapa de preparación del algoritmo. inmediatamente quedará claro cuántos bits altos del cociente son iguales a cero, de modo que podamos omitir la primera o varias fases del algoritmo. Por ejemplo, si C <3, entonces el resultado es inmediatamente cero y completamos la operación, seguro que puede derivar una fórmula para el número de medidas, pero ya estaba aburrido.
Curiosamente, la operación udiv solo da el cociente, aunque el resto obviamente permanece en algún lugar dentro. En principio, no es difícil obtenerlo en dos pasos, que se realizó en el fragmento estudiado del código de la máquina ejecutando el divisor Divisible-Private * de pseudocódigo, pero esto es para cualquier 2 pasos, ¿por qué no darlo inmediatamente en el par de registro? No sé la respuesta a esto. una pregunta
En general, conozca el PIB, dígale que definitivamente haremos la división en MK si aún le interesa.
PD: Por cierto, cuando estaba buscando KDPV (como notaron, no lo encontré), noté uno con la inscripción francamente incorrecta "No debe dividir por cero". Debo decir con certeza que es posible dividir por cero, no se puede dividir. Pero en serio, en diferentes arquitecturas se dividen entre cero de manera diferente, en x86 obtenemos una excepción (este es un error inolvidable 200), en algunos obtenemos un dividendo o cero, pero nunca he visto el número entero máximo. En ARM n / 0 = 0/0 y resulta 0.