Sur la question de la multiplication, de l'extraction des racines carrées, de la substitution des importations et de l'entreprise Milander

«L'entropie, une source ergodique, un espace de message multidimensionnel, des bits, la polysémie, le processus de Markov - tous ces mots semblent très impressionnants, quel que soit l'ordre dans lequel ils sont placés. Si vous les arrangez dans le bon ordre, ils acquièrent un certain contenu théorique. Et un vrai spécialiste peut parfois trouver une solution aux problèmes pratiques quotidiens avec son aide. »

John PIRS "Je ne vois aucun mal"

Ce poste est plein de discussions sur l'optimisation subtile des opérations mathématiques sur MK avec des ressources limitées, ainsi que des évaluations subjectives de divers aspects du développement de logiciels embarqués.

Ceux que cet avertissement n'a pas effrayés, je demande sous cat.

Avant de décrire la procédure d'extraction d'une racine carrée d'un entier, l'opération inverse de la mise au carré et, en conséquence, la multiplication, parlons de cette dernière.

Supposons que nous ayons la possibilité de multiplier un nombre 8 bits par un nombre 8 bits, obtenant un résultat 16 bits (8 * 8 = 16), comment pouvons-nous obtenir la mise en œuvre de l'opération 16 * 16 = 32 basée sur cette opération. La façon évidente est de représenter 16 comme la somme de deux 8, alors nous obtenons

(16)*(16)=(1(8)*256+2(8))*1(8)*256+2(8)) =1*1*256*256+1*2*256+2*1*256+2*2

Si dans l'expression résultante nous remplaçons la multiplication par 256 par un décalage à gauche de 8 chiffres, alors nous obtenons un algorithme complètement fonctionnel. Estimons le temps passé sur la mise en œuvre - nous avons besoin de 4 multiplications de 8 * 8 = 16 et de 4 additions de nombres à 4 octets 32 + 32 = 32. Pour l'AVR de type MK, nous obtenons 4 * 2 + 4 * 4 = 24 cycles, mais c'est pour une solution «frontale». Essayons d'améliorer le résultat. Le fait que nous ayons besoin non pas de 4, mais de 3 ajouts et d'une affectation simplifie quelque peu la situation, car la remise à zéro initiale du résultat n'est pas requise, mais nous n'en avons toujours pas tenu compte, bien que cela ait été nécessaire et que le temps total devrait être de 24 + 4 = 28 cycles. Mais, si nous prenons en compte la présence d'un décalage dans les trois premiers termes (respectivement, nous avons que le bas (deux octets bas) est nul et il est inutile de l'ajouter au résultat), alors nous devrons ajouter non pas 4 octets, mais trois et deux, ce qui réduira temps d'exécution pour 1 * 2 + 2 = 4 mesures et obtenez 20 mesures. De plus, nous pouvons faire attention au fait que les premier et dernier termes ne se croisent pas du tout, ce qui nous permet de remplacer la mise à zéro de la moitié supérieure du résultat par l'attribution du premier terme et de réduire le temps d'exécution de 2 cycles d'horloge à 18. De plus, en utilisant les fonctionnalités d'architecture, à savoir la présence du transfert de registre paires, enregistrez deux mesures supplémentaires et le résultat final - 16 mesures au lieu des 28 originales - une bagatelle, mais agréable.

Des méthodes d'optimisation similaires fonctionnent pour l'opération 32 * 32 = 32, pour laquelle vous pouvez réduire le temps d'exécution des 4 * 4 * (2 + 4) + 4 = 100 cycles d'horloge attendus à (3 + 5 + 4 + 3) + (5 + 3 +3) + (4 + 3) + 3 = 36 mesures, ce qui n'est pas mal du tout. Eh bien, à la fin de l'examen de diverses options de multiplication, nous notons que 16 * 16 = 16 peuvent être obtenus en 3 + 3 + 3 = 9 cycles. Notez que toutes ces considérations ne sont valables que sous l'hypothèse qu'il existe une opération 8 * 8 = 16 pour 2 mesures, et si elle n'est pas sur le MK cible, le temps d'exécution de toutes les autres versions de l'opération ne deviendra certainement pas plus rapide.

Résumons le temps nécessaire pour effectuer la multiplication (8 * 8 = 8 2, 8 * 8 = 16 9, 16 * 16 = 16 16, 16 * 16 = 32 36) et considérons maintenant le problème d'origine.

Nous devons extraire la racine entière carrée du nombre 32 bits H, c'est-à-dire trouver le plus grand nombre 16 bits n tel que n * n <= H. Nous tous du lycée connaissons la méthode d'approximation successive de la racine carrée (n = (N / n '+ n) / 2), mais lors de son utilisation, nous devrons diviser les nombres entiers, ce qui prend beaucoup de temps.

Par conséquent, d'autres schémas de calcul ont été développés, dont l'un est la méthode d'approximation au niveau du bit, qui dans le pseudo-code ressemble à ceci:

• valeurs initiales -> n = 0; b = 0x8000;
• effectuer 16 fois -> si ((n + b) * (n + b)> = H) n = n + b; b = b >> 1;

Vous pouvez immédiatement estimer le temps passé sur cette option 16 (le nombre de bits du résultat) * (2 (organisation du cycle) +2 (addition) + X (multiplication) +5 (comparaison et solution) +2 (modification du résultat) / 2 (moyenne mi-temps) +2 (décalage de bits)) = 16 * (12 + X). Vous demandez pourquoi dans la formule X au lieu du nombre 16, et il s'avère qu'une embuscade nous attendait, puisque nous écrivons en C, et non en assembleur. Le fait est que dans la bibliothèque standard, il n'y a pas d'opération de multiplication avec un changement de profondeur de bits et nous ne pouvons pas appliquer 16 * 16 = 32, mais nous sommes obligés d'utiliser 32 * 32 = 32, ce qui conduit à X = 36 au lieu de X = 16 et le chiffre final est 16 * 48 = 768 cycles d'horloge pour extraire la valeur entière de la racine carrée d'un nombre 32 bits.

Bien sûr, c'est beaucoup mieux que la méthode Newton, mais un peu beaucoup, voyons ce qui peut être fait.
Il est donc évident que la plupart du temps est consacré au calcul du résultat de multiplication suivant. Bien sûr, vous pouvez le réécrire dans l'assembleur et utiliser la version moins chère de la multiplication, obtenant 16 * (12 + 16) = 448 ticks, mais nous laisserons cette méthode en dernier recours. Considérez le processus plus attentivement et voyez que nous ne calculons pas la multiplication d'un nombre aléatoire par lui-même, mais plutôt la multiplication de la valeur précédente avec une certaine augmentation, et le carré de la valeur précédente est connu. Par conséquent, nous pouvons recourir à un schéma de différence basé sur la formule (n + b) * (n + b) = n * n + 2 * n * b + b * b. À première vue, cela ressemble à une moquerie - au lieu d'une multiplication, nous devons faire quatre pièces et même deux ajouts de nombres longs (32 bits). Mais commençons à comprendre: nous avons déjà n * n, b * b en tenant compte du fait que b = b '/ 2 est facile à obtenir, comme b' * b '/ 4, et de même 2 * n * b = 2 * n * b '/ 2.

Le schéma de calcul suivant émerge:

1. valeurs initiales -> nn = 0; n = 0; b = 0x8000; bb = b * b;
2. répéter 16 fois -> if (nn + n + bb> = H) {n = n + b; nn = nn + bb + n}; bb >> 2; b> 1;

Nous estimons les coûts de mise en œuvre 16 * (2 (organisation du cycle) +12 (affectation et deux ajouts) +5 (comparaison et solution) + (2 (ajout) +8 (deux ajouts)) / 2 (moyenne mi-temps) +8 (décalage à droite de 2) +2 (décalage à droite) = 16 * 34 = 544 cycles d'horloge. Mieux qu'avec une multiplication incorrecte de 32 * 32, mais nous avons encore des réserves.

Quels sont-ils - prêtons attention à l'opération la plus coûteuse - ajoutant et comparant un total de 17 cycles d'horloge et refait la boucle principale de l'algorithme:
2. répéter 16 fois -> T = H-bb-n; si (T> = 0) {H = T; n = n + b);}; bb >> 2; b> 1;
Le temps d'exécution du cycle sera alors de 16 * (2 (organisation du cycle) +12 (calcul de la nouvelle différence) +1 (comparaison et solution) + ((4 (affectation) +2 (ajout)) / 2 (demi-temps moyen) +8 +2) = 16 * 28 = 448 cycles, si vous prenez en compte les particularités de l'architecture, vous pouvez enregistrer encore 2 + 2 = 4 * 16 = 64 cycles et rester dans moins de 400 cycles.

Nous obtenons même un résultat légèrement meilleur, comme lors de l'utilisation de la multiplication correcte 16 * 16 = 32, mais sans assembleur, "en C pur". Cependant, il y a un inconvénient important - si tout est intuitif dans la version avec multiplication, alors la variante avec un schéma de différence sans commentaires donne l'impression d'une session de magie noire, vous devriez choisir. Notez également que nous avons échangé le nombre de mesures contre de la mémoire supplémentaire pour des variables intermédiaires, ce qui se produit généralement.

Remarque nécessaire - nous n'avons pas obtenu un gain significatif (parfois) par rapport aux multiplications, car nous avons une implémentation rapide de 8 * 8 = 16. S'il est absent dans le MK (et cela se produit) ou pas si rapide (et cela se produit également), le schéma de différence devient plusieurs fois plus rapide, car il n'utilise que des opérations d'ajout et de décalage standard, qui sont garanties d'être dans n'importe quel MK.

Il semblait que cela ne fonctionnerait pas mieux, mais il s'avère qu'il existe encore des réserves pour augmenter les performances de l'algorithme. Essayons d'utiliser une autre méthode classique d'accélération - diviser pour mieux régner. Et si vous extrayez d'abord la racine carrée de la moitié la plus ancienne de l'argument, puis l'affinez? Tout d'abord, nous montrons que cela est fondamentalement possible. En effet, nous présentons l'argument sous la forme H = H '<< 16 + H' 'et le résultat sous la forme n = n' << 8 + n ''. Puisque n '' <256, alors son carré sera évidemment inférieur au carré du nombre n = n '<< 8 + 256 = (n' + 1) << 8. Il s'ensuit que la partie la plus élevée du résultat ne dépasse pas la racine carrée de la partie la plus élevée de l'argument.

La mise en œuvre de cette approche est laissée au lecteur curieux.
Que nous apportera cette approche, car le nombre total d'itérations restera inchangé - nous pouvons effectuer la première moitié d'itérations avec des nombres de longueur plus courte, ce qui entraîne une diminution des coûts de temps. Cette approche peut être appliquée à la variante avec multiplication et à la variante de différence, le gain total sera jusqu'à un quart du temps d'exécution total.

Remarque nécessaire - l'applicabilité de cette approche n'est pas du tout évidente, lors de la mise en œuvre pour MK tels que AVR, l'accélération de l'exécution a lieu, mais pour certaines architectures, par exemple pour x86, le ralentissement des opérations est apparu de manière inattendue. Apparemment, travailler avec des données non natives (16 bits) dans cette architecture coûte beaucoup plus cher en temps qu'avec les natives (32 bits). Je n'ai pas mené une étude approfondie, mais le fait s'est produit et je devrais le signaler afin d'éviter tout malentendu.

Mais ce n'est pas tout. Puisque nous nous sommes déjà engagés sur la voie de la séparation et de la domination, alors pourquoi ne pas aller plus loin - extraire la racine des bits pas à pas, en commençant par les plus anciens (commencer par les plus jeunes est contre-productif dans notre cas). Le schéma d'algorithme est le même - nous ajoutons la portion suivante de bits dans le résultat actuel et essayons d'ajouter le bit suivant au résultat, en vérifiant si nous avons dépassé la valeur racine. La particularité est que nous ne pouvons vérifier que les bits hauts de l'argument, jusqu'à ce que nous arrivions aux bits bas.

Lors de l'implémentation, nous utilisons une astuce de plus - au lieu de déplacer nos nombres soustraits vers la droite, nous déplacerons notre argument décrémenté vers la gauche, la signification ne change pas et la vitesse augmente. Il augmente en raison de deux facteurs - 1) il nous suffit de soustraire uniquement des nombres à 16 bits (il y a une particularité, et il faut en tenir compte, mais nous envisageons une étude de cas, vout) et 2) nous n'avons pas besoin de déplacer le carré du bit suivant, car il sera toujours égal à un. Mais vous devez payer pour tout dans ce monde et nous aurons un décalage de la différence étendue (6 octets) vers la gauche, et de 2 bits par horloge. Voir pseudo code

1. valeurs initiales -> n = 0; H1 = 0;
2. répéter 16 fois -> (H1, H) << 2; T = H1-n-1; si (T> 0) {H1 = T; n = n + 2}; n << 1;

et évaluer le temps d'exécution, obtenant 16 * (12 (décalage étendu) +4 (calcul de la différence) +1 (solution) +2 (affectation) +1 (augmentation) +2 (décalage)) = 16 * 22 = 352 mesures, peut-être , le résultat est presque parfait. Lors de la mise en œuvre de cette option, il y a de petits pièges, je laisse à nouveau le lecteur curieux (enfin, il obtient le travail).

Eh bien, en conclusion de la section qui m'a incité à écrire ce post. Il y a une bibliothèque McuCpp absolument magnifique, rédigée par Anton Chizhov, dans laquelle, basé sur la classe d'auteur Loki, Andriescu est inhabituellement élégant (enfin, dans la mesure où l'élégance peut être appliquée aux modèles C ++), travaillez avec des épingles <a « github.com/KonstantinChizhov/ Mcucpp »J'ai beaucoup de respect pour l'auteur mentionné (tous les deux) et récemment, en relation avec les circonstances, dont je parlerai plus tard, j'ai regardé les sources de cette bibliothèque et j'ai encore une fois admiré.

Cependant, parmi d'autres fichiers, j'ai vu template_utils.h, dans lequel certaines routines auxiliaires ont été implémentées, et parmi elles une racine entière d'un nombre 32 bits. Le fait qu'il utilise l'algorithme d'approximation séquentielle le plus simple avec multiplication n'est pas effrayant, car cet algorithme ne perd pas beaucoup de vitesse, mais en termes de compréhensibilité, il donne beaucoup de points devant et gagne toujours. Mais je n'aimais pas vraiment le fait qu'il ait été mis en œuvre de manière quelque peu inexacte (en termes de performances), car "les enfants peuvent le voir". L'inexactitude consiste à représenter le nombre sélectionné avec 32 bits, car nous savons fermement que la racine du nombre 32 bits ne dépassera pas 16 bits, alors pourquoi devons-nous décaler zéro octet. Et c'est exactement le cas lorsque le compilateur lui-même ne devinera jamais d'effectuer une optimisation et devrait l'aider.

Conversion de fonction évidente

 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; } 

nous permet d'économiser 2 cycles sur un décalage de bit et 2 cycles sur la création du facteur suivant à chaque cycle, et l'organisation du cycle sous la forme indiquée est encore 4 cycles (je sais que le compilateur peut faire une telle optimisation pour nous, mais pourquoi ne pas l'aider explicitement ), ce qui est assez bon pour les modifications de code purement cosmétiques qui n'affectent en rien sa compréhensibilité.

Note ultérieure - un commentaire m'a fait penser que ce serait plus correct

  for (uint_fast8_t i= ...) 

Merci Oleg pour l'aide.

La cerise sur le gâteau est la fonction d'extraction de la racine carrée entière du numéro de signe situé juste en dessous, qui prétend que √-1 = 65635 = -1. D'un autre côté, pourquoi pas, ce qui est pire que tout autre résultat, nous n'avons pas d'exception cause dans MK, et la racine carrée entière d'un nombre négatif n'existe pas.

Eh bien, la conclusion sur la raison pour laquelle je me suis tourné vers la bibliothèque d'Anton Chizhov. J'ai été invité par un post récent concernant le RTOS domestique pour MK sous le nom MAX (MultiAgent Coherent System) - voir l'épigraphe du post annoncé par ses créateurs et porté sur le MK fabriqué par Milander. Remarque - ce message n'est en aucun cas du matériel promotionnel et il deviendra bientôt clair pour les lecteurs. Des auteurs mcucpp susmentionnés de l'OS ont utilisé la mise en œuvre d'un tampon en anneau (sans diminuer du tout les avantages de la bibliothèque Anton, je dois dire que cette partie n'est pas une référence, et c'est toujours une formulation douce, dont j'ai écrit dans un autre post que je ne publierai pas du tout). Comme je travaille en étroite collaboration avec les installations de production de Milander, le matériel m'a intéressé et j'ai suivi le lien vers le site Web des développeurs.

Ici commence le prochain cri de Yaroslavna.

L'année dernière, lorsque la création du RTOS national a été annoncée pour la première fois, j'ai téléchargé une description du produit logiciel à partir de ce site, mais d'une manière ou d'une autre mes mains n'ont pas atteint l'étude. De par la nature de mon activité, je dois gérer des composants domestiques (je comprends assez ...), donc ce serait bien d'avoir le logiciel approprié. Rappelant comment, dans la version de l'année dernière, le directeur de la société a parlé des millions de roubles dépensés pour le développement et de la grande équipe travaillant à la création de ce logiciel, j'ai décidé de voir la version d'essai disponible en téléchargement gratuit, et ici je partage les résultats.

Pour commencer, le descriptif semestriel a presque diminué de moitié en volume (de 115 à 55 pages), et si la disparition des applications avec des captures d'écran décrivant le processus de lancement de troisièmes produits de la «Description du programme» est la bienvenue, alors pas l'apparence de ces matériaux (pour la création desquels J'ai passé, bien que pas très important, mais encore du temps et de l'argent) dans un document tel que «Guide de l'opérateur», je suis personnellement perplexe. De plus, dans la toute première phrase du document, nous voyons une nette déviation de la vérité, puisque RTOS lui-même n'est pas destiné à "créer des programmes" de quelque manière que ce soit, pour une raison quelconque, les auteurs ne se sont pas permis de telles déclarations dans la version précédente du document, l'influence du service de marketing se fait sentir. Il fournit également que si la description était dans le dossier / docs du répertoire racine, et c'était logique, maintenant elle est cachée dans / toolchain / macs / docs, eh bien, comme ils l'ont dit dans ma jeunesse, "tout le monde est fou à sa manière", nous allons de l'avant.

Je commence à regarder la description, en regardant le code source (il est aimablement inclus dans la version d'essai) et, perplexe, je trouve l'absence de tout pilote de périphérique adapté pour fonctionner avec cet OS. J'ai d'abord suggéré qu'il s'agissait d'une fonctionnalité de l'essai, puis sur le forum dans les informations des développeurs, je trouve qu'il n'y a vraiment pas de pilotes, mais ils y travaillent. Plus de six mois (six mois, Carl, en fait près d'un an) à partir du moment où l'OS a été publié pour MK, et ils travaillent sur des pilotes. Naturellement, ou comme on dit, il va sans dire qu'on ne peut pas parler de produits tiers (système de fichiers, pile réseau, pile USB). Une idée amusante des auteurs sur les exigences de développement de logiciels pour MK, d'accord, a encore conduit.

Autrement dit, le système d'exploitation déclaré, dont la caractéristique mise en évidence est l'organisation de l'interaction au sein d'un système à plusieurs contrôleurs, ne dispose pas de moyens natifs pour organiser cette interaction. Ce que nous avons en fin de compte - et nous avons la gestion des tâches, en fait un sheduler, un service de temps minimal et des moyens de synchroniser les tâches, et c'est tout - drôle, pour dire le moins. D'accord, nous allons voir plus loin, même dans un tel ensemble de composants, des solutions intéressantes sont possibles, surtout si l'on considère que sur un site (pas l'entreprise du fabricant) j'ai vu un "examen" du code source de cet OS par référence. Ce document indique que le produit logiciel n'utilise pas de composants tiers (importation) et est original, il serait nécessaire de s'assurer.

La première observation est que si vous utilisez des fichiers ARM originaux inclus dans le package de code source pour porter sur une architecture Cortex-M0 spécifique (1986 BE1T), cela est très similaire à l'utilisation de fragments de texte tiers (importés) - je pense personnellement que c'est l'usage, mais Je ne sais probablement pas tout. Eh bien, et deuxièmement, le code source du sheduler et des composants de gestion des tâches connexes est vraiment original et n'a pas d'analogues (du moins je n'en connais pas), mais c'est le genre d'originalité quand je me souviens de la phrase du vieux chaman du film "The Evil Spirit of Yambuya" à propos de le grand chasseur: "Coupez les oreilles, faites cuire et mangez - auriez-vous deviné?"

Je vais essayer d'expliquer - dans la conception du système d'exploitation en général et dans le RTOS en particulier, l'un des problèmes complexes est celui de garantir l'accès de tous les processus du système à une ressource partagée - le temps d'exécution du processeur.Le fait est qu'un système mal conçu (et une tâche mal écrite) peut bloquer l'exécution de toutes les tâches avec une priorité inférieure, ce qui surprendra certainement le programmeur. Il ne s'agit pas d'effectuer des opérations interdites telles que le contrôle d'interruption (c'est un sujet pour une discussion séparée et n'a tout simplement pas de solution dans le cadre de MK simples, bien que les auteurs du système d'exploitation en question prétendent avoir résolu ce problème en utilisant le MPU), mais sur une exécution continue sans attendre.

, , , , . (1) , , FREE-RTOS 20 , ( , , ).

, , 60 ( ). , . ( ) , (, ) ,

1. (n)
2. — , 20*(3*4)=240 . , , , .

, , ( , , ) . , ( , ). mcucpp ( — ), .

La conclusion de cette section est que si d'autres décisions sur la substitution des importations dans le domaine des logiciels sont mises en œuvre de manière similaire avec des résultats de qualité similaire, les perspectives de construction de systèmes embarqués nationaux me semblent très mal définies.

En conclusion, je voudrais me tourner vers le manuel (non, pas un développeur de système d'exploitation, je ne veux même pas le mentionner à côté de bons développeurs) de l'entreprise-développeur et fabricant du MK-Milander mentionné. Vous faites de bons microcontrôleurs (je ne vais pas mentir, ils sont inférieurs en paramètres aux analogues étrangers, mais pas fatalement), par exemple, à un moment donné (en 2013) BE1T était presque le meilleur parmi les camarades de classe, mais dans la cour en 2019 et pendant ce temps, beaucoup l'ont rattrapé et dépassé.

Mais, si le bon MK produit par l'entreprise n'a pas:

1. ( , ) ( , , , , ),
2. ( ),
3. () 2,
4. HAL, CMSIS (- ),
5. ,
6. ,
7. (3rd part), ,
8. ,
9. ,
10. , (, , ..) « »,
11. , , ( , , MIT , « »), , (?).

, , , 5 ( , , 10, IDE). , , .

, , , .

, , () .