“Entropía, una fuente ergódica, un espacio de mensaje multidimensional, bits, polisemia, el proceso de Markov: todas estas palabras suenan muy impresionantes, en cualquier orden en que se coloquen. Si los organiza en el orden correcto, adquieren un cierto contenido teórico. Y un verdadero especialista a veces puede encontrar una solución a los problemas prácticos cotidianos con su ayuda ".
John PIRS "No veo mal"
Esta publicación está llena de discusiones sobre la sutil optimización de las operaciones matemáticas en MK con recursos limitados, así como evaluaciones subjetivas de varios aspectos del desarrollo de software embebido.
Aquellos a quienes esta advertencia no asustó, les pregunto debajo del gato.
Antes de continuar describiendo el procedimiento para extraer una raíz cuadrada de un número entero, la operación inversa a la cuadratura y, en consecuencia, la multiplicación, hablemos de esto último.
Supongamos que tenemos la oportunidad de multiplicar un número de 8 bits por un número de 8 bits, obteniendo un resultado de 16 bits (8 * 8 = 16), ¿cómo podemos obtener la implementación de la operación 16 * 16 = 32 basada en esta operación? La forma obvia es representar 16 como la suma de dos 8, entonces obtenemos
(16)*(16)=(1(8)*256+2(8))*1(8)*256+2(8)) =1*1*256*256+1*2*256+2*1*256+2*2Si en la expresión resultante reemplazamos la multiplicación por 256 por un desplazamiento a la izquierda por 8 dígitos, entonces obtenemos un algoritmo completamente funcional. Calculemos el tiempo dedicado a la implementación: necesitamos 4 multiplicaciones de 8 * 8 = 16 y 4 adiciones de números de 4 bytes 32 + 32 = 32. Para AVR tipo MK, obtenemos 4 * 2 + 4 * 4 = 24 ciclos, pero esto es para una solución de "frente". Intentemos mejorar el resultado. El hecho de que no necesitemos 4, sino 3 adiciones y una asignación, simplifica un poco la situación, ya que no se requiere la puesta a cero inicial del resultado, pero aún no lo tomamos en cuenta, aunque era necesario y el tiempo total debería ser 24 + 4 = 28 ciclos. Pero, si tenemos en cuenta la presencia de un cambio en los primeros tres términos (respectivamente, tenemos que el bajo (dos bytes bajos) es cero y no tiene sentido agregarlo al resultado), entonces tendremos que agregar no 4 bytes, sino tres y dos, lo que reducirá tiempo de ejecución para 1 * 2 + 2 = 4 medidas y obtener 20 medidas. Además, podemos prestar atención al hecho de que el primer y el último término no se cruzan en absoluto, lo que nos permite reemplazar la puesta a cero de la mitad más alta del resultado con la asignación del primer término y reducir el tiempo de ejecución en otros 2 ciclos de reloj a 18. Además, usando las características arquitectónicas, es decir, la presencia del comando de transferencia de registro pares, guardar dos medidas más y el resultado final - 16 medidas en lugar de las 28 originales - un poco, pero agradable.
Métodos de optimización similares funcionan para la operación 32 * 32 = 32, para lo cual puede reducir el tiempo de ejecución de los 4 * 4 * (2 + 4) + 4 = 100 ciclos de reloj esperados a (3 + 5 + 4 + 3) + (5 + 3 +3) + (4 + 3) + 3 = 36 medidas, lo cual no está nada mal. Bueno, al final de la consideración de varias opciones para la multiplicación, notamos que 16 * 16 = 16 se puede obtener en 3 + 3 + 3 = 9 ciclos. Tenga en cuenta que todas estas consideraciones son válidas solo bajo el supuesto de que hay una operación 8 * 8 = 16 para 2 medidas, y si no está en el objetivo MK, el tiempo de ejecución de todas las demás versiones de la operación definitivamente no será más rápido.
Resumamos el tiempo requerido para realizar la multiplicación (8 * 8 = 8 2, 8 * 8 = 16 9, 16 * 16 = 16 16, 16 * 16 = 32 36) y ahora consideremos el problema original.
Necesitamos extraer la raíz entera cuadrada del número de 32 bits H, es decir, encontrar el número de 16 bits más grande n tal que n * n <= H. Todos los del curso de secundaria conocemos el método de aproximación sucesiva a la raíz cuadrada (n = (N / n '+ n) / 2), pero al usarlo tendremos que dividir los enteros, y esta es una operación que requiere mucho tiempo.
Por lo tanto, se desarrollaron otros esquemas de cálculo, uno de los cuales es el método de aproximación a nivel de bits, que en el pseudocódigo tiene el siguiente aspecto:
- valores iniciales -> n = 0; b = 0x8000;
- realizar 16 veces -> if ((n + b) * (n + b)> = H) n = n + b; b = b >> 1;
Puede estimar inmediatamente el tiempo dedicado a esta opción 16 (el número de bits del resultado) * (2 (organización del ciclo) +2 (suma) + X (multiplicación) +5 (comparación y solución) +2 (modificación del resultado) / 2 (promedio medio tiempo) +2 (cambio de bit)) = 16 * (12 + X). Pregunta por qué en la fórmula X en lugar del número 16, y resulta que nos esperaba una emboscada, ya que estamos escribiendo en C, y no en ensamblador. El hecho es que en la biblioteca estándar no hay operación de multiplicación con un cambio en la profundidad de bits y no podemos aplicar 16 * 16 = 32, pero estamos obligados a usar 32 * 32 = 32, lo que lleva a X = 36 en lugar de X = 16 y la cifra final es 16 * 48 = 768 ciclos de reloj para extraer el valor entero de la raíz cuadrada de un número de 32 bits.
Por supuesto, esto es mucho mejor que el método de Newton, pero un poco más, veamos qué se puede hacer.
Por lo tanto, es obvio que la mayor parte del tiempo se gasta en calcular el siguiente resultado de multiplicación. Por supuesto, puede reescribirlo en ensamblador y usar la versión menos costosa de la multiplicación, obteniendo 16 * (12 + 16) = 448 ticks, pero lo dejaremos de esta manera como último recurso. Considere el proceso con más cuidado y vea que no calculamos la multiplicación de un número aleatorio por sí mismo, sino más bien la multiplicación del valor anterior con algún aumento, y se conoce el cuadrado del valor anterior. Por lo tanto, podemos recurrir a un esquema de diferencia basado en la fórmula (n + b) * (n + b) = n * n + 2 * n * b + b * b. A primera vista, parece una burla: en lugar de una multiplicación, necesitamos hacer cuatro piezas e incluso dos sumas de números largos (32 bits). Pero empecemos a entender: ya tenemos n * n, b * b teniendo en cuenta que b = b '/ 2 es fácil de obtener, como b' * b '/ 4, y de manera similar 2 * n * b = 2 * n * b '/ 2.
Surge el siguiente esquema de cálculo:
- valores iniciales -> nn = 0; n = 0; b = 0x8000; bb = b * b;
- repetir 16 veces -> if (nn + n + bb> = H) {n = n + b; nn = nn + bb + n}; bb >> 2; b> 1;
Estimamos los costos de implementación 16 * (2 (organización del ciclo) +12 (asignación y dos adiciones) +5 (comparación y solución) + (2 (adición) +8 (dos adiciones)) / 2 (medio tiempo promedio) +8 (cambio a la derecha por 2) +2 (cambio a la derecha) = 16 * 34 = 544 ciclos de reloj. Mejor que con una multiplicación incorrecta de 32 * 32, pero todavía tenemos reservas.
¿Qué son? - prestemos atención a la operación más costosa - agregando y comparando un total de 17 ciclos de reloj y rehaciendo el ciclo principal del algoritmo:
2. repetir 16 veces -> T = H-bb-n; si (T> = 0) {H = T; n = n + b);}; bb >> 2; b> 1;
Entonces el tiempo de ejecución del ciclo será 16 * (2 (organización del ciclo) +12 (cálculo de la nueva diferencia) +1 (comparación y solución) + ((4 (asignación) +2 (suma)) / 2 (medio tiempo promedio) +8 +2) = 16 * 28 = 448 ciclos, si tiene en cuenta las peculiaridades de la arquitectura, puede guardar otros 2 + 2 = 4 * 16 = 64 ciclos y mantenerlos en menos de 400 ciclos.
Obtenemos incluso un resultado ligeramente mejor, como cuando se usa la multiplicación correcta 16 * 16 = 32, pero sin ensamblador, "en C puro". Sin embargo, hay una desventaja significativa: si todo es intuitivo en la versión con multiplicación, entonces la variante con un esquema de diferencia sin comentarios da la impresión de una sesión de magia negra, debe elegir. Tenga en cuenta también que intercambiamos el número de medidas para memoria adicional para variables intermedias, lo que generalmente ocurre.
Nota necesaria: no obtuvimos una ganancia significativa (a veces) en comparación con las multiplicaciones, ya que tenemos una implementación rápida de 8 * 8 = 16. Si está ausente en el MK (y esto sucede) o no es tan rápido (y esto también sucede), entonces el esquema de diferencia se vuelve varias veces más rápido, ya que solo utiliza operaciones de suma y cambio estándar, que están garantizadas en cualquier MK.
Parecía que no funcionaría mejor, pero resulta que todavía hay reservas para aumentar el rendimiento del algoritmo. Intentemos usar otro método clásico de aceleración: dividir y conquistar. ¿Qué sucede si primero extrae la raíz cuadrada de la mitad anterior del argumento y luego la refina? En primer lugar, mostramos que esto es fundamentalmente posible. De hecho, presentamos el argumento en la forma H = H '<< 16 + H' 'y el resultado en la forma n = n' << 8 + n ''. Como n '' <256, entonces su cuadrado obviamente será menor que el cuadrado del número n = n '<< 8 + 256 = (n' + 1) << 8. Se deduce que la parte más alta del resultado no excede la raíz cuadrada de la parte más alta del argumento.
La implementación de este enfoque se deja al lector curioso.
¿Qué nos dará este enfoque, porque el número total de iteraciones permanecerá sin cambios? Podemos llevar a cabo la primera mitad de iteraciones con números de menor longitud, y esto conduce a una disminución en los costos de tiempo. Este enfoque se puede aplicar a la variante con multiplicación y la variante de diferencia, la ganancia total será de hasta un cuarto del tiempo total de ejecución.
Nota necesaria: la aplicabilidad de este enfoque no es del todo obvia, cuando se implementa para MK como AVR, la aceleración de ejecución tiene lugar, pero para algunas arquitecturas, por ejemplo para x86, la desaceleración de la operación apareció inesperadamente. Aparentemente, trabajar con datos no nativos (16 bits) en esta arquitectura es significativamente más costoso en el tiempo que con los nativos (32 bits). No realicé un estudio profundo, pero el hecho sí tuvo lugar y debo informarlo para evitar malentendidos.
Pero eso no es todo. Como ya nos hemos embarcado en el camino de la separación y el dominio, entonces, ¿por qué no ir más allá? Extraiga la raíz de los bits paso a paso, comenzando con los más antiguos (comenzar con los más jóvenes es contraproducente en nuestro caso). El esquema del algoritmo es el mismo: agregamos la siguiente porción de bits en el resultado actual e intentamos agregar el siguiente bit al resultado, verificando si hemos ido más allá del valor raíz. La peculiaridad es que solo podemos verificar los bits altos del argumento, hasta que lleguemos a los bits bajos.
Al implementar, utilizamos un truco más: en lugar de mover nuestros números restados a la derecha, moveremos nuestro argumento disminuido a la izquierda, el significado no cambia y la velocidad aumenta. Aumenta debido a dos factores: 1) es suficiente para nosotros restar solo números de 16 bits (hay una peculiaridad, y debe tenerse en cuenta, pero estamos considerando un estudio de caso, vout) y 2) no necesitamos cambiar el cuadrado del siguiente bit, ya que siempre será igual a uno Pero tiene que pagar por todo en este mundo y tendremos un desplazamiento de la diferencia extendida (6 bytes) a la izquierda, y 2 bits por reloj. Nos fijamos en el pseudocódigo
- valores iniciales -> n = 0; H1 = 0;
- repetir 16 veces -> (H1, H) << 2; T = H1-n-1; si (T> 0) {H1 = T; n = n + 2}; n << 1;
y evaluar el tiempo de ejecución, obteniendo 16 * (12 (turno extendido) +4 (calculando la diferencia) +1 (solución) +2 (asignación) +1 (aumento) +2 (turno)) = 16 * 22 = 352 medidas, quizás , el resultado es casi perfecto. Al implementar esta opción, existen pequeños inconvenientes, lo dejo nuevamente al lector curioso (bueno, él consigue el trabajo).
Bueno, en conclusión de la sección que me impulsó a escribir esta publicación. Existe una biblioteca McuCpp completamente maravillosa, creada por Anton Chizhov, en la que, basándose en la clase de autoría loki, Andriescu es inusualmente elegante (bueno, en la medida en que la elegancia se puede aplicar a las plantillas C ++), trabaje con pines <a «
github.com/KonstantinChizhov/ Mcucpp »Tengo un gran respeto por el autor mencionado (ambos) y recientemente, en relación con las circunstancias, que discutiré más adelante, miré las fuentes de esta biblioteca y una vez más admiré.
Sin embargo, entre otros archivos vi template_utils.h, en el que se implementaron algunas rutinas auxiliares, y entre ellas una raíz entera de un número de 32 bits. El hecho de que utilice el algoritmo de aproximación secuencial más simple con la multiplicación no da miedo, ya que este algoritmo no pierde tanta velocidad, pero en la comprensibilidad da muchos puntos por delante y aún gana. Pero realmente no me gustó el hecho de que se implementó de manera algo imprecisa (en términos de rendimiento), porque "los niños pueden verlo". La inexactitud consiste en representar el número seleccionado con 32 bits, porque sabemos firmemente que la raíz del número de 32 bits no irá más allá de 16 bits, entonces, ¿por qué necesitamos cambiar los bytes cero? Y este es exactamente el caso cuando el compilador mismo nunca adivinará llevar a cabo la optimización y debería ayudarlo.
Obvia conversión de funciones
static inline uint32_t sqrt(uint32_t value) { uint16_t result = 0; uint16_t add = 0x8000; for (uint8_t i = 16; i !=0; ++i) { uint32_t rootGuess = result | add; uint32_t guess = rootGuess * rootGuess; if (value >= guess) { result = rootGuess; } add >>= 1; } return result; }
nos permite guardar 2 ciclos en un cambio de bit y 2 ciclos al crear el siguiente factor en cada ciclo, y organizar el ciclo en la forma indicada son otros 4 ciclos (sé que el compilador puede hacer tal optimización para nosotros, pero ¿por qué no ayudarlo explícitamente? ), que es bastante bueno para los cambios de código puramente cosméticos que no afectan en lo más mínimo su comprensión.
Nota posterior: un comentario me hizo pensar que sería más correcto
for (uint_fast8_t i= ...)
Gracias Oleg por la ayuda.
La guinda del pastel es la función de extraer toda la raíz cuadrada del número de signo que se encuentra justo debajo, que dice ser √-1 = 65635 = -1. Por otro lado, ¿por qué no, lo que es peor que cualquier otro resultado, esto no es una excepción para nosotros? causa en MK, y no existe toda la raíz cuadrada de un número negativo.
Bueno, la conclusión sobre por qué recurrí a la biblioteca de Anton Chizhov. Una reciente publicación sobre el RTOS nacional para MK me impulsó con el nombre MAX (Sistema coherente multiagente): vea el epígrafe de la publicación anunciada por sus creadores y que ha sido portado a MK producido por Milander. Nota: esta publicación no es material promocional y pronto quedará claro para los lectores. De los autores de mcucpp antes mencionados del sistema operativo, utilizamos la implementación de un buffer de anillo (sin disminuir en absoluto las ventajas de la biblioteca Anton, debo decir que esta parte no es una referencia, y esta sigue siendo una formulación suave, sobre la cual escribí en otra publicación que no publicaré en absoluto). Como trabajo en estrecha colaboración con las instalaciones de producción de Milander, el material me interesó y seguí el enlace al sitio web de los desarrolladores.
Aquí comienza el próximo grito de Yaroslavna.
El año pasado, cuando se anunció por primera vez la creación del RTOS nacional, descargué una descripción del producto de software de este sitio, pero de alguna manera mis manos no llegaron al estudio. Por la naturaleza de mi actividad, tengo que tratar con componentes domésticos (entiendo lo suficiente ...), por lo que sería bueno tener el software adecuado. Recordando cómo en el lanzamiento del año pasado, el director de la compañía habló sobre los millones de rublos gastados en el desarrollo y el gran equipo que trabaja en la creación de este producto de software, decidí ver la versión de prueba disponible para descargar de forma gratuita, y aquí estoy compartiendo los resultados.
Para comenzar, la descripción de medio año casi se ha reducido a la mitad en volumen (de 115 a 55 páginas), y si la desaparición de las aplicaciones con capturas de pantalla que describen el proceso de lanzamiento de terceros productos de la "Descripción del programa" es bienvenida, entonces no aparece la aparición de estos materiales (cuya creación Pasé, aunque no muy significativo, pero aún así tiempo y dinero) en un documento como "Guía del operador" Personalmente estoy perplejo. Además, en la primera oración del documento, vemos una franca desviación de la verdad, ya que RTOS en sí mismo no tiene la intención de "crear programas" de ninguna manera, por alguna razón los autores no se permitieron tales declaraciones en la versión anterior del documento, se siente la influencia del servicio de marketing. También ofrece que si la descripción solía estar en la carpeta / docs del directorio raíz, y esto era lógico, ahora está oculto en / toolchain / macs / docs, bueno, como dijeron en mi juventud, "todos están locos a su manera", seguimos adelante.
Empiezo a mirar la descripción, mirando el código fuente (se incluye amablemente en la versión de prueba) y en el desconcierto encuentro la ausencia de controladores de dispositivos periféricos adaptados para trabajar con este sistema operativo. Primero sugerí que esta es una característica de la prueba, luego, en el foro, en la información de los desarrolladores, descubrí que realmente no hay controladores, pero están trabajando en ello. Más de seis meses (seis meses, Carl, en realidad cerca de un año) desde el momento en que se lanzó el sistema operativo para MK, y trabajan en los controladores. Naturalmente, o como dicen, no hace falta decir que no se puede hablar de ningún tercer producto (sistema de archivos, pila de red, pila USB). Una idea divertida de los autores sobre los requisitos para el desarrollo de software para MK, está bien, volvió a conducir.
Es decir, el sistema operativo declarado, cuya característica destacada es la organización de la interacción dentro de un sistema de controlador múltiple, no tiene medios nativos para organizar esta interacción. Lo que tenemos en el resultado final, y tenemos administración de tareas, en realidad un planificador, un servicio de tiempo mínimo y medios para sincronizar tareas, y eso es todo, divertido, por decir lo menos. Bien, buscaremos más allá, incluso en un conjunto de componentes de este tipo, son posibles soluciones interesantes, especialmente cuando consideras que en un sitio (no en la compañía del fabricante) vi un "examen" del código fuente de este sistema operativo por referencia. Este documento dice que el producto de software no utiliza componentes de terceros (importación) y es original, sería necesario asegurarse.
La primera observación es que si usa archivos ARM originales incluidos en el paquete de código fuente para portar a una arquitectura Cortex-M0 específica (BE1T de 1986), entonces esto es muy similar al uso de fragmentos de texto de terceros (importados), personalmente creo que este es el uso, pero Probablemente no lo sé todo. Bueno, y en segundo lugar, el código fuente del programador y los componentes de gestión de tareas relacionados es realmente original y no tiene análogos (al menos no sé ninguno), pero este es el tipo de originalidad cuando recuerdo la frase del viejo chamán de la película "El espíritu maligno de Yambuya" sobre el gran cazador: "Cortar las orejas, cocinar y comer, ¿lo habrías adivinado?"
Trataré de explicar: en el diseño del sistema operativo en general y en el RTOS en particular, uno de los problemas complejos es la cuestión de garantizar el acceso de todos los procesos del sistema a un recurso compartido: tiempo de ejecución del procesador. , ( ) , . ( , , MPU), .
, , , , . (1) , , FREE-RTOS 20 , ( , , ).
, , 60 ( ). , . ( ) , (, ) ,
- (n)
- — , 20*(3*4)=240 . , , , .
, , ( , , ) . , ( , ). mcucpp ( — ), .
— - , .
(, , ) - — . ( , , ), , ( 2013) 1 , 2019 .
, :
- ( , ) ( , , , , ),
- ( ),
- () 2,
- HAL, CMSIS (- ),
- ,
- ,
- (3rd part), ,
- ,
- ,
- , (, , ..) « »,
- , , ( , , MIT , « »), , (?).
, , , 5 ( , , 10, IDE). , , .
, , , .
, , () .